Semi-Blind Inference of Topologies and Dynamical Processes Over Dynamic Graphs
Semi-Blind Inference of Topologies and Dynamical Processes Over Dynamic Graphs
复制标题
DOI：
10.1109/tsp.2019.2903025
复制
发表时间：
2019-05-01
影响因子：
5.4
通讯作者：
Giannakis, Georgios B.
中科院分区：
文献类型：
--
作者：
Ioannidis, Vassilis N.;Shen, Yanning;Giannakis, Georgios B.
在网络科学中，一个具有重要实际意义的任务是从节点子集的噪声观测中推断图的结构。可用的拓扑推断方法通常假设网络上的过程在所有节点上都被观察到。然而，特定于应用的约束可能会阻止获取网络范围的观察。缓解现有方法的灵活性有限，这项工作提倡图形过程的结构模型，并开发新的算法，从部分节点的观察网络拓扑结构和过程的联合推理。结构方程模型（SEM）和结构向量自回归模型（SVARMs）在识别复杂图的有向拓扑结构方面具有很好的优点; SEM捕获节点之间的同时因果依赖关系，SVARMs进一步考虑了时滞影响。提出了一种批处理求解器，该批处理求解器在推断“最佳”拟合观测序列的有向图和通过利用与卡尔曼平滑相关的工具以降低的计算复杂度估计网络过程之间迭代。为了进一步适应延迟敏感的应用，提出了一种在线联合推理方法，甚至跟踪时间演化的拓扑结构。此外，我们指定了新的条件，用于确定网络拓扑结构的部分意见。我们证明了所需的观测值的唯一识别显着减少时，网络结构是稀疏的。合成以及真实的数据集的数值测试证实了所提出的方法的有效性。
A task of major practical importance in network science is inferring the graph structure from noisy observations at a subset of nodes. Available methods for topology inference typically assume that the process over the network is observed at all nodes. However, application-specific constraints may prevent acquiring network-wide observations. Alleviating the limited flexibility of existing approaches, this work advocates structural models for graph processes and develops novel algorithms for joint inference of the network topology and processes from partial nodal observations. Structural equation models (SEMs) and structural vector autoregressive models (SVARMs) have well documented merits in identifying even directed topologies of complex graphs; while SEMs capture contemporaneous causal dependencies among nodes, SVARMs further account for time-lagged influences. A batch solver is proposed that iterates between inferring directed graphs that "best" fit the sequence of observations, and estimating the network processes at reduced computational complexity by leveraging tools related to Kalman smoothing. To further accommodate delay-sensitive applications, an online joint inference approach is put forth that even tracks time-evolving topologies. Furthermore, we specify novel conditions for identifying the network topology given partial observations. We prove that the required number of observations for unique identification reduces significantly when the network structure is sparse. Numerical tests with synthetic as well as real datasets corroborate the effectiveness of the proposed approach.