PQKELP: Projected Quantum Kernel Embedding based Link Prediction in dynamic networks

In dynamic networks, where the network's topology is constantly changing, link prediction is a challenging issue. The two major challenges in link prediction within a time-varying network are accuracy and efficiency. Although random walk techniques have introduced promising embedding-based approaches, they fall short of optimization. Quantum computing, on the other hand, enhances performance in high-dimensional spaces, yet faces concerns about the limited efficiency of few qubit simulators. Addressing these issues, Projected Quantum Kernels (PQK) presents an elegant solution to achieve quantum advantage by simple quantum projection using the kernel trick, followed by a projection back to the classical state with relabeled data. In this work, we propose Projected Quantum Kernel Embedding based Link Prediction (PQKELP), a projected quantum kernel (PQK) approach on random walk embedding-based features to solve the link prediction problem. Thereby achieving a two-fold improvement by combining embedding generation and quantum projection, resulting in quantum-enhanced embedded features that enhance link prediction performance. Extensive experiments and analyses were done with a set of well-known random walk methods, i.e., Node2Vec, DeepWalk, and Walklets, also with six classical machine learning techniques and on five well-known dynamic network datasets. The results including several performance metrics like accuracy, AUC, F1-score, and precision show that our proposed model is better than traditional link prediction methods, classical machine learning approaches, and even the most cutting-edge methods available currently.