Blind Learning of Tree Network Topologies in the Presence of Hidden Nodes

Firoozeh Sepehr, Donatello Materassi

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

This paper considers the problem of learning the unknown structure of a network with the underlying topology given by a polyforest (a collection of directed trees with potentially multiple roots). The main result is an algorithm that consistently learns the network structure using only second-order statistics of the data. The methodology is robust with respect to the presence of unmeasured (latent) nodes: The algorithm detects the exact number and location of the latent nodes, when they satisfy specific degree conditions in the actual network graph. It is shown that the same degree conditions are also necessary for a consistent reconstruction. Thus, the proposed reconstruction algorithm achieves the fundamental limitations in learning the structure of a polyforest network of linear dynamic systems in the presence of latent nodes. This paper overcomes the limitations of previous results that only addressed single-rooted trees, tackling the problem in an efficient way since the computational complexity of the derived algorithm is proven to be polynomial in the number of observed nodes.

Original languageEnglish (US)
Article number8707081
Pages (from-to)1014-1028
Number of pages15
JournalIEEE Transactions on Automatic Control
Volume65
Issue number3
DOIs
StatePublished - Mar 2020

Bibliographical note

Funding Information:
Manuscript received October 26, 2018; revised February 15, 2019; accepted April 20, 2019. Date of publication May 6, 2019; date of current version February 27, 2020. This work was supported in part by NSF (CNS CAREER #1553504 and SaTC #1816703). Recommended by Associate Editor P. Rapisarda. (Corresponding author: Firoozeh Sepehr.) The authors are with the Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996 USA (e-mail:,fsepehr1@vols.utk.edu; dmateras@utk.edu).

Publisher Copyright:
© 1963-2012 IEEE.

Keywords

  • Blind learning
  • dynamic systems
  • hidden (latent) variables
  • network topology learning
  • stochastic processes

Fingerprint

Dive into the research topics of 'Blind Learning of Tree Network Topologies in the Presence of Hidden Nodes'. Together they form a unique fingerprint.

Cite this