mlsanityData to 14 Oct 2026

k-hop Graph Neural Networks

arXiv 1907.06051 ↗First posted 13 Jul 2019stat.ML cs.LGcited by 57

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) have emerged recently as a powerful architecture for learning node and graph representations. Standard GNNs have the same expressive power as the Weisfeiler-Leman test of graph isomorphism in terms of distinguishing non-isomorphic graphs. However, it was recently shown that this test cannot identify fundamental graph properties such as connectivity and triangle freeness. We show that GNNs also suffer from the same limitation. To address this limitation, we propose a more expressive architecture, k-hop GNNs, which updates a node's representation by aggregating information not only from its direct neighbors, but from its k-hop neighborhood. We show that the proposed architecture can identify fundamental graph properties. We evaluate the proposed architecture on standard node classification and graph classification datasets. Our experimental evaluation confirms our theoretical findings since the proposed model achieves performance better or comparable to standard GNNs and to state-of-the-art algorithms.

Key facts. Cited by 57 papers in the map (data through 14 Oct 2026). First posted on arXiv 13 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 11; 2023: 18; 2024: 12; 2025: 8; 2026: 4.

57 papers.

Sort:

  1. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 166
  2. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  3. 2021Nested Graph Neural Networkscited by 137
  4. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  5. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  6. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  7. 2023Locality-Aware Graph-Rewiring in GNNscited by 56
  8. 2024KAGNNs: Kolmogorov-Arnold Networks meet Graph Learningcited by 49
  9. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  10. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 36
  11. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  12. 2023Prot2Text: Multimodal Protein's Function Generation with GNNs and Transformerscited by 32
38 more
  1. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  2. 2024Understanding Virtual Nodes: Oversquashing and Node Heterogeneitycited by 14
  3. 2024Empowering Graph Invariance Learning with Deep Spurious Infomaxcited by 14
  4. 2021Graph Kernel Neural Networkscited by 13
  5. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  6. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  7. 2023Recurrent Distance Filtering for Graph Representation Learningcited by 11
  8. 2024Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Informationcited by 9
  9. 2022Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representationscited by 7
  10. 2025Graph Spectral Filtering with Chebyshev Interpolation for Recommendationcited by 7
  11. 2022Graph-in-Graph (GiG): Learning interpretable latent graphs in non-Euclidean domain for biological and healthcare applicationscited by 4
  12. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  13. 2023What Do GNNs Actually Learn? Towards Understanding their Representationscited by 4
  14. 2023Generating Post-hoc Explanations for Skip-gram-based Node Embeddings by Identifying Important Nodes with Bridgenesscited by 4
  15. 2023DeSCo: Towards Generalizable and Scalable Deep Subgraph Countingcited by 4
  16. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  17. 2022Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classificationcited by 3
  18. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  19. 2024Strada-LLM: Graph LLM for traffic predictioncited by 3
  20. 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2
  21. 2023Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions?cited by 2
  22. 2025Generalization Performance of Hypergraph Neural Networkscited by 2
  23. 2022SPGP: Structure Prototype Guided Graph Poolingcited by 1
  24. 2023A Network Science perspective of Graph Convolutional Networks: A surveycited by 1
  25. 2024wav2graph: A Framework for Supervised Learning Knowledge Graph from Speechcited by 1
  26. 2025Over-Squashing in GNNs and Causal Inference of Rewiring Strategiescited by 1
  27. 2025Memorization in Graph Neural Networkscited by 1
  28. 2021Ego-based Entropy Measures for Structural Representations on Graphscited by 0
  29. 2022Using Graph Algorithms to Pretrain Graph Completion Transformerscited by 0
  30. 2023GE-Blender: Graph-Based Knowledge Enhancement for Blendercited by 0
  31. 2023Supervised Attention Using Homophily in Graph Neural Networkscited by 0
  32. 2023Hybrid Focal and Full-Range Attention Based Graph Transformerscited by 0
  33. 2024WEST GCN-LSTM: Weighted Stacked Spatio-Temporal Graph Neural Networks for Regional Traffic Forecastingcited by 0
  34. 2024Rule Based Learning with Dynamic (Graph) Neural Networkscited by 0
  35. 2024Sampling Foundational Transformer: A Theoretical Perspectivecited by 0
  36. 2024Celcomen: spatial causal disentanglement for single-cell and tissue perturbation modelingcited by 0
  37. 2024Enhancing GNNs with Architecture-Agnostic Graph Transformations: A Systematic Analysiscited by 0
  38. 2025OpenGLT: A Comprehensive Benchmark of Graph Neural Networks for Graph-Level Taskscited by 0

50 most cited of 57 All 57 (JSON)