arXiv:2508.09265cs.LGstat.ME2025-08被引 4

提出量化图神经网络过压缩的新方法,指导重连策略是否有效。

Over-Squashing in GNNs and Causal Inference of Rewiring Strategies

  • 用节点对间互敏感性衰减速率衡量过压缩程度。
  • 发现多数图分类数据集存在严重过压缩,重连可缓解但效果因数据而异。
  • 提供无需训练的诊断工具,帮助判断重连是否值得尝试。

图神经网络在推荐系统、材料设计和药物重定位等领域表现优异,但消息传递机制导致远距离信息被指数级压缩,即过压缩问题,限制了模型表达能力。重连技术可缓解此瓶颈,但缺乏直接的实证评估指标。本文提出一种基于拓扑结构的严谨方法,通过节点对间互敏感性的衰减速率来评估过压缩,并扩展为四种图级统计量(普遍性、强度、变异性、极端性)。结合图内因果设计,在多种图与节点分类基准上量化重连策略对过压缩的影响。实验表明,多数图分类数据集存在显著过压缩,重连能有效缓解;但在节点分类数据集中,过压缩不明显,且重连常加剧该问题,性能变化与过压缩无关。结果表明,重连最适用于过压缩严重且适度修正的情况;过度激进或在过压缩轻微的图上使用,可能无效甚至有害。本文提出的即插即用诊断工具,使从业者可在训练前判断重连是否值得投入。

原文摘要 · Abstract (English)

Graph neural networks (GNNs) have exhibited state-of-the-art performance across wide-range of domains such as recommender systems, material design, and drug repurposing. Yet message-passing GNNs suffer from over-squashing -- exponential compression of long-range information from distant nodes -- which limits expressivity. Rewiring techniques can ease this bottleneck; but their practical impacts are unclear due to the lack of a direct empirical over-squashing metric. We propose a rigorous, topology-focused method for assessing over-squashing between node pairs using the decay rate of their mutual sensitivity. We then extend these pairwise assessments to four graph-level statistics (prevalence, intensity, variability, extremity). Coupling these metrics with a within-graph causal design, we quantify how rewiring strategies affect over-squashing on diverse graph- and node-classification benchmarks. Our extensive empirical analyses show that most graph classification datasets suffer from over-squashing (but to various extents), and rewiring effectively mitigates it -- though the degree of mitigation, and its translation into performance gains, varies by dataset and method. We also found that over-squashing is less notable in node classification datasets, where rewiring often increases over-squashing, and performance variations are uncorrelated with over-squashing changes. These findings suggest that rewiring is most beneficial when over-squashing is both substantial and corrected with restraint -- while overly aggressive rewiring, or rewiring applied to minimally over-squashed graphs, is unlikely to help and may even harm performance. Our plug-and-play diagnostic tool lets practitioners decide -- before any training -- whether rewiring is likely to pay off.

图神经网络过压缩重连策略诊断工具

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