Community detection thresholds and the weak Ramanujan property

Laurent Massoulie

Source-linked AI summary

Community detection thresholds and the weak Ramanujan property

Laurent Massoulie

arXiv:1311.3085v1Nov 13, 2013cs.SI

TL;DR

The paper asks whether meaningful community detection is possible above the conjectured sparse stochastic-block-model threshold, where earlier positive results did not reach the threshold. It constructs a matrix counting self-avoiding paths and uses its leading eigenvectors for detection. For logarithmic path lengths, this yields non-trivial detection and a weak Ramanujan spectral separation, proving the positive part of the conjecture.

Problem
Positive community-detection results in the sparse stochastic block model had not reached Decelle et al.’s conjectured threshold.
Method
The paper forms B(ℓ), whose entries count self-avoiding paths of length ℓ, and applies its leading eigenvectors.
Results
For ℓ ∼ c log(n) with c log(α) < 1/4, the second eigenvector yields empirical overlap converging to {−r, +r} for r > 0, while B(ℓ) has weak Ramanujan spectral separation.
Takeaways & Limitations
The path-expanded matrix provides a polynomial-time spectral route to non-trivial detection in the regime τ > 1.
Takeaways & Limitations
The paper has not proved that the analogous matrix ˆB defined through exact distance regularization has the same spectral regularization.

Abstract

from arXiv · show

Decelle et al.\cite{Decelle11} conjectured the existence of a sharp threshold for community detection in sparse random graphs drawn from the stochastic block model. Mossel et al.\cite{Mossel12} established the negative part of the conjecture, proving impossibility of meaningful detection below the threshold. However the positive part of the conjecture remained elusive so far. Here we solve the positive part of the conjecture. We introduce a modified adjacency matrix $B$ that counts self-avoiding paths of a given length $\ell$ between pairs of nodes and prove that for logarithmic $\ell$, the leading eigenvectors of this modified matrix provide non-trivial detection, thereby settling the conjecture. A key step in the proof consists in establishing a {\em weak Ramanujan property} of matrix $B$. Namely, the spectrum of $B$ consists in two leading eigenvalues $ρ(B)$, $λ_2$ and $n-2$ eigenvalues of a lower order $O(n^ε\sqrt{ρ(B)})$ for all $ε>0$, $ρ(B)$ denoting $B$'s spectral radius. $d$-regular graphs are Ramanujan when their second eigenvalue verifies $|λ|\le 2 \sqrt{d-1}$. Random $d$-regular graphs have a second largest eigenvalue $λ$ of $2\sqrt{d-1}+o(1)$ (see Friedman\cite{friedman08}), thus being {\em almost} Ramanujan. Erdős-Rényi graphs with average degree $d$ at least logarithmic ($d=Ω(\log n)$) have a second eigenvalue of $O(\sqrt{d})$ (see Feige and Ofek\cite{Feige05}), a slightly weaker version of the Ramanujan property. However this spectrum separation property fails for sparse ($d=O(1)$) Erdős-Rényi graphs. Our result thus shows that by constructing matrix $B$ through neighborhood expansion, we regularize the original adjacency matrix to eventually recover a weak form of the Ramanujan property.

1 Introduction

The paper addresses the sparse stochastic block model’s detectability threshold by replacing adjacency-matrix spectral clustering with a self-avoiding-path expansion. For logarithmic path lengths, its second eigenvector yields positively correlated spin estimates and the expanded matrix has weak Ramanujan spectral separation.

Background: The stochastic block model assigns node types and places edges independently according to type-dependent probabilities, providing a testbed for community-detection methods.Detection quality is measured by agreement between estimated and true node types.
Background: Decelle et al. conjectured a sharp sparse-regime transition, while existing positive spectral results did not reach the conjectured threshold.Mossel, Neeman, and Sly established impossibility below the threshold through tree-reconstruction arguments.
Main results: τ = (a − b)^2/[2(a + b)] separates the known impossible regime τ < 1 from the paper’s target feasible regime τ > 1.The model uses two uniformly and independently assigned spins, with within-type and between-type edge probabilities a/n and b/n.
Main results: The method forms B(ℓ), whose entries count self-avoiding paths of length ℓ between node pairs, instead of applying spectral methods directly to adjacency.The path expansion regularizes the initial data through neighborhood growth.
Main results: For ℓ ∼ c log(n) with c log(α) < 1/4, the second eigenvector of B(ℓ) produces estimates whose empirical overlap converges to {−r, +r} for r > 0.This establishes non-trivial detection in the target regime and proves the positive part of Decelle et al.’s conjecture.
Main results: B(ℓ) satisfies a weak Ramanujan property: its leading eigenvalues are separated from the remaining spectrum, whose eigenvalues are lower order.The paper identifies this spectral separation as an auxiliary result supporting the path-based spectral method.

2 Proof structure

The proof combines spectral analysis of the path-expanded matrix B(ℓ) with local neighborhood estimates to establish its leading eigenstructure and derive non-trivial detection.

The leading eigenvalue of B(ℓ) is Θ(α^ℓ) up to logarithmic factors, with eigenvector asymptotically parallel to B(ℓ)e.
The second eigenvalue is Ω(β^ℓ) up to logarithmic factors, with eigenvector asymptotically parallel to B(ℓ)σ.
A unit-mean variable X with variance 1/(β^2/α−1) characterizes the limiting distribution relevant to vectors aligned with B(ℓ)σ.
For every ε > 0, all remaining eigenvalues have order O(n^ε√ρ(B(ℓ))), yielding spectral separation from the two leading eigenvalues.
The resulting tail asymmetry of X and −X yields an empirical overlap converging to {−r, +r}, establishing non-trivial detection.
Local neighborhood quantities approximate (B(t)e)i and (B(t)σ)i and exhibit quasi-deterministic growth, with high-probability bounds for all nodes and logarithmic t.
Choosing ℓ = c log(n) with c log(α) < 1/4 ensures the weak-Ramanujan analysis applies and supports the theorem’s detection construction.
Coupling node neighborhoods to a random tree process identifies the scaled local quantities with spin-weighted variables governed by the limiting martingale X.

3 Matrix expansion and spectral radii bounds

The matrix expansion decomposes path-counting terms into structured products, while trace-method circuit bounds control the associated spectral radii for logarithmic path lengths.

B(ℓ) is expanded using sets of self-avoiding paths and products involving the conditional mean adjacency matrix Ā.
The path classes Q^m_ij encode endpoint constraints, simple segments, and a nonempty intersection between the corresponding vertex sets.
The resulting products yield entries of Δ(ℓ−m)ĀB(m−1), producing the stated matrix expansion.
The trace method bounds ρ(Δ(ℓ))^2k through tr((Δ(ℓ))^2k), using circuit encodings and the concatenated simple-path structure.
For ℓ = O(log n), choosing k with ε > 1/(2k) converts the trace bound into inequality (7), with the remaining polylogarithmic factor controlled.
The spectral radius of Γℓ,m is bounded by Proposition 3.2 for all k, ℓ ≥ 1 and m ∈ {1, …, ℓ}.
Applying the same trace strategy to Γℓ,m yields inequality (8), whose final bound decays as a power of n under 2kε > 1.

4 Local Analysis: structure of expanded neighborhoods

The analysis couples local graph neighborhoods to branching-process variables, controls cycles and dependencies, and transfers these controls to the path matrix B(ℓ). This yields two structurally distinct leading eigenvectors and convergence results for associated spin estimates.

Coupling and neighborhood structure: Neighborhood processes for distinct nodes become asymptotically independent when ℓ=c log(n) and c log(α)<1/2.Their joint law approaches the law with identical marginals and independence at a negative power of n.
Coupling and neighborhood structure: With high probability, only O(log^4(n)α^2ℓ) nodes have a cyclic ℓ-neighborhood, and no node has more than one cycle-edge when c log(α)<1/4.These bounds support replacing neighborhood counts by tree-based quantities.
Transfer to B(ℓ): For ℓ=O(log n), the leading eigenvalue of B(ℓ) is Θ(αℓ) up to logarithmic factors, while the second is Ω(βℓ) up to logarithmic factors.Their eigenvectors align asymptotically with B(ℓ)e and B(ℓ)σ, respectively.
Transfer to B(ℓ): All remaining eigenvalues of B(ℓ) are O(n^ε√αℓ), establishing weak Ramanujan spectral separation.The result holds for ℓ=c log n with c log α<1/4.
Martingale analysis: The neighborhood-count processes are analyzed through martingales, with ∆t converging almost surely to ∆∞ under β2>α.The limiting variable has unit mean and variance 1/(β2/α−1).
Limit convergence: Convergence in probability of empirical averages to (1/2)Eg(±∆∞) follows after variance control and Tchebitchev’s inequality.The convergence applies at continuity points of the relevant limiting distributions.

5 Conclusions

The conclusion identifies path expansion as a way to recover Ramanujan-like spectral separation and suggests broader applications, while explicitly leaving one related regularization claim unproved.

Conclusions: Path expansion may help prove a phase transition conjecture for the labeled stochastic block model.The text presents this as a possible further application of the developed methods.
Conclusions: The broader applicability of path expansion to repairing spectral methods through Ramanujan-like separation remains an open question.The authors ask how widely this regularization approach can be used.
Conclusions: The proposed matrix ˆB defined by ˆBij = 1dG(,ij)=ℓ may exhibit similar regularization, but this has not been proved.This is the clearest stated scope boundary of the conclusion.
Proof strategy: The trace-method proof controls circuits by decomposing simple paths into reused-tree paths, new-node discoveries, and cycle edges.The decomposition enables counting configurations according to their tree excess and edge multiplicities.
Proof strategy: For a circuit with v nodes and e edges, the tree excess c=e−v+1 counts traversals outside the discovery tree.This quantity organizes the expectation bounds in the trace argument.

C Proof of Theorem 2.3

The proof of Theorem 2.3 establishes high-probability growth and concentration bounds for neighborhood processes using conditional binomial structure and Chernoff inequalities.

Growth controls: For ℓ=C log(n), the stated neighborhood-process properties hold with high probability simultaneously for all nodes and times t≤ℓ.This is the main high-probability control supplied by Lemma C.1.
Growth controls: After the threshold time T when Ut reaches K log(n), coordinate-wise growth remains controlled through bounds involving αt−T and a decaying error εt.The proof sets εt=εα−(t−T)/2.
Growth controls: The process Ut is governed by the two-type mean matrix M=(a/2 b/2, b/2 a/2), whose spectral radius is α.Conditionally on the past, the components are independent with binomial-type distributions.
Concentration: Chernoff bounds make deviations from conditional means sufficiently unlikely, including a relative-deviation probability at most n−2.The constants are chosen so the relevant rate-function inequalities exceed the required threshold.
Concentration: The proof transfers growth bounds from the threshold time to later steps and uses β2>α to control the difference process Dt.These estimates establish the corresponding properties for both St and Dt.

D Proof of Lemma 4.2

The proof bounds cycle formation in logarithmic-depth neighborhoods by separating two cycle mechanisms and applying stochastic domination, expectation bounds, and union bounds.

Cycle mechanisms: Cycles arise either from an edge between nodes at distance k−1 or from two such nodes sharing a node at distance k.The proof treats these mechanisms separately.
Cycle bounds: The conditional expectation for shared-node cycles on Ωk−1(i) is O(log^2(n)α2ℓ).This estimate feeds into the probability bounds for cyclic neighborhoods.
Cycle bounds: With high probability, no node has two cycle-edges within its ℓ-neighborhood when ℓ=c log(n) and c log(α)<1/4.The corresponding union-bound estimate is O(log^6(n)α4ℓ/n^2).
Application: These cycle estimates support controlling the discrepancy between B(ℓ)e, B(ℓ)σ and their tree-based neighborhood-count representations.Nodes with one cycle can contribute at most twice to the relevant path counts.
Cycle bounds: For distinct nodes, neighborhood-cycle events are controlled using approximate disjointness and bounds on the joint probability of cycles.The proof obtains an O(log^3(n)α2ℓ/n) bound when neighborhoods meet.

E Proof of Lemma 4.3

For cycle-free ℓ-neighborhoods, the self-avoiding-path count B(m) records graph distance exactly. For neighborhoods containing one cycle, the relevant counts remain bounded because nodes can be counted at most twice.

For a tree-like ℓ-neighborhood, B(m)_ik is binary because at most one simple path connects i and k.
B(m)_ik = 1 exactly when dG(i,k) = m for such cycle-free neighborhoods.
At most twice, nodes within distance ℓ of a one-cycle neighborhood are counted in (B(ℓ)e)_i.

F Proof of Corollary 4.1

The proof bounds B(ℓ)'s action on vectors orthogonal to B(ℓ)e and B(ℓ)σ by separating cyclic-neighborhood contributions and applying Cauchy–Schwarz inequalities.

For a normed vector x satisfying x′B(ℓ)e = 0, the proof decomposes and bounds its relevant inner products.
Cauchy–Schwarz bounds the first summation using the control for cyclic vertices and the size bound on B.
The third summation is bounded using e′B(ℓ)x = 0, followed by another Cauchy–Schwarz inequality.
The argument establishes the bound (24) on |e′B(m−1)x| and, analogously, the bound (25) on |σ′B(m−1)x|.

G Proof of Lemma 4.6

The proof couples neighborhood-growth processes with conditionally independent Poisson approximations, then uses martingale convergence and variance control to obtain limiting distributions.

Each event Ω_k has probability 1 − o(n^-2), enabling the conditional approximation argument across growth steps.
Stein–Chen bounds the Bin(n, λ/n)-to-Poi(λ) variation distance by at most λ/n, while Poisson parameter changes contribute at most |λ − λ′|.
Choosing c so that c log(α) < 1/2 yields the required growth bound for ℓ = c log(n), with an ε margin in the exponent.
Induction establishes convergence of the two process sequences in variation distance under the conditional approximations.
Var(M_t) = Var(M_{t−1}) + α^-t, and the resulting variance is uniformly bounded for α > 1.
Uniform integrability gives almost-sure and L1 convergence, while the limiting variance of Δ is 1/(β^2/α − 1).

J Proof of Theorem 4.2

The theorem proves convergence of empirical neighborhood statistics and overlaps by coupling them to limiting variables, controlling approximation errors, and evaluating first and second moments.

With probability 1 − O(n^-ε), σ(i)β^-ℓD_ℓ(i) coincides with Δ_ℓ; failed couplings are controlled using logarithmic bounds.
A second-moment decomposition controls cross terms, with one contribution tending to zero as n → ∞.
The empirical sum converges in probability to (1/2)E(f(Δ∞)) after replacing it with a simpler coupled sum.
The same argument applied to g yields the corresponding convergence in probability for the second test function.
The empirical overlap converges in probability to the quantity determined by P(Δ∞ ≥ t) − P(Δ∞ ≤ −t), with positivity ensured by the choice of t.
The upper and lower overlap bounds differ by at most 2δ and approach the target expression as δ becomes arbitrary.
The first two vector approximations hold because the compared vectors agree on cycle-free ℓ-neighborhoods, with error o(√(nβ^ℓ)).
The scalar product ⟨{S_ℓ(i)},{D_ℓ(i)}⟩ is o(|{S_ℓ(i)}| × |{D_ℓ(i)}|).

L Proof of Lemma 4.5

The proof bounds quantities involving the modified matrix by estimating path-counting terms in a branching-process model and transferring the estimates by coupling.

Lower bound: The proof uses Cauchy–Schwarz and distinguishes node pairs by their distance parameter τ to derive the lower bound.The distance is parameterized as 2(d + d′ − τ), with τ ranging from 0 to 2(d ∧ d′).
Upper bound: The upper bound follows partly from the maximum row sum of B(ℓ), which is of order O(log(n)α^ℓ).The proof attributes this estimate to Lemma 4.3 and Theorem 2.3.
Tree model: For cycle-free 2ℓ-neighborhoods, the proof represents the relevant entry of B(ℓ)B(ℓ)σ and evaluates its second moment conditionally on the tree.The tree is modeled as a branching process with Poi(α) offspring and Markovian spin propagation.
Counting configurations: With high probability, the relevant path-counting quantities satisfy the stated tilde-O bounds in α, d, d′, and τ.These estimates control the numbers of nodes and shared-distance configurations used in the proof.
Coupling: Coupling transfers tree-model estimates to the original scenario, using concentration techniques based on the cited theorem and lemmas.The argument invokes a Tchebitchev inequality together with bounds from Theorem 2.3 and Lemmas 4.6 and 4.1.