LINK PREDICTION TECHNIQUES IN SOCIAL NETWORKS: A COMPREHENSIVE REVIEW OF TRADITIONAL, MACHINE LEARNING, GRAPH NEURAL NETWORK, AND TRANSFORMER-BASED APPROACHES
Abstract
—Link prediction is a fundamental task in social network analysis that aims to identify
missing, hidden, or potential future connections between nodes by exploiting structural, topological,
and semantic information in graph data. It plays a vital role in numerous real-world applications,
including friend recommendation, community detection, personalized advertising, knowledge
graph completion, cybersecurity, fraud detection, and biological network analysis. Over the years,
link prediction techniques have evolved from traditional similarity-based methods, such as
Common Neighbors, Jaccard Coefficient, Adamic–Adar, Preferential Attachment, and Katz Index,
to machine learning-based models, graph representation learning, graph neural networks (GNNs),
and, more recently, transformer-based and foundation model approaches. This review provides a
comprehensive and critical analysis of these methodologies by examining their theoretical
foundations, benchmark datasets, evaluation metrics, computational complexity, strengths,
limitations, and practical applications. Unlike conventional surveys that primarily summarize
existing studies, this paper systematically compares traditional, machine learning, graph
embedding, GNN, and transformer-based techniques while highlighting their advantages and
research challenges. Furthermore, it presents a novel taxonomy that categorizes existing methods
and identifies emerging research directions, including dynamic and heterogeneous graph learning,
self-supervised representation learning, explainable artificial intelligence, privacy-preserving link
prediction, graph transformers, and large language model-assisted graph reasoning. This review
offers researchers and practitioners a structured understanding of the current state of the art and
provides valuable insights into developing scalable, robust, and intelligent link prediction systems
for next-generation social networks.
References
D. Liben-Nowell and J. Kleinberg, "The link-prediction problem for social networks," J. Amer. Soc.
Inf. Sci. Technol., vol. 58, no. 7, pp. 1019-1031, May 2007.
B. Perozzi, R. Al-Rfou, and S. Skiena, "DeepWalk: Online learning of social representations," in Proc.
th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining (KDD), New York, NY, USA, Aug.
, pp. 701-710.
A. Grover and J. Leskovec, "node2vec: Scalable feature learning for networks," in Proc. 22nd ACM
SIGKDD Int. Conf. Knowl. Discovery Data Mining (KDD), San Francisco, CA, USA, Aug. 2016, pp.
-864.
T. N. Kipf and M. Welling, "Variational Graph Auto-Encoders," arXiv:1611.07308, Nov. 2016.
T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks,"
in Proc. Int. Conf. Learn. Representations (ICLR), Toulon, France, Apr. 2017.
W. Hamilton, Z. Ying, and J. Leskovec, "Inductive representation learning on large graphs," in Proc.
Adv. Neural Inf. Process. Syst. (NeurIPS), Long Beach, CA, USA, Dec. 2017, pp. 1025-1035.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, "Graph attention
networks," in Proc. Int. Conf. Learn. Representations (ICLR), Vancouver, BC, Canada, Apr. 2018.
M. Zhang and Y. Chen, "Link prediction based on graph neural networks," in Proc. Adv. Neural Inf.
Process. Syst. (NeurIPS), Montréal, QC, Canada, Dec. 2018, pp. 5171-5181.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?," in Proc. Int.
Conf. Learn. Representations (ICLR), New Orleans, LA, USA, May 2019.
J. You, Y. Liu, T. Yoshida, S. Ermon, and J. Leskovec, "Graph contrastive learning with
augmentations," in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), Vancouver, BC, Canada, Dec.
C. Ying et al., "Do transformers really perform bad for graph representation?," in Proc. Adv. Neural
Inf. Process. Syst. (NeurIPS), 2021.
S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim, "Graph transformer networks," in Proc. Adv. Neural
Inf. Process. Syst. (NeurIPS), 2019.
S. Iderus, M. R. Janodi, and N. Bohari, “Measurement of extremely low-frequency emissions from
compact distribution substations in proximity to commercial areas in Sibu,” International Journal of
Digital Twin Systems and Computing, vol. 2, no. 2, pp. 1–6, 2026.
W. Jin, T. Derr, H. Liu, and J. Tang, "Self-supervised learning on graphs: Deep insights and new
direction," AI Open, vol. 2, pp. 65-88, 2021.
J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, "LINE: Large-scale information network
embedding," in Proc. 24th Int. Conf. World Wide Web (WWW), Florence, Italy, May 2015, pp. 1067
M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu, "Asymmetric transitivity preserving graph embedding,"
in Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining (KDD), San Francisco, CA,
USA, Aug. 2016, pp. 1105-1114.
R. K. Sharma, “Grid-connected PV-wind system with energy storage and electric vehicle integration,”
International Journal of Digital Twin Systems and Computing, vol. 1, no. 1, pp. 01–07, 2025..
L. Lü and T. Zhou, "Link prediction in complex networks: A survey," Physica A, vol. 390, no. 6, pp.
-1170, Mar. 2011.
Y. Rong, W. Huang, T. Xu, and J. Huang, "DropEdge: Towards deep graph convolutional networks
on node classification," in Proc. Int. Conf. Learn. Representations (ICLR), 2020.
W. Hu et al., "Strategies for pre-training graph neural networks," in Proc. Int. Conf. Learn.
Representations (ICLR), 2020.
L. Rossi, B. Chamberlain, F. Frasca, D. Eynard, F. Monti, and M. Bronstein, "Temporal graph
networks for deep learning on dynamic graphs," arXiv:2006.10637, Jun. 2020.
S. Sharma and S. Pandey, “Machine learning-driven digital twin for real-time optimization of hybrid
energy storage systems,” International Journal of Digital Twin Systems and Computing, vol. 1, no. 2,
pp. 7–12, 2025.
L. Rampášek et al., "Recipe for a general, powerful, scalable graph transformer," in Adv. Neural Inf.
Process. Syst., vol. 35, 2022.
C. Sun, G. Guo, B. Yang, and Y. Liang, "PEG: Equivariant graph neural networks with positional
encoding," in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS), 2022.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, "A comprehensive survey on graph neural
networks," IEEE Trans. Neural Netw. Learn. Syst., vol. 32, no. 1, pp. 4-24, Jan. 2021.
