EUVIMEDEUVIMED entdecken
Open Access

Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold

Junda Sheng, Thomas Strohmer

Journal of Machine Learning · 2024

DOI: 10.4208/jml.230624 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Machine Learning, 2024. Verfasst von Junda Sheng und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Mathematics, University of California, Davis, CA 95616-5270, USA. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 75 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: NIBIB NIH HHS, NHLBI NIH HHS.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The stochastic block model is a canonical random graph model for clustering and community detection on network-structured data. Decades of extensive study on the problem have established many profound results, among which the phase transition at the Kesten-Stigum threshold is particularly interesting both from a mathematical and an applied standpoint. It states that no estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. Nevertheless, if we slightly extend the horizon to the ubiquitous semi-supervised setting, such a fundamental limitation will disappear completely. We prove that with an arbitrary fraction of the labels revealed, the detection problem is feasible throughout the parameter domain. Moreover, we introduce two efficient algorithms, one combinatorial and one based on optimization, to integrate label information with graph structures. Our work brings a new perspective to the stochastic model of networks and semidefinite program research.

Schlagwörter

Stichwörter der Autor:innen

ClusteringKesten-Stigum thresholdSemi-supervised learningSemidefinite programmingStochastic block model

Autor:innen und Institutionen

  • Department of Mathematics, University of California, Davis, CA 95616-5270, USA.
  • Department of Mathematics and Center of Data Science and Artificial Intelligence Research, University of California, Davis, CA 95616-5270, USA.

Förderung

  • NIBIB NIH HHS
  • NHLBI NIH HHS

Zitieren

APA

Sheng, J., & Strohmer, T. (2024). Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold. Journal of Machine Learning. https://doi.org/10.4208/jml.230624

Vancouver

Sheng J, Strohmer T. Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold. Journal of Machine Learning. 2024. doi:10.4208/jml.230624

BibTeX
@article{Sheng2024,
  author = {Sheng, Junda and Strohmer, Thomas},
  title = {Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold},
  journal = {Journal of Machine Learning},
  year = {2024},
  doi = {10.4208/jml.230624}
}
Kostenlos starten →