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
this https URL

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