188宝金博页面版

Local Algorithms for Block Models with Side Information[Extended Abstract]∗Elchanan MosselDepartment of StatisticsUniversity of Pennsylvania and U.C. Berkeleymossel@wharton.upenn.eduJiaming XuDepartment of StatisticsUniversity of Pennsylvaniajiamingx@wharton.upenn.eduABSTRACTThere has been a recent interest in understanding the powerof local algorithms for optimization and inference problemson sparse graphs. Gamarnik and Sudan (2014) showed thatlocal algorithms are weaker than global algorithms for f i nd-ing large independent sets in sparse random regular graphsthus refuting a conjecture by Hatami, Lovász, and Szegedy(2012). Montanari (2015) showed that local algorithms aresuboptimal for f i nding a community with high connectivityin the sparse Erd? os-R´ enyi random graphs. For the sym-metric planted partition problem (also named communitydetection for the block models) on sparse graphs, a simpleobservation is that local algorithms cannot have non-trivialperformance.In this work we consider the ef f ect of side information onlocal algorithms for community detection under the binarysymmetric stochastic block model. In the block model withside information each of the n vertices is labeled + or − in-dependently and uniformly at random; each pair of verticesis connected independently with probability a/n if both ofthem have the same label or b/n otherwise. The goal is toestimate the underlying vertex labeling given 1) the graphstructure and 2) side information in the form of a vertexlabeling positively correlated with the true one. Assumingthat the ratio between in and out degree a/b is Θ(1) andthe average degree (a + b)/2 = n o(1) , we show that a lo-cal algorithm, namely, belief propagation run on the localneighborhoods, maximizes the expected fraction of verticeslabeled correctly in the following three regimes:• |a − b| < 2 and all 0 < α < 1/2• (a − b) 2 > C(a + b) for some constant C and all 0 <α < 1/2• For all a,b if the probability that each given vertexlabel is incorrect is at most α ∗ for some constant α ∗ ∈(0,1/2).∗ A full version of this paper is available at arXiv:1508.02344.Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor prof i t or commercial advantage and that copies bear this notice and the full cita-tion on the f i rst page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-publish, to post on servers or to redistribute to lists, requires prior specif i c permissionand/or a fee. Request permissions from Permissions@acm.org.ITCS ’16 January 14–16, 2016, Cambridge, MA, USA2016 ACM ISBN 978-1-4503-4057-1/16/01 ...$15.00.http://dx.doi.org/10.1145/2840728.2840749.Thus, in contrast to the case of independent sets or a singlecommunity in random graphs and to the case of symmetricblock models without side information, we show that localalgorithms achieve optimal performance in the above threeregimes for the block model with side information.To complement our results, in the large degree limit a →∞, we give a formula of the expected fraction of vertices la-beled correctly by the local belief propagation, in terms of af i xed point of a recursion derived from the density evolutionanalysis with Gaussian approximations.Categories and Subject DescriptorsI.5.3 [PATTERN RECOGNITION]: Clustering—Algo-rithms; G.3 [PROBABILITY AND STATISTICS]: [Sta-tistical computing]KeywordsLocal algorithms; random graphs; community detection1. INTRODUCTIONIn this work we study the performance of local algorithmsfor community detection in sparse graphs thus combiningtwo lines of work which saw recent breakthroughs.The optimality of the performance of local algorithm foroptimization problems on large graphs was raised by Hatami,Lovász, and Szegedy [26] in the context of a theory of graphlimits for sparse graphs. The conjecture, regarding the op-timality for f i nding independent sets in random graphs wasrefuted by Gamarnik and Sudan [20]. More recently, localalgorithms are shown to be strictly suboptimal comparingto the maximum likelihood estimator for f i nding a commu-nity of higher connectivity than the background Erd? os-R´ enyirandom graph [35, 25].In a dif f erent direction, following a beautiful conjecturefrom physics [17], new ef f i cient algorithms for the stochas-tic block models (i.e. planted partition) were developed andshown to detect the blocks whenever this is information the-oretically possible [39, 37, 32, 9]. It is easy to (see e.g. [29])that no local algorithm with access to neighborhoods of ra-dius o(logn) can have non-trivial performance for this prob-lem.Our interest in this paper is in the application of localalgorithms for community detection with side informationon community structures. We show that unlike the cases ofindependent sets on regular graphs or the case of communitydetection on sparse random graphs, local algorithms do haveoptimal performance.71