Learning Long Range Dependencies on Graphs via Random Walks
This addresses a key limitation in graph neural networks for tasks requiring long-range information, offering a flexible framework that integrates various architectures, though it is incremental in combining existing techniques.
The paper tackles the problem of capturing long-range dependencies in graphs, which message-passing GNNs struggle with and graph transformers oversimplify, by introducing an architecture that combines random walks with local message passing, achieving performance improvements of up to 13% on benchmark datasets like PascalVoc-SP and COCO-SP.
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.