|
Abstract:
|
We consider a Bipartite Stochastic Block Model (BSBM) and investigate conditions of exact and almost exact recovery for polynomial-time algorithms of clustering over the vertex set of smaller cardinality. We propose a new computationally simple procedure achieving exact recovery under milder conditions than the state of the art. This procedure is a variant of Lloyd’s iterations initialized with a well-chosen spectral algorithm leading to what we expect to be optimal conditions for exact recovery in this model. The key elements of the proof techniques are different from classical community detection tools on random graphs. In particular, we develop a heavy-tailed variant of matrix Bernstein inequality. As a by-product, we improve upon known spectral thresholds for polynomial-time algorithms in BSBM. Finally, using the connection between planted satisfiability problems and the BSBM, we improve upon the sufficient number of clauses to completely recover the planted assignment. This is a joint work with Mohamed Ndaoud and Suzanne Sigalla.
|
