mlsanityData to 7 Oct 2026

A Topological Perspective on Demystifying GNN-Based Link Prediction Performance

arXiv 2310.04612 ↗First posted 6 Oct 2023cs.LG cs.SIcited by 11

Not on the map. Why?

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.

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

Builds on

33 of 46 references.

References · 33

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  4. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  5. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,134
  6. 2018Link Prediction Based on Graph Neural Networkscited by 829
  7. 2020Temporal Graph Networks for Deep Learning on Dynamic Graphscited by 521
  8. 2019Diffusion Improves Graph Learningcited by 414
  9. 2020Graph Neural Networks with Heterophilycited by 202
  10. 2021GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networkscited by 147
  11. 2018Streaming Graph Neural Networkscited by 91
  12. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
21 more
  1. 2022Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Predictioncited by 78
  2. 2021User-oriented Fairness in Recommendationcited by 75
  3. 2021Learning from Counterfactual Links for Link Predictioncited by 69
  4. 2023Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarkingcited by 69
  5. 2023Neural Common Neighbor with Completion for Link Predictioncited by 64
  6. 2022GraphWorld: Fake Graphs Bring Real Insights for GNNscited by 56
  7. 2020AutoEmb: Automated Embedding Dimensionality Search in Streaming Recommendationscited by 47
  8. 2020Graph Convolutional Networks for Graphs Containing Missing Featurescited by 46
  9. 2020Pre-Training Graph Neural Networks for Cold-Start Users and Items Representationcited by 42
  10. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  11. 2022Linkless Link Prediction via Relational Distillationcited by 39
  12. 2021Neural Link Prediction with Walk Poolingcited by 36
  13. 2020Inductive Link Prediction for Nodes Having Only Attribute Informationcited by 30
  14. 2019Fast and Accurate Network Embeddings via Very Sparse Random Projectioncited by 29
  15. 2021Imbalanced Graph Classification via Graph-of-Graph Neural Networkscited by 27
  16. 2022Experiments on Generalizability of User-Oriented Fairness in Recommender Systemscited by 13
  17. 2022RecipeRec: A Heterogeneous Graph Learning Model for Recipe Recommendationcited by 13
  18. 2022FakeEdge: Alleviate Dataset Shift in Link Predictioncited by 12
  19. 2022ChemicalX: A Deep Learning Library for Drug Pair Scoringcited by 11
  20. 2022Revisiting Neighborhood-based Link Prediction for Collaborative Filteringcited by 11
  21. 2022Link Prediction with Non-Contrastive Learningcited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 6; 2025: 3; 2026: 2.

11 papers.

  1. 2024Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Miningcited by 20
  2. 2024Optimizing Long-tailed Link Prediction in Graph Neural Networks through Structure Representation Enhancementcited by 9
  3. 2025GiGL: Large-Scale Graph Neural Networks at Snapchatcited by 8
  4. 2025Scalable Graph Condensation with Evolving Capabilitiescited by 6
  5. 2024How Does Message Passing Improve Collaborative Filtering?cited by 5
  6. 2024Edge Classification on Graphs: New Directions in Topological Imbalancecited by 4
  7. 2024PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extractioncited by 2
  8. 2025Intellectual Property in Graph-Based Machine Learning as a Service: Attacks and Defensescited by 2
  9. 2024Towards Understanding Link Predictor Generalizability Under Distribution Shiftscited by 0
  10. 2026Advancing Edge Classification through High-Dimensional Causal Modeling of Node-Edge Interplaycited by 0
  11. 2026A Survey on GNN-based Link Prediction: Techniques, Applications, and Challengescited by 0