mlsanityData to 14 Oct 2026

Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings

arXiv 2312.05905 ↗First posted 10 Dec 2023cs.LG cs.AIcited by 4

Not on the map. Why?

Abstract (arXiv)

We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features or extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP-GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match or improve previous baselines on expressivity, graph classification, graph regression, and proximity tasks -- while reducing memory usage by 18.1x in certain real-world settings.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 43 of its 52 references that are in the map. First posted on arXiv 10 Dec 2023.

Builds on

43 of 52 references.

References · 43

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  6. 2019Strategies for Pre-training Graph Neural Networkscited by 971
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  8. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  11. 2019Graph Transformer Networkscited by 523
  12. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
31 more
  1. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  2. 2019Provably Powerful Graph Networkscited by 389
  3. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  5. 2020Can Graph Neural Networks Count Substructures?cited by 236
  6. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  7. 2019Position-aware Graph Neural Networkscited by 203
  8. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  9. 2021Identity-aware Graph Neural Networkscited by 198
  10. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  11. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  12. 2021Equivariant Subgraph Aggregation Networkscited by 154
  13. 2021Nested Graph Neural Networkscited by 137
  14. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  15. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  16. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  17. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  18. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  19. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
  20. 2021The Logic of Graph Neural Networkscited by 85
  21. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  22. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  23. 2019k-hop Graph Neural Networkscited by 57
  24. 2022Ordered Subgraph Aggregation Networkscited by 57
  25. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  26. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  27. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  28. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  29. 2022pathGCN: Learning General Graph Spatial Operators from Pathscited by 15
  30. 2021Subgraph Permutation Equivariant Networkscited by 2
  31. 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2

Built on by

Cited by year

Citing papers per year: 2024: 3; 2025: 1.

4 papers.

  1. 2024Revisiting Random Walks for Learning on Graphscited by 13
  2. 2025Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Studycited by 2
  3. 2024WLPlan: Relational Features for Symbolic Planningcited by 1
  4. 2024Graph Learning for Planning: The Story Thus Far and Open Challengescited by 0