# Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels

arXiv: https://arxiv.org/abs/2104.02995 · HTML: https://mlsanity.com/paper/2104.02995/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 52 references that are in the map.
- First posted on arXiv 7 Apr 2021.

## Builds on (most cited first, 29 of 29)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [graph2vec: Learning Distributed Representations of Graphs](https://mlsanity.com/paper/1707.05005/) (2017)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Motifs in Temporal Networks](https://mlsanity.com/paper/1612.09259/) (2016)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Anonymous Walk Embeddings](https://mlsanity.com/paper/1805.11921/) (2018)
- [Convolutional Kernel Networks for Graph-Structured Data](https://mlsanity.com/paper/2003.05189/) (2020)
- [RetGK: Graph Kernels based on Return Probabilities of Random Walks](https://mlsanity.com/paper/1809.02670/) (2018)
- [Faster Kernels for Graphs with Continuous Attributes via Hashing](https://mlsanity.com/paper/1610.00064/) (2016)
- [GraLSP: Graph Neural Networks with Local Structural Patterns](https://mlsanity.com/paper/1911.07675/) (2019)
- [Deriving Neural Architectures from Sequence and Graph Kernels](https://mlsanity.com/paper/1705.09037/) (2017)
- [A simple yet effective baseline for non-attributed graph classification](https://mlsanity.com/paper/1811.03508/) (2018)
- [Graph Structural-topic Neural Network](https://mlsanity.com/paper/2006.14278/) (2020)
- [DDGK: Learning Graph Representations for Deep Divergence Graph Kernels](https://mlsanity.com/paper/1904.09671/) (2019)
- [A Novel Higher-order Weisfeiler-Lehman Graph Convolution](https://mlsanity.com/paper/2007.00346/) (2020)
- [Motif Clustering and Overlapping Clustering for Social Network Analysis](https://mlsanity.com/paper/1612.00895/) (2016)

## Built on by (most cited first, 19 of 19)

- [Spatial-Temporal Graph ODE Networks for Traffic Flow Forecasting](https://mlsanity.com/paper/2106.12931/) (2021)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [CoCo: A Coupled Contrastive Framework for Unsupervised Domain Adaptive Graph Classification](https://mlsanity.com/paper/2306.04979/) (2023)
- [BioRAG: A RAG-LLM Framework for Biological Question Reasoning](https://mlsanity.com/paper/2408.01107/) (2024)
- [Towards Graph Contrastive Learning: A Survey and Beyond](https://mlsanity.com/paper/2405.11868/) (2024)
- [TGNN: A Joint Semi-supervised Framework for Graph-level Classification](https://mlsanity.com/paper/2304.11688/) (2023)
- [Inductive Graph Alignment Prompt: Bridging the Gap between Graph Pre-training and Inductive Fine-tuning From Spectral Perspective](https://mlsanity.com/paper/2402.13556/) (2024)
- [Unveiling Delay Effects in Traffic Forecasting: A Perspective from Spatial-Temporal Delay Differential Equations](https://mlsanity.com/paper/2402.01231/) (2024)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [ScienceDB AI: An LLM-Driven Agentic Recommender System for Large-Scale Scientific Data Sharing Services](https://mlsanity.com/paper/2601.01118/) (2026)
- [Descriptive Kernel Convolution Network with Improved Random Walk Kernel](https://mlsanity.com/paper/2402.06087/) (2024)
- [Rethinking the impact of noisy labels in graph classification: A utility and privacy perspective](https://mlsanity.com/paper/2406.07314/) (2024)
- [MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts](https://mlsanity.com/paper/2509.09337/) (2025)
- [Representation Learning on Heterostructures via Heterogeneous Anonymous Walks](https://mlsanity.com/paper/2201.06972/) (2022)
- [Towards Graph Prompt Learning: A Survey and Beyond](https://mlsanity.com/paper/2408.14520/) (2024)
- [Graph-level Neural Networks: Current Progress and Future Directions](https://mlsanity.com/paper/2205.15555/) (2022)
- [Core Knowledge Learning Framework for Graph Adaptation and Scalability Learning](https://mlsanity.com/paper/2407.01886/) (2024)
- [LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisation](https://mlsanity.com/paper/2504.08530/) (2025)

## Abstract (arXiv)

Graph neural networks (GNNs) have achieved tremendous success in graph mining. However, the inability of GNNs to model substructures in graphs remains a significant drawback. Specifically, message-passing GNNs (MPGNNs), as the prevailing type of GNNs, have been theoretically shown unable to distinguish, detect or count many graph substructures. While efforts have been paid to complement the inability, existing works either rely on pre-defined substructure sets, thus being less flexible, or are lacking in theoretical insights. In this paper, we propose GSKN, a GNN model with a theoretically stronger ability to distinguish graph structures. Specifically, we design GSKN based on anonymous walks (AWs), flexible substructure units, and derive it upon feature mappings of graph kernels (GKs). We theoretically show that GSKN provably extends the 1-WL test, and hence the maximally powerful MPGNNs from both graph-level and node-level viewpoints. Correspondingly, various experiments are leveraged to evaluate GSKN, where GSKN outperforms a wide range of baselines, endorsing the analysis.