Bridging Theory and Practice in Link Representation with Graph Neural Networks
1Fondazione Bruno Kessler, Trento, Italy · 2University of Trento, Trento, Italy · 3University of Aalborg, Aalborg, Denmark · *Equal contribution
39th Conference on Neural Information Processing Systems (NeurIPS 2025) · Advances in Neural Information Processing Systems 38
In one sentence. This work unifies message-passing link models by expressiveness, introduces LR-EXP to test whether they distinguish structurally different links, and shows that graph symmetry predicts when expressive models are useful.
Problem
GNN expressiveness theory largely concerns whole-graph representations, while link prediction depends on representations of node pairs. Standard GNNs aggregate endpoint embeddings and can collapse non-automorphic links when their endpoints are automorphic. The paper asks how link models can be compared formally and when additional link-level structural expressiveness improves real-world predictions.
Main contributions
- The kφ-kρ-m framework characterizes endpoint encoders, link-neighborhood encoders, their expressive power, and accessible radius.
- Formal results place Pure GNNs, ELPH, Neo-GNN, NCN/NCNC, and SEAL in an expressiveness hierarchy.
- LR-EXP supplies 1,400 synthetic graphs containing non-automorphic links with 1-WL-indistinguishable endpoints.
- A graph-symmetry score connects structural ambiguity to model performance across 12 link-prediction datasets.
Framework and evaluation
The framework builds a link representation from endpoint embeddings computed by a message-passing function φ and an aggregated m-hop neighborhood representation computed by ρ. Their Weisfeiler–Lehman expressiveness levels are kφ and kρ. LR-EXP trains siamese copies of each model with contrastive loss and applies a reliable paired comparison to determine whether two non-automorphic links receive distinguishable embeddings. Real-world experiments use an efficient WL-based approximation of graph symmetry.
Experimental setting
- Tasks
- Link-representation discrimination on LR-EXP and link prediction under the HeaRT evaluation setting.
- Datasets
- LR-EXP; Cora, CiteSeer, PubMed; ogbl-citation2, ogbl-ddi, ogbl-ppa, ogbl-collab; NSC, YST, GRQ, AIFB, and EDIT-TSW.
- Metrics
- Precision on LR-EXP; mean reciprocal rank (MRR), Hits@10/20, and graph symmetry on real datasets.
- Models
- GCN, GAT, GraphSAGE, GAE, BUDDY/ELPH, Neo-GNN, NCN, NCNC, and SEAL.
Key results
On LR-EXP, pure GNNs score zero precision, NCN and Neo-GNN reach 75%, and SEAL reaches 97%, matching the theoretical ordering. On low-symmetry real datasets, simpler models can remain competitive. Across the six most symmetric datasets, no pure GNN ranks in the top three, while SEAL ranks first, supporting symmetry-aware model selection.
| Dataset / task | Metric | SEAL | Best pure-GNN baseline | Difference |
|---|---|---|---|---|
| LR-EXP / link distinction | Precision | 97 ± 0 | 0 ± 0 | +97 points |
| YST / link prediction | MRR | 17.51 ± 0.94 | GAE: 2.32 ± 0.01 | +15.19 |
| GRQ / link prediction | MRR | 56.72 ± 1.35 | GCN: 6.89 ± 0.47 | +49.83 |
| EDIT-TSW / link prediction | MRR | 25.82 ± 1.47 | GraphSAGE: 8.35 ± 7.27 | +17.47 |
When this work is relevant
This paper is relevant for expressive GNNs for link prediction, pairwise or edge representations, limits of endpoint-only embeddings, automorphic-node failures, structural-feature methods, synthetic expressiveness benchmarks, and choosing between fast pure GNNs and subgraph-based models such as SEAL.
Limitations
The theory covers message-passing link models and does not directly include transformer-based or spectral link architectures. LR-EXP is intentionally small and tests discrimination rather than scalability. The real high-symmetry datasets are also relatively small, so larger benchmarks are needed to study generalization in this regime.
Citation
Persistent identifiers: arXiv:2506.24018 · https://doi.org/10.48550/arXiv.2506.24018