On the diffusion geometry of graph Laplacians and applications

DOI10.1016/J.ACHA.2018.04.001MaRDI QIDQ2415409zbMATHOpenAlexWikidataFDO

Authors Xiuyuan Cheng, Manas Rachh, Stefan Steinerberger

Publication date 21 May 2019

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.03033

zbMATH Keywords

clusteringeigenvector centralityextremagraph Laplacianhot spots

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Applications of graph theory to circuits and networks (94C15) PDEs on graphs and networks (ramified or polygonal spaces) (35R02)

Abstract: We study directed, weighted graphs $G=(V,E)$ and consider the (not necessarily symmetric) averaging operator ${\displaystyle }$ (mathcal{L}u)(i) = -sum_{j sim_{} i}{p_{ij} (u(j) - u(i))},${\displaystyle }$ where $p_{ij}$ are normalized edge weights. Given a vertex $iinV$, we define the diffusion distance to a set $BsubsetV$ as the smallest number of steps $d_B(i)inmathbbN$ required for half of all random walks started in $i$ and moving randomly with respect to the weights $p_{ij}$ to visit $B$ within $d_B(i)$ steps. Our main result is that the eigenfunctions interact nicely with this notion of distance. In particular, if $u$ satisfies $mathcalLu=lambdau$ on $V$ and ${\displaystyle }$ B = left{ i in V: - varepsilon leq u(i) leq varepsilon ight} eq emptyset,${\displaystyle }$ then, for all $iinV$, ${\displaystyle }$ d_{B}(i) log{left( frac{1}{|1-lambda|} ight) } geq log{left( frac{ |u(i)| }{|u|_{L^{infty}}} ight)} - log{left(frac{1}{2} + varepsilon ight)}.${\displaystyle }$ $d_B(i)$ is a remarkably good approximation of $|u|$ in the sense of having very high correlation. The result implies that the classical one-dimensional spectral embedding preserves particular aspects of geometry in the presence of clustered data. We also give a continuous variant of the result which has a connection to the hot spots conjecture.

Recommendations

• Diffusions on graphs, Poisson problems and spectral geometry
• A graph discretization of the Laplace-Beltrami operator
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator
• Graph Laplacians and their convergence on random neighborhood graphs
• Graph approximations to the Laplacian spectra

Cites work

• scientific article; zbMATH DE number 18983 (Why is no real title available?)
• A counterexample to the ``hot spots conjecture
• Brownian motion and the fundamental frequency of a drum
• Isoperimetric Inequalities and Their Applications
• Localization of quantum states and landscape functions
• Lower bounds on nodal sets of eigenfunctions via the heat flow
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Metastability and low lying spectra in reversible Markov chains
• Metastability in reversible diffusion processes. I: Sharp asymptotics for capacities and exit times
• Metastability in reversible diffusion processes. II: Precise asymptotics for small eigenvalues
• Nodal geometry, heat diffusion and Brownian motion
• Normalized cuts are approximately inverse exit times
• On the Location of Maxima of Solutions of Schrödinger's Equation
• On the ``hot spots conjecture of J. Rauch
• On the nodal line of the second eigenfunction of the Laplacian in \(\mathbb{R}^ 2\)
• Probabilistic approach to the neumann problem
• Sharp \(L^1\)-Poincaré inequalities correspond to optimal hypersurface cuts

Cited in

(15)

• Detecting localized eigenstates of linear operators
• Spectral echolocation via the wave embedding
• The geometry of nodal sets and outlier detection
• Diffusions on graphs, Poisson problems and spectral geometry
• Machine Learning: ECML 2004
• On the dual geometry of Laplacian eigenfunctions
• Discrete diffusion-type equation on regular graphs and its applications
• Removable sets and approximation of eigenvalues and eigenfunctions on combinatorial graphs
• Spectral clustering revisited: information hidden in the Fiedler vector
• scientific article; zbMATH DE number 5054757 (Why is no real title available?)
• Convergence of the diffusion method for weighted torus graphs using Fourier analysis
• A metric on directed graphs and Markov chains based on hitting probabilities
• Three conjectures of Ostrander on digraph Laplacian eigenvectors
• Hypergraph Laplacians in Diffusion Framework
• Extreme values of the Fiedler vector on trees

This page was built for publication: On the diffusion geometry of graph Laplacians and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415409)