牛商的网站后台,室内设计女孩子学难吗,注册网站要注意什么,百合居装饰公司官网论文地址#xff1a;SCGC : Self-supervised contrastive graph clustering - ScienceDirect
代码地址#xff1a; https://github.com/gayanku/SCGC 摘要
图聚类旨在发现网络中的群体或社区。越来越多的模型使用自编码器#xff08;autoencoders#xff09;结合图神经网…
论文地址SCGC : Self-supervised contrastive graph clustering - ScienceDirect
代码地址 https://github.com/gayanku/SCGC 摘要
图聚类旨在发现网络中的群体或社区。越来越多的模型使用自编码器autoencoders结合图神经网络GNN来实现有效的聚类并将结构信息融合进来。然而基于卷积或注意力变体的GNN在动态融合方面存在不足容易出现过度平滑、噪声、节点异质性等问题计算开销较大且通常需要完整图结构的存在。为此作者提出了SCGC模型它通过无增强的边对比损失实现动态的软结构融合。此外还提出了SCGC*它采用了更具表现力的新型距离度量——影响力Influence并结合作者的影响力增强对比IAC损失所需的模型参数仅为原来的一半。SCGC和SCGC*模型能够动态融合具有辨别性的节点表示共同细化软聚类分配完全消除传统GNN中的卷积和注意力机制仅使用简单的线性单元却能高效地融合结构信息。它们对层深度不敏感具有较强的鲁棒性能抵抗过度平滑、错误边缘和异质性问题支持批处理且无增强放宽了同质性假设并能轻松并行化。作者在多个基准测试上显著超越了现有最先进的技术包括图像、传感器数据、文本和引用网络且效率非常高。具体而言DBLP上的ARI提升了20%NMI提升了18%训练时间总体减少了55%推理时间总体减少了81%。
引言
图研究因其高表达性和图结构数据的普遍性而受到越来越多的关注[1]。图的独特非欧几里得数据结构非常适合表示多样化的特征丰富的领域用于机器学习[2]。许多现实世界的任务如引文网络、社交网络和蛋白质-蛋白质相互作用分析都依赖于图数据挖掘技术。图聚类通过将相似的节点分配到不同的组中来发现网络中的群体或社区[2]。聚类已被广泛应用于图像[3,4]、文本[5,6]和社交网络[7,8]。到目前为止基于自编码器AE的深度聚类方法[6,9-11]已取得了最先进的性能。
为了利用结构中丰富的信息许多研究者[2,6,11,12]将图神经网络GNN与自编码器AE结合使用[13]。尽管这些模型在聚类上取得了最先进的结果但由于a过度平滑b噪声邻居异质性和cthe suspended animation problem[1]GNN在结构融合中的依赖性存在挑战。GNN通过堆叠层[14]促进不直接连接的节点之间的交互从而导致过度平滑使得节点表示变得不可区分原因是过度混合[15]。为了缓解这一问题大多数GNN是浅层的无法从深层模型中受益。像GCNII[16]和FDGATII[1]这样的模型可以实现更高的深度但仍然需要预先确定适当的深度并使用计算开销较大的卷积或softmax注意力操作。
众所周知结构信息表示了节点之间的潜在依赖关系[6]。然而这种依赖关系可以是直接局部依赖也可以是间接非局部依赖涉及一个或多个任意组合的阶数。因此使用固定的预选择卷积或其他层结构来逼近这种不可预测的潜在结构并非易事。最近更多的研究者转向了更简单且高效的模型实现[4,15,17]。尽管已有研究[4,18]使用对比损失来学习图嵌入但它们使用了昂贵的增强操作并包含了基于卷积的GNN形式。 在这项工作中如图1所示作者展示了如何从主训练循环和推理中消除先前工作的GNN和AE同时仍能在自监督图聚类中获得最先进的成果。作者通过无增强的边对比损失来融合结构避免复杂的融合操作还能够使用更简单的单一自监督。作者提出的深度聚类方法通过无增强的边对比损失学习动态的软结构融合以强制执行图结构和聚类优化而不是尝试匹配潜在的节点依赖动态。作者提出了两个模型SCGC和SCGC*。在SCGC中使用1-hop信息进行软结构融合并保留AE如先前工作中所述。在SCGC中通过提出的IAC损失使用聚合的多跳信息称之为影响力并丢弃了AE。具体来说在SCGC中使用最少的预训练30个epoch子批处理嵌入来有效且高效地替代训练过程中的AE。对于结构和特征融合引入了一种新型的对比损失度量——影响力并定义了具有放宽同质性假设的影响力增强对比IAC损失。此外使用了基于软标签的自监督机制。
SCGC在计算上是高效的因为它由简单的线性层MLP组成。没有昂贵的卷积、softmax操作或增强。无需通过模型传递邻接信息从而将模型结构与潜在的节点依赖结构解耦。因此SCGC结构可以在不同数据集之间保持不变正如通过使用图像、文本和图模式的基准数据集所展示的那样。SCGC非常适合边缘和资源受限的应用。通过仅使用无增强的对比损失进行软结构融合SCGC对噪声边缘具有更强的鲁棒性。此外由于使用基于概率分布的自监督机制该模型也对特征噪声和类别/标签噪声即异质性具有较强的鲁棒性。我们的主要贡献包括
提出了一种新型的深度聚类模型SCGC消除了传统GNN在图聚类中的需求。SCGC完全将结构与图解耦并将其转移到一个方便的损失函数中。引入了影响力度量作为复杂图结构的简单而强大的代理提供了高效的计算过程并提出了具有理论见解的影响力增强对比IAC损失并展示了其实验优势。在6个基准测试包括图像、传感器数据、文本和引文网络数据上的实验表明SCGC在准确性、训练和推理效率上超越了现有最先进的图聚类方法。
尽管现有的深度图聚类方法通常使用基于AE的重构损失最小化[20]作者证明了AE仅在最小初始化30个epoch时是必要的并且作者的训练和推理阶段不需要AE。此外通过学习一个结构感知的变换图信息在推理时不再是必需的因此作者的模型对节点的缺失连接具有较强的鲁棒性。此外大多数对比模型使用SimCLR[16]的噪声对比估计NCE方法需要增强视图通常每个epoch都需要增强并假设数据是独立同分布IID的。其他模型假设连接的节点是相似的同质性。相反作者使用通过作者新颖的影响力度量学习到的软局部-全局结构融合。通过使用有效的基于损失的模型来传递结构能够使用简单的MLP避免了昂贵的增强、卷积和注意力机制。最终的模型更加高效和快速。SCGC同样适用于图像、文本和图数据。
模型 对于图中任意两个节点 i 和 j不失一般性地假设节点 j 距离节点 i 有 R 个跳数hop如图 2(a) 所示节点 j 的邻域信息需要通过中介节点 p,q,r,s传递才能到达节点 i。为了实现这一点GNN图神经网络架构在训练和推理阶段携带并使用结构信息例如通过邻接矩阵或消息传递。同时堆叠层被用来增加感受野receptive field并覆盖多跳节点。然而这种结合模糊了特征的重要性[25]并且导致当前最先进模型中复杂的结构和计算开销[4]如图 1 所示。
相反作者提出一个单一的综合值来表示 i 和 j 之间的所有交互。实际上就是一个单一的标量如图 2(a) 所示记作 γij。这可以通过用一组值替代图结构来极大地简化图结构每条实际的图边 i,j对应一个标量值。由于现实世界的图通常是非常稀疏的邻接矩阵 A 大多数元素为零[31]因此使用边edges进一步提高了可扩展性和效率。因此GNN 架构不再需要层或更大的感受深度来捕获重要的多跳邻域信息。最终模型变得更加简单且有效并且避免了过拟合。作者将这种交互的综合体称为 影响力Influence。
影响力 能够有效地捕获局部和全局结构并对异质性具有较强的鲁棒性。通常GNN 架构很难确定在哪个深度或跳数下连接邻居信息对捕获局部和全局结构最有帮助。不同的数据集显示了不同程度的同质性和异质性。因此在没有先验信息的情况下选择深度跳数可能并非最优。例如对于同质性数据集1-hop 设计更为合适因为相互连接的节点更有可能是相似的[4,27]。对于异质性数据集这些数据集更可能包含不同标签的节点相互连接研究人员已经提出了使用固定跳数的设计[6,11,19]或者提出了通过堆叠层来学习跳数的混合设计[25]。如图 2(a) 所示使用组合交互不会假设任何特定的跳数而是使所有跳数信息都可以用于学习。
计算 影响力 并非易事因为存在相互依赖关系。例如节点 r 也受到节点 m,n的影响并且这部分影响会在通过 r 时与节点 j 的影响力结合。由于所有节点都会受到其他节点的影响因此需要一种计算简单且高效的方法来获得 影响力。在第 3.1.1 节中作者提出了一种优雅且简单的机制基于矩阵的性质和图边的稀疏性来计算 影响力。
在第 3.1 节中作者展示了 影响力 度量如何作为损失函数使用称为 IAC影响力增强对比损失。最后作者推导了提出的 SCGC 架构它使用 IAC 损失来处理结构并使用基于 KL 散度的自监督来进行聚类。聚类本质上是无监督的[32]而 MLP多层感知机通常是有监督的。
与以前的 GNN 架构不同SCGC 不包含 GNN而是使用一个简单且计算高效的 MLP 来进行图聚类使用 IAC 损失来处理结构并基于 KL 散度的自监督进行聚类。IAC 是无增强且边对比的与大多数对比损失方法不同。此外与以前使用多模态融合的最先进模型不同SCGC 使用单一模态避免了需要进行昂贵的多次优化和端点融合但如表 2 所示它取得了更好的结果。此外如图 6 所示作者实现了更高的效率。 3.1. Influence Augmented Contrastive (IAC) Loss
如图 2(a) 所示图形从一个独特的能力中受益多个深度下的非邻接节点可以对一个节点产生任意的不相似且可加的影响。通过使用前一节定义的 影响力Influence可以更广泛地捕捉这些来自局部和全局邻域的可加效应并且适用于给定的深度 R。尽管它可以携带更丰富的信息但重要的是影响力 通过结合间接的远距离节点放宽了同质性homophily假设。以往的 GNN 模型天真地假设一个固定的深度关系即通过超参数搜索得到的单一 r。典型的 GNN 层试图通过一个固定的层结构来利用这一特性。然而这个层结构需要与潜在的影响力结构对齐。此外GNN 层普遍应用于所有节点因此错误地假设所有节点从不同深度效应中获得相同的影响本质上是假设只有一个固定的 r。因此GNN 模型往往是次优的。此外大多数 GNN 模型由于过度平滑问题over smoothing无法超过 2 层深度像 FDGATII[1] 和 GCNII[16] 等模型试图解决这一问题。相比之下影响力 是一种简单且高效的替代方案。
作者将 影响力 γij作为加权因子应用于一种特定但流行的对比损失[4]以便为第 i 个节点公式化 IAC 损失其表达式为 其中τ 是温度参数γij是节点 i 和节点 j 之间连接的 影响力且对于所有 k∈{1,2,…,B}k≠i。目前使用所有节点 N而不是批量 B因此 BN。
本质上对于每个节点其累积的 R-hop 邻域影响力用于区分正样本将其与所有节点进行对比。IAC 损失 鼓励有影响力的节点在嵌入空间中比没有影响力的节点更接近。
图 2(b) 说明了 IAC 损失 的公式化过程。在接下来的两个子节中将概述如何计算累积影响力并提供相似性度量方法的详细信息即距离distance。
3.1.1. 确定影响力
图中的高阶关系和高阶邻近性是通过邻接矩阵的幂次来获取的。将邻接矩阵 A 提升到 r-次方提供了关于图中节点在第 r 距离或深度或跳数上的高阶连接信息 [4,31]。
对于归一化的邻接矩阵 A^ 其中I是自连接矩阵D 是对角矩阵且 r-次方提供了节点 i 和节点 j 之间的第 r 跳关系的强度 [4]。与以往所有的研究不同作者提出通过所有节点关系的加性形式来计算影响力而不是将其限制在某个特定的第 r 跳邻域内。具体来说将归一化邻接矩阵的第 R 次累积幂定义为影响力 I^R如图 2(a) 所示。因此 重要的是I^R包含了从 1 到 R 的所有之前邻域跳关系的聚合集。图 3 是 IAC 过程的可视化。归一化邻接矩阵 A^ 的各次幂直到第 R 次都被聚合以得到 I^R。 直观地来说邻接矩阵 A^的每一幂次表示图中一对节点之间特定长度路径的数量。具体而言A^r 的 ij-th 边给出节点 i 和节点 j 之间的 r-长度路径数。路径数越多表示节点对之间的旅行方式越多连接性越强。通过累加这些幂次影响力聚合了关于各种长度路径的信息从而捕捉图的整体连接性和结构。将幂次累加直到某个深度 R 可以捕获节点间在 R 跳距离内的累积连接性跨越从局部到全局的结构信息。
计算 I^R只需要在训练前进行一次使用邻接矩阵且开销非常小。在大规模图中可以使用稀疏实现来计算 I^R。实际的图通常是极其稀疏的邻接矩阵 A 大多数是零 [31]。此外I^R 的计算完全不涉及模型的学习过程不涉及昂贵的张量操作且边缘计算可以轻松地并行化。
边缘 γij 的影响力可以表示为 需要注意的是只有当节点 j 从其 r-跳邻域的节点 i 获得非零影响时γij才会取得非零值。总结如下 与本研究中影响力的定义不同[4] 提出了基于余弦相似度的 NContrast (NC) 损失用于分类其中每个节点仅考虑第 r 跳邻域而不是更全面的加性影响力。具体来说NContrast 仅使用图 3 中的一个 A^r并且仅适用于有监督的分类任务。NC 可以被视为更通用的 IAC 损失的一个特定情况。作者采用 [4] 的方法进行自监督聚类使用公式 (1) 和 对于批次 B 的完整 IAC 或 NC 对比损失为 请注意尽管公式 (5) 对于 IAC 和 NC 看似相同但它们每个在计算 ℓi时使用不同的 γij。IAC 使用更具信息量的聚合邻域 I^R。
3.1.2. 相似性函数
采用在谱聚类中常用的高斯核函数来计算两个样本之间的相似性定义为 其中τ是一个超参数表示方差或温度。由于 以下相似性函数可以作为一个高效的替代 3.2. 通过置信度增强的自监督聚类
图聚类本质上是无监督的。为此使用基于概率分布的置信软标签作为聚类增强的自监督机制如图 2(c) 所示。与现有的工作 [2,10,19] 类似首先获得嵌入 zi 和聚类中心 μ之间的软聚类分配概率 qiu其中 u 是聚类使用学生的 t-分布 [33] 作为核函数来衡量相似性以处理尺度不同的聚类并便于计算 [2]公式如下 其中聚类中心 μ是通过在预训练自编码器AE上进行 K-means 聚类初始化的η是学生 t-分布的自由度。在所有实验中将 Q作为所有样本的聚类分配分布并且保持 η1\如以往的工作 [6,11] 所示。
靠近聚类中心的节点在 Q 中具有更高的软分配概率。通过将 Q 提升到平方并归一化定义了一个目标分布 P该分布强调了置信度较高的分配定义如下 为了使数据表示更接近聚类中心并提高聚类的内聚性最小化 Q 和 P分布之间的 KL 散度损失这迫使当前的分布 Q 接近更有置信度的目标分布 P通过使用分布 Q 来监督聚类分配 P然后通过最小化 KL 散度来反向监督分布 Q具体为 KL 散度更新模型的方式更加平滑并减少了对嵌入的剧烈扰动 [6]。此外它可以兼顾 SCGC 的结构优化和特征优化目标。
3.3. 初始聚类中心和嵌入
为了获得初始嵌入 z 和聚类中心 μ作者使用基于自编码器AE的子批次预训练阶段通过最小化原始数据 X和重构数据 X^ 之间的重构损失即 编码器和解码器定义如下 3.4. 最终提出的模型
初步实验表明使用 IAC 后一旦获得了可接受的聚类中心 μ特征重构目标就变得冗余。自编码器可以仅通过编码器MLP替代公式 11这将减少一半的参数数量和训练开销。因此提出了两个模型变种分别是基于 AE 的 SCGC 和基于 MLP 的 SCGC*它们的目标函数分别为 SCGC SCGC*
其中α0 是平衡结构引入的超参数β0控制聚类优化的超参数。
实验 挺有新意的但是数据集没有大规模数据可以试一下大数据集测试一下。。
