Predicting missing links in COVID-19 infection networks

Real‑world infection networks are often incomplete since contact tracing cannot capture all infection events. As a result, many infected individuals appear as isolated cases with no recorded epidemiological links. Link prediction methods can be used to reconstruct these missing links, allowing for a more complete representation of the infection network. In this study, two approaches were evaluated for predicting missing links during the first four waves of COVID-19 in Cyprus. The first approach relied on classical machine learning classifiers trained on engineered edge‑level features. For each pair of cases, node‑level epidemiological attributes, such as age, gender, infection date, NACE, and residency, were combined using various operators to form an edge feature vector. Feature selection was performed using Minimum Redundancy Maximum Relevance (mRMR) followed by greedy forward feature selection, while permutation importance was used to assess the contribution of the selected features. Random Forest and Gradient Boosting consistently achieved the strongest performance, with F1-scores ranging from approximately ~0.82 to ~0.90 and Mean Reciprocal Rank (MRR) values between 0.55 and 0.64 for the first two waves. For the third and fourth waves, F1-scores ranged from 0.68 to 0.75 and MRR values from 0.23 to 0.33. The second approach employed graph representation learning, using a GraphSAGE model. Node embeddings were generated from both the node attributes and the observed network topology, and several embedding‑combination strategies were evaluated including concatenation, absolute difference, squared difference, Hadamard product, and dot product. Link prediction with graph representation learning achieved F1-scores ranging from ~0.70 to 0.79 and MRR values from 0.23 to 0.42 across all pandemic waves. After the best classifier was validated on known cases, it was applied to unlinked nodes to infer their most likely infectors, resulting in reconstructed networks with fewer isolated components and larger connected structures. The results confirmed plausible extension of connections while maintaining epidemiologically relevant characteristics, such the outdegree. These results demonstrate that machine learning and graph representation learning can identify missing infection links, thus identifying likely sources of infection. Such tools can assist epidemiologists by providing a more complete picture of the spread of the disease, particularly during small epidemic waves, to allow for more informed and targeted interventions.