Learning the Graph of Networked Dynamical Systems under Partial-observability via Artificial Neural Networks

Abstract

Nesta tese, abordamos o problema da identificação de grafos de sistemas dinâmicos lineares estocásticos em rede, a partir de dados de séries temporais que refletem a evolução do estado de um subconjunto de nós observados no sistema - portanto, um subconjunto complementar de nós permanece não observado ou latente. Dadas essas séries temporais ao nível do nó, o objetivo é recuperar consistentemente o grafo subjacente relativo às dependências entre os nós no sistema. Assumimos observabilidade parcial, isto é, apenas estão disponíveis um subconjunto das séries temporais dos nós que compõem a rede. Propomos um novo vetor de features calculadas a partir das séries temporais observadas, que agem como um descritor estatístico do acoplamento entre nós. Provamos formalmente que essas features são linearmente separáveis, ou seja, existe um hiperplano (no espaço de features) que separa o conjunto de features associadas a pares de nós conectados daquelas associados a pares de nós desconectados. Essa propriedade de separabilidade permite usar essas features para treinar um grande número de classificadores e efetuar a identificação da estrutura do grafo subjacente. Em particular, optamos por treinar Redes Neuronais Convolucionais (CNNs) sobre essas features resultando num modelo de aprendizagem que exibe uma performance, em geral, supeior a outros algoritmos state-of-the-art. Esta performance referece à complexidade amostral, isto é, número de amostras da série temporal necessárias para atingir um certo nível de precisão na recuperação do grafo. Enquanto as CNNs são treinadas em um grafo sintético específico, elas generalizam bem em sistemas de rede com padrões de conectividade distintos (densa ou esparsa), incluindo grafos do mundo real e regimes distintos de nível de ruído. Esta é uma propriedade importante, pois, em geral, podemos não ter informações sobre esses atributos estruturais. Por fim, o método proposto aprende consistentemente o grafo de maneira par-a-par, ou seja, inferindo se um determinado par de nós está conectado ou não a partir de suas séries temporais (ignorando as séries temporais de outros nós). Isso é particularmente adequado para sistemas de grande escala, onde a observação de todos os nós da rede é inviável.

In this thesis, we address the problem of graph identification of linear stochastic networked dynamical systems from the time series data that reflect the state evolution of a subset of observed nodes in the system -- hence, a complementary subset of nodes lies unobserved or latent. Given these node-level time series data, the goal is to consistently recover the underlying graph of dependencies among the nodes in the networked system. We assume partial observability, i.e., the time series data of only a subset of nodes comprising the network is available. We propose a novel feature vector computed from the observed time series as a statistical descriptor for the coupling between nodes. We formally prove that these features are linearly separable, that is, there exists a hyperplane (in feature space) that partitions the set of features associated with connected pairs of nodes from those associated with disconnected pairs of nodes. This separability property allows to use these features to train a multitude of classifiers in order to perform graph structure identification. In particular, we choose to train Convolutional Neural Networks (CNNs) over these features with a resulting graph learning algorithm that outperforms state-of-the-art counterparts w.r.t. sample-complexity, i.e., number of samples required to reach a certain level of accuracy in the recovery of the graph. While the CNNs are trained over a particular synthetic network, they generalize well over networked systems with distinct connectivity patterns (dense or sparse) including real-world networks, and distinct noise-level regimes. This is an important property as, in general, we might have no information about these structural attributes. Finally, the proposed method consistently learns the graph in a pairwise manner, that is, via inferring whether a particular pair of nodes is connected or not from their time series (ignoring the time series from other nodes). This is particularly tailored to large scale systems where observation of all nodes in the network is unfeasible.