Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$? - MathOverflow

Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?

2012-01-22T02:01:24Z

A graph $G$ is connected if and only if the second-largest eigenvalue $\lambda_2$ of the Laplacian of $G$ is greater than zero. (See, e.g., the Wikipedia article on algebraic connectivity.)

Is there an analogous statement for the eigenvalue $\lambda_2(M)$ of the Laplacian operator $\Delta$ for an $n$-dimensional ~~connected,~~ closed Riemannian manifold $M$?

($\Delta(f) = \nabla^2(f) = −\mathrm{div}(\mathrm{grad}(f))$.)

I am trying to understand the relationship between Laplacians on graphs and Laplacians on Riemannian manifolds. Pointers to help elucidate the connection would be greatly appreciated!

Addendum. See Richard Montgomery's interesting new comment on the Laplacian on the integer lattice.

Answer by Liviu Nicolaescu for Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?

2012-01-22T12:43:35Z

In my opinion, Colin de Verdiere's book "Spectre de Graphes" is the best place to start investigating the connection between the discrete Laplacian and the manifold Laplacian.

Recently, investigations in computer science (machine learning) lead to considerable progress.

Pick a "cloud" of points in a Riemann manifold. Consider the complete graph with vertices on these points. Next add weights to the edges that correlate with the geodesic distance between the corresponding points on the manifold. Then form a certain weighted Laplacian associated to this weighted graph. This operator converges with probability one to the the manifold Laplacian as the cloud is bigger and bigger and is chosen randomly with respect to the metric volume measure on the manifold.

I know I skipped many details, but you can get precise statements in this nice paper by M. Belkin and P. Niyogi:

Towards a Theoretical Foundation for Laplacian-Based Manifold Methods

M. Belkin's webpage has additional info.

Answer by Alain Valette for Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?

2012-01-22T23:09:24Z

Take a finite cover $\cal{U}$ of $M$ by open subsets, and view the nerve $N({\cal U})$ of this cover as a finite simplicial complex, carrying a combinatorial Laplace operator in each degree. By choosing $\cal{U}$ carefully, with a small enough mesh, in all degree $p$ you may approximate the $k$ first eigenvalues of the Laplace-Beltrami operator on $p$-forms of $M$, by the corresponding eigenvalues of the combinatorial Laplace operator in degree $p$ on $N({\cal U})$. Here $k=s_p({\cal U})-b_p(M)$, where $s_p({\cal U})$ is the number of $p$-simplices. See Theorem 3.1 in a paper by T. Mantuano http://arxiv.org/pdf/math/0609599.pdf Reference: Discretization of Riemannian manifolds applied to the Hodge Laplacian, Tatiana Mantuano, Source American Journal of Mathematics, Volume 130, Number 6, December 2008, pp. 1477-1508

Answer by Highwind for Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?

2012-04-02T21:47:47Z

Hi,

Note that in either case (graph or manifold) several Laplace Operator discrtizations exists (with different properties). Some of these do not converge to the true (continuous) operator when mesh size is reduced. Higher order FEM approaches can yield fast convergence. Most operators are linear approximations.
On the manifold discretization (usually triangles for surfaces), you have geometric information, e.g. the angles between edges, which does not necessarily exist in the graph case.
For any operator on a manifold (mesh) that discretizes the contniuous Laplacian this holds: the eigenvalues are a diverging sequence of real positive numbers (including zero, and of course the number of eigenvalues is limited by the discretization). The first eigenvalue is zero if the manifold is closed, or if the Neumann boundary condition is applied at the boundary. It is larger zero for Dirichlet boundary condition. Iff you have n eigenvalues that are zero, you have n connected components.

There may be easier ways of testing connectedness (e.g. using the mesh representation, Euler characteristic or flooding algorithms).