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. This 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 that 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.
Introduction
In many complex systems, the underlying causal relationships—the "edges" of a directed graph—are unobservable. We typically only have access to nodal measurements, such as stock prices or neuronal activity. Structural Equation Models (SEMs) provide a framework for inferring these edges by incorporating exogenous inputs (external stimuli) to resolve directional ambiguities. However, a significant challenge arises when these inputs are hidden or unobservable due to privacy concerns or measurement costs.
Furthermore, real-world networks are rarely static; they evolve over time. Existing methods often fail to uniquely identify directed topologies when inputs are hidden and lack the scalability required for real-time tracking of dynamic datasets.
Methodology
The proposed framework addresses these challenges through a two-pronged approach:
Tensor-based Batch Inference
The core innovation lies in leveraging the "piecewise-stationary" nature of exogenous inputs. By assuming that the statistical properties of these inputs remain constant within specific time windows but vary across them, the authors construct a three-way tensor $\underline{\mathbf{R}}^y$ by stacking the correlation matrices of nodal measurements from $M$ different windows.
Applying Parallel Factor (PARAFAC) decomposition to this tensor allows for the unique identification of the network's adjacency matrix ($A$). Unlike matrix factorization, PARAFAC decomposition is often uniquely identifiable, which guarantees that the inferred structure is the only one consistent with the observed data. This "blind" estimation simultaneously recovers the network structure and the local correlation matrices of the hidden inputs.
Adaptive Tracking
To handle time-varying networks, an online algorithm based on Recursive Least Squares (RLS) is developed. This algorithm updates the tensor factors incrementally as new observations arrive, avoiding the need to re-process historical data. This enables real-time tracking of structural changes with minimal computational and memory overhead.
Experimental Results
The approach was validated using both synthetic and real-world datasets:
- Synthetic Kronecker Graphs: Tests on 64-node directed networks demonstrated that the Edge Identification Error Rate (EIER) decreases significantly as the number of time windows ($M$) or the window length ($L$) increases.
- Real-world Stock Data: Analysis of historical closing prices for tech companies and retailers correctly identified strong dependencies between direct competitors, such as Macy’s and Nordstrom, reflecting how market shocks propagate through the network.
- Dynamic Tracking: The adaptive algorithm successfully tracked edges appearing or disappearing in simulated dynamic networks, demonstrating rapid recovery after structural shifts.
Conclusion
This paper presents a robust tensor-based framework for blind topology inference and real-time tracking of directed networks. By exploiting the diversity in second-order statistics of hidden inputs, the method overcomes the limitations of traditional SEMs. Future research directions include incorporating network priors (e.g., sparsity), developing distributed implementations for large-scale networks, and extending the framework to non-linear nodal interactions.
Summary updated