用拉马努金图重连网络，解决GNN信息压缩难题。
Ramanujan Graph Rewiring with Non Negative Resistance Curvature
- 用拉马努金图构造新拓扑，保证非负电阻曲率。
- 在多个数据集上超越9种先进重连方法。
- 适合需要长程依赖建模的图神经网络任务。
图神经网络（GNN）通过边上传播和聚合信息来学习图结构数据，但传统消息传递机制常因过度压缩导致信息损失，阻碍长距离依赖学习。本文提出拉马努金传播，一种基于拉马努金图的图重连策略，可缓解拓扑瓶颈。我们证明，合理选择的拉马努金图能保证非负电阻曲率，从而减轻过挤压问题并促进信息高效流动。进而提出算法框架，构建保留原始局部连接性的拉马努金重连图。实验表明，该方法优于九种先进重连技术。结果确立拉马努金图为可扩展、拓扑感知消息传递的严谨结构先验。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) have emerged as a powerful paradigm for learning on graph-structured data by iteratively propagating and aggregating information across edges. However, conventional message passing schemes often suffer from over-squashing, whereby exponentially large neighborhoods are compressed into fixed-dimensional embeddings, impeding effective long-range dependency learning. In this work, we introduce Ramanujan Propagation, a graph rewiring strategy that leverages Ramanujan graphs to alleviate topological bottlenecks in GNNs. We first establish that suitably chosen Ramanujan graphs guarantee non-negative resistance curvature, which mitigates over-squashing and facilitates efficient information flow. We then propose an algorithmic framework to construct a Ramanujan rewired graph that preserves the local connectivity of the original graph. Our experiments demonstrate that our method outperforms nine state-of-the-art rewiring techniques. These results establish Ramanujan graphs as a rigorous structural prior for scalable, topology-aware message passing in GNNs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。