mlsanityData to 7 Oct 2026

How Powerful are K-hop Message Passing Graph Neural Networks

arXiv 2205.13328 ↗First posted 26 May 2022cs.LG cs.AIcited by 90

Not on the map. Why?

Abstract (arXiv)

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing -- aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by the Weisfeiler-Lehman (1-WL) test. Recently, researchers extended 1-hop message passing to K-hop message passing by aggregating information from K-hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of K-hop message passing. In this work, we theoretically characterize the expressive power of K-hop message passing. Specifically, we first formally differentiate two different kernels of K-hop message passing which are often misused in previous works. We then characterize the expressive power of K-hop message passing by showing that it is more powerful than 1-WL and can distinguish almost all regular graphs. Despite the higher expressive power, we show that K-hop message passing still cannot distinguish some simple regular graphs and its expressive power is bounded by 3-WL. To further enhance its expressive power, we introduce a KP-GNN framework, which improves K-hop message passing by leveraging the peripheral subgraph information in each hop. We show that KP-GNN can distinguish many distance regular graphs which could not be distinguished by previous distance encoding or 3-WL methods. Experimental results verify the expressive power and effectiveness of KP-GNN. KP-GNN achieves competitive results across all benchmark datasets.

Key facts. Cited by 90 papers in the map (data through 7 Oct 2026). Builds on 44 of its 79 references that are in the map. First posted on arXiv 26 May 2022.

Builds on

44 of 79 references.

References · 44

  1. 2017Attention Is All You Needcited by 59,932
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2017Graph Attention Networkscited by 8,854
  4. 2017Inductive Representation Learning on Large Graphscited by 6,284
  5. 2018How Powerful are Graph Neural Networks?cited by 4,355
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  9. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  10. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  11. 2017Deep Setscited by 1,394
  12. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
32 more
  1. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,024
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  3. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  4. 2018Link Prediction Based on Graph Neural Networkscited by 829
  5. 2015Gated Graph Sequence Neural Networkscited by 792
  6. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  7. 2020Benchmarking Graph Neural Networkscited by 672
  8. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  9. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  10. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  11. 2019Provably Powerful Graph Networkscited by 385
  12. 2018Invariant and Equivariant Graph Networkscited by 339
  13. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  14. 2020Can Graph Neural Networks Count Substructures?cited by 235
  15. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  16. 2021Identity-aware Graph Neural Networkscited by 197
  17. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  18. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  19. 2020Random Features Strengthen Graph Neural Networkscited by 184
  20. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  21. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  22. 2021Equivariant Subgraph Aggregation Networkscited by 154
  23. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  24. 2019Relational Pooling for Graph Representationscited by 150
  25. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  26. 2021Nested Graph Neural Networkscited by 136
  27. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  28. 2021Reconstruction for Powerful Graph Representationscited by 65
  29. 2019k-hop Graph Neural Networkscited by 57
  30. 2020Multi-hop Attention Graph Neural Networkcited by 53
  31. 2020The expressive power of kth-order invariant graph networkscited by 34
  32. 2020Graph convolutions that can finally model local structurecited by 31

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 28; 2024: 34; 2025: 16; 2026: 9.

90 papers.

Sort:

By area:

  1. 2023One for All: Towards Training One Graph Model for All Classification Taskscited by 239
  2. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  3. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  4. 2024GOFA: A Generative One-For-All Model for Joint Graph Language Modelingcited by 56
  5. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  6. 2023Locality-Aware Graph-Rewiring in GNNscited by 55
  7. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  8. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  9. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  10. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  11. 2023WL meet VCcited by 30
  12. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
38 more
  1. 2024Unifying Generation and Prediction on Graphs with Latent Graph Diffusioncited by 24
  2. 2024Optimizing OOD Detection in Molecular Graphs: A Novel Approach with Diffusion Modelscited by 21
  3. 2023Curvature Filtrations for Graph Generative Model Evaluationcited by 18
  4. 2023Pure Message Passing Can Estimate Common Neighbor for Link Predictioncited by 18
  5. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  6. 2024Unleashing the Potential of Fractional Calculus in Graph Neural Networks with FRONDcited by 16
  7. 2024Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programscited by 16
  8. 2024FedSSP: Federated Graph Learning with Spectral Knowledge and Personalized Preferencecited by 16
  9. 2023Curve Your Attention: Mixed-Curvature Transformers for Graph Representation Learningcited by 15
  10. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  11. 2023Facilitating Graph Neural Networks with Random Walk on Simplicial Complexescited by 14
  12. 2024Empowering Graph Invariance Learning with Deep Spurious Infomaxcited by 14
  13. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  14. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  15. 2023Effective Structural Encodings via Local Curvature Profilescited by 13
  16. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  17. 2023MAG-GNN: Reinforcement Learning Boosted Graph Neural Networkcited by 11
  18. 2023Recurrent Distance Filtering for Graph Representation Learningcited by 11
  19. 2023Discrete Graph Auto-Encodercited by 10
  20. 2024LLM-Powered Explanations: Unraveling Recommendations Through Subgraph Reasoningcited by 10
  21. 2024TAGLAS: An atlas of text-attributed graph datasets in the era of large graph and language modelscited by 9
  22. 2024Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Informationcited by 9
  23. 2023Deep Prompt Tuning for Graph Transformerscited by 8
  24. 2025Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvaturecited by 8
  25. 2024Distributed-Order Fractional Graph Operating Networkcited by 7
  26. 2023From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisitedcited by 6
  27. 2025Enhancing Graph Representation Learning with Localized Topological Featurescited by 6
  28. 2023Tailoring Self-Attention for Graph via Rooted Subtreescited by 5
  29. 2024A Clifford Algebraic Approach to E(n)-Equivariant High-order Graph Neural Networkscited by 5
  30. 2025HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representationscited by 5
  31. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  32. 2023Improving Graph Neural Networks on Multi-node Tasks with the Labeling Trickcited by 4
  33. 2024Graph as Point Setcited by 4
  34. 2024Demystifying Higher-Order Graph Neural Networkscited by 4
  35. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  36. 2024Rethinking the Effectiveness of Graph Classification Datasets in Benchmarks for Assessing GNNscited by 4
  37. 2025Unlearning Inversion Attacks for Graph Neural Networkscited by 4
  38. 2025Training Transformers for Mesh-Based Simulationscited by 4

50 most cited of 90 All 90 (JSON)