From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians

Matthias Hein, Jean-Yves Audibert, Ulrike von LuxburgCOLT 2005 · OpenReview

Abstract

In the machine learning community it is generally believed that graph Laplacians corresponding to a finite sample of data points converge to a continuous Laplace operator if the sample size increases. Even though this assertion serves as a justification for many Laplacian-based algorithms, so far only some aspects of this claim have been rigorously proved. In this paper we close this gap by establishing the strong pointwise consistency of a family of graph Laplacians with data- dependent weights to some weighted Laplace operator. Our investigation also includes the important case where the data lies on a submanifold of ${\mathbb R}^{d}$ .
BibTeX
@inproceedings{hein2005from,
  author = {Matthias Hein and Jean-Yves Audibert and Ulrike von Luxburg},
  title = {{From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians}},
  booktitle = {Conference on Learning Theory},
  year = {2005},
  url = {https://openreview.net/forum?id=Uy4bvzSsACuD},
}

Loading related content...

Figure