Learning Long Range Dependencies on Graphs via Random Walks

这篇论文讨论了消息传递图神经网络（GNN）在捕捉局部关系方面表现出色，但在处理图的长程依赖时常常遇到困难。相反，图变换器（GT）能够在所有节点之间进行信息交换，但过于简化图结构，将其视为一组固定长度的向量。本文提出了一种新的体系结构NeuralWalker，通过将随机游走与消息传递相结合，克服了两种方法的局限性。NeuralWalker通过将随机游走视为序列来实现这一点，从而允许应用序列模型的最新进展，以捕捉这些游走中的长程依赖关系。基于这个概念，我们提出了一个框架，提供了（1）更具表现力的图表示，通过随机游走序列，（2）利用任何序列模型来捕捉长程依赖关系，和（3）通过集成各种GNN和GT架构的灵活性。我们的实验评估表明，NeuralWalker在19个图形和节点基准数据集上实现了显着的性能提升，特别是在PascalVoc-SP和COCO-SP数据集上，超过现有方法高达13％。代码可在https://github.com/BorgwardtLab/NeuralWalker获得。

论文旨在解决图神经网络在捕捉长距离依赖方面的局限性，提出一种结合随机游走和消息传递的新型架构NeuralWalker。

NeuralWalker通过将随机游走看作序列，并应用序列模型来捕获这些序列中的长距离依赖关系，从而克服了消息传递图神经网络和图转换器的局限性。

论文提出的NeuralWalker架构在19个图和节点基准数据集上取得了显著的性能提升，特别是在PascalVoc-SP和COCO-SP数据集上超过现有方法高达13%。论文提供了代码开源。

相关研究包括《Graph Attention Networks》、《Gated Graph Sequence Neural Networks》、《Graph Convolutional Networks》等。