Recovering Communities in Structured Random Graphs

Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska

This academic paper, "Recovering Communities in Structured Random Graphs," by Michael Kapralov, Luca Trevisan, and Weronika Wrzos-Kaminska, explores a challenging frontier in network science: identifying communities that aren't just hidden, but are also heavily overlapping. By using the $d$-dimensional hypercube as a mathematical "stress test," the authors prove that we can recover complex, overlapping structures even when the vast majority of the graph's edges are missing.

TL;DR

The authors demonstrate that it is possible to recover the "coordinate cuts" of a hypercube from a heavily subsampled version of the graph. This moves beyond the standard Stochastic Block Model (SBM) by showing that community detection is possible even when communities overlap significantly, provided the underlying graph has a strong enough combinatorial structure.

What Problem Does This Paper Address?

Most research on community detection focuses on the Stochastic Block Model (SBM), where a graph is partitioned into disjoint (non-overlapping) clusters. In the SBM, edges are more likely to exist within a cluster than between them. However, real-world networks—like social circles or protein-interaction maps—often feature "communities" that overlap. A person might belong to a "work" community and a "hobby" community simultaneously.

The authors tackle a fundamental question: Can we recover communities if they overlap significantly?

To study this, they use the $d$-dimensional hypercube. A hypercube has $d$ different "coordinate cuts" (splitting the cube in half along any of its $d$ axes). These cuts are the sparsest possible ways to divide the graph, but they overlap extensively. The paper asks if these $d$ axes can be identified if we are only given a random sample of the hypercube's edges (a "subsampled" hypercube).

Methods

The paper is primarily theoretical, providing a mathematical proof of recoverability and an algorithm to achieve it.

  1. The Optimization Problem: The authors propose an algorithm that finds $d$ balanced, orthogonal cuts by minimizing the total number of edges crossing those cuts in the subsampled graph.
  2. Fourier Analysis of Boolean Functions: The core of the proof relies on the Friedgut–Kalai–Naor (FKN) theorem. This theorem states that if a boolean function (representing a cut) has its "Fourier mass" concentrated on its first-level coefficients, it must be very close to a coordinate cut.
  3. Karger’s Cut Counting: To handle the randomness of the subsampling, the authors use Karger’s famous argument to show that "weird" or "non-coordinate" cuts are unlikely to accidentally become sparse enough to fool the algorithm.
  4. Algorithm Complexity: The proposed algorithm uses direct enumeration (exhaustive search) to solve the optimization, resulting in a running time of $2^{O(n \log n)}$, where $n$ is the number of vertices.

Datasets

As a theoretical computer science paper, it does not use empirical real-world datasets. Instead, it defines and analyzes two specific graph models:

  • The $d$-dimensional Hypercube ($Q_d$): A graph with $2^d$ vertices where edges connect points differing by exactly one bit.
  • The $k$-distance Hypercube ($Q_{d,k}$): A variation where edges connect vertices at a Hamming distance of exactly $k$. This model is used to demonstrate "exact" recovery.

Key Insights and Ideas

  • Structure Trumps Sparsity: Even when a hypercube is subsampled so heavily that vertices have only a logarithmic number of edges (near the threshold of the graph becoming disconnected), the "ghost" of the original coordinate structure remains the most efficient way to partition the graph.
  • Simultaneous Recovery: The authors show you don't just find one cut; you can find all $d$ orthogonal dimensions at once.
  • Bridging Fields: The paper elegantly connects spectral graph theory (Laplacians and eigenvalues) with the analysis of boolean functions (Fourier transforms), showing that the "sparsest cut" problem in these graphs is deeply tied to the bit-structure of the vertices.

Key Results

  • Approximate Recovery: For a hypercube $Q_d$ subsampled at a rate $p \approx \log d / d$, the algorithm finds $d$ cuts that are $1/\text{poly}(d)$-close to the true coordinate cuts with high probability. This rate is asymptotically optimal.
  • Exact Recovery: In the $k$-distance hypercube model, the authors prove that exact recovery of the coordinate cuts is possible.
  • Tight Bounds: The authors show their sampling rate is nearly as low as it can possibly go; any lower, and the graph would have so many isolated vertices that recovery would be impossible.

Limitations and Future Work

  • Computational Efficiency: The current algorithm is exponential in time. While it proves what is possible to recover, it isn't practical for massive networks. The authors suggest that the Sum-of-Squares (SoS) hierarchy might be a path toward a polynomial-time algorithm for this problem.
  • Model Specificity: The results are highly tailored to the rigid, symmetric structure of the hypercube. A major open question is how these techniques might translate to more "organic" or less structured graphs that still exhibit high overlap.
  • Exact vs. Approximate: While exact recovery is achieved for $k$-distance graphs, for the standard hypercube, the recovery remains "approximate" due to the presence of isolated vertices at the critical sampling threshold.

Summary updated

Abstract

The problem of recovering planted community structure in random graphs has received a lot of attention in the literature on the stochastic block model, where the input is a random graph in which edges crossing between different communities appear with smaller probability than edges induced by communities. The communities themselves form a collection of vertex-disjoint sparse cuts in the expected graph, and can be recovered, often exactly, from a sample as long as a separation condition on the intra- and inter-community edge probabilities is satisfied. In this paper, we ask whether the presence of a large number of overlapping sparsest cuts in the expected graph still allows recovery. For example, the $d$-dimensional hypercube graph admits $d$ distinct (balanced) sparsest cuts, one for every coordinate. Can these cuts be identified given a random sample of the edges of the hypercube where each edge is present independently with some probability $p\in (0, 1)$? We show that this is the case, in a very strong sense: the sparsest balanced cut in a sample of the hypercube at rate $p=C\log d/d$ for a sufficiently large constant $C$ is $1/\text{poly}(d)$-close to a coordinate cut with high probability. This is asymptotically optimal and allows approximate recovery of all $d$ cuts simultaneously. Furthermore, for an appropriate sample of hypercube-like graphs recovery can be made exact. The proof is essentially a strong hypercube cut sparsification bound that combines a theorem of Friedgut, Kalai and Naor on boolean functions whose Fourier transform concentrates on the first level of the Fourier spectrum with Karger's cut counting argument.
BibTeX
@inproceedings{kapralov2026recovering,
  author = {Michael Kapralov and Luca Trevisan and Weronika Wrzos-Kaminska},
  title = {{Recovering Communities in Structured Random Graphs}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.85},
}
Figure