Research map / Graph learning / GNN architectures
Bridging Theory and Practice in Link Representation with Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a unifying k_phi-k_rho-m framework for message-passing link representations, derives an expressiveness hierarchy, introduces the LR-EXP synthetic benchmark, and shows that expressive models win on real link-prediction datasets as graph symmetry increases.
Problem
Theoretical understanding of GNN expressiveness has focused on graph-level representations, while the ability of message-passing models to distinguish node pairs (links) is poorly understood, and it is unclear whether expressiveness matters for link prediction in practice.
Approach
A general framework combining endpoint node representations (via phi, k_phi) with a pairwise representation of the m-order joint neighborhood (via rho, k_rho, radius m) that subsumes Pure GNN, NCN, NCNC, ELPH, BUDDY, Neo-GNN and SEAL, enabling formal expressiveness comparisons and a hierarchy; plus a graph symmetry metric based on WL color counts to predict when expressive models help.
Key results
- On LR-EXP, SEAL distinguishes 97% of non-automorphic links versus 75% for Neo-GNN and NCN, 62% for ELPH, 45% for BUDDY, and 0% for pure GNNs.
- On the highest-symmetry real datasets (e.g., edit-tsw, aifb, GRQ), SEAL ranks first in MRR (25.82 on edit-tsw vs. 10.32 for NCN and 8.10 for Neo-GNN).
- Pure GNN methods rank among the top three on the five least symmetric datasets but none appears in the top three on the six most symmetric datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use link-aware subgraph labeling and message passing rather than endpoint-only GNN representations | Link representation models · LR-EXP test | precision (%): 0 { ($\pm$ 0)} -> 97 { ($\pm$ 0)} | Helped |
| Use approximate common-neighbor counting in BUDDY instead of ELPH's counting | BUDDY versus ELPH · LR-EXP test | precision (%): 62 { ($\pm$ 7)} -> 45 { ($\pm$ 1)} | Hurt |
| Increase model expressiveness as graph symmetry increases | Link prediction models · Real-world link prediction benchmarks | MRR | Mixed |
Surprising findings
- Expressive models such as SEAL can underperform simpler models like NCN and GCN on standard low-symmetry benchmarks (e.g., SEAL 10.67 vs GAE 18.32 on Cora).
Limitations
- The framework is restricted to message-passing models and does not cover transformer-based or spectral link representation methods.
- High-symmetry evaluation datasets are relatively small, limiting assessment of generalization.
- LR-EXP is small by design (1400 graphs), so it probes expressivity rather than scalability.
Experimental setup
Datasets: Cora Citeseer Pubmed ogbl-citation2 ogbl-ddi ogbl-ppa ogbl-collab NSC YST GRQ aifb edit-tsw
Benchmarks: LR-EXP Cora Citeseer Pubmed ogbl-citation2 ogbl-ddi ogbl-ppa ogbl-collab NSC YST GRQ aifb
Metrics: precision MRR
Baselines: GCN GAT GAE SAGE BUDDY ELPH Neo-GNN NCN NCNC
Builds on: SEAL NCN ELPH Neo-GNN BUDDY
Closest papers by meaning
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.92)
- An Empirical Study of Realized GNN Expressiveness (ICML 2024 · similarity 0.91)
- Spectral Basis Learning for Expressive Graph Neural Networks in Link Prediction (AAAI 2026 · similarity 0.91)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.90)
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.90)
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.