Smoothing graph signals via random spanning forests

International audienceAnother 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