Network Topology And Causal Structure Recovery In Linear Dynamical Systems

Thumbnail Image

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Network Topology And Causal Structure Recovery In Linear Dynamical Systems

Published Date




Thesis or Dissertation


Modeling and representing complex systems by a network of interacting agents provide cost-effective and efficient ways to simulate, design, and test the solutions to real-world problems in science and engineering. Applications such as finance, neuroscience, climate science, power grids, etc. involve modeling the agents and states that interact and evolve dynamically and can contain feedback loops. Most existing literature assumes a static relationship between the agents, which fails to capture the dependencies across time. Learning the interdependency (topology) and cause-and-effect structure among the agents is therefore of importance and having an active interest in the graphical network representation and effective modeling of the dynamical systems. Identifying the unknown interaction structure can in general be classified into active and passive techniques. The active techniques involve intervention in the normal operation of the system by injecting external signals and/or modifying agents in the system. Critical applications in financial markets, power grids, meteorological systems, etc. do not allow active intervention in the system. In such critical applications passive methods, which infer the information from the observed time-series measurements, are applied. In the passive techniques, the evolution of the underlying system is mathematically modeled using a generative model, where the agents are excited with a disturbance signal. In this thesis, we study passive techniques to identify the interdependency and the influence pathways in the dynamical systems, where the agents interact linearly. Further, in practice, it might not be viable to observe all the states in the system. Thus, it is imperative to identify the influence structure (network topology) when the system involves hidden/latent states, which is a challenging problem. In Chapter 2, we provide a novel algorithm to identify the interdependency structure, including the dependency among the latent nodes, when only a subset of the nodes/agents provide the time-series measurements. In many applications, the proposed algorithm retrieves the exact influence pathways, with partial directions, including that of the latent nodes. Another practical issue is that some of the disturbances at the agents themselves can be correlated, which renders the agents' influence structure indistinguishable from passive observations. Examples of such systems are observable in applications such as power grids and stock markets. Learning the network topology in the presence of such correlated disturbances is difficult as it is required to extract the dependency between the disturbances first. In Chapter 3, we show that the correlation between the disturbances is equivalent to the dependency induced by the latent nodes. The network topology only provides the correlation structure of the network of agents. It is well known that correlation is not equivalent to causation and the cause-effect structure contains more information than the correlation structure. In many applications in medicine, biology, and statistics the correlation structure might not be sufficient. Here, it is necessary to know the causal structure of the underlying dynamics. In Chapter 4, we provide an algorithm to learn the causal structure of a linear dynamical system when the agents are excited by identical noise sources. Further, a sample complexity analysis is provided, which finds matching upper and lower bounds on the number of samples required to obtain a given error performance. In general, without intervention and assumptions on the generative models, it is impossible to identify a complete causal structure. The best one can identify without further restriction is an equivalent set of graphs with the same conditional correlation structure, Essential Graphs. In Chapter 5, we provide algorithms to estimate the essential graph in linear dynamical systems using the Wiener filter (WF). The conventional time-domain approach to computing WF is computationally expensive. To speed up the calculation, we propose a fast Fourier transform-based computationally efficient approach to estimate the Wiener filter. The conventional probability notion of CI fails to capture the CI notion in a stochastic process. To tackle this problem, we propose a novel probability notion of CI for stochastic processes in the frequency domain. This notion is used to extend the notions of the front-door and the back-door criterion from static graphical models to linear dynamical systems, where the nodal states are stochastic processes.


University of Minnesota Ph.D. dissertation. April 2024. Major: Electrical Engineering. Advisor: Murti Salapaka. 1 computer file (PDF); xiv, 187 pages.

Related to




Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.