Properly-Weighted Graph Laplacian for Semi-supervised Learning

Jeff Calder, Dejan Slepčev

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The performance of traditional graph Laplacian methods for semi-supervised learning degrades substantially as the ratio of labeled to unlabeled data decreases, due to a degeneracy in the graph Laplacian. Several approaches have been proposed recently to address this, however we show that some of them remain ill-posed in the large-data limit. In this paper, we show a way to correctly set the weights in Laplacian regularization so that the estimator remains well posed and stable in the large-sample limit. We prove that our semi-supervised learning algorithm converges, in the infinite sample size limit, to the smooth solution of a continuum variational problem that attains the labeled values continuously. Our method is fast and easy to implement.

Original languageEnglish (US)
Pages (from-to)1111-1159
Number of pages49
JournalApplied Mathematics and Optimization
Volume82
Issue number3
DOIs
StatePublished - Dec 1 2020

Bibliographical note

Funding Information:
Calder was supported by NSF Grant DMS:1713691. Slep?ev acknowledges the NSF support (Grants DMS-1516677 and DMS-1814991). He is grateful to University of Minnesota, where this project started, for hospitality. He is also grateful to the Center for Nonlinear Analysis of CMU for its support. Both authors thank the referees for valuable suggestions.

Funding Information:
Calder was supported by NSF Grant DMS:1713691. Slepčev acknowledges the NSF support (Grants DMS-1516677 and DMS-1814991). He is grateful to University of Minnesota, where this project started, for hospitality. He is also grateful to the Center for Nonlinear Analysis of CMU for its support. Both authors thank the referees for valuable suggestions.

Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

Keywords

  • Asymptotic consistency
  • Gamma-convergence
  • Label propagation
  • PDEs on graphs
  • Semi-supervised learning

Fingerprint Dive into the research topics of 'Properly-Weighted Graph Laplacian for Semi-supervised Learning'. Together they form a unique fingerprint.

Cite this