Consistencies and inconsistencies between model selection and link prediction in networks

A principled approach to understand network structures is to formulate generative models. Given a collection of models, however, an outstanding key task is to determine which one provides a more accurate description of the network at hand, discounting statistical fluctuations. This problem can be approached using two principled criteria that at first may seem equivalent: selecting the most plausible model in terms of its posterior probability; or selecting the model with the highest predictive performance in terms of identifying missing links. Here we show that while these two approaches yield consistent results in most cases, there are also notable instances where they do not, that is, where the most plausible model is not the most predictive. We show that in the latter case the improvement of predictive performance can in fact lead to overfitting both in artificial and empirical settings. Furthermore, we show that, in general, the predictive performance is higher when we average over collections of models that are individually less plausible than when we consider only the single most plausible model.

Figure 1

(a) Number of edges between groups in a synthetic network, before the removal of edges, with $e_{\text{in}}$ edges in the diagonal and $e_{\text{out}}$ in the of diagonal, represented as squares. (b) The same as in (a), but after a single edge has been removed, in the position shown in red (grey). The modified entry has $e_{\text{out}}-1$ edges, which will cause the predictive likelihood in this position to be lower than for all the other entries.

Figure 2

Consistency and discrepancy between model selection approaches in empirical networks. Comparison between AUC values and the description length $\mathrm{\Sigma }$, after the removal of a fraction of $f=0.05$ of the edges for two empirical networks: (a) global airports; (b) Movielens movie ratings. We show results obtained by comparing the degree-corrected nested SBM with the three remaining variants, as shown in the legend: traditional SBM with noninformative priors, degree-corrected with noninformative priors, and traditional with nested priors. Each point corresponds to a single instance of the removed edges, and the difference $\mathrm{\Delta }\text{AUC}$ in AUC and $\mathrm{\Delta }\mathrm{\Sigma }$ in description length are with respect to the degree-corrected nested SBM. Points in the grey region represent inconsistent results in which the model with the smallest description length (in both cases, the degree-corrected nested model) has smaller AUCs (lower predictive power).

Figure 3

Significance of the discrepancy between model selection approaches. For each pair of model classes and for all of the empirical networks in Table 1, we show the $t$ statistic [Eq. (14)] for the difference in AUC and the description length $\mathrm{\Sigma }$. Results correspond to 30–150 edge removal experiments of a fraction $f=0.05$ of the edges (we observe similar results for different fractions of removed edges). The number of repetitions for each network is different because for larger networks it takes a longer time to get the results but, at the same time, the fluctuations between results are smaller. In general, we use as many repetitions as necessary to get reasonable error bars in all our estimates. Colors (gray tones) show the associated $p$ value. Points in the top half of the figure indicate a consistency between both model selection criteria: The model with the smallest description length also yields the largest AUC. For points in the bottom half (grey), the comparisons are inconsistent. On the right axis, we show a histogram of the $t_{\mathrm{\Delta }\text{AUC}}$ values, showing that a majority of comparisons are consistent.

Figure 4

Comparison between single-point and average link prediction for four real networks and the four model classes. Single-point predictions are obtained using Eq. (12) whereas average predictions are obtained using MCMC sampling to approximate Eq. (11). In all cases, we removed a fraction $f=0.05$ of the true links of the network, and computed the AUC to measure predictive power (see text). Sampling with the simplest model class (the traditional noninformative SBM) always gives more accurate predictions than the single-point prediction with the best model.

Figure 5

(a) Average AUC values obtained by removals of a single edge from a PP with $n_r=100$, $B=10$, and $〈k〉=20$, both for “canonical” (i.e., unconstrained) as well as microcanonical samples, where Eq. (B2) holds. The legend indicates which model was used to compute the AUC (i.e., the SBM or the DC-SBM). The solid line corresponds to Eq. (B13), and the vertical line the value $c^{*}=1/B+(B-1)/\left(B\sqrt{〈k〉}\right)$ corresponding to the detectability threshold. The inset shows the difference of the AUC values obtained with the two model classes, ${\text{AUC}}_{\text{DC-SBM}}-{\text{AUC}}_{\text{SBM}}$, with networks sampled from the canonical model. (b) The same as (a), but with a fraction $f=0.05$ of the edges removed. (c) Description length difference between the SBM and DC-SBM, both for the canonical and microcanonical samples, for a fraction $f=0.05$ of the edges removed.

Figure 6

(a) AUC values obtained by removing a fraction $f=0.05$ of the edges of a PP with $n_r=100$, $B=10$, $〈k〉=20$, and $c=0.8$, for microcanonical samples fulfilling Eq. (B2), and forcing $B=B^{\prime }$ during inference. (b) The same as (a), but with the description length $\mathrm{\Sigma }$, instead. The MDL criterion pinpoints the correct planted value of $B^{\prime }=10$, whereas AUC overfits.