Removing noisy links benefits link prediction in complex network

Link prediction seeks to infer missing or prospective links from observed graph topology. However, real-world networks frequently contain redundant or adversarial injected links(hereafter termed noisy links). The noisy links disrupt the alignment between node embeddings and network topology in graph neural networks (GNNs), and thereby degrade prediction accuracy. To address this issue, we propose Noisy Link detection for Link Prediction (NLLP) algorithm to detect the noisy links whose removal improves the link prediction accuracy. NLLP quantifies the impact of each link on the objective of link prediction-based GNN model via loss-perturbation analysis. We provide a systematic analysis of its time and space complexity. NLLP has both theoretical rigor and computational efficiency. We empirically evaluate NLLP on different real-world datasets and the results verify the effectiveness of our algorithm.