Understanding the Success of Graph-Based Semi-Supervised Learning Using Partially Labelled Stochastic Block Model

Avirup Saha, Shreyas Sheshadri, Samik Datta, Niloy Ganguly, Disha Makhija, Priyank Patel

IJCAI 2020 pp. 1345-1351

doi:10.24963/IJCAI.2020/187 /ijcai/2020/saha2020ijcai-understanding/

Abstract

With the proliferation of learning scenarios with an abundance of instances, but limited amount of high-quality labels, semi-supervised learning algorithms came to prominence. Graph-based semi-supervised learning (G-SSL) algorithms, of which Label Propagation (LP) is a prominent example, are particularly well-suited for these problems. The premise of LP is the existence of homophily in the graph, but beyond that nothing is known about the efficacy of LP. In particular, there is no characterisation that connects the structural constraints, volume and quality of the labels to the accuracy of LP. In this work, we draw upon the notion of recovery from the literature on community detection, and provide guarantees on accuracy for partially-labelled graphs generated from the Partially-Labelled Stochastic Block Model (PLSBM). Extensive experiments performed on synthetic data verify the theoretical findings.

PDF IJCAI Semantic Scholar

Cite

Text

Saha et al. "Understanding the Success of Graph-Based Semi-Supervised Learning Using Partially Labelled Stochastic Block Model." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/187

Markdown

[Saha et al. "Understanding the Success of Graph-Based Semi-Supervised Learning Using Partially Labelled Stochastic Block Model." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/saha2020ijcai-understanding/) doi:10.24963/IJCAI.2020/187

BibTeX

@inproceedings{saha2020ijcai-understanding,
  title     = {{Understanding the Success of Graph-Based Semi-Supervised Learning Using Partially Labelled Stochastic Block Model}},
  author    = {Saha, Avirup and Sheshadri, Shreyas and Datta, Samik and Ganguly, Niloy and Makhija, Disha and Patel, Priyank},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2020},
  pages     = {1345-1351},
  doi       = {10.24963/IJCAI.2020/187},
  url       = {https://mlanthology.org/ijcai/2020/saha2020ijcai-understanding/}
}