Granger-Faithfulness and Link Orientation in Network Reconstruction

Mihaela Dimovska, Donatello Materassi

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)113-124
Number of pages12
JournalIEEE Transactions on Control of Network Systems
Volume9
Issue number1
DOIs
StatePublished - Mar 1 2022

Bibliographical note

Funding Information:
This work was supported in part by the NSF, CNS CAREER under Grant 1553504, and SaTC under Grant 1816703.

Publisher Copyright:
© 2014 IEEE.

Keywords

  • Graphical models
  • learning systems
  • system identification

Fingerprint

Dive into the research topics of 'Granger-Faithfulness and Link Orientation in Network Reconstruction'. Together they form a unique fingerprint.

Cite this