⚡ electrical engineering

Path-Based Conditions for the Identifiability of Non-additive Nonlinear Networks with Full Measurements

This paper establishes that for nonlinear networks with non-additive dynamics under full measurements, generic identifiability is guaranteed for directed acyclic graphs if vertex-disjoint paths exist from excited nodes to the in-neighbors of each node, and proves this condition is necessary for polynomial functions while noting it does not apply to additive nonlinear models.

Original authors: Renato Vizuete, Julien M. Hendrickx

Published 2026-07-23

📖 4 min read☕ Coffee break read

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 you are a detective trying to solve a mystery inside a giant, invisible machine. This machine is a "network," a web of connected parts where one part whispers a secret to the next, which then whispers to the next, and so on. In the world of science, this is called system identification. The goal is to figure out exactly how each part of the machine works just by listening to what it says. Usually, we assume we know the map of the machine (who is connected to whom), but we don't know the specific rules or "functions" that turn an input into an output. It's like knowing that a pipe connects a faucet to a sink, but not knowing if the water flows fast, slow, or if the pipe has a weird bend that changes the water's shape.

For a long time, scientists mostly studied machines where the rules were simple and additive. Think of it like a recipe where you just add ingredients together: one cup of flour plus two eggs equals a batter. In these simple cases, the math is straightforward. But real life is messier. Many modern systems, like the artificial brains in your phone or the way people change their opinions in a social group, are non-additive. This means the ingredients don't just add up; they mix and interact in complex, non-linear ways. Maybe a little bit of flour changes how the eggs behave, or two ingredients cancel each other out. The big question is: If the rules are this complicated, and we can't see the inside of the machine, can we still figure out exactly how every single part works?

This paper tackles that exact puzzle. The authors, Renato Vizuete and Julien M. Hendrickx, investigate whether we can identify the hidden rules of these complex, non-additive networks when we can measure the output of every single node in the system. They introduce a clever concept called "generic identifiability." Instead of asking if we can solve the puzzle for every single possible set of rules (which might be impossible for some weird, rare cases), they ask if we can solve it for almost all rules. It's like saying, "If you pick a random lock from a million, can you pick it?" If the answer is yes for 99.9% of locks, that's good enough for most practical purposes.

The team discovers that for networks that don't have any loops (called Directed Acyclic Graphs, or DAGs—think of a river flowing downstream without any waterfalls that loop back up), there is a specific "key" to unlocking the mystery. They prove that if you can send a signal from your "excited" starting points to the inputs of every other node using paths that never cross each other (vertex-disjoint paths), then you can almost certainly figure out the hidden rules. They use a mathematical tool called an "unfolded digraph," which is like taking a movie of the network and laying out every frame side-by-side to see the flow of information clearly. By analyzing the "rank" of a special matrix built from this flow, they show that if the paths are disjoint, the information is unique enough to solve the puzzle.

However, the paper also draws a sharp line in the sand. While this "disjoint path" rule is a sure-fire way to guarantee identification for complex, non-additive networks, it is not the only way. The authors show that for a specific type of simple, additive network (where ingredients just add up), you might still be able to solve the puzzle even if the paths cross. But for the more complex, non-additive networks they focus on, if you don't have those clean, non-crossing paths, the puzzle is generally impossible to solve specifically for the class of polynomial functions. They prove this using algebraic geometry, showing that without those paths, there are always multiple different sets of rules that could produce the exact same output, making it impossible to know which one is the real one. (Note: While the paper establishes this impossibility for polynomials, the status for all possible analytic functions remains an open question).

In short, the paper provides a rigorous map for when we can trust our detective work. It tells us that for complex, interacting systems, we need a very specific kind of "signal traffic" to ensure we aren't just guessing. If the signals from our starting points can reach every part of the network without bumping into each other, we are golden. If they collide and merge, the mystery might remain unsolved. This helps engineers and scientists design better experiments and sensors, ensuring they have the right setup to understand the complex, non-linear world around them.

Technical Summary: Path-Based Conditions for the Identifiability of Non-additive Nonlinear Networks with Full Measurements

Problem Formulation
This work addresses the system identification problem for networks characterized by non-additive nonlinear dynamics. Unlike previous studies that assume additive models where node dynamics are sums of independent edge functions, this paper considers a generalized model where the dynamics of a node $i$ are governed by a multivariate nonlinear function $\Phi_i$ of the past outputs of its in-neighbors. This function cannot necessarily be decomposed into a sum of edge-wise terms, a scenario relevant to applications such as neural networks and opinion dynamics.

The study focuses on the "full measurement" case, where the output of every node in the network is observable. The network topology is assumed to be known, and the objective is to determine which nodes must be excited (driven by external signals) to uniquely identify the local dynamics $\Phi_i$ of all nodes. The analysis is restricted to Directed Acyclic Graphs (DAGs) to ensure the system output can be expressed as a Nonlinear Finite Impulse Response (NFIR) model dependent on a finite number of excitation signals.

Methodology and Definitions
To handle the infinite-dimensional space of nonlinear functions, the authors introduce the concept of generic identifiability. A network is generically identifiable if the node functions are uniquely determined for almost all parameter choices, excluding a set of measure zero. The authors define this rigorously using a $K$ -analytic parametrization, where functions are expanded into Taylor series, and genericity is defined with respect to the coefficients of the lower-order terms.

Key methodological tools include:

Unfolded Digraphs ( $H_v(G)$ ): The network is transformed into an unfolded digraph where nodes are replicated across time steps to account for delays. This structure allows the mapping of time-delayed dependencies into a static graph representation.
Nonlinear Network Matrix ( $J_{H_v(G)}$ ): A matrix is constructed based on the derivatives of the nonlinear functions in the unfolded graph. This matrix serves as a nonlinear analogue to the weighted adjacency matrix in linear systems.
Vertex-Disjoint Paths: The core structural condition analyzed is the existence of vertex-disjoint paths from the set of excited nodes to the in-neighbors of every node in the network.

Key Contributions and Results

Sufficient Condition for Analytic Functions: For DAGs composed of analytic functions, the paper derives a sufficient condition for generic identifiability. Specifically, if there exist vertex-disjoint paths from the excited nodes to the in-neighbors of every node in the network, the system is generically identifiable. This result is proven using an inductive argument on the topological ordering of the DAG, leveraging the surjectivity of the Jacobian mapping of the excitation signals to the node outputs.
Necessity for Polynomial Functions: For the specific class of polynomial functions, the authors prove that the vertex-disjoint path condition is not only sufficient but also necessary. If the condition is not met (i.e., the number of vertex-disjoint paths to the in-neighbors is insufficient), the system is unidentifiable. This is demonstrated using results from algebraic geometry, specifically the theory of affine algebraic varieties, showing that without sufficient disjoint paths, one can always construct a non-zero polynomial function that vanishes on the observed data, rendering the true dynamics non-unique.
Distinction from Additive Models: The paper highlights a critical divergence between non-additive and additive nonlinear models. In additive models, the vertex-disjoint path condition is not necessary for identifiability. The authors provide a counterexample where an additive network is identifiable despite lacking sufficient vertex-disjoint paths, due to the separability of the node functions which prevents the cancellation of specific interaction terms. Conversely, in the non-additive case, the lack of separability allows for complex cancellations that can obscure the dynamics if the path condition is not met.
Role of Sources and Sinks: The analysis establishes that exciting all source nodes is necessary for identifiability, while exciting sink nodes is never necessary. Furthermore, measuring source nodes is not required for identifiability as their outputs are purely the excitation signals.

Significance and Claims
The paper claims to provide a rigorous characterization of generic identifiability for non-additive nonlinear networks, a class of systems where previous conditions were either insufficient or restricted to additive models. By introducing a formal definition of genericity based on nonlinear matrices and unfolded digraphs, the work bridges the gap between linear structural identifiability and complex nonlinear dynamics.

The authors emphasize that their results clarify the limitations of path-based conditions in nonlinear settings: while the condition is sufficient for analytic functions and necessary for polynomials in the non-additive case, it is not necessary for additive nonlinear models. This distinction underscores the impact of nonlinearity structure on identifiability, suggesting that the "lower risk of ambiguities" often attributed to nonlinear superposition does not universally relax structural requirements when the dynamics are non-additive.

The work concludes by noting that extending these conditions to graphs containing loops (cycles) remains an open problem, as this would involve systems dependent on an infinite number of excitation signals.

More like this