Singular value decomposition-based graph densification for link prediction in sparse graphs

Abstract Link prediction is a crucial task in complex network analysis, aiming to predict future connections between nodes in a graph. This problem is particularly challenging in sparse networks, where the low number of edges complicates traditional prediction methods. To address this, we propose singular value decomposition-graph attention network-gradient boosting (SVD-GAT-GB), a hybrid approach that densifies the sparse graph using truncated SVD, improves node representations through a GAT, and applies GB for accurate link prediction. Our method effectively handles the sparsity issue, significantly enhancing the prediction accuracy by leveraging structural information extracted from the densified graph. We validate our approach through extensive experiments on multiple datasets, demonstrating improvements in both F1-score and AUC by approximately 32% and 11%, respectively, over existing methods. The proposed model proves to be accurate and robust across diverse types of networks, making it an effective solution for link prediction in sparse graphs.