Fast Multiscale Diffusion on Graphs

Paulo Gonçalves, Amélie Barbe, Marc Sebban, Sibylle Marcotte, Titouan Vayer, Rémi Gribonval, Pierre Borgnat

Publication date: 29 April 2021

Abstract: 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.

Has companion code repository: https://github.com/krishnaswamylab/heatgeo

This page was built for publication: Fast Multiscale Diffusion on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6366477)