Source-linked AI summary
A Reconstruction algorithm for an unknown network
Donatello Materassi, Murti V. Salapaka
TL;DR
Reconstructing unknown dynamical networks is difficult despite their broad modeling value and the need for general reconstruction tools. The paper uses Wiener filtering to detect network links, deriving guarantees for self-kin networks and conditions for detecting links in the smallest self-kin supernetwork otherwise. Measurement noise limits the ideal sparsity property, though sufficiently small known noise can be handled with thresholding.
Problem
Reconstructing an unknown dynamical network poses formidable theoretical and practical challenges, motivating general tools for identifying network interconnectedness.
Method
The paper detects network links using the sparsity of non-causal Wiener filters and derives conditions for local, distributed filtering.
Results
For self-kin networks, the Wiener-filter method guarantees exact reconstruction; for general networks, it identifies the smallest self-kin network containing the original system.
Takeaways & Limitations
Wiener filtering provides theoretical conditions for link detection in a broad class of dynamical networks, including loops, multiple inputs, and disconnected nodes.
Takeaways & Limitations
Measurement noise destroys Wiener-filter sparsity, although sufficiently small known measurement noise can be addressed by thresholding to reconstruct the minimal self-kin network.
Abstract
from arXiv · showhide
The interest for networks of dynamical systems has been increasing in the past years, especially because of their capability of modeling and describing a large variety of phenomena and behaviors. We propose a technique, based on Wiener filtering, which provides general theoretical guarantees for the detection of links in a network of dynamical systems. For a large class of network that we name "self-kin" sufficient conditions for a correct detection of a link are formulated. For networks not belonging to this class we give conditions for correct detection of links belonging to the smallest self-kin network containing the actual one.
1 Introduction
Networks of dynamical systems model interconnected phenomena, but reconstructing an unknown network remains theoretically and practically challenging. The paper proposes Wiener filtering to detect links, with conditions for local filtering and distributed implementation.
- Motivation: Networks of dynamical systems model diverse phenomena and support modular design, redundancy, and distributed or parallel algorithms.These benefits motivate interest across physics and engineering.
- The reconstruction problem: Reconstructing an unknown dynamical network poses formidable theoretical and practical challenges despite increasing demand for general reconstruction tools.Existing approaches derive topology from sampled data or identify particular substructures.
- Approach: The proposed approach uses non-Bayesian Wiener filtering to detect links through sparsity of the network’s non-causal Wiener filter.The paper derives conditions under which filtering a signal is local.
- Scope: The paper develops theoretical results for non-causal and causal Wiener filtering, Granger causality, topology-detection algorithms, and robustness.Its organization reflects these extensions and implementation scenarios.
- Network representation: A dynamical network represents each node as a stochastic signal, with directed edges encoding transfer functions and node signals affected by process noise.The graphical representation associates an edge from N_i to N_j with H_ji(z).
2 Illustrative examples
The examples show when Wiener-filter sparsity identifies directly connected nodes and when a more general network causes a non-directly connected signal to enter the estimate. These cases motivate the paper’s topology-reconstruction problem.
- Cascade networks: In cascade examples, the Wiener filter estimating x0 uses only the directly linked parent or child signal.Both downstream and upstream configurations yield one non-null filter entry corresponding to the link with x0.
- Loop networks: For loop networks, the Wiener filter can remain sparse and use only signals directly connected to the estimated node.The loop example excludes x2 from the optimal estimate of x0 despite x2 not being directly connected.
- General networks: In a more general network, the Wiener filter uses both directly linked x2 and non-directly linked x1 when estimating x0.This demonstrates that filter nonzero entries need not always correspond to direct links.
- Reconstruction problem: The examples motivate asking under which assumptions measured node signals and Wiener filtering can reconstruct the topology of linear dynamical systems.The question follows from the contrast between sparse direct-link detection and the general-network counterexample.
3 Preliminary definitions
The paper represents dynamical networks with directed or oriented graphs, then defines topology, kin relations, and self-kin graphs to support link analysis. It also specifies Linear Dynamic Graphs through transfer functions and stationary noise assumptions.
- A directed graph uses ordered node pairs, whereas an undirected graph uses unordered pairs of distinct nodes.
- A graph’s topology removes edge orientation, retaining an undirected connection whenever either directed edge exists.
- The kin-graph is an undirected graph encoding the symmetric kin relation between nodes.
- Self-kin graphs form a class that includes oriented trees and rings, with a ring network always self-kin.
- A Linear Dynamic Graph assigns transfer functions to graph edges and uses rationally related, mutually uncorrelated stationary noise processes under well-posedness and detectability conditions.
4 Problem Formulation
The paper formulates reconstruction as recovering an unknown graph topology from power and cross-spectral densities of the node signals in a well-posed Linear Dynamic Graph.
- Given the power and cross-spectral densities of the node signals, the task is to reconstruct the unknown topology of a well-posed Linear Dynamic Graph.
5 Sparsity of the non-causal Wiener Filter
The paper studies when non-causal Wiener-filter sparsity reveals network relationships. For self-kin graphs, nonzero filter entries identify topological links; outside that class, kin links can remain undetected only under specific cancellation conditions.
- A full-normal-rank spectral condition gives unique transfer-function representations for processes in the relevant time-frequency span.
- The non-causal Wiener filter estimates one node signal from the others by minimizing a spectral-domain approximation cost.
- A nonzero Wiener-filter entry implies that the corresponding pair of nodes is kin in the graph.
- For self-kin graphs, a nonzero filter entry implies an undirected topological link between the corresponding nodes.
- A kin link is undetected when both reciprocal Wiener-filter entries vanish, under the specific conditions characterized by Theorem 31.
- The paper characterizes simultaneous cancellations as pathological, and notes that such cancellation cannot occur when a node is simple.
6 Sparsity of causal filtering operators
Causal Wiener filtering yields sparse operators whose nonzero entries identify kin or parent-child relationships under progressively stronger network assumptions. The results also connect causal filtering to Granger-causal reconstruction.
- Causal Wiener filtering: The causal Wiener filter is formulated as the unique minimizer over the causal transfer-function span of the observed signals.The construction uses spectral factorization and Hilbert-space projection to obtain the unique estimate.
- Causal Wiener filtering: The causal Wiener filter estimating x_j from other signals has nonzero entries corresponding to the kin signals of x_j.This sparsity result holds for well-posed, causal, topologically detectable LDGs.
- Granger-causal filtering: Under strictly causal transfer functions, the one-step prediction operator has nonzero entries only for x_j itself or parent signals.This establishes the relevant sparsity pattern for the Granger-causal operator.
- Granger-causal filtering: Granger-causality provides exact reconstruction of parent-child links when the network is strictly causal.Without that stronger strict-causality hypothesis, the stated result concerns sparsity of the one-step prediction operator.
7 A reconstruction algorithm
The reconstruction procedure estimates each node signal from the others, tests the resulting filter entries, and adds corresponding links to the inferred adjacency structure. Efficient computation and thresholding support application to many signals.
- Algorithm: The algorithm solves a minimization problem for each signal and adds a link when the corresponding Wiener-filter entry is nonzero.The pseudocode applies the reconstruction technique developed from the preceding theoretical results.
- Implementation: Step 2 can be computed efficiently for many signals using Gram-Schmidt orthogonalization techniques.This addresses the computational cost of repeatedly solving the signal-approximation problems.
- Implementation: The nonzero-entry test can be implemented as ||W_ji(z)|| > sigma_thr(x_i, x_j), using a threshold that may depend on both signals.A suitable norm must be defined on the transfer-function space.
8 Discussion on the robustness of the reconstruction
Measurement noise destroys the Wiener filter’s sparsity, but sufficiently small known noise can be handled with thresholding to recover the minimal self-kin topology. A bound on the corrupted filter’s deviation from the ideal filter supplies a sharp link-detection criterion.
- Robustness to measurement noise: Measurement noise destroys the Wiener filter’s sparsity property, limiting direct topology reconstruction from corrupted node signals.The analysis begins from an ideal setting with process noise actively driving the network.
- Robustness to measurement noise: A sufficiently small known measurement-noise level allows thresholding to recover the topology of the minimal self-kin network.The paper states that the robustness guarantee is quantified through the corrupted-filter analysis.
- Filter perturbation bound: Theorem 38 bounds the difference between the ideal topological filter and the corrupted filter obtained from measured outputs.The bound compares W(z), computed from the network dynamics, with its corrupted counterpart ˆW(z).
- Filter perturbation bound: A known function bounding measurement-noise spectral power provides a direct way to apply the filter-error bound.The corollary uses a function D(z) that bounds ∥Φη(z)∥.
- Link-detection criterion: Theorem 38’s inequality must hold for every z, making it a sharp criterion for detecting a link in a corrupted linear dynamical graph.The criterion is applied through a contradiction argument when a link is absent from the kinship graph.
9 Numerical Examples
Numerical examples apply the proposed algorithm to linear dynamical networks, including a 15-node self-kin ring and a 24-node non-self-kin network. The ring reconstruction detects every link without spurious links, while the non-self-kin reconstruction adds links between kins.
- Experimental setup: The examples demonstrate the theoretical results for general linear models without assumptions on transfer-function order or causality.The section presents the applications as illustrative numerical tests.
- Self-kin network: A 15-node ring with fifth-order FIR link dynamics was simulated for 1000 steps using equal noise power at every node.The resulting data were processed with the developed topology-identification algorithm.
- Self-kin network: Every link in the 15-node ring was detected, and the reconstructed self-kin topology contained no spurious links.Figure 8 reports the original and reconstructed topologies.
- Non-self-kin network: A 24-node network was simulated for 1000 steps and its reconstructed topology was reported alongside the original topology.The example corresponds to Figure 9.
10 Conclusions
The paper presents Wiener filtering as a procedure for identifying linear dynamical network structure with exact reconstruction for self-kin graphs. For general graphs, it reconstructs the smallest self-kin graph containing the original, and numerical examples illustrate the method’s correctness and reliability.
- Main conclusions: The proposed Wiener-filtering procedure identifies the general structure of networks of linear dynamical systems.The conclusion describes the procedure as simple but effective.
- Main conclusions: For self-kin network topologies, the method guarantees exact reconstruction, including networks with loops, multiple inputs, and disconnected nodes.The conclusion characterizes self-kin networks as a non-trivial class.
- General networks: For a general graph, the procedure reconstructs the topology of the smallest self-kin graph containing the original graph.The paper presents this result as optimal in the stated sense.
- Evidence from examples: Numerical examples illustrate the correctness and reliability of the identification technique.The examples include a non-self-kin network whose reconstruction contains additional links between kins.
Acknowlgements
The authors acknowledge Lipeng Ning for useful discussions on the paper’s topics.
- Acknowledgements: Donatello Materassi thanks Lipeng Ning for useful discussions related to the paper’s topics.The acknowledgement identifies the contributor and the nature of the assistance.