Graph Clustering with Graph Neur

摘要

图神经网络（GNN）在许多图分析任务（例如节点分类和链接预测）上均取得了最新的成果。然而，事实证明，图上的重要无监督问题（例如图聚类）更能抵抗GNN的发展。在本文中，我们研究了基于聚类能力的GNN池的无监督训练。

我们从绘制图集群和图池之间的联系开始：直观地讲，良好的图集群是GNN池层所期望的。与直觉相反，我们表明对于最先进的合并方法（例如MinCut合并），情况并非如此。为了解决这些不足，我们引入了深度模块化网络（DMON），这是一种不受监督的池化方法，其灵感来自于聚类质量的模块化度量，并展示了其如何解决现实世界中具有挑战性的聚类结构的恢复。为了阐明现有方法失败的情况，我们仔细设计了一组针对合成数据的实验，这些实验表明DMON能够联合利用图结构和节点属性中的信号。同样，在现实世界的数据上，我们表明DMON产生了高质量的群集，这些群集与地面真相标签紧密相关，从而获得了最新的结果。

1引言

近年来，对于开发各种图形神经网络（GNN）的研究兴趣激增，这些神经网络是用于处理图形结构化数据的专用深度学习架构，例如社交网络[47]，推荐图[68]或分子图[13，69]。 GNN利用数据的结构作为计算图，从而允许信息跨图的边缘传播[49]。当许多实壁系统以图形表示时，它们会表现出局部的边缘不均匀分布，从而形成簇（也称为社区或模块），即具有高组内边缘密度和相对低组外密度的节点组。聚类可以对应于基础图中有趣的现象，例如对应于社会图中的教育[57]或就业[41]。 GNN已显示出受益于利用来自聚类[9、69、31]的高阶结构信息，例如通过集中或边缘上的可训练注意力[60]。

有趣的是，大多数现有的关于GNN的工作都利用高阶结构，并没有直接解决节点分区或计算图中聚类的估计问题。此外，大多数工作都只在半监督或监督框架内探索这些机制，而忽略了无监督图聚类本身通常是极其有用的最终目标这一事实–无论是用于数据探索[45]，可视化[11，12]，基因组特征发现[7]，异常检测[44]或讨论的许多其他用例，例如在[19]中。另外，许多现有的结构感知方法具有不良的特性，例如依赖于多步优化过程，该过程不允许通过端对端的梯度下降来优化目标[46]。

在这项工作中，我们从头开始解决GNN域中的聚类问题，弥合了传统图聚类目标和深度神经网络之间的差距。我们首先绘制图池之间的联系，图池通常在文献中作为有监督的GNN体系结构的正则化器进行研究，而后者则是完全无监督的聚类。具体来说，我们贡献：

•DMON，一种用于GNN中无监督聚类的方法，允许以端到端的可区分方式优化聚类分配。

•对综合图性能的实证研究，说明了现有工作的问题以及DMON如何在这些情况下改善模型性能。

•对实际数据进行全面的实验评估，表明许多池化方法无法很好地反映层次结构，无法同时使用图结构和节点属性。

2相关工作

我们的工作基于对图神经网络和图池化方法的大量研究。

图神经网络（GNN）[49、15、40、21、29]允许对具有任意结构的数据进行端到端的不同损失。它们已被应用到从社交网络[47]到推荐系统[68]到计算化学[21]的各种应用。尽管GNN具有足够的灵活性以允许无监督的损失，但大多数工作遵循[29]中节点分类的半监督设置。要完整地介绍这个庞大的主题，我们请感兴趣的读者进行详细的调查[6，25，8]。

GNN的无监督训练通常是通过以自我监督的方式最大化相互信息[3，26，58，54]来完成的。 Deep Graph Infomax（DGI）[61]改编自Deep InfoMax [26]的基于互信息的学习，学习属性图中节点的无监督表示。 InfoGraph [56]将这个想法扩展到学习整个图形的表示，而不仅仅是学习节点。在[27]中，在预训练GNN来生成图形表示的背景下独立引入了一种非常相似的方法，该方法首先在[36]中解决。

图池旨在通过迭代粗化来解决图的层次性。早期的体系结构[13]采用固定的公理化池，在网络学习时没有优化聚类。 DiffPool [69]建议将可学习的池包含到GNN架构中。为了帮助收敛，DiffPool包括一个链接预测损失以帮助封装图的聚类结构，以及一个附加的熵损失以惩罚软分配。 Top-k [20]和SAG池[31]通过学习的权重来稀疏图（为每个节点选择top-k边）。 MinCutPool [4]合并研究了将频谱聚类作为合并策略的可区分公式。

我们根据与聚类能力相关的六个理想属性，总结了表1中的主流图形池化方法：

•可训练的。端到端训练允许捕获图结构和节点特征。

•无监督训练是聚类模型的理想设置。有监督图聚类[66，62]的工作不在此工作范围之内。

•稀疏。由于现实世界中的图在大小和稀疏性上各不相同，因此方法不受O（n2）链接预测目标（如DiffPool [69]）或计算A2（如top-k池化方法[20，31]）的限制。

•节点聚合对于我们根据图聚类来解释图池至关重要。 Top-k [20]和SAG池[31]都仅使图稀疏，并且不减少节点集。

•软分配可提供有关集群交互的更多灵活性推理。

•稳定–该方法在图形结构方面应该是稳定的。 DiffPool [69]在图形稀疏性方面不稳定，而MinCutPool [4]无法处理不均匀度分布。

图嵌入[48、23、59]可以被认为是具有身份特征矩阵的（非常受限制的）无监督GNN，这意味着每个节点都可以学习自己的位置表示[70]。通过噪声对比估计[24]，图嵌入中的学习过程通常以与DGI相似的方式进行。据我们所知，所有用于学习没有属性的节点嵌入的合并策略都是不言而喻的[10、33、14]。

3初步

我们将介绍DMON的必要背景，从问题表述开始，回顾常见的图聚类目标以及如何有效地使它们可区分。

通过一组节点V =（v1，...，vn），| V |定义图G =（V，E）。 = n，边E⊆V×V，| E | =米我们对测量图分区函数F的质量感兴趣：n→k将节点集V分成k个分区Vi = {vj，F（vj）= i}。另外，与标准图聚类相反，我们还提供了节点属性X∈Rn×s，这些节点属性提供了不仅未反映在图结构中而且与之相关的其他信息。

3.1图聚类质量函数

目标函数的设计对于算法性能至关重要。我们回顾了两个适合频谱优化的聚类质量函数族，并回顾了它们的一些缺点。

基于切割的指标。 Fiedler在开创性的工作中[18]建议，图拉普拉斯算子的第二个（Fiedler）特征向量产生的图在边的权重方面被最小化。剪切的这种简单概念在现实世界的图形上会退化，因为它不需要分区就大小进行平衡。可以使用比率切割[63]来归一化的分区，该比率通过两个分区中节点数的乘积对切割进行归一化，或使用分区的总边缘体积作为归一化的归一化切割[52] 。

然而，在真实的网络中，有证据表明在真实的社区中存在良好的切入点[32]。这可以由以下事实来解释：单个节点隐式地参与了许多不同的集群[17]，例如。社交网络中的一个人同时与家人和工作朋友联系在一起，从而迫使算法将这些社区合并在一起。

最近，MinCutPool [4]修改了归一化剪切的概念以用作合并的正则化器。虽然从理论上讲，MinCutPool目标应该适合于图中的节点聚类，但我们（i）表明它并没有优化其自身的目标函数，并且（ii）在综合实验和实际实验中提供了针对此目标的证据。

模块化[38]从统计角度解决了相同的问题，并引入了一个空模型来量化相对于随机图的聚类的重要性。在具有给定度数的完全随机图中，度数为du和dv的节点u和v以概率dudv / 2m连接。模块化度量群集内部边缘与预期边缘之间的差异：

如果i和j在同一群集中，则δ（ci，cj）= 1，否则为0。注意Q∈（−1/2; 1]（当聚类与边缘密度不相关时为0），但不一定在1处最大化，并且仅在具有相同度分布的图之间具有可比性。模块化度量已被确定[22]，它仍然是科学文献中最常用和最有用的图聚类度量之一[19]。

3.2频谱模块化最大化

模块化的最大化被证明是NP难的[5]，但是，该问题的频谱松弛可以有效地解决[37]。令C∈0，1n×k为聚类分配矩阵，d为度向量。然后，通过将模块化矩阵B定义为B = A-dd⊤，可以将模块化Q重新表示为：

放宽C∈Rn×k，最大化Q的最优C是模块化矩阵B的前k个特征向量。当B密集时，迭代特征值求解器可以利用B是a的和的事实。

稀疏A和秩一矩阵-dd⊤，意味着可以计算矩阵向量乘积Bx

高效地

2mBx = Ax −d⊤xd2m

并通过幂迭代或Lanczos算法等迭代方法进行有效优化。然后可以通过光谱二等分[37]获得具有类似于Kernighan-Lin算法[28]的迭代细化的聚类。但是，这些公式完全在图结构上运行，并且使它们适合于使用归因图并非易事。

3.3图神经网络

图神经网络是一类灵活的模型，可针对图结构执行非线性特征聚合。出于这项工作的目的，我们考虑了转导性GNN，每个节点输出一个嵌入。图卷积网络（GCN）[29]是简单而有效的[51]符合我们标准的消息传递网络。设X0∈Rn×s为初始节点特征，A ̃ = D-1 AD-1为归一化邻接矩阵，则第t层Xt + 1的输出为

Xt + 1 = SeLU（A ̃XtW + XWskip）（3）

我们对经典的GCN架构进行了两项更改：首先，我们删除了自循环的创建，而是使用Wskip∈Rs×s可训练的跳过连接；其次，我们将ReLU非线性替换为SeLU [30]，以实现更好的收敛性。

4方法

在本节中，我们介绍DMON，这是一种使用图神经网络进行属性图聚类的方法。受模块化功能及其频谱优化的启发，我们提出了一个完全可微分的无监督聚类目标，该目标使用空模型来控制图中的不均匀性来优化软聚类分配。然后，我们讨论了对聚类分配进行正则化的挑战，并提出了针对琐碎解的崩溃正则化（正交性损失的较软版本）。

4.1 DMON：深度模块化网络

聚类的挑战归结为在聚类分配矩阵C上定义优化过程。在DMON中，我们建议通过softmax函数的输出获得C，从而允许（软）聚类分配是可微的。群集分配的输入可以是任何可区分的消息传递函数，但是在此我们专门考虑使用图卷积网络为每个节点获取软群集的情况，如下所示：

C = softmax（GCN（A ̃，X）），（4）其中，GCN是（可能）在归一化邻接关系上运行的多层卷积网络

22矩阵A ＝ D-1（A）D-1。

然后，我们建议以以下目标优化此分配，该目标结合了频谱模块化最大化（2）和正则化的见解，以确保提供信息丰富的集群：

  ∥·∥F是Frobenius范数。我们将Tr（C⊤BC）的计算分解为稀疏矩阵矩阵乘法和秩一度归一化Tr（C⊤AC-C⊤d⊤dC）之和。这使我们能够在稀疏状态下有效地优化DMON参数。

4.2折叠正则化

在分配矩阵C上没有其他约束的情况下，最小切割和模块化目标的频谱聚类具有虚假的局部最小值：将所有节点分配给同一聚类会产生琐碎的局部最优解，该解会捕获基于梯度的优化方法。 MinCut池[4]通过以软正交[2]正则化􏰃􏰃C⊤C-I􏰃􏰃F的形式适应频谱正交性约束来解决此问题。我们注意到，与softmax类分配结合使用时，该术语的限制过于严格-直观地讲，当C的值范围限制为R∩[0，1]时，软正交正则化器的优化将主导损失。

我们在图1中说明了这个问题，该图描述了在Cora数据集上200个历元的过程中，这两种方法的主要目标和正则项的优化过程。软正交正则化项主导了MinCutPool的优化，因此在训练过程中，剪切目标变得比随机目标差。

我们通过提出一种宽松的崩溃正则化概念来解决此问题，该概念可以防止琐碎的划分，同时又不限制主要目标的优化。正则化器是（软）集群成员计数的Frobenius范数，规格化为范围[0，1]。当群集大小达到完美平衡时，其值为0；在所有群集崩溃为1的情况下，其值为1。我们还建议通过在softmax之前对GNN表示应用dropout [55]来稳定训练，防止梯度下降卡在高度非凸目标函数的局部最优中。

5个实验

我们根据图聚类和标签对齐来评估DMON的聚类性能。我们在此URL2上发布DMON的实现。

数据集。我们使用7个真实的数据集来评估模型质量。 Cora，Citeseer和Pubmed [50]是引用网络。节点代表通过引证边连接的论文；功能是词袋摘要，标签代表论文主题。 Amazon PC和Amazon Photo [51]是网站上计算机和照片部分的Amazon共同购买图的子集，其中节点代表

经常一起购买的边缘之间的商品；节点功能是“袋中评论”，类别标签是产品类别。合著者CS和合著者PHY [51]是基于Microsoft Academic Graph的共同著作权网络，分别用于计算机科学和物理学领域。节点是作者，如果他们共同共同撰写论文，则它们由边连接；节点功能是作者论文的论文关键词的集合；班级标签指示最常见的研究领域。

基线。当我们研究如何利用来自图和属性的信息时，我们采用两个使用严格图或属性信息的基线。我们简要介绍以下使用的基准：

•k-均值（特征）是我们的基准，仅考虑特征数据。我们将本地劳埃德算法[34]与k-means ++播种[1]策略结合使用。

•SBM [42]是仅依赖于图形结构的基线。我们估计了给定k个簇的数量的约束随机块模型，从而最大化了网络的模块化[38]。

•k-means（DGI）[61]证明了联合学习聚类和表示的必要性。我们使用DGI学习无监督的节点表示形式，并对所得表示形式运行k-means。 •MinCutPool（图形，功能）[4]是一种深度池化方法，我们将其重新解释为聚类。

指标。我们测量基于图的聚类和标签相关性的度量，以研究图和属性结构方面的归因图的聚类性能。对于图级度量，我们报告平均群集电导（根据[64]的定义）和图模块化[38]。对于地面标签相关性分析，我们报告了群集分配和标签之间的归一化互信息（NMI），以及所有节点对及其关联的群集对之间的成对F-1分数。在可能的情况下，我们将所有指标乘以100进行归一化，以方便比较。

参数设置。我们将所有实验进行了10次，并得出各次实验的平均结果。所有模型均在Tensorflow 2中实现并在CPU上进行了培训。我们修复了所有群集网络的体系结构，使其具有一个隐藏层，其中包含512个神经元的真实世界数据集和64个隐藏层的小型合成图。我们将所有数据集和方法的聚类数设置为16。

5.1随机块模型的仿真实验

为了更好地探索图和节点特征方差的稳健性，我们提出了使用归因度校正的随机块模型（ADC-SBM）对合成图进行的研究。 SBM [53]在图形中植入群集的一个分区（“块”），并通过以该分区为条件的分布来生成边。该模型已被广泛用于基准图聚类方法[19]，最近已用于最新的GNN的实验[16]。在我们的模型版本中，还使用多元混合模型来生成节点特征，其中混合成员与聚类成员具有某种对应关系。

为了生成ADC-SBM的实例，我们固定了多个节点n和多个群集k，然后均匀地随机选择节点群集成员。定义矩阵Dk×k，其中Dij是群集i和j中节点之间共享的预期边数。我们通过固定（1）节点的期望平均度d∈{1，n}和（2）阳极的期望平均子度dout≤d到任何其他群集来确定D。团簇的光谱可检测性[35]。最后，我们生成幂律n矢量θ，其中θi与i的期望度成正比。具有隶属度和参数D和θ。我们使用图工具[43]生成图。

为了生成s维特征，我们首先从kf聚类标签生成特征成员资格。对于同时在边缘和节点特征上运行的图聚类GNN，重要的是检查在特征聚类与图聚类不同或对图聚类进行分割的数据上的性能：因此，潜在kf̸= k。我们检查了特征成员资格与图成员资格匹配，分组或嵌套的情况，如图3所示。有了现有的成员资格，我们可以从s个多元协方差矩阵σc2·Is的法线生成k个零均值特征簇中心。 ×s。然后，对于特征簇i≤kf，我们从具有协方差矩阵σ2·Is×s的s多元法线生成特征。注意，比率σc2/σ2控制群集的平方之间/平方和内的经典值的期望值。

上面的段落描述了我们的综合基准模型的一代ADC-SBM。为了探究鲁棒性，我们定义了一个“默认” ADC-SBM，并在默认范围内探索模型参数。我们将默认模型配置如下：我们生成的图的n = 1，将000个节点分组为k = 4个群集，将s = 32维特征分组为kf = 4个匹配特征群集，其中σ= 1群集内中心方差和σc= 3聚类中心方差。我们尝试使用幂律参数dmin = 2，dmax = 4，α= 2来模拟d = 20平均度和dout = 2平均群集间度的真实世界图的度分布。总共考虑了6种不同的情况，如表4所述。

  图5展示了在所有考虑的场景中DMON的压倒性优势。在方案1中，我们看到DMON可以有效地利用特征信号来获得出色的聚类性能，即使图形结构接近随机，也远远超出了光谱可检测性阈值（以灰色显示）。方案2证明，即使存在弱特征信号，DMON的性能也优于随机SBM最小化，而MinCutPool需要两个强度更高的信号才能达到相同的性能。方案3演示了DMON不易受嵌套要素群集的影响，并且可以正确恢复基础图结构。场景4显示DMON更容易受到分组特征的影响，因为很难区分具有相似特征的图簇，但是，MinCutPool努力获取数据中的任何信号。场景5和6证明了DMON在图形的度分布方面是稳定的，而MinCutPool不是。我们还注意到，尽管k均值（DGI）基线相对于单独使用功能或图形结构提供了一些改进，但它从未超过图形中最强的信号提供者，也从未比kmeans（特征）和SBM之间的最佳信号提供者更好。最后，我们提供了一个示例，说明了DMON在图4中成功实现时MinCutPool如何崩溃为一个集群。

5.2实际数据

现在，我们继续进行现实网络的研究，以7个不同数据集的DMON和4个基线为特征。在每个数据集和指标上，DMON均比其神经同类产品具有更好的聚类性能，而且就NMI而言，DMON在Cora和Citeseer上的DGI + k-means损失了两次。与专门优化模块化的方法SBM相比，我们可以将NMI保持在2个百分点以内，同时可以对功能进行聚类。出乎意料的是，在Citeseer和Pubmed上，我们实现了比为优化模块而设计的方法更好的模块化性–我们将其归因于图结构与功能之间的高度相关性。我们还强调指出，即使在尝试针对该指标进行优化时，我们在所有数据集的电导率（平均图形切割）方面都击败了MinCutPool。

在Amazon PC和Amazon Photo上，即使调整正交正则化参数，MinCutPool也无法收敛。我们认为这是由于这些图的结构极不平衡，因为流行产品与许多其他物品共同购买，因此[17，32]中讨论的效果会妨碍良好的削减。这对应于我们的合成方案5和6中的d ad dmax的高值。

总体而言，DMON在图形聚类和标签关联方面均表现出出色的性能，成功地利用了图形和属性信息。合成和真实世界的实验都证明，DMON在归因图聚类方面远远优于其同类产品。

六，结论

在这项工作中，我们将通过属性图聚类的角度研究GNN池。我们引入了非模块化目标深度模块化网络（DMON），并使用可以恢复高质量集群的GNN来实现。除了最近提出的最新池化方法（MinCutPool）外，我们还与具有挑战性的基准进行了比较，即优化结构（SBM），特征（kmeans）或同时优化这两种结构（DGI + k-means）的基准。

我们使用合成数据在图形和特征信号方面探究了GNN聚类方法的局限性，我们发现DMON比所有现有方法都更好地利用了结构和属性。在真实数据集上进行的广泛实验中，我们表明DMON发现的群集更可能与地面真相标签相对应，并且具有更好的属性，如群集指标（例如电导或模块化）所示。我们希望这项工作将在GNN的无监督学习以及归因图聚类方面取得进一步进展，从而允许图学习进一步发展。

影响更广

我们相信，通过属性图聚类的镜头更好地理解图池将有助于设计更有效的图神经网络体系结构。我们的改写鼓励对图中的节点进行显式分组，我们设想这将在具有自然存在的社区结构的域中有用，例如社交网络或信息检索。此外，我们的M-GCN可以充当半监督体系结构中的“图形上下文”头衔[67]，从而在这些系统中允许基于社区的更严格的约束。

我们的工作还允许翻译网络科学中有关将属性图聚类到GNN域的开放性问题，从而有可能实现功能强大的新建模解决方案。具体而言，现有的用于属性图聚类的组合[65]和贝叶斯[39]方法使用图特征来提高聚类的准确性。 [39]表明使用特征允许他们基于估计的方法克服图形[35]的频谱“可检测性”限制，我们在这项研究中重复了这一结果。使用我们的模型，网络科学界的更多想法可能会移植到GNN架构中。