摘要

图神经网络（Graph Neural Networks, GNNs）是建模图数据的流行机器学习方法。尽管许多GNN在同质性（homophily）图上表现良好，但在异质性（heterophily）图上的性能却往往不尽如人意。近期，一些研究者开始关注通过调整消息传递机制或扩大消息传递的感受野来设计适用于异质性图的GNN。与现有工作从模型设计角度缓解异质性问题不同，本文提出从一个正交视角出发，通过重连图结构以降低异质性程度，从而使传统GNN在异质性图上获得更好的表现。通过全面的实验研究与分析，我们验证了图重连方法在提升GNN性能方面的潜力。为进一步挖掘该潜力，本文提出一种名为深度异质性图重连（Deep Heterophily Graph Rewiring, DHGR）的方法，该方法通过添加同质性边并剪除异质性边来重构图结构。具体的重连策略基于节点邻居在标签或特征分布上的相似性进行判断与决策。此外，我们还设计了一种可扩展的实现方案，以确保DHGR在大规模图上的高效运行。DHGR可作为即插即用的模块，即作为任意GNN的图预处理步骤，适用于面向同质性或异质性图的各类GNN模型，显著提升其在节点分类任务中的性能。据我们所知，这是首个系统研究图重连用于异质性图的开创性工作。在11个公开图数据集上的大量实验结果表明，所提出的方法在性能上具有显著优势，充分验证了其有效性与通用性。