arXiv:2502.04891cs.LGcs.SI2025-02ICLR被引 16

通过重构图结构提升GNN性能,关键在于社区与特征相似性的协同优化。

GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring

  • 基于社区结构和特征相似性设计三种图重连策略
  • 在多个数据集上显著提升GNN泛化能力,尤其在标签与社区对齐时效果更优
  • 适合关注GNN结构优化与图建模的开发者与研究者

通过图重连最大化谱间隙已被提出用于缓解消息传递GNN中的过挤压问题,从而提升性能。然而我们发现,最小化谱间隙同样能改善泛化能力。为解释这一现象,我们基于随机块模型分析了重连对GNN的影响:谱间隙优化主要影响社区强度,在社区结构与节点标签一致时可提升性能。基于此洞察,我们提出三种不同重连策略:(a) 基于社区结构的重连(ComMa),一种计算更高效且目标相近的替代方案;(b) 基于特征相似性的重连(FeaSt),旨在最大化全局同质性;(c) 混合方法(ComFy),在保持社区结构的同时增强局部特征相似性,以优化标签与社区的对齐。大量实验验证了这些策略的有效性,并支持我们的理论分析。

原文摘要 · Abstract (English)

Maximizing the spectral gap through graph rewiring has been proposed to enhance the performance of message-passing graph neural networks (GNNs) by addressing over-squashing. However, as we show, minimizing the spectral gap can also improve generalization. To explain this, we analyze how rewiring can benefit GNNs within the context of stochastic block models. Since spectral gap optimization primarily influences community strength, it improves performance when the community structure aligns with node labels. Building on this insight, we propose three distinct rewiring strategies that explicitly target community structure, node labels, and their alignment: (a) community structure-based rewiring (ComMa), a more computationally efficient alternative to spectral gap optimization that achieves similar goals; (b) feature similarity-based rewiring (FeaSt), which focuses on maximizing global homophily; and (c) a hybrid approach (ComFy), which enhances local feature similarity while preserving community structure to optimize label-community alignment. Extensive experiments confirm the effectiveness of these strategies and support our theoretical insights.

图神经网络图重连社区结构特征相似性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。