通过自适应随机游走，让消息传递更高效地捕捉长程依赖。
Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchies
- 基于图层次结构设计可学习的游走策略，动态选择走原图或捷径。
- 在合成任务上，用层次捷径的短游走达到原图长游走效果。
- 适合处理大规模图且需长距离信息传播的场景。
消息传递架构在节点和图预测任务中难以充分建模长程依赖。本文提出一种新方法，利用图层次结构与自适应随机游走解决此问题。方法引入可学习的转移概率，决定游走是偏好原始图结构，还是跨越层次捷径。在合成的长程任务中，我们证明该方法可突破仅依赖原始拓扑的传统方法的理论极限。具体而言，偏好层次结构的游走能达到与原图更长游走相当的性能。初步结果表明，该方法为高效处理大图并有效捕捉长程依赖提供了有前景的新方向。
原文摘要 · Abstract (English)
Message-passing architectures struggle to sufficiently model long-range dependencies in node and graph prediction tasks. We propose a novel approach exploiting hierarchical graph structures and adaptive random walks to address this challenge. Our method introduces learnable transition probabilities that decide whether the walk should prefer the original graph or travel across hierarchical shortcuts. On a synthetic long-range task, we demonstrate that our approach can exceed the theoretical bound that constrains traditional approaches operating solely on the original topology. Specifically, walks that prefer the hierarchy achieve the same performance as longer walks on the original graph. These preliminary findings open a promising direction for efficiently processing large graphs while effectively capturing long-range dependencies.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。