PaperlayerView exact revision on arXiv

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

arXiv:1501.05021v2cs.DS

TL;DR

The paper studies community recovery in stochastic block models and the open question of partial recovery for sparse censor block models. It analyzes a spectral algorithm and proves that, under the theorem’s conditions, it finds a γ-correct partition with probability 1 − o(1).

  • Problem

    The paper asks how accurately communities can be identified in stochastic block graphs and addresses the open question of partial recovery for sparse censor block models.

    Source: §1 · pp. 1, 3

  • Method

    The paper analyzes a fast, robust spectral algorithm for approximate partition recovery.

    Source: §1 · p. 2

  • Results

    With probability 1 − o(1), a simple spectral algorithm finds a γ-correct partition under Theorem 1.3’s conditions.

    Source: §1 · p. 2

  • Takeaways & Limitations

    It settles the open question from [ABBS14] of partial recovery for sparse censor block models.

    Source: §1 · p. 3

    For unequal blocks, the stated extension assumes comparable sizes, with theorem constants depending on the size ratio.

    Source: §1 · p. 3

Abstract

from arXiv · show

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 presents a simple spectral algorithm for partial recovery in sparse stochastic block models, extending to any fixed number of blocks. It also applies the method to partial recovery in the Censor Block Model.

1 Introduction

  • In the sparse two-block setting, isolated vertices occur in a linear portion of the graph, ruling out complete recovery and motivating recovery of a large portion of each block.The paper defines γ-correctness by requiring at least (1−γ)n correctly recovered vertices from each block.Source: §1 · pp. 1–2
  • A prior polynomial-time result guarantees a γ-correct partition for sufficiently large a, b under a condition involving a+b and log(a+b), but the authors say its log term may be removable and its accuracy threshold remains unresolved.They describe that earlier algorithm as involved.Source: §1 · p. 2
  • For two blocks, a simple spectral algorithm finds a γ-correct partition with probability 1 − o(1) under the paper’s stated condition on a, b, and γ.The authors identify the optimal relation between recovery accuracy and the density gap as a main goal; the condition itself is not fully present in the supplied passage.Source: §1 · p. 2
  • For any fixed k, the authors give a simple spectral algorithm that finds a γ-correct partition with probability at least 1 − o(1).They believe the result is sharp up to constants, and say the method also works for comparable unequal block sizes and denser graphs.Source: §1 · p. 3
  • For the Censor Block Model, a simple spectral algorithm finds a γ-correct partition with probability 1 − o(1) when np ≥ C1(1−2ϵ)^2 and p ≥ C2/n.This addresses the partial-recovery question for sparse graphs posed after prior work on exact recovery and a semidefinite algorithm.Source: §1 · p. 3

2 Two communitites

For two communities, the section presents a spectral partitioning method that trims high-degree vertices, then corrects mislabeled vertices using degree information and a split of the edges. Under the stated parameter condition, it proves recovery guarantees and illustrates the clustering result with density plots.

Two communitites

  • The procedure zeros rows and columns of A0 for vertices with degree greater than 20d, producing A; the resulting noise matrix E has norm significantly smaller than E0.The perturbation Δ is only O(1) with probability 1−o(1).Source: §2 · pp. 4–5
  • The correction step uses degree-based neighbor counts to reclassify mislabeled vertices, and splits edges so correction uses edges not used for the initial partition.Large deviations let the method detect a majority of mislabeled vertices; the split addresses the dependence between the initial labels and their neighbors.Source: §2 · pp. 5–6
  • Figure 4 contrasts input and post-clustering density plots for n=7500, a=10, b=3; the run took less than 3 seconds in Matlab.Source: §2 · p. 6, Figure 4 · p. 6
  • Starting from a 0.1-correct partition, Correction produces a γ-correct partition with γ given by an exponential bound.The supplied bound begins γ = 2 exp(−0.072(a−b)^2, but its remaining terms are truncated.Source: §2 · p. 6

3 First step: Proof of Theorem 2.1

The proof has two steps: bound the angle between the leading two-dimensional eigenspaces of A and the corresponding space of Ā, then use a sufficiently close subspace to recover and improve an approximate partition.

3 First step: Proof of Theorem 2.1

  • The proof is organized around bounding the angle between the leading two-dimensional eigenspaces and recovering a partition from a sufficiently close subspace.It defines the subspace angle as the norm of the difference between the corresponding orthogonal projection operators.Source: §3 · pp. 6–7

3.1 Bounding the angle

  • The proof first bounds the eigenspace angle: a matrix-norm bound and the Davis–Kahan bound yield sin ∠(W, W̄) ≤ c < 1 with probability 1 − o(1).The key random-matrix lemma bounds the norm of a matrix after zeroing rows and columns with more than 20σ²n positive entries by Cσ√n with probability 1 − o(1).Source: §3.1 · p. 7

3.2 Recovery

  • If sin ∠(W, W̄) ≤ c < 1/16, the recovery step obtains an 8c/3-correct partition and then uses Blue edges in a correction routine to improve it.The correction routine outputs a γ-correction partition; the supplied passage does not provide a complete expression for γ.Source: §3.2 · p. 8

4 Multiple communities

For k > 2, the algorithm randomly splits edges to obtain independent data for partitioning and correction. It first spectrally partitions part of the graph, corrects labels using degrees, and then extends labels to Y.

4.1 Overview

  • Randomly coloring edges Red or Blue with equal probability gives the algorithm independent edge sets for its successive steps.For k > 2, the extra random split supports recovering the partitions when approximating the space spanned by the first k eigenvectors.Source: §4.1 · p. 8

4.2 Details

  • Step 1 applies a spectral algorithm to part of the adjacency matrix to recover a large portion of each block in Z.The algorithm approximates the space spanned by the first k eigenvectors rather than directly approximating the eigenvectors themselves.Source: §4.2 · p. 8, §4.1 · p. 8
  • Step 2 uses the degree sequence to identify and reclassify mislabeled vertices in Z, yielding optimal logarithmic dependence between γ and (a−b)^2/(a+b).It thresholds Red-neighbor counts in the provisional clusters.Source: §4.2 · p. 9
  • Correction on Red edges over Z and Merge on Blue edges over Y ∪ Z each produce a γ-correct partition from a 0.1-correct partition of Z.Combining these lemmas yields the stated result.Source: §4.2 · pp. 9–10
  • Step 3 uses clustering information from Z to label vertices in Y, using the Blue graph over Y ∪ Z.This extension is performed by the Merge subroutine.Source: §4.2 · pp. 9–10

5 Censor Block Model · A Two communities

The section models two equally sized communities in a censored Erdős–Rényi graph and describes spectral recovery from the observed adjacency matrix. Its recovery argument uses the rank-two mean matrix and a degree-trimming step.

5 Censor Block Model

  • The model has 2n vertices split evenly between labels 1 and 0, with the Erdős–Rényi setup following [ABBS14].The underlying graph is drawn from G_{2n,p}.Source: §5 · p. 10
  • Each potential edge appears with probability p, and an observed edge is flipped with noise probability ε.The supplied cases assign probabilities p(1−ε) to an unflipped edge, pε to a flipped edge, and 1−p to no edge.Source: §5 · p. 11
  • The algorithm takes the adjacency matrix Y and edge probability p as input, then removes rows and columns for vertices with degree above 20pn.The resulting trimmed matrix is Y0; Figure 10 is captioned as Algorithm 3.Source: §5 · p. 11, Figure 10 · p. 11

A Two communities

  • Writing community disagreement as W, the mean adjacency matrix is Ȳ = pεI + p(1−2ε)W.The entrywise noise terms are mean zero and have variance at most p.Source: §5 · p. 11
  • Ȳ has rank 2, with eigenvalues pn and p(1−2ε)n and corresponding constant and community-sign eigenvectors.The sign vector separates the two communities.Source: §5 · p. 11
  • Algorithm 10, essentially the same as Algorithm 2, recovers the communities when np ≥ C²/(1−2ε)².Recovery follows by finding the community-sign eigenvector of the observed matrix.Source: §5 · p. 11

A.1 Bounding ∥∆∥and ∥E∥ · A.2 Recovery

The appendix bounds the random-matrix terms used in the spectral argument and shows how a sufficiently accurate subspace vector yields block recovery. Under the stated angle condition, the sign-based procedure correctly identifies a large fraction of each block.

A.1 Bounding ∥∆∥and ∥E∥

  • The proof of Lemma 3.1 bounds high degrees by showing that a vertex set with all degrees above 20d must have many internal or crossing edges, then applying a union bound.The passage states the dichotomy as |E(X)| ≥ 2cnd or |E(X, Xc)| ≥ 8cnd.Source: §A.1 · pp. 13–14
  • With probability 1 − o(1), the random symmetric matrix M has norm at most C₂σ√n.The proof uses an ε-net argument, splitting vector-coordinate pairs into light and heavy classes.Source: §A.1 · p. 14
  • With probability 1 − o(1), the graph GA has maximum degree at most 20σ²n.Lemma A.3 also asserts edge-discrepancy conditions for vertex subsets, but their formulas are missing from the supplied passage.Source: §A.1 · p. 15
  • After bounding ∆, the proof turns to bounding ∥E∥ under a > b ≥ C₀.The supplied passages begin describing the within- and between-community cases but do not include the resulting norm bound.Source: §A.1 · pp. 16–17

A.2 Recovery

  • For any constant c < 1, constants can be chosen so a vector v satisfies sin(∠v̄₂, v) ≤ c with probability 1 − o(1).The construction projects v̄₁ onto W, then takes a unit vector in W perpendicular to that projection.Source: §A.2 · p. 17
  • When sin(∠v̄₂, v) < c ≤ 0.5, at least a (1 − 4/3c²) fraction of vertices in each block can be identified correctly.Source: §A.2 · p. 17

A.3 Proof of lemma 2.3 · B Multiple communities

The proof of Lemma 2.3 first partitions the Red graph spectrally, then uses Blue-edge information and Chernoff bounds to analyze a correction step. For multiple communities, the proofs assume perfect splits for simplicity, with only an o(1) error from imperfect splits.

A.3 Proof of lemma 2.3

  • With probability 1−o(1), Spectral Partition on the Red graph produces two sets under the stated density-gap condition.The supplied passage refers to Theorem 2.1 for the condition but does not provide its complete formula.Source: §A.3 · p. 18
  • The proof conditions on the Red partition event and on every vertex having Red degree at most log^2 n, an event that holds with probability 1−o(1).Source: §A.3 · p. 18
  • For non-Red edges, Blue-edge probabilities differ by block relation: 1−b/(2n) across sets and 1−a/(2n) within a set.These probabilities underpin the subsequent vertex-correction analysis.Source: §A.3 · p. 18
  • Chernoff bounds estimate the correction step’s misclassification probabilities, and symmetry extends the resulting estimate to the other set.The supplied passages do not expose the complete numerical bound.Source: §A.3 · pp. 19–20
  • The analysis requires (a−b)^2/(a+b) to exceed a sufficiently large constant; improving the initial partition’s accuracy can lower 13.89 to 8.1 or any larger constant.The passage identifies 8 as the method’s limit.Source: §A.3 · p. 20

B Multiple communities

  • For multiple communities, the proofs assume perfect splits for simplicity; imperfect splits add only an o(1) error, leaving the bounds essentially unchanged.Source: B Multiple communities · p. 20

B.1 Proof of theorem 4.1 · Proof

The proof analyzes spectral recovery for a stochastic block model with a fixed number of equal-size blocks. It establishes subspace and sampled-vector guarantees, then uses Blue-edge densities to distinguish sets concentrated in one block from more mixed sets.

B.1 Proof of theorem 4.1

  • For the equal-size-block model, the proof represents the observed matrix using expected matrices and deleted rows and columns, and bounds the deleted part by controlling high-degree vertices.The model has k blocks of size n/k, with k fixed as n grows.Source: §B.1 · pp. 20–21
  • When (a − b) > C1 k^2 a and a > b ≥ C2, the estimated and expected left-singular-vector subspaces have angle at most c with probability 1 − o(1).The proof considers fixed k as n grows and applies a singular-value bound with Davis–Kahan.Source: §B.1 · pp. 20–21
  • Sampling m = 2 log n columns and projecting them yields at least m/2 good vectors with probability at least 1 − o(1).The proof bounds projection error using the subspace angle and the projected noise, enabling approximate recovery of the vectors used to identify block intersections.Source: §B.1 · pp. 21–22
  • Under the lemma’s stated conditions, each good set U_ij contains 0.95 of the vertices in its corresponding block intersection V_nij ∩ Z.The proof obtains this guarantee by choosing the constants appropriately.Source: §B.1 · p. 22
  • After discarding half the candidate sets, each remaining set intersects some block intersection V_nij ∩ Z in 0.9 of its vertices.The proof first selects sets with the least Blue-edge densities.Source: §B.1 · p. 22
  • For sets X of size n/2k, Lemma B.5 separates block-concentrated from more mixed sets using their induced Blue-edge counts, with failure probability at most e^−cn.The bounds distinguish counts below versus above an −0.09(a − b)n/16k from an/16k.Source: §B.1 · p. 22

Proof

  • Chernoff bounds control both upper and lower deviations of e(X), the number of induced Blue edges, under the stated block-balance condition on X.The proof applies these bounds to assess whether e(X) crosses the specified threshold.Source: Proof · pp. 22–23

B.2 Proof of lemma 4.2

The proof first obtains an initial partition by spectral partitioning the Red graph, then uses the edges within Z and Chernoff bounds to show that correction yields a gamma-correct partition with high probability.

B.2 Proof of lemma 4.2

  • Under the condition in Theorem step1, Spectral Partition on the Red graph produces the initial sets with probability 1-o(1).Source: §B.2 · p. 23
  • Chernoff bounds control correction errors by bounding the probability of the stated failure event and the number of misclassified vertices in each block.Source: §B.2 · pp. 23–24
  • With probability 1-o(1), the corrected sets form a gamma-correct partition, and a union bound extends the guarantee across all blocks.The proof gives a specific bound on gamma.Source: §B.2 · p. 24

B.3 Proof of lemma 4.3

The proof merges Y and Z using Blue edges, classifying vertices in Y by their degrees to an assumed γ-correct partition. It bounds classification errors with Chernoff and union bounds to establish a high-probability γ-correct partition of Y.

B.3 Proof of lemma 4.3

  • The merge routine labels vertices in Y by their Blue-edge degrees to a given γ-correct partition U′ of U1, ..., Uk.The analysis assumes γ ≤ 0.1 and conditions on the event that every vertex has Red degree at most log2 n, which occurs with probability 1 − o(1).Source: §B.3 · p. 24
  • Blue-edge probabilities differ between cross-block and same-block vertex pairs, providing the basis for merging Vi ∩ Y with Vi ∩ Z.The passages specify separate cases for pairs involving Vi ∩ Y and Vj ∩ Z, and for pairs involving Vi ∩ Z; the displayed probability expressions are incomplete.Source: §B.3 · p. 24
  • Chernoff bounds and a union bound yield a high-probability bound on mislabeled vertices in Y and establish a γ-correct partition of Y.The proof defines ρ as the probability that at least one of the misclassification events occurs, then bounds the number of mislabeled vertices using indicator variables.Source: §B.3 · pp. 25–26

C Censor Block Model

The censor-block analysis bounds the perturbation after removing high-degree rows and columns, then relates the required spectral separation to the second eigenvalue of the expected matrix. The stated assumption is identified as the one in Theorem 1.6.

C Censor Block Model

  • The analysis bounds ∥E∥ after forming Y0 by zeroing rows and columns of Y with high degree, using a lemma whose proof follows Corollary 3.4.The supplied passage does not include the lemma’s bound.Source: C Censor Block Model · p. 26
  • The second eigenvalue of ¯Y is p(1 −2ϵ)n, and the stated assumption for making the top-two-eigenvector eigenspace angle small is identified as the assumption in Theorem 1.6.The assumption itself is incomplete in the supplied passages.Source: C Censor Block Model · p. 27

D Proof of Lemma A.2

The proof is described as essentially the same as. It introduces parameterized sets and analyzes the remaining cases through logarithmic subcases.

D Proof of Lemma A.2

  • The proof follows and introduces sets parameterized by γ_k.Source: D Proof of Lemma A.2 · p. 27
  • Using α_i := s_i/(dγ_j), the proof applies the maximum-degree bound λ_i,j ≤ c1n/t_j.Source: D Proof of Lemma A.2 · pp. 27–28
  • After excluding cases 1–3, the proof divides the remaining analysis into subcases based on logarithmic thresholds involving λ_i,j, γ_j, and β_j.The displayed subcases include log λ_i,j > (1/4)[2 log γ_j + log(1/β_j)] and 2 log γ_j ≥ log(1/β_j).Source: D Proof of Lemma A.2 · pp. 28–29

Related papers

Loading 1501.05021v2…