Properly-weighted graph Laplacian for semi-supervised learning

DOI10.1007/S00245-019-09637-3zbMATH Open1465.35152arXiv1810.04351OpenAlexW2993986630WikidataQ126575701 ScholiaQ126575701MaRDI QIDQ2019913FDOQ2019913

Authors: Jeff Calder, Dejan Slepčev 

Publication date: 22 April 2021

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1810.04351

Recommendations

• Semi-supervised learning with regularized Laplacian
• Large data and zero noise limits of graph-based semi-supervised learning algorithms
• Learning Theory
• Laplacian-optimized diffusion for semi-supervised learning
• Performance analysis of the LapRSSLG algorithm in learning theory

zbMATH Keywords

gamma-convergencesemi-supervised learningasymptotic consistencylabel propagationPDEs on graphs

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Smoothness and regularity of solutions to PDEs (35B65) Variational methods for second-order elliptic equations (35J20) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12)

Cites Work

• Title not available (Why is that?)
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Optimal Transport
• On optimal matchings
• An introduction to \(\Gamma\)-convergence
• Title not available (Why is that?)
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• From graph to manifold Laplacian: the convergence rate
• Continuum limit of total variation on point clouds
• On the Rate of Convergence of Empirical Measures in ∞-transportation Distance
• Upper and Lower Bounds for Stochastic Processes
• Minimax grid matching and empirical measures
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• A First Course in Sobolev Spaces
• A transportation \(L^p\) distance for signal analysis
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• Title not available (Why is that?)
• Determining Intrinsic Dimension and Entropy of High-Dimensional Shape Spaces
• Analysis of $p$-Laplacian Regularization in Semisupervised Learning
• Distance-based classification with Lipschitz functions
• A variational approach to the consistency of spectral clustering
• Weighted nonlocal Laplacian on interpolation from sparse data
• Large data and zero noise limits of graph-based semi-supervised learning algorithms
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Consistency of Cheeger and ratio graph cuts
• Uncertainty Quantification in Graph-Based Classification of High Dimensional Data
• The game theoreticp-Laplacian and semi-supervised learning with few labels
• Consistency of Lipschitz Learning with Infinite Unlabeled Data and Finite Labeled Data

Cited In (14)

• Learning Theory
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning
• A spectral approach to the shortest path problem
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Boundary estimation from point clouds: algorithms, guarantees and applications
• On the effectiveness of Laplacian normalization for graph semi-supervised learning
• Ratio convergence rates for Euclidean first-passage percolation: applications to the graph infinity Laplacian
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Lipschitz Regularity of Graph Laplacians on Random Data Clouds
• Laplacian-optimized diffusion for semi-supervised learning
• Multiscale Elliptic PDE Upscaling and Function Approximation via Subsampled Data
• A continuum limit for the PageRank algorithm
• A Maximum Principle Argument for the Uniform Convergence of Graph Laplacian Regressors

Uses Software

• ImageNet
• IntDim

This page was built for publication: Properly-weighted graph Laplacian for semi-supervised learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019913)