内容纲要

谱聚类是一种很流行的方法,然而特征分解的代价非常昂贵,因为聚类结果都是图相关的,基于SC的池化方法对于每个新的样本都要采取新的优化方法。这篇论文中,我们提出一种图聚类方法,我们公式化连续性松弛和归一化的minCUT问题,然后训练一个GNN来计算簇类的分布减少目标函数。我们的GNN方法是可微的,不需要计算谱分解。另外提出一个图池化的方法。

introduction

已经存在的model-free方法只考虑了图拓扑i结构,但是node feature没有考虑,同时基于模型的方法大都基于遗传。结果,前者无法学习如何为特定的下游任务自适应地粗化图,而后者则不稳定并且即使在简单任务上也容易找到退化的解决方案.
SC没有明确考虑节点属性,并且拉普拉斯算子的特征分解是不可微且昂贵的操作。
我们制定了标准化minCUT问题的连续松弛,并通过优化此目标训练了GNN以计算聚类分配。我们的方法学习了SC找到的解决方案,同时还明确考虑了节点特征以识别集群。 同时,我们基于GNN的实现是可微的,不需要计算拉普拉斯算子的昂贵频谱分解,因为它利用了可快速计算的空间局部图卷积。 这还允许仅通过评估学习的函数即可将样本外图的节点聚类。
从提出的聚类方法中,我们派生了一个名为MinCutPool的基于模型的池化运算符,它克服了无模型和基于模型的池化方法的缺点。 通过最小化minCUT目标来学习MinCutPool层中的参数,可以将其与特定于任务的损失共同优化。
在后一种情况下,minCUT损失是一个正则项,可以防止退化的解决方案,并且GNN可以在特定任务和聚类目标之间找到最佳折衷方案。 由于它们是完全可区分的,因此可以将MinCutPool层堆叠在GNN的不同级别上以获得分层表示,并且可以端对端地训练整个体系结构(图1)。 我们对各种无监督和受监督的任务进行了比较研究,结果表明MinCutPool导致了对最新池化方法的重大改进

背景

图神经网络

作者采取最基本的消息传递作为网络,file

minCUT

最小割问题:移除最少的边,将图节点分割成K个不相交的子集。
也就说,问题最大化:file
如果用Cij表示簇类分配矩阵。则最小割问题可以描述为:
file
其中上个问题是NP-hard,因此我们可以通过下式得到近似解:
file
上式仍然是非凸的,存在一个最优解Q,其中Q分解成两个矩阵。

谱聚类

谱聚类获得聚类分配,通过应用K-mean算法到最优解Q的每一排,最大的限制是计算A的谱获得Q。
为了针对SC的可扩展能力。4
可以通过梯度下降的算法来得到解,有通过正交约束或者沿着测地线距离更新。另一个基于QR格式化的方法是约束可行解的空间,或者满足minibatch中的理论。
为了寻找合适的谱聚类方法,很多使用神经网络。比如自编码器来训练Laplace的第i行映射到前K个特征向量的第i个成分。或者定义一个正交约束学习谱嵌入。还有就是定义损失函数的,但这些方法都不是端到端的方法,不适合pooling。

方法

图拓扑结构,相似的特征应该相互靠近,不相似的特征应该远离。
定义Xbar为节点矩阵,通过一个或者多个消息传递层产生,我们计算节点的簇类分类分数,通过一个多层感知器+softmax,将节点特征映射到簇类分配矩阵S的第i行:
file
其中两个Θ都是可训练的参数,softmax保证第三个公式的约束。我们注意到可以添加一个temperature参数到softmax上来控制si应该靠近one-hot向量多少,也就是说,簇类分配的模糊程度。
通过无监督的方法来训练上述两个参数,有点像最小割问题:
file
cut loss项Lc,通过soft的簇类分配S,评估minCUT,边界为file减少Lc鼓励强连接的节点聚集到簇类,因为当aij大时,si sj的内积增大。当file时。Lc有着单个最大值。这在下属情况下会发生,如果对于每一对相连的节点(aij>0)簇类分配都是正交的。当如果分子分母两个矩阵的迹相等时,Lc达到最小值-1,当在具有K个不连接的组件的图中,群集分配对于相同成分中的所有节点均相等并且与不同成分中的节点的群集分配正交时,就会发生这种情况。
但是Lc时非凸的,很容易陷入局部最小值。比如把所有的节点全都赋予同一个类别,或者每个节点都被同等的赋值到所有簇中。
为了惩罚Lc,加入正交项L0,使得簇类分类更加正交和簇的尺寸差不多大。因为L0有着一元的范数,因此Lo的范围0-2。因此两个损失是可相当的,直接对两项进行相加而不需要引入额外的weights。Ik可以认为是rescaled的矩阵,file其中S为N/K个点到每个聚类,Frobenius范数度量和簇类大小无关,因此可以用于优化intra-class的偏差。

池化和图粗化

使用簇类分配矩阵S来生成一个图的粗糙版本。
粗糙的临界矩阵和池化的节点特征通过下述方式来计算:
file
aii^pool表示簇内之间的加权边,aij_pool表示簇间之间的加权边。这样的话,A pool的迹表示了很多内部的连接儿很少关注之间的连接,因此A将会是一个对角矩阵,描述一个图有着很强的自环连接,这样会阻止邻居节点的信息传报,因此我们计算一个新的邻接矩阵,通过中心化对角线和应用度归一化。file

注释

  1. Lo的存在会使得非凸的Lc寻找最优解
  2. 簇聚类有着强烈连接的将会有相似的特征,减少发现次优解的风险。
  3. Lc的次优解也可以通过使用task-specific的损失来避免
  4. minCUT目标函数更像是一个正则项,可以通过下游的损失任务来联合进行优化。
最后修改日期:2020年12月14日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。