Identifying the Topology of Undirected Networks From Diffused Non-Stationary Graph Signals
Identifying the Topology of Undirected Networks From Diffused Non-Stationary Graph Signals
复制标题
DOI：
10.1109/ojsp.2021.3063926
复制
发表时间：
2018-01
影响因子：
2.8
通讯作者：
Rasoul Shafipour;Santiago Segarra;A. Marques;G. Mateos
中科院分区：
文献类型：
--
作者：
Rasoul Shafipour;Santiago Segarra;A. Marques;G. Mateos
我们解决的问题推断一个无向图从节点的意见，这是建模为非平稳的图形信号产生的局部扩散动力学，取决于未知网络的结构。使用所谓的图形移位算子（GSO），这是一个矩阵表示的图形，我们首先确定的特征向量的移位矩阵的扩散信号的观察，然后估计的特征值施加所需的属性上的图形要恢复。与可以直接从测量的协方差矩阵获得特征向量的静态设置不同，这里我们需要首先估计未知扩散（图）滤波器-GSO中的多项式，其保留所寻求的特征基。为了执行这个初始系统识别步骤，我们利用关于任意相关输入信号的不同信息源来驱动图上的扩散。我们首先探索观察、输入信息和未知图过滤器线性相关的设置。然后，我们解决的情况下，关系是由一个系统的矩阵二次方程，这产生在务实的情况下，只有二阶统计的输入是可用的。虽然这样的二次滤波器识别问题归结为一个非凸的四阶多项式最小化，我们讨论可识别的条件，提出算法来近似的解决方案，并分析其性能。数值试验表明，所提出的拓扑推理算法的有效性，在恢复大脑，社会，金融和城市交通网络，使用合成和真实世界的信号。
We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics that depend on the structure of the unknown network. Using the so-called graph-shift operator (GSO), which is a matrix representation of the graph, we first identify the eigenvectors of the shift matrix from observations of the diffused signals, and then estimate the eigenvalues by imposing desirable properties on the graph to be recovered. Different from the stationary setting where the eigenvectors can be obtained directly from the covariance matrix of the measurements, here we need to estimate first the unknown diffusion (graph) filter – a polynomial in the GSO that preserves the sought eigenbasis. To carry out this initial system identification step, we exploit different sources of information on the arbitrarily-correlated input signal driving the diffusion on the graph. We first explore the setting where the observations, the input information, and the unknown graph filter are linearly related. We then address the case where the relation is given by a system of matrix quadratic equations, which arises in pragmatic scenarios where only the second-order statistics of the inputs are available. While such a quadratic filter identification problem boils down to a non-convex fourth-order polynomial minimization, we discuss identifiability conditions, propose algorithms to approximate the solution, and analyze their performance. Numerical tests illustrate the effectiveness of the proposed topology inference algorithms in recovering brain, social, financial, and urban transportation networks using synthetic and real-world signals.