mlsanityData to 7 Oct 2026

Theoretically Improving Graph Neural Networks via Anonymous Walk Graph Kernels

arXiv 2104.02995 ↗First posted 7 Apr 2021cs.LG cs.AIcited by 19

Not on the map. Why?

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.

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

Builds on

29 of 52 references.

References · 29

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2019Simplifying Graph Convolutional Networkscited by 1,470
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  10. 2016Learning Convolutional Neural Networks for Graphscited by 314
  11. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  12. 2020Can Graph Neural Networks Count Substructures?cited by 235
17 more
  1. 2017graph2vec: Learning Distributed Representations of Graphscited by 228
  2. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  3. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  4. 2019Wasserstein Weisfeiler-Lehman Graph Kernelscited by 104
  5. 2016Motifs in Temporal Networkscited by 101
  6. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  7. 2018Anonymous Walk Embeddingscited by 46
  8. 2020Convolutional Kernel Networks for Graph-Structured Datacited by 38
  9. 2018RetGK: Graph Kernels based on Return Probabilities of Random Walkscited by 32
  10. 2016Faster Kernels for Graphs with Continuous Attributes via Hashingcited by 31
  11. 2019GraLSP: Graph Neural Networks with Local Structural Patternscited by 25
  12. 2017Deriving Neural Architectures from Sequence and Graph Kernelscited by 23
  13. 2018A simple yet effective baseline for non-attributed graph classificationcited by 16
  14. 2020Graph Structural-topic Neural Networkcited by 16
  15. 2019DDGK: Learning Graph Representations for Deep Divergence Graph Kernelscited by 14
  16. 2020A Novel Higher-order Weisfeiler-Lehman Graph Convolutioncited by 10
  17. 2016Motif Clustering and Overlapping Clustering for Social Network Analysiscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 4; 2024: 8; 2025: 2; 2026: 1.

19 papers.

Sort:

By area:

  1. 2021Spatial-Temporal Graph ODE Networks for Traffic Flow Forecastingcited by 209
  2. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  3. 2022A Survey on Graph Representation Learning Methodscited by 66
  4. 2023CoCo: A Coupled Contrastive Framework for Unsupervised Domain Adaptive Graph Classificationcited by 46
  5. 2024BioRAG: A RAG-LLM Framework for Biological Question Reasoningcited by 42
  6. 2024Towards Graph Contrastive Learning: A Survey and Beyondcited by 26
  7. 2023TGNN: A Joint Semi-supervised Framework for Graph-level Classificationcited by 19
  8. 2024Inductive Graph Alignment Prompt: Bridging the Gap between Graph Pre-training and Inductive Fine-tuning From Spectral Perspectivecited by 13
  9. 2024Unveiling Delay Effects in Traffic Forecasting: A Perspective from Spatial-Temporal Delay Differential Equationscited by 11
  10. 2023State of the Art and Potentialities of Graph-level Learningcited by 6
  11. 2024Descriptive Kernel Convolution Network with Improved Random Walk Kernelcited by 5
  12. 2024Rethinking the impact of noisy labels in graph classification: A utility and privacy perspectivecited by 5
7 more
  1. 2026ScienceDB AI: An LLM-Driven Agentic Recommender System for Large-Scale Scientific Data Sharing Servicescited by 5
  2. 2025MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Expertscited by 3
  3. 2022Representation Learning on Heterostructures via Heterogeneous Anonymous Walkscited by 1
  4. 2024Towards Graph Prompt Learning: A Survey and Beyondcited by 1
  5. 2022Graph-level Neural Networks: Current Progress and Future Directionscited by 0
  6. 2024Core Knowledge Learning Framework for Graph Adaptation and Scalability Learningcited by 0
  7. 2025LGRPool: Hierarchical Graph Pooling Via Local-Global Regularisationcited by 0