FakeEdge: Alleviate Dataset Shift in Link Prediction

Kaiwen Dong, Yijun Tian, Zhichun Guo, Yang Yang, Nitesh Chawla
Proceedings of the First Learning on Graphs Conference, PMLR 198:56:1-56:19, 2022.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v198-dong22a, title = {FakeEdge: Alleviate Dataset Shift in Link Prediction}, author = {Dong, Kaiwen and Tian, Yijun and Guo, Zhichun and Yang, Yang and Chawla, Nitesh}, booktitle = {Proceedings of the First Learning on Graphs Conference}, pages = {56:1--56:19}, year = {2022}, editor = {Rieck, Bastian and Pascanu, Razvan}, volume = {198}, series = {Proceedings of Machine Learning Research}, month = {09--12 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v198/dong22a/dong22a.pdf}, url = {https://proceedings.mlr.press/v198/dong22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T FakeEdge: Alleviate Dataset Shift in Link Prediction %A Kaiwen Dong %A Yijun Tian %A Zhichun Guo %A Yang Yang %A Nitesh Chawla %B Proceedings of the First Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2022 %E Bastian Rieck %E Razvan Pascanu %F pmlr-v198-dong22a %I PMLR %P 56:1--56:19 %U https://proceedings.mlr.press/v198/dong22a.html %V 198 %X 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.
APA
Dong, K., Tian, Y., Guo, Z., Yang, Y. & Chawla, N.. (2022). FakeEdge: Alleviate Dataset Shift in Link Prediction. Proceedings of the First Learning on Graphs Conference, in Proceedings of Machine Learning Research 198:56:1-56:19 Available from https://proceedings.mlr.press/v198/dong22a.html.

Related Material