# Recovering the Graph Underlying Networked Dynamical Systems under Partial Observability: A Deep Learning Approach

arXiv: https://arxiv.org/abs/2208.04405 · HTML: https://mlsanity.com/paper/2208.04405/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 65 references that are in the map.
- First posted on arXiv 8 Aug 2022.

## Builds on (most cited first, 15 of 15)

- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [Signal Processing on Graphs: Causal Modeling of Unstructured Data](https://mlsanity.com/paper/1503.00173/) (2015)
- [Linear identification of nonlinear systems: A lifting technique based on the Koopman operator](https://mlsanity.com/paper/1605.04457/) (2016)
- [Generalized Network Dismantling](https://mlsanity.com/paper/1801.01357/) (2018)
- [Network dismantling](https://mlsanity.com/paper/1603.08883/) (2016)
- [Causal Inference by Identification of Vector Autoregressive Processes with Hidden Components](https://mlsanity.com/paper/1411.3972/) (2014)
- [Dynamical Systems on Networks: A Tutorial](https://mlsanity.com/paper/1403.7663/) (2014)
- [SILVar: Single Index Latent Variable Models](https://mlsanity.com/paper/1705.03536/) (2017)
- [Hardness of parameter estimation in graphical models](https://mlsanity.com/paper/1409.3836/) (2014)
- [Local Tomography of Large Networks under the Low-Observability Regime](https://mlsanity.com/paper/1805.09081/) (2018)
- [An Unbiased Symmetric Matrix Estimator for Topology Inference under Partial Observability](https://mlsanity.com/paper/2203.15500/) (2022)
- [Network Inference from Consensus Dynamics](https://mlsanity.com/paper/1708.05329/) (2017)
- [Identification of diffusively coupled linear networks through structured polynomial models](https://mlsanity.com/paper/2106.01813/) (2021)

## Built on by (most cited first, 2 of 2)

- [Inferring the Graph of Networked Dynamical Systems under Partial Observability and Spatially Colored Noise](https://mlsanity.com/paper/2312.11324/) (2023)
- [The Powers of Precision: Structure-Informed Detection in Complex Systems -- From Customer Churn to Seizure Onset](https://mlsanity.com/paper/2601.21170/) (2026)

## Abstract (arXiv)

We study the problem of graph structure identification, i.e., of recovering the graph of dependencies among time series. We model these time series data as components of the state of linear stochastic networked dynamical systems. We assume partial observability, where the state evolution of only a subset of nodes comprising the network is observed. We devise a new feature vector computed from the observed time series and prove that these features are linearly separable, i.e., there exists a hyperplane that separates the cluster of features associated with connected pairs of nodes from those associated with disconnected pairs. This renders the features amenable to train a variety of classifiers to perform causal inference. In particular, we use these features to train Convolutional Neural Networks (CNNs). The resulting causal inference mechanism outperforms state-of-the-art counterparts w.r.t. sample-complexity. The trained CNNs generalize well over structurally distinct networks (dense or sparse) and noise-level profiles. Remarkably, they also generalize well to real-world networks while trained over a synthetic network (realization of a random graph). Finally, the proposed method consistently reconstructs the graph in a pairwise manner, that is, by deciding if an edge or arrow is present or absent in each pair of nodes, from the corresponding time series of each pair. This fits the framework of large-scale systems, where observation or processing of all nodes in the network is prohibitive.