Essec\Faculty\Model\Contribution {#2216
#_index: "academ_contributions"
#_id: "12730"
#_source: array:26 [
"id" => "12730"
"slug" => "improved-clustering-algorithms-for-the-bipartite-stochastic-block-model"
"yearMonth" => "2022-03"
"year" => "2022"
"title" => "Improved clustering algorithms for the Bipartite Stochastic Block Model"
"description" => "NDAOUD, M., SIGALA, S. et TSYBAKOV, A. (2022). Improved clustering algorithms for the Bipartite Stochastic Block Model. <i>IEEE Transactions on Information Theory</i>, 68(3), pp. 1960-1975."
"authors" => array:3 [
0 => array:3 [
"name" => "NDAOUD Mohamed"
"bid" => "B00791786"
"slug" => "ndaoud-mohamed"
]
1 => array:1 [
"name" => "SIGALA Suzanne"
]
2 => array:1 [
"name" => "TSYBAKOV Alexandre"
]
]
"ouvrage" => ""
"keywords" => array:6 [
0 => "Bipartite Stochastic Block Model"
1 => "exact recovery"
2 => "almost full recovery"
3 => "spectral methods"
4 => "clustering"
5 => "phase transition"
]
"updatedAt" => "2023-05-24 16:29:20"
"publicationUrl" => "https://arxiv.org/pdf/1911.07987.pdf"
"publicationInfo" => array:3 [
"pages" => "1960-1975"
"volume" => "68"
"number" => "3"
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => """
We establish sufficient conditions of exact and almost full recovery of the node partition in Bipartite Stochastic Block Model (BSBM) using polynomial time algorithms. First, we improve upon the known conditions of almost full recovery by spectral clustering algorithms in BSBM. Next, we propose a new computationally simple and fast procedure achieving exact recovery under milder conditions than the state of the art. Namely, if the vertex sets $V_1$ and $V_2$ in BSBM have sizes $n_1$ and $n_2$, we show that the condition \n
p = \Omega\left(\max\left(\sqrt{\frac{\log{n_1}}{n_1n_2}},\frac{\log{n_1}}{n_2}\right)\right) $ on the edge intensity $p$ is sufficient for exact recovery witin $V_1$. This condition exhibits an elbow at $n_{2} \asymp n_1\log{n_1}$ between the low-dimensional and high-dimensional regimes. The suggested procedure is a variant of Lloyd's iterations initialized with a well-chosen spectral estimator leading to what we expect to be the optimal condition for exact recovery in BSBM. {The optimality conjecture is supported by showing that, for a supervised oracle procedure, such a condition is necessary to achieve exact recovery.} The key elements of the proof techniques are different from classical community detection tools on random graphs. Numerical studies confirm our theory, and show that the suggested algorithm is both very fast and achieves {almost the same} performance as the supervised oracle. 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.
"""
"en" => """
We establish sufficient conditions of exact and almost full recovery of the node partition in Bipartite Stochastic Block Model (BSBM) using polynomial time algorithms. First, we improve upon the known conditions of almost full recovery by spectral clustering algorithms in BSBM. Next, we propose a new computationally simple and fast procedure achieving exact recovery under milder conditions than the state of the art. Namely, if the vertex sets $V_1$ and $V_2$ in BSBM have sizes $n_1$ and $n_2$, we show that the condition \n
p = \Omega\left(\max\left(\sqrt{\frac{\log{n_1}}{n_1n_2}},\frac{\log{n_1}}{n_2}\right)\right) $ on the edge intensity $p$ is sufficient for exact recovery witin $V_1$. This condition exhibits an elbow at $n_{2} \asymp n_1\log{n_1}$ between the low-dimensional and high-dimensional regimes. The suggested procedure is a variant of Lloyd's iterations initialized with a well-chosen spectral estimator leading to what we expect to be the optimal condition for exact recovery in BSBM. {The optimality conjecture is supported by showing that, for a supervised oracle procedure, such a condition is necessary to achieve exact recovery.} The key elements of the proof techniques are different from classical community detection tools on random graphs. Numerical studies confirm our theory, and show that the suggested algorithm is both very fast and achieves {almost the same} performance as the supervised oracle. 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.
"""
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2024-11-21T12:21:46.000Z"
"docTitle" => "Improved clustering algorithms for the Bipartite Stochastic Block Model"
"docSurtitle" => "Journal articles"
"authorNames" => "<a href="/cv/ndaoud-mohamed">NDAOUD Mohamed</a>, SIGALA Suzanne, TSYBAKOV Alexandre"
"docDescription" => "<span class="document-property-authors">NDAOUD Mohamed, SIGALA Suzanne, TSYBAKOV Alexandre</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2022</span>"
"keywordList" => "<a href="#">Bipartite Stochastic Block Model</a>, <a href="#">exact recovery</a>, <a href="#">almost full recovery</a>, <a href="#">spectral methods</a>, <a href="#">clustering</a>, <a href="#">phase transition</a>"
"docPreview" => "<b>Improved clustering algorithms for the Bipartite Stochastic Block Model</b><br><span>2022-03 | Journal articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://arxiv.org/pdf/1911.07987.pdf" target="_blank">Improved clustering algorithms for the Bipartite Stochastic Block Model</a>"
]
+lang: "en"
+"_type": "_doc"
+"_score": 8.816764
+"parent": null
}
