Learning Preferential Attachment Graphs under Partial Observability

Abstract

This thesis work deals with the problem of learning the topology of a network starting from the signals emitted by the network nodes while executing some distributed processing task. In particular, these signals are generated over time through a vector autoregressive process, which is a linear diffusion process where each node exchanges messages with its neighbors (therefore, according to the underlying network graph) and aggregate them according to a certain combination policy. We consider the demanding setting of graph learning under partial observability, where only part of the nodes can be probed, and we study under which conditions the subgraph relative to the probed nodes can be correctly estimated. This is a challenging problem since the observed signals are also influenced by the presence of latent nodes, whose signals act as noise and can in principle prevent faithful graph reconstruction. In particular, we consider two fundamental questions. The first question is about achievability: Under which conditions the graph learning problem can be solved? Namely, for meaningful classes of graphs, is there a graph estimator which, starting from signals of the probed nodes, is able to recover the related subgraph? Usually, a positive answer for achievability only says that one or more estimators exist, and that it works for a sufficiently large number of samples. Therefore, the second question arises in the context of sample complexity: Given a graph estimator found by the achievability analysis, how many samples it needs to work properly in practice? Recent results in the literature examined this problem when the underlying graph is generated according to an Erdos-Renyi random model. .. [edited by Author]

Questa tesi analizza il problema della stima della topologia di una rete a partire dai segnali prodotti dai suoi nodi durante l’esecuzione di un algoritmo distribuito. In particolare, i suddetti segnali sono generati nel tempo secondo un modello autoregressivo vettoriale, ossia un modello diffusivo lineare in cui ogni nodo scambia messaggi con i suoi vicini (dunque, in base al grafo che descrive la rete) e li combina seguendo una certa regola. Si considera il complesso scenario in cui la stima della topologia debba avvenire sotto l’ipotesi di osservabilità parziale, secondo la quale solo parte dei nodi può essere osservata, e vengono studiate le condizioni sotto le quali il grafo relativo ai nodi osservati può essere ricostruito; si tratta di un problema complesso, in quanto i segnali osservati sono influenzati dalla presenza di nodi latenti, i cui segnali fungono da rumore e possono in principio inficiare la ricostruzione del grafo. Si considerano due aspetti fondamentali del problema. Il primo aspetto riguarda la fattibilità: sotto quali condizioni il problema di stima della topologia è risolvibile? Ossia, esiste uno stimatore in grado di ricostruire il grafo in esame a partire dai segnali emessi dai nodi osservati? In generale, una risposta affermativa a queste domande permette soltanto di sapere che uno stimatore esiste, e che funzionerà con un numero sufficientemente grande di campioni. Di conseguenza, il secondo aspetto analizzato riguarda l’onerosità della soluzione: dato uno stimatore individuato dalla suddetta analisi di fattibilità, quanti campioni richiede per funzionare correttamente in pratica? Studi recenti hanno analizzato il problema quando il grafo in esame `e generato secondo il modello aleatorio di Erdos-Renyi. .. [a cura dell'Autore]