PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Graph Clustering

Yudong Chen, Sujay Sanghavi, Huan Xu

arXiv:1210.3335v3stat.ML

TL;DR

Graph clustering must recover groups in graphs whose density gaps, sparsity, cluster sizes, and node affiliations may vary. The paper develops a convex relaxation of maximum likelihood and analyzes it in generalized and semi-random stochastic blockmodels, obtaining stronger exact-recovery guarantees across several planted models.

  • Problem

    Graph clustering is difficult in sparse, heterogeneous graphs with small density gaps, growing numbers of clusters, and unaffiliated nodes.

  • Method

    The paper develops a convex relaxation of the maximum-likelihood estimator for graph clustering.

  • Results

    The method matches existing exact-recovery methods up to logarithmic factors broadly and improves them by polynomial factors for general scalings in planted partition, disjoint-clique, and noisy-coloring models.

  • Takeaways & Limitations

    The guarantees extend to generalized and semi-random settings with heterogeneity, unequal cluster sizes, unaffiliated nodes, and related planted models.

Abstract

from arXiv · show

Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this paper we present a new algorithm--a convexified version of Maximum Likelihood--for graph clustering. We show that, in the classic stochastic block model setting, it outperforms existing methods by polynomial factors when the cluster size is allowed to have general scalings. In fact, it is within logarithmic factors of known lower bounds for spectral methods, and there is evidence suggesting that no polynomial time algorithm would do significantly better. We then show that this guarantee carries over to a more general extension of the stochastic block model. Our method can handle the settings of semi-random graphs, heterogeneous degree distributions, unequal cluster sizes, unaffiliated nodes, partially observed graphs and planted clique/coloring etc. In particular, our results provide the best exact recovery guarantees to date for the planted partition, planted k-disjoint-cliques and planted noisy coloring models with general cluster sizes; in other settings, we match the best existing results up to logarithmic factors.

I. INTRODUCTION

The paper introduces a convex relaxation of maximum likelihood for graph clustering and analyzes it under broad stochastic and semi-random models. It targets difficult graphs with sparse, heterogeneous, small, or weakly separated clusters and reports stronger exact-recovery guarantees than existing methods in several settings.

  • Motivation: Graph clustering seeks disjoint node groups with denser within-cluster than across-cluster edges, supporting applications such as community detection and recommendation.The paper motivates this task using similarity relationships and social-network communities.
  • Challenges: Modern graphs complicate clustering through small density gaps, sparsity, growing numbers of clusters, unaffiliated nodes, and heterogeneous structure.These characteristics reduce signal, information, or model fit, making the underlying clustering harder to detect.
  • Method: The proposed method convexifies the maximum-likelihood estimator by replacing combinatorial cluster-matrix constraints with a convex program.The likelihood becomes linear in the cluster matrix, but the original optimization is generally intractable.
  • Results: The analysis covers a semi-random generalized stochastic blockmodel and extends to planted partition, disjoint-clique, dense-subgraph, and coloring models.The generalized setting permits broader structural variation than the standard stochastic blockmodel.
  • Results: For general cluster-size scalings, the method improves existing exact-recovery methods by polynomial factors in standard planted partition, disjoint-clique, and noisy-coloring models.The paper states that it matches existing methods up to logarithmic factors more broadly and succeeds over a larger parameter range in these cases.
  • Scope: The algorithm can additionally handle unaffiliated nodes, heterogeneity, hierarchical structure, planted clique, and planted noisy coloring.The paper also describes applications to other graph-clustering settings beyond the standard model.

A. Remarks about the Algorithm

The algorithm is derived from a standard stochastic-blockmodel relaxation but is analyzed in a generalized and semi-random setting. Its resolution parameter and model allow heterogeneous probabilities, unequal cluster sizes, unaffiliated nodes, and adversarial edge modifications.

  • Algorithm: The algorithm can be run on a given graph using an appropriate choice of t, with c_A and c_Ac determined accordingly.The paper notes that its guarantees apply beyond the model used to derive the method.
  • Algorithm: The convex formulation is one relaxation among alternatives using nuclear-norm, spectral, positive-semidefinite, and linear constraints.The paper focuses on its original formulation because guarantees transfer to tighter alternative relaxations without order-wise better theoretical guarantees.
  • Resolution parameter: The parameter t acts as the clustering resolution and should lie between p and q in the general setting.It resolves whether the intended target is a higher-level cluster or a denser subcluster in hierarchical structure.
  • GSBM: The generalized stochastic blockmodel separates clustered nodes from unaffiliated nodes and permits lower or upper bounds on in-cluster and cross-cluster edge probabilities.This supports heterogeneous degrees and nested clusters.
  • Semi-random GSBM: In the semi-random model, an adversary may add or remove within-cluster and cross-cluster edges according to whether p exceeds or falls below q.The objective remains recovery of the underlying true clusters.
  • GSBM: The minimum cluster size K is a lower bound, allowing clusters to have unequal sizes.The standard stochastic blockmodel is recovered when unaffiliated nodes are absent and clusters and probabilities are uniform.
  • Semi-random GSBM: The algorithm succeeds on the semi-random GSBM whenever it succeeds on the corresponding GSBM with the same parameters.This establishes inherent robustness to the permitted adversarial modifications.

A. Special Cases

The paper’s convex program applies across multiple planted graph models and remains robust to semi-random perturbations. Its guarantees cover heterogeneous graphs, many clusters, unaffiliated nodes, and broad parameter scalings, with near-matching lower-bound evidence in key regimes.

  • Generalized model: GSBM includes planted clique, planted dense subgraph, planted partition, planted coloring, and planted noisy coloring as special cases.The cases are determined by parameter choices and whether p exceeds or falls below q.
  • Semi-random robustness: The algorithm is robust to semi-random changes that add within-cluster edges or remove across-cluster edges aligned with the true clustering.Under these perturbations, success on the GSBM implies success on the semi-random GSBM with matching parameters.
  • Main guarantee: The convex program recovers the true cluster matrix as its unique optimum with probability at least 1 − 4n−8 when the theorem’s conditions on t and model parameters hold.The threshold must satisfy 1/4p + 3/4q ≤ t ≤ 3/4p + 1/4q; the theorem quantifies dependence on p, q, K, and unaffiliated nodes.
  • Tightness: When K = Θ(n), the guarantee is optimal up to logarithmic factors for all p and q, while smaller clusters require K = Ω(√n).The smaller-cluster scaling is connected to the planted clique case, where finding cliques of size o(√n) is widely believed computationally hard.
  • Scalability and heterogeneity: The method supports up to r = Θ(√n) equal-sized clusters when p − q = Θ(1), and can tolerate n2 = Θ(n) unaffiliated nodes.It also addresses non-uniform edge probabilities and node degrees through the GSBM formulation.

C. Consequences and Comparison with Literature

The method matches existing exact-recovery results up to logarithmic factors and achieves polynomially stronger guarantees in several planted models and scaling regimes.

  • Comparison with Literature: The results match the best existing guarantees up to logarithmic factors and are stronger in important parameter settings.The comparison includes planted coloring and planted r-cut under the generalized model.
  • Standard Stochastic Blockmodel: Polynomial-factor improvements hold for general p, q, and K, enabling recovery in noisier and sparser graphs as r grows.The result applies when cluster size and the number of clusters scale with n.
  • Planted r-Disjoint-Cliques Problem: The planted r-disjoint-cliques guarantee succeeds with probability at least 1−4n−8 under the stated Corollary 1 condition.For r = 1 and q = 1/2, it recovers planted cliques of size K = Ω(√n).
  • The p < q Case: Corollary 2 extends the algorithm to p < q by complementing the graph, converting densities to p′ = 1 −p and q′ = 1 −q.The transformed instance satisfies p′ > q′, allowing Theorem 1 to apply.
  • Planted Coloring: For planted coloring, the method succeeds when q = Ω(n/K^2 + log^4 n), matching prior algorithms for K = O(n/log^4(n)).For larger K, the result is within a few logarithmic factors of existing guarantees.

5) Clustering Partially Observed Graphs:

The paper extends clustering guarantees to partially observed graphs and describes spectral estimation of model parameters for the standard stochastic blockmodel.

  • Clustering Partially Observed Graphs: Partial observation is modeled by independently erasing each graph entry with probability 1−s after graph generation.Here s is the observation probability, and the algorithm is applied to the resulting observed matrix A′′.
  • Clustering Partially Observed Graphs: Corollary 3 matches the best known partially observed result up to a logarithmic factor and supports more general p and q values.It is order-wise better than a zero-imputation method whenever K ≲n/log^4 n.
  • Estimating t in Special Cases: In the standard equal-size blockmodel, eigenvalue gaps estimate r and K, while the leading eigenvalues estimate p and q.The implementation replaces E[A] with the observed adjacency matrix A.
  • Estimating t in Special Cases: Algorithm 2 computes and sorts the eigenvalues, selects the largest gap to estimate r, and sets K = n/r.It then uses the first two estimated eigenvalues to calculate p and q.
  • Estimating t in Special Cases: Under the stated condition, parameter estimation errors are sufficiently small and the estimated t satisfies Theorem 1’s condition.Combining the estimation theorem with Theorem 1 yields cluster recovery without knowing the generative parameters.

V. EMPIRICAL RESULTS

Experiments evaluate the convex program and its ALM implementation on synthetic and NIPS co-authorship graphs, revealing stronger statistical performance but higher computational cost than simpler methods.

  • Implementation Issues: The convex program is solved efficiently with an Augmented Lagrange Multiplier method because general-purpose SDP solvers scale poorly beyond a few hundred nodes.The ALM method uses weighted nuclear-norm plus ℓ1-norm optimization.
  • Implementation Issues: The ALM method is observed to converge Q-linearly, using residual 10−2 as the stopping criterion.Its main computational bottleneck is an SVD at each iteration, with Θ(n^2) memory usage.
  • Simulations: On synthetic graphs, the method succeeds over a strictly larger range of (p, q) than SLINK, spectral clustering, and L+S.For sparse graphs with p ≤0.3 and q ≤0.1, SLINK and L+S fail completely while the proposed method outperforms spectral clustering.
  • Simulations: The proposed and L+S convex methods require more computational time than spectral clustering and SLINK.The experiments therefore expose a tradeoff between statistical and computational performance.
  • Simulations: The NIPS dataset contains 2037 authors and 1740 papers, producing a sparse authorship graph with overall edge density 0.002.All methods are evaluated under a forced partition into r = 8 clusters using in-cluster and cross-cluster densities.

VII. PROOF OF THEOREM 1

The proof establishes recovery through monotonicity, homogeneous-model reduction, and dual-certificate conditions for convex-program optimality.

  • Proof Strategy: The proof is organized into three main steps and uses high probability to mean at least 1−4n−12.This probability convention applies throughout the theorem proof.
  • Proof Strategy: Monotonicity reduces heterogeneous edge probabilities to the homogeneous case by showing that added in-cluster edges and removed cross-cluster edges preserve success.Thus heterogeneous probabilities can only increase the success probability relative to uniform p and q.
  • Optimality Conditions: The argument characterizes matrix supports, projections, norms, and nuclear-norm subgradients to compare feasible alternatives with the true cluster matrix.These objects establish inequalities sufficient for optimality.
  • Optimality Conditions: A dual certificate provides sufficient conditions for the true cluster matrix to be the unique optimum of the convex program.The proof uses an approximate certificate because exact conditions are difficult to satisfy and do not guarantee uniqueness.

C. Step 3: Constructing W

The proof constructs W as a sum of four matrices designed to satisfy Proposition 1’s conditions with high probability. The resulting conditions establish unique optimality of Y*.

  • C. Step 3: Constructing W: W is decomposed as W1 + W2 + W3 + W4, with W4 accounting specifically for unaffiliated nodes.W4 is diagonal and has nonzero diagonal entries exactly on unaffiliated nodes.
  • C. Step 3: Constructing W: W1, W2, and W3 combine equality-derived terms with zero-mean random terms intended to keep their norms small.The zero-mean structure follows from randomness in A and supports conditions (a) and (b).
  • C. Step 3: Constructing W: Proposition 2 states that the constructed W satisfies Proposition 1 conditions (a)–(c) with high probability under Theorem 1’s conditions.This proposition is used to establish Theorem 1.
  • C. Step 3: Constructing W: The objective difference is strictly negative for every feasible perturbation D ≠ 0, proving that Y* is the unique optimal solution.The argument uses the projection decomposition and sign restrictions imposed by feasibility.

E. Proof of Proposition 2

The proof verifies Proposition 2 by bounding W and its projection, then checking the remaining inequalities in Proposition 1. These bounds rely on concentration properties of the random matrix components and parameter conditions from Theorem 1.

  • E. Proof of Proposition 2: The parameter conditions imply p(1 − q) ≥ t(1 − t), together with lower bounds involving max{t, 1 − t}.These inequalities are used to control the random-matrix terms in the proof.
  • E. Proof of Proposition 2: W1, W2, and W3 are symmetric random matrices with independent zero-mean entries whose supports, magnitudes, and variances are bounded.These properties permit standard random-matrix and concentration bounds.
  • E. Proof of Proposition 2: The proof proceeds in three sub-steps corresponding to the three conditions in Proposition 1.It first bounds ∥W∥, then ∥P_T W∥∞, and finally checks the equalities and inequalities in condition (c).
  • E. Proof of Proposition 2: Standard spectral-norm bounds and Bernstein’s inequality control ∥W∥ and ∥P_T W∥∞ with high probability.The projection bound uses entrywise concentration followed by a union bound.
  • E. Proof of Proposition 2: W4 contributes no term to one projected component because it is diagonal and supported on R^c, while the relevant projection is supported on R.The remaining projected terms are combined to obtain the required infinity-norm bound.
  • E. Proof of Proposition 2: The equalities in condition (c) follow from W’s definition, and the inequalities follow from p ≥ t, p ≤ 4t, and related parameter bounds.This completes the verification of Proposition 2.

VIII. PROOF OF THEOREM 2

The proof derives an information-theoretic lower bound using Fano’s inequality for recovering uniformly random equal-sized clusterings under the generalized stochastic block model. It bounds the mutual information between the graph and the planted cluster matrix.

  • VIII. PROOF OF THEOREM 2: The argument considers all assignments of n nodes into equal-sized clusters and lets the planted cluster matrix be uniformly random over them.The graph is then generated according to the GSBM with uniform edge probabilities.
  • VIII. PROOF OF THEOREM 2: Fano’s inequality relates the recovery error of any measurable estimator to the cardinality of the clustering family and the mutual information I(A; Y*).This provides the information-theoretic framework for the lower bound.
  • VIII. PROOF OF THEOREM 2: The mutual information is analyzed through entropy and conditional independence of edge variables under the uniform distribution of Y*.The proof reduces the information calculation to divergences involving representative edge distributions.
  • VIII. PROOF OF THEOREM 2: The resulting divergence bound yields the stated recovery lower-bound condition, completing the theorem.The proof requires the final right-hand side to be less than 1/n for sufficiently large n.

IX. PROOF OF THEOREM 3

The proof analyzes spectral estimation by bounding the noise matrix A − E[A] and applying Weyl’s inequality to the eigenvalues. The resulting eigengap identifies the number and size of clusters, while the edge probabilities are estimated separately.

  • IX. PROOF OF THEOREM 3: The noise matrix A − E[A] has independent, bounded, zero-mean entries with variance at most p(1 − q).Under Theorem 3’s condition, a random-matrix norm bound applies with high probability.
  • IX. PROOF OF THEOREM 3: The population eigenvalues separate the cluster-related eigenvalues from the remaining eigenvalues through terms involving K(p − q).The proof uses these eigenvalue expressions to estimate the number of clusters.
  • IX. PROOF OF THEOREM 3: The eigengap satisfies ˆλr − ˆλr+1 > K(p − q)/2, while other consecutive gaps are smaller under the stated conditions.This guarantees ˆr = r and consequently ˆK = K.
  • IX. PROOF OF THEOREM 3: The proof then bounds the estimation error of ˆq and uses the resulting estimates of ˆp and ˆq to choose t.The two sides of the interval for t are obtained from the corresponding parameter bounds.

X. CONCLUSION

The paper presents a convex optimization method for semi-random generalized stochastic blockmodels and reports broad theoretical and empirical effectiveness. It also identifies faster implementations, better rounding, online clustering, and broader model classes as future work.

  • X. CONCLUSION: The method is a convexification of the maximum likelihood estimator for a semi-random Generalized Stochastic Blockmodel.The formulation is designed for clustered random graphs and recovers many classical generative models.
  • X. CONCLUSION: Theoretical analysis guarantees correct cluster recovery across a wide range of problem parameters.The method succeeds under less restrictive conditions than existing methods in this setting.
  • X. CONCLUSION: Experiments validate the effectiveness of the proposed method.
  • X. CONCLUSION: Future work includes faster implementations, improved postprocessing or rounding, online clustering, and extensions to overlapping clusters and non-uniform densities.The proposed extensions go beyond the models currently analyzed.

APPENDIX

The appendix records two standard technical tools used in the theoretical proofs: a spectral-norm bound for random symmetric matrices and Bernstein’s inequality for sums of independent random variables.

  • APPENDIX: The first appendix lemma provides a standard spectral-norm bound for a random symmetric matrix.Its assumptions involve independent mean-zero entries with bounded variance and absolute magnitude.
  • APPENDIX: The proof of the first lemma follows the proof of a cited theorem, aside from the matrix being symmetric.
  • APPENDIX: The second appendix lemma restates Bernstein’s inequality for sums of independent random variables.The variables are independently bounded and have variance bounded by σ^2.
Loading 1210.3335v3…