Network Topology Inference from Spectral Templates
Network Topology Inference from Spectral Templates
复制标题
DOI：
10.1109/tsipn.2017.2731051
复制
发表时间：
2017-09-01
影响因子：
3.2
通讯作者：
Ribeiro, Alejandro
中科院分区：
文献类型：
--
作者：
Segarra, Santiago;Marques, Antonio G.;Ribeiro, Alejandro
我们解决的问题，确定无向图的结构，从观察其节点上定义的信号。从根本上说，未知图编码信号元素之间的直接关系，我们的目标是从图上的扩散过程产生的可观察的间接关系中恢复。这里提倡的新外观利用了凸优化和图信号的平稳性的概念，以便仅在其特征向量的情况下识别图移位算子（图的矩阵表示）。这些光谱模板可以通过，例如，从在所寻找的网络上扩散的独立图形信号的样本协方差。新的想法是找到一个图的移动，同时与提供的光谱信息一致，赋予网络某些所需的属性，如稀疏性。为此，我们开发了有效的推理算法源于可证明的紧凸松弛自然非凸标准，特别是两个移位的结果：邻接矩阵和规范化拉普拉斯算子。算法和理论恢复条件的开发，不仅当模板是完全已知的，而且当特征向量是嘈杂的，或者当只有一个子集时，他们给出。数值试验表明，所提出的算法在恢复合成和真实世界的网络的有效性。
We address the problem of identifying the structure of an undirected graph from the observation of signals defined on its nodes. Fundamentally, the unknown graph encodes direct relationships between signal elements, which we aim to recover from observable indirect relationships generated by a diffusion process on the graph. The fresh look advocated here leverages concepts from convex optimization and stationarity of graph signals, in order to identify the graph shift operator (a matrix representation of the graph) given only its eigenvectors. These spectral templates can be obtained, eg., from the sample covariance of independent graph signals diffused on the sought network. The novel idea is to find a graph shift that, while being consistent with the provided spectral information, endows the network with certain desired properties such as sparsity. To that end, we develop efficient inference algorithms stemming from provably tight convex relaxations of natural nonconvex criteria, particularizing the results for two shifts: the adjacency matrix and the normalized Laplacian. Algorithms and theoretical recovery conditions are developed not only when the templates are perfectly known, but also when the eigenvectors are noisy or when only a subset of them are given. Numerical tests showcase the effectiveness of the proposed algorithms in recovering synthetic and real-world networks.