Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck operators

Abstract

This paper presents a diffusion based probabilistic interpretation of spectral clustering and dimensionality reduction algorithms that use the eigenvectors of the normalized graph Laplacian. Given the pairwise adjacency matrix of all points, we define a diffusion distance between any two data points and show that the low dimensional representation of the data by the first few eigenvectors of the corresponding Markov matrix is optimal under a certain mean squared error criterion. Furthermore, assuming that data points are random samples from a density $p(\x) = e^{-U(\x)}$ we identify these eigenvectors as discrete approximations of eigenfunctions of a Fokker-Planck operator in a potential $2U(\x)$ with reflecting boundary conditions. Finally, applying known results regarding the eigenvalues and eigenfunctions of the continuous Fokker-Planck operator, we provide a mathematical justification for the success of spectral clustering and dimensional reduction algorithms based on these first few eigenvectors. This analysis elucidates, in terms of the characteristics of diffusion processes, many empirical findings regarding spectral clustering algorithms.

submitted to NIPS 2005

References in corpus (1)

• Precise asymptotics of small eigenvalues of reversible diffusions in the metastable regime

Cited by in corpus (41)

• Object-Part Attention Model for Fine-grained Image Classification
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Discovery of Self-Assembling $\pi$-Conjugated Peptides by Active Learning-Directed Coarse-Grained Molecular Simulation
• Context-Aware Hypergraph Construction for Robust Spectral Clustering
• Data Fusion via Intrinsic Dynamic Variables: An Application of Data-Driven Koopman Spectral Analysis
• Cluster Forests
• A bag-of-paths framework for network data analysis
• Topological Persistence Machine of Phase Transitions
• Stability of Graph Scattering Transforms
• Scalable Extended Dynamic Mode Decomposition using Random Kernel Approximation
• Construction of embedded fMRI resting state functional connectivity networks using manifold learning
• Manifold learning with arbitrary norms
• Coarse Graining of Data via Inhomogeneous Diffusion Condensation
• Extendable and invertible manifold learning with geometry regularized autoencoders
• Learning Clustered Representation for Complex Free Energy Landscapes
• Unsupervised learning of topological phase diagram using topological data analysis
• Canonical tensor model through data analysis -- Dimensions, topologies, and geometries --
• Manifold Learning with Contracting Observers for Data-driven Time-series Analysis
• The Hierarchical Subspace Iteration Method for Laplace--Beltrami Eigenproblems
• Preconditioned Gradient Descent Algorithm for Inverse Filtering on Spatially Distributed Networks
• Reconstruction of Protein Structures from Single-Molecule Time Series
• Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey
• Mapping the bacterial ways of life
• Data driven Dirichlet sampling on manifolds
• Manifold learning techniques and model reduction applied to dissipative PDEs
• Selecting the independent coordinates of manifolds with large aspect ratios
• A Comprehensive Approach to Mode Clustering
• CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• Product Manifold Learning
• Interpreting Economic Complexity
• Spectral Clustering with Smooth Tiny Clusters
• Supervised Visualization for Data Exploration
• SA-Net: A deep spectral analysis network for image clustering
• Data mining when each data point is a network
• Density-Based Clustering with Kernel Diffusion
• Self-organized manifold learning and heuristic charting via adaptive metrics
• Diffusion Fingerprints
• Unsupervised Co-Learning on $\mathcal{G}$-Manifolds Across Irreducible Representations
• A Measure of the Connection Strengths between Graph Vertices with Applications
• Measuring the Robustness of Graph Properties