Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T04:23:23.087Z Has data issue: false hasContentIssue false
  • English
  • Français

Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log*|V|) time

Part of: Decision theory Multivariate analysis

Published online by Cambridge University Press:  26 July 2018

Bruce Hajek ,
Yihong Wu  and
Jiaming Xu
Bruce Hajek*
Affiliation:
University of Illinois at Urbana-Champaign
Yihong Wu*
Affiliation:
Yale University
Jiaming Xu*
Affiliation:
Purdue University
*
* Postal address: Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA. Email address: [email protected]
** Postal address: Department of Statistics and Data Science, Yale University, New Haven, CT 06511, USA.
*** Postal address: Krannert School of Management, Purdue University, West Lafayette, IN 47907, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n1-o(1) ≤ K ≤ o(n). A critical parameter is the effective signal-to-noise ratio λ = K2(p - q)2 / ((n - K)q), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log*n + O(1) iterations, with the total time complexity O(|E|log*n), where log*n is the iterated logarithm of n. Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ (n / logn) (ρBP + o(1)), where ρBP is a function of p / q.

Keywords

Hidden communitybelief propagationmessage passingspectral algorithmshigh-dimensional statistics

MSC classification

Primary: 62H12: Estimation
Secondary: 62C20: Minimax procedures
Type
Research Papers
Information
Journal of Applied Probability , Volume 55 , Issue 2 , June 2018 , pp. 325 - 352
Copyright
Copyright © Applied Probability Trust 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Abbe, E. and Sandon, C. (2016). Detection in the stochastic block model with multiple clusters: proof of the achievability conjectures, acyclic BP, and the information-computation gap. Preprint. Available at https://arxiv.org/abs/1512.09080. Google Scholar
[2]Alon, N., Krivelevich, M. and Sudakov, B. (1998). Finding a large hidden clique in a random graph. Random Structures Algorithms 13, 457–466. Google Scholar
[3]Ames, B. P. and Vavasis, S. A. (2011). Nuclear norm minimization for the planted clique and biclique problems. Math. Program. 129, 69–89. Google Scholar
[4]Arias-Castro, E. and Verzelen, N. (2014). Community detection in dense random networks. Ann. Statist. 42, 940–969. Google Scholar
[5]Banks, J., Moore, C., Neeman, J. and Netrapalli, P. (2016). Information-theoretic thresholds for community detection in sparse networks. In Proceedings of the 29th Conference on Learning Theory, pp. 383–416. Google Scholar
[6]Bordenave, C., Lelarge, M. and Massoulié, L. (2015). Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, IEEE, New York, pp. 1347–1357. Google Scholar
[7]Chen, Y. and Xu, J. (2016). Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. J. Mach. Learn. Res. 17, 27. Google Scholar
[8]Davis, C. and Kahan, W. M. (1970). The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal. 7, 1–46. Google Scholar
[9]Decelle, A., Krzakala, F., Moore, C. and Zdeborová, L. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84, 066106. Google Scholar
[10]Dekel, Y., Gurel-Gurevich, O. and Peres, Y. (2014). Finding hidden cliques in linear time with high probability. Combin. Prob. Comput 23, 29–49. Google Scholar
[11]Deshpande, Y. and Montanari, A. (2015). Finding hidden cliques of size √N/e in nearly linear time. Found. Comput. Math. 15, 1069–1128. Google Scholar
[12]Deshpande, Y. and Montanari, A. (2015). Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In Proceedings of the 28th Conference on Learning Theory, pp. 523–562. Google Scholar
[13]Feige, U. and Ron, D. (2010). Finding hidden cliques in linear time. In Proceedings of 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms, pp. 189–204. Google Scholar
[14]Hajek, B., Wu, Y. and Xu, J. (2015). Computational lower bounds for community detection on random graphs. In Proceedings of the 28th Conference on Learning Theory, pp. 899–928. Google Scholar
[15]Hajek, B., Wu, Y. and Xu, J. (2016). Achieving exact cluster recovery threshold via semidefinite programming. IEEE Trans. Inf. Theory 62, 2788–2797. Google Scholar
[16]Hajek, B., Wu, Y. and Xu, J. (2017). Information limits for recovering a hidden community. IEEE Trans. Inf. Theory 63, 4729–4745. Google Scholar
[17]Hajek, B., Wu, Y. and Xu, J. (2018). Recovering a hidden community beyond the Kesten-Stigum threshold in O(|E|log*|V|) time. Preprint. Available at https://arxiv.org/abs/1510.02786. Google Scholar
[18]Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13–30. Google Scholar
[19]Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983). Stochastic blockmodels: first steps. Social Networks 5, 109–137. Google Scholar
[20]Hopkins, S. B., Kothari, P. K. and Potechin, A. (2015). SoS and planted clique: tight analysis of MPW moments at all degrees and an optimal lower bound at degree four. Preprint. Available at https://arxiv.org/abs/1507.05230. Google Scholar
[21]Jerrum, M. (1992). Large cliques elude the Metropolis process. Random Structures Algorithms 3, 347–359. Google Scholar
[22]Kailath, T. (1967). The divergence and Bhattacharyya distance measures in signal selection. IEEE Trans. Commun. Tech. 15, 52–60. Google Scholar
[23]Kesten, H. and Stigum, B. P. (1966). Additional limit theorems for indecomposable multidimensional Galton–Watson processes. Ann. Math. Statist. 37, 1463–1481. Google Scholar
[24]Kobayashi, H. and Thomas, J. B. (1967). Distance measures and related criteria. In Proceedings of Fifth Allerton Conference Circuit and System Theory (Monticello, IL), pp. 491–500. Google Scholar
[25]Krzakala, F.et al. (2013). Spectral redemption in clustering sparse networks. Proc. Nat. Acad. Sci. USA 110, 20935–20940. Google Scholar
[26]Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. In STOC'14—Proceedings of the 2014 ACM Symposium on Theory of Computing, ACM, New York, pp. 694–703. Google Scholar
[27]McSherry, F. (2001). Spectral partitioning of random graphs. In 42nd IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos, CA, pp. 529–537. Google Scholar
[28]Meka, R., Potechin, A. and Wigderson, A. (2015). Sum-of-squares lower bounds for planted clique. In STOC'15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, pp. 87–96. Google Scholar
[29]Mitzenmacher, M. and Upfal, E. (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. Google Scholar
[30]Montanari, A. (2015). Finding one community in a sparse graph. J. Statist. Phys. 161, 273–299. Google Scholar
[31]Mossel, E. (2004). Survey: information flow on trees. In Graphs, Morphisms and Statistical Physics, American Mathematical Society, Providence, RI, pp. 155–170. Google Scholar
[32]Mossel, E., Neeman, J. and Sly, A. (2015). Consistency thresholds for the planted bisection model. In STOC'15—Proceedings of the 2015 ACM Symposium on Theory of Computing, ACM, New York, pp. 69–75. Google Scholar
[33]Mossel, E., Neeman, J. and Sly, A. (2015). Reconstruction and estimation in the planted partition model. Prob. Theory Relat. Fields 162, 431–461. Google Scholar
[34]Mossel, E., Neeman, J. and Sly, A. (2017). A proof of the block model threshold conjecture. Combinatorica 37, 44 pp. Google Scholar
[35]Poor, H. V. (1994). An Introduction to Signal Detection and Estimation, 2nd edn. Springer, New York. Google Scholar
[36]Raghavendra, P. and Schramm, T. (2016). Tight lower bounds for planted clique in the degree-4 SOS program. Preprint. Available at https://arxiv.org/abs/1507.05136. Google Scholar
[37]Yun, S.-Y. and Proutiere, A. (2014). Accurate community detection in the stochastic block model via spectral algorithms. Preprint. Available at https://arxiv.org/abs/1412.7335. Google Scholar