On the diffusion geometry of graph Laplacians and applications

DOI10.1016/J.ACHA.2018.04.001zbMATH Open1412.35353arXiv1611.03033OpenAlexW2962894265WikidataQ129904571 ScholiaQ129904571MaRDI QIDQ2415409FDOQ2415409

Authors: Xiuyuan Cheng, Manas Rachh, Stefan Steinerberger 

Publication date: 21 May 2019

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

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.

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

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

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)

Cites Work

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

Cited In (16)

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

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)