Community detection in sparse networks via Grothendieck's inequality

Olivier Guédon; Roman Vershynin

Source-linked AI summary

Community detection in sparse networks via Grothendieck's inequality

Olivier Guédon, Roman Vershynin

arXiv:1411.4686v4Nov 17, 2014math.STcs.SI

TL;DR

The paper addresses whether simple semidefinite programs can consistently recover communities in sparse random networks. It uses Grothendieck’s inequality on random errors and shows arbitrarily small misclassification fractions across several stochastic network settings, while noting unresolved information-theoretic optimality.

Problem
It asks whether semidefinite programs can recover community structure in totally sparse networks with bounded average degree, where prior results were limited.
Method
The method applies Grothendieck’s inequality to the random error matrix within a flexible analysis of semidefinite programs.
Results
Various simple semidefinite programs recover communities with an arbitrarily small fraction of misclassified vertices in sparse and broader stochastic network models.
Takeaways & Limitations
Semidefinite programming succeeds for totally sparse networks and can handle variable edge probabilities and multiple equal-sized communities.
Takeaways & Limitations
Whether semidefinite programming reaches information-theoretic limits remains open, and Theorem 1.1 requires tighter constants and ε-dependence.

Abstract

from arXiv · show

We present a simple and flexible method to prove consistency of semidefinite optimization problems on random graphs. The method is based on Grothendieck's inequality. Unlike the previous uses of this inequality that lead to constant relative accuracy, we achieve any given relative accuracy by leveraging randomness. We illustrate the method with the problem of community detection in sparse networks, those with bounded average degrees. We demonstrate that even in this regime, various simple and natural semidefinite programs can be used to recover the community structure up to an arbitrarily small fraction of misclassified vertices. The method is general; it can be applied to a variety of stochastic models of networks and semidefinite programs.

1.1. Semidefinite problems on random graphs.

The paper develops a general method for estimating solutions to discrete optimization problems from random matrix instances. Semidefinite relaxations combined with Grothendieck’s inequality use random errors to achieve arbitrarily small relative accuracy.

The method proves consistency for various semidefinite optimization problems on random graphs.
The framework estimates the solution of a discrete optimization problem when the unknown expectation matrix is unavailable.
Boolean quadratic problems encode graph partitions when A is an adjacency matrix and x represents two vertex classes.
Semidefinite relaxations previously provided constant relative accuracy, including a 0.56 approximation guarantee for a related relaxation.
Applying Grothendieck’s inequality to the random error A − Ā rather than A enables any given relative accuracy.
The method is simple and flexible enough to analyze semidefinite programs beyond Boolean problems and to produce community-detection results.

1.2. Community detection: the classical stochastic block model.

The classical stochastic block model divides vertices into two equal communities with different within- and across-community edge probabilities. The paper studies semidefinite recovery in this sparse setting and obtains arbitrarily small classification error under suitable conditions.

The classical stochastic block model has two equal communities, with edge probabilities p within communities and q across communities.
Community detection seeks to recover the two communities from one observed random graph, including when the expected average degree pn is O(1).
Community recovery is equivalent to estimating the community membership vector represented by a Boolean vector.
The semidefinite program estimates the rank-one community matrix from the observed adjacency matrix under positive-semidefinite and diagonal constraints.
Theorem 1.1 guarantees that a solution of the semidefinite program approximates the target matrix with probability at least 1 − e^(35−n) under stated assumptions.
The leading eigenvector of the estimated matrix recovers the partition with at most εn misclassified vertices.
The result answers positively whether simple semidefinite programs can succeed for totally sparse graphs and extends to broader network models and program variants.

1.3. Community detection: general stochastic block models.

The paper extends its semidefinite approach to general stochastic block models with arbitrary community sizes, outliers, and unequal edge probabilities. It analyzes cluster-matrix estimation and explains the method’s scope, assumptions, and consequences for small communities and unknown community sizes.

General stochastic block model: The general stochastic block model permits multiple communities of arbitrary sizes, arbitrarily many outliers, and unequal edge probabilities.Outliers are represented by communities of size 1.
General stochastic block model: The model requires within-community edge probabilities at least p and across-community probabilities at most q.For each pair, the edge probability may vary as pij while preserving this separation.
Semidefinite formulation: The cluster matrix records whether each pair of vertices belongs to the same community, and the semidefinite program estimates this matrix from the graph.The optimization uses positive-semidefinite and nonnegative matrix constraints and sets λ to the number of elements in the cluster matrix.
Semidefinite formulation: When all communities have size s, the parameter is λ = Ks2 = ns.This is the specialization of λ to K equal-sized communities.
Guarantee: Theorem 1.3 gives a high-probability recovery guarantee for the general stochastic block model.The supplied theorem passage introduces the guarantee but does not include its full inequality.
Guarantee: Small communities of size o(n) may be absorbed into the error term and therefore may not be recovered.The theorem’s power does not depend on the number and sizes of communities, but this scope comes with that limitation.
Unknown community sizes: If community sizes are unknown, choosing λ below or above λ0 yields a subgraph or supergraph of the cluster graph, respectively.The discrepancy can involve at most λ0 − λ missing edges when λ ≤ λ0, or at most λ − λ0 extra edges when λ ≥ λ0.
Interpretation: The semidefinite program can be viewed as densifying connections within communities and sparsifying connections across them.This interpretation treats the cluster matrix as the adjacency matrix of a cluster graph.

1.4. Related work.

Earlier community-detection guarantees primarily addressed relatively dense networks, while sparse networks with bounded or slowly growing average degrees were less understood. The paper positions its semidefinite programs as successful in totally sparse settings, with broader applicability but without reaching information-theoretic limits.

Relatively dense networks: Most rigorous community-detection results before this work concerned networks whose expected degrees grow with n, often at least logarithmically.In the Ω(log n) regime, perfect recovery may be possible using spectral, likelihood, or convex methods.
Relatively dense networks: Earlier semidefinite relaxations could perfectly recover communities under conditions such as (a −b)2 ≥C(a log n + b).These results apply to relatively dense networks.
Totally sparse networks: For sparser networks, expected average degrees may grow arbitrarily slowly or remain bounded, and comparatively little was known theoretically.The paper focuses on this practically motivated sparse regime.
Totally sparse networks: When degrees grow slower than log n, perfect classification is impossible because a positive fraction of vertices will be isolated with high probability.The fraction of isolated vertices nevertheless tends to zero, leaving majority recovery possible.
Prior sparse-network methods: A truncated spectral method removes vertices with excessively large degrees before approximately recovering communities from the second eigenvector.Its analysis yields concentration for the truncated adjacency matrix under a suitable sparse-network condition.
Prior sparse-network methods: Removing high-degree vertices is often impractical for real networks, and the cited probabilistic estimate is not sharp.This limits the practical appeal and precision of that spectral approach.
Prior sparse-network methods: Adaptive spectral and path-counting algorithms also approximately recover communities under sparse-network conditions, while some constants lack explicit dependence on the target accuracy.The cited adaptive spectral method is described as complicated.
Information-theoretic limits: Condition (1.14) has the optimal form, with the necessary lower-bound constant diverging as ε approaches zero.This lower bound applies to any algorithm seeking at most εn misclassified vertices.

1.5. Plan of the paper.

The paper first develops the general method, then studies Grothendieck’s inequality and random-matrix concentration before specializing to community detection in the classical stochastic block model.

Section 2: Section 2 presents the method in general terms and explains how Grothendieck’s inequality proves tightness of semidefinite programs on random graphs.The paper emphasizes consistency for semidefinite optimization problems.
Section 3: Section 3 develops Grothendieck’s inequality and its implications for semidefinite programming.
Section 4: Section 4 proves a concentration inequality for random matrices in the cut norm.
Section 5: Section 5 specializes the method to community detection in the classical stochastic block model and proves Theorem 1.1.

2. Semidefinite optimization on random graphs: the method in a nutshell

The method analyzes a random semidefinite program by comparing it with an expected, tightly relaxed problem, controlling random deviations, and converting objective closeness into recovery of the original solution.

Expected problem: The semidefinite relaxation must be tight for the expected problem, so its maximizer represents the rank-one solution of the original optimization problem.This condition is verified in the setting of Theorem 1.1.
Random deviation: A uniform deviation inequality is required to show that the random and expected objective functions are close over all feasible candidates.The paper proves this inequality using fixed-pair concentration followed by a union bound.
Grothendieck step: Grothendieck’s inequality converts the deviation control into an almost-optimal expected objective value for the random program’s solution.The paper applies the inequality to the random error rather than directly to the original matrix.
Stability: The expected objective must distinguish points near its maximizer, allowing an almost maximizer to be close in Frobenius or operator norm.The paper interprets this property as non-trivial curvature of the feasible set at the maximizer.
Recovery: Because the reference maximizer is rank one, closeness of the semidefinite solution makes it approximately rank one and allows recovery through its leading eigenvector.The recovered eigenvector estimates the original optimization solution.

3. Grothendieck’s inequality and semidefinite programming

Grothendieck’s inequality relates vector-valued and sign-valued matrix optimizations, enabling semidefinite programs to be compared with simpler reference problems through an appropriate matrix norm.

Context: Previous uses of Grothendieck’s inequality analyzed semidefinite relaxations with constant accuracy, whereas this paper targets arbitrary relative accuracy using randomness.The inequality has also been applied to hard combinatorial optimization problems.
Matrix formulation: The inequality compares optimization over unit vectors with optimization over sign vectors, represented respectively by matrix sets M_G and M_1.The sign-vector objective is the ℓ∞→ℓ1 norm of the coefficient matrix.
Positive semidefinite form: Restricting the Grothendieck set to positive semidefinite matrices yields a class containing feasible matrices with entries bounded by one.The paper derives this inclusion using Gram representations and Cauchy–Schwarz.
Optimization class: The general program maximizes ⟨B,Z⟩ over a subset M_opt of the positive semidefinite Grothendieck set, including examples based on random graph adjacency matrices.For one example, B is A−λE_n and M_opt is the positive semidefinite Grothendieck set.
Reference comparison: Replacing the random matrix B by a simpler reference matrix R shows that the optimizer of the original program almost maximizes the reference objective when B and R are close.Lemma 3.3 establishes this transfer of near-optimality.

4. Deviation in the cut norm

The paper controls random-matrix deviations in the ℓ∞→ℓ1, or cut, norm using Bernstein’s inequality and a union bound, obtaining concentration suitable for bounded-average-degree graphs.

Deviation bound: Lemma 4.1 bounds the ℓ∞→ℓ1 deviation of a symmetric random matrix whose independent entries lie in [0,1].The bound applies under a lower condition on the average variance parameter.
Sparse graphs: For G(n,a/n), the deviation satisfies ∥A−E A∥∞→1 ≤3a^1/2n, while the expected matrix has norm at least an.Thus the relative deviation decreases as a grows.
Regularization: Bounded expected degrees are tractable when a exceeds a sufficiently large absolute constant, because a=pn is the expected average degree.The cut norm averages contributions across vertices and suppresses the influence of a few high-degree vertices.
Proof strategy: For each fixed sign pair x,y, the deviation becomes a sum of independent centered variables controlled by Bernstein’s inequality.The variables have bounded magnitude and variance determined by the average edge variance.
Uniformization: A union bound over all 2^2n sign pairs upgrades fixed-pair concentration to a uniform ℓ∞→ℓ1 bound.The argument then uses the norm’s definition to conclude Lemma 4.1.

5. Stochastic block model: proof of Theorem 1.1

For the stochastic block model, the proof chooses a block-structured reference matrix close to the expected centered adjacency matrix, then combines cut-norm concentration and Grothendieck’s inequality to recover communities.

Model and program: The classical stochastic block model is analyzed using B:=A−λE_n and a feasible set that is a special case of the general semidefinite program class.The two communities are assumed, without loss of generality, to occupy the first and second halves of the vertices.
Reference matrix: The reference matrix R captures the leading block structure of E B, while identity and all-ones corrections are treated as negligible terms.The paper explicitly states that R≈E B in the relevant analysis.
Reference optimization: The reference optimizer Z_R is determined from the block form of R and belongs to the feasible set, establishing tightness for the expected problem.Its maximization is first checked on the larger entrywise bounded set and then transferred to M_opt.
Community recovery: The reference maximizer equals x̄x̄^T, where x̄ encodes the two communities, so the leading eigenvector of the semidefinite solution estimates the membership vector.The rank-one reference matrix has spectral gap n, enabling a Davis–Kahan eigenvector argument.
Concentration and stability: With probability at least 1−e^(35−n), the random and reference maximizers are close when the variance parameter satisfies the required condition.Lemma 5.2 obtains this result by separately bounding the random adjacency, λ, and correction terms.

6. General stochastic block model: proof of Theorem 1.3

The proof identifies the community membership matrix as the expected-objective maximizer, then shows random and expected maximizers are close enough to yield arbitrarily accurate recovery under the theorem’s signal condition.

Reference problem: The reference matrix equals the expected adjacency matrix, which need not itself have block form when edge probabilities vary across pairs.Nevertheless, the reference problem’s solution is the block-structured community membership matrix.
Expected objective: The expected objective is maximized by the community membership matrix because its λ largest entries form the within-community blocks.The argument first maximizes over a larger 0/1-matrix set, whose extreme-point maximizer selects the λ largest entries of the expectation matrix.
Expected objective: The expected objective distinguishes every feasible matrix from the community membership matrix according to within- versus across-community entries.The proof partitions entries into In and Out and uses p-versus-q separation together with the common matrix mass constraint.
Random objective: With probability at least 1 −e35−n, the maximizers of the random and expected objectives are close when the average within-community probability satisfies (4.1).This is the probabilistic stability step connecting the observed optimization problem to its population counterpart.
Recovery guarantee: The theorem’s condition (a −b)2 ≥484 ε−2g bounds the recovery error by εn2 in the ∥· ∥1 norm.The proof uses Grothendieck’s constant KG ≤1.783 before rearranging the bound.
Recovery guarantee: The same closeness result also gives the stated Frobenius-norm bound because all entries of both matrices lie in [0, 1].The entrywise bound ∥bZ−¯Z∥∞≤ 1 converts the ∥· ∥1 control into Frobenius control.

7. The balanced planted partition model.

For equally sized communities, the paper generalizes the semidefinite program to estimate a rank-(K−1) projection, and proves accurate recovery in the balanced partition model under explicit sparsity and separation conditions.

Model and program: The direct generalization of semidefinite program (1.4) detects multiple communities of equal sizes.For K = 2, the additional lower-bound constraint is redundant, and the result matches Corollary 1.2.
Model and program: In the balanced partition model, within-community edges have probability p and cross-community edges have probability q, with n = Ks and equal community size s.The model partitions n vertices into K communities and samples each distinct-vertex edge according to whether its endpoints share a community.
Spectral recovery: The method estimates the community structure through an orthogonal projection ¯P of rank K −1 using semidefinite program (7.2).The estimated projection bP is formed from the eigenvectors associated with the 2K−3 largest eigenvalues of a solution bZ.
Theorem 7.1: With probability at least 1 −e35−n, Theorem 7.1 provides the stated recovery bound when n ≥104K/ε2 and max {a(1 −p), (K −1)b(1 −q)} ≥10.The theorem applies to K equal-sized communities in the balanced partition model and defines bP from the leading 2K−3 eigenvectors.
Spectral recovery: The reference optimizer is a multiple of ¯P, and semidefinite feasibility follows because ¯P is an orthogonal projection.This establishes the population target for the random optimization problem.
Spectral recovery: The proof controls the random optimizer’s distance from the reference optimizer and then uses Weyl’s inequalities and Davis–Kahan to control the projection estimate.The spectral argument exploits a separation gap between the relevant eigenvalue groups.