Abstract
The Random Walk Conformer (RWC) is a novel graph neural network framework designed to capture both long-range global dependencies and short-range local structures (motifs). By integrating random walk encodings with a Conformer-style architecture—interleaving self-attention and 1D convolutions over walk sequences—RWC achieves superior expressiveness over standard GNNs. Experimental results demonstrate state-of-the-art performance across various graph classification and regression benchmarks.
Introduction
Graph Neural Networks (GNNs) typically face a trade-off between local expressiveness and global context. Standard message-passing GNNs aggregate information from immediate neighbors, making them efficient but theoretically limited by the 1-WL isomorphism test. Consequently, they struggle to distinguish complex local structures like cycles and fail to model long-distance relationships. Conversely, Graph Transformers utilize self-attention for global modeling but often ignore graph topology and incur high computational costs ($O(V^2)$).
While motif-based approaches attempt to capture local structures, exhaustive motif searching is combinatorially expensive. The Random Walk Conformer (RWC) addresses these challenges by using random walks as an efficient sampling tool to capture both motifs and global patterns simultaneously.
The Random Walk Conformer Architecture
The RWC architecture draws inspiration from the "Conformer" architecture used in speech processing, utilizing a modular design to balance different scales of information.
Key Components:
- Random Walk Encodings: Instead of fixed shortest-path distances, RWC employs distances and edge features derived from multiple random walks. This approach is mathematically proven to be strictly more expressive than the 1-WL test and standard spatial encodings.
- RW-SAN (Random Walk Self-Attention Network): This module applies attention to nodes sampled via random walks, allowing the model to capture long-range correlations across sequences without the overhead of full graph attention.
- RW-Conv (Random Walk Convolution): By treating a random walk sequence as a 1D string, RWC applies 1D convolutions. This "sliding window" effectively detects local structural patterns (motifs) without needing to enumerate every possible subgraph combination.
- Non-backtracking Walks: To ensure effective graph exploration, the model uses non-backtracking random walks, forcing the walker to move to new neighbors rather than immediately returning to a previous node.
Key Insights and Expressiveness
The core innovation of RWC lies in using 1D convolutions over random walks as proxies for motifs. If a walk traverses a triangle, the 1D CNN kernel identifies that specific sequence of features. This mechanism allows RWC to break the 1-WL barrier, distinguishing graph structures that standard GNNs find identical.
Furthermore, the "Conformer sandwich" structure—placing RW-SAN and RW-Conv between Feed-Forward (FF) modules—helps the model maintain a balance between broad topological views and fine-grained local details. The stochastic nature of random walks also provides a form of natural data augmentation, enhancing model robustness through varied path sampling during training.
Experimental Results
RWC was evaluated on standard benchmarks including graph classification (TUDatasets) and large-scale regression (ZINC, PCQM4Mv2).
As shown in the results, RWC achieved state-of-the-art (SOTA) performance:
- Regression: On the ZINC dataset, RWC outperformed the motif-based CIN by 14% and the Transformer-based GRPE by 28% in Mean Absolute Error (MAE).
- Classification: The model set new SOTA records on MUTAG (94.7% accuracy) and PTC (74.4% accuracy), significantly outperforming both traditional kernels and modern GNNs.
- Efficiency: RWC maintains a computational complexity of $O(V^2d)$, comparable to standard Transformers, while providing superior topological awareness through walk encodings.
Limitations and Future Work
Despite its success, RWC's performance is sensitive to walk length; walks that are too short may miss global context, while excessively long walks might over-sample dense regions. Future research could explore more sophisticated multi-walk coverage strategies for large, sparse graphs and optimize the preprocessing overhead associated with generating random walks.
Summary updated