Message-passing graph neural networks (GNNs), while excelling at capturing local relationships, often struggle with long-range dependencies on graphs. Conversely, graph transformers (GTs) enable information exchange between all nodes but oversimplify the graph structure by treating them as a set of fixed-length vectors. This work proposes a novel architecture, NeuralWalker, that overcomes the limitations of both methods by combining random walks with message passing. NeuralWalker achieves this by treating random walks as sequences, allowing for the application of recent advances in sequence models in order to capture long-range dependencies within these walks. Based on this concept, we propose a framework that offers (1) more expressive graph representations through random walk sequences, (2) the ability to utilize any sequence model for capturing long-range dependencies, and (3) the flexibility by integrating various GNN and GT architectures. Our experimental evaluations demonstrate that NeuralWalker achieves significant performance improvements on 19 graph and node benchmark datasets, notably outperforming existing methods by up to 13% on the PascalVoc-SP and COCO-SP datasets. Code is available at https://github.com/BorgwardtLab/NeuralWalker.

本文提出了一种名为NeuralWalker的新型架构，通过将随机游走视为序列，利用序列模型捕捉这些游走中的长程依赖关系，从而克服了消息传递图神经网络和图变换器方法的局限性，实现更具表达力的图表示，并能够使用任何序列模型来捕捉长程依赖关系，同时具备集成各种图神经网络和图变换器架构的灵活性。实验证明，NeuralWalker在19个图和节点基准数据集上取得了显著的性能改进，在PascalVoc-SP和COCO-SP数据集上的性能超过现有方法高达13%。

通过随机游走学习图上的长程依赖