mlsanityData to 7 Oct 2026

FakeEdge: Alleviate Dataset Shift in Link Prediction

arXiv 2211.15899 ↗First posted 29 Nov 2022cs.LG cs.SI stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

Link prediction is a crucial problem in graph-structured data. Due to the recent success of graph neural networks (GNNs), a variety of GNN-based models were proposed to tackle the link prediction task. Specifically, GNNs leverage the message passing paradigm to obtain node representation, which relies on link connectivity. However, in a link prediction task, links in the training set are always present while ones in the testing set are not yet formed, resulting in a discrepancy of the connectivity pattern and bias of the learned representation. It leads to a problem of dataset shift which degrades the model performance. In this paper, we first identify the dataset shift problem in the link prediction task and provide theoretical analyses on how existing link prediction methods are vulnerable to it. We then propose FakeEdge, a model-agnostic technique, to address the problem by mitigating the graph topological gap between training and testing sets. Extensive experiments demonstrate the applicability and superiority of FakeEdge on multiple datasets across various domains.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 33 of its 64 references that are in the map. First posted on arXiv 29 Nov 2022.

Builds on

33 of 64 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. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  7. 2016Variational Graph Auto-Encoderscited by 1,373
  8. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  9. 2015Effective Approaches to Attention-based Neural Machine Translationcited by 1,024
  10. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  11. 2018Link Prediction Based on Graph Neural Networkscited by 829
  12. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
21 more
  1. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  2. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  3. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  4. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  5. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  6. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 163
  7. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 148
  8. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  9. 2021Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Datacited by 86
  10. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  11. 2021Learning from Counterfactual Links for Link Predictioncited by 69
  12. 2022Graph Data Augmentation for Graph Machine Learning: A Surveycited by 61
  13. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  14. 2022Linkless Link Prediction via Relational Distillationcited by 39
  15. 2022OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphscited by 38
  16. 2021Neural Link Prediction with Walk Poolingcited by 36
  17. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  18. 2015Evaluating Link Prediction Methodscited by 31
  19. 2021Pairwise Learning for Neural Link Predictioncited by 23
  20. 2021Edge Proposal Sets for Link Predictioncited by 16
  21. 2022Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Predictioncited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 6; 2025: 0; 2026: 1.

12 papers.

  1. 2023Neural Common Neighbor with Completion for Link Predictioncited by 64
  2. 2023Knowledge Distillation on Graphs: A Surveycited by 38
  3. 2023Pure Message Passing Can Estimate Common Neighbor for Link Predictioncited by 18
  4. 2024A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptationcited by 16
  5. 2023Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practicescited by 13
  6. 2024Universal Link Predictor By In-Context Learning on Graphscited by 12
  7. 2023A Topological Perspective on Demystifying GNN-Based Link Prediction Performancecited by 11
  8. 2024Beyond Generalization: A Survey of Out-Of-Distribution Adaptation on Graphscited by 6
  9. 2024Node Duplication Improves Cold-start Link Predictioncited by 4
  10. 2024CORE: Data Augmentation for Link Prediction via Information Bottleneckcited by 0
  11. 2024Towards Understanding Link Predictor Generalizability Under Distribution Shiftscited by 0
  12. 2026A Survey on GNN-based Link Prediction: Techniques, Applications, and Challengescited by 0