用群论构造新图拓扑，解决图神经网络长程信息传播阻塞问题。
Schreier-Coset Graph Rewiring
- 基于特殊线性群构造陪集图，重构图结构以增强信息通路。
- 实验显示有效电阻降低5-40%，显著改善长距离通信效率。
- 理论保证谱间隙与有界有效电阻，适合对连通性敏感的任务。
图神经网络中的信息流动受过挤压（over-squashing）根本制约，结构瓶颈阻碍长程信息传播。现有图重布线方法常引入巨大结构与计算开销，破坏原始图关键属性且大幅增加边数。本文提出一种新型群论重布线方法——Schreier-Coset Graph Rewiring（SCGR），通过在输入图上叠加由特殊线性群导出的陪集图来增强拓扑。该方法提供理论保障，生成具有谱间隙和有界有效电阻的图，为长距离通信构建低阻抗通路。实证表明，SCGR在多种学习任务中使有效电阻降低5-40%，有效缓解连通性瓶颈，同时保持竞争力的准确率。
原文摘要 · Abstract (English)
The information flow in the graph neural networks (GNNs) is fundamentally constrained by over-squashing, where structural bottlenecks impede long range information propagation. Graph-rewiring methods, which modify graph topology, have been extensively used to alleviate this. However, existing approaches often introduce prohibitive structural and computational bottlenecks, fail to preserve the critical properties of original graphs, and increase the edge counts massively. We introduce a novel method Schreier-Coset Graph Rewiring , a group-theoretic rewiring method that augments the input graph with a Schreier-Coset graph derived from a special linear group. Our method provides theoretical guarantees, a graph that exhibits spectral gap and a bounded effective resistance, creating a low-resistance bypass for long-range communication. Empirical evaluations demonstrate that SCGR reduces effective resistance by 5-40% across various learning tasks, effectively mitigating connectivity bottlenecks while maintaining competitive accuracy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。