TY - JOUR

T1 - Network Topology Inference from Heterogeneous Incomplete Graph Signals

AU - Yang, Xiao

AU - Sheng, Min

AU - Yuan, Yanli

AU - Quek, Tony Q.S.

N1 - Funding Information:
Manuscript received April 10, 2020; revised August 29, 2020; accepted November 14, 2020. Date of publication December 2, 2020; date of current version January 11, 2021. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Vincent Gripon. This work was supported by the Natural Science Foundation of China under Grants 91638202, 61725103, and U19B2025. The work of Xiao Yang was also supported by the scholarship of CSC (China Scholarship Council). (Corresponding author: Min Sheng; Yanli Yuan.) Xiao Yang and Min Sheng are with the State Key Laboratory of Integrated Service Networks, Institute of Information Science, Xidian University, Xi’an, Shaanxi 710071, China (e-mail: XYang_2@stu.xidian.edu.cn; mshengxd@gmail.com).

PY - 2021

Y1 - 2021

N2 - Inferring network topologies from observed graph-structured data (also known as graph signals) is a crucial task in many applications of network science. Existing papers on network topology inference typically assume that the observations at all nodes are available. However, there are many situations where only partial observations can be collected due to application-specific constraints. To handle the missing data problem, we propose a framework that relies on heterogeneous incomplete data from a collection of related networks to identify multiple network topologies simultaneously. This work advocates the Gaussian graphical model (GGM) and casts the topology inference problem in terms of estimating the precision matrix that has a form of graph Laplacian. Firstly, an unbiased estimator for the covariance matrix of incomplete data is established and then algorithms based on the alternating direction method of multipliers (ADMM) are developed to jointly estimate graph topologies, rather than estimate each graph topology separately. So that we can borrow information across the multiple related networks to eliminate the impact of missing data. Moreover, non-asymptotic statistical analysis is provided, which proves the consistency of the graph estimator and enables us to investigate the effect of several key factors on the graph estimation error bound. Furthermore, based on the consistent graph estimator, an adaptive algorithm that utilizes the reweighting scheme is proposed to improve the estimation accuracy of the graph-edge structure. Finally, we evaluate our method on both real and synthetic datasets, and the experimental results demonstrate the advantage of our method in comparison with benchmarking algorithms.

AB - Inferring network topologies from observed graph-structured data (also known as graph signals) is a crucial task in many applications of network science. Existing papers on network topology inference typically assume that the observations at all nodes are available. However, there are many situations where only partial observations can be collected due to application-specific constraints. To handle the missing data problem, we propose a framework that relies on heterogeneous incomplete data from a collection of related networks to identify multiple network topologies simultaneously. This work advocates the Gaussian graphical model (GGM) and casts the topology inference problem in terms of estimating the precision matrix that has a form of graph Laplacian. Firstly, an unbiased estimator for the covariance matrix of incomplete data is established and then algorithms based on the alternating direction method of multipliers (ADMM) are developed to jointly estimate graph topologies, rather than estimate each graph topology separately. So that we can borrow information across the multiple related networks to eliminate the impact of missing data. Moreover, non-asymptotic statistical analysis is provided, which proves the consistency of the graph estimator and enables us to investigate the effect of several key factors on the graph estimation error bound. Furthermore, based on the consistent graph estimator, an adaptive algorithm that utilizes the reweighting scheme is proposed to improve the estimation accuracy of the graph-edge structure. Finally, we evaluate our method on both real and synthetic datasets, and the experimental results demonstrate the advantage of our method in comparison with benchmarking algorithms.

UR - http://www.scopus.com/inward/record.url?scp=85097425730&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097425730&partnerID=8YFLogxK

U2 - 10.1109/TSP.2020.3039880

DO - 10.1109/TSP.2020.3039880

M3 - Article

AN - SCOPUS:85097425730

VL - 69

SP - 314

EP - 327

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

M1 - 9277914

ER -