Semi-Blind Inference of Topologies and Dynamical Processes over Graphs

Abstract

Network science provides valuable insights across numerous disciplines including sociology, biology, neuroscience and engineering. A task of major practical importance in these application domains is inferring the network 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. This paper develops algorithms that iterate between inferring directed graphs that "best" fit the data, 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, conditions for identifying the network topology given partial observations are specified. It is proved 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 novel approach.

References in corpus (15)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Multilayer Networks
• Kronecker Graphs: An Approach to Modeling Networks
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Stationary Graph Processes and Spectral Estimation
• Kernel-based Reconstruction of Graph Signals
• Adaptive Least Mean Squares Estimation of Graph Signals
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Clustering Partially Observed Graphs via Convex Optimization
• Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks
• Learning Laplacian Matrix in Smooth Graph Signal Representations
• Inference of Spatio-Temporal Functions over Graphs via Multi-Kernel Kriged Kalman Filtering
• Nonlinear Structural Vector Autoregressive Models for Inferring Effective Brain Network Connectivity
• Online Categorical Subspace Learning for Sketching Big Data with Misses

Cited by in corpus (11)

• Graph topology inference based on sparsifying transform learning
• A User Guide to Low-Pass Graph Signal Processing and its Applications
• Online Graph-Adaptive Learning with Scalability and Privacy
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications
• Learning Product Graphs Underlying Smooth Graph Signals
• Sparse Graphical Linear Dynamical Systems
• Finite-Time Model Inference From A Single Noisy Trajectory
• On Inference of Network Topology and Confirmation Bias in Cyber-Social Networks
• Identifying First-order Lowpass Graph Signals using Perron Frobenius Theorem