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.Author summary: Understanding how infectious diseases spread requires accurate contact information. However, real-world contact tracing is often incomplete, leaving many cases without any recorded links. These missing connections limit the ability of public health teams to understand transmission patterns and to design effective interventions. This study explores how network analysis, machine learning, and graph‑based methods can help fill this gap by predicting likely infection links between infected individuals. Two approaches were evaluated. The first employed traditional machine learning models trained on the epidemiological characteristics of each pair of cases, such as age, infection date, workplace category, and geographic proximity. The second approach used graph representation learning, where a GraphSAGE neural network was trained on patterns directly from the structure of the observed infection network. Both methods were evaluated across multiple pandemic waves. The results suggest that the proposed methods are capable of identifying plausible missing links. Reconstructed networks contained fewer isolated cases and revealed possible infection pathways while maintaining epidemiologically important network characteristics, such as outdegree. These findings demonstrate that data‑driven link prediction can support public health decision‑making by providing a more complete picture of how infections spread, even when contact tracing is incomplete.