# Fast Multiscale Diffusion on Graphs

arXiv: https://arxiv.org/abs/2104.14652 · HTML: https://mlsanity.com/paper/2104.14652/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2021.

## Built on by (most cited first, 2 of 2)

- [Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds](https://mlsanity.com/paper/2211.00805/) (2022)
- [Pheno-GS: Phenoscape-scale Geodesic Sinkhorn](https://mlsanity.com/paper/2609.27633/) (2026)

## Abstract (arXiv)

Diffusing a graph signal at multiple scales requires computing the action of the exponential of several multiples of the Laplacian matrix. We tighten a bound on the approximation error of truncated Chebyshev polynomial approximations of the exponential, hence significantly improving a priori estimates of the polynomial order for a prescribed error. We further exploit properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus reducing drastically its computational cost.