An Analysis of the Convergence of Graph Laplacians
arXiv:1101.5435
Abstract
Existing approaches to analyzing the asymptotics of graph Laplacians typically assume a well-behaved kernel function with smoothness assumptions. We remove the smoothness assumption and generalize the analysis of graph Laplacians to include previously unstudied graphs including kNN graphs. We also introduce a kernel-free framework to analyze graph constructions with shrinking neighborhoods in general and apply it to analyze locally linear embedding (LLE). We also describe how for a given limiting Laplacian operator desirable properties such as a convergent spectrum and sparseness can be achieved choosing the appropriate graph construction.
References in corpus (2)
Cited by in corpus (16)
- Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
- Consistency of Cheeger and Ratio Graph Cuts
- Manifold learning with arbitrary norms
- Earthmover-based manifold learning for analyzing molecular conformation spaces
- Sinkformers: Transformers with Doubly Stochastic Attention
- Graph Signal Processing for Geometric Data and Beyond: Theory and Applications
- TearingNet: Point Cloud Autoencoder to Learn Topology-Friendly Representations
- Estimating Vector Fields on Manifolds and the Embedding of Directed Graphs
- A continuum limit for the PageRank algorithm
- Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems
- Improved graph Laplacian via geometric self-consistency
- Spectral Convergence of Symmetrized Graph Laplacian on manifolds with boundary
- Product Manifold Learning
- An information-geometric approach to feature extraction and moment reconstruction in dynamical systems
- The decomposition of the higher-order homology embedding constructed from the -Laplacian
- PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds