⚡ electrical engineering

Nonlinear Network Identifiability with Full Excitations

This paper establishes that for nonlinear networks with additive dynamics and full node excitation, measuring all sinks is necessary and sufficient for identifiability in directed acyclic graphs (provided dynamics lack constant terms), while for general digraphs, measuring one node from each sink in the condensation digraph suffices, though the presence of constant terms renders identifiability impossible if any node has multiple in-neighbors.

Original authors: Renato Vizuete, Julien M. Hendrickx

Published 2026-06-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Renato Vizuete, Julien M. Hendrickx

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, complex city where every building (a node) talks to its neighbors through pipes (the edges). Water flows through these pipes, but the flow isn't just a simple straight line; it's twisted by valves, filters, and twists in the pipe that change the water's behavior in complicated, non-linear ways.

The goal of this research is to figure out exactly how each of those specific valves and filters works, just by watching the water come out of certain buildings. This is called identifiability: Can we uniquely determine the rules of the pipes just by observing the output?

The authors, Renato Vizuete and Julien Hendrickx, tackle a tricky problem: What is the minimum number of buildings we need to put sensors on to figure out the entire city's plumbing?

Here is the breakdown of their findings using simple analogies:

1. The Setup: Full Excitation

Imagine the city manager decides to turn on a faucet in every single building simultaneously. This is called "Full Excitation." The researchers assume we can see exactly what comes out of the buildings we choose to measure.

2. The "Dead End" Rule (DAGs)

First, they look at cities where the water only flows one way and never loops back on itself. Think of a waterfall or a series of waterfalls where water goes from the top, down to the next level, and never returns. In math terms, these are Directed Acyclic Graphs (DAGs).

The Problem with "Static" Rules: If the pipes just added a constant amount of water (like a fixed leak) regardless of the flow, the system becomes a mess. If two pipes feed into one building, you can't tell which pipe contributed what if they both have constant leaks. It's like trying to guess how much salt two different people added to a soup if they both added a fixed spoonful; you can't tell them apart.
The Solution (Dynamic Rules): The researchers assume the pipes are "smart." They don't just add a fixed amount; they react to the flow. For example, a valve might open wider if the pressure is higher. Crucially, if there is no water flowing, there is no extra output (mathematically, $f(0)=0$ ).
The Result: For these one-way cities, you only need to measure the "sinks."
- Analogy: A "sink" is a building with no pipes leading out of it; it's the final destination where water just pools.
- The Magic: If you measure the water level at the very bottom of the waterfall (the sink), you can mathematically work your way backwards up the chain to figure out exactly how every single valve in the entire system works. You don't need to measure the middle buildings. The non-linear nature of the valves (how they react to flow) acts like a unique fingerprint that lets you untangle the signals coming from different paths.

3. The "Loop" Problem (General Digraphs)

Now, imagine a city where pipes form loops. Water flows from Building A to B, then B to C, and C back to A. This creates a cycle.

The Issue: In a loop, the water keeps circling. If you measure the output, it's a mix of water that just entered and water that has circled around 10 times. It looks like an infinite mess of variables.
The Fix: The researchers assume the city starts completely dry and empty (at rest) before the faucets are turned on.
The "Unfolding" Trick: To solve the loop problem, they use a mathematical trick called "unfolding." Imagine taking a video of the city and laying out every frame side-by-side.
- Frame 1: Water enters.
- Frame 2: Water moves to the next building.
- Frame 3: Water moves again.
- By looking at the "unfolded" version, the loops disappear because the water in Frame 1 is distinct from the water in Frame 2. The loop becomes a long, straight line (a DAG).
The Result: Even with loops, you don't need to measure everything. You need to measure one building in every "final group" (sink) of the city's structure.
- Analogy: If the city has several distinct neighborhoods that eventually drain into a few main reservoirs, you just need to measure one building in each of those final reservoirs. The "unfolding" math proves that this is enough to figure out every valve in the loops leading up to them.

4. Why This is Different from Linear Systems

In the old days (linear systems), if two pipes fed into a building, you needed very specific, separate paths to measure them to tell them apart. It was like needing two different cameras to see two people in a crowd.

But in this non-linear world, the "smart valves" (the non-linear functions) are so unique in how they react that they naturally separate the signals.

Analogy: Imagine two people whispering into a microphone. In a linear world, their voices mix into a muddy noise. But in this non-linear world, the microphone distorts their voices in such a unique, complex way that you can actually separate them perfectly just by listening to the final output, even if they spoke at the same time.

Summary of the Rules

No Loops (DAGs): Measure the sinks (the dead ends). That's it.
With Loops: Assume the system starts empty. Unfold the loops into a straight line. Measure one node in every sink of the "condensed" structure (the final groups of the city).
The Catch: The pipes must be "dynamic" (reacting to flow, not just adding a constant leak) and smooth (no sudden jumps). If a building has multiple pipes feeding it and they act like simple, constant leaks, the system is impossible to solve.

The Bottom Line:
You don't need to put sensors on every building in a complex, non-linear network. If the network behaves in a "smart" (non-linear) way, you can often figure out the entire system's secret rules just by watching the water come out of the final destinations. The complexity of the non-linear functions actually helps you solve the puzzle, rather than making it harder.

Technical Summary: Nonlinear Network Identifiability with Full Excitations

Problem Formulation
This paper addresses the problem of network identifiability for nonlinear systems characterized by additive dynamics at the edge level. The network is modeled as a weakly connected directed graph $G=(V, E)$ where the state of each node $i$ at time $k$ is determined by an external excitation signal $u_{i}^{k-1}$ and the past outputs of its in-neighbors $j \in N_i$ through nonlinear functions $f_{i,j}$ . The model assumes full excitation (all nodes can be excited) and finite memory. The objective is to determine the necessary and sufficient conditions on the set of measured nodes ( $N_m$ ) such that the local dynamics (the functions $f_{i,j}$ ) can be uniquely identified from the global behavior (the input-output relationships $F_i$ ).

The analysis distinguishes between two primary topological cases:

Directed Acyclic Graphs (DAGs): Networks without cycles.
General Digraphs: Networks that may contain cycles.

The study considers specific classes of nonlinear functions, ranging from all continuously differentiable functions to twice continuously differentiable functions with specific properties (e.g., $f(0)=0$ and non-linear components).

Methodology
The authors employ a theoretical framework based on system identification principles, assuming an ideal scenario where the global input-output functions $F_i$ are perfectly known. The methodology proceeds as follows:

Class Restriction: The authors analyze identifiability within specific function classes. They first consider the class of all functions ( $\mathcal{F}_{ALL}$ ) and then refine this to continuously differentiable functions with no static offset ( $\mathcal{F}_Z$ , where $f(0)=0$ ), and finally to twice continuously differentiable functions that are not purely linear ( $\mathcal{F}_{Z,NL}$ ).
DAG Analysis: For DAGs, the authors utilize the property that information flows unidirectionally. They employ a recursive approach, starting from the sinks (nodes with no outgoing edges). Key lemmas establish that if a node $i$ is measured and has an in-neighbor $j$ with a unique path to $i$ , the edge function $f_{i,j}$ can be isolated. For general DAGs, they use a "removal of a node" argument (Lemma 4) to show that if a node with a unique path to a measured node is identified, the remaining subgraph's identifiability can be analyzed recursively.
General Digraph Analysis: For graphs with cycles, the input-output relationship involves an infinite number of past inputs. To handle this, the authors introduce Assumption 3 (the network is initially at rest at $k=0$ ) and Assumption 4 (functions are additively separable). Under these assumptions, they construct an unfolded digraph $H_i^k(G)$ , which is a time-expanded, acyclic representation of the original graph up to time $k$ . This construction transforms the cyclic identification problem into a DAG identification problem.
Condensation Digraph: For general digraphs, the authors utilize the condensation digraph $C(G)$ , where each strongly connected component is collapsed into a single node. Since $C(G)$ is a DAG, the results derived for DAGs are applied to $C(G)$ to determine the necessary measurements for the original graph.

Key Contributions and Results

Impossibility in General Nonlinear Classes: The paper demonstrates that for the class of all functions ( $\mathcal{F}_{ALL}$ ), identifiability is impossible if any node has more than one in-neighbor, even with full measurement. This is due to the inability to distinguish constant shifts in additive functions (Proposition 2).
DAGs with Smooth Functions:
- For path graphs and trees in the class $\mathcal{F}_Z$ (continuously differentiable, $f(0)=0$ ), the measurement of the sink is necessary and sufficient.
- For general DAGs in the class $\mathcal{F}_{Z,NL}$ (twice continuously differentiable, $f(0)=0$ , and not purely linear), the measurement of all sinks is necessary and sufficient (Theorem 1).
- Significance: Unlike linear systems, where identifying outgoing edges of a node requires multiple vertex-disjoint paths to measured nodes, nonlinear systems allow the identification of all edges by measuring only the sinks, provided the functions are sufficiently smooth and non-linear.
General Digraphs:
- Under the assumptions of initial rest and additively separable functions, a general digraph is identifiable if and only if one node is measured in every sink of the condensation digraph (Theorem 2).
- This result extends the DAG findings to cyclic networks by leveraging the unfolded digraph construction, proving that measuring the sinks of the condensation graph guarantees the identifiability of all walks in the original network.

Significance and Claims
The paper claims to derive the first identifiability conditions for nonlinear networks in discrete time based on network topology. The primary significance lies in the contrast with linear system identifiability:

Weaker Measurement Requirements: In nonlinear networks, the nonlinearity of the functions allows the system to distinguish information arriving via different paths (unlike the superposition principle in linear systems). Consequently, the requirement for multiple disjoint paths to measured nodes is relaxed.
Necessity of Sink Measurement: The authors show that for DAGs, measuring sinks is not just sufficient but necessary. If a sink is not measured, its incoming edges cannot be identified.
Role of Function Properties: The results highlight that identifiability is heavily dependent on the class of functions. Specifically, the presence of constant terms (non-zero $f(0)$ ) renders identifiability impossible for nodes with multiple in-neighbors, and purely linear functions prevent the separation of paths that nonlinear derivatives enable.

The paper concludes that while the analysis assumes ideal conditions (perfect knowledge of global behavior, specific function classes), these theoretical bounds provide a fundamental intuition for experimental design. If an edge is not identifiable under perfect information, it cannot be identified with partial information. The work sets a foundation for future research into non-additive models and non-differentiable function classes.