Network Structure, Metadata, and the Prediction of Missing Nodes and Annotations

The empirical validation of community detection methods is often based on available annotations on the nodes that serve as putative indicators of the large-scale network structure. Most often, the suitability of the annotations as topological descriptors itself is not assessed, and without this it is not possible to ultimately distinguish between actual shortcomings of the community detection algorithms, on one hand, and the incompleteness, inaccuracy, or structured nature of the data annotations themselves, on the other. In this work, we present a principled method to access both aspects simultaneously. We construct a joint generative model for the data and metadata, and a nonparametric Bayesian framework to infer its parameters from annotated data sets. We assess the quality of the metadata not according to their direct alignment with the network communities, but rather in their capacity to predict the placement of edges in the network. We also show how this feature can be used to predict the connections to missing nodes when only the metadata are available, as well as predicting missing metadata. By investigating a wide range of data sets, we show that while there are seldom exact agreements between metadata tokens and the inferred data groups, the metadata are often informative of the network structure nevertheless, and can improve the prediction of missing nodes. This shows that the method uncovers meaningful patterns in both the data and metadata, without requiring or expecting a perfect agreement between the two.

Popular Summary

A long-standing goal related to network systems is the characterization of their large-scale structure. In this context, the most popular approach is the division of the network into modules or “communities” that group nodes into discrete classes according to their connection patterns with the rest of the network. However, this idea has generated an enormous variety of competing methods to extract communities from network data. With the goal of interpreting and validating the output of various methods of dividing networks, researchers have used comparisons with metadata (i.e., data annotations that are assumed to correspond to the “true” division of the network into meaningful categories). However, recent systematic comparisons of various community detection methods with metadata have revealed that their relative correspondence is very poor in the majority of cases. Here, we argue that this problem is the outcome of a naive and unrealistic interpretation of the role of the network annotations, and we propose a more refined approach by formally erasing the distinction between data and metadata, and by formulating a probabilistic generative model that describes both of their structures simultaneously.

By inferring the parameters of our model from data, we can determine the precise relationship between data and metadata, instead of specifying it beforehand. Furthermore, our nonparametric Bayesian inference framework is capable of distinguishing structure from noise, and it reveals patterns according to their statistical significance. We apply our method to an assortment of annotated network data sets such as APS citations, Amazon co-purchases, and IMDB movie data, and we find that their annotations vary considerably in their predictive quality, showing that their indiscriminate use in the validation of community-finding algorithms is often misguided.

Our findings accordingly reveal that metadata should be treated with caution and used as one tool of many to group nodes within networks.

Figure 1

Schematic representation of the joint data-metadata model. The data layer is composed of data nodes and is described by an adjacency matrix $\mathit{A}$, and the metadata layer is composed of the same data nodes, as well as tag nodes, and is described by a bipartite adjacency matrix $\mathit{T}$. Both layers are generated by two coupled degree-corrected SBMs, where the partition of the data nodes into groups is the same in both layers.

Figure 2

Joint data-metadata model inferred for the network of American football teams [45]. (a) Hierarchical partition of the data nodes (teams), corresponding to the “data” layer. (b) Partition of the data (teams) and tag (conference) nodes, corresponding to the second layer. (c) Average predictive likelihood of missing nodes relative to using only the data (discarding the conferences), using the original conference assignment of Ref. [45] (GN) and the corrected assignment of Ref. [46] (TE).

Figure 3

Node prediction performance, measured by the average predictive likelihood ratio $⟨\lambda ⟩$ for a variety of annotated data sets (see Appendix pp2 for descriptions). Values above $1/2$ indicate that the metadata improve the node prediction task. On the right-hand axis a histogram of the likelihood ratios is shown, with a red line marking the average.

Figure 4

Top: Examples of artificial annotated networks, showing aligned, misaligned, and random metadata, as described in the text. Bottom: Node prediction performance, measured by the likelihood ratio $⟨\lambda ⟩$, average over all possible single-node removals, for annotated networks generated with $B_d=B_t=B$ groups, $N=M=30B$ nodes and tags, $E=E_m=5N$ node-node and tag-node edges, with specific network construction given by the legend. One of the curves corresponds to networks with misaligned metadata with a larger number of nodes, $N=M=10^3\times B$.

Figure 5

Metadata predictiveness for several empirical data sets. The panels show the predictiveness of metadata groups ${\mu }_r$ [Eq. (18)] versus metadata group sizes $n_r$.The sizes of the symbols indicate the metadata frequency. The symbols correspond to the most frequent types of tags in each group (which may contain tags of different types). On the axis of each figure are shown marginal histograms, weighted according to the tag frequencies. A red horizontal line marks the average predictiveness.

Figure 6

Average predictive likelihood ratio $⟨\lambda ⟩$ of missing metadata tags (conferences) for the American football data, using the annotations given in Ref. [47]. Tags 11–18 are “independents,” i.e., teams that do not belong to any conference. The dashed line marks the value $1/19$, corresponding to a uniform likelihood between all tags.