An Analysis of the Convergence of Graph Laplacians

Existing approaches to analyzing the asymptotics of graph Laplacians typically assume a well-behaved kernel function with smoothness assumptions. We remove the smoothness assumption and generalize the analysis of graph Laplacians to include previously unstudied graphs including kNN graphs. We also introduce a kernel-free framework to analyze graph constructions with shrinking neighborhoods in general and apply it to analyze locally linear embedding (LLE). We also describe how, for a given limit operator, desirable properties such as a convergent spectrum and sparseness can be achieved by choosing the appropriate graph construction.

• Publication year

  2010

• Venue

  International Conference on Machine Learning

• Publication date

  2010-06-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1101.5435
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Submanifold density estimation

  2009cited by this paper
• Influence of graph construction on graph-based clustering measures

  2008cited by this paper
• Consistency of spectral clustering

  2008influential reference
• Convergence of Laplacian Eigenmaps

  2006cited by this paper
• From graph to manifold Laplacian: The convergence rate

  2006cited by this paper
• Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results

  2006cited by this paper
• Graph Laplacians and their Convergence on Random Neighborhood Graphs

  2006influential reference
• Kernel density estimation on Riemannian manifolds

  2005cited by this paper
• From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians

  2005influential reference
• Diffusion maps, spectral clustering and reaction coordinates of dynamical systems

  2005influential reference
• Towards a theoretical foundation for Laplacian-based manifold methods

  2005cited by this paper
• Markov Processes: Characterization and Convergence

  2005cited by this paper
• Semi-Supervised Learning on Riemannian Manifolds

  2004cited by this paper
• Self-Tuning Spectral Clustering

  2004cited by this paper
• Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

  2003cited by this paper
• Measure Based Regularization

  2003influential reference
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation

  2003influential reference
• Agile Software Development

  2002cited by this paper
• Nonlinear dimensionality reduction by locally linear embedding.

  2000cited by this paper
• On clusterings-good, bad and spectral

  2000cited by this paper
• Variable Kernel Density Estimation

  1992cited by this paper
• Density Estimation for Statistics and Data Analysis

  1987cited by this paper
• Limit Theorems for Stochastic Processes

  1987cited by this paper
• On Bandwidth Variation in Kernel Estimates-A Square Root Law

  1982cited by this paper
• The Strong Uniform Consistency of Nearest Neighbor Density Estimates.

  1977cited by this paper
• An introduction to differentiable manifolds and Riemannian geometry

  1975cited by this paper
• A nonparametric estimate of a multivariate density function

  1965cited by this paper

• Large Data Limits of Laplace Learning for Gaussian Measure Data in Infinite Dimensions

  2026cites this paper
• Laplace Learning in Wasserstein Space

  2025cites this paper
• Adaptive Geometric Regression for High-Dimensional Structured Data

  2025cites this paper
• Higher-Order Regularization Learning on Hypergraphs

  2025cites this paper
• Estimating Fair Graphs from Graph-Stationary Data

  2025cites this paper
• Partial differential equations in data science

  2025cites this paper
• Fokker-Planck diffusion maps of microglial transcriptomes reveal radial differentiation into substates associated with Alzheimer’s pathology

  2025cites this paper
• Manifold learning in metric spaces

  2025cites this paper
• Random walks on simplicial complexes

  2024cites this paper
• How well behaved is finite dimensional Diffusion Maps?

  2024cites this paper
• Discrete-to-continuum rates of convergence for nonlocal p-Laplacian evolution problems

  2024cites this paper
• Fokker-Planck diffusion maps of multiple single cell microglial transcriptomes reveals radial differentiation into substates associated with Alzheimer’s pathology

  2024cites this paper
• Latent Functional Maps

  2024cites this paper
• Dimensional reduction of gradient-like stochastic systems with multiplicative noise via Fokker-Planck diffusion maps

  2024influential citation
• Manifold Learning with Sparse Regularised Optimal Transport

  2023cites this paper
• Graph Laplacians on Shared Nearest Neighbor graphs and graph Laplacians on $k$-Nearest Neighbor graphs having the same limit

  2023cites this paper
• Manifold learning: what, how, and why

  2023influential citation
• Consistency of Fractional Graph-Laplacian Regularization in Semisupervised Learning with Finite Labels

  2023cites this paper
• A Review of Operator Estimation and Interpolation on Unknown Manifolds

  2022cites this paper
• Improved spectral convergence rates for graph Laplacians on ε-graphs and k-NN graphs

  2022cites this paper
• Tracking Evolving Geometric Data by Local Graph Laplacian Operators

  2022cites this paper
• Strong uniform convergence of Laplacians of random geometric and directed kNN graphs on compact manifolds

  2022cites this paper
• Quadratically Regularized Optimal Transport: nearly optimal potentials and convergence of discrete Laplace operators

  2022cites this paper
• IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality Estimation

  2022cites this paper
• Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport

  2022cites this paper
• Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise

  2022cites this paper
• Understanding the Generalization Performance of Spectral Clustering Algorithms

  2022cites this paper
• Helmholtzian Eigenmap: Topological feature discovery & edge flow learning from point cloud data

  2021cites this paper
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications

  2021cites this paper
• Sinkformers: Transformers with Doubly Stochastic Attention

  2021cites this paper
• ANALYSIS OF CONVERGENCE RATE OF GAUSSIAN BELIEF PROPAGATION USING WALK SUMMABILITY AND LAPLACIAN APPROACHES

  2021cites this paper
• Spectral Convergence of Symmetrized Graph Laplacian on manifolds with boundary

  2021cites this paper
• Clustering dynamics on graphs: from spectral clustering to mean shift through Fokker-Planck interpolation

  2021cites this paper
• Large sample spectral analysis of graph-based multi-manifold clustering

  2021cites this paper
• The decomposition of the higher-order homology embedding constructed from the k-Laplacian

  2021cites this paper
• Non-parametric manifold learning

  2021cites this paper
• Statistical mechanics meets single-cell biology

  2021cites this paper
• Towards a mathematical theory of trajectory inference

  2021cites this paper
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation

  2021cites this paper
• Computing the Riemannian curvature of image patch and single-cell RNA sequencing data manifolds using extrinsic differential geometry

  2021cites this paper
• Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems

  2021cites this paper
• Manifold Learning with Arbitrary Norms

  2020cites this paper
• Convergence of Graph Laplacian with kNN Self-tuned Kernels

  2020cites this paper
• The Mathematical Foundations of Manifold Learning

  2020cites this paper
• Dynamic Point Cloud Denoising via Manifold-to-Manifold Distance

  2020cites this paper
• Product Manifold Learning

  2020cites this paper
• On the Mathematics of RNA Velocity I: Theoretical Analysis

  2020influential citation
• An Overview of Graph Spectral Clustering and Partial Differential Equations

  2020cites this paper
• Graph Signal Processing for Geometric Data and Beyond: Theory and Applications

  2020cites this paper
• Lipschitz regularity of graph Laplacians on random data clouds

  2020cites this paper
• TearingNet: Point Cloud Autoencoder to Learn Topology-Friendly Representations

  2020cites this paper
• Construction and Monte Carlo Estimation of Wavelet Frames Generated by a Reproducing Kernel

  2020cites this paper
• Clustering on Laplacian-embedded latent manifolds when clusters overlap

  2020cites this paper
• A P ] 2 4 Ja n 20 20 A CONTINUUM LIMIT FOR THE PAGERANK ALGORITHM

  2020cites this paper
• Fundamental limits on dynamic inference from single cell Fundamental limits on dynamic inference from single cell

  2020cites this paper
• Nonlinear Filtering With Variable Bandwidth Exponential Kernels

  2020cites this paper
• Graph Construction from Data by Non-Negative Kernel Regression

  2020cites this paper
• A continuum limit for the PageRank algorithm

  2020cites this paper
• The SPDE Approach to Matérn Fields: Graph Representations

  2020cites this paper
• An information-geometric approach to feature extraction and moment reconstruction in dynamical systems

  2020cites this paper
• Regularization on a rapidly varying manifold

  2020cites this paper
• Selecting the independent coordinates of manifolds with large aspect ratios

  2019cites this paper
• Analysis and algorithms for $\ell_p$-based semi-supervised learning on graphs

  2019cites this paper
• Differential Similarity in Higher Dimensional Spaces: Theory and Applications

  2019cites this paper
• The Calculus of variations

  2019cites this paper
• Intrinsic Multi-scale Evaluation of Generative Models

  2019cites this paper
• Cryo-EM reconstruction of continuous heterogeneity by Laplacian spectral volumes

  2019cites this paper
• Continuum Limits of Nonlocal p-Laplacian Variational Problems on Graphs

  2019cites this paper
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds

  2019cites this paper
• Graph Construction from Data using Non Negative Kernel regression (NNK Graphs)

  2019cites this paper
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs

  2019cites this paper
• Earthmover-Based Manifold Learning for Analyzing Molecular Conformation Spaces

  2019cites this paper
• Bayesian nonparametric estimation in the current status continuous mark model

  2019influential citation
• The Shape of Data: Intrinsic Distance for Data Distributions

  2019cites this paper
• Active contour methods on arbitrary graphs based on partial differential equations

  2019cites this paper
• Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace–Beltrami Operator

  2018cites this paper
• Nonlocal $p$-Laplacian Variational problems on graphs.

  2018cites this paper
• Data-Driven Computational Methods

  2018cites this paper
• On Nonlinear Dimensionality Reduction, Linear Smoothing and Autoencoding

  2018cites this paper
• Manifold Coordinates with Physical Meaning

  2018cites this paper
• Geometric Data Analysis Across Scales via Laplacian Eigenvector Cascading.

  2018cites this paper
• A regression approach for explaining manifold embedding coordinates

  2018cites this paper
• Nearest Neighbor Distances

  2017cites this paper
• Spectral Domain Sampling of Graph Signals

  2017cites this paper
• On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms

  2017cites this paper
• Gromov–Hausdorff limit of Wasserstein spaces on point clouds

  2017cites this paper
• Intrinsic Metrics: Exact Equality between a Geodesic Metric and a Graph metric

  2017cites this paper
• Metric Manifold Learning: Preserving the Intrinsic Geometry

  2017cites this paper
• The Geometry of Continuous Latent Space Models for Network Data

  2017cites this paper
• Scalable Manifold Learning and Related Topics

  2017cites this paper
• Fundamental limits on dynamic inference from single-cell snapshots

  2017influential citation
• Metric Learning and Manifolds: Preserving the Intrinsic Geometry

  2017influential citation
• Analysis of $p$-Laplacian Regularization in Semi-Supervised Learning

  2017influential citation
• Consistency of Lipschitz learning with infinite unlabeled data and finite labeled data

  2017cites this paper
• The game theoretic p-Laplacian and semi-supervised learning with few labels

  2017cites this paper
• Variational Limits of k-NN Graph-Based Functionals on Data Clouds

  2016cites this paper
• Nearly Isometric Embedding by Relaxation

  2016cites this paper
• Word Embeddings as Metric Recovery in Semantic Spaces

  2016cites this paper
• Gain function approximation in the feedback particle filter

  2016cites this paper
• Optimal bandwidth estimation for a fast manifold learning algorithm to detect circular structure in high-dimensional data

  2016cites this paper