Graph Laplacians and their convergence on random neighborhood graphs

by: Matthias Hein, Jean-Yves Audibert, Ulrike von Luxburg

(27 Jun 2007)

View FullText article

arXiv (abstract), arXiv (PDF)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

trunov, ansobol, bigbossman

Find related articles with these CiteULike tags

discrete-laplacian, graph, graphs, laplace-beltrami, laplacian, no-tag, random, riemannian-manifold

Abstract

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.

@misc{citeulike:1419429, abstract = {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.}, author = {Hein, Matthias and Audibert, Jean-Yves and von Luxburg, Ulrike }, citeulike-article-id = {1419429}, eprint = {math/0608522}, keywords = {graph, graphs, laplacian, random}, month = {Jun}, posted-at = {2007-06-28 13:00:50}, priority = {2}, title = {Graph Laplacians and their convergence on random neighborhood graphs}, url = {http://arxiv.org/abs/math/0608522}, year = {2007} }

RIS record

TY - ELEC ID - citeulike:1419429 L3 - citeulike-article-id:1419429 TI - Graph Laplacians and their convergence on random neighborhood graphs N2 - 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. KW - graph KW - graphs KW - laplacian KW - random AU - Hein, Matthias AU - Audibert, Jean-Yves AU - von Luxburg, Ulrike PY - 2007/Jun/27/ UR - http://arxiv.org/abs/math/0608522 ER -

RIS BibTeX