Almost Exact Recovery in Label Spreading

Konstantin Avrachenkov 1 Maximilien Dreveton 1
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In semi-supervised graph clustering setting, an expert provides cluster membership of few nodes. This little amount of information allows one to achieve high accuracy clustering using efficient computational procedures. Our main goal is to provide a theoretical justification why the graph-based semi-supervised learning works very well. Specifically, for the Stochastic Block Model in the moderately sparse regime, we prove that popular semi-supervised clustering methods like Label Spreading achieve asymptotically almost exact recovery as long as the fraction of labeled nodes does not go to zero and the average degree goes to infinity.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-02397060
Contributor : Konstantin Avrachenkov <>
Submitted on : Friday, December 6, 2019 - 1:09:18 PM
Last modification on : Tuesday, January 21, 2020 - 1:58:48 PM

File

WAW2019_SSL_SBM(3).pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Konstantin Avrachenkov, Maximilien Dreveton. Almost Exact Recovery in Label Spreading. WAW 2019 - 16th Workshop on Algorithms and Models for the Web Graph, Jul 2019, Brisbane, Australia. ⟨10.1007/978-3-030-25070-6_3⟩. ⟨hal-02397060⟩

Share

Metrics

Record views

39

Files downloads

169