Fast Multiscale Diffusion On Graphs

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

ICASSP 2022accepted0 citations

Fast Multiscale Diffusion On Graphs

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

Abstract

Diffusing a graph signal at multiple scales requires to compute the action of the exponential of as many versions of the Laplacian matrix. Considering the truncated Chebyshev polynomial approximation of the exponential, we derive a tightened bound on the approximation error, allowing thus for a better estimate of the polynomial degree that reaches a prescribed error. We leverage the properties of these approximations to factorize the computation of the action of the diffusion operator over multiple scales, thus drastically reducing its computational cost.

BibTeX

@inproceedings{icassp2022_fastmultiscaledi,
  title = {Fast Multiscale Diffusion On Graphs},
  author = {Sibylle Marcotte and Amélie Barbe and Rémi Gribonval and Titouan Vayer and Marc Sebban and Pierre Borgnat and Paulo Gonçalves},
  booktitle = {ICASSP 2022},
  year = {2022}
}