Granger-Faithfulness and Link Orientation in Network Reconstruction
Lists
Only you see this
Abstract
Networked dynamic systems are often abstracted as directed graphs, where the observed system processes form the vertex set and directed edges are used to represent nonzero transfer functions. Recovering the exact underlying graph structure of such a networked dynamic system, given only observational data, is a challenging task. In this article, we prove that there are instances of networks for which any method is susceptible to inferring false negative edges or false positive edges. Borrowing a terminology from the theory of graphical models, we say those systems are unfaithful to their networks. We formalize a variant of faithfulness for dynamic systems, called Granger-faithfulness, and for a large class of dynamic networks, we show that Granger-unfaithful systems constitute a Lebesgue zero-measure set. For the same class of networks, under the Granger-faithfulness assumption, we provide an algorithm that reconstructs the network topology, which guarantees for no false positive and no false negative edges in its output. We augment the topology reconstruction algorithm with orientation rules for some of the inferred edges, and we prove the rules are consistent under the Granger-faithfulness assumption.
BibTeX
@article{dimovska2020granger,
author = {Mihaela Dimovska and Donatello Materassi},
title = {{Granger-Faithfulness and Link Orientation in Network Reconstruction}},
journal = {IEEE Trans. Control. Netw. Syst.},
year = {2020},
doi = {10.1109/tcns.2022.3145305},
}| An algorithm for reconstruction of triangle-free linear dynamic networks with verification of correctness | arXiv · 2020 |
| Reconstruction of Interconnectedness in Networks of DynamicalSystems Based on Passive Observations | Proceedings of the International Conference of Control, Dynamic Systems, and Robotics · 2020 |
| A Reconstruction algorithm for an unknown network | arXiv · 2010 |
| Directed Information Graphs | IEEE Trans. Information Theory · 2015 |
| Physics informed topology learning in networks of linear dynamical systems | arXiv · 2018 |
| Topology Inference over Networks with Nonlinear Coupling | arXiv · 2019 |