mlsanityData to 7 Oct 2026

Beyond 1-WL with Local Ego-Network Encodings

arXiv 2211.14906 ↗First posted 27 Nov 2022cs.LG cs.SIcited by 2

Not on the map. Why?

Abstract (arXiv)

Identifying similar network structures is key to capture graph isomorphisms and learn representations that exploit structural information encoded in graph data. This work shows that ego-networks can produce a structural encoding scheme for arbitrary graphs with greater expressivity than the Weisfeiler-Lehman (1-WL) test. We introduce IGEL, a preprocessing step to produce features that augment node representations by encoding ego-networks into sparse vectors that enrich Message Passing (MP) Graph Neural Networks (GNNs) beyond 1-WL expressivity. We describe formally the relation between IGEL and 1-WL, and characterize its expressive power and limitations. Experiments show that IGEL matches the empirical expressivity of state-of-the-art methods on isomorphism detection while improving performance on seven GNN architectures.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 34 of its 42 references that are in the map. First posted on arXiv 27 Nov 2022.

Builds on

34 of 42 references.

References · 34

  1. 2017Graph Attention Networkscited by 8,854
  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. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  7. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  8. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  9. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  10. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  11. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  12. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
22 more
  1. 2020Benchmarking Graph Neural Networkscited by 672
  2. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  3. 2019Provably Powerful Graph Networkscited by 385
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  5. 2020Can Graph Neural Networks Count Substructures?cited by 235
  6. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  7. 2019Position-aware Graph Neural Networkscited by 203
  8. 2021Identity-aware Graph Neural Networkscited by 197
  9. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  10. 2020Design Space for Graph Neural Networkscited by 182
  11. 2021Equivariant Subgraph Aggregation Networkscited by 154
  12. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  13. 2021Nested Graph Neural Networkscited by 136
  14. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  15. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  16. 2018NeVAE: A Deep Generative Model for Molecular Graphscited by 66
  17. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  18. 2019k-hop Graph Neural Networkscited by 57
  19. 2022Message passing all the way upcited by 47
  20. 2021Ego-GNNs: Exploiting Ego Structures in Graph Neural Networkscited by 17
  21. 2017On the expressive power of query languages for matricescited by 14
  22. 2018On the expressive power of linear algebra on graphscited by 14

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 0; 2025: 1.

2 papers.

  1. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  2. 2025On the Relationship Between Robustness and Expressivity of Graph Neural Networkscited by 3