Abstract
This paper bridges the gap between two historically separate approaches to graph learning: Random Walk (RW) kernels and the Weisfeiler-Leman (WL) subtree kernel. By introducing a "node-centric" approach to walk counting and a parameterized similarity measure, we demonstrate that random walk kernels can match the expressivity of WL while offering a more flexible, "non-strict" way to compare graph neighborhoods. Our proposed Node-centric $\ell$-walk (NCW) kernel achieves competitive results on standard benchmarks, particularly where structural noise necessitates soft similarity measures.
Introduction
In graph machine learning, measuring structural similarity is a fundamental challenge. Historically, Random Walk (RW) kernels were a primary tool, operating by counting identical walk sequences shared between graphs. However, they were largely superseded by the Weisfeiler-Leman (WL) subtree kernel, which offers superior expressivity and computational efficiency through iterative node label refinement.
A significant drawback of the WL approach is its "all-or-nothing" nature: discrete hashing treats even slightly different neighborhoods as entirely distinct. Conversely, while classical RW kernels are less expressive, they offer a more continuous view of similarity. This work introduces a framework that combines the expressivity of WL with the fine-grained, "soft" comparisons characteristic of random walks.
Methods: The Node-Centric $\ell$-Walk Kernel
The core innovation is the Node-centric $\ell$-walk graph kernel (NCW). Unlike traditional RW kernels that aggregate common walks globally, NCW groups walks by their starting node. This shift in perspective allows the kernel to capture local neighborhood structures more effectively, similar to how WL unfolding trees capture subtree structures.
Key technical components include:
- Walk Profile Comparison: By comparing "walk profiles" between node pairs rather than global counts, the method significantly increases structural resolution.
- Parameterized Similarity: The method employs a generalized node kernel ($k_v$) and a Gaussian-style distance controlled by a parameter $\alpha$. High $\alpha$ values mimic the discrete checks of WL, while lower values enable "soft" refinement where similar neighborhoods contribute to the similarity score.
- Direct Product Graph Refinement: The computation utilizes direct product graphs. We provide a refined algorithm that re-encodes node similarities in each iteration, allowing the kernel to reach WL-level expressivity as the walk length $\ell$ increases.
Key Insights and Expressivity
The "aha moment" of this research is that the perceived weakness of classical RW kernels is not inherent to the walks themselves, but rather to how they are aggregated. By shifting to a node-centric comparison, walks become as powerful as subtrees.
As shown in the partition lattice, the NCW kernel ($rw_+$) creates a hierarchy of refinements. While WL refinement is a "hard" partition, the NCW kernel's $\alpha$ parameter allows for a "soft" refinement. This flexibility is crucial for real-world datasets where minor structural variations or noise should not result in a total lack of similarity. Experimental "completeness ratios" confirm that NCW matches the expressivity of the WL subtree kernel as $\ell$ increases.
Experimental Evaluation
We evaluated the NCW kernel on several standard benchmarks from the TUDataset, including small molecules (MUTAG, NCI1), macromolecules (ENZYMES, PROTEINS), and social networks (COLLAB, IMDB-BINARY).
- Superior Accuracy on Noisy Data: On the ENZYMES dataset, NCW achieved 54.8% accuracy, outperforming both the WL kernel (53.8%) and traditional RW kernels (33.9%). This success stems from the ability to consider larger neighborhoods while comparing them less strictly.
- Matching WL Performance: On NCI1 and NCI109, NCW matched WL performance while outperforming classical RW kernels by over 10 percentage points.
- Social Network Flexibility: Results on social datasets (COLLAB, IMDBBIN) highlighted the importance of the kernel's flexibility, as they showed a clear preference for specific parameter settings ($\beta=0$) that are unavailable in standard WL.
Conclusion and Future Work
By rethinking random walks through a node-centric lens, we have shown that they are not merely a precursor to WL but a powerful, flexible alternative. The main limitation remains computational complexity; while WL runs in linear time $O(m)$, NCW relies on direct product graphs ($O(n^2)$), making it more memory-intensive. Future work will focus on acceleration techniques and extending the framework to heavily attributed graphs, potentially addressing the "bottleneck problem" in Graph Neural Networks (GNNs) by providing a more robust representation of expanding neighborhoods.
Summary updated