# A Topological Perspective on Demystifying GNN-Based Link Prediction Performance

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 46 references that are in the map.
- First posted on arXiv 6 Oct 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks](https://mlsanity.com/paper/2103.08826/) (2021)
- [Streaming Graph Neural Networks](https://mlsanity.com/paper/1810.10627/) (2018)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [User-oriented Fairness in Recommendation](https://mlsanity.com/paper/2104.10671/) (2021)
- [Learning from Counterfactual Links for Link Prediction](https://mlsanity.com/paper/2106.02172/) (2021)
- [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)
- [GraphWorld: Fake Graphs Bring Real Insights for GNNs](https://mlsanity.com/paper/2203.00112/) (2022)
- [AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendations](https://mlsanity.com/paper/2002.11252/) (2020)
- [Graph Convolutional Networks for Graphs Containing Missing Features](https://mlsanity.com/paper/2007.04583/) (2020)
- [Pre-Training Graph Neural Networks for Cold-Start Users and Items Representation](https://mlsanity.com/paper/2012.07064/) (2020)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (2022)
- [Neural Link Prediction with Walk Pooling](https://mlsanity.com/paper/2110.04375/) (2021)
- [Inductive Link Prediction for Nodes Having Only Attribute Information](https://mlsanity.com/paper/2007.08053/) (2020)
- [Fast and Accurate Network Embeddings via Very Sparse Random Projection](https://mlsanity.com/paper/1908.11512/) (2019)
- [Imbalanced Graph Classification via Graph-of-Graph Neural Networks](https://mlsanity.com/paper/2112.00238/) (2021)
- [Experiments on Generalizability of User-Oriented Fairness in Recommender Systems](https://mlsanity.com/paper/2205.08289/) (2022)
- [RecipeRec: A Heterogeneous Graph Learning Model for Recipe Recommendation](https://mlsanity.com/paper/2205.14005/) (2022)
- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)

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

- [Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining](https://mlsanity.com/paper/2403.04780/) (2024)
- [Optimizing Long-tailed Link Prediction in Graph Neural Networks through Structure Representation Enhancement](https://mlsanity.com/paper/2407.20499/) (2024)
- [GiGL: Large-Scale Graph Neural Networks at Snapchat](https://mlsanity.com/paper/2502.15054/) (2025)
- [Scalable Graph Condensation with Evolving Capabilities](https://mlsanity.com/paper/2502.17614/) (2025)
- [How Does Message Passing Improve Collaborative Filtering?](https://mlsanity.com/paper/2404.08660/) (2024)
- [Edge Classification on Graphs: New Directions in Topological Imbalance](https://mlsanity.com/paper/2406.11685/) (2024)
- [Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defenses](https://mlsanity.com/paper/2508.19641/) (2025)
- [PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction](https://mlsanity.com/paper/2404.15225/) (2024)
- [Towards Understanding Link Predictor Generalizability Under Distribution Shifts](https://mlsanity.com/paper/2406.08788/) (2024)
- [Advancing Edge Classification through High-Dimensional Causal Modeling of Node-Edge Interplay](https://mlsanity.com/paper/2605.00374/) (2026)
- [A Survey on GNN-based Link Prediction: Techniques, Applications, and Challenges](https://mlsanity.com/paper/2607.16198/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have shown great promise in learning node embeddings for link prediction (LP). While numerous studies aim to improve the overall LP performance of GNNs, none have explored its varying performance across different nodes and its underlying reasons. To this end, we aim to demystify which nodes will perform better from the perspective of their local topology. Despite the widespread belief that low-degree nodes exhibit poorer LP performance, our empirical findings provide nuances to this viewpoint and prompt us to propose a better metric, Topological Concentration (TC), based on the intersection of the local subgraph of each node with the ones of its neighbors. We empirically demonstrate that TC has a higher correlation with LP performance than other node-level topological metrics like degree and subgraph density, offering a better way to identify low-performing nodes than using cold-start. With TC, we discover a novel topological distribution shift issue in which newly joined neighbors of a node tend to become less interactive with that node's existing neighbors, compromising the generalizability of node embeddings for LP at testing time. To make the computation of TC scalable, We further propose Approximated Topological Concentration (ATC) and theoretically/empirically justify its efficacy in approximating TC and reducing the computation complexity. Given the positive correlation between node TC and its LP performance, we explore the potential of boosting LP performance via enhancing TC by re-weighting edges in the message-passing and discuss its effectiveness with limitations. Our code is publicly available at https://github.com/YuWVandy/Topo_LP_GNN.