Graph Laplacians and their Convergence on Random Neighborhood Graphs

By Matthias Hein, Jean-Yves Audibert, Ulrike von Luxburg. 2006

312 citations recorded by the source corpus.

Given a sample from a probability measure with support on a submanifold in Euclidean space one can construct a neighborhood graph which can be seen as an approximation of the submanifold. The graph Laplacian of such a graph is used in several machine learning methods like semi-supervised learning, dimensionality reduction and clustering. In this paper we determine the pointwise limit of three different graph Laplacians used in the literature as the sample size increases and the neighborhood size approaches zero. We show that for a uniform measure on the submanifold all graph Laplacians have the same limit up to constants. However in the case of a non-uniform measure on the submanifold only the so called random walk graph Laplacian converges to the weighted Laplace-Beltrami operator.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2018, background): “g [26]) results are only valid in the limit of innite data.”
A tutorial on spectral clustering (2007, methodology): “In the machine learning community, spectral clustering has been made popular by the works of Shi and Malik (2000), Ng et al.”
Metric Learning and Manifolds: Preserving the Intrinsic Geometry (2017, methodology): “The renormalization proceeds by de(cid:28)ning a new adjacency matrix ˜ K n = T ( This new random walk graph Laplacian is consistent for ∆ M irrespective of the sampling density (Hein et al., 2007), a fact that will be instrumental in proving the consistency of our new algorithm in Section 6.”
$\Gamma$-convergence of graph Ginzburg-Landau functionals (2012, background): “Instead of sums ∑m i=1 they use averages 1 m ∑m i=1, which is a choice not unanimously adopted in the literature, but leads to cleaner convergence statements in [41].”
Handbook of Cluster Analysis (2015, background): “The relationship between the continuous ∆ and the graph Laplacian has been studied by [8, 14, 19].”
Tighter PAC-Bayes bounds through distribution-dependent priors (2013, background): “A series of results (Bousquet et al., 2003; Hein et al., 2007) demonstrate that under certain conditions on the distribution of instances, certain constructions of graph Laplacian converge to a generalized Laplace operator on the support of the data generating distribution and the smoothness…”
Spectral clustering based on the graph p-Laplacian (2009, background): “(Hein et al., 2007), that the standard graph Laplacian ∆2 can be defined as the operator which induces the following quadratic form for a function f : V → R:”
Graph Signal Processing: Overview, Challenges, and Applications (2017, unknown): “points goes to infinity [194], [195], [196].”
Introduction to Semi-Supervised Learning (2009, unknown): “The graph construction itself is important [11, 83, 82, 29, 167, 196].”