Smoothing graph signals via random spanning forests

Yusuf Yigit Pilavci (1) , Pierre-Olivier Amblard (1) , Simon Barthelme (2) , Nicolas Tremblay (1)

1 GIPSA-CICS - GIPSA - Communication Information and Complex Systems
2 GIPSA-VIBS - GIPSA - Vision and Brain Signal Processing

Another facet of the elegant link between random processes on graphs and Laplacian-based numerical linear algebra is uncovered: based on random spanning forests, novel Monte-Carlo estimators for graph signal smoothing are proposed. These random forests are sampled efficiently via a variant of Wilson's algorithm-in time linear in the number of edges. The theoretical variance of the proposed estimators are analyzed , and their application to several problems are considered , such as Tikhonov denoising of graph signals or semi-supervised learning for node classification on graphs.

Mots clés: graph signal processing; smoothing; random spanning forests; Index Terms-graph signal processing

Domaines: Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]

Yusuf Yigit Pilavci, Pierre-Olivier Amblard, Simon Barthelme, Nicolas Tremblay. Smoothing graph signals via random spanning forests. 2019. ⟨hal-02319175v1⟩