# EDEN: A Plug-in Equivariant Distance Encoding to Beyond the 1-WL Test

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 19 Nov 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [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)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [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)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Expressive Power of Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/2006.15646/) (2020)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties](https://mlsanity.com/paper/1811.04801/) (2018)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)

## Abstract (arXiv)

The message-passing scheme is the core of graph representation learning. While most existing message-passing graph neural networks (MPNNs) are permutation-invariant in graph-level representation learning and permutation-equivariant in node- and edge-level representation learning, their expressive power is commonly limited by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. Recently proposed expressive graph neural networks (GNNs) with specially designed complex message-passing mechanisms are not practical. To bridge the gap, we propose a plug-in Equivariant Distance ENcoding (EDEN) for MPNNs. EDEN is derived from a series of interpretable transformations on the graph's distance matrix. We theoretically prove that EDEN is permutation-equivariant for all level graph representation learning, and we empirically illustrate that EDEN's expressive power can reach up to the 3-WL test. Extensive experiments on real-world datasets show that combining EDEN with conventional GNNs surpasses recent advanced GNNs.