论文题目：GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring
论文领域：图神经网络，图重连算法
论文发表：ICLR 2025
论文背景：
为了提高消息传递图神经网络（GNN）的性能，提出了通过图重布线来最大化谱间隙的方法。然而，如我们所示，最小化谱间隙也可以提高泛化能力。为了解释这一点，我们分析了在随机块模型的背景下，重新布线如何有益于GNN。由于频谱间隔优化主要影响社区强度，因此当社区结构与节点标签对齐时，它可以提高性能。在此基础上，我们提出了三种不同的重新布线策略，明确针对社区结构、节点标签及其对齐方式：（a）基于社区结构的重新布线（逗号），这是实现类似目标的频谱间隙优化的一种计算效率更高的替代方案；（b）基于特征相似性的重新布线（FeaSt），其重点是最大限度地提高全局同质性；（c）一种混合方法（ComFy），该方法在保持社区结构的同时增强局部特征相似性，从而优化标签社区对齐。大量的实验证实了这些策略的有效性，并支持我们的理论见解。
当前很多图重连技术很多是提高特征相似的节点的连接性，都没有考虑节点邻居和节点标签的关系。为了克服基于谱域的图重连算法的局限性，算法深入探究特征相似性和对齐的关系。
基于谱域的方法是通过添加边来实现谱间隙最大化，更大的光谱间隙与更快的混合时间存在内在联系，因此能获得更好的信息流动效率。但异质图上的谱间隙最大化会导致过度平滑。
光谱间隙也可以通过删除边缘来最大化，这已被证明有助于减缓有害的过度平滑，同时减轻过度压缩，尤其是在异质性环境中。相反，也有研究主张最小化光谱间隙，但没有解释这种情况何时可能有利。
本文发现边连接的两个节点是否相似类型对GNN的性能很重要。已有研究分析了社区和其标签的相互关系，他们提出了一种信息论度量方法，并通过在现实世界图中人为创建和破坏社区来展示其对性能的影响。这还突显了同标签邻居的积极影响的重要性，以及不同标签邻居如何损害节点分类性能。本文基于该理论分析了谱重连不能实现对齐效果。
图神经网络中图结构与任务对齐的必要性已经有研究关于其训练动态的研究中得到探讨。该研究从理论上分析了图神经网络模型倾向于将其神经切向核（NTK）矩阵与输入原始图的邻接矩阵A对齐。
1，指出最小化谱间隙，从而放大社区结构，也可以提高GNN的性能，并提供一个系统分析，分析不同场景下的更优情况。（光谱间隙最大化会削弱图的社区结构。）
2，我们对SBMs的理论见解和实验证据表明，任务与图结构的匹配程度是解释谱间隙重连何时能提升学习任务效果的关键因素。这突显了基于谱的方法的主要局限性——它们无法直接改善图-任务的匹配度。
3，为突破这一局限，我们基于理论洞见提出将特征相似性整合到图重连方法中的创新方案。通过三种新策略分别研究社区结构与特征相似性在孤立环境（ComMa和FeaSt）及联合应用（ComFy）中的影响机制。
4，基于真实世界的数据的实验验证了研究的发现。我们发现，同质性图最能从最大化全局特征相似性的FeaSt方法中获益，而异质性图则主要受益于一种混合方法——ComFy，该方法在最大化特征相似性的同时还能保持社区结构。
我们通过对随机图的理论分析获得这些见解，随机图是从随机块模型（SBM）中抽取的，SBM是具有社区结构的图的范式模型，在此我们定义了一个节点分类任务，其中我们控制了两个决定GNNs成功的关键参数： 社区强度和图任务对齐。
本文使用三种方法来研究图拓扑结构和图同质性的重要性。
第一，ComMa的目标是输入图的潜在社区的强度，HigherComMa是在同类节点中增加边和在异类节点中删除边，从而增加整个图的社区结构强度，LowerComMa是在删除同类节点中的边和在异类节点中增加边，从而减小整个图的社区结构强度。该方法是谱域方法的随机对应方法，但比谱方法执行更快。
第二，FeaSt算法致力于最大化全局特征相似度。该算法根据这一目标对边进行优先级排序，通过添加能提升平均相似度最高的边，并删除连接相似度最低节点的现有边来实现优化。FeaSt在处理高同质性图时表现尤为出色，这种机制有助于消除冲突邻域带来的干扰。因此，FeaSt会优先关注那些本身具有同质化倾向的图区域，并进一步强化这种趋势。
第三，ComFy根据特征相似性重新连接边，但能够根据它们所属的社区来预算边的数量，从而使影响分布在图中。 ComFy在同源性场景中的表现与FeaSt旗鼓相当，在异源性场景中则更胜一筹。我们通过多个图神经网络基准测试的大量实验结果表明：图重连技术不能单纯依赖拓扑特征作为基础，而需要将拓扑结构与特征相似性相结合才能发挥效用。
最大化谱间隙的过程，添加社区间边并删除社区内的边，会减弱社区结构的强度。
总之，增加q和减少p会增大光谱间隙，但会使群落结构的差异性降低。
在图任务和类结构的高度对齐过程中，增加社区内的边和减少社区间的边，可能会导致信息传递趋向于更少的结构信息，从而降低分类表现。
通过一个典型的社区结构范例——随机块模型 SBM(p,q,C)，来阐述社区结构与节点标签之间的关联。该模型是一种具有嵌入式社区的随机图模型。
理论2使用SBM可以实现聚类和节点标签间完美对齐，但是现实数据集却很少满足。图任务和潜在的社区结构之间的关系，可能不一定是明显的，可以采取更复杂的形式。
对于异质图来说，谱重连的效果不是很直接。虽然谱重连可以通过改变潜在社区结构的显著程度来影响性能，但如果直接改进前文提到的对齐方法，对输入图的聚合效果会显著提升，而谱重连在这方面却无能为力。
我们的理论证实并量化了这一直觉。定理3描述了邻域聚合步骤后错误分类节点比例的行为。
根据理论来举个例子，定义图任务对齐率为$\psi$，当$\psi$为1时为完美对齐。当$\psi$为0时则正好相反（此时重新定义社区类型则可以实现完美对齐），当$\psi$为0.5时 $P(M)$=$\Phi(0)$=$\frac{1}{2}$，此时分类性能堪比随机分类。如图
后续的正态近似来模拟该连续过程，证明了核心参数$\psi$是决定GNN性能的。
为量化谱隙对性能的影响，我们采用具有正态分布节点特征的SBM图进行采样，其中均值表示节点所属类别。类别归属从独立伯努利分布中采样，其概率（即对齐概率）取决于节点的社区标签。
针对不同的p和q值，训练一个2层GCN，其中准确率使用NMI来衡量真实和预测值。
实验说明了越是同质图和高对齐，最小化谱间隙会加强社区强度和任务标签的关系。然而谱间隙并不能完全与GCN的准确性相关联，只能影响社区强度。图中说明了缺乏图任务对齐会降低GNN的性能。实验结果突显了即使不考虑特征相似性或图任务对齐的情况下，增加边（从而提高图密度）所带来的潜在优势。
现实数据集通常具有复杂的社区结构和混合的对齐趋势。图谱中的某些部分可能表现出良好的图任务对齐效果，而其他部分则不适合基于频谱的重连操作。
对于同质图来说，标签和社区强度的对齐，关系到下游的模型的准确率。对于Cora和Citeseer数据集上是这样的表现，如图
对于某些需要信息在不同集群间传输的任务来说，增强网络连接性可能是关键所在。所有类型的谱重连方法都能在少量边变更的情况下取得成效，因为它们可能对某些（幸运的）边产生局部去噪效果。
然而，谱重连的倾向性变化可能与其增删边的类型有关，这需要综合考虑节点标签和社区标签的关联情况。图5通过可视化展示了在Cora和Chameleon数据集上，针对500条边进行谱最小化、最大化及随机重连时，连接相同或不同节点与社区标签的边数量分布。
在最小化谱间隙中，我们发现最小化方法比其他两种方法能生成更多同社区边。在同质性场景（Cora数据集）中添加边时，这种方法表现最好。
在最大化谱间隙中，通过删除实现的谱最大化在异嗜性环境中特别有效，这一事实也得到了其对图神经网络性能显著提升的优势所支持。
ComMa算法
一般的图重连算法是预处理的， 以贪心算法为基础，但是会破坏原有图结构的社区特性。ComMa是一个非贪心的且更有效率的图重连算法。ComMa可以很好的检测原始图的社区强度，可自己增大或减小社区强度，基于Louvain算法，所以可扩展到大图中。
其中HigherComMa算法为：
LowerComMa算法为
FeaSt算法
为了最大化图中连接的节点和节点间的特征相似度，节点u和v的cosine相似度为
根据所有可能删除或增加的边的相似度进行排序，根据特定需求来进行删除和增加边。
ComFy算法
谱重连的缺点是没考虑到图任务，特征相似最大化图重连的缺点是不考虑原有的图社区结构。ComFy算法是将相似性最大化限制在特定社区对之间的边或社区内部的边的算法，同时限制整个图的最大增加的边的数量N。最终算法的计算量和前两个算法的集合是一个级别。
基础模型是GCN
比较算法是FoSR算法，ProxyAddMax算法，ProxyDelMax算法
在节点分类任务上的表现，数据集有同质图和异质图：
发现FeaSt-Del算法在同质图上表现最好，ComFy-Del似乎在异质图中处于领先地位，在某些同质图中表现相当。
在大型异质图基准测试，FeaSt-Add在一些数据上表现好，所有的ComFy算法都表现良好。
同时给出了众多方法在添加和删除边的情况下的表现
计算效率，为实验情况下的计算效率
评价指标
实验所用的数据集，提供了多种评估指标，包括边缘标签信息量（ELI）和调整后的同质性评分（AHS）。通过Louvain方法进行社区检测后，我们还计算了归一化互信息（NMI）、调整互信息（AMI）以及模块度评分，以评估图结构的信息价值。需要说明的是，AMI的调整仅在比较不同规模数据集时必要，而同一数据集内部类别数量保持不变。 因此，我们可以通过NMI值来比较算法的效果。然而，AMI值对于跨不同数据集的比对具有重要参考价值。
分析了之前的谱方法在不同数据集上的表现，主要区分在同质图和异质图上。从标签维度来重新讨论图结构问题。增加了标签的信息，帮助图重连算法更好的提高性能。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。