# Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 53 references that are in the map.
- First posted on arXiv 25 Feb 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Graph Coarsening with Preserved Spectral Properties](https://mlsanity.com/paper/1802.04447/) (2018)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Learning Latent Block Structure in Weighted Networks](https://mlsanity.com/paper/1404.0431/) (2014)
- [The physics of brain network structure, function, and control](https://mlsanity.com/paper/1809.06441/) (2018)
- [Multi-scale brain networks](https://mlsanity.com/paper/1608.08828/) (2016)
- [On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations](https://mlsanity.com/paper/1607.00084/) (2016)
- [Information-theoretic bounds for exact recovery in weighted stochastic block models using the Renyi divergence](https://mlsanity.com/paper/1509.06418/) (2015)
- [Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms](https://mlsanity.com/paper/1503.00609/) (2015)
- [Node-Centric Graph Learning from Data for Brain State Identification](https://mlsanity.com/paper/2011.02179/) (2020)
- [A Hierarchical Graph Signal Processing Approach to Inference from Spatiotemporal Signals](https://mlsanity.com/paper/2010.13164/) (2020)
- [Scalable and Robust Community Detection with Randomized Sketching](https://mlsanity.com/paper/1805.10927/) (2018)

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

- [Learning the Structure of Large Networked Systems Obeying Conservation Laws](https://mlsanity.com/paper/2206.07083/) (2022)
- [Controllability of Coarsely Measured Networked Linear Dynamical Systems (Extended Version)](https://mlsanity.com/paper/2206.10569/) (2022)

## Abstract (arXiv)

We study the problem of community recovery from coarse measurements of a graph. In contrast to the problem of community recovery of a fully observed graph, one often encounters situations when measurements of a graph are made at low-resolution, each measurement integrating across multiple graph nodes. Such low-resolution measurements effectively induce a coarse graph with its own communities. Our objective is to develop conditions on the graph structure, the quantity, and properties of measurements, under which we can recover the community organization in this coarse graph. In this paper, we build on the stochastic block model by mathematically formalizing the coarsening process, and characterizing its impact on the community members and connections. Through this novel setup and modeling, we characterize an error bound for community recovery. The error bound yields simple and closed-form asymptotic conditions to achieve the perfect recovery of the coarse graph communities.