by Nicolas Tremblay, GIBSA-lab, University of Grenoble, France
Abstract: Kirchhoff forests (KFs) are random forests over graphs, and can be understood as an extension of uniform spanning trees. In this talk, we will explore how KFs can be advantageously leveraged as extremely concise graph summaries, enabling a very efficient and original estimation of some graph operations such as graph signal smoothing or graph signal interpolation. We will see that KFs are interesting for two main reasons: they are very fast to sample (via a variant of Wilson’s algorithm) and they are theoretically well understood as they are a determinantal point process over the nodes and the edges of the graph. This is joint work with Pierre-Olivier Amblard, Luca Avena, Simon Barthelmé, Alexandre Gaudillière, Hugo Jaquard and Yigit Pilavci.
Organized by the Northernmost GraphML Group.