Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks

Abstract

Directed networks are pervasive both in nature and engineered systems, often underlying the complex behavior observed in biological systems, microblogs and social interactions over the web, as well as global financial markets. Since their structures are often unobservable, in order to facilitate network analytics, one generally resorts to approaches capitalizing on measurable nodal processes to infer the unknown topology. Structural equation models (SEMs) are capable of incorporating exogenous inputs to resolve inherent directional ambiguities. However, conventional SEMs assume full knowledge of exogenous inputs, which may not be readily available in some practical settings. The present paper advocates a novel SEM-based topology inference approach that entails factorization of a three-way tensor, constructed from the observed nodal data, using the well-known parallel factor (PARAFAC) decomposition. It turns out that second-order piecewise stationary statistics of exogenous variables suffice to identify the hidden topology. Capitalizing on the uniqueness properties inherent to high-order tensor factorizations, it is shown that topology identification is possible under reasonably mild conditions. In addition, to facilitate real-time operation and inference of time-varying networks, an adaptive (PARAFAC) tensor decomposition scheme which tracks the topology-revealing tensor factors is developed. Extensive tests on simulated and real stock quote data demonstrate the merits of the novel tensor-based approach.

References in corpus (6)

• Tensor Decomposition for Signal Processing and Machine Learning
• Kronecker Graphs: An Approach to Modeling Networks
• Uncovering the Temporal Dynamics of Diffusion Networks
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• On the Convexity of Latent Social Network Inference
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks

Cited by in corpus (7)

• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Kernel-Based Structural Equation Models for Topology Identification of Directed Networks
• Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
• Hanson-Wright Inequality for Random Tensors under Einstein Product
• Time-Varying Graph Learning with Constraints on Graph Temporal Variation
• Graph Enhanced High Dimensional Kernel Regression
• Dynamic network identification from non-stationary vector autoregressive time series