Progresses and Challenges in Link Prediction

INTRODUCTION

• Link prediction seeks to uncover missing or future links from network topology.The review notes applications in network reconstruction [5], evolving-model evaluation [7], biological interaction inference [9], and online recommendations [11].Source: INTRODUCTION · p. 1
• The review first defines the standard problem and discusses evaluation metrics, then surveys representative achievements mostly published after.Topics include local similarity indices, link predictability, network embedding, matrix completion, and ensemble learning.Source: INTRODUCTION · p. 2
• The review also outlines limitations of existing studies and long-standing open challenges for future work.Source: INTRODUCTION · p. 2

Evaluation setup

• The standard setup treats observed links as known training information and nonobserved links as candidates, with probe links withheld from prediction.Random division is common; temporal division is usually used when predicting future links.Source: EVALUATION · p. 2

Evaluation metrics

• Threshold-independent evaluation commonly uses areas under threshold curves, while Precision and Recall are widely used threshold-dependent metrics.AUC is interpreted as the probability that a randomly chosen observed link receives a higher likelihood than a randomly chosen nonobserved link; a value near 0.5 corresponds to chance under identically distributed likelihoods.Source: EVALUATION · pp. 3–4
• A single threshold-dependent score may not reflect predictor performance, and choosing the number of predicted links or score threshold is generally difficult.Robust evaluation should vary thresholds, for example by varying L [16,19].Source: EVALUATION · p. 3
• AUC is inadequate for early retrieval, which matters in biological applications, and can overrate algorithms that rank many negatives at the bottom.The text also notes criticism that AUC may be incoherent because classifiers are evaluated under different misclassification-cost distributions [26].Source: EVALUATION · pp. 4–5
• AUPR is increasingly used, especially in biological studies, and its Precision-Recall points have explicit meaning and absolute accuracy measures can better match practical requirements.The text contrasts these features with AUC's relative-rank interpretation and notes alternatives including H measure, concentrated ROC, and normalized Discounted Cumulative Gain.Source: EVALUATION · p. 5

Metric comparison

• AUC and AUPR can rank algorithms differently: an unpublished study found differing ranks in about 1/3 of pairwise comparisons, and large-scale experiments also reported inconsistency.The review recommends reporting both metrics and judging one algorithm better for a network only when it obviously outperforms in both.Source: EVALUATION · p. 5

LOCAL SIMILARITY INDICES

• The Cannistraci-Hebb index incorporates local-community structure and Hebbian learning, including the negative impacts of external local-community links.Source: LOCAL SIMILARITY INDICES · pp. 6–7
• Empirical analyses indicate that local-community structure and Hebbian learning can considerably improve routine local similarity indices.Source: LOCAL SIMILARITY INDICES · p. 7
• Three-hop indices were reported to outperform two-hop indices on protein–protein interaction networks, world trade networks, and food webs.Source: LOCAL SIMILARITY INDICES · p. 8
• On 137 real networks, 3-hop indices outperform 2-hop indices on AUC, while 3-hop and 2-hop indices are competitive on Precision.Source: LOCAL SIMILARITY INDICES · p. 8
• CH indices perform best among the considered candidates, and 3-hop indices suit disassortative networks with lower density and clustering.Source: LOCAL SIMILARITY INDICES · p. 8
• A hybrid of 2-hop and 3-hop indices using collaborative filtering techniques can yield better overall performance.Source: LOCAL SIMILARITY INDICES · p. 8

LINK PREDICTABILITY

• The structural perturbation method applies a perturbation-based approach to missing-link prediction and is described as among the most accurate methods to date.Source: LINK PREDICTABILITY · p. 10
• Structural regularity measures predictability through a low-rank, sparse representation of a network by its ego networks.Source: LINK PREDICTABILITY · pp. 10–11
• A compression-based approach quantifies structural predictability using a network’s normalized shortest lossless-compression length.Source: LINK PREDICTABILITY · p. 11
• Structural consistency, structural regularity, and compression length are ad hoc probes of intrinsic difficulty, not mathematical formulations of prediction limits.Source: LINK PREDICTABILITY · p. 12
• Temporal-network predictability can be estimated from link-evolution sequences, but the Lempel-Ziv method can overestimate predictability and yield values near 1.Source: LINK PREDICTABILITY · p. 13
• Tang et al.’s normalized predictability compares a target temporal network with its corresponding null network to characterize topological-temporal regularity.Source: LINK PREDICTABILITY · p. 13

NETWORK EMBEDDING

• Early embedding methods could not handle large-scale networks because they relied on solving for leading eigenvectors.Source: NETWORK EMBEDDING · pp. 13–14
• Node2vec uses biased random walks to flexibly sample neighborhoods, and tuning its parameters p and q can yield better link-prediction performance than DeepWalk.Source: NETWORK EMBEDDING · pp. 14–15
• LINE learns representations that preserve both first-order proximity from observed links and second-order proximity from shared context distributions.Source: NETWORK EMBEDDING · p. 15
• Empirical studies involving more than a thousand networks found that embedding algorithms perform worse than some elaborately designed mechanistic algorithms.Source: NETWORK EMBEDDING · p. 16
• Hyperbolic-model approaches have reported stronger prediction than traditional methods for low-degree Internet nodes, while hyperbolic distance alone performs poorly when communities are present.Source: NETWORK EMBEDDING · pp. 16–17
• HYPERLINK is described as competitive with other link predictors and particularly effective for links that are difficult to predict.Source: NETWORK EMBEDDING · p. 17

MATRIX COMPLETION

• Around 10% higher AUC was reported for AUC-based loss than for routine loss functions.The objective uses known present and known absent links.Source: MATRIX COMPLETION · p. 18
• The factorization framework can be extended to directed and bipartite networks, and explicit node features can be incorporated alongside latent features [78][80].The directed case uses distinct factor matrices; the bipartite case uses separate representations for the two node sets.Source: MATRIX COMPLETION · p. 19
• The described approach combines explicit node features with latent features learned from observed topology, and defines predicted values using each node’s explicit feature vector.Source: MATRIX COMPLETION · p. 19
• Inductive matrix completion requires learning st parameters rather than Nd, and is expected to have much lower computational complexity when the number of nodes N greatly exceeds feature count s.The comparison assumes latent dimensions d and t are broadly similar.Source: MATRIX COMPLETION · p. 20
• A low-rank decomposition separates the network into a low-rank backbone and a sparse noise matrix, then ranks predicted links from zero entries in the observed adjacency matrix [85].The noise matrix represents spurious positive and missing links.Source: MATRIX COMPLETION · pp. 20–21
• The low-rank algorithm outperformed similarity-based algorithms [14][30], the hierarchical structure model, and the stochastic block model, but slightly underperformed LOOP, SPM, and Cannistraci-Hebb automata.The reported comparison is qualitative; no metric or values are supplied here.Source: MATRIX COMPLETION · p. 21

ENSEMBLE LEARNING

• Weighted Borda aggregation combines predictor rankings using weights proportional to their precision, while weighted score aggregation requires normalized scores for comparability.For Borda counts, a smaller value indicates higher estimated link existence likelihood.Source: ENSEMBLE LEARNING · p. 22
• OWA can markedly improve over individual predictors when predictors are ordered by quality, whereas ordering them by normalized values unrelated to quality does not work well [95].The later experiments report the ordering-by-quality comparison.Source: ENSEMBLE LEARNING · pp. 22–23
• Bagging decomposition was reported to reduce computational complexity without sacrificing prediction accuracy.The approaches include sampling nodes with their immediate neighbors and favoring dense components.Source: ENSEMBLE LEARNING · p. 23
• Integrating individually less plausible stochastic block models through Bayesian MCMC sampling can yield higher predictive performance than the single most plausible model.Source: ENSEMBLE LEARNING · p. 23
• AdaBoost iteratively reweights misclassified instances, and its link-prediction application requires a time-sensitive base learner plus sampled and undersampled negative instances.For sparse networks, the noise from sampling negatives is described as ignorable.Source: ENSEMBLE LEARNING · pp. 23–24
• Ghasemian et al. stacked 203 primary link predictors across 550 disparate networks, using a standard supervised random-forest learner [89]; they reported superiority to individual predictors on real networks and that the model can approach theoretical optima on synthetic networks.Source: ENSEMBLE LEARNING · p. 25

DISCUSSION

• The review classifies representative works from the last decade into five groups, and Table 1 roughly categorizes algorithms into three computational-complexity classes, including high-scalability methods applicable to large-scale networks.Other surveys [107][108] are suggested as complements.Source: DISCUSSION · p. 26, Table 1 · p. 27
• Neural link-prediction methods [110][111] show competitive preliminary performance, but their features and models remain pieced together without intrinsic connections.The authors call for in-depth, comprehensive analyses to advance these pioneering approaches.Source: DISCUSSION · p. 28
• Future work should uncover meaningful relationships between node attributes and structural roles, and investigate how topology and dynamics can inform link prediction [114].The discussion notes that even a small fraction of missing links can substantially bias dynamical-process models [114], while studies connecting topology and dynamics remain rare.Source: DISCUSSION · p. 28
• Experiments indicate that no known link predictor performs best or worst across all inputs, so algorithm research remains valuable for real networks [117].The review argues that real networks differ substantially from all possible networks, leaving room for useful predictors despite a no-free-lunch concern.Source: DISCUSSION · p. 29
• The stacking model performs worse than elaborately designed individual algorithms such as SPM and Cannistraci-Hebb automata; an individual algorithm could also be cost-effective, with competitive performance and low time complexity.Source: DISCUSSION · p. 29
• Because designing effective algorithms for general networks is increasingly hard, future studies are expected to design more algorithms for particular network types, such as directed and weighted networks and knowledge graphs [132].For recommendations, the text raises explaining recommendations to improve the acceptance rate.Source: DISCUSSION · p. 30
• Recent large-scale experiments [32][33][65][66] suggest that comparisons of few algorithms on small networks using one or two metrics can mislead, motivating systematic evaluation.The proposed analyses should span synthetic and real networks, benchmarks, state-of-the-art algorithms, and metrics; relevant results should be made publicly available, preferably with data and code.Source: DISCUSSION · pp. 30–31
• Link prediction is a fundamental, enduring problem and a tool for analyzing network evolution, privacy-protection methods, and network embeddings [7][100][135][136][137].The discussion emphasizes that its value extends beyond predicting missing or future links.Source: DISCUSSION · p. 31

• The last decade has brought plentiful and substantial achievements in link prediction.Source: DISCUSSION · p. 31
• The study of link prediction is still unfolding.Source: DISCUSSION · p. 31
• More effort is required toward a full picture of how links do.Source: DISCUSSION · p. 31