Abstract
Learning the community structure of a largescale graph is a fundamental problem in machine learning, computer science and statistics. Among others, the Stochastic Block Model (SBM) serves a canonical model for community detection and clustering, and the Massively Parallel Computation (MPC) model is a mathematical abstraction of realworld parallel computing systems, which provides a powerful computational framework for handling largescale datasets. We study the problem of exactly recovering the communities in a graph generated from the SBM in the MPC model. Specifically, given kn vertices that are partitioned into k equalsized clusters (i.e., each has size n), a graph on these kn vertices is randomly generated such that each pair of vertices is connected with probability p if they are in the same cluster and with probability q if not, where p > q > 0.
We give MPC algorithms for the SBM in the (very general) sspace MPC model, where each machine is guaranteed to have memory s = Ω(log n). Under the condition that (pq)/√p ≥ Ω̃(k^{1/2} n^{1/2+1/(2(r1))}) for any integer r ∈ [3,O(log n)], our first algorithm exactly recovers all the k clusters in O(kr log_s n) rounds using Õ(m) total space, or in O(rlog_s n) rounds using Õ(km) total space. If (pq)/√p ≥ Ω̃(k^{3/4} n^{1/4}), our second algorithm achieves O(log_s n) rounds and Õ(m) total space complexity. Both algorithms significantly improve upon a recent result of CohenAddad et al. [PODC'22], who gave algorithms that only work in the sublinear space MPC model, where each machine has local memory s = O(n^δ) for some constant δ > 0, with a much stronger condition on p,q,k. Our algorithms are based on collecting the rstep neighborhood of each vertex and comparing the difference of some statistical information generated from the local neighborhoods for each pair of vertices. To implement the clustering algorithms in parallel, we present efficient approaches for implementing some basic graph operations in the sspace MPC model.
BibTeX  Entry
@InProceedings{li_et_al:LIPIcs.ESA.2023.78,
author = {Li, Zelin and Peng, Pan and Zhu, Xianbin},
title = {{Massively Parallel Algorithms for the Stochastic Block Model}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {78:178:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18731},
URN = {urn:nbn:de:0030drops187313},
doi = {10.4230/LIPIcs.ESA.2023.78},
annote = {Keywords: Massively Parallel Computation, Stochastic Block Model, Graph Algorithms}
}
Keywords: 

Massively Parallel Computation, Stochastic Block Model, Graph Algorithms 
Collection: 

31st Annual European Symposium on Algorithms (ESA 2023) 
Issue Date: 

2023 
Date of publication: 

30.08.2023 