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. Modern methods and classical problems
• 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 theoretic \(p\)-Laplacian and semi-supervised learning with few labels
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data

Cited In (24)

• Lipschitz regularity of graph Laplacians on random data clouds
• Learning Theory
• Performance analysis of the LapRSSLG algorithm in learning theory
• Consistency of fractional graph-Laplacian regularization in semisupervised learning with finite labels
• Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning
• Multiscale elliptic PDE upscaling and function approximation via subsampled data
• A spectral approach to the shortest path problem
• A maximum principle argument for the uniform convergence of graph Laplacian regressors
• From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds
• Boundary estimation from point clouds: algorithms, guarantees and applications
• Semi-supervised learning with local and global consistency
• 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
• Posterior consistency of semi-supervised regression on graphs
• HesGCN: Hessian graph convolutional networks for semi-supervised classification
• Gromov-Hausdorff limit of Wasserstein spaces on point clouds
• Weighted co-association rate-based Laplacian regularized label description for semi-supervised regression
• Large data and zero noise limits of graph-based semi-supervised learning algorithms
• Semi-supervised eigenvectors for large-scale locally-biased learning
• Adaptive edge weighting for graph-based learning algorithms
• Semi-supervised learning with regularized Laplacian
• Laplacian-optimized diffusion for semi-supervised learning
• A continuum limit for the PageRank algorithm
• On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms

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)