An Analysis of the Convergence of Graph Laplacians

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 (1)

• Consistency of spectral clustering

Cited by in corpus (9)

• Consistency of Cheeger and Ratio Graph Cuts
• Sinkformers: Transformers with Doubly Stochastic Attention
• Estimating Vector Fields on Manifolds and the Embedding of Directed Graphs
• Efficient Representations of Signals in Nonlinear Signal Processing with Applications to Inverse Problems
• Spectral Convergence of Symmetrized Graph Laplacian on manifolds with boundary
• Improved graph Laplacian via geometric self-consistency
• An information-geometric approach to feature extraction and moment reconstruction in dynamical systems
• The decomposition of the higher-order homology embedding constructed from the $k$-Laplacian
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds