# FakeEdge: Alleviate Dataset Shift in Link Prediction

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

## Key facts

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

## 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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data](https://mlsanity.com/paper/2108.01099/) (2021)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [Learning from Counterfactual Links for Link Prediction](https://mlsanity.com/paper/2106.02172/) (2021)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (2022)
- [OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs](https://mlsanity.com/paper/2205.15117/) (2022)
- [Neural Link Prediction with Walk Pooling](https://mlsanity.com/paper/2110.04375/) (2021)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [Evaluating Link Prediction Methods](https://mlsanity.com/paper/1505.04094/) (2015)

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

- [Neural Common Neighbor with Completion for Link Prediction](https://mlsanity.com/paper/2302.00890/) (2023)
- [Knowledge Distillation on Graphs: A Survey](https://mlsanity.com/paper/2302.00219/) (2023)
- [Pure Message Passing Can Estimate Common Neighbor for Link Prediction](https://mlsanity.com/paper/2309.00976/) (2023)
- [A Survey of Deep Graph Learning under Distribution Shifts: from Graph Out-of-Distribution Generalization to Adaptation](https://mlsanity.com/paper/2410.19265/) (2024)
- [Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices](https://mlsanity.com/paper/2306.00899/) (2023)
- [Universal Link Predictor By In-Context Learning on Graphs](https://mlsanity.com/paper/2402.07738/) (2024)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [Beyond Generalization: A Survey of Out-Of-Distribution Adaptation on Graphs](https://mlsanity.com/paper/2402.11153/) (2024)
- [Node Duplication Improves Cold-start Link Prediction](https://mlsanity.com/paper/2402.09711/) (2024)
- [CORE: Data Augmentation for Link Prediction via Information Bottleneck](https://mlsanity.com/paper/2404.11032/) (2024)
- [Towards Understanding Link Predictor Generalizability Under Distribution Shifts](https://mlsanity.com/paper/2406.08788/) (2024)
- [A Survey on GNN-based Link Prediction: Techniques, Applications, and Challenges](https://mlsanity.com/paper/2607.16198/) (2026)

## 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.