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

By Boaz Nadler, Stéphane Lafon, Ronald R. Coifman, Ioannis G. Kevrekidis. Neural Information Processing Systems, 2005

509 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/90d9d11a335c02af5b3ba6d6f3f3fc69af4ed05d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Geometry and Topology

In Statistical and Nonlinear Physics

Citations in the corpus

Handbook of Cluster Analysis (2015, background): “Moreover, [32] showed that setting v ← λ k v, with some t > 1, is related to the diffusion distance, a true metric on the nodes of a graph.”
Ieee Transactions on Knowledge and Data Engineering Context-aware Hypergraph Construction for Robust Spectral Clustering (unknown): “Spectral clustering is an effective means of clustering data with complex topological structure [8]–[13], [15], [16], [31], [34]–[36].”
Object-Part Attention Model for Fine-Grained Image Classification (2017, background): “6, where the coordinate values represent the two largest eigenvectors of similarity matrices among all neurons, as the work [33].”
Multi-Task Learning for Analyzing and Sorting Large Databases of Sequential Data (2008, methodology): “The similarity matrix learned from (i) is then normalized to define a random walk on a graph, where the nodes on the graph correspond to the different musical pieces; this normalized graph matrix is then applied in a graph-diffusion analysis [14], for music search and sorting.”
Type 1 and 2 mixtures of Kullback-Leibler divergences as cost functions in dimensionality reduction based on similarity preservation (2013, background): “Among many other examples, Laplacian eigenmaps [13], locally linear embedding [14], and diffusion maps [15] involve sparse matrices of similarities, also called affinity matrices.”
Diffusion Maps, Reduction Coordinates, and Low Dimensional Representation of Stochastic Systems (2008, methodology): “As a side issue, our analysis provides a mathematical explanation for the success and limitations of these methods in their tasks of identifying clusters [38] [40].”
Decision Forests: A Unified Framework for Classification, Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning (2012, methodology): “This second part is based on the well known Laplacian eigen-maps technique [3, 70] which we summarize here for completeness.”
A Data–Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition (2014, methodology): “Model reduction based on the Koopman eigenfunctions is equally applicable in both deterministic and stochastic settings, but we choose to present it for stochastic systems to highlight the similarities between EDMD and manifold learning techniques such as diffusion maps [45,46].”
SpectralNet: Spectral Clustering using Deep Neural Networks (2018, methodology): “probabilistic interpretation, since the Euclidean distance in the embedding space is equal to a diffusion distance, which, informally, measures the time it takes probability mass to transfer between points, via other points in the dataset (Nadler et al., 2006; Coifman & Lafon, 2006a).”