A brief explanation of the issue of faithfulness and link orientation in network reconstruction

Mihaela Dimovska, Donatello Materassi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Complex systems can often be understood via a graph abstraction where nodes represent individual components and edges represent input/output relations among them. Recovering the network structure of a complex system from noninvasively observed data plays a central role in many areas of science. A classic approach to this problem is Granger causality. For strictly causal linear dynamic systems, Granger causality guarantees a consistent reconstruction of the network. However, it is a well-established fact that Granger causality, and analogous methods, lead to the inference of spurious links in the presence of direct feedthroughs. On the other hand, graphical model approaches can deal successfully with static operators in acyclic structures. Indeed, in those cases, graphical model tools guarantee a consistent network reconstruction, apart from pathological conditions associated with very specific values of the system parameters. When these pathological conditions do not occur, borrowing terminology from the theory of graphical models, the network is said to be faithful to its graph representation. We discuss the notion of faithfulness and adapt it to the more general case of networks of dynamic systems, in order to combine the main idea behind Granger causality with graphical model techniques. We provide an algorithm which, under faithfulness, has theoretical guarantees for the reconstruction of a large class of linear models containing both direct feedthroughs and feedback loops.

Original languageEnglish (US)
Title of host publication2019 American Control Conference, ACC 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages1
ISBN (Electronic)9781538679265
StatePublished - Jul 1 2019
Event2019 American Control Conference, ACC 2019 - Philadelphia, United States
Duration: Jul 10 2019Jul 12 2019

Publication series

NameProceedings of the American Control Conference
Volume2019-July
ISSN (Print)0743-1619

Conference

Conference2019 American Control Conference, ACC 2019
CountryUnited States
CityPhiladelphia
Period7/10/197/12/19

Fingerprint

Large scale systems
Dynamical systems
Terminology
Feedback

Cite this

Dimovska, M., & Materassi, D. (2019). A brief explanation of the issue of faithfulness and link orientation in network reconstruction. In 2019 American Control Conference, ACC 2019 [8814776] (Proceedings of the American Control Conference; Vol. 2019-July). Institute of Electrical and Electronics Engineers Inc..

A brief explanation of the issue of faithfulness and link orientation in network reconstruction. / Dimovska, Mihaela; Materassi, Donatello.

2019 American Control Conference, ACC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. 8814776 (Proceedings of the American Control Conference; Vol. 2019-July).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Dimovska, M & Materassi, D 2019, A brief explanation of the issue of faithfulness and link orientation in network reconstruction. in 2019 American Control Conference, ACC 2019., 8814776, Proceedings of the American Control Conference, vol. 2019-July, Institute of Electrical and Electronics Engineers Inc., 2019 American Control Conference, ACC 2019, Philadelphia, United States, 7/10/19.
Dimovska M, Materassi D. A brief explanation of the issue of faithfulness and link orientation in network reconstruction. In 2019 American Control Conference, ACC 2019. Institute of Electrical and Electronics Engineers Inc. 2019. 8814776. (Proceedings of the American Control Conference).
Dimovska, Mihaela ; Materassi, Donatello. / A brief explanation of the issue of faithfulness and link orientation in network reconstruction. 2019 American Control Conference, ACC 2019. Institute of Electrical and Electronics Engineers Inc., 2019. (Proceedings of the American Control Conference).
@inproceedings{2671d833d7b849e1a584e0da71baec8a,
title = "A brief explanation of the issue of faithfulness and link orientation in network reconstruction",
abstract = "Complex systems can often be understood via a graph abstraction where nodes represent individual components and edges represent input/output relations among them. Recovering the network structure of a complex system from noninvasively observed data plays a central role in many areas of science. A classic approach to this problem is Granger causality. For strictly causal linear dynamic systems, Granger causality guarantees a consistent reconstruction of the network. However, it is a well-established fact that Granger causality, and analogous methods, lead to the inference of spurious links in the presence of direct feedthroughs. On the other hand, graphical model approaches can deal successfully with static operators in acyclic structures. Indeed, in those cases, graphical model tools guarantee a consistent network reconstruction, apart from pathological conditions associated with very specific values of the system parameters. When these pathological conditions do not occur, borrowing terminology from the theory of graphical models, the network is said to be faithful to its graph representation. We discuss the notion of faithfulness and adapt it to the more general case of networks of dynamic systems, in order to combine the main idea behind Granger causality with graphical model techniques. We provide an algorithm which, under faithfulness, has theoretical guarantees for the reconstruction of a large class of linear models containing both direct feedthroughs and feedback loops.",
author = "Mihaela Dimovska and Donatello Materassi",
year = "2019",
month = "7",
day = "1",
language = "English (US)",
series = "Proceedings of the American Control Conference",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "2019 American Control Conference, ACC 2019",

}

TY - GEN

T1 - A brief explanation of the issue of faithfulness and link orientation in network reconstruction

AU - Dimovska, Mihaela

AU - Materassi, Donatello

PY - 2019/7/1

Y1 - 2019/7/1

N2 - Complex systems can often be understood via a graph abstraction where nodes represent individual components and edges represent input/output relations among them. Recovering the network structure of a complex system from noninvasively observed data plays a central role in many areas of science. A classic approach to this problem is Granger causality. For strictly causal linear dynamic systems, Granger causality guarantees a consistent reconstruction of the network. However, it is a well-established fact that Granger causality, and analogous methods, lead to the inference of spurious links in the presence of direct feedthroughs. On the other hand, graphical model approaches can deal successfully with static operators in acyclic structures. Indeed, in those cases, graphical model tools guarantee a consistent network reconstruction, apart from pathological conditions associated with very specific values of the system parameters. When these pathological conditions do not occur, borrowing terminology from the theory of graphical models, the network is said to be faithful to its graph representation. We discuss the notion of faithfulness and adapt it to the more general case of networks of dynamic systems, in order to combine the main idea behind Granger causality with graphical model techniques. We provide an algorithm which, under faithfulness, has theoretical guarantees for the reconstruction of a large class of linear models containing both direct feedthroughs and feedback loops.

AB - Complex systems can often be understood via a graph abstraction where nodes represent individual components and edges represent input/output relations among them. Recovering the network structure of a complex system from noninvasively observed data plays a central role in many areas of science. A classic approach to this problem is Granger causality. For strictly causal linear dynamic systems, Granger causality guarantees a consistent reconstruction of the network. However, it is a well-established fact that Granger causality, and analogous methods, lead to the inference of spurious links in the presence of direct feedthroughs. On the other hand, graphical model approaches can deal successfully with static operators in acyclic structures. Indeed, in those cases, graphical model tools guarantee a consistent network reconstruction, apart from pathological conditions associated with very specific values of the system parameters. When these pathological conditions do not occur, borrowing terminology from the theory of graphical models, the network is said to be faithful to its graph representation. We discuss the notion of faithfulness and adapt it to the more general case of networks of dynamic systems, in order to combine the main idea behind Granger causality with graphical model techniques. We provide an algorithm which, under faithfulness, has theoretical guarantees for the reconstruction of a large class of linear models containing both direct feedthroughs and feedback loops.

UR - http://www.scopus.com/inward/record.url?scp=85072273522&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85072273522&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85072273522

T3 - Proceedings of the American Control Conference

BT - 2019 American Control Conference, ACC 2019

PB - Institute of Electrical and Electronics Engineers Inc.

ER -