论文信息
论文标题：SCGC : Self-Supervised Contrastive Graph Clustering
论文作者：Gayan K.
Kulatilleke, Marius Portmann, Shekhar S. Chandra
论文来源：2022, arXiv
论文地址：download
论文代码：download
转自本人博客《论文解读（SCGC）《SCGC : Self-Supervised Contrastive Graph Clustering》
1 Introduction
为了利用结构中存在的丰富信息，许多研究人员将图神经网络(GNN)变体与AEs结合起来。这些方法存在的问题是：
- over-smoothing
- noisy neighbours (heterophily)
- the suspended animation problem
贡献：
- 提出一种有效的新型深度聚类模型
，消除了在整个学习层中携带结构/边缘信息的必要性；
- 提出了一种新的影响增强对比(IAC)损失来合并图结构，它可以有效地将任何模型转换为图感知； 提出了
，一种利用预学习质心的更精简的变体，它使用了一半的原始参数，显著提高了训练和推理速度；
2 Method
整体框架如 Figure 1 所示：
2.1 Graph structure by contrastive loss
对比损失使正或连通节点更近，负或不连通节点在特征空间中更远。基于此思想，将拓扑结构信息合并到嵌入中。
2.1.1 Influence Augmented Contrastive (IAC) loss.
考虑不同深度的节点之间的影响（相连或不相连），并考虑不可加性以及可加性。对于可加性，对于一个给定的 深度，总影响定义为：
其中， 为深度
处节点
之间关系的系数。
先前的GNN模型假设了一个固定的深度关系，即通过超参数搜索获得的单个 。然而，该层结构需要与潜在的影响结构保持一致。此外，GNN层普遍适用于所有节点，因此错误地假设了所有节点从不同的深度中获得相同的影响。因此，GNN模型往往不是最优的。此外，由于过度平滑，大多数GNN模型的深度不能超过
层，如 FDGATII [14] 和 GCNII[4] 试图解决这些模型。
给定 ，我们将
节点的
损失表示为：
其中， 为温度参数，
为节点
与
之间连接的影响。
对于每个节点，它的 邻域内的节点被认为是正样本，将其与所有节点进行对比。
损失鼓励有影响的节点在嵌入空间中比无影响的节点更近。接下来，概述了如何计算累积影响。
2.1.2 Determining Influence
由于真实世界的图通常非常稀疏，邻接矩阵 中的大部分项都是零。然而，在两个节点
和
之间没有一条边并不意味着没有关联；仍然可以有很强的关联，即：高阶接近度。这种直觉促使我们利用图中的高阶关系，通常通过将
提高到
次幂 [3,10] 来实现的。
的第
个条目给出了
长度的行走次数。
归一化邻接矩阵：
次幂提供了节点
和
之间的
跳关系的强度。
通过计算节点之间的累加关系作为节点关系强度，而不是限制在任意的第 跳邻域上。即，将归一化邻接矩阵的
次累积幂定义为
，其中，
。
包含了
中所有先前的邻域跳跃关系的聚合集。
只需要在训练之前计算一次，开销很少。另外，当节点
对节点
的
邻居产生非零影响时，
才能得到非零值。
与我们在影响方面的工作不同，Graph-MLP 提出了基于余弦相似度的 NContrast (NC) 损失进行分类，其中每个节点只考虑 邻域，而不考虑更全面的加性影响。其
的计算如下：
或
的对比损失定义为：
2.2 Self supervised clustering
图聚类本质上是一项无监督的任务，没有反馈来指导优化过程。为此，使用概率分布导出的软标签作为聚类增强的自监督机制，有效地将聚类叠加到嵌入上。
首先获得软集群分配概率 ，嵌入
和簇中心
，使用 student’s t -distribution 作为内核来衡量嵌入和质心之间的相似性，为处理不同的簇：
其中，簇中心 由预先训练过的 AE 的嵌入上的
经
初始化，
是 Student’s t-distribution 的自由度。使用
作为所有样本的聚类分配的分布，并在实验中设置
。
节点在 中具有更高的软分配概率，通过将
提高到二次幂并进行归一化，定义一个强调高置信度分配的目标分布
，将其定义为：
其中， 为质心
的软簇频率。
为了使数据表示更接近聚类中心，将 KL 散度损失用于 和
分布最小化，迫使当前分布
接近高置信度的目标分布
。通过使用分布
来实现目标分布
来自监督簇分配，然后通过最小化 KL 散度来依次监督分布
，如下：
2.3 Initial centroids and embeddings
为了提取节点特征并获得初始嵌入 和聚类质心
进行优化，我们采用了基于AE的预训练阶段。首先，我们使用编码器-解码器通过最小化原始数据
和重建数据
重构损失来提取潜在嵌入
，即：
2.4 Final proposed models
2.5 Complexity Analysis
给定输入数据维数 和 AE 层的维数为
，第一个编码器层的权重矩阵大小为
。当输入数据大小为
时，
的时间复杂度为
，
的时间复杂度为
。假设
聚类，从
可知，时间复杂度
。
对于对比损失，我们计算了所有 的
和
。因此，时间复杂度为
，其中
是嵌入维数。虽然这导致了理论时间复杂度为
，但鉴于
是对称的，我们只需要计算一半的结果，并且由于矩阵的转置是相同的、索引交换的矩阵，缓存可以产生超过两倍的影响。
3 Experiments
数据集
4 Conclusion
本文介绍了影响增强对比(IAC)，这是一种新的图表示的自监督学习方法。它的可加性使更强的归纳偏差能够进行泛化，而不需要近似复杂图的潜在依赖关系和关系结构。使用IAC，我们的SCGC*比传统的基于GNN的方法提供了显著的优势；SCGC可以自然地适应本地、长期或任何节点依赖的混合组合，支持批处理，高效，具有线性推理的复杂性，并且可以简单地并行化。SCGC与先进技术相比取得了显著的改进(DBLP的NMIARI为18%，ACM训练时间减少了69%，训练时间减少了55%，推理时间减少了81%)。通过展示对比学习、聚类[2,27,29]和自动编码器模型[6,9,30]之间有效的图聚类的新可能性，我们希望为这些领域的模型改进提供灵感和指导，并解决本文概述的一些局限性。
文章出处登录后可见！
