Item

Abstract

Message-passing graph neural networks (GNNs) excel at capturing local
relationships but struggle with long-range dependencies in graphs. In contrast,
graph transformers (GTs) enable global information exchange but often
oversimplify the graph structure by representing graphs as sets of fixed-length
vectors. This work introduces a novel architecture that overcomes the
shortcomings of both approaches by combining the long-range information of
random walks with local message passing. By treating random walks as sequences,
our architecture leverages recent advances in sequence models to effectively
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
our approach 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. The code is available at
https://github.com/BorgwardtLab/NeuralWalker.