Topology Identification of Directed Graphs via Joint Diagonalization of Correlation Matrices
Topology Identification of Directed Graphs via Joint Diagonalization of Correlation Matrices
复制标题
DOI：
10.1109/tsipn.2020.2984131
复制
发表时间：
2020
影响因子：
3.2
通讯作者：
Yanning Shen;Xiao Fu;G. Giannakis;N. Sidiropoulos
中科院分区：
文献类型：
--
作者：
Yanning Shen;Xiao Fu;G. Giannakis;N. Sidiropoulos
发现定向网络的连接模式是理解复杂系统（如大脑、社会和金融网络）的关键一步。现有的几种网络拓扑推断方法依赖于结构方程模型（sem）。这些假设外源输入是可用的，这在某些应用中可能是不现实的。最近，另一种工作将基于sem的拓扑识别重新定义为三向张量分解任务。这样，知道外生输入相关统计（而不是外生输入本身）就足以进行网络拓扑识别。缺点是这种方法的计算成本很高。此外，很难将网络结构的先验信息（例如，稀疏性和局部平滑性）纳入该框架，而这些先验信息可能有助于在处理现实世界的噪声数据时提高性能。本文提出了一种基于联合对角化的有向网络拓扑推理方法。JD可以看作是张量分解的一种变体，但具有更有效的算法，并且可以很容易地解释网络结构。与现有的替代方案不同，新的可识别性保证是在不考虑外生输入或其统计的情况下获得的。开发了三种适合网络拓扑推断的JD算法，并通过模拟和实际数据测试展示了它们的性能。
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.