{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T16:05:14Z","timestamp":1750349114319,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,1,14]],"date-time":"2016-01-14T00:00:00Z","timestamp":1452729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["328025"],"award-info":[{"award-number":["328025"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DOD ONR Grant","award":["N00014-14-1-0823"],"award-info":[{"award-number":["N00014-14-1-0823"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,1,14]]},"DOI":"10.1145\/2840728.2840749","type":"proceedings-article","created":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T14:26:11Z","timestamp":1452003971000},"page":"71-80","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Local Algorithms for Block Models with Side Information"],"prefix":"10.1145","author":[{"given":"Elchanan","family":"Mossel","sequence":"first","affiliation":[{"name":"University of Pennsylvania & University of California, Berkeley, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaming","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,1,14]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"October","author":"Abbe E.","year":"2014","unstructured":"E. Abbe , A. S. Bandeira , and G. Hall . Exact recovery in the stochastic block model. arXiv 1405.3267 , October 2014 . E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. arXiv 1405.3267, October 2014."},{"key":"e_1_3_2_1_2_1","volume-title":"March","author":"Abbe E.","year":"2015","unstructured":"E. Abbe and C. Sandon . Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. arXiv 1503.00609 , March , 2015 . E. Abbe and C. Sandon. Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms. arXiv 1503.00609, March, 2015."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1209\/0295-5075\/90\/18002"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.5555\/2627435.2670323"},{"key":"e_1_3_2_1_5_1","volume-title":"April","author":"Bandeira A.","year":"2015","unstructured":"A. Bandeira . Random Laplacian matrices and convex relaxations. arXiv 1504.03987 , April , 2015 . A. Bandeira. Random Laplacian matrices and convex relaxations. arXiv 1504.03987, April, 2015."},{"key":"e_1_3_2_1_6_1","first-page":"27","volume-title":"ICML","volume":"2","author":"Basu S.","year":"2002","unstructured":"S. Basu , A. Banerjee , and R. J. Mooney . Semi-supervised clustering by seeding . In ICML , volume 2 , pages 27 -- 34 , 2002 . S. Basu, A. Banerjee, and R. J. Mooney. Semi-supervised clustering by seeding. In ICML, volume 2, pages 27--34, 2002."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/1014052.1014062"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1073\/pnas.0907096106"},{"key":"e_1_3_2_1_9_1","volume-title":"January","author":"Bordenave C.","year":"2015","unstructured":"C. Bordenave , M. Lelarge , and L. Massouli\u00e9 . Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. ArXiv 1501.06087 , January 2015 . C. Bordenave, M. Lelarge, and L. Massouli\u00e9. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. ArXiv 1501.06087, January 2015."},{"key":"e_1_3_2_1_10_1","volume-title":"Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. arXiv preprint arXiv:1404.6000","author":"Cai T.","year":"2014","unstructured":"T. Cai and X. Li . Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. arXiv preprint arXiv:1404.6000 , 2014 . T. Cai and X. Li. Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. arXiv preprint arXiv:1404.6000, 2014."},{"key":"e_1_3_2_1_11_1","first-page":"585","volume-title":"NIPS","author":"Chapelle O.","year":"2002","unstructured":"O. Chapelle , J. Weston , and B. Schoelkopf . Cluster kernels for semi-supervised learning . In NIPS , pages 585 -- 592 , 2002 . O. Chapelle, J. Weston, and B. Schoelkopf. Cluster kernels for semi-supervised learning. In NIPS, pages 585--592, 2002."},{"key":"e_1_3_2_1_12_1","volume-title":"Improved graph clustering","author":"Chen Y.","year":"2012","unstructured":"Y. Chen , S. Sanghavi , and H. Xu . Improved graph clustering . IEEE Transactions on Information Theory. An earlier version of this work appeared under the title \"Clustering Sparse Graphs\" at NIPS 2012 , 60(10): 6440--6455, Oct 2014. Y. Chen, S. Sanghavi, and H. Xu. Improved graph clustering. IEEE Transactions on Information Theory. An earlier version of this work appeared under the title \"Clustering Sparse Graphs\" at NIPS 2012, 60(10):6440--6455, Oct 2014."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of ICML 2014 (Also arXiv: 1402","author":"Chen Y.","year":"2014","unstructured":"Y. Chen and J. Xu . Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices . In Proceedings of ICML 2014 (Also arXiv: 1402 .1267), Feb 2014 . Y. Chen and J. Xu. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. In Proceedings of ICML 2014 (Also arXiv:1402.1267), Feb 2014."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.5555\/1070432.1070552"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1017\/S0963548309990514"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1002\/1098-2418(200103)18:2%3C116::AID-RSA1001%3E3.0.CO;2-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1103\/PhysRevE.84.066106"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1103\/PhysRevLett.107.065701"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1016\/0196-6774(89)90001-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1145\/2554797.2554831"},{"key":"e_1_3_2_1_21_1","volume-title":"Achieving optimal misclassification proportion in stochastic block model. arXiv:1505.03772","author":"Gao C.","year":"2015","unstructured":"C. Gao , Z. Ma , A. Y. Zhang , and H. H. Zhou . Achieving optimal misclassification proportion in stochastic block model. arXiv:1505.03772 , 2015 . C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou. Achieving optimal misclassification proportion in stochastic block model. arXiv:1505.03772, 2015."},{"key":"e_1_3_2_1_22_1","first-page":"1","volume-title":"Probability Theory and Related Fields","author":"Gu\u00e9don O.","year":"2015","unstructured":"O. Gu\u00e9don and R. Vershynin . Community detection in sparse networks via grothendieck's inequality . Probability Theory and Related Fields , pages 1 -- 25 , 2015 . O. Gu\u00e9don and R. Vershynin. Community detection in sparse networks via grothendieck's inequality. Probability Theory and Related Fields, pages 1--25, 2015."},{"key":"e_1_3_2_1_23_1","volume-title":"Nov.","author":"Hajek B.","year":"2014","unstructured":"B. Hajek , Y. Wu , and J. Xu . Achieving exact cluster recovery threshold via semidefinite programming. arXiv1 412.6156 , Nov. 2014 . B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming. arXiv1 412.6156, Nov. 2014."},{"key":"e_1_3_2_1_24_1","volume-title":"Achieving exact cluster recovery threshold via semidefinite programming: Extensions. arXiv:1502.07738","author":"Hajek B.","year":"2015","unstructured":"B. Hajek , Y. Wu , and J. Xu . Achieving exact cluster recovery threshold via semidefinite programming: Extensions. arXiv:1502.07738 , 2015 . B. Hajek, Y. Wu, and J. Xu. Achieving exact cluster recovery threshold via semidefinite programming: Extensions. arXiv:1502.07738, 2015."},{"key":"e_1_3_2_1_25_1","volume-title":"October","author":"Hajek B.","year":"2015","unstructured":"B. Hajek , Y. Wu , and J. Xu . Recovering a hidden community beyond the spectral limit in O(|E|\u0142og*|V|) time. arXiv 1510.02786 , October 2015 . B. Hajek, Y. Wu, and J. Xu. Recovering a hidden community beyond the spectral limit in O(|E|\u0142og*|V|) time. arXiv 1510.02786, October 2015."},{"key":"e_1_3_2_1_26_1","volume-title":"Limits of local-global convergent graph sequences. arXiv preprint arXiv:1205.4356","author":"Hatami H.","year":"2012","unstructured":"H. Hatami , L. Lov\u00e1sz , and B. Szegedy . Limits of local-global convergent graph sequences. arXiv preprint arXiv:1205.4356 , 2012 . H. Hatami, L. Lov\u00e1sz, and B. Szegedy. Limits of local-global convergent graph sequences. arXiv preprint arXiv:1205.4356, 2012."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1016\/0378-8733(83)90021-7"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1016\/S0166-218X(97)00133-9"},{"key":"e_1_3_2_1_29_1","first-page":"779","volume-title":"Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Kanade V.","year":"2014","unstructured":"V. Kanade , E. Mossel , and T. Schramm . Global and local information in clustering labeled block models . In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages 779 -- 810 , 2014 . V. Kanade, E. Mossel, and T. Schramm. Global and local information in clustering labeled block models. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 779--810, 2014."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1214\/aoms\/1177699139"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1016\/j.ejc.2011.03.008"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1145\/2591796.2591857"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.5555\/874063.875554"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198570837.001.0001","volume-title":"Information, Physics, and Computation","author":"Mezard M.","year":"2009","unstructured":"M. Mezard and A. Montanari . Information, Physics, and Computation . Oxford University Press, Inc. , New York, NY, USA , 2009 . M. Mezard and A. Montanari. Information, Physics, and Computation. Oxford University Press, Inc., New York, NY, USA, 2009."},{"key":"e_1_3_2_1_35_1","volume-title":"Feb","author":"Montanari A.","year":"2015","unstructured":"A. Montanari . Finding one community in a sparse random graph. arXiv 1502.05680 , Feb 2015 . A. Montanari. Finding one community in a sparse random graph. arXiv 1502.05680, Feb 2015."},{"key":"e_1_3_2_1_36_1","volume-title":"Belief propogation, robust reconstruction, and optimal recovery of block models. arXiv 1309.1380","author":"Mossel E.","year":"2013","unstructured":"E. Mossel , J. Neeman , and A. Sly . Belief propogation, robust reconstruction, and optimal recovery of block models. arXiv 1309.1380 , 2013 . E. Mossel, J. Neeman, and A. Sly. Belief propogation, robust reconstruction, and optimal recovery of block models. arXiv 1309.1380, 2013."},{"key":"e_1_3_2_1_37_1","volume-title":"A proof of the block model threshold conjecture. arXiv 1311.4115","author":"Mossel E.","year":"2013","unstructured":"E. Mossel , J. Neeman , and A. Sly . A proof of the block model threshold conjecture. arXiv 1311.4115 , 2013 . E. Mossel, J. Neeman, and A. Sly. A proof of the block model threshold conjecture. arXiv 1311.4115, 2013."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1145\/2746539.2746603"},{"key":"e_1_3_2_1_39_1","volume-title":"Reconstruction and estimation in the planted partition model. To appear in Probability Theory and Related Fields. The Arxiv version of this paper is titled Stochastic Block Models and Reconstruction","author":"Mossel E.","year":"2015","unstructured":"E. Mossel , J. Neeman , and A. Sly . Reconstruction and estimation in the planted partition model. To appear in Probability Theory and Related Fields. The Arxiv version of this paper is titled Stochastic Block Models and Reconstruction , 2015 . E. Mossel, J. Neeman, and A. Sly. Reconstruction and estimation in the planted partition model. To appear in Probability Theory and Related Fields. The Arxiv version of this paper is titled Stochastic Block Models and Reconstruction, 2015."},{"key":"e_1_3_2_1_40_1","volume-title":"Sept.","author":"Mossel E.","year":"2015","unstructured":"E. Mossel and J. Xu . Density evolution in the degree-correlated stochastic block model. arXiv:1509.03281 , Sept. 2015 . E. Mossel and J. Xu. Density evolution in the degree-correlated stochastic block model. arXiv:1509.03281, Sept. 2015."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1145\/2840728.2840749"},{"key":"e_1_3_2_1_42_1","volume-title":"July","author":"Newman M. J.","year":"2015","unstructured":"M. J. Newman and A. Clauset . Structure and inference in annotated networks. arXiv:1507.04001 , July , 2015 . M. J. Newman and A. Clauset. Structure and inference in annotated networks. arXiv:1507.04001, July, 2015."},{"key":"e_1_3_2_1_43_1","volume-title":"A semidefinite program for unbalanced multisection in the stochastic block model. arXiv:1507.05605v1","author":"Perry W.","year":"2015","unstructured":"W. Perry and A. S. Wein . A semidefinite program for unbalanced multisection in the stochastic block model. arXiv:1507.05605v1 , 2015 . W. Perry and A. S. Wein. A semidefinite program for unbalanced multisection in the stochastic block model. arXiv:1507.05605v1, 2015."},{"key":"e_1_3_2_1_44_1","volume-title":"Local algorithms for independent sets are half-optimal. arXiv preprint arXiv:1402.0485","author":"Rahman M.","year":"2014","unstructured":"M. Rahman and B. Virag . Local algorithms for independent sets are half-optimal. arXiv preprint arXiv:1402.0485 , 2014 . M. Rahman and B. Virag. Local algorithms for independent sets are half-optimal. arXiv preprint arXiv:1402.0485, 2014."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_45_1","DOI":"10.5555\/1795974"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_46_1","DOI":"10.1007\/s003579900004"},{"key":"e_1_3_2_1_47_1","volume-title":"Phase transitions in community detection: A solvable toy model. arXiv 1312.0631","author":"Steeg G. Ver","year":"2013","unstructured":"G. Ver Steeg , C. Moore , A. Galstyan , and A. E. Allahverdyan . Phase transitions in community detection: A solvable toy model. arXiv 1312.0631 , 2013 . G. Ver Steeg, C. Moore, A. Galstyan, and A. E. Allahverdyan. Phase transitions in community detection: A solvable toy model. arXiv 1312.0631, 2013."},{"key":"e_1_3_2_1_48_1","volume-title":"Proceedings of The 27th Conference on Learning Theory","author":"Yun S.","year":"2014","unstructured":"S. Yun and A. Proutiere . Community detection via random and adaptive sampling . In Proceedings of The 27th Conference on Learning Theory , 2014 . S. Yun and A. Proutiere. Community detection via random and adaptive sampling. In Proceedings of The 27th Conference on Learning Theory, 2014."},{"key":"e_1_3_2_1_49_1","volume-title":"Accurate community detection in the stochastic block model via spectral algorithms. arXiv 1412.7335","author":"Yun S.-Y.","year":"2014","unstructured":"S.-Y. Yun and A. Proutiere . Accurate community detection in the stochastic block model via spectral algorithms. arXiv 1412.7335 , 2014 . S.-Y. Yun and A. Proutiere. Accurate community detection in the stochastic block model via spectral algorithms. arXiv 1412.7335, 2014."},{"key":"e_1_3_2_1_50_1","volume-title":"Minimax rates of community detection in stochastic block models. arXiv:1507.05313","author":"Zhang A. Y.","year":"2015","unstructured":"A. Y. Zhang and H. H. Zhou . Minimax rates of community detection in stochastic block models. arXiv:1507.05313 , 2015 . A. Y. Zhang and H. H. Zhou. Minimax rates of community detection in stochastic block models. arXiv:1507.05313, 2015."},{"key":"e_1_3_2_1_51_1","volume-title":"Comparitive study for inference of hidden classes in stochastic block models. Journal of Statistical Mechanics : Theory and Experiment","author":"Zhang P.","year":"2012","unstructured":"P. Zhang , F. Krzakala , J. Reichardt , and L. Zdeborov\u00e1 . Comparitive study for inference of hidden classes in stochastic block models. Journal of Statistical Mechanics : Theory and Experiment , 2012 . P. Zhang, F. Krzakala, J. Reichardt, and L. Zdeborov\u00e1. Comparitive study for inference of hidden classes in stochastic block models. Journal of Statistical Mechanics : Theory and Experiment, 2012."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_52_1","DOI":"10.1103\/PhysRevE.90.052802"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"ITCS'16","name":"ITCS'16: Innovations in Theoretical Computer Science","location":"Cambridge Massachusetts USA"},"container-title":["Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2840728.2840749","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2840728.2840749","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:53:47Z","timestamp":1750222427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2840728.2840749"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,14]]},"references-count":52,"alternative-id":["10.1145\/2840728.2840749","10.1145\/2840728"],"URL":"https:\/\/doi.org\/10.1145\/2840728.2840749","relation":{},"subject":[],"published":{"date-parts":[[2016,1,14]]},"assertion":[{"value":"2016-01-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}