Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?
Haitao Mao1, Zhikai Chen1, Wei Jin4, Haoyu Han1, Yao Ma3, Tong Zhao2, Neil Shah2, Jiliang Tang1 1Michigan State University 2Snap Inc 3Rensselaer Polytechnic Institute. 4 Emory University {haitaoma,
Abstract
Recent studies on Graph Neural Networks(GNNs) provide both empirical and theoretical evidence supporting their effectiveness in capturing structural patterns on both homophilic and certain heterophilic graphs. Notably, most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns, exhibiting a structural disparity. However, the analysis of GNN performance with respect to nodes exhibiting different structural patterns, e.g., homophilic nodes in heterophilic graphs, remains rather limited. In the present study, we provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes within homophilic graphs and heterophilic nodes within heterophilic graphs while struggling on the opposite node set, exhibiting a performance disparity. We theoretically and empirically identify effects of GNNs on testing nodes exhibiting distinct structural patterns. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity, namely the aggregated feature distance and homophily ratio difference between t
中文速览
图神经网络（GNN）在节点分类任务中被广泛使用，但现实图数据中同质节点（homophilic nodes，即与邻居标签相同的节点）和异质节点（heterophilic nodes，即与邻居标签不同的节点）往往同时存在，而已有研究几乎都只关注整体性能，忽视了不同结构模式节点之间的表现差异。研究者系统地发现：GNN 在同质图中的同质节点、异质图中的异质节点上表现出色，却在"少数派"节点（如同质图里的异质节点）上明显落后于不使用图结构的 MLP 模型，存在显著的性能分化（performance disparity）。为了揭示背后原因，作者推导了一个严格的非独立同分布 PAC-Bayes 泛化界，从理论上证明训练节点与测试节点之间的聚合特征距离差异和同质性比例差异是导致性能分化的核心因素。这一发现不仅解释了更深层 GNN 在某些场景下有效的原因，还揭示了图分布外泛化（graph out-of-distribution generalization）研究中一个长期被忽视的分布偏移来源，为设计更公平、更鲁棒的图学习方法提供了重要理论基础。
原文 arXiv:2306.01323;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2306.01323v3