Topology Identification of Directed Graphs via Joint Diagonalization of Correlation Matrices

Yanning Shen, Xiao Fu, Georgios B. Giannakis, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

Abstract

Discovering connectivity patterns of directed networks is a crucial step to understand complex systems such as brain-, social-, and financial networks. Several existing network topology inference approaches rely on structural equation models (SEMs). These presume that exogenous inputs are available, which may be unrealistic in certain applications. Recently, an alternative line of work reformulated SEM-based topology identification as a three-way tensor decomposition task. This way, knowing the exogenous input correlation statistics (rather than the exogenous inputs themselves) suffices for network topology identification. The downside is that this approach is computationally expensive. In addition, it is hard to incorporate prior information of the network structure (e.g., sparsity and local smoothness) into this framework, while such prior information may help enhance performance when handling real-world noisy data. The present work puts forth a joint diagonalizaition (JD)-based approach to directed network topology inference. JD can be viewed as a variant of tensor decomposition, but features more efficient algorithms, and can readily account for the network structure. Different from existing alternatives, novel identifiability guarantees are derived regardless of the exogenous inputs or their statistics. Three JD algorithms tailored for network topology inference are developed, and their performance is showcased using simulated and real data tests.

Original languageEnglish (US)
Article number9055060
Pages (from-to)271-283
Number of pages13
JournalIEEE Transactions on Signal and Information Processing over Networks
Volume6
DOIs
StatePublished - 2020

Bibliographical note

Funding Information:
Manuscript received July 6, 2019; revised December 13, 2019 and February 29, 2020; accepted March 14, 2020. Date of publication April 2, 2020; date of current version April 20, 2020. This work was supported in part by National Science Foundation under projects NSF 1711471, 1500713, ECCS 1808159, NSF III-1910118, ARO W911NF-19-1-0407, and IIS 1704074, in part by the Army Research office under project ARO W911NF-19-1-0247, and in part by the National Institutes of Health under project NIH 1R01GM104975-01. The associate editor coordinating the review of this manuscript and approving it for publication was Xiaowen Dong. (Corresponding author: Georgios Giannakis.) Yanning Shen is with the Department of EECS and the Center for Pervasive Communications and Computing, University of California, Irvine, CA 92697 USA (e-mail: yannings@uci.edu).

Publisher Copyright:
© 2015 IEEE.

Keywords

  • Structural equation models
  • directed network topology inference
  • joint diagonalization
  • tensor-based model

Fingerprint Dive into the research topics of 'Topology Identification of Directed Graphs via Joint Diagonalization of Correlation Matrices'. Together they form a unique fingerprint.

Cite this