# Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 88 references that are in the map.
- First posted on arXiv 17 Oct 2022.

## Builds on (most cited first, 24 of 24)

- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [The ground truth about metadata and community detection in networks](https://mlsanity.com/paper/1608.05878/) (2016)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Stacking Models for Nearly Optimal Link Prediction in Complex Networks](https://mlsanity.com/paper/1909.07578/) (2019)
- [Bayesian stochastic blockmodeling](https://mlsanity.com/paper/1705.10225/) (2017)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [Nonparametric Bayesian inference of the microcanonical stochastic block model](https://mlsanity.com/paper/1610.02703/) (2016)
- [Network histograms and universality of blockmodel approximation](https://mlsanity.com/paper/1312.5306/) (2013)
- [Evaluating Overfit and Underfit in Models of Network Community Structure](https://mlsanity.com/paper/1802.10582/) (2018)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Community detection in networks: Structural communities versus ground truth](https://mlsanity.com/paper/1406.0146/) (2014)
- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [Reconstructing networks with unknown and heterogeneous errors](https://mlsanity.com/paper/1806.07956/) (2018)
- [A physical model for efficient ranking in networks](https://mlsanity.com/paper/1709.09002/) (2017)
- [The many facets of community detection in complex networks](https://mlsanity.com/paper/1611.07769/) (2016)
- [Revealing consensus and dissensus between network partitions](https://mlsanity.com/paper/2005.13977/) (2020)
- [Statistical inference of assortative community structures](https://mlsanity.com/paper/2006.14493/) (2020)
- [Consistencies and inconsistencies between model selection and link prediction in networks](https://mlsanity.com/paper/1705.07967/) (2017)
- [Disentangling homophily, community structure and triadic closure in networks](https://mlsanity.com/paper/2101.02510/) (2021)
- [Universality of the stochastic block model](https://mlsanity.com/paper/1806.04214/) (2018)
- [Significant Scales in Community Structure](https://mlsanity.com/paper/1306.3398/) (2013)
- [Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths](https://mlsanity.com/paper/2112.00183/) (2021)
- [Model selection and hypothesis testing for large-scale network models with overlapping groups](https://mlsanity.com/paper/1409.3059/) (2014)

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

- [The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks](https://mlsanity.com/paper/2310.01144/) (2023)
- [MDL-Pool: Adaptive Multilevel Graph Pooling Based on Minimum Description Length](https://mlsanity.com/paper/2409.10263/) (2024)
- [Why the Metric Backbone Preserves Community Structure](https://mlsanity.com/paper/2406.03852/) (2024)

## Abstract (arXiv)

The task of community detection, which aims to partition a network into clusters of nodes to summarize its large-scale structure, has spawned the development of many competing algorithms with varying objectives. Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model, while other methods are descriptive, dividing a network according to an objective motivated by a particular application, making it challenging to compare these methods on the same scale. Here we present a solution to this problem that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model. This allows us to compute the description length of a network and its partition under arbitrary objectives, providing a principled measure to compare the performance of different algorithms without the need for "ground truth" labels. Our approach also gives access to instances of the community detection problem that are optimal to any given algorithm, and in this way reveals intrinsic biases in popular descriptive methods, explaining their tendency to overfit. Using our framework, we compare a number of community detection methods on artificial networks, and on a corpus of over 500 structurally diverse empirical networks. We find that more expressive community detection methods exhibit consistently superior compression performance on structured data instances, without having degraded performance on a minority of situations where more specialized algorithms perform optimally. Our results undermine the implications of the "no free lunch" theorem for community detection, both conceptually and in practice, since it is confined to unstructured data instances, unlike relevant community detection problems which are structured by requirement.