通过参考图重连网络,提升异质图的同质性以改善分类效果。
It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph
- 用参考图指导边重连,增强图的同质性
- 在11个真实异质图上提升分类准确率
- 方法高效可扩展,适合大规模异质图
图神经网络(GNN)在结构化图数据上表现优异,但在异质图(连接节点常属不同类别)上性能下降。现有方法多依赖专用架构,而边重连策略尚未被充分探索。本文建立边同质性、GNN嵌入平滑性与分类性能之间的理论联系,证明提升同质性有助于性能提升。基于此,提出一种利用参考图增强同质性的重连框架,并给出同质性保证。为扩大适用性,提出一种基于标签驱动的扩散方法,从节点特征和训练标签构建同质参考图。通过大量模拟实验分析原始图与参考图同质性对重连结果的影响。在11个真实异质图数据集上评估,本方法优于现有重连技术及专门针对异质图的GNN模型,在保持高效可扩展的同时显著提升节点分类准确率。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) excel at analyzing graph-structured data but struggle on heterophilic graphs, where connected nodes often belong to different classes. While this challenge is commonly addressed with specialized GNN architectures, graph rewiring remains an underexplored strategy in this context. We provide theoretical foundations linking edge homophily, GNN embedding smoothness, and node classification performance, motivating the need to enhance homophily. Building on this insight, we introduce a rewiring framework that increases graph homophily using a reference graph, with theoretical guarantees on the homophily of the rewired graph. To broaden applicability, we propose a label-driven diffusion approach for constructing a homophilic reference graph from node features and training labels. Through extensive simulations, we analyze how the homophily of both the original and reference graphs influences the rewired graph homophily and downstream GNN performance. We evaluate our method on 11 real-world heterophilic datasets and show that it outperforms existing rewiring techniques and specialized GNNs for heterophilic graphs, achieving improved node classification accuracy while remaining efficient and scalable to large graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。