Free Lunches in Link Prediction

Ghasemian et al. (10) frame their contribution in terms of the so-called no-free-lunch (NFL) theorems (12, 13). Generally speaking, NFL theorems state that, for certain classes of mathematical problems, no single model or algorithm performs better (or worse) than any other when applied to all possible problems in the class; if a model is better than another at solving one particular problem, then it must be worse at others. In network science, an NFL theorem has been proved for the problem of identifying natural groups (or communities or modules) of nodes in the network (13). According to the theorem, all algorithms perform identically when applied to all possible networks and all possible groupings of nodes in each network. So Ghasemian et al. (10) hypothesize that link prediction may be of the NFL class and, therefore, argue that no algorithm may be consistently better at predicting links across all networks.

With this rationale they use model stacking (11), that is, a metamodel that works by combining all other models; if each model is good at some link prediction problems and bad at others, then such a metamodel may be able to get the best of each one and be good in all cases. Indeed, they find that model stacking performs better than all individual models in most networks considered. And here is the paradox—the stacked model is, after all, another model, so this looks exactly like a free lunch. In this regard, the results of Ghasemian et al. (10) highlight the theoretical value of NFL theorems, as well as their limitations from a practical point of view. Theoretically, they compel us to think about ensembles of models, each model having its own virtues and limitations. In practice, we are rarely (if ever) interested in solving all problems of a given class, and some models are more appropriate than others because they are good at solving the interesting problems and bad at solving the uninteresting ones. So, in practice, there are free lunches. In the particular case of link prediction, we are not interested in predicting links in any network, but only real-world networks. And real-world networks have some general properties that make some specific models more appropriate than others, which network science has been uncovering in the last 20 y—broad degree distributions or the related properties of group structure and “small worldiness,” to name the most prominent ones.

By bringing forth this apparent paradox of NFL theorems, the article by Ghasemian et al. (10) invites us to think more deeply about two keys aspects of network science (and, in a way, science more broadly): ensemble methods and model expressiveness.

Ensemble Methods

With regard to the first issue, Ghasemian et al. (10) convincingly argue for the need to combine different models because of their error diversity, that is, because each model makes certain errors and, conversely, is able to correctly capture certain unique features. By combining models we can get the best of each. But, no less important and perhaps more fundamental, ensemble methods are necessary because in (network) science we are seldom certain about the exact process that generated whatever empirical observations we may have, and this uncertainty must be taken into consideration using probability theory (14). In particular, given a set M={M1,M2,…}$ℳ=\left.M_1,M_2,\dots \right\}$ of candidate models that could potentially explain a certain dataset D, each model Mi$M_i$ has a probability p(Mi|D)$p(M_i|D)$ of being the true generating model given the data. Given this posterior distribution over models, and assuming that the true generating model is one of the models in ℳ, the consistent estimate f∗$f^{*}$ of a given property f(M)$f(M)$ (for example, the existence of a link in a network in the link prediction problem) is

Model Expressiveness

Ghasemian et al. (10) also shed light on the second issue, namely model expressiveness in network science. Model expressiveness is the ability of a model to represent distinct relevant situations; in network science, a model is expressive to the extent that it can represent many different features of real-world networks (for example, broad connectivity distributions, connectivity correlations, network motifs, or group structure). The proposed model stacking is explicitly built to be very expressive by incorporating the expressiveness of each of the 203 constituent models, but not all constituent models are equally expressive. Indeed, given a network and the stacked model, a very interesting question is, Which constituent model contributes most to the description of the network? It is not difficult to see how answering this question could illuminate the mechanisms responsible for the structure of the network and how the process of mechanism discovery could be set on solid grounds by extending this scheme—adding new models to the stacked model, checking how they improve predictive power, and iterating the process.

In this sense, the work of Ghasemian et al. (10) is also seminal as a large-scale comparison of the predictive ability of hundreds of models on hundreds of networks. And the results are telling—stochastic block models (3, 16⇓–18) and, in particular, the degree-corrected stochastic block model (19) are, on average, the most explanatory individual models for biological, economic, technological, information, and transportation networks, that is, for all types of networks except social networks (figure 1 in ref. 10). Considering, again, the NFL theorems, the general goodness of stochastic block models is remarkable and suggests that they are, themselves, extremely expressive models. In fact, Bayesian model averaging over the whole family of stochastic block models (3, 9, 20) is almost as predictive of links as the whole stacked model including 203 diverse constituent models (figure 3 in ref. 10)—except, of course, that when the Bayesian model averaging of the stochastic block models is added to the stack, the stacked model comes out ahead by a fair amount again. So stochastic block models are very expressive, but can still benefit for features that are present in other existing models. Can we find ways to incorporate such features into mathematically tractable model families?

In very remarkable ways, then, and besides link prediction, Ghasemian et al. (10) contribute significantly to a program for solid progress in network modeling and for understanding the generative mechanisms of complex networks. In a way, it seems, progress in network science is about finding free lunches—model families that can express the features of real-world networks, that we can explore systematically, and that we can refine as new patterns are uncovered to improve their predictive performance.