# Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 22 Jul 2021.

## Builds on (most cited first, 15 of 15)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [Spectral properties of the Laplacian of multiplex networks](https://mlsanity.com/paper/1307.2090/) (2013)

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

- [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)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [A Theoretical Comparison of Graph Neural Network Extensions](https://mlsanity.com/paper/2201.12884/) (2022)
- [An Efficient Subgraph GNN with Provable Substructure Counting Power](https://mlsanity.com/paper/2303.10576/) (2023)
- [Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman](https://mlsanity.com/paper/2306.03266/) (2023)
- [Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach](https://mlsanity.com/paper/2201.05158/) (2022)
- [From Graphs to Qubits: A Critical Review of Quantum Graph Neural Networks](https://mlsanity.com/paper/2408.06524/) (2024)
- [Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm](https://mlsanity.com/paper/2206.02059/) (2022)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Beyond 1-WL with Local Ego-Network Encodings](https://mlsanity.com/paper/2211.14906/) (2022)
- [A Graph-based Methodology for the Sensorless Estimation of Road Traffic Profiles](https://mlsanity.com/paper/2201.04968/) (2022)
- [Scale-aware Message Passing For Graph Node Classification](https://mlsanity.com/paper/2411.19392/) (2024)
- [OpenGLT: A Comprehensive Benchmark of Graph Neural Networks for Graph-Level Tasks](https://mlsanity.com/paper/2501.00773/) (2025)
- [BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs](https://mlsanity.com/paper/2504.10948/) (2025)

## Abstract (arXiv)

Graph neural networks (GNNs) have achieved remarkable success as a framework for deep learning on graph-structured data. However, GNNs are fundamentally limited by their tree-structured inductive bias: the WL-subtree kernel formulation bounds the representational capacity of GNNs, and polynomial-time GNNs are provably incapable of recognizing triangles in a graph. In this work, we propose to augment the GNN message-passing operations with information defined on ego graphs (i.e., the induced subgraph surrounding each node). We term these approaches Ego-GNNs and show that Ego-GNNs are provably more powerful than standard message-passing GNNs. In particular, we show that Ego-GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real-world graphs. We also motivate our approach from the perspective of graph signal processing as a form of multiplex graph convolution. Experimental results on node classification using synthetic and real data highlight the achievable performance gains using this approach.