Topology Identification and Learning Over Graphs: Accounting for Nonlinearities and Dynamics
Topology Identification and Learning Over Graphs: Accounting for Nonlinearities and Dynamics
复制标题
DOI：
10.1109/jproc.2018.2804318
复制
发表时间：
2018-05-01
影响因子：
20.6
通讯作者：
Karanikolas, Georgios Vasileios
中科院分区：
文献类型：
--
作者：
Giannakis, Georgios B.;Shen, Yanning;Karanikolas, Georgios Vasileios
识别图拓扑以及在图上演化的过程出现在涉及基因调控、大脑、电力和社交网络的各种应用中，仅举几例。关键的图感知学习任务包括回归、分类、子空间聚类、异常识别、插值、外推和降维。处理这种高维任务的可扩展方法经历了范式转变，以解决与数据驱动科学相关的独特建模和计算挑战。虽然简单易行，但线性时不变模型是有限的，因为它们无法处理一般不断变化的拓扑结构，以及节点过程之间的非线性和动态依赖关系。为此，本文的主要目标是概述总体进展，并开发一个原则性的框架，通过内核，这是明智地选择从预选字典，以最佳地适应数据捕捉非线性。该框架包含并利用部分相关性和部分格兰杰因果关系的（非）线性对应物，以及（非）线性结构方程和向量自回归，沿着低秩、稀疏性和平滑性等属性，以捕获具有突变点的甚至方向依赖性，以及可能随时间演变的拓扑结构上的随时间演变的过程。总体方法继承了基于内核的方法的通用性和通用性，并适合于批量和计算负担得起的在线学习算法，其中包括图形上的新型卡尔曼滤波器。真实的数据实验突出了非线性和动态模型对消费者和金融网络以及基因调控和功能连接大脑网络的影响，其中显示的连接模式相对于现有方法表现出明显的差异。
Identifying graph topologies as well as processes evolving over graphs emerge in various applications involving gene-regulatory, brain, power, and social networks, to name a few. Key graph-aware learning tasks include regression, classification, subspace clustering, anomaly identification, interpolation, extrapolation, and dimensionality reduction. Scalable approaches to deal with such high-dimensional tasks experience a paradigm shift to address the unique modeling and computational challenges associated with data-driven sciences. Albeit simple and tractable, linear time-invariant models are limited since they are incapable of handling generally evolving topologies, as well as nonlinear and dynamic dependencies between nodal processes. To this end, the main goal of this paper is to outline overarching advances, and develop a principled framework to capture nonlinearities through kernels, which are judiciously chosen from a preselected dictionary to optimally fit the data. The framework encompasses and leverages (non) linear counterparts of partial correlation and partial Granger causality, as well as (non) linear structural equations and vector autoregressions, along with attributes such as low rank, sparsity, and smoothness to capture even directional dependencies with abrupt change points, as well as time-evolving processes over possibly time-evolving topologies. The overarching approach inherits the versatility and generality of kernel-based methods, and lends itself to batch and computationally affordable online learning algorithms, which include novel Kalman filters over graphs. Real data experiments highlight the impact of the nonlinear and dynamic models on consumer and financial networks, as well as gene-regulatory and functional connectivity brain networks, where connectivity patterns revealed exhibit discernible differences relative to existing approaches.