Research map / Graph learning / GNN architectures
A Topological Perspective on Demystifying GNN-Based Link Prediction Performance
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 Topological Concentration (TC) and its scalable approximation ATC to explain node-varying GNN link prediction performance, identifies topological distribution shift, and boosts LP via TC-inspired edge reweighting.
Problem
GNN-based link prediction performance varies across nodes, but prior work studied node-varying performance only for node/graph classification or general cold-start LP; degree is a weak predictor of per-node LP performance.
Approach
Measure each node's local topology by the average intersection between its K-hop computation tree and those of its neighbors (Topological Concentration), approximate it cheaply via propagated Gaussian random projections (ATC), and reweight message-passing edges toward neighbors that are better connected to the neighborhood to raise TC and LP performance.
Key results
- TC^Tr achieves higher Pearson correlation with node LP performance than degree and subgraph density (the paper reports about 82.10% more correlation than degree).
- Edge reweighting (GCN_rw) improves GCN on Cora from 70.63 to 75.98 Hits@100 and on Citeseer from 65.96 to 74.40 Hits@100.
- NCN_rw gives only modest gains over NCN (e.g., Cora 87.73 to 87.95 Hits@100), since NCN already captures common-neighbor signals.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add weighted message-passing to GCN | GCN · Cora, Citeseer, Collab, Citation2, Reptile, Vole | Hits@100 (Hits@50 on Collab; MRR on Citation2): 70.63$\pm$0.67 -> 75.98$\pm$1.28; 65.96$\pm$2.12 -> 74.40$\pm$1.13; 49.52$\pm$0.52 -> 52.85$\pm$0.14; 84.42$\pm$0.05 -> | Helped |
| Add weighted message-passing to GCN | GCN · Pubmed | Hits@100: 69.35$\pm$1.02 -> 68.87$\pm$0.99 | Hurt |
| Add weighted message-passing to SAGE | SAGE · Cora, Citeseer, Pubmed, Collab, Citation2, Reptile, Vole | Hits@100 (Hits@50 on Collab; MRR on Citation2): 74.27$\pm$2.08 -> 74.62$\pm$2.30; 61.57$\pm$3.28 -> 69.89$\pm$1.66; 66.25$\pm$1.08 -> 66.77$\pm$0.69; 50.01$\pm$0.50 -> | Helped |
| Add weighted message-passing to NCN | NCN · Cora, Citeseer, Pubmed, Reptile, Vole | Hits@100: 87.73$\pm$1.41 -> 87.95$\pm$1.30; 90.93$\pm$0.83 -> 91.86$\pm$0.82; 76.20$\pm$1.55 -> 76.51$\pm$1.41; 68.37$\pm$3.57 -> | Helped |
| Add weighted message-passing to NCN | NCN · Collab | Hits@50: 54.43$\pm$0.17 -> 54.16$\pm$0.24 | Hurt |
| Add weighted message-passing to GCN, SAGE, or NCN | GCN, SAGE, and NCN · Link prediction benchmarks | LP performance | Mixed |
Surprising findings
- Cold-start nodes (low degree) often perform better than high-degree nodes on Collab and Citation2, contrary to the common belief.
- Precision, F1 and NDCG have degree-related evaluation bias: even an untrained predictor's scores rise with node degree.
Limitations
- TC is correlational rather than causal; the reweighting boosts are modest and inconsistent (e.g., NCN gains are small)
- Exact TC is computationally expensive for large graphs, e.g., only up to 3 hops for Collab
- Theoretical ATC approximation relies on assumptions (e.g., independence of embeddings, uniform inverse-degree averages) that are not fully satisfied
Experimental setup
Datasets: Cora Citeseer Pubmed Collab Citation2 Reptile Vole
Benchmarks: Cora Citeseer Pubmed Collab Citation2 Reptile Vole
Metrics: Hits@100 Hits@50 MRR Recall Precision F1 NDCG Hits^N@K Pearson correlation
Baselines: GCN SAGE NCN LightGCN
Builds on: GCN GraphSAGE NCN LightGCN
Closest papers by meaning
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.90)
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.90)
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.90)
- Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2024 · similarity 0.90)
- Structural Information Enhanced Graph Representation for Link Prediction (AAAI 2024 · similarity 0.89)
- Implicit degree bias in the link prediction task (ICML 2025 · similarity 0.89)
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.