arXiv：cs.LG· Ferran Hernandez Caralt, Simon Heilig, Adri\'an Bazaga, Asja Fischer, Moshe Eliasof, Pietro Li\`o·· 3 小时前AI 评分45
用 GRIP 验证 GNN 过挤压：一个可量化的长程交互框架
Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing
AI 导读
研究者提出四条可验证公理（Predictability、Tightness、Strictly k-Range、Topology-Invariance），并据此构建 TRIP 与 GRIP 框架，可将任意图转化为可证明的长程任务。
正文
Abstract:Empirical claims about the connection between over-squashing and long-range interactions in GNNs, can only be trusted if the benchmarks used to validate them genuinely require long-range interactions. The de-facto standard, the Long Range Graph Benchmark, has been repeatedly shown to be saturated by tuned short-range models, with existing synthetic alternatives being tied to specific topologies. As such, there is a lack of principled certificate of long-rangedness on arbitrary graphs. This state reflects the absence of a precise characterization of long-ranged benchmarks. We address this fundamental gap by introducing four verifiable axioms: Predictability, Tightness, Strictly $k$-Range, and Topology-Invariance, that any task claiming to test $k$-hop interactions must satisfy. We formally prove that violating any one of them admits failure modes that undermine conclusions drawn from the task. Based on these axioms, we introduce TRIP (Truly Ranged Interactions Problem) and its generalisation GRIP (Generally Ranged Interactions Problem), constructive procedures that turn any graph into a provably long-ranged task by drawing features from stable distributions. Moreover, by construction, GRIP admits a closed-form, per-range Maximum-Likelihood oracle that yields the first a priori per-range lower bound on test error available on any benchmark. Using our framework, we: (i) audit 4 common long-range benchmarks and identify their failures modes with respect to our axioms; (ii) on TRIP-instantiated topologies, we find a popular notion of curvature is uncorrelated with GNN performance, supporting topological-vs-computational bottleneck distinction; and (iii) we show that a novel benchmark's over-squashing measures factors beyond pure long-rangedness. Code to use the framework and reproduce experiments is released this https URL.
| Comments: | Published at the Conference on Neural Information Processing Systems (NeurIPS 2026). Track on Evaluations and Datasets |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.03556 [cs.LG] |
| (or arXiv:2610.03556v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.03556 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Ferran Hernandez Caralt [view email]
[v1]
Fri, 2 Oct 2026 16:37:19 UTC (436 KB)
来源：arXiv：cs.LG · arxiv.org