Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this phenomenon, we study a classical SDP relaxation of the minimum graph bisection problem, when applied to Erd o s-Renyi random graphs with bounded average degree @math , and obtain several types of results. First, we use a dual witness construction (using the so-called non-backtracking matrix of the graph) to upper bound the SDP value. Second, we prove that a simple local algorithm approximately solves the SDP to within a factor @math of the upper bound. In particular, the local algorithm is at most @math suboptimal, and @math suboptimal for large degree. We then analyze a more sophisticated local algorithm, which aggregates information according to the harmonic measure on the limiting Galton-Watson (GW) tree. The resulting lower bound is expressed in terms of the conductance of the GW tree and matches surprisingly well the empirically determined SDP values on large-scale Erd o s-Renyi graphs. We finally consider the planted partition model. In this case, purely local algorithms are known to fail, but they do succeed if a small amount of side information is available. Our results imply quantitative bounds on the threshold for partial recovery using SDP in this model.
Several papers applied sophisticated spectral methods to the stochastic block model near the detection threshold @cite_37 @cite_29 @cite_39 . Our upper bound in Theorem is based on a duality argument, where we establish feasibility of a certain dual witness construction using an argument similar to @cite_39 .
@cite_37 @cite_29 @cite_39
2023348178 1737288045 2073261148 1526954821
[1] conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from the stochastic block model. Mossel, Neeman and Sly [2] established the negative part of the conjecture, proving impossibility of non-trivial reconstruction below the threshold. In this work we solve the positive part of the conjecture. To that end we introduce a modified adjacency matrix B which counts self-avoiding paths of a given length e between pairs of nodes. We then prove that for logarithmic length e, the leading eigenvectors of this modified matrix provide a non-trivial reconstruction of the underlying structure, thereby settling the conjecture. A key step in the proof consists in establishing a weak Ramanujan property of the constructed matrix B. Namely, the spectrum of B consists in two leading eigenvalues ρ(B), λ2 and n -- 2 eigenvalues of a lower order O(ne √ρ(B) for all e 0, ρ(B) denoting B's spectral radius. New phase transition phenomena have recently been discovered for the stochastic block model, for the special case of two non-overlapping symmetric communities. This gives raise in particular to new algorithmic challenges driven by the thresholds. This paper investigates whether a general phenomenon takes place for multiple communities, without imposing symmetry. In the general stochastic block model @math , @math vertices are split into @math communities of relative size @math , and vertices in community @math and @math connect independently with probability @math . This paper investigates the partial and exact recovery of communities in the general SBM (in the constant and logarithmic degree regimes), and uses the generality of the results to tackle overlapping communities. The contributions of the paper are: (i) an explicit characterization of the recovery threshold in the general SBM in terms of a new divergence function @math , which generalizes the Hellinger and Chernoff divergences, and which provides an operational meaning to a divergence function analog to the KL-divergence in the channel coding theorem, (ii) the development of an algorithm that recovers the communities all the way down to the optimal threshold and runs in quasi-linear time, showing that exact recovery has no information-theoretic to computational gap for multiple communities, in contrast to the conjectures made for detection with more than 4 communities; note that the algorithm is optimal both in terms of achieving the threshold and in having quasi-linear complexity, (iii) the development of an efficient algorithm that detects communities in the constant degree regime with an explicit accuracy bound that can be made arbitrarily close to 1 when a prescribed signal-to-noise ratio (defined in term of the spectrum of @math ) tends to infinity. We prove the existence of an asymptotic phase transition threshold on community detectability for the spectral modularity method [M. E. J. Newman, Phys. Rev. E 74, 036104 (2006) and Proc. National Academy of Sciences. 103, 8577 (2006)] under a stochastic block model. The phase transition on community detectability occurs as the inter-community edge connection probability @math grows. This phase transition separates a sub-critical regime of small @math , where modularity-based community detection successfully identifies the communities, from a super-critical regime of large @math where successful community detection is impossible. We show that, as the community sizes become large, the asymptotic phase transition threshold @math is equal to @math , where @math is the within-community edge connection probability. Thus the phase transition threshold is universal in the sense that it does not depend on the ratio of community sizes. The universal phase transition phenomenon is validated by simulations for moderately sized communities. Using the derived expression for the phase transition threshold we propose an empirical method for estimating this threshold from real-world data. We consider the problem of community detection in the Stochastic Block Model with a finite number @math of communities of sizes linearly growing with the network size @math . This model consists in a random graph such that each pair of vertices is connected independently with probability @math within communities and @math across communities. One observes a realization of this random graph, and the objective is to reconstruct the communities from this observation. We show that under spectral algorithms, the number of misclassified vertices does not exceed @math with high probability as @math grows large, whenever @math , @math and where @math and @math denote the (fixed) proportions of vertices in the two smallest communities. In view of recent work by and , this establishes that the proposed spectral algorithms are able to exactly recover communities whenever this is at all possible in the case of networks with two communities with equal sizes. We conjecture that condition (1) is actually necessary to obtain less than @math misclassified vertices asymptotically, which would establish the optimality of spectral method in more general scenarios.