Source-linked AI summary
Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
Peter Chin, Anup Rao, Van Vu
TL;DR
The paper asks how accurately communities can be recovered in sparse stochastic block models, including the unresolved partial-recovery problem in the censor block model. It develops a simple, robust spectral algorithm for any fixed number of blocks and shows high-probability γ-correct recovery under stated signal conditions. The method also applies beyond constant-density graphs and to blocks of comparable, unequal sizes.
Problem
The paper studies how to identify blocks as correctly as possible in sparse stochastic block models, including partial recovery in the censor block model.
Method
The paper designs a fast, robust spectral algorithm for two blocks and refines it to handle any fixed number of blocks.
Results
A γ-correct partition is recovered with probability 1−o(1) under the stated signal condition for two blocks and for any fixed k.
Takeaways & Limitations
The method is claimed to be sharp up to constants, applies to comparable unequal block sizes and denser graphs, and addresses partial recovery in the censor block model.
Takeaways & Limitations
The main guarantees assume a fixed number of blocks; unequal block sizes are covered only when their sizes are comparable, with constants depending on the size ratio.
Abstract
from arXiv · showhide
In this paper, we present and analyze a simple and robust spectral algorithm for the stochastic block model with $k$ blocks, for any $k$ fixed. Our algorithm works with graphs having constant edge density, under an optimal condition on the gap between the density inside a block and the density between the blocks. As a co-product, we settle an open question posed by Abbe et. al. concerning censor block models.
1 Introduction
The paper studies partial community recovery in sparse stochastic block models, seeking simple spectral algorithms under sharp conditions on within- versus between-block connectivity. It extends the approach to any fixed number of blocks and applies it to the censor block model.
- Motivation: Sparse stochastic block models require partial rather than complete recovery because a linear portion of vertices can be isolated.The goal is to recover a large portion of each block through a γ-correct partition.
- Motivation: The paper’s main goal is to determine the optimal relation between recovery accuracy γ and the signal ratio (a−b)^2/(a+b).Earlier polynomial-time recovery required an additional logarithmic factor, which had been conjectured removable.
- Two blocks: A simple spectral algorithm finds a γ-correct partition with probability 1−o(1) under the paper’s stated condition for a>b>C0.The constants in the condition are explicit in principle, although the paper does not optimize them.
- Censor block model: In the censor block model, the spectral method gives partial recovery when np is at least a constant multiple of (1−2ϵ)^2 and p is at least a constant over n.This addresses the partial-recovery question left open by prior work on sparse graphs.
2 Two communitites
For two communities, the algorithm first uses a truncated spectral partition and then corrects mislabeled vertices using independently sampled edges. Under the stated separation condition, it achieves a γ-correct partition with high probability.
- Spectral Partition: The spectral algorithm truncates vertices with degree above 20d, computes the top two eigenspace, and partitions vertices by the second eigenvector.Here d := a+b is supplied as an input for exposition, although it can be estimated efficiently from the adjacency matrix.
- Spectral Partition: The truncation reduces the perturbation norm, enabling Davis–Kahan control of the angle between the ideal and observed second eigenspaces.The analysis states that the relevant perturbation becomes significantly smaller after auxiliary deletion.
- Spectral Partition: Theorem 2.1 states that for a > b > C0 and the stated condition involving γ and (a−b)^2, Spectral Partition outputs a γ-correct partition with probability 1−o(1).The result is established for fixed constants satisfying the theorem’s separation requirement.
- Correction: Correction uses degree-based thresholding to reclassify mislabeled vertices and achieves the optimal logarithmic dependence between γ and (a−b)^2/(a+b).Large-deviation bounds provide the exponential error probability needed for this dependence.
- Correction: The correction step uses a random edge split so that one half supports spectral partitioning and the other half supports correction.The split does not make the stages completely independent, but the paper states that it suffices to prove the result.
- Experiment: For an input with n=7500, a=10, and b=3, the paper reports a density plot before and after clustering and runtime below 3 seconds in Matlab on a 2009 MacPro.The comparison is between the unclustered input matrix and the permuted matrix after the algorithm runs.
3 First step: Proof of Theorem 2.1
The proof first bounds the distance between the empirical and ideal top eigenspaces, then converts this subspace control into an approximate partition and improves it through correction. The key spectral bound follows from controlling deletion and random-matrix errors.
- Proof strategy: The proof has two steps: bound the angle between the empirical and ideal eigenspaces, then recover and improve an approximate partition.The first step controls subspace proximity; the second translates that proximity into vertex recovery.
- Bounding the angle: After deletion, the adjacency matrix decomposes into the ideal matrix plus deletion and random-matrix error terms whose norms are bounded with probability 1−o(1).The deletion term is controlled through high-degree vertices, while the random term requires a separate matrix-norm lemma.
- Bounding the angle: A random symmetric matrix with entries bounded by σ² has, after zeroing high-positive-degree rows and columns, operator norm at most Cσ√n with probability 1−o(1).This lemma supplies the central bound for the random error matrix.
- Bounding the angle: If a−b is sufficiently large relative to d=a+b and a is sufficiently large, the empirical and ideal two-dimensional eigenspaces have angle at most any fixed c<1 with probability 1−o(1).The result follows by applying the Davis–Kahan bound to the combined error and the second-eigenvalue gap.
- Recovering the partition: When the eigenspace angle is below 1/16, the method recovers an 8c/3-correct partition.This provides the approximate partition needed before the correction stage.
4 Multiple communities
For fixed k, the algorithm uses random edge splitting and spectral partitioning to recover coarse community information, then corrects and merges labels. The correction and merge steps yield γ-correct partitions under the paper’s stated conditions.
- 4 Multiple communities: Randomly splitting edges provides independent graphs for the algorithm’s successive steps.The procedure colors edges red and blue with equal probability so different stages use independent edge sets.
- 4 Multiple communities: Step 1 applies a spectral algorithm to part of the adjacency matrix and recovers a large portion of each block.The recovered subsets are denoted Z ∩ V1, ..., Z ∩ Vk.
- 4 Multiple communities: For any fixed k, the paper states constants C1 and C2 under which the multi-community procedure satisfies its recovery theorem.The correction and merge lemmas are combined to obtain the stated result.
- 4.2 Details: Step 2 uses degree information to correct mislabeled vertices and achieves logarithmic dependence between γ and (a−b)^2/(a+b).A mislabeled vertex is reclassified by comparing its red-neighbor counts across the estimated communities.
- 4.2 Details: Step 3 merges the clustering information from Z with labels for Y using the Merge sub-routine.The analysis treats this step through a separate lemma for the blue graph over Y ∪ Z.
5 Censor Block Model
The censor block model is formulated with hidden binary labels, a random graph, and edge-dependent noise. The proposed procedure trims high-degree vertices, extracts a two-dimensional eigenspace, constructs a separating vector, and outputs two ranked vertex sets.
- 5 Censor Block Model: The model has 2n vertices, exactly n labeled 1 and n labeled 0, with an Erdős–Rényi graph generated at edge probability p.These assumptions define the hidden bipartition setting used for the analysis.
- 5 Censor Block Model: Observed edge information is noisy: an edge reveals xi ⊕ xj with probability p(1−ϵ), its flipped value with probability pϵ, and zero otherwise.The noise variables are Bernoulli(ϵ), producing the stated three-way observation distribution.
- 5 Censor Block Model: The algorithm zeroes rows and columns for vertices with degree above 20pn before computing the top-two eigenspace.This produces the trimmed matrix Y0 and eigenspace U.
- 5 Censor Block Model: It projects the all-ones vector onto U, then chooses a unit vector in the relevant subspace perpendicular to that projection.The resulting vectors are v1 and v2, respectively.
- 5 Censor Block Model: The output consists of two vertex sets formed by sorting vertices according to their values in v2.The first set contains the top n vertices, and the second is the complementary set.
A Two communities
The appendix develops probabilistic bounds for sparse random matrices and graph substructures underlying the two-community spectral analysis. It combines truncation, net arguments, concentration inequalities, and union bounds to control matrix norms and degrees.
- A Two communities: A standard random-graph argument bounds the probability that a linear-size vertex set has all degrees above a large threshold.The proof reduces this event to unusually many internal or crossing edges and applies Chernoff bounds.
- A Two communities: The random-matrix lemma states that, with probability 1−o(1), a centered symmetric matrix has operator norm at most C2σ√n.The entries are independent above the diagonal and their probabilities are bounded by σ^2.
- A Two communities: The norm proof uses an ε-net of the unit sphere and separates light and heavy coordinate pairs.Bernstein bounds control light pairs, while graph discrepancy and degree properties control heavy pairs.
- A Two communities: The appendix verifies the required degree and discrepancy properties with probability 1−o(1) using Chernoff bounds and union bounds.These properties are then used in the heavy-pair portion of the matrix norm argument.
- A Two communities: After zeroing rows and columns with too many positive entries, the truncated matrix retains an O(σ√n) norm bound with high probability.The proof applies a union bound over possible zeroed row and column sets.
A.2 Recovery
The recovery argument converts an approximate eigenspace direction into a partition by thresholding vector coordinates. A sufficiently small angle from the ideal community vector guarantees recovery of a large fraction of vertices.
- A.2 Recovery: Once the angle condition holds, recovery reduces to identifying a vector in the estimated subspace close to the ideal community vector.The appendix constructs such a vector through orthogonal projections.
- A.2 Recovery: If sin(∠v, v̄2) ≤ 2√c, the estimated vector is quantitatively close to the ideal direction.The bound follows from projecting the ideal basis vectors into the estimated subspace.
- A.2 Recovery: For any constant c<1, the analysis can choose constants so that sin(∠v̄2,v)≤c with probability 1−o(1).This is the probabilistic angle guarantee used before thresholding.
- A.2 Recovery: Thresholding the signs of the approximate eigenvector identifies at least a (1−4c^2/(1−c^2)) fraction of vertices from each block when c≤0.5.The coordinate error bound limits how many vertices can receive the wrong sign.
A.3 Proof of lemma 2.3
The proof establishes a polynomial-time spectral procedure that finds a γ-correct partition with high probability under a logarithmic signal condition, while recovery is impossible below the corresponding threshold.
- The proof uses Red edges for an initial partition, Blue-edge degree comparisons for correction, and Chernoff bounds to control errors.The analysis conditions on bounded Red degrees and tolerates imperfect splittings with only an o(1) error term.
- The resulting correctness parameter is bounded through an exponential expression, yielding the constant 13.89 log^2 for the analyzed partition quality.Improving the initial .1-correct partition can reduce 13.89 toward any constant larger than 8.
B.1 Proof of theorem 4.1
The theorem’s proof combines spectral subspace approximation with projected coordinates and Blue-edge counts to recover block-aligned vertex sets under a signal-to-noise condition.
- The analysis considers a stochastic block model with fixed k blocks, each of size n/k.
- The expected matrix has rank k and least non-trivial singular value proportional to a−b, providing the spectral separation used by the algorithm.
- If (a−b) > C1k^2√a and a > b ≥ C2, the estimated and expected eigenspaces have small principal angle with probability 1−o(1).
- At least m/2 sampled error vectors are good with probability 1−o(1), enabling approximate recovery of the block-specific coordinates.
- For every good index, the constructed set contains 95% of the corresponding block vertices, while selecting the least Blue-edge-density sets leaves 90% block purity.
- Chernoff-based Blue-edge counts distinguish sets concentrated in one block from sets spread across blocks with exponentially high probability.
B.2 Proof of lemma 4.2
This proof bounds the correction errors for an initially γ-correct partition by applying large-deviation estimates to within- and between-block edge counts.
- The proof begins from a γ-correct partition produced by Spectral Partition with probability 1−o(1) under (a−b)^2/(a+b) ≥ C.
- For vertices in each block, misclassification is reduced to low-probability deviations in their edge-count statistics.
- Chernoff bounds and a union bound show that the corrected partition has only a controlled number of mislabeled vertices with probability 1−o(1).
- The resulting γ parameter satisfies γ ≤ 25 log^2 k/[k(a+b)].
B.3 Proof of lemma 4.3
The merge proof labels vertices using Blue-edge degrees to an already corrected partition, then bounds the resulting errors with Chernoff concentration and spectral noise control.
- The procedure merges block portions in Y and Z using Blue edges between the two vertex sets.
- Vertices in Y are labeled according to their degrees to the corrected sets U′1,…,U′k.
- Chernoff estimates bound the probability of misleading degree events and thereby control the number of mislabeled vertices in Y.
- With probability 1−o(1), the merged partition is γ-correct with γ ≤ 31 log^2 k/[k(a+b)].
- The spectral analysis requires sufficiently large signal so the top-two eigenspace of the expected matrix is well separated.
D Proof of Lemma A.2
The proof follows the argument in, introducing auxiliary notation and partitioning the analysis into cases and subcases. It derives bounds on λi,j and σi,jαi using degree constraints, parameter inequalities, and a geometric-sum calculation.
- The proof begins by defining sets and auxiliary quantities, including γk := 2k and αi := si.
- A degree bound yields λi,j ≤ c1n/tj when the maximum degree is at most c1d.
- The argument separates cases according to inequalities involving log λi,j, log γj, and log(1/βj), then analyzes additional subcases.
- The final estimates use that a displayed sum is geometric, together with relations involving γi and γj.
- Outside the earlier cases, the proof assumes log λi,j ≥ 1 and obtains an upper bound on σi,jαi.