Diffusion maps reduce data to coordinates that preserve how points are connected by a similarity graph—not simply how close every pair is in the original feature space. They build a Markov random walk on that graph, then use its leading eigenvectors to summarize the ways probability spreads between points. The result depends on choices such as kernel bandwidth, density normalization, diffusion time, and embedding dimension; there is no universally correct setting.
What a diffusion map represents
Imagine starting a random walk at each data point. After a chosen number of steps, the walk has a probability distribution over the graph. Two points are close in diffusion distance when their walks produce similar distributions, even if the points are not close in the raw feature space. Multiple paths through the graph contribute to this comparison, so a short chain of locally similar observations can connect points that are far apart by direct feature-space distance.
A diffusion map compresses these transition profiles into a small set of Euclidean coordinates. Its geometry therefore describes graph connectivity at a selected scale. It is useful when observations lie near a lower-dimensional nonlinear structure, or when connectivity and gradual transitions matter more than preserving every original pairwise distance.
This is different from PCA, which finds directions of greatest linear variance, and from methods that primarily preserve selected pairwise distances. Diffusion maps begin with a graph and a walk; the kernel, graph construction, normalization, and walk time all help define what “near” means.
Crashes, No Sound, or Screen Glitches?
Random freezes, missing sound and display glitches usually trace back to one bad driver. Find and replace yours safely.Free scan · under a minutePC Slower Than It Used to Be?
A free scan shows the junk files, broken settings and background clutter dragging Windows down - then fixes them in one click.Free scan · Windows 10 & 11#1 Best Overall
How the construction works
- Build similarities. Treat observations as graph nodes and assign larger nonnegative weights to similar pairs. A common choice is the Gaussian kernel
W[i,j] = exp(-||x[i]-x[j]||² / epsilon). Hereepsilonis a squared-distance scale: increasing it generally broadens neighborhoods. - Correct for local sampling density, if desired. Let
q[i]be the sum of rowiofW. A density correction with exponentalphaformsW_alpha[i,j] = W[i,j] / (q[i]^alpha q[j]^alpha). This is a modeling choice, not merely a numerical adjustment. - Turn weights into transition probabilities. Divide each row of the corrected kernel by its row sum. The resulting row-stochastic matrix
Pgives the one-step transition probabilities of a random walk. - Extract coordinates. Compute leading eigenpairs of
P. The stationary, constant-like eigenvector ordinarily does not distinguish observations, so coordinates use leading nontrivial eigenvectors. Diffusion timetweights each eigenvector bylambda^t.
For a symmetric affinity kernel and symmetric density correction, the row-normalized transition matrix is generally not symmetric. A symmetric matrix similar to it can be diagonalized instead, then its eigenvectors can be converted back to right eigenvectors of P. The implementation below uses that approach.
Choose the modeling settings for the question
Kernel and neighborhood scale
The bandwidth determines which observations exchange probability directly. If it is too narrow, the graph may fragment into disconnected pieces; if it is too broad, local structure can be blurred by long-range connections. A full Gaussian kernel connects every pair mathematically, but weights can become so small that the effective graph is poorly connected. A sparse neighborhood graph reduces storage and computation, but its neighbor rule and symmetrization also affect connectivity.
Rank #2
- Use scikit-learn to track an example ML project end to end
- Explore several models, including support vector machines, decision trees, random forests, and ensemble methods
- Exploit unsupervised learning techniques such as dimensionality reduction, clustering, and anomaly detection
- Dive into neural net architectures, including convolutional nets, recurrent nets, generative adversarial networks, autoencoders, diffusion models, and transformers
- Use TensorFlow and Keras to build and train neural nets for computer vision, natural language processing, generative models, and deep reinforcement learning
Inspect graph components or connectivity, and examine how the leading eigenvalues and embedding change across plausible scales. If the result changes drastically after a modest bandwidth adjustment, treat that instability as a modeling finding rather than hiding it behind one selected value. Distances also depend on feature scaling: standardize or otherwise scale features only when that scaling matches their meaning in the problem.
Density normalization
Nonuniform sampling can influence the walk: densely sampled regions collect more kernel mass. In the manifold-sampling analysis, the conventional alpha = 1 correction is used to target Laplace–Beltrami, or heat-operator, geometry independently of nonuniform sampling density, under the analysis assumptions. With no correction (alpha = 0), sampling density remains part of the operator’s behavior. Other normalizations can represent other operators or retain density and potential effects. Choose normalization according to whether density is nuisance variation or meaningful signal; do not assume one setting is correct for every data-generating process.
What’s actually slowing this PC down?
Pick the symptom - the matching free tool is one click away.
Rank #3
| Normalization choice | Interpretation to consider | Use when |
|---|---|---|
alpha = 0 |
No kernel-density correction; sampling density influences the walk. The distinct operator limits for normalizations are discussed by Nadler et al. (2006). | Density or density-related dynamics should remain part of the geometry. |
alpha = 1 in the conventional construction |
Targets Laplace–Beltrami geometry independently of nonuniform sampling density in the manifold-sampling analysis; assumptions matter (Nadler et al., 2006). | The goal is manifold geometry less affected by uneven sampling. |
Diffusion time and dimension
Time changes which spectral modes matter. Raising eigenvalues to t suppresses modes with smaller magnitude more strongly as t grows, so longer times emphasize persistent connectivity and coarser structure. At short times, more local distinctions can remain visible. Compare embeddings at times relevant to the phenomenon rather than treating a time value as an incidental default.
Retain enough nontrivial eigenvectors to represent the structures needed for the task, then assess the result in that task. Eigenvalue decay can help describe the spectrum, but the foundational sources do not establish a universal cutoff or a single dimension-selection rule.
Rank #4
A dense reference implementation in Python
This implementation takes a numeric feature matrix, constructs the Gaussian kernel and density correction, and returns coordinates plus the nontrivial eigenvalues. It uses alpha = 1 as an explicit choice for a density-independent manifold-geometry target, not as a universal default. Pass an epsilon appropriate to the scaled features and data; the code does not select one automatically.
import numpy as np
from scipy.linalg import eigh
def diffusion_map(X, epsilon, n_components=2, alpha=1.0, t=1):
"""Dense diffusion map for a small or moderate data set.
X: array of shape (n_samples, n_features)
epsilon: positive squared-distance bandwidth for exp(-distance_squared / epsilon)
n_components: number of nontrivial coordinates to return
alpha: kernel-density normalization exponent
t: nonnegative integer diffusion time
"""
X = np.asarray(X, dtype=float)
if X.ndim != 2 or X.shape[0] < 2:
raise ValueError("X must be a 2D array with at least two rows")
if not np.isfinite(X).all():
raise ValueError("X must contain only finite values")
if epsilon <= 0:
raise ValueError("epsilon must be positive")
if n_components < 1 or n_components >= X.shape[0]:
raise ValueError("n_components must be between 1 and n_samples - 1")
if int(t) != t or t < 0:
raise ValueError("t must be a nonnegative integer")
# Pairwise squared Euclidean distances; clamp roundoff below zero.
norms = np.sum(X * X, axis=1)
dist2 = norms[:, None] + norms[None, :] - 2.0 * X @ X.T
np.maximum(dist2, 0.0, out=dist2)
W = np.exp(-dist2 / epsilon)
q = W.sum(axis=1)
W_alpha = W / (q[:, None] ** alpha * q[None, :] ** alpha)
d = W_alpha.sum(axis=1)
# S is symmetric and similar to the row-stochastic transition matrix P.
S = W_alpha / np.sqrt(d[:, None] * d[None, :])
eigenvalues, eigenvectors = eigh(S)
order = np.argsort(eigenvalues)[::-1]
eigenvalues = eigenvalues[order]
eigenvectors = eigenvectors[:, order]
# Convert S eigenvectors to right eigenvectors of P = D^-1 W_alpha.
psi = eigenvectors / np.sqrt(d[:, None])
lambdas = eigenvalues[1:n_components + 1]
coordinates = psi[:, 1:n_components + 1] * (lambdas ** t)[None, :]
return coordinates, lambdasExample call: coordinates, eigenvalues = diffusion_map(X, epsilon=1.0, n_components=3, alpha=1.0, t=2). The example’s epsilon is illustrative only; it is not a recommended value for arbitrary data. Eigenvector signs are arbitrary, so a coordinate axis may flip sign across implementations without changing the represented geometry.
Do these 3 things before closing this tab:
1Scan for outdated or missing drivers - takes under a minute2Repair Windows errors before they cause bigger problems3Fix the driver behind crashes, sound loss and screen glitchesBest Value
What this code does not scale to
The reference implementation stores a dense pairwise distance matrix and dense kernels, requiring quadratic memory in the number of observations; its dense eigendecomposition is also costly as the data set grows. For larger data, construct a sparse neighborhood graph, maintain symmetry as required by the chosen construction, and use a sparse eigensolver for leading eigenpairs. A surfaced Python package describes sparse linear algebra and optional GPU acceleration, but its current maintenance and compatibility were not established, so verify its present state and dependencies before relying on it.
Quick Recap
Validate the embedding against the data and task
- Check graph connectivity. Look for isolated observations or disconnected components; a narrow kernel or restrictive neighbor graph can split the data.
- Compare plausible settings. Examine whether important neighborhoods, transitions, or clusters persist across reasonable bandwidths, normalization choices, and diffusion times.
- Use an external task criterion where possible. If coordinates feed a prediction, clustering, or visualization task, assess them against that task rather than selecting dimension solely by appearance.
- Interpret the scale correctly. Distances in the embedding summarize the selected graph walk and time, not a promise to preserve all raw-space distances.
Foundational sources
- Ronald R. Coifman and Stéphane Lafon, “Diffusion maps,” Applied and Computational Harmonic Analysis, 21(1), 5–30 (July 2006). Introduces the framework, diffusion coordinates, and the family of diffusion distances.
- Boaz Nadler, Stéphane Lafon, Ronald R. Coifman, and Ioannis G. Kevrekidis, “Diffusion maps, spectral clustering and reaction coordinates of dynamical systems,” Applied and Computational Harmonic Analysis, 21(1), 113–127 (July 2006). Analyzes normalization choices and continuum differential-operator limits.
- Boaz Nadler, Stéphane Lafon, Ioannis G. Kevrekidis, and Ronald R. Coifman, “Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators,” NeurIPS 2005. Develops diffusion-distance interpretation and a low-dimensional approximation result under a specified mean-squared-error criterion.
- Coifman et al., “Geometric diffusions as a tool for harmonic analysis and structure definition of data: diffusion maps,” PNAS (2005), a complementary multiscale account.
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
