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

Nafiseh Ghoroghchian, Gautam Dasarathy, Stark C. DraperAISTATS 2021

Abstract

This work introduces a mathematical framework for detecting communities in graphs when only aggregated or "coarse" measurements of nodes are observable. We define the Coarsened Weighted Stochastic Block Model and provide the first theoretical conditions and error bounds for perfectly recovering community structures from these low-resolution summaries.

Introduction: The Challenge of Coarse Observations

In traditional community detection, researchers typically assume full visibility of every node and edge in a "high-resolution" graph. However, real-world constraints—such as brain imaging (EEG/ECoG), massive social networks, or memory-limited data storage—often restrict access to only "coarse" measurements.

Consider the task of identifying social circles in a city where individual friendships are hidden, but the total volume of connections between apartment buildings is known. Each "coarse node" (c-node) represents a bundle of "fine nodes." This coarsening process blurs community boundaries and introduces edge weights based on the aggregate connectivity between these bundles. The fundamental question addressed here is whether original community structures can be recovered from these blurred, weighted, and potentially overlapping summaries.

Methodology

The authors extend the standard Stochastic Block Model (SBM) to account for coarsening through a three-stage process:

  1. Mathematical Modeling of Coarsening: The measurement process is formalized using a matrix that aggregates fine nodes into c-nodes. The study focuses on "r-homogeneous" measurements (each c-node contains $r$ fine nodes) and "balanced" measurements (c-nodes sample equally from overlapping communities).
  2. The Weighted Overlapping SBM: Coarsening transforms an unweighted graph into a Weighted Overlapping SBM. Since a single c-node can contain members from multiple communities, they exhibit "mixed memberships."
  3. Two-Stage Recovery Strategy:
    • Stage 1 (Binarization): To simplify the problem, weighted edges in the coarse graph are thresholded, converting it back into an unweighted graph where only significant connections remain.
  4. Stage 2 (Extended Communities): Overlapping c-nodes are mapped to "extended communities" (e.g., a c-node overlapping Communities A and B belongs to meta-community {A, B}). This allows the application of classic SBM recovery tools, such as Maximum A Posteriori (MAP) estimators.
The coarsening process from a high-resolution graph to a low-resolution graph and subsequent community recovery.

Key Results and Insights

The theoretical analysis reveals that coarsening is not merely a source of information loss; the resulting edge weights in the coarse graph carry vital statistical information about underlying community densities.

  • Theoretical Bounds and Recovery Conditions: The authors derived a closed-form upper bound on the failure probability of the MAP estimator. They identified a "phase transition" for recovery, showing that as the number of measurements ($m$) and the coverage size ($r$) increase, the error probability asymptotically drops to zero.
  • Performance Comparison: Numerical simulations on synthetic graphs (up to $n=30,000$ nodes) demonstrate that the theoretical bound becomes very tight as resolution increases. In high-resolution regimes, this approach outperforms general-purpose algorithms like BigClam or SLPA, which are not optimized for the specific structure of coarsened data.
Recovery error versus measurement size ($m$), comparing the theoretical bound with state-of-the-art algorithms.

Discussion and Future Directions

While this framework provides a rigorous foundation for coarse community recovery, it currently relies on strict assumptions of "homogeneous" and "balanced" measurements. Future work will focus on:

  • Relaxing Assumptions: Adapting the model for noisy or unbalanced measurements.
  • Utilizing Full Weight Distributions: Moving beyond simple binarization to use the full "Poisson Binomial" distribution of edge weights for potentially more efficient recovery.
  • Parameter Estimation: Developing methods to estimate the number of communities ($K$) and connection probabilities directly from coarse data.

This research marks a significant step toward understanding how community structures persist across different scales of observation, providing tools for analysis in data-constrained environments.

Summary updated

BibTeX
@inproceedings{ghoroghchian2021graph,
  author = {Nafiseh Ghoroghchian and Gautam Dasarathy and Stark C. Draper},
  title = {{Graph Community Detection from Coarse Measurements: Recovery Conditions for the Coarsened Weighted Stochastic Block Model}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
}
Figure