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 language||English (US)|
|Number of pages||15|
|Journal||IEEE Transactions on Automatic Control|
|State||Published - Mar 2020|
Bibliographical noteFunding 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:,firstname.lastname@example.org; email@example.com).
© 1963-2012 IEEE.
- Blind learning
- dynamic systems
- hidden (latent) variables
- network topology learning
- stochastic processes