arXiv:2508.17822cs.LGcond-mat.dis-nn2025-08

揭示消息传递模型在节点分类中的信号噪声瓶颈,提出改进方法

Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio

  • 用信噪比统一分析异质性与结构瓶颈对模型的影响
  • 发现高阶同质性决定信号敏感度,低值导致分类性能下降
  • 提出基于图重连的BRIDGE算法,显著提升各类图上的分类准确率

消息传递神经网络(MPNN)在节点分类中表现强大,但在异质性(同类连接率低)和图结构瓶颈下性能受限。本文建立统一统计框架,通过信噪比(SNR)揭示异质性与瓶颈的关系。SNR可分解为依赖特征的参数与不依赖特征的敏感度。证明模型对类别信号的敏感度受高阶同质性(扩展至多跳邻域)限制,低高阶同质性表现为结构瓶颈与类别标签的局部交互(类瓶颈)。通过图集合分析,进一步将瓶颈分解为深度不足(信号无法到达)与广度不足(信号路径过少),并给出闭式表达式。证明最大化高阶同质性的最优图结构为单类或二类二分簇的不相交并集。由此提出BRIDGE算法,通过图重连消除‘中等同质性陷阱’,在合成基准上实现近完美分类,在真实世界基准上显著优于现有重连技术。该框架提供诊断工具与可解释的图优化方法,代码已开源。

原文摘要 · Abstract (English)

Message passing neural networks (MPNNs) are powerful models for node classification but suffer from performance limitations under heterophily (low same-class connectivity) and structural bottlenecks in the graph. We provide a unifying statistical framework exposing the relationship between heterophily and bottlenecks through the signal-to-noise ratio (SNR) of MPNN representations. The SNR decomposes model performance into feature-dependent parameters and feature-independent sensitivities. We prove that the sensitivity to class-wise signals is bounded by higher-order homophily -- a generalisation of classical homophily to multi-hop neighbourhoods -- and show that low higher-order homophily manifests locally as the interaction between structural bottlenecks and class labels (class-bottlenecks). Through analysis of graph ensembles, we provide a further quantitative decomposition of bottlenecking into underreaching (lack of depth implying signals cannot arrive) and oversquashing (lack of breadth implying signals arriving on fewer paths) with closed-form expressions. We prove that optimal graph structures for maximising higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters. This yields BRIDGE, a graph ensemble-based rewiring algorithm that achieves near-perfect classification accuracy across all homophily regimes on synthetic benchmarks and significant improvements on real-world benchmarks, by eliminating the ``mid-homophily pitfall'' where MPNNs typically struggle, surpassing current standard rewiring techniques from the literature. Our framework, whose code we make available for public use, provides both diagnostic tools for assessing MPNN performance, and simple yet effective methods for enhancing performance through principled graph modification.

图神经网络节点分类消息传递图重连

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