Random spanning forests : theory and applications

Nowadays, the field of network science is of central importance in many real-life applications spanning from telecommunication, to transportation, social media analysis, neuroscience and many more. In most of these applications, graph theory are often employed as a model of these networks because it enables meaningful representations, useful and numerous models providing powerful analysis tools as well as algorithms. One of these tools is called random spanning forests (RSF). RSFs are simply random variables whose instances are spanning forests realizations which can be considered as sub-parts of networks. Thanks to the solid theoretical background and to the efficient sampling algorithms, RSFs are preferable for several analysis and applications. For example, Avena \etal [2] propose signal processing applications and multi-resolution analysis tools that are based on RSF. In this thesis, we describe and elaborate on significant properties of RSFs. More specifically, we explain their probability distribution, their sampling procedure by describing one algorithm (a variant of Wilson's algorithm [3]) and their useful connections with the algebraic graph theory. In addition, we underline the strong relations between RSFs and a mathematical model called determinantal point process (DPP) which can model the probabilistic point of view of RSFs. While doing so, we provide an algebraic point of view that disconnects sampling algorithms from these relations. Finally, by using these theoretical outcomes, we provide practical use-cases of RSFs. In particular, we propose and analyze two unbiased RSF-based estimators for the optimization problems defined in graph signal processing. Moreover, we compare these estimators, both theoretically and empirically.

Il campo della scienza delle reti è oggi di centrale importanza in molteplici applicazioni alla vita reale che vanno dalle telecomunicazioni, ai trasporti, analisi dei social media, neuroscienze e molto altro. Nella maggior parte di queste applicazioni, la teoria dei grafi è spesso utilizzata come modello per queste reti poichè fornisce rappresentazioni significative, numerosi ed utili modelli che forniscono strumenti d'analisi, così come algoritmi. Uno di questi strumenti è detto "random spanning forest" (RSF). Le RSF sono variabili aleatorie semplici le cui istanze sono delle realizzazioni delle "spanning forest" che possono essere considerate come sotto-parti delle reti. Grazie al solido background teorico e ad efficienti algoritmi di campionamento, le RSF sono preferibili in molte analisi ed applicazioni. Ad esempio, Avena [2] propone delle applicazioni al trattamento dei segnali e strumenti per l'analisi a multi-risoluzione, basati sulle RSF. In questa tesi, descriviamo ed elaboriamo circa proprietà significative delle RSF. Più nello specifico, spieghiamo la loro distribuzione di probabilità, il loro procedimento di campionamento descrivendo un algoritmo (una variante dell'algoritmo di Wilson [3]) e le loro utili connessioni con la teoria algebrica dei grafi. In più, sottolineiamo le forti relazioni tra RSF ed un modello matematico detto "determinantal point process" (DPP) che può modellare il punto di vista probabilistico delle RSF. Intanto, forniamo un punto di vista algebrico che separa gli algoritmi di campionamento da queste relazioni. Infine, facendo uso dei nosttri risultati teorici, mettiamo a disposizione casi pratici d'uso delle RSF. In particolare, proponiamo ed analizziamo due estimatori oggettivi basati sulle RSF per i problemi di ottimizzazione definiti nel trattamento dei segnali sui grafi. Inoltre, compariamo questi estimatori, sia teoricamente che empiricamente.