Recovering Communities in Structured Random Graphs

Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska · 2026

Read Recovering Communities in Structured Random Graphs by Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-16910.txt.

Introduction

Michael Kapralov, Luca Trevisan, and Weronika Wrzos-Kaminska hunt hidden crowds in chance graphs. Some graphs are built with crowds sewn in by chance. Links in a crowd come oft, links across crowds come rare. The task is to find those crowds from the graph. Their 2026 preprint works on graphs with extra shape built in.

That shape can help or hide the crowd hunt. The team gives ways to find crowds in such graphs. Crowd hunts serve fraud, bio, and social net work. Firm proofs on chance graphs guide real-world hunts. They show when crowds can be found at all.

Catalog record

CREATORMichael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-16910

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Recovering Communities in Structured Random Graphs Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska 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 d -dimensional hypercube graph admits d 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 ∈ ( 0 , 1 ) 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 p=C\log d/d for a sufficiently large constant C C is 1 / poly ​ ( d ) 1/\text{poly}(d) -close to a coordinate cut with high probability. This is asymptotically optimal and allows approximate recovery of all d 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. 1 Introduction Graph clustering, or community detection, is a fundamental problem in data analysis. The input is a graph G=(V,E) , where a subset C\subseteq V of vertices is considered a ‘community’ if it is sparsely connected to the rest of the graph and is reasonably well-connected as an induced subgraph. The task is to recover the communities. Graph clustering with a planted solution has received a lot of attention in the literature. In this setting the vertex set V of the graph G is assumed to be partitioned into vertex disjoint clusters C_{1},C_{2},\ldots,C_{k} such that the clusters induce well-connected subgraphs and are sparsely connected to the rest of the graph [ 26 , 18 , 31 , 33 , 34 , 12 , 2 , 17 , 15 , 25 ] . For example, in the stochastic block model (SBM; [ 5 ] ) edges of G are generated independently, where an edge \{u,v\} is included in the graph with higher probability if u and v belong to the same cluster, and lower probability otherwise. A large body of work on the stochastic block model shows that, if the edge probabilities satisfy a separation condition, the communities C_{1},C_{2},\ldots,C_{k} can be recovered from a sample graph with high probability. Determining the exact recovery threshold is a fascinating information theoretic problem for which tight bounds have been obtained over the past two decades [ 16 , 32 , 37 , 14 , 34 , 2 , 4 ] . Most of the work on SBM has focused on the case of non-overlapping communities, with only a few works allowing for some overlap. At the same time, in the practice of graph clustering one typically does not expects to have very pronounced cluster. Instead, several clusterings of the vertex set may be consistent with the edge set of the graph. Our central question in this paper is: Can highly overlapping clusterings be recovered from a sample of the underlying graph? Perhaps the most basic example of a graph with a large number of overlapping communities is the hypercube graph on n=2^{d} vertices, where each of d coordinate cuts is a sparsest cut, and defines a partition of the vertex set into two ‘communities’, namely the two corresponding coordinate halfspaces. This setting is very different from the SBM with two communities, where the expected graph is a union of two cliques on the two clusters and a clique on the entire vertex set, and therefore the two communities are uniquely defined. Formally, the main question we ask in this paper is a structured version of the stochastic block model that allows for many communities with large overlaps: Can coordinate cuts be recovered from the edge set of a subsampled hypercube? A priori it would seem plausible that cuts of sparsity comparable to the coordinate cuts may emerge in a subsampled hypercube. Intuitively, this could be a mixture of several coordinate cuts in the original cube (a similar effect is seen in rounding the SDP solution to the sparsest cut problem on the hypercube). However, we show that this is not the case: Theorem 1 . Let Q_{d} be the d -dimensional hypercube, and let Q^{\prime}_{d} be obtained by including each edge with probability p\geq C\cdot\log d/d , where C is a sufficiently large constant. There exists an algorithm with running time 2^{O(n\log n)} that, given Q^{\prime}_{d} , recovers d orthogonal balanced cuts, each with Hamming distance O(2^{d}/\mathrm{poly}(d)) to a coordinate cut, with probability at least 1-d^{-100} over the subsampling. We say that a cut A\subseteq V is balanced if |A|=|V|/2 . The Hamming distance between two sets A,B\subseteq V is given by |A\triangle B| , and we say A and B are orthogonal cuts if |A\triangle B|=|V|/2 . We also remind the reader of the definition of the d -dimensional hypercube graph: Definition 2 (Hypercube) . Define the d -dimensional hypercube to be the graph Q_{d}=(V,E) with vertex set V=\{0,1\}^{d} , and any two vertices are connected by an edge if their Hamming distance is exactly 1 . We let n\coloneqq|V|=2^{d} denote the number of vertices. We note that the subsampling rate in Theorem 1 is such that the expected degree of a vertex is at least C\log d=C\log\log n , i.e. Theorem 1 allows for an exponential reduction of the average degree after sampling. The guarantee in Theorem 1 is tight up to \mathrm{poly}\left(d\right) factors, since the expected number of isolated vertices in Q^{\prime}_{d} is at least 2^{d}/\mathrm{poly}\left(d\right) . To see this, note that the degree of each vertex in Q^{\prime}_{d} is distributed as \mathrm{Bin}(d,p) . For p=C\log d/d , the probability that a given vertex is isolated is (1-p)^{d}=\left(1-\frac{C\log d}{d}\right)^{d}\;\geq\;e^{-C\log d}\left(1-\tfrac{(C\log d)^{2}}{d}\right)=\frac{1}{\mathrm{poly}\left(d\right)}. So in expectation, at least 2^{d}/\mathrm{poly}(d) vertices are isolated, and we cannot hope to classify those vertices. Exact recovery. Furthermore, we show that, similarly to SBM, exact recovery is possible for a sufficiently high degree sample, specifically, a sample where every vertex has expected degree at least C\log n,n=2^{d}, for a sufficiently large constant C>0 . The hypercube itself is not a good model to study this setting, as the degree in the hypercube itself is d=\log_{2}n . We therefore study the k -distance hypercube, defined below: Definition 3 ( k -distance hypercube) . Define the k -distance hypercube to be the graph Q_{d,k}=(V,E) with vertex set V=\{0,1\}^{d} , and any two vertices are connected by an edge if their

Read the complete text