text: We study the statistical performance of semidefinite programming (SDP) relaxations for clustering under random graph models. Under the @math Synchronization model, Censored Block Model and Stochastic Block Model, we show that SDP achieves an error rate of the form [ [- (1-o(1) ) n I^* ]. ] Here @math is an appropriate multiple of the number of nodes and @math is an information-theoretic measure of the signal-to-noise ratio. We provide matching lower bounds on the Bayes error for each model and therefore demonstrate that the SDP approach is Bayes optimal. As a corollary, our results imply that SDP achieves the optimal exact recovery threshold under each model. Furthermore, we show that SDP is robust: the above bound remains valid under semirandom versions of the models in which the observed graph is modified by a monotone adversary. Our proof is based on a novel primal-dual analysis of SDP under a unified framework for all three models, and the analysis shows that SDP tightly approximates a joint majority voting procedure.
  @cite_35: 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.
  @cite_37: In this paper, we consider the cluster estimation problem under the stochastic block model. We show that the semidefinite programming (SDP) formulation for this problem achieves an error rate that decays exponentially in the signal-to-noise ratio. The error bound implies weak recovery in the sparse graph regime with bounded expected degrees as well as exact recovery in the dense regime. An immediate corollary of our results yields error bounds under the censored block model. Moreover, these error bounds are robust, continuing to hold under heterogeneous edge probabilities and a form of the so-called monotone attack. Significantly, this error rate is achieved by the SDP solution itself without any further pre- or post-processing and improves upon existing polynomially decaying error bounds proved using the Grothendieck’s inequality. Our analysis builds on two key ingredients: 1) showing that the graph has a well-behaved spectrum, even in the sparse regime, after discounting an exponentially small number of edges and 2) an order-statistics argument that governs the final error rate. Both arguments highlight the implicit regularization effect of the SDP formulation.
  @cite_51: 
  @cite_54: We investigate the clustering performances of the relaxed @math means in the setting of sub-Gaussian Mixture Model (sGMM) and Stochastic Block Model (SBM). After identifying the appropriate signal-to-noise ratio (SNR), we prove that the misclassification error decay exponentially fast with respect to this SNR. These partial recovery bounds for the relaxed @math means improve upon results currently known in the sGMM setting. In the SBM setting, applying the relaxed @math means SDP allows to handle general connection probabilities whereas other SDPs investigated in the literature are restricted to the assortative case (where within group probabilities are larger than between group probabilities). Again, this partial recovery bound complements the state-of-the-art results. All together, these results put forward the versatility of the relaxed @math means.
  @cite_39: Resolving a conjecture of Abbe, Bandeira, and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model (SBM) of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper, it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: 1) binary SBM with two clusters of sizes proportional to network size but not necessarily equal; 2) SBM with a fixed number of equal-sized clusters; and 3) binary censored block model with the background graph being Erdős–Renyi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection.
  @cite_44: Community detection, which aims to cluster @math nodes in a given graph into @math distinct groups based on the observed undirected edges, is an important problem in network data analysis. In this paper, the popular stochastic block model (SBM) is extended to the generalized stochastic block model (GSBM) that allows for adversarial outlier nodes, which are connected with the other nodes in the graph in an arbitrary way. Under this model, we introduce a procedure using convex optimization followed by @math -means algorithm with @math . Both theoretical and numerical properties of the method are analyzed. A theoretical guarantee is given for the procedure to accurately detect the communities with small misclassification rate under the setting where the number of clusters can grow with @math . This theoretical result admits to the best-known result in the literature of computationally feasible community detection in SBM without outliers. Numerical results show that our method is both computationally fast and robust to different kinds of outliers, while some popular computationally fast community detection algorithms, such as spectral clustering applied to adjacency matrices or graph Laplacians, may fail to retrieve the major clusters due to a small portion of outliers. We apply a slight modification of our method to a political blogs data set, showing that our method is competent in practice and comparable to existing computationally feasible methods in the literature. To the best of the authors' knowledge, our result is the first in the literature in terms of clustering communities with fast growing numbers under the GSBM where a portion of arbitrary outlier nodes exist.
  @cite_23: 
  @cite_49: Denote by A the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing over the set of positive semidefinite matrices X with diagonal entries X_ii=1. We prove that for large (bounded) average degree d, the value of this semidefinite program (SDP) is --with high probability-- 2n*sqrt(d) + n, o(sqrt(d))+o(n). For a random regular graph of degree d, we prove that the SDP value is 2n*sqrt(d-1)+o(n), matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size n 2, with edge probability a n (within group) and b n (across). We prove that SDP detects the partition with high probability provided (a-b)^2 (4d)> 1+o_d(1), with d= (a+b) 2. By comparison, the information theoretic threshold for detecting the hidden partition is (a-b)^2 (4d)> 1: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: (i) A new 'higher-rank' Grothendieck inequality for symmetric matrices; (ii) An interpolation method inspired from statistical physics; (iii) An analysis of the eigenvectors of deformed Gaussian random matrices.
  @cite_59: Given a background graph with n vertices, the binary censored block model assumes that vertices are partitioned into two clusters, and every edge is labeled independently at random with labels drawn from Bern(1 − e) if two endpoints are in the same cluster, or from Bern(e) otherwise, where e ∈ [0; 1 2] is a fixed constant. For Erdős-Renyi graphs with edge probability p = a log n n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold equation for exactly recovering the partition from the labeled graph with probability tending to one as n → ∞. For random regular graphs with degree scaling as a log n, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1 2)∥Bern(e)) > 1, where D denotes the Kullback-Leibler divergence.
  @cite_5: We consider the problem of estimating the discrete clustering structures under Sub-Gaussian Mixture Models. Our main results establish a hidden integrality property of a semidefinite programming (SDP) relaxation for this problem: while the optimal solutions to the SDP are not integer-valued in general, their estimation errors can be upper bounded in terms of the error of an idealized integer program. The error of the integer program, and hence that of the SDP, are further shown to decay exponentially in the signal-to-noise ratio. To the best of our knowledge, this is the first exponentially decaying error bound for convex relaxations of mixture models, and our results reveal the "global-to-local" mechanism that drives the performance of the SDP relaxation. A corollary of our results shows that in certain regimes the SDP solutions are in fact integral and exact, improving on existing exact recovery results for convex relaxations. More generally, our results establish sufficient conditions for the SDP to correctly recover the cluster memberships of @math fraction of the points for any @math . As a special case, we show that under the @math -dimensional Stochastic Ball Model, SDP achieves non-trivial (sometimes exact) recovery when the center separation is as small as @math , which complements previous exact recovery results that require constant separation.
  @cite_46: We consider the problem of identifying underlying community-like structures in graphs. Toward this end, we study the stochastic block model (SBM) on k-clusters: a random model on n = km vertices, partitioned in k equal sized clusters, with edges sampled independently across clusters with probability q and within clusters with probability p, p > q. The goal is to recover the initial “hidden” partition of [n]. We study semidefinite programming (SDP)-based algorithms in this context. In the regime (p = (m) m ) and (q = (m) m ), we show that a certain natural SDP-based algorithm solves the problem of exact recovery in the k-community SBM, with high probability, whenever ( - > 1 ), as long as (k=o( n) ). This threshold is known to be the information theoretically optimal. We also study the case when (k= ( (n)) ). In this case however, we achieve recovery guarantees that no longer match the optimal condition ( - > 1 ), thus leaving achieving optimality for this range an open question.
  @cite_16: The stochastic block model is one of the oldest and most ubiquitous models for studying clustering and community detection. In an exciting sequence of developments, motivated by deep but non-rigorous ideas from statistical physics, conjectured a sharp threshold for when community detection is possible in the sparse regime. Mossel, Neeman and Sly and Massoulie proved the conjecture and gave matching algorithms and lower bounds. Here we revisit the stochastic block model from the perspective of semirandom models where we allow an adversary to make helpful' changes that strengthen ties within each community and break ties between them. We show a surprising result that these helpful' changes can shift the information-theoretic threshold, making the community detection problem strictly harder. We complement this by showing that an algorithm based on semidefinite programming (which was known to get close to the threshold) continues to work in the semirandom model (even for partial recovery). This suggests that algorithms based on semidefinite programming are robust in ways that any algorithm meeting the information-theoretic threshold cannot be. These results point to an interesting new direction: Can we find robust, semirandom analogues to some of the classical, average-case thresholds in statistics? We also explore this question in the broadcast tree model, and we show that the viewpoint of semirandom models can help explain why some algorithms are preferred to others in practice, in spite of the gaps in their statistical performance on random models.
  @cite_10: The largest eigenvalue of a matrix is always larger or equal than its largest diagonal entry. We show that for a class of random Laplacian matrices with independent off-diagonal entries, this bound is essentially tight: the largest eigenvalue is, up to lower order terms, often the size of the largest diagonal. entry. Besides being a simple tool to obtain precise estimates on the largest eigenvalue of a class of random Laplacian matrices, our main result settles a number of open problems related to the tightness of certain convex relaxation-based algorithms. It easily implies the optimality of the semidefinite relaxation approaches to problems such as ( Z _2 ) Synchronization and stochastic block model recovery. Interestingly, this result readily implies the connectivity threshold for Erdős–Renyi graphs and suggests that these three phenomena are manifestations of the same underlying principle. The main tool is a recent estimate on the spectral norm of matrices with independent entries by van Handel and the author.
summary: For SBM, SDP has been proven to succeed in exact and weak recovery above the corresponding optimal thresholds (sometimes under additional assumptions). In particular, see @cite_46 @cite_10 @cite_23 for exact recovery, and @cite_49 for weak recovery. Prior to our work, SDP was not known to achieve the optimal error rate between the exact and weak recovery regimes. Sub-optimal polynomial rates are first proved in @cite_35 , later improved to exponential in @cite_37 , and further generalized in @cite_5 @cite_54 . Robustness has been recognized as a distinct feature of the SDP approach as compared to other more specialized algorithms for SBMs. Work in this direction has established robustness of SDP against random erasures @cite_59 @cite_39 , atypical node degrees @cite_35 and adversarial corruptions @cite_23 @cite_49 @cite_44 @cite_51 . The work in @cite_16 investigates the relationship between statistical optimality and robustness under monotone semirandom models; we revisit this result in more details later.