Stacking Models for Nearly Optimal Link Prediction in Complex Networks

Amir Ghasemian; Homa Hosseinmardi; Aram Galstyan; Edoardo M. Airoldi; Aaron Clauset

Source-linked AI summary

Stacking Models for Nearly Optimal Link Prediction in Complex Networks

Amir Ghasemian, Homa Hosseinmardi, Aram Galstyan, Edoardo M. Airoldi, Aaron Clauset

arXiv:1909.07578v1Sep 17, 2019stat.MLcs.LGcs.SIphysics.data-anq-bio.MN

TL;DR

The paper asks whether any link predictor is consistently best and how close existing methods are to optimality across diverse networks. It evaluates 203 predictors across 548 networks and combines them with stacking, finding optimal or nearly optimal accuracy on synthetic networks and superior performance on empirical networks, with substantial domain variation.

Problem
Systematic evidence was lacking on whether one predictor or family is consistently best, how performance varies across domains, and how close current methods are to optimality.
Method
The study evaluates 203 predictors from three families across diverse synthetic and empirical networks, then combines predictors using stacked models.
Results
Stacking achieves optimal or near-optimal accuracy on synthetic networks and more accurate predictions than individual predictors on empirical networks.
Takeaways & Limitations
No individual predictor or family is universally best, so accurate link prediction benefits from combining methods across realistic inputs.
Takeaways & Limitations
The study cannot rule out further gains from adding new predictors or families and lacks strong theoretical guarantees that stacking reaches the performance upper bound.

Abstract

from arXiv · show

Most real-world networks are incompletely observed. Algorithms that can accurately predict which links are missing can dramatically speedup the collection of network data and improve the validity of network models. Many algorithms now exist for predicting missing links, given a partially observed network, but it has remained unknown whether a single best predictor exists, how link predictability varies across methods and networks from different domains, and how close to optimality current methods are. We answer these questions by systematically evaluating 203 individual link predictor algorithms, representing three popular families of methods, applied to a large corpus of 548 structurally diverse networks from six scientific domains. We first show that individual algorithms exhibit a broad diversity of prediction errors, such that no one predictor or family is best, or worst, across all realistic inputs. We then exploit this diversity via meta-learning to construct a series of "stacked" models that combine predictors into a single algorithm. Applied to a broad range of synthetic networks, for which we may analytically calculate optimal performance, these stacked models achieve optimal or nearly optimal levels of accuracy. Applied to real-world networks, stacked models are also superior, but their accuracy varies strongly by domain, suggesting that link prediction may be fundamentally easier in social networks than in biological or technological networks. These results indicate that the state-of-the-art for link prediction comes from combining individual algorithms, which achieves nearly optimal predictions. We close with a brief discussion of limitations and opportunities for further improvement of these results.

Methods and Materials

The study compares broad families of link predictors on synthetic and empirical networks, then uses meta-learning to combine predictors. Synthetic networks vary in structural properties, while the empirical benchmark spans 548 networks across six domains.

Predictor families: The study evaluates 203 predictors spanning topological, model-based, and embedding-based approaches to missing-link prediction.The topological group includes network statistics; model-based methods use structural models; embedding-based methods use latent-space proximity.
Stacking: Meta-learning combines individual predictors by learning from query characteristics and predictor errors, but requires sufficiently diverse predictors with distinct errors.Stacked generalization can be more accurate than component predictors when their signals and mistakes differ.
Evaluation data: Synthetic networks vary in degree-distribution variability, community count, and community-boundary fuzziness, enabling evaluation across structurally different graphs.The synthetic data-generating process permits exact calculation of optimal link-prediction accuracy.
Evaluation data: The empirical benchmark contains 548 structurally diverse networks spanning social, biological, economic, technological, information, and transportation domains.The corpus spans three orders of magnitude in network size.
Evaluation assumptions: Evaluations assume edges are sampled uniformly at random, making missingness independent of observed edges and metadata; alternative missingness mechanisms remain future work.The uniform-sampling assumption provides an application-agnostic assessment but may not represent settings where missingness correlates with node or edge characteristics.

Results

Across synthetic and real-world networks, stacking diverse link predictors generally achieves optimal or nearly optimal accuracy. Performance varies by network structure and scientific domain, while a relatively small predictor subset often suffices.

Prediction Error Diversity: No individual predictor or method family is best or worst across all networks, reflecting heterogeneous errors and multiple missingness signals.Predictor importance varies across networks and domains, with different subsets accounting for most accuracy.
Synthetic Networks: Predictability ranges from chance in simple random graphs to nearly perfect in networks with many distinct communities and heavy-tailed degree distributions.Fewer communities and fuzzier boundaries reduce the upper limit of achievable prediction accuracy.
Synthetic Networks: Stacking typically achieves optimal or nearly optimal synthetic-network performance, with the best stack reducing the optimality gap to ∆AUC = 0.04 versus 0.07 for MDL (DC-SBM) and 0.23 for average nonstacked methods.Across-family stacking averages ⟨AUC⟩ = 0.83 versus 0.80 for within-family stacking.
Real-world Networks: Across domains, stacked models reach AUC = 0.98 ± 0.06 on social networks but only 0.83 ± 0.10 on biological and technological networks.Economic and information networks have marginally higher performance at AUC = 0.88 ± 0.10.
Sufficiency and Optimality: Performance rises quickly with the 10 most-important predictors, stabilizes around 30, and degrades slightly beyond 30–50, indicating mild overfitting in full models.Embedding-only stacks saturate earlier and at a lower level than other stacked models.

Discussion

The analysis finds broad, domain-dependent variation in link-prediction performance, while stacking combines predictors to achieve near-optimal accuracy. Remaining uncertainty concerns theoretical optimality, predictor coverage, and performance outside social networks.

Prediction diversity: 203 predictors show broad error diversity, with no individual predictor or family consistently best or worst across realistic networks.This supports evaluating methods across broad, structurally diverse network collections rather than narrow test cases.
Stacking performance: Stacking achieves optimal or near-optimal accuracy on synthetic networks where optimal performance is calculable.Accuracy is generally closer to perfect when networks have highly variable degree distributions or many distinct communities.
Stacking performance: On empirical networks, stacking is more accurate than any individual predictor, with little evidence that the evaluated predictor set can yield further gains.New predictors or families could still improve coverage for subsets of networks.
Domain variation: Link-prediction performance varies substantially by scientific domain, with most algorithms achieving highly accurate predictions on social networks.This may reflect either genuinely easier social-network structure or selective inference from methods developed around social data.
Future directions: Embedding-based methods generally perform more poorly than topological or model-based predictors.The paper identifies tuning embedding-based methods for link prediction as a direction for future work.
Limitations: Strong theoretical guarantees are currently unavailable, so the claim that stacking reaches the upper performance bound remains unproven.The evidence supports near-optimality across many realistic inputs, not certainty of global optimality.

1. Methods for predicting missing links

The study combines topological, model-based, embedding-based, and meta-learning methods to predict missing links. Stacking learns how predictor outputs and network context should be combined for more accurate predictions.

Topological predictors: The analysis uses 42 topological predictors, including global, pairwise, and node-based functions of network structure.Global predictors provide network-level context; pairwise predictors describe node-pair properties; node-based predictors separately characterize the two nodes.
Topological predictors: Global predictors describe network statistics such as size, observed edges, degree variation, diameter, assortativity, and clustering.Their main role is to provide context that helps supervised models generalize across unseen networks.
Topological predictors: Pairwise predictors use joint properties of candidate nodes, including common neighbors, shortest paths, PageRank, degree product, and similarity indices.These features score whether a particular unconnected pair is likely to be a missing link.
Topological predictors: Node-based predictors independently characterize the two nodes using measures such as clustering, degree, betweenness, closeness, eigenvector, Katz, PageRank, and load centrality.The study includes 20 node-based predictors.
Model-based predictors: The study evaluates 11 model-based predictors that score candidate pairs using likelihood or optimization strategies based on large-scale network structure.Likelihood methods estimate parametric connection probabilities after network decomposition; optimization methods assess community-structure objectives.
Embedding-based predictors: Embedding-based predictors project nodes into low-dimensional spaces and derive pair features from coordinates or distances.The study uses DeepWalk and VGAE embeddings, producing 144 Hadamard-product features plus six distance or similarity features.
Meta-learning and stacking: Stacked generalization treats individual predictor outputs as features and learns which predictors are most accurate for different input subsets.Cross-validation generates predictions for a second-level supervised model, while boosting approaches provide a robustness check.
Meta-learning and stacking: The study leaves investigation of other meta-learning algorithms for future work.This bounds the method comparison to stacking and two boosting approaches used in the analysis.

2. Tests on synthetic data

The study tests link predictors on synthetic networks whose degree distributions, community counts, and boundary fuzziness vary systematically, with analytically calculable optimal accuracy as a reference.

Synthetic network design: Synthetic networks vary degree-distribution variability, community count k, and community-boundary fuzziness ϵ.The degree distributions are Poisson, Weibull, or power law; k ranges from 1 to 32; and ϵ is low, medium, or high.
Synthetic network design: The networks are generated with degree-corrected stochastic block models, allowing systematic control of these structural parameters.For each parameterization, the known data-generating process and uniform missingness function permit exact calculation of a theoretical upper limit on accuracy.
Optimal accuracy: AUC is defined as the probability that a predictor scores a missing edge higher than a non-edge.This equivalence enables optimal accuracy to be calculated under the specified generative model and missingness function.
Optimal accuracy: In an Erdős-Rényi random graph, the maximum AUC is no better than chance because all edges and non-edges receive the same score.Uniformly random tie-breaking produces chance-level discrimination.
Optimal accuracy: For k = {2, 4, 8, 16, 32} in the deep detectable regime, the optimal AUC is {0.75, 0.875, 0.94, 0.97, 0.98}, respectively.These values are accurate only when ϵ is low, so the planted partition is sharp or recoverable.
Optimal accuracy: At high ϵ, stacked models appear closer to the true upper bound than the conservative calculations suggest because community recovery is not guaranteed.The discrepancy is attributed to the assumption that the planted partition is known in the calculation.

3. Empirical corpus for link prediction evaluations

The empirical evaluation uses 548 real-world networks from the CommunityFitNet corpus, spanning six scientific domains and diverse sizes and structures.

Corpus: The study selects 548 networks from the CommunityFitNet corpus, drawn from the Index of Complex Networks.The corpus contains 572 real-world networks overall.
Corpus: The selected networks span social, economic, biological, technological, information, and transportation graphs.Their proportions are 22% social, 21% economic, 34% biological, 12% technological, 4% information, and 7% transportation.

4. Evaluation of the link prediction algorithms

The evaluation uses a uniformly random missingness process and supervised training on observed non-edges, with 20% of edges held out unless otherwise specified.

Evaluation design: The missingness function samples edges uniformly at random, independently of observed edges and metadata.Each edge is observed with probability α, making this a hard test for link prediction algorithms.
Evaluation design: Supervised predictors are trained with 5-fold cross-validation using observed non-edges as negative examples.This approach treats non-links in the observed graph as negative examples for training.
Evaluation design: Because networks are sparse, mislabeled future links among training non-edges induce only an O(1/n) bias.The authors argue that improved generalizability can compensate for this small labeling error.
Evaluation design: Unless otherwise specified, α = 0.8, meaning 20% of edges are unobserved for evaluation.Other values produce qualitatively similar results.

5. Diversity in prediction error

Predictor importance is highly uneven and domain-dependent: a small subset of predictors often dominates, while different predictor types perform better in different network domains.

Importance concentration: The ensemble of learned predictor importances has a mean Gini coefficient of 0.64 ± 0.14, indicating strong skew.Lorenz curves across the 548 networks show that relatively few predictors account for much of the importance.
Importance concentration: Only 9% of all predictors account for 90% of importance in social networks, compared with 37% in biological networks.The required share varies across domains.
Domain dependence: The top predictors differ across domains, with as many as 91 of 203 predictors explaining most importance for technological networks.For biological networks, 26 of 42 topological predictors can account for the corresponding concentration.

11 model-based predictors

Model-based predictors contribute strongly to stacked link prediction, but their importance varies across networks and is complemented by topological and embedding predictors. In many networks, roughly 10 predictors suffice to achieve at least 95% of final AUC.

Predictor importance: Model-based and selected topological predictors are among the most important features across networks, while embedding predictors generally occupy middle importance ranks.Embedding predictors are rarely the worst, but no embedding predictor is dominant across a network domain.
Stacking sufficiency: Roughly 10 predictors achieve at least 95% of final AUC in a large portion of networks.The minimum feature count k* measures the number of predictors needed to reach this threshold for each stacking-method family.
Predictor importance: Predictor importance is concentrated unevenly, with a small fraction of predictors accounting for much of the learned importance in many empirical networks.Importance distributions are summarized using Lorenz curves, rank distributions, clustering, and entropy.
Synthetic-network evaluation: Synthetic-data evaluations compare individual and stacked predictors across degree distributions, community-boundary fuzziness, and numbers of communities against theoretical performance limits.These evaluations use AUC on generated networks with controlled structural variability.