# The ground truth about metadata and community detection in networks

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2016.

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

- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [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)
- [DINE: Dimensional Interpretability of Node Embeddings](https://mlsanity.com/paper/2310.01162/) (2023)
- [Normalized mutual information is a biased measure for classification and community detection](https://mlsanity.com/paper/2307.01282/) (2023)
- [Structure and inference in hypergraphs with node attributes](https://mlsanity.com/paper/2311.03857/) (2023)
- [The Implications of the No-Free-Lunch Theorems for Meta-induction](https://mlsanity.com/paper/2103.11956/) (2021)
- [Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity](https://mlsanity.com/paper/2209.04562/) (2022)
- [Nonbacktracking spectral clustering of nonuniform hypergraphs](https://mlsanity.com/paper/2204.13586/) (2022)
- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection](https://mlsanity.com/paper/2210.09186/) (2022)
- [Modularity Based Community Detection in Hypergraphs](https://mlsanity.com/paper/2406.17556/) (2024)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks](https://mlsanity.com/paper/2310.01144/) (2023)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Graph Neural Network Surrogates of Fair Graph Filtering](https://mlsanity.com/paper/2303.08157/) (2023)
- [Inference and Visualization of Community Structure in Attributed Hypergraphs Using Mixed-Membership Stochastic Block Models](https://mlsanity.com/paper/2401.00688/) (2024)
- [MDL-Pool: Adaptive Multilevel Graph Pooling Based on Minimum Description Length](https://mlsanity.com/paper/2409.10263/) (2024)
- [Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model](https://mlsanity.com/paper/2601.06262/) (2026)
- [Synwalk -- Community Detection via Random Walk Modelling](https://mlsanity.com/paper/2101.08623/) (2021)
- [Overcoming Bias in Community Detection Evaluation](https://mlsanity.com/paper/2102.03472/) (2021)
- [The Automatic Quasi-clique Merger algorithm (AQCM)](https://mlsanity.com/paper/2103.04186/) (2021)
- [Node metadata can produce predictability transitions in network inference problems](https://mlsanity.com/paper/2103.14424/) (2021)
- [pygrank: A Python Package for Graph Node Ranking](https://mlsanity.com/paper/2110.09274/) (2021)
- [A Modular Framework for Centrality and Clustering in Complex Networks](https://mlsanity.com/paper/2111.11623/) (2021)
- [Identifying bias in cluster quality metrics](https://mlsanity.com/paper/2112.06287/) (2021)
- [Perfect Spectral Clustering with Discrete Covariates](https://mlsanity.com/paper/2205.08047/) (2022)
- [Edge Augmentation on Disconnected Graphs via Eigenvalue Elevation](https://mlsanity.com/paper/2207.05301/) (2022)
- [Bayesian Detection of Mesoscale Structures in Pathway Data on Graphs](https://mlsanity.com/paper/2301.11120/) (2023)

## Abstract (arXiv)

Across many scientific domains, there is a common need to automatically extract a simplified view or coarse-graining of how a complex system's components interact. This general task is called community detection in networks and is analogous to searching for clusters in independent vector data. It is common to evaluate the performance of community detection algorithms by their ability to find so-called "ground truth" communities. This works well in synthetic networks with planted communities because such networks' links are formed explicitly based on those known communities. However, there are no planted communities in real world networks. Instead, it is standard practice to treat some observed discrete-valued node attributes, or metadata, as ground truth. Here, we show that metadata are not the same as ground truth, and that treating them as such induces severe theoretical and practical problems. We prove that no algorithm can uniquely solve community detection, and we prove a general No Free Lunch theorem for community detection, which implies that there can be no algorithm that is optimal for all possible community detection tasks. However, community detection remains a powerful tool and node metadata still have value so a careful exploration of their relationship with network structure can yield insights of genuine worth. We illustrate this point by introducing two statistical techniques that can quantify the relationship between metadata and community structure for a broad class of models. We demonstrate these techniques using both synthetic and real-world networks, and for multiple types of metadata and community structure.