# Beyond 1-WL with Local Ego-Network Encodings

arXiv: https://arxiv.org/abs/2211.14906 · HTML: https://mlsanity.com/paper/2211.14906/

## Key facts

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

## Builds on (most cited first, 30 of 34)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [NeVAE: A Deep Generative Model for Molecular Graphs](https://mlsanity.com/paper/1802.05283/) (2018)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [k-hop Graph Neural Networks](https://mlsanity.com/paper/1907.06051/) (2019)

## Built on by (most cited first, 2 of 2)

- [Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings](https://mlsanity.com/paper/2312.05905/) (2023)
- [On the Relationship Between Robustness and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2504.13786/) (2025)

## 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.