# Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2020.

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

- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes](https://mlsanity.com/paper/2310.19285/) (2023)
- [Unsupervised Network Embedding Beyond Homophily](https://mlsanity.com/paper/2203.10866/) (2022)
- [Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation](https://mlsanity.com/paper/2205.09389/) (2022)
- [From Graphs to Hypergraphs: Hypergraph Projection and its Remediation](https://mlsanity.com/paper/2401.08519/) (2024)
- [Weisfeiler and Leman Go Measurement Modeling: Probing the Validity of the WL Test](https://mlsanity.com/paper/2307.05775/) (2023)
- [Bridging Distance and Spectral Positional Encodings via Anchor-Based Diffusion Geometry Approximation](https://mlsanity.com/paper/2601.04517/) (2026)

## Abstract (arXiv)

Learning representations of sets of nodes in a graph is crucial for applications ranging from node-role discovery to link prediction and molecule classification. Graph Neural Networks (GNNs) have achieved great success in graph representation learning. However, expressive power of GNNs is limited by the 1-Weisfeiler-Lehman (WL) test and thus GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order-WL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph. Here we propose and mathematically analyze a general class of structure-related features, termed Distance Encoding (DE). DE assists GNNs in representing any set of nodes, while providing strictly more expressive power than the 1-WL test. DE captures the distance between the node set whose representation is to be learned and each node in the graph. To capture the distance DE can apply various graph-distance measures such as shortest path distance or generalized PageRank scores. We propose two ways for GNNs to use DEs (1) as extra node features, and (2) as controllers of message aggregation in GNNs. Both approaches can utilize the sparse structure of the underlying graph, which leads to computational efficiency and scalability. We also prove that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. We evaluate DE on three tasks over six real networks: structural role prediction, link prediction, and triangle prediction. Results show that our models outperform GNNs without DE by up-to 15% in accuracy and AUROC. Furthermore, our models also significantly outperform other state-of-the-art methods especially designed for the above tasks.