--- author: - Amir Ghasemian - Homa Hosseinmardi - Aram Galstyan - 'Edoardo M. Airoldi' - Aaron Clauset title: Stacking Models for Nearly Optimal Link Prediction in Complex Networks --- etworks provide a powerful abstraction for representing the structure of complex social, biological, and technological systems. However, data on most real-world networks is incomplete. For instance, social connections among people may be sampled, intentionally hidden, or simply unobservable @kossinets2006effects [@fire2013computationally]; interactions among genes, or cells, or species must be observed or inferred by expensive experiments @lu2011link [@nagarajan2015predicting]; and, connections mediated by a particular technology omit all off-platform interactions @fire2013computationally [@kane2012s]. The presence of such "missing links" can, depending on the research question, dramatically alter scientific conclusions when analyzing a network's structure or modeling its dynamics. Methods that accurately predict which observed pairs of unconnected nodes should, in fact, be connected have broad utility. For instance, they can improve the accuracy of predictions of future network structure and minimize the use of scarce experimental or network measurement resources @burgess2016link [@mirshahvalad2012significant]. Moreover, the task of link prediction itself has become a standard for evaluating and comparing models of network structure @ghasemian2018evaluating [@valles2018consistencies], playing a role in networks that is similar to that of cross-validation in traditional statistical learning @arlot2010survey [@trevor2009elements]. Hence, by helping to select more accurate network models @ghasemian2018evaluating, methods for link prediction can shed light on the organizing principles of complex systems of all kinds. But, predicting missing links is a statistically hard problem. Most real-world networks are relatively sparse, and the number of unconnected pairs in an observed network—each a potential missing link—grows quadratically, like $O(n^{2})$ for a network with $n$ nodes when the number of connected pairs or edges $m$ grows linearly, like $O(n)$. The probability of correctly choosing by chance a missing link is thus only $O(1/n)$—an impractically small chance even for moderate-sized systems @clauset2008hierarchical. Despite this baseline difficulty, a plethora of link prediction methods exist @lu2011link [@martinez2017survey; @al2011survey], embodied by the three main families we study here: (i) topological methods @liben2007link [@zhou2009predicting], which utilize network measures like node degrees, the number of common neighbors, and the length of a shortest path; (ii) model-based methods @clauset2008hierarchical [@ghasemian2018evaluating], such as the stochastic block model, its variants, and other models of community structure; and (iii) embedding methods @grover2016node2vec [@cai2018comprehensive], which project a network into a latent space and predict links based on the induced proximity of its nodes. A striking feature of this array of methods is that all appear to work relatively well @liben2007link [@ghasemian2018evaluating; @grover2016node2vec]. However, systematic comparisons are lacking, particularly of methods drawn from different families, and most empirical evaluations are based on relatively small numbers of networks. As a result, the general accuracy of different methods remains unclear, and we do not know whether different methods, or families, are capturing the same underlying signatures of "missingness." For instance, is there a single best method or family for all circumstances? If not, then how does missing link predictability vary across methods and scientific domains, e.g., in social versus biological networks, or across network scales? And, how close to optimality are current methods? Here, we answer these questions using a large corpus of 548 structurally and scientifically diverse real-world networks and 203 missing link predictors drawn from three large methodological families. First, we show that individual methods exploit different underlying signals of missingness, and, affirming the practical relevance of the No Free Lunch theorem @wolpert:macready:1997 [@peel2017ground], no method performs best or worst on all realistic inputs. We then show that a meta-learning approach @schapire1990strength [@breiman1996bagging; @srivastava2014dropout] can exploit this diversity of errors by "stacking" individual methods into a single algorithm @wolpert1992stacked, which we argue makes nearly optimal predictions of missing links. We support this claim with three lines of evidence: (i) evaluations on synthetic data with known structure and optimal performance, (ii) tests using real-world networks across scientific domains and network scales, and (iii) tests of sufficiency and saturation using subsets of methods. Across these tests, model stacking is nearly always the best method on held-out links, and nearly-optimal performance can be constructed using model-based methods, topological methods, or a mixture of the two. Furthermore, we find that missing links are generally easiest to predict in social networks, where most methods perform well, and hardest in biological and technological networks. We conclude by discussing limitations and opportunities for further improvement of these results. Methods and Materials {#methods-and-materials .unnumbered} ===================== As a general setting, we imagine an unobserved simple network $G$ with a set of $E$ pairwise connections among a set of $V$ nodes, with sizes $m$ and $n$, respectively. Of these, a subset $E'\subset E$ of connections is observed, chosen by some function $f$. Our task is to accurately guess, based only on the pattern of observed edges $E'$, which unconnected pairs $X=V\times V - E'$ are in fact among the missing links $Y=E - E'$. A link prediction method defines a *score* function over these unconnected pairs $i,j\in X$ so that better-scoring pairs are more likely to be missing links @liben2007link. In a supervised setting, the particular function that combines input predictors to produce a score is learned from the data.We evaluate the accuracy of such predictions using the standard AUC statistic, which provides a context-agnostic measure of a method's ability to distinguish a missing link $i,j\in Y$ (a true positive) from a non-edge $X-Y$ (a true negative) @clauset2008hierarchical. Other accuracy measures may provide insight about a predictor's performance in specific settings, e.g., precision and recall at certain thresholds. We leave their investigation for future work. The most common approach to predict missing links constructs a score function from network statistics of each unconnected node pair @liben2007link. We study 42 of these topological predictors, which include predictions based on node degrees, common neighbors, random walks, node and edge centralities, among others (see SI Appendix, Table \[table:top\_feat\]). Models of large-scale network structure are also commonly used for link prediction. We study 11 of these model-based methods @ghasemian2018evaluating, which either estimate a parametric probability $\Pr(i\to j\,|\,\theta)$ that a node pair is connected @clauset2008hierarchical, given a decomposition of a network into communities, or predict a link as missing if it would improve a measure of community structure @liben2007link (see SI Appendix, Table \[table:abbr\]). Close proximity of an unconnected pair, after embedding a network's nodes into a latent space, is a third common approach to link prediction. We study 150 of these embedding-based predictors, derived from two popular graph embedding algorithms and six notions of distance or similarity in the latent space. In total, we consider 203 features of node pairs, some of which are the output of existing link prediction algorithms, while others are numerical features derived from the network structure. For our purposes, each is considered a missing link "predictor." A lengthier description of these 203 methods, and the three methodological families they represent, is given in SI Appendix, section A. Meta-learning techniques are a powerful class of machine learning algorithms that can learn from data how to combine individual predictors into a single, more accurate algorithm @breiman1996bagging [@schapire1999brief]. Stacked generalization @wolpert1992stacked combines predictors by learning a supervised model of input query characteristics and the errors that individual predictors make. In this way, model "stacking" treats a set of predictors as a panel of experts, and learns the kinds of questions each is most expert at answering correctly. Stacked models can thus be strictly more accurate than their component predictors @wolpert1992stacked, making them attractive for hard problems like link prediction @koren2009bellkor, but only if those predictors make distinct errors and are sufficiently diverse in the signals they exploit. We evaluate individual prediction methods, and their stacked generalizations, using two types of network data. The first is a set of synthetic networks with known structure that varies along three dimensions: (i) the degree distribution's variability, being low (Poisson), medium (Weibull), or high (power law); (ii) the number of "communities" or modules $k\in\{1,2,4,16,32\}$; and (iii) the fuzziness of the corresponding community boundaries $\epsilon$, being low, medium, or high. These synthetic networks thus range from homogeneous to heterogeneous random graphs, from no modules to many modules, and from weakly to strongly modular structure (see SI Appendix, section B and Table \[tab:par\_set\]). Moreover, because the data generating process for these networks is known, we exactly calculate the optimal accuracy that any link prediction method could achieve, as a reference point (see SI Appendix, section B). The second is a large corpus of 548 real-world networks. This structurally diverse corpus includes social (23%), biological (33%), economic (22%), technological (12%), information (3%), and transportation (7%) networks @ghasemian2018evaluating, and spans three orders of magnitude in size (see SI Appendix, section C and Fig. \[fig:AD\]). It is by far the largest and most diverse empirical benchmark of link prediction methods to date, and enables an assessment of how methods perform across scientific domains. Finally, our evaluations assume a missingness function $f$ that samples edges uniformly at random from $E$ so that each edge $(i,j)\in E$ is observed with probability $\alpha$. This choice presents a hard test, as $f$ is independent of both observed edges and metadata. Other models of $f$, e.g., in which missingness correlates with edge or node characteristics, may better capture particular scientific settings and are left for future work. Our results thus provide a general, application-agnostic assessment of link predictability and method performance. In cases of supervised learning, we train a method using 5-fold cross validation by choosing as positive examples a subset of edges $E'' \subset E'$ according to the same missingness model $f$, along with all observed non-edges $V\times V - E'$ as negative examples (see SI Appendix, section D). Unless other specified, results reflect a choice of $\alpha=0.8$, i.e., 20% of edges are unobserved (holdout set); other values produce qualitatively similar results. Results {#sec:R .unnumbered} ======= \[t!\] <span>cc</span> ![image](importance_vf.pdf){width="100.00000%"} Prediction Error Diversity {#prediction-error-diversity .unnumbered} -------------------------- If all link predictors exploit a common underlying signal of missingness, then one or a few predictors will consistently perform best across realistic inputs. Optimal link prediction could then be obtained by further leveraging this universal signal. In contrast, if different predictors exploit distinct signals, they will exhibit a diversity of errors in the form of heterogenous performance across inputs, In this case, there will be no best or worst method overall, and optimal link predictions can only be obtained by combining multiple methods. This dichotomy also holds at the level of predictor families, one of which could be best overall, e.g., topological methods, even if no one family member is best. To distinguish these possibilities, we characterize the empirical distribution of errors by training a random forest classifier over the 203 link predictors applied to each of the 548 real-world networks and separately to all networks in each of the six scientific domains within our corpus (see SI Appendix section E). In this setting, the character of a predictor's errors is captured by its learned Gini importance (mean decrease in impurity) @trevor2009elements within the random forest: the higher the Gini importance, the more generally useful the predictor is for correctly identifying missing links on that network or that domain. If all methods exploit a common missingness signal (one method to rule them all), the same few predictors or predictor family will be assigned consistently greater importance across networks and domains. However, if there are multiple distinct signals (a diversity of errors), the learned importances will be highly heterogeneous across inputs, and no predictor or family will be best. Across networks and domains, we find wide variation in both individual and family-wise predictor importances, such that no individual method and no family of methods is best, or worst, on all networks. On individual networks, predictor importances tend to be highly skewed, such that a relatively small subset of predictors account for the majority of prediction accuracy (SI Appendix, Table \[tab:FIE\] and Fig. \[fig:LCF\]). However, the precise composition of this subset varies widely across both networks and families (SI Appendix, Tables \[tab:FIE\]–\[tab:FWE\], and Figs. \[fig:HFR\]–\[fig:CFB\]), implying a broad diversity of errors and multiple distinct signals of missingness. At the same time, not all predictors perform well on realistic inputs, e.g., a subset of topological methods generally receive low importances, and most embedding-based predictors are typically mediocre. Nevertheless, each family contains some members that are ranked among the most important predictors for many, but not all, networks. Across domains, predictor importances cluster in interesting ways, such that some individual and some families of predictors perform better on specific domains. For instance, examining the 10 most-important predictors by domain (29 unique predictors; Fig. \[fig:FID\]), we find that topological methods, such as those based on common neighbors or localized random walks, perform well on social networks but less well on networks from other domains. In contrast, model-based methods perform relatively well across domains, but often perform less well on social networks than do topological measures and some embedding-based methods. Together, these results indicate that predictor methods exhibit a broad diversity of errors, which tend correlate somewhat with scientific domain. This performance heterogeneity highlights the practical relevance to link prediction of the general No Free Lunch theorem @wolpert:macready:1997, which proves that across all possible inputs, every machine learning method has the same average performance, and hence accuracy must be assessed on a per dataset basis. The observed diversity of errors indicates that none of the 203 individual predictors is a universally-best method for the subset of all inputs that are realistic. However, that diversity also implies that a nearly-optimal link prediction method for realistic inputs could be constructed by combining individual methods so that the best individual method is applied for each given input. Such a meta-learning algorithm cannot circumvent the No Free Lunch theorem, but it can achieve optimal performance on realistic inputs by effectively redistributing its worse-than-average performance onto unrealistic inputs, which are unlikely to be encountered in practice. In the following sections, we develop and investigate the near-optimal performance of such an algorithm. \[t!\] <span>cc</span> ![image](all_aucs_randomforest_total_Jun19.pdf){width="100.00000%"} Stacking on Networks with Known Structure {#stacking-on-networks-with-known-structure .unnumbered} ----------------------------------------- Model "stacking" is a meta-learning approach that learns to apply the best individual predictor according to the input's characteristics @wolpert1992stacked. Here, we assess the accuracy of model stacking both within and across families of prediction methods, which adds seven more prediction algorithms to our evaluation set. Because the optimality of an algorithm's predictions can only be assessed when the underlying data generating process is known, we first characterize the accuracy of model stacking using synthetic networks with known structure, for which we calculate an exact upper bound on link prediction accuracy (see SI Appendix, section B). To provide a broad range of realistic variation in these tests, we use a structured random graph model, in which we systematically vary its degree distribution's variance, the number of communities $k$, and the fuzziness of those community boundaries ${\epsilon}$. Across these structural variables, the upper limit on link predictability varies considerably (Fig. \[fig:exp\_PL\_LN\]A), from no better than chance in a simple random graph ($k=1$; Poisson) to nearly perfect in networks with many distinct communities and a power-law degree distribution. Predictability is generally lower (no methods can do well) with fewer communities (low $k$) or with more fuzzy boundaries (high ${\epsilon}$), but higher with increasing variance in the degree distribution (Weibull or power law). Most methods, whether stacked or not, perform relatively well when predictability is low. However, as potential predictability increases, methods exhibit considerable dispersion in their accuracy, particularly among topological and embedding-based methods. Regardless of the synthetic network's structure, however, we find that stacking methods are typically among the most accurate prediction algorithms, and they often achieve optimal or nearly-optimal prediction accuracy (Fig. \[fig:exp\_PL\_LN\]A). For instance, the best model stacking method exhibits a substantially smaller gap between practical and optimal performance (all topol., model & embed., $\Delta\textrm{AUC}=0.04$; SI Appendix, Table \[tab:gap\]) than the best individual predictor (MDL (DC-SBM), $\Delta\textrm{AUC}=0.07$; SI Appendix, Table \[tab:best\_10\_AUCgap\]), and is far better than the average non-stacked topological and model-based methods ($\langle \Delta\textrm{AUC}\rangle=0.23$; SI Appendix, Table \[tab:gap\]). Moreover, in all structural settings, stacking across families tends to produce slightly more accurate predictions ($\langle\textrm{AUC}\rangle = 0.83$; SI Appendix, Table \[tab:AUC\_synt\]) than stacking within families ($\langle\textrm{AUC}\rangle = 0.80$), and only one stacked model (all embed.) is less accurate than the best individual predictor (marginally, with $\Delta\textrm{AUC}=0.01$, and Table \[tab:AUC\_synt\]). Stacking on Real-world Networks {#stacking-on-real-world-networks .unnumbered} ------------------------------- To characterize the real-world accuracy of model stacking, we apply these methods, along with the individual predictors, to our corpus of 548 structurally diverse real-world networks. We analyze the results both within and across scientific domains, and as a function of network size. Both across all networks, and within individual domains, model stacking methods produce the most accurate predictions of missing links (Fig. \[fig:exp\_PL\_LN\]B and Table \[tab:satexp\]), and some individual predictors perform relatively well, particularly model-based ones. Applied to all networks, the best model-stacking method achieves slightly better average performance (all topol. & model, $\langle\textrm{AUC}\rangle = 0.87\pm0.10$) than the best individual method (MDL (DC-SBM), $\langle\textrm{AUC}\rangle = 0.84\pm0.10$), and far better performance than the average individual topological or model-based predictor ($\langle\textrm{AUC}\rangle = 0.63$; and see Tables \[tab:satexp\] and \[tab:APR\_indiv\_real\]). However, model stacking also achieves substantially better precision in its predictions (Table \[tab:satexp\]), which can be a desirable property in practice. We note that these stacking results were obtained by optimizing the standard F measure to choose the random forest's parameters. Alternatively, we may optimize the AUC itself, which produces similar results, but with slightly lower precisions in exchange for slightly higher AUC scores (see Table \[tab:rf\_AUC\]). algorithm AUC precision recall ---------------------------- -------------------- --------------------- ------------------- Q $ 0.7\pm0.14$ $ 0.14 \pm0.17$ $ 0.67\pm0.15$ Q-MR $0.67\pm 0.15$ $0.12\pm 0.17$ $0.63\pm0.13$ Q-MP $0.64\pm 0.15$ $0.09\pm 0.11$ $0.59\pm 0.17$ B-NR (SBM) $0.81\pm 0.13$ $0.13\pm0.12$ $0.65\pm0.22$ B-NR (DC-SBM) $ 0.7\pm0.2$ $0.12\pm0.12$ $0.61\pm0.24$ cICL-HKK $ 0.79\pm0.13$ $0.14\pm0.14$ $ 0.58\pm 0.25$ B-HKK $0.77\pm0.13$ $0.11\pm 0.1$ $ 0.51\pm0.26$ Infomap $0.73\pm0.14$ $ 0.12\pm0.12$ $0.68\pm0.13$ MDL (SBM) $ 0.79\pm 0.15$ $0.14\pm0.13$ $0.57\pm 0.3$ MDL (DC-SBM) $ 0.84\pm 0.1$ $0.13\pm0.11$ $0.78\pm0.12$ S-NB $ 0.71\pm0.19$ $ 0.12\pm0.13$ $0.66\pm0. 17$ mean model-based $ 0.74 \pm 0.16 $ $ 0.12 \pm 0.13 $ $ 0.63 \pm 0.21 $ mean indiv. topol. $ 0.6 \pm 0.13 $ $ 0.09 \pm 0.16 $ $ 0.53 \pm 0.35 $ mean indiv. topol. & model $ 0.63 \pm 0.15 $ $ 0.09 \pm 0.16 $ $ 0.55 \pm 0.33 $ emb-DW $0.63\pm0.23$ $0. 17\pm0.19$ $0.42\pm0. 35$ emb-vgae $0.69\pm 0.19$ $0.05\pm 0.05$ $0.69\pm0.21$ all topol. $0.86\pm0. 11$ $0.42\pm0.33$ $0.44\pm0.32$ all model-based $0.83\pm0.12$ $0.39\pm0.34$ $0.3\pm0.29$ all embed. $0. 77\pm 0.16$ $0. 32\pm0. 32$ $0.32\pm0.31$ all topol. & model $0.87\pm0.1$ $0.48\pm0.36$ $0.35\pm0.35$ all topol. & embed. $0. 84\pm0. 13$ $0. 4\pm0. 34$ $0.39\pm0.3 3$ all model & embed. $0.84\pm0.13$ $0.36\pm0.32$ $0.36\pm0.31$ all topol., model & embed. $0.85\pm0. 14$ $0.42\pm0.34$ $0.39\pm0.33$ : Link prediction performance (mean$\pm$std. err.), measured by AUC, precision, and recall, for link prediction algorithms applied to the 548 structurally diverse networks in our corpus. \[tab:satexp\] Among the stacked models, the highest accuracy on real-world networks is achieved by stacking model-based and topological predictor families. Adding embedding-based predictors does not significantly improve accuracy, suggesting that the network embeddings do not capture more structural information than is represented by the model-based and topological families. This behavior aligns with our results on synthetic networks above, where the performances of stacking all predictors and stacking only model-based and topological predictors were nearly identical (SI Appendix, Tables \[tab:gap\] and \[tab:best\_10\_AUCgap\]). Applied to individual scientific domains, we find considerable variation in missing link predictability, which we take to be approximated by the most-accurate stacked model (Fig. \[fig:exp\_PL\_LN\]B). In particular, most predictors, both stacked and individual (SI Appendix, Figs. \[tab:gap\] and \[tab:best\_10\_AUCgap\]), perform well on social networks, and on these networks, model stacking achieves nearly perfect link prediction (up to $\textrm{AUC}=0.98\pm0.06$; Table \[tab:AUC\_soc\_dom\]). In contrast, this upper limit is substantially lower in non-social domains, being lowest for biological and technological networks ($\textrm{AUC}=0.83\pm0.10$; Tables \[tab:AUC\_bio\_dom\] and \[tab:AUC\_tech\_dom\]), while marginally higher for economic and information networks ($\textrm{AUC}=0.88\pm0.10$; SI Appendix, Tables \[tab:AUC\_eco\_dom\] and \[tab:AUC\_info\_dom\]). ![Mean link prediction performance (AUC) as a function of network size (number of edges $m$) for stacked models and select individual predictors, applied to 548 real-world networks. Generally, stacking topological predictors, model-based predictors, or both yields superior performance, but especially on larger networks where link prediction is inherently more difficult.<span data-label="fig:aveAUC_vs_size"></span>](auc_netSize_randomforest_Jun19_vr.pdf "fig:"){width="0.98\columnwidth"} \[fig:aveAUC\_vs\_size\_real\] Stacked models also exhibit superior performance on link prediction across real-world networks of different scales (number of edges $m$; Fig. \[fig:aveAUC\_vs\_size\]), and generally exhibit more accurate predictions as network size increases, where link prediction is inherently harder. We note, however, that on small networks ($m<200$), an alternative algorithm based on a simple majority-vote among model-based predictors slightly outperforms all stacking methods, but performs substantially worse than the best stacked model on larger networks ($m>1000$). And, embedding-based methods perform poorly at most scales, suggesting a tendency to overfit, although stacking within that family produces higher accuracies on larger networks, but still lower than other stacked models. Sufficiency and Optimality {#sufficiency-and-optimality .unnumbered} -------------------------- In practice, the optimality of a meta-learning method can only be established indirectly, over a set of considered predictors applied to a sufficiently diverse range of empirical tests cases @wolpert:macready:1997. We assess this indirect evidence for stacked link-prediction models through two numerical experiments. In the first, we consider how performance varies as a function of the number of predictors stacked, either within or across families. Evidence for optimality here appears as an early saturation, in which performance achieves its maximum prior to the inclusion of all available individual predictors. This behavior would indicate that a subset of predictors is sufficient to capture the same information as the total set. To test for this early-saturation signature, we first train a random forest classifier on all predictors in each of our stacked models and calculate each predictor's within-model Gini importance. For each stacked model, we then build a new sequence of sub-models in which we stack only the $k$ most important predictors at a time and assess its performance on the test corpus. ![Mean link prediction performance (AUC) as a function of the number of stacked features, for within- and across-family stacked models, applied to 548 real-world networks. The shaded regions show the standard error, and the early saturation behavior (at between 10 and 50 predictors) indicates that a small subset of predictors is sufficient to capture the same information as the total set.<span data-label="fig:AUC_saturation"></span>](auc_vc_nFeatures_randomforest_fmeasureModelSelectionlog6_Jun19.pdf){width="0.98\columnwidth"} In each of the stacked models, performance exhibits a classic saturation pattern: it increases quickly as the 10 most-important predictors are included, and then stabilizes by around 30 predictors (Fig. \[fig:AUC\_saturation\] and SI Appendix, Fig. \[fig:DKstar\]). Performance then degrades slightly beyond 30–50 included predictors, suggesting a slight degree of overfitting in the full models. Notably, each within and across family model exhibits a similar saturation curve, except for the embedding-only model, which saturates early and at a lower level than other stacked models. This similar behavior suggests that these families of predictors are capturing similar missingness signals, despite their different underlying representations of the network structure. As in other experiments, the best saturation behavior is achieved by stacking model-based and topological predictors. In the second, we evaluate whether individual predictors represent "weak" learners in the sense that their link-prediction performance is better than random. In general, we find that nearly all of the predictors satisfy this condition (SI Appendix, Figs. \[fig:HWL\_me\] and \[fig:HWL\_top\]), implying that they can be combined according to the Adaboost theorem to construct an optimal algorithm @freund:schapire:1997. Replacing the random forest algorithm within our stacking approach with a standard boosting algorithm also produces nearly identical performance on our test corpus (see Tables \[tab:xgb\_f\]–\[tab:ada\_AUC\]). The similar performance between the two methods suggests that relatively little additional performance is likely possible using other meta-learning approaches over the same set of predictors. Discussion {#discussion .unnumbered} ========== Developing more accurate methods for predicting missing links in networks would help reduce the use of scarce resources in collecting network data, and would provide more powerful tools for evaluating and comparing network models of complex systems. The literature on such methods gives an unmistakable impression that most published algorithms produce reasonably accurate predictions. However, relatively few of these studies present systematic comparisons across different families of methods and they typically draw their test cases from a narrow set of empirical networks, e.g., social networks. As a result, it has remained unknown whether a single best predictor or family of predictors exists, how link predictability itself varies across different methods and scientific domains, or how close to optimality current methods may be. Our broad analysis of individual link prediction algorithms, representing three large and popular families of such methods, applied to a large corpus of structurally diverse networks, shows definitively that common predictors in fact exhibit a broad diversity of errors across realistic inputs (Fig. \[fig:FID\] and SI Appendix, Fig. \[fig:LCF\]). Moreover, this diversity is such that no one predictor, and no family of predictors is overall best, or worst, in practice (SI Appendix, Table \[tab:FIE\] and Fig. \[fig:HFR\]). The common practice of evaluating link prediction algorithms using a relatively narrow range of test cases is thus problematic. The far broader range of empirical networks and algorithms considered here shows that, generally speaking, good performance on a few test cases does not generalize across inputs. The diversity of errors we find serves to highlight the practical relevance of the No Free Lunch theorem @wolpert:macready:1997 for predicting missing links in complex networks, and suggests that optimal performance on realistic inputs may only be achieved by combining methods, e.g., via meta-learning, to construct an ensemble whose domain of best performance matches the particular structural diversity of real-world networks. Model stacking is a popular meta-learning approach, and our results indicate that it can produce highly accurate predictions of missing links by combining either topological predictors alone, model-based predictors alone, or both. Applied to structurally diverse synthetic networks, for which we may calculate optimal performance, stacking achieves optimal or near-optimal accuracy, and accuracy is generally closer to perfect when networks exhibit a highly variable degree distribution and/or many, structurally distinct communities (Fig. \[fig:exp\_PL\_LN\]A). Similarly, applied to empirical networks, stacking produces more accurate predictions than any individual predictor (Fig. \[fig:exp\_PL\_LN\]B and Table \[tab:satexp\]), and these predictions appear to be nearly optimal, i.e., we find little evidence that further accuracy can be achieved using this set of predictors (Fig. \[fig:AUC\_saturation\]), even under alternative meta-learning approaches. Of course, we cannot rule out the possibility that more accurate predictions overall could be obtained by incorporating, within the stacked models, specific new predictors or new families, if they provide better prediction coverage of some subset of input networks than do the currently considered predictors. Given the diverse set of predictors and families considered here, this possibility seems unlikely without fundamentally new ideas about how to represent the structure of networks, and therefore also signals of missingness. Across networks drawn from different scientific domains, e.g., social vs. biological networks, we find substantial variation in link predictor performance, both for individual predictors and for stacked models. This heterogeneity suggests that the basic task of link prediction may be fundamentally harder in some domains of networks than others. Most algorithms produce highly accurate predictions in social networks, which are stereotypically rich in triangles (local clustering), exhibit broad degree distributions, and are composed of assortative communities, suggesting that link prediction in social networks may simply be easier @epasto2019single than in non-social network settings. In fact, stacked models achieve nearly perfect accuracy at distinguishing true positives (missing links) from true negatives (non-edges) in social networks (Fig. \[fig:exp\_PL\_LN\]B and SI Appendix, Table \[tab:AUC\_soc\_dom\]). An alternative interpretation of this difference is that the existing families of predictors exhibit some degree of selective inference, i.e., they work well on social networks because social network data is the most common inspiration and application for link prediction methods. Our results make it clear that developing more accurate individual predictors for non-social networks, e.g., biological and informational networks, is an important direction of future work. Progress along these lines will help clarify whether link prediction is fundamentally harder in non-social domains, and why. Across our analyses, embedding-based methods, which are instances of representation learning on networks, generally perform more poorly than do either topological or model-based predictors. This behavior is similar to recent results in statistical forecasting, which found that neural network and other machine learning methods perform less well by themselves than when combined with other, conventional statistical methods @makridakis2018m4 [@makridakis2018statistical]. A useful direction of future work on link prediction would specifically investigate tuning embedding-based methods to perform better on the task of link prediction. Only strong theoretical guarantees, which currently seem out of reach, would allow us to say for certain whether the stacked models presented here actually achieve the upper bound on link prediction performance in complex networks. However, the evidence suggests that stacking achieves nearly optimal performance across a wide variety of realistic inputs. It is likely that efforts to develop new individual link prediction algorithms will continue, and these efforts will be especially beneficial in specific application domains, e.g., predicting missing links in genetic regulatory networks or in food webs. Evaluations of new predictors, however, should be carried out in the context of meta-learning, in order to assess whether they improve the overall prediction coverage embodied by the state-of-the-art stacked models applied to realistic inputs. Similarly, these evaluations should be conducted on a large and structurally diverse corpus of empirical networks, like the one considered here. More narrow evaluations are unlikely to produce reliable estimates of predictor generalization. Fortunately, stacked models can easily be extended to incorporate any new predictors, as they are developed, providing an incremental path toward fully optimal predictions. <span>10</span> Kossinets G (2006) Effects of missing data in social networks. 28(3):247–268. Fire M, et al. (2013) Computationally efficient link prediction in a variety of social networks. 5(1):10. L<span>ü</span> L, Zhou T (2011) Link prediction in complex networks: A survey. 390(6):1150–1170. Nagarajan M, et al. (2015) Predicting future scientific discoveries based on a networked analysis of the past literature in <span>*Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*</span>. (ACM), pp. 2019–2028. Kane GC, Alavi M, Labianca GJ, Borgatti S (2014) What's different about social media networks? a framework and research agenda. 38(1):274–304. Burgess M, Adar E, Cafarella M (2016) Link-prediction enhanced consensus clustering for complex networks. 11(5):e0153384. Mirshahvalad A, Lindholm J, Derlen M, Rosvall M (2012) Significant communities in large sparse networks. 7(3):e33721. Ghasemian A, Hosseinmardi H, Clauset A (2019) Evaluating overfit and underfit in models of network community structure. . Vall<span>è</span>s-Catal<span>à</span> T, Peixoto TP, Sales-Pardo M, Guimer<span>à</span> R (2018) Consistencies and inconsistencies between model selection and link prediction in networks. 97(6):062316. Arlot S, Celisse A, , et al. (2010) A survey of cross-validation procedures for model selection. 4:40–79. Hastie T, Tibshirani R, Friedman J (2009) <span>*The elements of statistical learning: data mining, inference, and prediction*</span>. (New York, NY: Springer). Clauset A, Moore C, Newman MEJ (2008) Hierarchical structure and the prediction of missing links in networks. 453(7191):98. Mart<span>í</span>nez V, Berzal F, Cubero JC (2017) A survey of link prediction in complex networks. 49(4):69. Al Hasan M, Zaki MJ (2011) A survey of link prediction in social networks in <span>*Social Network Data Analytics*</span>. (Springer), pp. 243–275. Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. 58(7):1019–1031. Zhou T, L<span>ü</span> L, Zhang YC (2009) Predicting missing links via local information. 71(4):623–630. Grover A, Leskovec J (2016) node2vec: Scalable feature learning for networks in <span>*Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*</span>. (ACM), pp. 855–864. Cai H, Zheng VW, Chang KCC (2018) A comprehensive survey of graph embedding: Problems, techniques, and applications. 30(9):1616–1637. Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. 1(1):67–82. Peel L, Larremore DB, Clauset A (2017) The ground truth about metadata and community detection in networks. 3(5):e1602548. Schapire RE (1990) The strength of weak learnability. 5(2):197–227. Breiman L (1996) Bagging predictors. 24(2):123–140. Srivastava N, Hinton G, Krizhevsky A, Sutskever I, Salakhutdinov R (2014) Dropout: a simple way to prevent neural networks from overfitting. 15(1):1929–1958. Wolpert DH (1992) Stacked generalization. 5(2):241–259. Schapire RE (1999) A brief introduction to boosting in <span>*Proceedings of the 16th International Joint Conference on Artificial intelligence, Volume 2*</span>. (Morgan Kaufmann Publishers Inc.), pp. 1401–1406. Koren Y (2009) The <span>BellKor</span> solution to the <span>Netflix Grand Prize</span>. pp. 1–10. Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. 55:119–139. Epasto A, Perozzi B (2019) Is a single embedding enough? <span>Learning</span> node representations that capture multiple social contexts in <span>*The World Wide Web Conference*</span>. (ACM), pp. 394–404. Makridakis S, Spiliotis E, Assimakopoulos V (2018) The <span>M4</span> competition: <span>Results</span>, findings, conclusion and way forward. 34(4):802–808. Makridakis S, Spiliotis E, Assimakopoulos V (2018) Statistical and machine learning forecasting methods: Concerns and ways forward. 13(3):e0194889. Newman M (2019) <span>*Networks*</span>. (Oxford University Press). Cukierski W, Hamner B, Yang B (2011) Graph-based features for supervised link prediction in <span>*Neural Networks (IJCNN), The 2011 International Joint Conference on*</span>. (IEEE), pp. 1237–1244. Hagberg A, Swart P, S Chult D (2008) Exploring network structure, dynamics, and function using networkx, (Los Alamos National Lab.(LANL), Los Alamos, NM (United States)), Technical report. Leicht EA, Holme P, Newman MEJ (2006) Vertex similarity in networks. 73(2):026120. Newman MEJ, Girvan M (2004) Finding and evaluating community structure in networks. 69(2):026113. Newman MEJ (2016) Community detection in networks: Modularity optimization and maximum likelihood are equivalent. . Zhang P, Moore C (2014) Scalable detection of statistically significant communities and hierarchies, using message passing for modularity. 111(51):18144–18149. Newman MEJ, Reinert G (2016) Estimating the number of communities in a network. 117(7):078301. Hayashi K, Konishi T, Kawamoto T (2016) A tractable fully <span>Bayesian</span> method for the stochastic block model. . Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. 105(4):1118–1123. Peixoto TP (2013) Parsimonious module inference in large networks. 110(14):148701. Krzakala F, et al. (2013) Spectral <span>R</span>edemption in <span>C</span>lustering <span>S</span>parse <span>N</span>etworks. 110(52):(715)984-7259. Perozzi B, Al-Rfou R, Skiena S (2014) Deepwalk: Online learning of social representations in <span>*Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*</span>. (ACM), pp. 701–710. Kipf TN, Welling M (2016) Variational graph auto-encoders. . Hamilton WL, Ying R, Leskovec J (2017) Representation learning on graphs: Methods and applications. . Dietterich T (2000) Ensemble methods in machine learning. pp. 1–15. Sewell M (2008) Ensemble learning. 11(02). Chen T, Guestrin C (2016) Xgboost: A scalable tree boosting system in <span> *Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*</span>. pp. 785–794. Freund Y, Schapire RE (1997) A decision-theoretic generalization of on-line learning and an application to boosting. 55(1):119–139. Karrer B, Newman MEJ (2011) Stochastic blockmodels and community structure in networks. 83(1):016107. Decelle A, Krzakala F, Moore C, Zdeborov<span>á</span> L (2011) Asymptotic <span>A</span>nalysis of the <span>S</span>tochastic <span>B</span>lock <span>M</span>odel for <span>M</span>odular <span>N</span>etworks and <span>I</span>ts <span>A</span>lgorithmic <span>A</span>pplications. 84(6):066106. Clauset A, Tucker E, Sainz M (2016) <span>The Colorado Index of Complex Networks</span>. (<https://icon.colorado.edu/>). Al Hasan M, Chaoji V, Salem S, Zaki M (2006) Link prediction using supervised learning in <span>*SDM06: workshop on link analysis, counter-terrorism and security*</span>. Ahmed C, ElKorany A, Bahgat R (2016) A supervised learning approach to link prediction in twitter. 6(1):24. Lichtenwalter RN, Lussier JT, Chawla NV (2010) New perspectives and methods in link prediction in <span>*Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining*</span>. (ACM), pp. 243–252. Cover TM, Thomas JA (2012) <span>*Elements of information theory*</span>. (John Wiley & Sons). Supporting Information {#supporting-information .unnumbered} ====================== Methods for predicting missing links {#sec:A} ==================================== Here, we describe in detail the three families of link predictors and their specific members used in the analysis, including the abbreviations used in the main text. In addition, we describe in more detail the setup of the supervised stacked generalization algorithm we use to combine individual predictors into a single algorithm. Topological predictors {#topological-predictors .unnumbered} ---------------------- Topological predictors are simple functions of the observed network topology, e.g., counts of edges, measures of overlapping sets of neighbors, and measures derived from simple summarizations of the network's structure. We consider 42 topological predictors, which come in three types: global, pairwise, and node-based. Within these groups, the "pairwise" predictors include a number of topological features that are often used in the literature to directly predict missing links @liben2007link, e.g., the number of shared neighbors of $i,j$. A listing of all topological predictors is given in Table \[table:top\_feat\], along with corresponding literature references. *Global predictors.* These predictors quantify various network-level statistics and are inherited by each pair of nodes $i,j$ that is a candidate missing link. Their primary utility is to provide global context to other predictors under supervised learning. For example, a predictor that performs well on small networks, but poorly on larger networks, can be employed appropriately under a supervised model when the global measure of the network's size is available. Or, a large variance in the degree distribution would imply that a predictor based on degree product may be useful. Or, a large clustering coefficient would imply that an assortative community detection algorithm like modularity is likely to be useful. For this reason, global predictors are not expected by themselves to be accurate predictors of missing links (see Figs. \[fig:HFR\] and \[fig:CFB\] and Tables \[tab:APR\_indiv\_real\] and \[tab:APR\_indiv\_synt\]). These global predictors are generally useful in capturing missingness in unseen networks and not on the same network link prediction experiments. These features help to learn from existing configurations in training networks and generalize them to unseen networks in experiments like Fig. \[fig:FID\] in the main text. The 8 global predictors are the number of nodes (N), number of observed edges (OE), average degree (AD), variance of the degree distribution (VD), network diameter (ND), degree assortativity of graph (DA), network transitivity or clustering coefficient (NT), and average (local) clustering coefficient (ACC) @newman:networks:2018 [@liben2007link; @al2011survey; @cukierski2011graph]. \[b!\] ---------------------------- ------------------------------------------------------------------------------------ ----------- ----------- ------------ ----------------------- Abbreviation Description Global Pairwise Node-based Ref. \[0.5ex\] N number of nodes $\bullet$ @newman:networks:2018 OE number of observed edges $\bullet$ @newman:networks:2018 AD average degree $\bullet$ @newman:networks:2018 VD variance of degree distribution $\bullet$ @newman:networks:2018 ND network diameter $\bullet$ @newman:networks:2018 DA degree assortativity of graph $\bullet$ @networkx NT network transitivity (clustering coefficient) $\bullet$ @newman:networks:2018 ACC average (local) clustering coefficient $\bullet$ @newman:networks:2018 \[0.5ex\] CN common neighbors of $i,j$ $\bullet$ @liben2007link SP shortest path between $i,j$ $\bullet$ @liben2007link LHN Leicht-Holme-Newman index of neighbor sets of $i,j$ $\bullet$ @leicht2006vertex PPR $j$-th entry of the personalized page rank of node $i$ $\bullet$ @networkx PA preferential attachment (degree product) of $i,j$ $\bullet$ @liben2007link JC Jaccard's coefficient of neighbor sets of $i,j$ $\bullet$ @liben2007link AA Adamic/Adar index of $i,j$ $\bullet$ @liben2007link RA resource allocation index of $i,j$ $\bullet$ @networkx LRA entry $i,j$ in low rank approximation (LRA) via singular value decomposition (SVD) $\bullet$ @cukierski2011graph dLRA dot product of columns $i$ and $j$ in LRA via SVD for each pair of nodes $i,j$ $\bullet$ @cukierski2011graph mLRA average of entries $i$ and $j$'s neighbors in low rank approximation $\bullet$ @cukierski2011graph LRA-approx an approximation of LRA $\bullet$ @cukierski2011graph dLRA-approx an approximation of dLRA $\bullet$ @cukierski2011graph mLRA-approx an approximation of mLRA $\bullet$ @cukierski2011graph \[0.5ex\] LCC$_i$, LCC$_j$ local clustering coefficients for $i$ and $j$ $\bullet$ @networkx AND$_i$, AND$_j$ average neighbor degrees for $i$ and $j$ $\bullet$ @networkx SPBC$_i$, SPBC$_j$ shortest-path betweenness centralities for $i$ and $j$ $\bullet$ @networkx CC$_i$, CC$_j$ closeness centralities for $i$ and $j$ $\bullet$ @networkx DC$_i$, DC$_j$ degree centralities for $i$ and $j$ $\bullet$ @networkx EC$_i$, EC$_j$ eigenvector centralities for $i$ and $j$ $\bullet$ @networkx KC$_i$, KC$_j$ Katz centralities for $i$ and $j$ $\bullet$ @networkx LNT$_i$, LNT$_j$ local number of triangles for $i$ and $j$ $\bullet$ @networkx PR$_i$, PR$_j$ Page rank values for $i$ and $j$ $\bullet$ @networkx LC$_i$, LC$_j$ load centralities for $i$ and $j$ $\bullet$ @networkx ---------------------------- ------------------------------------------------------------------------------------ ----------- ----------- ------------ ----------------------- \[table:top\_feat\] *Pairwise predictors.* These predictors are functions of the joint topological properties of the pair of nodes $i,j$ being considered. The 14 pairwise predictors are the number of common neighbors of $i,j$ (CN), shortest path between $i,j$ (SP), Leicht-Holme-Newman index of neighbor sets of $i,j$ (LHN), personalized page rank (PPR),[^1] preferential attachment or degree product of $i,j$ (PA), Jaccard coefficient of the neighbor sets of $i,j$ (JC), Adamic-Adar index of $i,j$ (AA), resource allocation index of $i,j$ (RA), the entry $i,j$ in a low rank approximation (LRA) via a singular value decomposition (SVD) (LRA), the dot product of the $i,j$ columns in the LRA via SVD (dLRA), the mean of entries $i$ and $j$'s neighbors in the LRA (mLRA), and simple approximations of the latter three predictors (LRA-approx, dLRA-approx, mLRA-approx) @newman:networks:2018 [@liben2007link; @al2011survey; @cukierski2011graph]. We omit from consideration several pairwise predictors found in the literature, e.g. edge betweenness centrality, due to their large computational complexity for an evaluation as large as ours. *Node-based predictors.* These predictors are functions of the independent topological properties of the individual nodes $i$ and $j$, and thus produce a pair of predictor values. Unlike many of the pairwise predictors, which can be used as standalone algorithms to predict missing links, these node-based predictors do not directly score the likelihood that $i,j$ is a missing link. Instead, the particular function that converts the pair of node-based predictors into a score is learned within the supervised framework. The 20 node-based predictors are two instance each of the local clustering coefficient (LCC), average neighbor degree (AND), shortest-path betweenness centrality (SPBC), closeness centrality (CC), degree centrality (DC), eigenvector centrality (EC), Katz centrality (KC), local number of triangles (LNT), Page rank (PR), and load centrality (LC) @newman:networks:2018 [@liben2007link; @al2011survey; @cukierski2011graph]. Model-based predictors {#model-based-predictors .unnumbered} ---------------------- Model-based predictors are a broad class of prediction algorithms that rely on models of large-scale network structure to score pairs $i,j$ that are more or less likely to be missing. To make link predictions, model-based algorithms employ one of two strategies: likelihood or optimization. In the first case, a method estimates a parametric probability $\Pr(i\to j\,|\,\theta)$ that a node pair should be connected, given a decomposition of a network into communities, as in the stochastic block model and its variants. In the second it predicts a link as missing if it would improve its measure of community structure, as in Infomap and modularity. We consider 11 model-based predictors for missing links, which include many state-of-the-art in community detection algorithms @ghasemian2018evaluating, are sufficiently scalable to be applied in an evaluation as large as ours, and each of which has previously been used as a standalone link prediction algorithm. A listing of all model-based predictors is given in Table \[table:abbr\], along with the corresponding literature references. For the model-based predictors that make predictions by likelihood, we follow Ref. @ghasemian2018evaluating to employ a "model-specific" score function for each method. Under this approach, a particular method first decomposes the network into a set of communities using its corresponding parametric model, and then extracts from that same parametric model a score $\Pr(i\to j\,|\,\theta)$ for each candidate pair $i,j$. See Ref. @ghasemian2018evaluating for additional details. \[h!\] ---------------- ------------------------------------------------------------------------ ------------ -------------- -------------------------- Abbreviation Description Likelihood Optimization Ref. \[0.5ex\] Q modularity, Newman-Girvan $\bullet$ @newman2004finding Q-MR modularity, Newman's multiresolution $\bullet$ @newman2016community Q-MP modularity, message passing $\bullet$ @zhang2014scalable B-NR (SBM) Bayesian stochastic block model, Newman and Reinert $\bullet$ @newman2016estimating B-NR (DC-SBM) Bayesian degree-corrected stochastic block model, Newman and Reinert $\bullet$ @newman2016estimating B-HKK (SBM) Bayesian stochastic block model, Hayashi, Konishi and Kawamoto $\bullet$ @hayashi2016tractable cICL-HKK (SBM) Corrected integrated classification likelihood, stochastic block model $\bullet$ @hayashi2016tractable Infomap Map equation $\bullet$ @rosvall2008maps MDL (SBM) Minimum description length, stochastic block model $\bullet$ @peixoto2013parsimonious MDL (DC-SBM) Minimum description length, degree-corrected stochastic block model $\bullet$ @peixoto2013parsimonious S-NB Spectral with non-backtracking matrix $\bullet$ @Krzakala2013 ---------------- ------------------------------------------------------------------------ ------------ -------------- -------------------------- \[table:abbr\] Embedding-based predictors {#embedding-based-predictors .unnumbered} -------------------------- Embedding-based predictors are derived from graph embedding techniques, which attempt to automate the feature engineering phase of learning with graphs by projecting a network's nodes into a relatively low-dimensional latent space, with the goal of locally preserving the node neighborhoods. Embedding-based predictors are thus either node coordinates in such an embedding, or measure of distance between embedded pairs. We consider a total of 150 embedding-based predictors, all derived from 2 popular graph embedding algorithms, DeepWalk (emb-DeepWalk) @perozzi2014deepwalk—a special case of node2vec (emb-node2vec) @grover2016node2vec—and the variational graph auto encoder (emb-vgae) @kipf2016variational. Using emb-DeepWalk and emb-vgae, we embed each network into a 128-dimensional and 16-dimensional space, respectively. For each pair of nodes $i,j$, we then apply a Hadamard product function to the corresponding pair of coordinates to obtain 144 link predictors as features for supervised learning @hamilton2017representation. To these, we add 6 more predictors by applying, for each of the 2 embedding methods, a different distance or similarity function to the corresponding pair of coordinate vectors: an inner product, an inner product with a sigmoid function, and Euclidean distance. Stacked generalization and meta-learning for link prediction {#stacked-generalization-and-meta-learning-for-link-prediction .unnumbered} ------------------------------------------------------------ Meta-learning or ensemble techniques are a powerful class of supervised machine learning algorithms that can learn from data how to combine individual predictors into a single, more accurate algorithm @breiman1996bagging [@schapire1999brief; @dietterich2000ensemble; @sewell2008ensemble]. By treating the output of individual prediction algorithms as features of the input instances themselves, a supervised meta-learning algorithm can construct a correlation function that relates which individual algorithm is most accurate on which subset of inputs. Of the several approaches to meta-learning, we focus on the approach of stacked generalization or model "stacking" @wolpert1992stacked, and we consider two boosting approaches (see below) as a robustness check. We leave further investigation of other meta-learning algorithms for future work. Stacking aims to minimize the generalization error of a set of component learners. In the classic setting, the two training levels can be summarized as follows. Given a dataset $\mathcal{D}=\{(y_{\ell},x_{\ell}), \ell\in\{1, ... ,L\} \}$, where $x_{\ell}$ is the feature vector of the $\ell$-th example and $y_{\ell}$ is its label, randomly split $\mathcal{D}$ into $J$ "folds" appropriate for $J$-fold cross validation. Each fold $j$ contributes once as a test set $\mathcal{D}^j$ and the rest contributes once as a training set $\mathcal{D}^{-j} = \mathcal{D} \smallsetminus \mathcal{D}^j$. For each base classifier $r$, where $r\in\{1,...,R\}$, called a level-$0$ generalizer, we fit it to the $j$th fold in the training set $\mathcal{D}^{-j}$ to build a model $\mathcal{M}_r^{-j}$, called a level-$0$ model. Now for each data point $x_{\ell}$ in the $j$th test set, we employ these level-$0$ models $\mathcal{M}_r^{-j}$ to predict the output $z_{r\ell}$. The new data set $\mathcal{D}_{CV} =\{(y_{\ell},z_{1\ell},...,z_{R\ell}), \ell\in\{1, ... ,L\}\}$, is now prepared for the next training level, called a level-$1$ generalizer. In the second training phase, an algorithm learns a new model from this data, denoted as $\tilde{\mathcal{M}}$. Now, we again train the base classifiers using the whole data $\mathcal{D}$, noted as $\mathcal{M}_r$, we complete the training phase and the models are ready to classify a new data point $x$. The new data point will first be fed into the trained base classifiers $\mathcal{M}_r$ and then the output of these level-$0$ models will construct the input for the next level model $\tilde{\mathcal{M}}$. In the network setting of link prediction, the classifiers (predictors) in the first level are all unsupervised, and therefore, we alter the stacked generalization algorithm as follows to account for this difference and to adapt it to a network setting. For a given network $G=(V,E)$, we sample the edges uniformly and construct the observed network $G'=(V,E')$, where $| E |=\alpha | E |$ ($\alpha=0.8$ in our experiments). Here, we use only the uniform edge-removal model and leave the analysis of any non-uniform edge removal model for future work. The removed edges $E\setminus E'$ are considered as held-out data in the link prediction task. Then, in order to train a model, we remove $1-\alpha'$ ($\alpha'=0.8$ in our experiments) of the edges as our positive examples and take all non-edges in the observed network $G'$ as negative examples. Although this procedure makes the negative samples noisy, since the networks are sparse, it introduces a negligible error in the learned model, and should not significantly effect the model's performance. In our setting, the unsupervised classifiers in the first level are our level-$0$ predictors, and we use the scores coming from these link prediction techniques as our meta features. The second training phase is conducted through supervised learning with $5$-fold cross validation on the training set. We use a standard supervised random forest algorithm for the meta-learning step, and assess the learning process on 3 within-family models (topol. only, model-based only, and embed. only) and on 4 across-family models (all families, and each of topol. & model, topol. & embed, and model & embed.), for a total of 7 stacked models. *Model selection.* In order to choose the best parameters of the model using 5-fold cross validation, we can choose the parameters of the model through optimizing the AUC performance or the F measure. In the main text all figures and tables show results for a standard random forest with the parameters chosen through F measure optimization and the results are reported on the test set. Results for, instead, optimizing using the AUC are given in Table \[tab:rf\_AUC\] which can be compared with Table \[tab:satexp\] in the main text. *Alternative meta-learning algorithms.* In addition to a standard random forest, we also evaluate two methods of boosting, XGBoost @chen2016xgboost and AdaBoost @freund1997decision, for learning a single algorithm over the individual predictors. The results from these meta-learning algorithms are provided in Tables \[tab:xgb\_f\]-\[tab:ada\_AUC\] for different
{'source': 'arXiv_out/1909'}