A graph decomposition approach for the synthesis of EMPs in directed acyclic networks

1 Introduction

• The general setting allows selected, rather than all, nodes to be excited or measured, but identifying the network requires finding valid combinations of those nodes.Prior necessary conditions and results for trees, single loops, and Parallel Paths Networks frame this design problem [19] [20].Source: §1 · p. 2
• The paper targets sparse EMPs because valid designs for general network topologies remain difficult, although minimal EMPs are known for several specific topology classes.Exciting and measuring every node gives a valid EMP, but the authors seek designs using few excitations and measurements.Source: §1 · p. 2
• The algorithm constructs EMPs for DAGs by decomposing them into Induced Trees and Parallel Paths Networks, then combining subset EMPs under conditions that preserve validity for the whole graph.Each node defines a uniquely determined Induced Tree; earlier results give minimal EMP constructions for the two component structures [20].Source: §1 · p. 2
• The DAG algorithm aims for low EMP cardinality but does not generally produce a minimal EMP; exhaustive search is described as impractical even for moderate networks.Two design features tend to keep cardinality low: minimal EMPs for each Induced Tree and choices that make connecting Parallel Paths Networks identifiable without extra excitations or measurements.Source: §1 · pp. 2–3
• The paper’s novel contributions include the Induced Tree concept, its properties and interactions with Parallel Paths Networks, and the theorems validating the algorithm.The implementation ultimately designs minimal EMPs for the Induced Trees.Source: §1 · p. 3
• The authors report a Python implementation and use a 25-node example to illustrate the resulting EMP’s parsimonious nature.They also note an alternative DAG EMP procedure based on disjoint trees.Source: §1 · p. 3

2 Definitions, Notations and Preliminaries

• The network is modeled by node signals connected through discrete-time transfer-function edges, with selection matrices specifying inputs and measured outputs.The graph records an edge from node j to node i when the corresponding network-matrix entry is nonzero.Source: §2 · p. 3
• A dource has an out-neighbor shared by all its in-neighbors, while a dink has an in-neighbor shared by all its out-neighbors; a node can be both.Sources have no incoming edges and sinks have no outgoing edges.Source: §2 · pp. 3–4
• Generic identifiability asks whether the network matrix can be fully recovered from the known input-output transfer matrix, except possibly for a zero-measure set of parameter values.The setup assumes the input-output model is known and that the input signal is sufficiently rich for its identification from data.Source: §2 · p. 4
• Necessary conditions require nonempty excitation and measurement sets, excitation of sources and dources, measurement of sinks and dinks, and coverage of every node by excitation or measurement.For n nodes, a minimal EMP has cardinality between n and 2n − f − s, where f and s count sources and sinks.Source: §2 · p. 4
• A valid EMP is a choice of excited and measured nodes that makes the network generically identifiable, and its cardinality is the total number selected.A minimal EMP is valid and has no valid competitor with smaller cardinality.Source: §2 · p. 4

• A directed tree is generically identifiable exactly when all sources are excited, all sinks are measured, and every node is excited or measured.Source: §3 · p. 5
• A PPN has one source, one sink, and at least two paths that share only those endpoints; a direct source-to-sink path is permitted.Source: §3 · p. 5
• A PPN with n nodes has a minimal EMP of size n without single-internal-node paths, or n + K1 + K2 − 1 when such paths occur.K1 counts paths with one internal node; K2 is 1 when a direct source-to-sink link exists and 0 otherwise.Source: §3 · p. 5
• An edge (i, j) with alternative paths is generically identifiable when those other paths’ edges are known, node i is excited, and node j is measured.Source: §3 · p. 6
• An induced tree contains nodes reachable from its root by exactly one directed path and has a minimal EMP of size equal to its node count.The section notes that ordinary trees would not provide the same decomposition property.Source: §3 · p. 6
• For any DAG edge with multiple paths between its endpoints, some such path consists entirely of edges belonging to induced trees.The section introduces this property as a cornerstone of the decomposition algorithm and summarizes identifiability conditions and minimal EMPs for both building blocks.Source: §3 · p. 7

• Every DAG can be completely covered by induced trees and PPNs; the construction forms two-path PPNs from uncovered edges, and the resulting cover need not be unique.Source: §4 · p. 7
• An EMP valid for an isolated subdigraph may fail when embedded; in the example, adding edge (3, 4) makes the tree’s EMP invalid for identifying all its edges.Source: §4 · pp. 7–8, Figure 2 · p. 8
• An induced tree’s isolated EMP remains valid when embedded in a network of any topology, because no path can leave the tree and return to it.Source: §4 · p. 8
• A PPN’s isolated EMP identifies its embedded transfer functions when all paths that leave the PPN and return to it are known.The section uses these induced-tree and PPN conditions as the basis for deriving an algorithm to identify all modules in a DAG.Source: §4 · p. 8

5 Design algorithm of a valid EMP for a DAG

• The algorithm covers the DAG with induced trees and parallel-path networks, then applies local EMPs that remain valid when embedded in the full graph.The algorithm first builds induced trees for each node, selects a smallest set covering their union, and designs an EMP for those trees.Source: §5 · pp. 8–9
• Steps 11 and 12 select excitations and measurements at nodes incident to edges leaving or entering the induced-tree cover, respectively.The algorithm also complements the sets to meet the conditions for identifying each induced tree.Source: §5 · p. 9
• For each uncovered edge with multiple alternative paths, Theorem 5.1 guarantees an edge on a parallel-path network whose other paths are known and which can therefore be identified.The edge is identifiable when its source is excited and its destination is measured.Source: §5 · p. 9
• Theorem 5.2 establishes that the algorithm’s EMP identifies every edge outside the induced-tree cover, completing identification of the DAG.The proof combines known paths in the cover with excited source nodes and measured destination nodes already included in the EMP.Source: §5 · pp. 9–10
• The algorithm’s particular choices make the EMP designed for the induced trees valid for uncovered edges in parallel-path networks as well.The proof relies on the DAG decomposition and identifiability conditions for isolated and embedded parallel-path networks.Source: §5 · pp. 9–10

6 A tutorial example

• The selected induced-tree cover T1 ∪ T3 leaves only edges (1,6) and (2,5) uncovered.The two edges each form a two-path network with a path whose edges are already known.Source: §6 · p. 10
• The tree EMPs combine to B = {1, 2, 3}, C = {4, 5, 6}, identifying all edges in T1 and T3.For this example, step 13 is not required.Source: §6 · p. 10
• The EMP B = {1, 2, 3}, C = {4, 5, 6} identifies the whole DAG and is minimal, with cardinality 6 for 6 nodes.The two uncovered edges are identified through parallel-path networks whose other paths are already known.Source: §6 · p. 10
• Choosing different valid EMPs for the isolated trees would leave the two parallel-path edges unidentified without extra excitations or measurements.The alternative choices shown require cardinality 7, rather than 6.Source: §6 · p. 10

7 Example

• The selected tree cover uses nodes K = {1, 3, 4, 5, 6, 9, 10, 12, 15, 16, 17, 18, 19, 21} to cover the induced-tree union.The procedure eliminates trees contained in larger induced trees, such as T7 within T8.Source: §7 · p. 11
• The eight edges outside the induced-tree cover each belong to a parallel-path network whose other paths are known, so the EMP identifies them.The paper lists the edges in the order in which they can be identified.Source: §7 · p. 11
• The algorithm’s EMP is valid for the whole DAG, but the authors make no claim that it is minimal or close to the lower bound.The EMP is designed for the induced trees and also identifies uncovered edges that belong to parallel-path networks.Source: §7 · pp. 11–12
• The algorithm’s EMP has cardinality 34 for the 25-node DAG, and the paper gives 27 to 43 as the range for a valid EMP’s cardinality.The lower bound is at least 27 because nodes 3 and 21 must each be both excited and measured.Source: §7 · p. 12

8 Conclusion

• The algorithm synthesizes a valid, low-cardinality EMP for Directed Acyclic Networks.The procedure is almost entirely automatic, and the authors report that produced EMPs have low cardinality without claiming minimality.Source: §8 · p. 12
• Conditions for identifying trees and PPNs, and for preserving EMP validity when subdigraphs are embedded in a larger digraph, underpin the decomposition method [20].The PPN identification conditions and subdigraph-embedding conditions were established in earlier work [20].Source: §8 · p. 12
• A DAG can be covered by Induced Trees and Parallel Paths Networks, with EMP construction accounting for connections among the subdigraphs.The algorithm constructs an EMP for the induced trees while taking their connections to the PPNs into account.Source: §8 · p. 12
• The authors describe DAG EMP design as a very simple, almost entirely automatic task, while making no claim that the resulting EMP is minimal.Their experience indicates that the algorithm produces EMPs of low cardinality.Source: §8 · p. 12