# Bridging Theory and Practice in Link Representation with Graph Neural Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 60 references that are in the map.
- First posted on arXiv 30 Jun 2025.

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

- [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)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [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)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Relational Pooling for Graph Representations](https://mlsanity.com/paper/1903.02541/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Line Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2010.10046/) (2020)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding](https://mlsanity.com/paper/2011.11545/) (2020)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Simplifying approach to Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2111.06748/) (2021)
- [Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks](https://mlsanity.com/paper/2502.14546/) (2025)
- [Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Models](https://mlsanity.com/paper/1906.09427/) (2019)
- [The expressive power of pooling in Graph Neural Networks](https://mlsanity.com/paper/2304.01575/) (2023)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphs](https://mlsanity.com/paper/2302.02209/) (2023)
- [From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks](https://mlsanity.com/paper/2305.04963/) (2023)

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

- [Rethinking GNNs and Missing Features: Challenges, Evaluation and a Robust Solution](https://mlsanity.com/paper/2601.04855/) (2026)
- [Plain Transformers are Surprisingly Powerful Link Predictors](https://mlsanity.com/paper/2602.01553/) (2026)
- [On the Expressive Power of Implicit Line-Graph Higher-Order Weisfeiler--Leman](https://mlsanity.com/paper/2609.16412/) (2026)
- [Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction](https://mlsanity.com/paper/2609.34729/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are widely used to compute representations of node pairs for downstream tasks such as link prediction. Yet, theoretical understanding of their expressive power has focused almost entirely on graph-level representations. In this work, we shift the focus to links and provide the first comprehensive study of GNN expressiveness in link representation. We introduce a unifying framework, the kφ-kρ-m framework, that subsumes existing message-passing link models and enables formal expressiveness comparisons. Using this framework, we derive a hierarchy of state-of-the-art methods and offer theoretical tools to analyze future architectures. To complement our analysis, we propose a synthetic evaluation protocol comprising the first benchmark specifically designed to assess link-level expressiveness. Finally, we ask: does expressiveness matter in practice? We use a graph symmetry metric that quantifies the difficulty of distinguishing links and show that while expressive models may underperform on standard benchmarks, they significantly outperform simpler ones as symmetry increases, highlighting the need for dataset-aware model selection.