# Structure and inference in annotated networks

arXiv: https://arxiv.org/abs/1507.04001 · HTML: https://mlsanity.com/paper/1507.04001/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2015.

## Built on by (most cited first, 30 of 30)

- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [Inference of hyperedges and overlapping communities in hypergraphs](https://mlsanity.com/paper/2204.05646/) (2022)
- [An iterative clustering algorithm for the Contextual Stochastic Block Model with optimality guarantees](https://mlsanity.com/paper/2112.10467/) (2021)
- [Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs](https://mlsanity.com/paper/2302.01204/) (2023)
- [Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model](https://mlsanity.com/paper/2310.19854/) (2023)
- [Structure and inference in hypergraphs with node attributes](https://mlsanity.com/paper/2311.03857/) (2023)
- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Bayesian community detection for networks with covariates](https://mlsanity.com/paper/2203.02090/) (2022)
- [Multilayer Networks for Text Analysis with Multiple Data Types](https://mlsanity.com/paper/2106.15821/) (2021)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Flexible inference in heterogeneous and attributed multilayer networks](https://mlsanity.com/paper/2405.20918/) (2024)
- [Comparing the information content of probabilistic representation spaces](https://mlsanity.com/paper/2405.21042/) (2024)
- [Learning Joint and Individual Structure in Network Data with Covariates](https://mlsanity.com/paper/2406.08776/) (2024)
- [Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation](https://mlsanity.com/paper/2505.20992/) (2025)
- [Nested stochastic block model for simultaneously clustering networks and nodes](https://mlsanity.com/paper/2307.09210/) (2023)
- [Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models](https://mlsanity.com/paper/2401.00688/) (2024)
- [Node metadata can produce predictability transitions in network inference problems](https://mlsanity.com/paper/2103.14424/) (2021)
- [Extending Bootstrap AMG for Clustering of Attributed Graphs](https://mlsanity.com/paper/2109.09367/) (2021)
- [Geodesic Length Distribution in Sparse Network Ensembles](https://mlsanity.com/paper/2111.02330/) (2021)
- [Perfect Spectral Clustering with Discrete Covariates](https://mlsanity.com/paper/2205.08047/) (2022)
- [A network community detection method with integration of data from multiple layers and node attributes](https://mlsanity.com/paper/2305.13012/) (2023)
- [A stochastic block model for community detection in attributed networks](https://mlsanity.com/paper/2308.16382/) (2023)
- [Network-based Neighborhood regression](https://mlsanity.com/paper/2407.04104/) (2024)
- [Changepoint Detection in Highly-Attributed Dynamic Graphs](https://mlsanity.com/paper/2407.06998/) (2024)
- [Robust Markov stability for community detection at a scale learned based on the structure](https://mlsanity.com/paper/2504.11621/) (2025)
- [How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?](https://mlsanity.com/paper/2506.11869/) (2025)
- [Learning Multi-Order Block Structure in Higher-Order Networks](https://mlsanity.com/paper/2511.21350/) (2025)
- [Covariate-assisted graph matching](https://mlsanity.com/paper/2512.11761/) (2025)
- [Alcmean's: Unsupervised community detection using local Laplacian, automatic detection of the number of centers](https://mlsanity.com/paper/2606.09100/) (2026)
- [Topology-induced Operators Reveal Complementary Graph Representations without Training](https://mlsanity.com/paper/2609.08152/) (2026)

## Abstract (arXiv)

For many networks of scientific interest we know both the connections of the network and information about the network nodes, such as the age or gender of individuals in a social network, geographic location of nodes in the Internet, or cellular function of nodes in a gene regulatory network. Here we demonstrate how this "metadata" can be used to improve our analysis and understanding of network structure. We focus in particular on the problem of community detection in networks and develop a mathematically principled approach that combines a network and its metadata to detect communities more accurately than can be done with either alone. Crucially, the method does not assume that the metadata are correlated with the communities we are trying to find. Instead the method learns whether a correlation exists and correctly uses or ignores the metadata depending on whether they contain useful information. The learned correlations are also of interest in their own right, allowing us to make predictions about the community membership of nodes whose network connections are unknown. We demonstrate our method on synthetic networks with known structure and on real-world networks, large and small, drawn from social, biological, and technological domains.