PaperlayerView exact revision on arXiv

Source-linked AI summary

On semidefinite relaxations for the block model

Arash A. Amini, Elizaveta Levina

arXiv:1406.5647v3cs.LGcs.SIstat.ML

TL;DR

The paper addresses the computational difficulty of fitting stochastic block models by maximum likelihood. It develops a unified family of semidefinite relaxations, centered on tighter SDP-1, and shows broader exact-recovery guarantees, flexible block-size handling, and strong empirical performance against spectral methods.

  • Problem

    Maximum-likelihood fitting of the SBM is computationally infeasible because it requires optimization over community assignments.

  • Method

    The paper derives SDP relaxations of the SBM MLE, unifies existing formulations through parameter-space restrictions, and connects them to sparse PCA.

  • Results

    SDP-1 is tighter than prior relaxations and is strongly consistent for a wider class of weakly assortative SBMs, while previous SDP approaches require strong assortativity.

  • Takeaways & Limitations

    Combining SDP-1 with existing relaxations provides flexibility for weak assortativity and unbalanced communities, while SDPs empirically outperform adjacency-based spectral clustering for large K.

  • Takeaways & Limitations

    The theoretical analysis focuses mainly on balanced models, and disassortative results require applying the SDPs to −A.

Abstract

from arXiv · show

The stochastic block model (SBM) is a popular tool for community detection in networks, but fitting it by maximum likelihood (MLE) involves a computationally infeasible optimization problem. We propose a new semidefinite programming (SDP) solution to the problem of fitting the SBM, derived as a relaxation of the MLE. We put ours and previously proposed SDPs in a unified framework, as relaxations of the MLE over various sub-classes of the SBM, revealing a connection to sparse PCA. Our main relaxation, which we call SDP-1, is tighter than other recently proposed SDP relaxations, and thus previously established theoretical guarantees carry over. However, we show that SDP-1 exactly recovers true communities over a wider class of SBMs than those covered by current results. In particular, the assumption of strong assortativity of the SBM, implicit in consistency conditions for previously proposed SDPs, can be relaxed to weak assortativity for our approach, thus significantly broadening the class of SBMs covered by the consistency results. We also show that strong assortativity is indeed a necessary condition for exact recovery for previously proposed SDP approaches and not an artifact of the proofs. Our analysis of SDPs is based on primal-dual witness constructions, which provides some insight into the nature of the solutions of various SDPs. We show how to combine features from SDP-1 and already available SDPs to achieve the most flexibility in terms of both assortativity and block-size constraints, as our relaxation has the tendency to produce communities of similar sizes. This tendency makes it the ideal tool for fitting network histograms, a method gaining popularity in the graphon estimation literature, as we illustrate on an example of a social networks of dolphins. We also provide empirical evidence that SDPs outperform spectral methods for fitting SBMs with a large number of blocks.

1 Introduction

The SBM offers a tractable model for community detection, but exact likelihood fitting is computationally infeasible and existing methods have initialization or sparsity limitations. The paper develops SDP relaxations, including a tighter SDP-1 with broader consistency guarantees and flexible block-size behavior.

  • Fitting the SBM requires optimizing over K^n assignments, making exact maximum-likelihood estimation computationally infeasible.
  • SDP methods relax the infeasible likelihood optimization while retaining global optimization and likelihood-based modeling, though they require more computationally costly solvers.
  • The proposed SDP-1 is tighter than previously proposed SDP relaxations and empirically gives better results with reasonable first-order ADMM computation.
  • SDP-1 achieves strong consistency for weakly assortative SBMs when expected degree grows as Ω(log n), broadening prior consistency conditions.
  • The framework connects the SDP relaxations to sparse PCA and combines SDP features to support weak assortativity and differing block-size constraints.

2 The stochastic block model

The SBM represents communities through latent node memberships and a matrix of edge probabilities, with adjacency entries conditionally independent given these quantities. The planted-partition special cases simplify the likelihood through within- versus between-community probabilities and block-size assumptions.

  • Each node has one latent community membership, and Ψ specifies the edge probability between every pair of communities.
  • Conditional on memberships and Ψ, edges are drawn independently as Bernoulli variables with means z_i^T Ψ z_j.
  • The matrix M_Z = ZΨZ^T embeds the K × K probability matrix as a block-constant, rank-K n × n matrix.
  • The SBM log-likelihood can be written as inner products involving A, the entrywise functions f and g applied to M_Z, and the all-ones matrix.
  • The planted-partition model uses within-community probability p and between-community probability q with p > q, while PPbal additionally assumes equal block sizes.

3 Relaxing the maximum likelihood estimator (MLE)

The paper relaxes the SBM MLE by replacing discrete clustering matrices with convex feasible sets defined by PSD, nonnegativity, trace, and balance constraints. It compares SDP-1 with other relaxations and relates the resulting formulation to sparse PCA and spectral eigenvalue truncation.

  • The MLE has desirable consistency properties but is generally NP-hard because it optimizes over latent community assignments.
  • Different MLE relaxations arise by varying the parameter space, equivalently replacing the discrete clustering-matrix set with a tractable feasible region.
  • SDP-1: For balanced planted partitions, SDP-1 relaxes permutation-generated cluster matrices using PSD, nonnegativity, unit diagonal, and equal row-sum constraints.
  • SDP-2: SDP-1 is tighter than SDP-2 because it imposes the total-sum constraint through separate affine row constraints rather than one aggregate constraint.
  • SDP-3 and sparse PCA: The unbalanced formulation retains a sparsity penalty through ∥X∥_1, linking the relaxation to sparse PCA and allowing block-size deviation controlled by γ.
  • Connection with sparse PCA: When γ = 1, the normalized relaxation corresponds to a sparse-PCA relaxation for recovering a sparse K-dimensional leading eigenspace.
  • Connection with spectral clustering: Eigenvalue truncation maximizes ⟨A, X̃⟩ subject to PSD, trace, and spectral-norm constraints, and SDP-1 is a strictly tighter relaxation of it.

4 Strong consistency results

The paper establishes exact recovery guarantees for SDP relaxations, showing that SDP-1 succeeds for weakly assortative balanced block models while SDP-2′ requires strong assortativity. These results are proved using primal-dual witness constructions and apply under explicit degree and probability conditions.

  • Model scope: The results use balanced block models with n = mK and include extensions to disassortative models by applying the SDPs to −A.The paper also gives an expected-degree formulation, noting that fixed out-in ratio β requires d = Ω(K^2 log n) for SDP-2′ and hence SDP-1.
  • Scope of assortativity: Strong assortativity requires every within-block probability to exceed the largest relevant between-block probability, whereas weak assortativity requires the corresponding comparison block by block.Strong assortativity implies weak assortativity, making the latter a strictly broader condition.
  • Consistency guarantees: SDP-2′ is strongly consistent for balanced planted partition models under the stated probability condition, with probability at least 1 − c(Km^-r + n^-r) − n^-c1 − 2m^-1n^-c2.The same guarantee extends to strongly assortative balanced block models after replacing p and q with p− and q+.
  • Consistency guarantees: SDP-1 is strongly consistent for weakly assortative balanced block models, with probability at least 1 − c(Km^-r + n^-r) − n^-c1 − 2m^-1n^-c2.Because SDP-1 is tighter than SDP-2′, it inherits the latter’s guarantees and additionally covers the larger weakly assortative class.
  • Scope of assortativity: For fixed K and constant entries of Ψ, condition (4.7) holds for large n, so SDP-1 is strongly consistent for any weakly assortative balanced block model in that regime.The paper also states that SDP-2′ fails in general outside the strongly assortative class.
  • Proof strategy: The analysis constructs primal and dual solutions satisfying KKT conditions, which establishes optimality and supports uniqueness of the true cluster matrix.For an optimal pair, the primal-dual witness certifies strong duality; exact recovery is expressed as the true cluster matrix being the unique SDP solution.

5 Failure of SDP-2′ in the absence of strong assortativity

The paper shows that SDP-2′ can fail to recover communities when strong assortativity is absent, even in the noiseless population-mean setting. This establishes that strong assortativity is necessary for exact recovery by this approach.

  • Strong assortativity is necessary for exact recovery by SDP-2′, as failure already occurs on the noiseless mean matrix.The result is deterministic and non-asymptotic, without expected-degree constraints beyond assortativity assumptions.
  • The failure construction applies to general block sizes and includes balanced models when at most two blocks violate the relevant threshold.The proposition defines I_c as the blocks with p_k below q_{k0ℓ0}.
  • Under weak but not strong assortativity, SDP-2′ fails to recover blocks whose within-block probabilities fall below a critical between-block probability.For such blocks, the constructed solution sets the corresponding β_k values to zero.

6 Extensions to the unbalanced case

The unbalanced-case analysis shows how SDP-1 and SDP-13 behave when community sizes differ. With suitable parameters, both can recover selected blocks perfectly, while SDP-1 tends to favor similarly sized communities.

  • SDP-1 and SDP-13 in unbalanced models: For weakly assortative unbalanced models, SDP-1 with m ≤ min_k n_k admits a solution whose recovery coefficients depend on block sizes.The corresponding proposition analyzes SDP-1 at the population mean and allows m below the smallest block size.
  • SDP-1 and SDP-13 in unbalanced models: SDP-13 can improve on SDP-1 when m ≤ min_k n_k and its regularization parameter is chosen appropriately.Its solution is characterized using the ordered block probabilities and the index sets I, I_1(k), and J_k.
  • Illustration: Figure 1 illustrates these results on a weakly but not strongly assortative model with unequal block sizes (10, 10, 5, 20, 10, 10).It compares the population mean, several SDP outputs, and the ideal cluster matrix using m = min_k n_k.
  • Recovery behavior: The two relaxations differ because SDP-1 can assign zero recovery coefficients to blocks violating weak assortativity, whereas SDP-13 guarantees nonzero coefficients in the analyzed construction.Blocks with coefficients in (0,1) are imperfectly recovered, while coefficient 1 denotes perfect recovery.
  • Recovery behavior: Both SDP-1 and SDP-13 recover the smallest blocks perfectly when m = min_k n_k.This choice is described as optimal when the minimum block size is known.

7 Application to network histograms

The paper applies balanced block-model fitting to network histograms for graphon estimation. SDP-1 is especially suitable because its tendency toward equal-sized communities matches the histogram construction.

  • Graphon approximation: Balanced block models provide nonparametric graphon approximations through block-constant functions, with approximation improving as the number of blocks increases under regularity conditions.The construction partitions [0,1] into equal-sized intervals and maps the block probability matrix to a block-constant graphon.
  • Estimation procedure: Algorithm 1 converts an estimated cluster matrix into a graphon estimator using eigendecomposition, K-means, block averaging, and label ordering.Its output is the estimator M̂_Z constructed from the estimated labels and block parameters.
  • Why SDP-1 is useful: SDP-1 is well suited to network histograms because it tends to form equal-sized blocks, unlike likelihood-based estimators that do not enforce equal block sizes.SDP-3 is more flexible but does not enforce either a fixed number of blocks or a fixed block size.
  • Empirical context: Figure 2 evaluates bias-corrected NMI against the number of communities K for varying average degree d in a balanced planted partition model.The experiments use n = 120 and β = 0.05.

8 Numerical Results

Numerical experiments compare SDP-1 with other SDPs and spectral clustering across balanced, weakly assortative, and dolphin-network settings. SDP-1 generally benefits from its tighter relaxation and remains stable where SDP-2 degrades.

  • Balanced planted partition experiments: SDP-1 dominates SDP-2 and SDP-3 in bias-corrected NMI, while all SDPs outperform the spectral method EVT in the planted partition experiments.The comparison averages NMI over 25 Monte Carlo replications and adjusts random guessing to NMI = 0.
  • Balanced planted partition experiments: As average degree decreases or the out-in ratio increases, community estimation becomes harder in the balanced planted partition model.The experiments vary the number of communities K and average degree d.
  • Weak-assortativity experiments: Figure 4 tracks NMI and relative cluster-matrix error against p3 for the probability matrix in (8.1).The figure is used to visualize the contrasting degradation of SDP-2 and stability of SDP-1.
  • Weak-assortativity experiments: In the weakly but not strongly assortative model, SDP-2 loses blocks as p3 decreases, whereas SDP-1 remains approximately stable even at p3 = 0.05.SDP-2 has difficulty recovering the fourth block and completely fails on the third at p3 = 0.05.
  • Dolphins network: For the dolphins network, replacing equality constraints with inequality constraints lets SDP-1 misclassify only two nodes despite unbalanced ground-truth blocks of sizes 20 and 42.The analysis also finds nine strong and one weak clusters, though the two-community ground truth is not unique.

9 Discussion

The paper consolidates SDP relaxations for SBM fitting and shows that the proposed SDP-1 broadens exact-recovery guarantees beyond strong assortativity. It also compares flexibility, robustness, and remaining limitations across SDP formulations.

  • Discussion: SDP-1 is strongly consistent for weakly assortative models, whereas SDP-2 fails outside the strongly assortative class.The paper identifies mixed assortative and dissortative networks as an open question.
  • Discussion: The authors combine SDP-1 and SDP-3 to obtain consistency for weakly assortative and unbalanced models.The mixture is intended to combine the flexibility of the two relaxations.
  • Discussion: SDP-3 offers more flexibility than SDP-2 through a continuous tuning parameter λ, but this makes it unsuitable for some tasks such as histogram estimation.For every A and K, Lagrange duality gives a λ making SDP-3 equivalent to SDP-2.
  • Discussion: SDPs empirically outperform adjacency-based spectral clustering, especially when the number of communities K is large.The paper relates this pattern to better dependence on K in current theoretical guarantees and possible robustness to noise.

B Probabilistic bounds for BMbal

This section establishes probabilistic bounds for balanced block models by controlling within-community and between-community degrees and associated fluctuation terms. These concentration results supply the auxiliary conditions used in the consistency analysis.

  • Probabilistic bounds: Within-community degrees satisfy high-probability lower bounds, while between-community degrees concentrate around their expected values.The stated bounds hold with probabilities at least 1 − n^−(c1−1) and 1 − 2m^−1n^−(c2−2), respectively.
  • Cross-community concentration: The argument uses concentration of average cross-community degrees around their means to control the relevant probabilistic inequalities.The average degree lies in [q̄_kℓ(1 − ζ_kℓ), q̄_kℓ(1 + ζ_kℓ)] with high probability.
  • Auxiliary conditions: The proof requires logarithmic lower bounds on expected within-community and between-community degree scales.Auxiliary conditions include lower bounds involving log n and log m.

C Proofs of Section 4.2.1

These proofs establish optimality and uniqueness of the planted block solution through primal-dual conditions and block-constant structure. A coupling argument transfers the required optimality property between adjacency matrices.

  • Coupling argument: A coupling between A and an auxiliary matrix eA is used to prove the corresponding optimality result.The construction draws A from the balanced planted-partition model and verifies that eA has the same distribution.
  • Block structure: If a feasible matrix has range in the block-indicator span, it must be block-constant and can be written as B ⊗ E_m.This structural lemma reduces the candidate solution to a K × K block matrix B.
  • Uniqueness: The KKT conditions force off-diagonal block coefficients to zero and diagonal coefficients to one, yielding the planted solution X0.Nonzero dual blocks enforce b_kℓ = 0 for k ≠ ℓ, while diagonal feasibility gives b_kk = 1.

D.1 Proof of Theorem 4.1: primal-dual witness for SDP-2′

The primal-dual witness proof constructs dual variables and blockwise corrections so that feasibility and complementary conditions certify SDP-2′. Probabilistic degree and spectral-norm bounds then provide sufficient conditions for this construction to succeed.

  • Success conditions: Choosing μ as the maximum of the relevant right-hand sides yields a deterministic success condition for SDP-2′, which is then converted into a probabilistic condition.The probabilistic version is obtained using concentration arguments in the subsequent analysis.
  • Blockwise construction: The cross-community blocks are arranged so every row and column of A + Γ has the same sum μm.Equivalently, 1_m is a left and right eigenvector associated with eigenvalue μm.
  • Dual construction: The proof chooses a scalar dual parameter and blockwise matrices so that dual feasibility reduces to inequalities involving cross-community adjacency blocks.The construction uses B_SkSℓ = P_1⊥ A_SkSℓ P_1⊥ and requires μE_m + B_SkSℓ ≥ A_SkSℓ.
  • Concentration bounds: Within-block fluctuation norms are bounded at order √(p̄m), while off-diagonal fluctuations are controlled at order √(qn).The bounds hold with high probability and are combined by a union bound.
  • Degree concentration: Bernstein inequalities provide high-probability control of within-community and cross-community degrees around their respective means.The argument applies union bounds over nodes and communities.

H Proof of Proposition 5.1

The proof constructs primal-dual witnesses for SDP-2′ and SDP-1 under weak assortativity, using block-specific parameters to satisfy feasibility and complementary-slackness conditions. The resulting restrictions explain which blocks can be recovered imperfectly or perfectly and how block-size constraints affect the construction.

  • Primal-dual witness construction: The proof chooses block-structured dual variables so that ΛX = 0 and complementary slackness reduce to scalar restrictions on block parameters.For SDP-2′, these restrictions include βkγk = 0 and ρkℓαkℓ = 0, together with nonnegative dual variables.
  • Primal-dual witness construction: Setting µ to the largest off-diagonal probability permits only αk0ℓ0 and αℓ0k0 to be potentially nonzero among the relevant blocks.This follows from the uniqueness of the maximizing pair (k0, ℓ0) and the dual restrictions.
  • Feasibility: The constructed parameters satisfy primal feasibility under the stated assumptions, completing the proof of the proposition.The proof verifies the remaining conditions after choosing the block parameters and dual variables.
  • SDP-1 construction: When nk > m, setting αk = 1 forces φk = 0, so the proof avoids perfect recovery for such blocks when preserving dual flexibility is necessary.The construction instead reserves αk = 1 primarily for blocks with nk = m.
  • SDP-1 construction: For SDP-1, the condition ΛX = 0 becomes λk(1 − αk) = 0, so blocks with αk < 1 require λk = 0.The construction partitions blocks into I1, I2, and Ic to satisfy the associated primal and dual feasibility conditions.

K Details on Figure 1: comparing the theoretical predictions with empirical results

The Figure 1 example numerically matches the theoretical predictions for SDP-1, SDP-13, and SDP-2′ on a weakly assortative six-block model. The example also illustrates perfect recovery for selected blocks and the effect of strong-assortativity violations on SDP-2′.

  • Model setup: The six-block example has overall maximum off-diagonal probability 0.521, and its last three blocks violate strong assortativity.This provides a weakly assortative setting for comparing the SDP predictions.
  • SDP-2′: SDP-2′ is predicted to have α1 = α2 = α3 = 1, α23 = α32 = 0.6, and βk = 0 for k = 4, 5, 6.The prediction follows from the block-size ratios and the maximizing off-diagonal pair (2, 3).
  • SDP-13: SDP-13 predicts three perfectly recovered blocks in the example.Its parameters are selected with µ = 0.55 and m = mink nk = 5.
  • SDP-1: SDP-1 predicts a solution with diagonal recovery parameters 0.444, 0.444, 1, 0.211, 0.444, and 0.444.These values are reported for SDP-1 with m = 5.
  • Comparison with empirical results: The empirical results in Figure 1 match the predictions for SDP-1 and SDP-13, while SDP-3 can also be predicted by examining the proofs.The behavior of SDP-3 is not covered directly by Propositions 5.1 and 6.1.
  • NMI adjustment: After subtracting the average NMI of random guessing, the dip in the Figure 2 curves disappears.The adjustment addresses the nonzero empirical NMI of random guessing when K is large.
Loading 1406.5647v3…