# Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 68 references that are in the map.
- First posted on arXiv 4 Jun 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (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)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [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)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)

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

- [Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvature](https://mlsanity.com/paper/2503.01079/) (2025)
- [Message Passing on the Edge: Towards Scalable and Expressive GNNs](https://mlsanity.com/paper/2510.13615/) (2025)
- [Invariant-Stratified Propagation for Expressive Graph Neural Networks](https://mlsanity.com/paper/2603.01388/) (2026)
- [Treatment Effect Estimation with Differentiated Networked Effect on Graph Data](https://mlsanity.com/paper/2605.24358/) (2026)

## Abstract (arXiv)

Message passing graph neural networks (GNNs) are known to have their expressiveness upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) algorithm. To achieve more powerful GNNs, existing attempts either require ad hoc features, or involve operations that incur high time and space complexities. In this work, we propose a general and provably powerful GNN framework that preserves the scalability of the message passing scheme. In particular, we first propose to empower 1-WL for graph isomorphism test by considering edges among neighbors, giving rise to NC-1-WL. The expressiveness of NC-1-WL is shown to be strictly above 1-WL and below 3-WL theoretically. Further, we propose the NC-GNN framework as a differentiable neural version of NC-1-WL. Our simple implementation of NC-GNN is provably as powerful as NC-1-WL. Experiments demonstrate that our NC-GNN performs effectively and efficiently on various benchmarks.