# Nonlinear Network Identifiability with Full Excitations

Renato Vizuete and Julien M. Hendrickx This work was supported by F.R.S.-FNRS
via the _KORNET_ project and via the Incentive Grant for Scientific Research
(MIS) _Learning from Pairwise Comparisons_ , and by the _RevealFlight_
Concerted Research Action (ARC) of the Fédération Wallonie-Bruxelles.R.
Vizuete and J. M. Hendrickx are with ICTEAM institute, UCLouvain, B-1348,
Louvain-la-Neuve, Belgium. R. Vizuete is a FNRS Postdoctoral Researcher - CR.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We derive conditions for the identifiability of nonlinear networks
characterized by additive dynamics at the level of the edges when all the
nodes are excited. In contrast to linear systems, we show that the measurement
of all sinks is necessary and sufficient for the identifiability of directed
acyclic graphs, under the assumption that dynamics are described by analytic
functions without constant terms (i.e., $f(0)=0$). But if constant terms are
present, then the identifiability is impossible as soon as one node has more
than one in-neighbor. In the case of general digraphs where cycles can exist,
we consider additively separable functions for the analysis of the
identifiability, and we show that the measurement of one node of all the sinks
of the condensation digraph is necessary and sufficient. Several examples are
added to illustrate the results.

###### Index Terms:

Network analysis and control, system identification.

##  I Introduction

Networked systems composed of single entities or subsystems that interact in a
network can be found in many domains including biological networks, power
networks, social networks, etc [1, 2]. In this type of systems, one of the
most important characteristics is the network topology, which models the
exchange of information among the nodes. However, in many networks, different
dynamical systems may also be associated at the level of edges or nodes, which
generates a more complex behavior in the system.

Knowledge of the interactions between the nodes is useful and in many
situations can be essential for the analysis, estimation and control of
networks [3]. For this reason, the identification of networks has become an
important research area where the objective is to identify the network
topology and all the dynamics associated with nodes and edges [4, 5, 6, 7].
Since in many networks the number of nodes and edges can be relatively large,
the appropriate placement of sensors and instruments to perform experiments
for the identification process is crucial [8, 9, 10]. In this case, when the
network topology is available, the notion of _identifiability_ plays an
important role since it allows us to determine which nodes should be excited
and measured to identify the different dynamics in the network. The
identifiability problem in networks has been extensively studied in the case
of linear systems associated with edges where, based on the knowledge of the
network topology, conditions for the full measurement or full excitation cases
have been provided in [11, 12]. The case of partial measurement/excitation has
been analyzed in several works [13, 14, 15, 16, 17] where different
identifiability conditions have been proposed depending on the scenario,
though no necessary and sufficient condition is known. However, most of real
networks are nonlinear, including systems in important fields of interest like
coupled oscillators [18], gene regulatory networks [19], biochemical reaction
networks [20], organic reactions [21], social networks [22], among others. To
the best of our knowledge, the problem of identifiability of nonlinear
networks has not been previously analyzed.

The identification of even a single nonlinear system is a challenging task due
to the diverse types of nonlinearities and models that can be used to
reproduce the behavior of the system [23]. In fact, the choice of the model
might depend on the type of application and some particular models could not
be well suited for several systems [24, 25, 26]. At the level of nonlinear
networks, the complexity increases considerably since essentially the
identification of nonlinear functions that represent the dynamics of edges or
nodes must be performed without disconnecting the network. In this case,
identifiability conditions could be even more important than in the linear
case since in general the experiments for nonlinear identification are more
complex and expensive, so that the knowledge of which nodes should be excited
and measured is fundamental. Although the analysis of identifiability is based
on all the information that could theoretically be obtained from measurements
(even if it would not necessarily be practical to obtain so much information),
it can give us a good intuition for the outcome of experiments. If an edge is
not identifiable based on such perfect information, then it can certainly not
be identified with partial information. On the other hand, if an edge can be
identified in the ideal situation, it could be possible that with appropriate
experiments we manage to obtain an approximation of the edge.

The class of functions considered in the identifiability of nonlinear networks
is important for the derivation of conditions that guarantee the
identification. The nonlinear dynamics of real networks can be modeled by
functions of different nature like trigonometric in coupled oscillators [18]
or non-differentiable in neural networks [27]. Clearly, the identifiability
should be analyzed in a specific class of functions and an appropriate
delimitation of this class is fundamental. If the class of functions is too
restrictive, it could be easier to guarantee identifiability but the type of
functions could not match real dynamical models. If the class of functions is
overly general, identifiability might be very restrictive since many different
functions could satisfy the information obtained with measurements.
Nevertheless, we will derive strong results for the identifiability of
nonlinear networks for very general classes of functions.

A preliminary version of this work was presented in [28] where identifiability
conditions for directed acyclic graphs (DAGs) characterized by nonlinear
static interactions were derived in the full excitation case to highlight the
differences with linear networks. By contrast, in this work, we derive
identifiability conditions in the full excitation case for more complex
nonlinear networks where the edges are characterized by nonlinear dynamical
systems (i.e., involving memory), and cycles are allowed. In this way, our
results can be applied to real networks where the dynamics is one of the main
characteristics of the edges and the presence of cycles is common.

The remainder of this article is organized as follows. In Section II, we
present the dynamical model associated with each node and the notions of
identifiability at the level of edges and networks. In Section III, we study
the identifiability problem in DAGs. For path graphs and trees, we analyze the
identifiability problem in a smaller class of functions where each function is
analytic and the static part is removed, and we show that the measurement of
the sink is necessary and sufficient for identifiability. In the case of
general DAGs, we discard linear functions for the identifiability problem and
we prove that the measurement of the sinks is necessary and sufficient for the
identifiability. Section IV focuses on the case of general digraphs where
cycles are allowed. By considering that the network is at rest at the initial
time, we show that by measuring a node of all the sinks of the condensation
digraph, we guarantee the identifiability of any digraph. Finally, conclusions
and future perspectives for the identifiability of nonlinear networks are
exposed in Section V.

##  II Problem formulation

###  II-A Notation

Scalars are denoted by $x\in\mathbb{R}$ and vectors are denoted by
$\mathbf{x}\in\mathbb{R}^{n}$. The vector of an appropriate size constituted
of only zeros is denoted by $\mathbf{0}$. The value of a general input or
output $x$ at the time instant $k$ is denoted by $x^{k}$. The shift operator
acting on a vector $\mathbf{x}=(x_{1},\ldots,x_{n})$ corresponds to a shift of
coordinates and it is denoted by
$\tau^{p}\mathbf{x}=(x_{1+p},\ldots,x_{n+p})$, where we assume that
$\mathbf{x}$ is well defined for coordinates $x_{i}$ with $i>n$.

###  II-B Model class

We consider the identifiability problem in a network where the dynamics are
additive on the edges and have finite memory. The network is characterized by
a weakly connected digraph $G=(V,E)$ composed by a set of nodes
$V=\\{1,\ldots,n\\}$ and a set of edges $E\subseteq V\times V$. The output of
each node $i$ in the network is given by:

$y_{i}^{k}=\sum_{j\in\mathcal{N}_{i}}f_{i,j}(y_{j}^{k-0},y_{j}^{k-1},y_{j}^{k-2},\ldots,y_{j}^{k-m_{j}})+u_{i}^{k-1},$
(1)

where $y_{i}^{k}$ is the state of the node $i$, $u_{i}^{k-1}$ is an external
excitation signal, $\mathcal{N}_{i}$ is the set of in-neighbors of node $i$
without including $i$, $f_{i,j}$ is a nonzero nonlinear function depending on
past outputs of the neighbors $j$ of the node $i$, and each delay
$m_{j}\in\mathbb{Z}^{\geq}$ is finite (i.e., finite memory). The model (1) is
causal if the nonlinear functions $f_{i,j}$ do not depend on $y_{j}^{k-0}$
(i.e., $f_{i,j}(y_{j}^{k-1},y_{j}^{k-2},\ldots,y_{j}^{k-m_{j}})$ with
$m_{j}\in\mathbb{Z}^{+}$), and along this work we will only consider the
identifiability of causal models (real-world dynamics). The particular case of
a delay $m_{j}=0$ will be used only for the adapted DAG introduced in Section
IV, which is a mathematical construction used in the proof of Theorem 2. The
model (1) implies that the output of a node $i$ in the network is determined
by its own excitation signal and the past outputs of its neighbors that are
affected by nonlinear functions $f_{i,j}$ located in each edge that connect
the neighbors with the node $i$. Furthermore, the model (1) corresponds to the
full excitation case where all the nodes in the network can be excited through
the inputs $u_{i}$. When the functions $f_{i,j}$ are linear, the
identifiability problem with full excitations has been studied in [11]. In
this work, we will consider analytic functions, whose representation as power
series will allow us to derive conditions for the identifiability of nonlinear
networks.

######  Assumption 1.

The topology of the network is known, where the presence of an edge implies a
nonzero function.

Assumption 1 implies that we know which nodes are connected by nonzero
functions. Similarly to [11, 13, 14], for the identification process we assume
that in an ideal scenario the relations between excitations and outputs of the
nodes have been perfectly identified and all nodes are excited. In the first
part, we focus on networks that do not contain any cycle (i.e., DAGs). Due to
the absence of cycles and finite memory, the function $F_{i}$ associated with
the measurement of a node $i$, depends on a finite number of inputs:

$y_{i}^{k}=u_{i}^{k-1}+F_{i}(u_{1}^{k-2},\ldots,u_{1}^{k-T_{1}},\ldots,u_{n_{i}}^{k-2},\ldots,u_{n_{i}}^{k-T_{n_{i}}}),\\\
1,\dots,n_{i}\in\mathcal{N}_{i}^{p},$ (2)

where $\mathcal{N}_{i}^{p}$ is the set of nodes with a path to node $i$. The
function $F_{i}$ is implicitly defined by (1) and the inputs in $F_{i}$
correspond to the nodes that have a path to the measured node $i$.

######  Assumption 2.

If the node $i$ is measured, the function $F_{i}$ is known.

With a slight abuse of notation, we use the superscript in the function
$F_{i}^{(s)}$ to indicate that all the inputs in (2) are delayed by $s$ (i.e.,
$F_{i}^{(s)}=F_{i}(u_{1}^{k-2-s},\ldots,u_{n_{i}}^{k-T_{n_{i}}-s})$).

123$f_{2,1}$$f_{3,2}$$f_{3,1}$$u_{1}$$u_{2}$$u_{3}$ Figure 1: DAG where the
function associated with the measurement of the node $3$ only depends on a
finite number of inputs.

######  Example 1 (Finite inputs).

Let us consider the DAG in Fig. 1 with nonlinear functions of the form
$f_{3,2}(y_{2}^{k-1})$, $f_{3,1}(y_{1}^{k-1},y_{1}^{k-2})$ and
$f_{2,1}(y_{1}^{k-1})$. The measurement of the node 3 provides an output of
the type:

$\displaystyle y_{3}^{k}$
$\displaystyle=u_{3}^{k-1}+f_{3,2}(y_{2}^{k-1})+f_{3,1}(y_{1}^{k-1},y_{1}^{k-2})$
$\displaystyle=u_{3}^{k-1}+f_{3,2}(u_{2}^{k-2}+f_{2,1}(u_{1}^{k-3}))+f_{3,1}(u_{1}^{k-2},u_{1}^{k-3}),$
(3)

so that the function $F_{3}$ associated with the measurement is a function of
a finite number of variables $F_{3}(u_{1}^{k-2},u_{1}^{k-3},u_{2}^{k-2})$.

###  II-C Identifiability

We first define the relationships between the measurements of the nodes and
the functions $f_{i,j}$.

######  Definition 1 (Set of measured functions).

Given a set of measured nodes $\mathcal{N}^{m}$, the set of measured functions
$F(\mathcal{N}^{m})$ associated with $\mathcal{N}^{m}$ is given by:

$F(\mathcal{N}^{m}):=\\{F_{i}\;|\;i\in\mathcal{N}^{m}\\}.$

We say that a digraph $G$ and a set of functions $f_{i,j}$ generate
$F(\mathcal{N}^{m})$ if the functions $F_{i}\in F(\mathcal{N}^{m})$ are
obtained through (1).

Since the identifiability problem can be hard or unrealistic for general
functions, we restrict the problem to a certain class of functions
$\mathcal{F}$: the functions associated with the edges belong to $\mathcal{F}$
and the identifiability is considered only among the functions belonging to
$\mathcal{F}$. The different classes of functions will be defined depending on
the different types of network topologies considered for the analysis.

######  Definition 2 (Identifiability).

Given a set of functions $\\{f\\}=\\{f_{i,j}\in\mathcal{F}\;|\;(i,j)\in E\\}$
that generates $F(\mathcal{N}^{m})$ and another set of functions
$\\{\tilde{f}\\}=\\{\tilde{f}_{i,j}\in\mathcal{F}\;|\;(i,j)\in E\\}$ that
generates $\tilde{F}(\mathcal{N}^{m})$. An edge $f_{i,j}$ is identifiable in a
class $\mathcal{F}$ if $F(\mathcal{N}^{m})=\tilde{F}(\mathcal{N}^{m})$,
implies that $f_{i,j}=\tilde{f}_{i,j}$. A network $G$ is identifiable in a
class $\mathcal{F}$ if $F(\mathcal{N}^{m})=\tilde{F}(\mathcal{N}^{m}),$
implies that $\\{f\\}=\\{\tilde{f}\\}.$

According to Definition 2, in a network $G$, an edge $f_{i,j}$ is identifiable
in a class $\mathcal{F}$ if given a set of measured functions
$F(\mathcal{N}^{m})$, every set of functions in $\mathcal{F}$ leading to
$F(\mathcal{N}^{m})$ has the same $f_{i,j}$ [28]. A network $G$ is
identifiable in a class $\mathcal{F}$ if all the edges are identifiable in the
class $\mathcal{F}$ [28].

Although Assumption 2 seems strong, it is clear that if a function $f_{i,j}$
cannot be identified with $F_{i}$, it is unidentifiable based on the
measurement of this node. However, if the function $f_{i,j}$ is identifiable
based on $F_{i}$, it is expected that a good approximation of $F_{i}$ with
experiments, may eventually provide a good approximation of the function
$f_{i,j}$. Thus, the possibility of identifying $f_{i,j}$ could be determinant
for the approximation of these functions based on measurements and experiments
[29].

##  III Directed acyclic graphs (DAGs)

We now begin by deriving identifiability conditions for networks that do not
contain any cycle (i.e., DAGs), considering specific classes of functions.

DAGs encompass a large number of graph topologies that present specific
characteristics that can be used for the derivation of conditions for
identifiability [30, 31]. Since sources and sinks 111A source is a node with
no incoming edges. A sink is a node with no outgoing edges. are important
nodes in DAGs, we first provide a result similar to the static case in [28]
about the information that we can obtain from the measurements of these nodes.

######  Proposition 1 (Sinks and sources).

The measurement of the sources is never necessary for the identifiability of
the network. The incoming edges of sinks are not identifiable if the sinks are
not measured.

###### Proof.

First, the measurement of any source $\ell$ generates the output
$y_{\ell}^{k}=u_{\ell}^{k-1}$, which does not provide any information about
functions associated with edges in the network. Then, let us consider a sink
$i$ with $\left|\mathcal{N}_{i}\right|$ in-neighbors. The measurement of this
sink provides the output:

$y_{i}^{k}=u_{i}^{k-1}+\sum_{j\in\mathcal{N}_{i}}f_{i,j}(y_{j}^{k-1},\ldots,y_{j}^{k-m_{j}}),$

and it is the only way of obtaining information about the functions $f_{i,j}$
for $j\in\mathcal{N}_{i}$. Thus, if the sink $i$ is not measured, the incoming
edges $f_{i,j}$ are not identifiable. ∎

###  III-A Identifiability of general nonlinear functions

We start by considering the identifiability problem in the class of all
analytic functions.

######  Definition 3 (Class of functions $\mathcal{F}_{ALL}$).

Let $\mathcal{F}_{ALL}$ be the class of all analytic functions
$f:\mathbb{R}^{m}\to\mathbb{R}$.

Notice that the dimension $m$ corresponds to the function $f_{i,j}$ in the
network with the largest number of arguments (i.e., number of past inputs).

Unfortunately, the following proposition shows that even in the trivial case
when we measure all the nodes, there are some important network topologies
where the identifiability problem is unsolvable in the class
$\mathcal{F}_{ALL}$.

######  Proposition 2 (Unidentifiability).

If a DAG contains two (or more) edges arriving at a same node, then none of
them are identifiable in $\mathcal{F}_{ALL}$.

###### Proof.

Let us consider an arbitrary DAG with a node $i$ with 2 or more in-neighbors.
Let us assume that we measure all the nodes (i.e., $\mathcal{N}^{m}=V$), which
is all the information that we can get from a network. Since the function
$F_{i}\in F(\mathcal{N}^{m})$, we obtain:

$\displaystyle y_{i}^{k}$ $\displaystyle=u_{i}^{k-1}+F_{i}$
$\displaystyle=u_{i}^{k-1}\\!+\\!\sum_{j\in\mathcal{N}_{i}}\\!f_{i,j}(u_{j}^{k-2}\\!+\\!F_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}\\!+\\!F_{j}^{(m_{j})}).$

Let us consider two arbitrary in-neighbors $p$ and $q$ of the node $i$ and set
the functions $\tilde{f}_{i,p}=f_{i,p}+\gamma$ and
$\tilde{f}_{i,q}=f_{i,q}-\gamma$, with $\gamma\neq 0$. Notice that $F_{i}$ can
also be obtained with the functions $\tilde{f}_{i,p}$ and $\tilde{f}_{i,q}$,
which implies that these edges cannot be identified. ∎

$p$$i$$q$$f_{i,p}$$\tilde{f}_{i,p}=f_{i,p}+\gamma$$\tilde{f}_{i,q}=f_{i,q}-\gamma$$f_{i,q}$DAG
Figure 2: If a DAG has at least a node $i$ with two or more in-neighbors, then
it is not identifiable in the class $\mathcal{F}_{ALL}$.

Proposition 2 implies that DAGs having nodes with two or more in-neighbors
cannot be identified, which restricts considerably the types of networks that
can be identified in the class $\mathcal{F}_{ALL}$. In the following
proposition we show that the identifiability of graphs where all the nodes
have only 1 in-neighbor (i.e., an arborescence) is possible but requires the
measurement of all the nodes except by the source.

######  Proposition 3 (Arborescence).

An arborescence is identifiable in the class $\mathcal{F}_{ALL}$, if and only
if all the nodes are measured except possibly the source.

###### Proof.

Let us consider an arborescence with $n>2$ nodes and a node $i$, which is
neither the source nor a sink 222An arborescence can have several sinks but
only one source.. The output of an out-neighbor of $i$ denoted by $i+1$ is
given by:

$\displaystyle y_{i+1}^{k}$ $\displaystyle=u_{i+1}^{k-1}+F_{i+1}$ (4)
$\displaystyle=u_{i+1}^{k-1}+f_{i+1,i}(u_{i}^{k-2}+F_{i}^{(1)},\ldots,u_{i}^{k-m_{i}-1}+F_{i}^{(m_{i})})$
$\displaystyle=u_{i+1}^{k-1}+f_{i+1,i}(u_{i}^{k-2}+f_{i,i-1}(u_{i-1}^{k-3}+F_{i-1}^{(2)},\ldots),\ldots,$
$\displaystyle\quad\>\>u_{i}^{k-m_{i}-1}+f_{i,i-1}(u_{i-1}^{k-m_{i}-2}+F_{i-1}^{(m_{i}-1)},\ldots)),$

where $i-1$ is the in-neighbor of $i$. If the node $i$ is not measured, we can
consider the functions
$\tilde{f}_{i,i-1}(\mathbf{x})=f_{i,i-1}(\mathbf{x})+\gamma$ and
$\tilde{f}_{i+1,i}(\mathbf{x})=f_{i+1,i}(x_{1}-\gamma,\ldots,x_{m_{i}}-\gamma)$
with $\gamma\neq 0$, that generate $\tilde{F}_{i+1}$ and satisfy
$F_{i+1}=\tilde{F}_{i+1}$ in (4), which implies that the arborescence cannot
be identified.

On the other hand, if we measure all the nodes (i.e., $\mathcal{N}^{m}=V$), we
know the function $F_{j}$ associated with any node $j$ in the network. Let us
consider a node $i$ with an in-neighbor and we set all the inputs to zero
except $u_{i}$ with the corresponding delays. Then, the measurement of the
node $i$ gives us:

$\displaystyle y_{i}^{k}$ $\displaystyle=u_{i}^{k-1}+F_{i}$ (5)
$\displaystyle=u_{i}^{k-1}+f_{i,i-1}(u_{i}^{k-2}+F_{i-1}^{(1)}(\mathbf{0}),\ldots,$
$\displaystyle\quad\>\>u_{i}^{k-m_{i-1}-1}+F_{i-1}^{(m_{i-1})}(\mathbf{0})).$

If there is another function $\tilde{f}_{i,i-1}$ that generates
$\tilde{F}_{i}$ and satisfies $F_{i}=\tilde{F}_{i}$ in (5), we would have for
all $u_{i}^{k-2},\ldots,u_{i}^{k-m_{i-1}-1}\in\mathbb{R}$:

$f_{i,i-1}(u_{i}^{k-2}+F_{i-1}(\mathbf{0}),\ldots,u_{i}^{k-m_{i-1}-1}+F_{i-1}^{(m_{i-1})}(\mathbf{0}))=\\\
\tilde{f}_{i,i-1}(u_{i}^{k-2}+F_{i-1}(\mathbf{0}),\ldots,u_{i}^{k-m_{i-1}-1}+F_{i-1}^{(m_{i-1})}(\mathbf{0})),$

which implies that $f_{i,i-1}=\tilde{f}_{i,i-1}$ because all the $F_{i-1}$ are
the same, and we thus identify $f_{i,i-1}$. Since the node $i$ was arbitrary,
the analysis holds for the other nodes and therefore all the nonlinear
functions in the arborescence are identified. By Proposition 1, it is never
necessary to measure the source. Finally, since each edge between two measured
nodes is identified, it is sufficient to measure all the nodes except possibly
the source, which does not provide information. ∎

Notice that in the proofs of Propositions 2 and 3 we do not use properties of
analytic functions and the results are also valid for nonlinear functions that
are not analytic. We can see that even for simple topologies like
arborescences, the identifiability problem requires the measurement of all the
nodes except by the source, which could be impractical due to physical
limitations and economic costs. Furthermore, as Proposition 2 showed, for more
complex graph topologies, even the measurement of all the nodes is not enough
to identify all the nonlinear functions in a network. From the proof of
Proposition 2, we can see that the main problem is the identification of the
static part of the nonlinear functions since it requires more information
through the measurement of additional nodes. Therefore, we will consider
nonlinear functions where no static part is present (i.e., only a dynamic
part), which could be interpreted as the difference with respect to the steady
state.

######  Definition 4 (Class of functions $\mathcal{F}_{Z}$).

Let $\mathcal{F}_{Z}$ be the class of functions
$f:\mathbb{R}^{m}\to\mathbb{R}$ with the following properties:

  1. 1.

$f$ is analytic in $\mathbb{R}^{m}$.

  2. 2.

$f(\mathbf{0})=0$.

###  III-B Path graphs and trees

The notion of paths plays an important role in the identifiability problem in
networks since they carry information between the excited nodes and the
measured nodes. For this reason, in this section, we focus first on the
identifiability of path graphs 333A path graph is a digraph that can be drawn
so that all the nodes and edges lie on a single straight line.. Before, we
need the following lemma about the identifiability of in-neighbors.

######  Lemma 1.

Let $G$ be a DAG such that the edge $(i,j)$ is the only path from the node $j$
to the node $i$. Then if $i$ is measured, $f_{i,j}$ is identifiable in the
class $\mathcal{F}_{Z}$.

###### Proof.

The measurement of the node $i$ provides the output:

$y_{i}^{k}=u_{i}^{k-1}+\sum_{\ell\in\mathcal{N}_{i}}f_{i,\ell}(u_{\ell}^{k-2}+F_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+F_{\ell}^{(m_{\ell})}).$
(6)

Since $F_{i}\in F(\mathcal{N}^{m})$, let us assume that there exists a set
$\\{\tilde{f}\\}\neq\\{f\\}$ such that $F_{i}=\tilde{F}_{i}$, which implies:

$\sum_{\ell\in\mathcal{N}_{i}}f_{i,\ell}(u_{\ell}^{k-2}+F_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+F_{\ell}^{(m_{\ell})})=\\\
\sum_{\ell\in\mathcal{N}_{i}}\tilde{f}_{i,\ell}(u_{\ell}^{k-2}+\tilde{F}_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+\tilde{F}_{\ell}^{(m_{\ell})}).$
(7)

Let us set to zero all the inputs except the inputs of the node
$j\in\mathcal{N}_{i}$ with their respective delays. Since $(i,j)$ is the only
path between $i$ and $j$, the functions $F_{\ell}$, $\tilde{F}_{\ell}$ do not
depend on the inputs $u_{j}$, and given that all the functions are in the
class $\mathcal{F}_{Z}$, the equality (7) becomes:

$f_{i,j}(u_{j}^{k-2}+F_{j}^{(1)}(\mathbf{0}),\ldots,u_{j}^{k-m_{j}-1}+F_{j}^{(m_{j})}(\mathbf{0}))=\\\
\tilde{f}_{i,j}(u_{j}^{k-2}+\tilde{F}_{j}^{(1)}(\mathbf{0}),\ldots,u_{j}^{k-m_{j}-1}+\tilde{F}_{j}^{(m_{j})}(\mathbf{0})).$

which yields for all $u_{j}^{k-2},\ldots,u_{j}^{k-m_{j}-1}\in\mathbb{R}$:

$f_{i,j}(u_{j}^{k-2},\ldots,u_{j}^{k-m_{j}-1})=\tilde{f}_{i,j}(u_{j}^{k-2},\ldots,u_{j}^{k-m_{j}-1}).$

Therefore, we obtain $f_{i,j}=\tilde{f}_{i,j}$, which implies that the
function $f_{i,j}$ is identifiable. ∎

This leads to the following corollary.

######  Corollary 1.

For identifiability in the class $\mathcal{F}_{Z}$, the measurement of a node
$i$ provides the identification of all the incoming edges corresponding to in-
neighbors with only one path to $i$.

###### Proof.

The proof is simply based on the successive application of Lemma 1 for other
in-neighbors with only one path to the measured node $i$. ∎

Due to the presence of past inputs, Corollary 1 is different from Lemma 2 in
our preliminary work [28] corresponding to the static case, where the
measurement of a node provides the identification of all the incoming edges of
the node. For instance, let us consider again the network in Fig. 1 and the
nonlinear functions of Example 1. Notice that based on (3), the function
$f_{3,2}$ can be identified by setting to zero $u_{1}^{k-2}$ and
$u_{1}^{k-3}$, but the function $f_{3,1}$ cannot be identified by using the
same approach since $u_{1}^{k-3}$ is also present in $f_{3,2}$. This shows
that the identifiability problem in the dynamic case is clearly more complex
than in the static case.

Next, we provide the following technical lemma that will be used in the proofs
of the main results, where we remind that $\tau$ is the shift operator of
coordinates defined in Section II-A.

######  Lemma 2 (Multivariate function).

Given three nonzero analytic functions $f:\mathbb{R}^{p}\to\mathbb{R}$ and
$g,\tilde{g}:\mathbb{R}^{q}\to\mathbb{R}$ that satisfy:

$g(\mathbf{0})=\tilde{g}(\mathbf{0})=0;$
$f(x_{1}\\!+\\!g(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,x_{p}\\!+\\!g(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}))=\\\
f(x_{1}\\!+\\!\tilde{g}(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,x_{p}\\!+\\!\tilde{g}(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r})),$
(8)

then either $g=\tilde{g}$ or $f$ is constant.

###### Proof.

The proof is differed to Appendix -A ∎

Since the functions in the class $\mathcal{F}_{Z}$ satisfy $f(0)=0$, we have
the following corollary.

######  Corollary 2.

Under the same conditions as in Lemma 2, if $f(\mathbf{0})=0$, then

$g=\tilde{g}.$

######  Proposition 4 (Path graphs).

A path graph is identifiable in the class $\mathcal{F}_{Z}$ if and only if the
sink is measured.

###### Proof.

By Proposition 1 the measurement of the sink $i$ is necessary. The measurement
gives us the output:

$\displaystyle y_{i}^{k}$ $\displaystyle\\!=\\!u_{i}^{k-1}+F_{i}$
$\displaystyle\\!=\\!u_{i}^{k-1}\\!+\\!f_{i,i-1}(u_{i-1}^{k-2}\\!+\\!F_{i-1}^{(1)},\ldots,u_{i-1}^{k-m_{i-1}-1}\\!+\\!F_{i-1}^{(m_{i-1})}).$

Since $F_{i}\in F(\mathcal{N}^{m})$, let us assume that there exists a set
$\\{\tilde{f}\\}\neq\\{f\\}$ such that $F_{i}=\tilde{F}_{i}$, which
corresponds to the equality:

$f_{i,i-1}(u_{i-1}^{k-2}+F_{i-1}^{(1)},\ldots,u_{i-1}^{k-m_{i-1}-1}+F_{i-1}^{(m_{i-1})})=\\\
\tilde{f}_{i,i-1}(u_{i-1}^{k-2}+\tilde{F}_{i-1}^{(1)},\ldots,u_{i-1}^{k-m_{i-1}-1}+\tilde{F}_{i-1}^{(m_{i-1})}).$

Notice that $F_{i-1}$ and $\tilde{F}_{i-1}$ could at this stage be different
since the node $i-1$ has not been measured. Between the nodes $i$ and $i-1$
there is only one path corresponding to the edge $(i,i-1)$, which implies that
the function $f_{i,i-1}$ can be identified according to Lemma 1, so that
$f_{i,i-1}=\tilde{f}_{i,i-1}$. Then, we get:

$f_{i,i-1}(u_{i-1}^{k-2}+F_{i-1}^{(1)},\ldots,u_{i-1}^{k-m_{i-1}-1}+F_{i-1}^{(m_{i-1})})=\\\
f_{i,i-1}(u_{i-1}^{k-2}+\tilde{F}_{i-1}^{(1)},\ldots,u_{i-1}^{k-m_{i-1}-1}+\tilde{F}_{i-1}^{(m_{i-1})}).$

By virtue of Lemma 2 we can guarantee $F_{i-1}^{(1)}=\tilde{F}_{i-1}^{(1)}$.
This is equivalent to the mathematical constrained obtained with the
measurement of the node $i-1$ (i.e., $F_{i-1}\in F(\mathcal{N}^{m}$)) and we
can continue with the same procedure until we reach the root. In this way, we
guarantee $\\{f\\}=\\{\tilde{f}\\}$ and all the path can be identified. ∎

######  Proposition 5 (Trees).

A tree is identifiable in the class $\mathcal{F}_{Z}$, if and only if all the
sinks are measured.

###### Proof.

By Proposition 1 the measurement of all the sinks is necessary. Let us
consider one of the sinks $i$ of an arbitrary tree. The output is given by:

$\displaystyle y_{i}^{k}$ $\displaystyle=u_{i}^{k-1}+F_{i}$
$\displaystyle=u_{i}^{k-1}\\!+\\!\sum_{j\in\mathcal{N}_{i}}\\!f_{i,j}(u_{j}^{k-2}\\!+\\!F_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}\\!+\\!F_{j}^{(m_{j})}).$
(9)

Given that $F_{i}\in F(\mathcal{N}^{m})$, let us assume that there exists a
set $\\{\tilde{f}\\}\neq\\{f\\}$ such that $F_{i}=\tilde{F}_{i}$, which
implies:

$\sum_{j\in\mathcal{N}_{i}}f_{i,j}(u_{j}^{k-2}+F_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}+F_{j}^{(m_{j})})=\\\
\sum_{j\in\mathcal{N}_{i}}\tilde{f}_{i,j}(u_{j}^{k-2}+\tilde{F}_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}+\tilde{F}_{j}^{(m_{j})}).$
(10)

Since in a tree, between two nodes, there is only one path, we can choose an
arbitrary path that finishes in the sink $i$ and set to zero the excitation
signals of all the nodes that do not belong to that path. In this way, the
equality (10) corresponds to the identifiability of a path graph and by
Proposition 4 all the edges can be identifiable. We can use the same procedure
for other paths that finish in the sink $i$ to identify all the branches that
ends in $i$, and by measuring the other sinks, we can identify all the edges
in the tree. ∎

We recall that the case of arborescences are also included in Proposition 5.

###  III-C General DAGs

Unlike the particular case of trees, in more general DAGs, the functions
$F_{j}^{(1)}$ in (9) could depend on common variables due to several possible
paths between two nodes with the same length, which makes impossible to
isolate parts of the network through appropriate zero inputs. In addition,
some functions in the class $\mathcal{F}_{Z}$ might not be identifiable in a
DAG.

######  Example 2.

Let us consider the network in Fig. 3 with nonlinear functions of the form
$f_{4,3}(y_{3}^{k-1})$, $f_{4,2}(y_{2}^{k-1})$, $f_{2,1}(y_{1}^{k-1})$ and
$f_{3,1}(y_{1}^{k-1})$. The measurement of the node 4 provides an output of
the type:

$\displaystyle y_{4}^{k}$
$\displaystyle\\!=\\!u_{4}^{k-1}+f_{4,2}(y_{2}^{k-1})+f_{4,3}(y_{3}^{k-1})$
$\displaystyle\\!=\\!u_{4}^{k-1}\\!+\\!f_{4,2}(u_{2}^{k-2}\\!+\\!f_{2,1}(u_{1}^{k-3}))\\!+\\!f_{4,3}(u_{3}^{k-2}\\!+\\!f_{3,1}(u_{1}^{k-3})).$

The excitation signal $u_{1}^{k-3}$ appears in the the functions $f_{4,2}$ and
$f_{4,3}$, so that the different paths from 1 to 4 cannot be isolated by
setting to zero the corresponding excitation signals. Furthermore, let us
assume that the functions $f_{4,2}=a_{1}u_{2}^{k-1}$ and
$f_{4,3}=a_{2}u_{3}^{k-1}$ are linear. Then, we have:

$\displaystyle y_{4}^{k}$
$\displaystyle\\!=\\!u_{4}^{k-1}\\!+\\!a_{1}u_{2}^{k-2}\\!+\\!a_{2}u_{3}^{k-2}\\!+\\!a_{1}f_{2,1}(u_{1}^{k-3})\\!+\\!a_{2}f_{3,1}(u_{1}^{k-3})$
$\displaystyle\\!=\\!u_{4}^{k-1}\\!+\\!a_{1}u_{2}^{k-2}\\!+\\!a_{2}u_{3}^{k-2}\\!+\sum_{n=1}^{\infty}(a_{1}\alpha_{n}+a_{2}\beta_{n})(u_{1}^{k-3})^{n},$
(11)

where $f_{2,1}(x)=\sum_{n=1}^{\infty}\alpha_{n}x^{n}$ and
$f_{3,1}(x)=\sum_{n=1}^{\infty}\beta_{n}x^{n}$. There are infinitely many
possible values for each pair $(\alpha_{n},\beta_{n})$ that satisfy (11), and
each of them generates different functions $f_{2,1}$ and $f_{3,1}$. This is
due to the superposition principle that does not allow to distinguish the
information of node 1 that arrives through the node 2 or 3.

1243$f_{2,1}$$f_{4,2}$$f_{3,1}$$f_{4,3}$ Figure 3: Network with functions in
$\mathcal{F}_{Z}$ that cannot be identified by only measuring the sink when
$f_{2,1}$ and $f_{3,1}$ are linear due to the superposition principle.

For this reason, we restrict the identifiability problem to a smaller class of
functions [28].

######  Definition 5 (Class of functions $\mathcal{F}_{Z,NL}$).

Let $\mathcal{F}_{Z,NL}$ be the class of functions
$f:\mathbb{R}^{m}\to\mathbb{R}$ with the following properties:

  1. 1.

$f$ is analytic in $\mathbb{R}^{m}$.

  2. 2.

$f(\mathbf{0})=0$.

  3. 3.

At least one of the partial derivatives of $f$ is not constant.

Unlike the class $\mathcal{F}_{Z}$, the last condition in Definition 5 implies
that none of the functions $f$ in $\mathcal{F}_{Z,NL}$ is purely linear, which
still encompasses numerous nonlinear functions. Since in a DAG, an input can
influence a node via multiple paths, we cannot apply the argument of the proof
of Proposition 5 based on setting to zero specific inputs. For this reason, we
need to exploit further properties of DAGs to derive identifiability
conditions. The following lemma is well-known, and we provide a proof for the
sake of completeness.

######  Lemma 3.

In a DAG, any node $i$ which is not a source has at least an in-neighbor $j$
with only one path to $i$.

###### Proof.

If all the nodes except the sources have only one in-neighbor, the result
trivially holds. When there is a node with more than one in-neighbor, we prove
it by contradiction. Let us assume there is a DAG with a node $i$ with
$\left|\mathcal{N}_{i}\right|\geq 2$ in-neighbors. Let us suppose that all the
in-neighbors of $i$ have more than one path to $i$ and let us consider the
subgraph induced444An induced subgraph $G_{S}$ of a digraph $G$ is a subgraph
formed by a subset $S$ of the vertices of $G$ and all the edges of $G$ that
have both endpoints in $S$. by the set of in-neighbors of $i$ and the nodes
that correspond to any path between two in-neighbors of $i$. This subgraph
does not have a sink, which contradicts the fact that any subgraph of a DAG is
also a DAG. Therefore, there must be at least one neighbor $j$ with only one
path to $i$, which would correspond to the sink of the induced subgraph. ∎

The following lemma provides a relationship between the identifiability
problem based on the measurement of a node in a graph $G$ and the
identifiability problem based on the measurement of the same node in the
induced subgraph $G_{V\setminus\\{j\\}}$. For our convenience, we introduce
the notion of identifiability of a function $F_{\ell}$ that will be used in
the lemma.

######  Definition 6 (Identifiability of $F_{\ell}$).

Given a set of functions $\\{f\\}=\\{f_{i,j}\in\mathcal{F}\;|\;(i,j)\in E\\}$
that generates $F(\mathcal{N}^{m})$ and another set of functions
$\\{\tilde{f}\\}=\\{\tilde{f}_{i,j}\in\mathcal{F}\;|\;(i,j)\in E\\}$ that
generates $\tilde{F}(\mathcal{N}^{m})$. The function $F_{\ell}$ is
identifiable if $F(\mathcal{N}^{m})=\tilde{F}(\mathcal{N}^{m})$, implies that
$F_{\ell}=\tilde{F}_{\ell}$, which is equivalent to the mathematical
constraint associated with the measurement of the node $\ell$.

######  Lemma 4 (Removal of a node).

Given a DAG $G$ and a node $j$ with only one path to its out-neighbor $i$. Let
us assume that $j$ has been measured and the edge $f_{i,j}$ is identifiable.
The edges $f_{i,\ell}$ and functions $F_{\ell}$ for $\ell\in\mathcal{N}_{i}$
are identifiable in $G$ if they are identifiable in the induced subgraph
$G_{V\setminus\\{j\\}}$ with the measurement of $i$.

###### Proof.

In the DAG $G$, the measurement of the node $i$ provides the output:

$\displaystyle y_{i}^{k}$ $\displaystyle=u_{i}^{k-1}+F_{i}$
$\displaystyle=u_{i}^{k-1}+\sum_{\ell\in\mathcal{N}_{i}}f_{i,\ell}(u_{\ell}^{k-2}+F_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+F_{\ell}^{(m_{\ell})}),$
(12)

where the functions $F_{\ell}$ for $\ell\in\mathcal{N}_{i}\setminus\\{j\\}$ do
not depend on any information coming through $j$ since there is no path from
$j$ to other in-neighbors of $i$. Let us assume that there exists a set
$\\{\tilde{f}\\}\neq\\{f\\}$ such that $F_{i}=\tilde{F}_{i}$, which implies:

$\sum_{\ell\in\mathcal{N}_{i}}f_{i,\ell}(u_{\ell}^{k-2}+F_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+F_{\ell}^{(m_{\ell})})=\\\
\sum_{\ell\in\mathcal{N}_{i}}\tilde{f}_{i,\ell}(u_{\ell}^{k-2}+\tilde{F}_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+\tilde{F}_{\ell}^{(m_{\ell})}).$

Since the measurement of $j$ implies the knowledge of $F_{j}$ (i.e.,
$F_{j}=\tilde{F}_{j}$), and the edge $f_{i,j}$ is identifiable (i.e.,
$f_{i,j}=\tilde{f}_{i,j}$), we get:

$\sum_{\ell\in\mathcal{N}_{i}\setminus\\{j\\}}f_{i,\ell}(u_{\ell}^{k-2}+F_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+F_{\ell}^{(m_{\ell})})=\\\
\sum_{\ell\in\mathcal{N}_{i}\setminus\\{j\\}}\tilde{f}_{i,\ell}(u_{\ell}^{k-2}+\tilde{F}_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+\tilde{F}_{\ell}^{(m_{\ell})}).$
(13)

Now, let us consider the induced subgraph $G_{V\setminus\\{j\\}}$. With the
removal of the node $j$, the measurement of the node $i$ provides the output:

$y_{i}^{k}=u_{i}^{k-1}+\sum_{\ell\in\mathcal{N}_{i}\setminus\\{j\\}}f_{i,\ell}(u_{\ell}^{k-2}+\hat{F}_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+\hat{F}_{\ell}^{(m_{\ell})}).$
(14)

Since $j$ does not affect the functions $F_{\ell}$ for
$\ell\in\mathcal{N}_{i}\setminus\\{j\\}$, we have that
$\hat{F}_{\ell}=F_{\ell}$, so that (14) implies (13). Therefore, if the edges
$f_{i,\ell}$ and the functions $F_{\ell}$ for
$\ell\in\mathcal{N}_{i}\setminus\\{j\\}$ are identifiable in
$G_{V\setminus\\{j\\}}$, they are also identifiable in $G$. ∎

Before introducing the main result of this section, we will need the following
technical lemma where we remind that $\tau$ is the shift operator of
coordinates defined in Section II-A.

######  Lemma 5 (Sum of multivariate functions).

Given three nonzero analytic functions $f:\mathbb{R}^{p}\to\mathbb{R}$ and
$g,\tilde{g}:\mathbb{R}^{q}\to\mathbb{R}$. Let us assume that at least one of
the partial derivatives of $f$ is not constant and they satisfy:

$f(\mathbf{0})=g(\mathbf{0})=\tilde{g}(\mathbf{0})=0;$
$f(x_{1}\\!+\\!g(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,x_{p}\\!+\\!g(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}))=\\\
f(x_{1}\\!+\\!\tilde{g}(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,x_{p}\\!+\\!\tilde{g}(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}))+h,$
(15)

where $h$ is an arbitrary function that does not depend on
$x_{1},\ldots,x_{p}$. Then $g=\tilde{g}$.

###### Proof.

The proof is differed to Appendix -B ∎

######  Theorem 1 (DAGs).

A DAG is identifiable in the class $\mathcal{F}_{Z,NL}$, if and only if all
the sinks are measured.

###### Proof.

By Proposition 1 the measurement of all the sinks is necessary. Let us
consider an arbitrary DAG. The measurement of a sink $i$ provides the output:

$\displaystyle y_{i}^{k}$ $\displaystyle=u_{i}^{k-1}+F_{i}$
$\displaystyle=u_{i}^{k-1}\\!+\\!\sum_{j\in\mathcal{N}_{i}}\\!f_{i,j}(u_{j}^{k-2}\\!+\\!F_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}\\!+\\!F_{j}^{(m_{j})}).$

Let us assume that there exists a set $\\{\tilde{f}\\}\neq\\{f\\}$ such that
$F_{i}=\tilde{F}_{i}$, which implies:

$\sum_{j\in\mathcal{N}_{i}}f_{i,j}(u_{j}^{k-2}+F_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}+F_{j}^{(m_{j})})=\\\
\sum_{j\in\mathcal{N}_{i}}\tilde{f}_{i,j}(u_{j}^{k-2}+\tilde{F}_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}+\tilde{F}_{j}^{(m_{j})}).$
(16)

By Lemma 3, there is at least one in-neighbor $\ell$ with only one path to
$i$. Then, we can use Lemma 1 to guarantee $f_{i,\ell}=\tilde{f}_{i,\ell}$,
and (16) can be expressed as:

$f_{i,\ell}(u_{\ell}^{k-2}+F_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+F_{\ell}^{(m_{\ell})})=\\\
f_{i,\ell}(u_{\ell}^{k-2}+\tilde{F}_{\ell}^{(1)},\ldots,u_{\ell}^{k-m_{\ell}-1}+\tilde{F}_{\ell}^{(m_{\ell})})+\phi,$
(17)

where $\phi$ does not depend on any of the inputs $u_{\ell}$ since the only
path from $\ell$ to $i$ is the edge $(i,\ell)$. By using Lemma 5 in (17) we
obtain $F_{\ell}^{(1)}=\tilde{F}_{\ell}^{(1)}$, which corresponds to the
mathematical constraint associated with the measurement of the node $\ell$.
Then, the equality (16) becomes:

$\sum_{j\in\mathcal{N}_{i}\setminus\left\\{\ell\right\\}}f_{i,j}(u_{j}^{k-2}+F_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}+F_{j}^{(m_{j})})=\\\
\sum_{j\in\mathcal{N}_{i}\setminus\left\\{\ell\right\\}}\tilde{f}_{i,j}(u_{j}^{k-2}+\tilde{F}_{j}^{(1)},\ldots,u_{j}^{k-m_{j}-1}+\tilde{F}_{j}^{(m_{j})}),$
(18)

and according to Lemma 4, the edges $f_{i,j}$ and functions $F_{j}$ for
$j\in\mathcal{N}_{i}\setminus\\{\ell\\}$ are identifiable if they are
identifiable in the induced subgraph $G_{V\setminus\\{\ell\\}}$. By Lemma 3,
in the subgraph $G_{V\setminus\\{\ell\\}}$ there must be now another node with
only one path to the node $i$ and we can follow a similar approach. Then, we
can show that

$f_{i,j}=\tilde{f}_{i,j}\quad\text{ for all }j\in\mathcal{N}_{i},$

and similarly for the functions

$F_{j}^{(1)}=\tilde{F}_{j}^{(1)}\quad\text{ for all }j\in\mathcal{N}_{i}.$

The last condition corresponds to the mathematical constraint obtained with
the measurement of all the in-neighbors of $i$ (i.e., $F_{j}\in
F(\mathcal{N}^{m})$ for all $j\in\mathcal{N}_{i}$) and each in-neighbor can be
treated in a similar way to the node $i$, independently of other in-neighbors.
By following a similar approach, we can guarantee that
$\\{f\\}=\\{\tilde{f}\\}$ for every path that ends in the sink $i$, and since
in a DAG all the paths end in a sink [32], by measuring the other sinks we can
identify all the network. ∎

Theorem 1 is also valid if the nonlinear functions $f_{i,j}$ depend on outputs
with zero delays (i.e., $y_{j}^{k-0}$), and this will be used in the proof of
Theorem 2.

##  IV General digraphs

Now, we analyze general digraphs where cycles are allowed. In this case, the
delays $T_{j}$ in (2) for $j\in\mathcal{N}_{i}^{p}$ might not be finite, which
would imply an infinite number of variables due to the past values of the
inputs.

12$f_{2,1}$$f_{1,2}$ Figure 4: Cycle graph with 2 nodes, where the function
associated with the measurement of node 2 depends on an infinite number of
past inputs due to the cycle.

######  Example 3 (Infinite inputs).

Let us consider the cycle graph in Fig. 4 with nonlinear functions of the form
$f_{1,2}(y_{2}^{k-1})$, and $f_{2,1}(y_{1}^{k-1})$. The measurement of the
node 2 provides an output of the type:

$\displaystyle y_{2}^{k}$
$\displaystyle=u_{2}^{k-1}+f_{2,1}(u_{1}^{k-2}+f_{1,2}(y_{2}^{k-2}))$ (19)
$\displaystyle=u_{2}^{k-1}+f_{2,1}(u_{1}^{k-2}+f_{1,2}(u_{2}^{k-3}+f_{2,1}(y_{1}^{k-3}))),$

where we can observe that due to the cycles, the inputs will be repeated
indefinitely with different delays, such that the function $F_{2}$ associated
with the measurement is a function of an infinite number of variables.

Notice that the output (19) corresponds to a NARX model [25]:

$y_{2}^{k}=F_{\mathrm{NARX}}(u_{1}^{k-2},u_{2}^{k-1},y_{2}^{k-2}),$

where past outputs are considered in the formulation. Nevertheless, in this
work, we restrict our analysis to Volterra type models that depend only on
excitation signals (i.e., inputs) of the system.

Given that a general digraph can have cycles that depend on an infinite number
of past values of the inputs, the design of experiments to obtain the ideal
information associated with $F_{i}$ becomes more complex due to the infinite
amount of information (past inputs) required. To avoid this case and obtain
identifiability conditions that could match realistic experimental settings,
we make the following assumption.

######  Assumption 3 (Network initially at rest).

The network is initially at rest at time $k=0$, which implies $y_{i}^{k}=0$
for all $k\leq 0$ and all $i\in V$.

Assumption 3 covers the case of many networks that should be at rest at some
time instant if external signals are no longer applied. Also, it is reasonable
to assume that any experimental setting will consider the system at rest to
begin with the application of the excitation signals, such that all the
information obtained through the measured nodes is exclusively generated by
the excitation signals, neglecting the influence of uncontrolled inputs.

Under Assumption 3, when there are cycles in the network, the number of inputs
that appear in the function associated with the measurement of a node is
finite because the excitation signals can be nonzero only for $k>0$. This
implies a truncation of the function $F_{i}$ in (2) such that the output of a
node $i$ is given by:

$y_{i}^{k}=u_{i}^{k-1}+F_{i}^{k}(u_{1}^{k-2},\ldots,u_{1}^{0},\ldots,u_{n_{i}}^{k-2},\ldots,u_{n_{i}}^{0}),\\\
1,\dots,n_{i}\in\mathcal{N}_{i}^{p},$ (20)

where $F_{i}^{k}$ depends on inputs only until the time $k=0$ (i.e.,
$u_{i}^{0}$). For instance, let us consider again the cycle graph in Fig. 4
with the functions of the Example 3 and the measurement of the node 2 at the
time instant $k=4$. Under Assumption 3, the output is given by:

$\displaystyle y_{2}^{k}$ $\displaystyle=u_{2}^{k-1}+F_{2}^{k}$
$\displaystyle=u_{2}^{k-1}+f_{2,1}(u_{1}^{k-2}+f_{1,2}(u_{2}^{k-3}+f_{2,1}(u_{1}^{k-4}+f_{1,2}(y_{2}^{k-4}))))$
$\displaystyle=u_{2}^{k-1}+f_{2,1}(u_{1}^{k-2}+f_{1,2}(u_{2}^{k-3}+f_{2,1}(u_{1}^{k-4}))),$

which depends on a finite number of inputs since $y_{2}^{k-4}=0$.

Unlike the case of DAGs, the functions $F_{i}^{k}$ in (20) are parameterized
by $k$. In this case we assume that for each $k$, when we measure a node $i$,
we know perfectly the corresponding function $F_{i}^{k}$. Since we have a
family of functions parameterized by $k$, the identifiability of edges must be
guaranteed for each $F_{i}^{k}$. We extend the Definitions 1 and 2 for the
family of functions.

######  Definition 7 (Set of measured functions at $k$).

Given a set of measured nodes $\mathcal{N}^{m}$, the set of measured functions
$F^{k}(\mathcal{N}^{m})$ associated with $\mathcal{N}^{m}$ at a time instant
$k$ is given by:

$F^{k}(\mathcal{N}^{m}):=\\{F_{i}^{k}\;|\;i\in\mathcal{N}^{m}\\}.$

$F^{k}$ represents how the outputs of measured nodes $y^{k}$ depend on the
excitation signals from 0 to $k$.

######  Definition 8 (Identifiability at $k$).

Given a set of functions $\\{f\\}=\\{f_{i,j}\in\mathcal{F}\;|\;(i,j)\in E\\}$
that generates $F^{k}(\mathcal{N}^{m})$ and another set of functions
$\\{\tilde{f}\\}=\\{\tilde{f}_{i,j}\in\mathcal{F}\;|\;(i,j)\in E\\}$ that
generates $\tilde{F}^{k}(\mathcal{N}^{m})$. An edge $f_{i,j}$ is identifiable
in a class $\mathcal{F}$ at $k$ if
$F^{k}(\mathcal{N}^{m})=\tilde{F}^{k}(\mathcal{N}^{m})$, implies that
$f_{i,j}=\tilde{f}_{i,j}$. A network $G$ is identifiable in a class
$\mathcal{F}$ at $k$ if
$F^{k}(\mathcal{N}^{m})=\tilde{F}^{k}(\mathcal{N}^{m}),$ implies that
$\\{f\\}=\\{\tilde{f}\\}$.

Unlike DAGs where nonzero excitation signals $u_{i}^{k}$ at time instants
$k<0$ are allowed, for general digraphs, the time instant considered for the
measurement of a node should be long enough to let all the excitation signals
to have an effect on the output of the measured node. If we consider again the
cycle graph in Fig. 4, but with a measurement of the node 2 performed at the
time instant $k=2$, the output is given by:

$\displaystyle y_{2}^{k}$ $\displaystyle=u_{2}^{k-1}+F_{2}^{k}$
$\displaystyle=u_{2}^{k-1}+f_{2,1}(u_{1}^{k-2}+f_{1,2}(y_{2}^{k-2}))$
$\displaystyle=u_{2}^{k-1}+f_{2,1}(u_{1}^{k-2}),$ (21)

since $y_{2}^{k-2}=0$. Even if the measurement of the node 2 could give us
information also about the function $f_{1,2}$, this is not reflected on the
function $F_{2}^{k}$ due to the short period of time chosen for the
measurement. In this case, any function $f_{1,2}\in\mathcal{F}$ could generate
the output (21), which implies that $f_{1,2}$ is not identifiable at the time
instant $k=2$. For this reason, we introduce the notion of general
identifiability.

######  Definition 9 (General identifiability).

A network $G$ is identifiable in a class $\mathcal{F}$ if there exists a
$k_{\min}$ such that it is identifiable for $k>k_{\min}$.

In any digraph, we will be able to consider:

$\bar{k}_{\min}=m_{\max}+\text{diam}(G),$ (22)

where $m_{\max}$ is the largest delay of the nonlinear functions $f_{i,j}$,
and $\text{diam}(G)$ is the diameter of the digraph $G$. By choosing
$k_{\min}=\bar{k}_{\min}$ we will guarantee the appearance of all the possible
nonlinear functions $f_{i,j}$ with all their arguments in
$F^{k_{\min}}(\mathcal{N}^{m})$ (see the proof of Lemma 6). Notice that the
consideration of time instants $k>\bar{k}_{\min}$ for the analysis of
identifiability is not restrictive since it is logical that in any
experimental setting, we need to wait until the outputs of measured nodes
reflect the influence of all the possible excitation signals. Also, since the
definition of the time $k=0$ depends on the context of the analysis, it can be
associated with the beginning of the application of the excitation signals in
the nodes.

Definition 1 for DAGs is encompassed by Definition 7 since the information
obtained from the measurement of a node (i.e., $F(\mathcal{N}^{m})$) is
independent of the time instant $k$. Similarly, Definition 2 is encompassed by
Definitions 8 and 9, since for DAGs, identifiability at an arbitrary time
instant $k$ guarantees identifiability for all time instants $k$ because the
functions $F_{i}$ are not parameterized by $k$.

During the analysis of identifiability, one of the most basic steps that
guarantees the identification of all the network is the identifiability of the
in-neighbors of measured nodes. This has been performed by isolating parts of
the network with appropriate zero excitation inputs (see Lemma 1). However,
the extension of this methodology to general digraphs is not always possible
since several inputs can be repeated due to the cycles. For example, let us
consider again the cycle graph in Fig. 4 with the functions
$f_{3,2}(y_{2}^{k-1},y_{2}^{k-4})$, $f_{2,1}(y_{1}^{k-1})$ and
$f_{1,3}(y_{3}^{k-1})$ where the measurement of the node 3 provides the
output:

$\displaystyle y_{3}^{k}$
$\displaystyle=u_{3}^{k-1}+f_{3,2}(y_{2}^{k-1},y_{2}^{k-4})$
$\displaystyle=u_{3}^{k-1}+f_{3,2}(u_{2}^{k-2}+f_{2,1}(u_{1}^{k-3}+f_{1,3}(u_{3}^{k-4}+$
$\displaystyle\quad\;f_{3,2}(u_{2}^{k-5}))),u_{2}^{k-5}).$

Notice that we cannot identify $f_{3,2}$ by setting to zero the other inputs
because the input $u_{2}^{k-5}$ is repeated due to the cycle. Nevertheless,
the results can still be extended by considering additively separable
functions.

######  Assumption 4 (Additively separable functions).

The nonlinear functions $f_{i,j}$ are additively separable:

$f_{i,j}(y_{j}^{k-1},\ldots,y_{j}^{k-m_{j}})=\sum_{\ell=1}^{m_{j}}f_{i,j}^{\\{\ell\\}}(y_{j}^{k-\ell}),$
(23)

where if each function $f_{i,j}^{\\{\ell\\}}$ is nonzero, then it belongs to
$\mathcal{F}_{Z,NL}$.

The determination of an initial time and a final time for the identification
process implies in some way that nodes associated with inputs $u^{0}$ stop
being influenced through incoming edges and nodes associated with inputs
$u^{k}$ stop influence other nodes through outgoing edges. This clearly
entails an analogy with the notions of sources and sinks of DAGs, and this
allows us to construct a special type of DAG associated with any digraph that
will be used in the proofs of the results. This DAG will be generated based on
nodes with a nonempty set of out-neighbors (i.e.,
$\mathcal{N}_{i}^{\text{out}}\neq\emptyset$), where only for its construction,
we will assume that the first node denoted by $i_{0}$ satisfies
$\mathcal{N}_{i_{0}}^{\text{out}}\neq\emptyset$.

Data: Graph $G=(V,E)$, measured node $i$, measurement time $k$

Result: Adapted DAG $H_{i}^{k}(G)$

1

2Create a copy of the node $i$ denoted by $i_{0}$ with excitation signal
$u_{i}^{k}$

3for  _$t=1,\ldots,k-1$_ do

4

5 Create copies of the nodes $v\in V$ denoted by $v_{t}$ with excitation
signal $u_{v}^{k-t}$

6 for  _each node $v_{t}$ and each node $w_{m}$ with
$\mathcal{N}_{w_{m}}^{out}\neq\emptyset$ and $m=0,\ldots,t-1$_ do

7

8 if  _$f_{w,v}^{\\{t-m\\}}(y_{v}^{k-t+m})\neq 0$ _ then

9 Connect $w_{m}$ and $v_{t}$ with $f_{w,v}^{\\{t-m\\}}(y_{v}^{k})$

10 end if

11

12 end for

13

14 end for

15

Algorithm 1 Adapted DAG $H_{i}^{k}(G)$

######  Definition 10 (Adapted DAG).

An adapted DAG at a node $i$ at the time instant $k$ of a digraph $G$ denoted
by $H_{i}^{k}(G)$ is a DAG generated through Algorithm 1 where the nonlinear
functions of the edges have delay 0.

123456$a)$ Digraph
$G$$f_{2,1}$$f_{3,2}$$f_{4,3}$$f_{1,4}$$f_{3,1}$$f_{2,5}$$f_{6,5}$$f_{3,6}$$C_{1}$$\\{1,2,3,4\\}$
$C_{2}$$\\{5\\}$ $C_{3}$$\\{6\\}$ $b)$ Condensation digraph
$C(G)$$3_{0}$$u_{3}^{k}$$1_{1}$$u_{1}^{k-1}$$6_{1}$$u_{6}^{k-1}$$2_{1}$$u_{2}^{k-1}$$5_{2}$$u_{5}^{k-2}$$1_{2}$$u_{1}^{k-2}$$4_{2}$$u_{4}^{k-2}$$3_{3}$$u_{3}^{k-3}$$4_{3}$$u_{4}^{k-3}$$k=0$$k=1$$k=2$$k=3$$f_{3,1}$$f_{3,2}$$f_{3,6}$$f_{2,5}$$f_{6,5}$$f_{2,1}$$f_{1,4}$$f_{4,3}$$f_{1,4}$$c)$
Adapted DAG $H_{3}^{4}(G)$ Figure 5: General digraph $G$ with with its
corresponding condensation digraph $C(G)$ and adapted DAG $H_{3}^{4}(G)$
constructed at the node 3 and the time instant $k=4$. The identification of
$G$ at $k=4$ is equivalent to the identification of $H_{3}^{4}(G)$ where
several copies of the nodes of $G$ are created for its construction with
inputs determined by the corresponding delays. The adapted DAG is also a
multipartite digraph with sets $\\{3_{0}\\}$, $\\{1_{1},2_{1},6_{1}\\}$,
$\\{4_{2},1_{2},5_{2}\\}$ and $\\{3_{3},4_{3}\\}$, which are constructed by
grouping nodes with the same delays on the inputs.

Intuitively, in the adapted DAG, there is a copy of each node for each time
instant $t=1,\ldots,k-1$, and two nodes $v_{t}$ and $w_{m}$ are connected if
the node $v_{t}$ at time $t$ influences directly the node $w_{m}$ at time $m$.
Notice that the adapted DAG $H_{i}^{k}(G)$ is composed by several copies of
all the nodes in $G$. However, some of the copies are disconnected (no
incoming or outgoing edges) and their effect will be neglected in the analysis
of identifiability. In addition, the adapted DAG can be seen as a multipartite
digraph555A $k$-partite digraph is a digraph whose vertices can be partitioned
into $k$ different sets such that for each set, there is no an edge connecting
two nodes. where each set is composed by the nodes with excitation signals
having the same delays. Since the edges can only go from a node to another
node with a smaller delay, there are no cycles and the graph is clearly a DAG.
In Fig. 5 we present the adapted DAG $H_{i}^{k}(G)$ of a general digraph $G$
with several cycles and nonlinear functions of the form $f_{i,j}(y_{j}^{k-1})$
where we can see the several copies of the nodes grouped according to the
delays of the excitation signals (each group corresponds to a different set of
a multipartite digraph). The disconnected copies of nodes have been removed
from $H_{i}^{k}(G)$, since they have no effect on the identifiability problem.
Notice that the adapted DAG $H_{i}^{k}(G)$ is unique and different for each
measured node $i$.

The utility of this mathematical construction is highlighted by the following
lemma.

######  Lemma 6.

Given a digraph $G$ and a measured node $i$. Under Assumptions 3 and 4, for
any $k>\bar{k}_{\min}$, the edges on all the paths that arrive to the node $i$
in $G$ are identifiable if the adapted DAG $H_{i}^{k}(G)$ is identifiable with
the measurement of $i$.

###### Proof.

Under Assumption 3, the function $F_{i}^{k}$ associated with the measurement
of a node $i$ depends on a finite number of inputs. The measurement of the
node $i$ in $G$ provides an output of the form:

$\displaystyle y_{i}^{k}$ $\displaystyle=u_{i}^{k-1}+F_{i}^{k}$
$\displaystyle=u_{i}^{k-1}+\sum_{j\in\mathcal{N}_{i}}f_{i,j}(y_{j}^{k-1},\ldots,y_{j}^{k-m_{j}})$
$\displaystyle=u_{i}^{k-1}+\sum_{j\in\mathcal{N}_{i}}\sum_{\ell_{j}=1}^{\hat{m}_{j}}f_{i,j}^{\\{\ell_{j}\\}}(y_{1}^{k-\ell_{j}})$
$\displaystyle=u_{i}^{k-1}+\sum_{j\in\mathcal{N}_{i}}\sum_{\ell_{j}=1}^{\hat{m}_{j}}f_{i,j}^{\\{\ell_{j}\\}}\left(u_{j}^{k-\ell_{j}-1}+F_{j}^{(\ell_{j})}\right).$
(24)

Since $k>\bar{k}_{\min}$ we guarantee that $\hat{m}_{j}=m_{j}$ such that all
the possible nonlinear functions $f_{i,j}^{\\{\ell_{j}\\}}$ appear in (24).
Let us assume that there exists a set $\\{\tilde{f}\\}\neq\\{f\\}$ such that
$F_{i}^{k}=\tilde{F}_{i}^{k}$, which implies:

$\sum_{j\in\mathcal{N}_{i}}\sum_{\ell_{j}=1}^{m_{j}}f_{i,j}^{\\{\ell_{j}\\}}\left(u_{j}^{k-\ell_{j}-1}+F_{j}^{(\ell_{j})}\right)=\\\
\sum_{j\in\mathcal{N}_{i}}\sum_{\ell_{j}=1}^{m_{j}}\tilde{f}_{i,j}^{\\{\ell_{j}\\}}\left(u_{j}^{k-\ell_{j}-1}+\tilde{F}_{j}^{(\ell_{j})}\right).$
(25)

Now, let us consider the adapted DAG $H_{i}^{k}(G)$. The measurement of the
sink $i$ in $H_{i}^{k}(G)$ provides the output:

$y_{i}^{k}=u_{i}^{k-1}+\sum_{j\in\mathcal{N}_{i}}\sum_{\ell_{j}=1}^{m_{j}}f_{i,j}^{\\{\ell_{j}\\}}\left(u_{j}^{k-\ell_{j}-1}+\hat{F}_{j}^{(\ell_{j})}\right).$
(26)

Since the adapted DAG $H_{i}^{k}(G)$ guarantees that each node is connected by
copies of the same in-neighbors in $G$ where the delays of the excitation
signals are given by the delays of the nonlinear functions and the time
instants in which the nodes were created, we can guarantee that the outputs of
all the nodes in $G$ and $H_{i}^{k}(G)$ are the same with the corresponding
delays, which implies $\hat{F}_{j}^{(\ell_{j})}=F_{j}^{(\ell_{j})}$ and hence
$\hat{F}_{j}=F_{j}$. Then, (26) implies (25). Since $k>\bar{k}_{\min}$, we
have that for each $F_{j}$, all the possible nonlinear functions
$f_{j,p}^{\\{\ell_{p}\\}}$ associated with an in-neighbor $p$ of $j$ appear in
$F_{j}$. Hence, if the nonlinear functions of the edges are identifiable in
$H_{i}^{k}(G)$, they are also identifiable in $G$. ∎

The following theorem provides identifiability conditions for any digraph $G$
based on the measurement of nodes associated with the condensation digraph
$C(G)$ 666The _condensation digraph_ $C(G)$ of a digraph $G$ is a digraph
where each strongly connected component is replaced by a node and all the
edges from one strongly connected component to another are replaced by a
single edge..

######  Theorem 2 (General digraph).

Under Assumptions 3 and 4, for any $k>\bar{k}_{\min}$, a digraph is
identifiable in the class $\mathcal{F}_{Z,NL}$, if and only if one node is
measured in every sink of the condensation digraph.

###### Proof.

Let us consider an arbitrary digraph $G$. By measuring one node of each sink
of the condensation digraph $C(G)$, we can guarantee that there is a path from
any node of the network to one of the measured nodes. Let us assume that we
measure one node $i$ of a sink of $C(G)$ at an arbitrary time instant
$k>\bar{k}_{\min}$. According to Lemma 6, the paths that arrive to the node
$i$ are identifiable if the adapted DAG $H_{i}^{k}(G)$ is identifiable at
$k>\bar{k}_{\min}$. By Theorem 1, the adapted DAG $H_{i}^{k}(G)$ is
identifiable with the measurement of the sink corresponding to the node $i$,
which implies that the edges of all the paths in $G$ that end in the node $i$
are identifiable, and since all the paths end in a sink of $C(G)$, we identify
all the network at the time instant $k$. Since $k$ was arbitrary, the
procedure can be applied for other $k>\bar{k}_{\min}$, such that the network
is identifiable. ∎

The static model is a particular case of additively separable functions, where
the function $f_{ij}$ in (23) only depends on $y_{j}^{k-1}$:

$y_{i}^{k}=\sum_{j\in\mathcal{N}_{i}}f_{i,j}(y_{j}^{k-1})+u_{i}^{k-1}.$ (27)

Therefore, Theorem 2 allows us to complete the results of identifiability of
networks in the static case analyzed in [28], where the case of general
digraphs was missing.

######  Remark 1 (Self-loops).

In the case of nonlinear state space representations where dynamics at the
level of nodes can be present as self-loops, the output of each node $i$ is
given by:

$y_{i}^{k}=\sum_{j\in\mathcal{N}_{i}^{i}}f_{i,j}(y_{j}^{k-1},y_{j}^{k-2},\ldots,y_{j}^{k-m_{j}})+u_{i}^{k-1},$
(28)

where $\mathcal{N}_{i}^{i}$ is the set of in-neighbors of the node $i$
including $i$. Notice that in the associated adapted DAG, the set of in-
neighbors of a node $i$ is just extended to $\mathcal{N}_{i}^{i}$ including
the same node $i$ connected by $f_{i,i}$. Therefore, Theorem 2 is also valid
in this case.

##  V Conclusions and future work

We have shown fundamental differences in the identifiability conditions for
nonlinear networks with respect to the linear case. Specifically, we have
shown for pure nonlinear functions that identifiability was determined by
measuring the sinks in the case of DAGs, or nodes in the sinks of the
condensation digraph for general digraphs assuming that the nonlinear
functions are additively separable and the network is at rest in the last
case.

Our approach of the nonlinear network identifiability is novel, and there are
consequently many open problems. Clearly, the family of functions considered
for the identifiability problem plays a crucial role. The first extension
would be the analysis of general digraphs when the nonlinear functions are not
necessarily additively separable. Also, in a more general framework, it would
be important to analyze more general classes of functions that are not
analytic or differentiable. Finally, the derivation of identifiability
conditions for a non-additive dynamical model is definitely an interesting
area of research.

## References

  * [1] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, “Complex networks: Structure and dynamics,” _Physics reports_ , vol. 424, no. 4-5, pp. 175–308, 2006.
  * [2] F. Bullo, _Lectures on Network Systems_ , 1.6 ed. Kindle Direct Publishing, 2022.
  * [3] X. Wang and H. Su, “Pinning control of complex networked systems: A decade after and beyond,” _Annual Reviews in Control_ , vol. 38, no. 1, pp. 103–111, 2014.
  * [4] J. Gonçalves and S. Warnick, “Necessary and sufficient conditions for dynamical structure reconstruction of LTI networks,” _IEEE Transactions on Automatic Control_ , vol. 53, no. 7, pp. 1670–1674, 2008.
  * [5] A. Mauroy and J. M. Hendrickx, “Spectral identification of networks using sparse measurements,” _SIAM Journal on Applied Dynamical Systems_ , vol. 16, no. 1, pp. 479–513, 2017.
  * [6] S. Jahandari and D. Materassi, “Optimal selection of observations for identification of multiple modules in dynamic networks,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 9, pp. 4703–4716, 2022.
  * [7] M. Verhaegen, C. Yu, and B. Sinquin, _Data-Driven Identification of Networks of Dynamic Systems_. Cambridge University Press, 2022.
  * [8] K. R. Ramaswamy, P. M. J. Van den Hof, and A. G. Dankers, “Generalized sensing and actuation schemes for local module identification in dynamic networks,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 5519–5524.
  * [9] X. Bombois, K. Colin, P. M. J. Van den Hof, and H. Hjalmarsson, “On the informativity of direct identification experiments in dynamical networks,” _Automatica_ , vol. 148, p. 110742, 2023.
  * [10] E. M. M. Kivits and P. M. J. Van den Hof, “Identifiability of diffusively coupled linear networks with partial instrumentation,” in _22nd World Congress of the International Federation of Automatic Control (IFAC 2023 World Congress)_ , 2023.
  * [11] J. M. Hendrickx, M. Gevers, and A. S. Bazanella, “Identifiability of dynamical networks with partial node measurements,” _IEEE Transactions on Automatic Control_ , vol. 64, no. 6, pp. 2240–2253, 2019.
  * [12] H. J. van Waarde, P. Tesi, and M. K. Camlibel, “Necessary and sufficient topological conditions for identifiability of dynamical networks,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 11, pp. 4525–4537, 2020.
  * [13] A. Legat and J. M. Hendrickx, “Local network identifiability with partial excitation and measurement,” in _2020 59th IEEE Conference on Decision and Control (CDC)_ , 2020, pp. 4342–4347.
  * [14] ——, “Path-based conditions for local network identifiability,” in _2021 60th IEEE Conference on Decision and Control (CDC)_ , 2021, pp. 3024–3029.
  * [15] A. S. Bazanella, M. Gevers, and J. M. Hendrickx, “Network identification with partial excitation and measurement,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 5500–5506.
  * [16] X. Cheng, S. Shi, I. Lestas, and P. M. J. Van den Hof, “A necessary condition for network identifiability with partial excitation and measurement,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 11, pp. 6820–6827, 2023.
  * [17] A. Legat and J. M. Hendrickx, “Combinatorial characterization for global identifiability of separable networks with partial excitation and measurement,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_ , 2023.
  * [18] F. Dörfler and F. Bullo, “Synchronization in complex networks of phase oscillators: A survey,” _Automatica_ , vol. 50, no. 6, pp. 1539–1564, 2014\.
  * [19] W. Pan, Y. Yuan, J. Gonçalves, and G.-B. Stan, “Reconstruction of arbitrary biochemical reaction networks: A compressive sensing approach,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_. IEEE, 2012, pp. 2334–2339.
  * [20] A. Aalto, L. Viitasaari, P. Ilmonen, L. Mombaerts, and J. Gonçalves, “Gene regulatory network inference from sparsely sampled noisy data,” _Nature communications_ , vol. 11, no. 1, p. 3493, 2020.
  * [21] J. Burés and I. Larrosa, “Organic reaction mechanism classification using machine learning,” _Nature_ , vol. 613, no. 7945, pp. 689–695, 2023.
  * [22] A. Bizyaeva, A. Franci, and N. E. Leonard, “Nonlinear opinion dynamics with tunable sensitivity,” _IEEE Transactions on Automatic Control_ , vol. 68, no. 3, pp. 1415–1430, 2023.
  * [23] J. Schoukens and L. Ljung, “Nonlinear system identification: A user-oriented road map,” _IEEE Control Systems Magazine_ , vol. 39, no. 6, pp. 28–99, 2019\.
  * [24] A. Janczak, _Identification of Nonlinear Systems Using Neural Networks and Polynomial Models_. Springer, 2004.
  * [25] O. Nelles, _Nonlinear System Identification_. Springer, 2020.
  * [26] J. Paduart, L. Lauwers, J. Swevers, K. Smolders, J. Schoukens, and R. Pintelon, “Identification of nonlinear systems using polynomial nonlinear state space models,” _Automatica_ , vol. 46, no. 4, pp. 647–656, 2010.
  * [27] C. C. Aggarwal, “Neural Networks and Deep Learning,” _Springer_ , 2018.
  * [28] R. Vizuete and J. M. Hendrickx, “Nonlinear network identifiability: The static case,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_ , 2023, pp. 443–448.
  * [29] L. Ljung, _System Identification: Theory for the User_. Prentice Hall PTR, 1999.
  * [30] X. Cheng, S. Shi, I. Lestas, and P. M. Van den Hof, “Identifiability in dynamic acyclic networks with partial excitations and measurements,” _arXiv preprint arXiv:2201.07548_ , 2022.
  * [31] E. Mapurunga, M. Gevers, and A. S. Bazanella, “Excitation and measurement patterns for the identifiability of directed acyclic graphs,” in _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 2022, pp. 1616–1621.
  * [32] J. Bang-Jensen and G. Z. Gutin, _Digraphs: Theory, Algorithms and Applications_. Springer Science & Business Media, 2008.

###  -A Proof of Lemma 2

Let us consider the change of variables:

$\hat{x}_{1}=x_{1}+g(\mathbf{y}_{1},\ldots,\mathbf{y}_{r});$ $\vdots$
$\hat{x}_{p}=x_{p}+g(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}).$

Then, (8) can be written as:

$f(\hat{x}_{1},\ldots,\hat{x}_{p})=f(\hat{x}_{1}+\psi(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,\\\
\hat{x}_{p}+\psi(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r})),$
(29)

where $\psi=\tilde{g}-g$. The equality (29) must hold for the particular case
$\hat{\mathbf{x}}=(\hat{x}_{1},\ldots,\hat{x}_{p})=\mathbf{0}$, so that we
get:

$f(\psi(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,\psi(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}))=f(\mathbf{0}).$
(30)

If $f$ is constant, then it corresponds to one of the possible results of the
Lemma. Let us assume that there exists at least some $z_{q}$ in
$f(z_{1},\ldots,z_{q},\ldots,z_{p})$ such that $\frac{\partial f}{\partial
z_{q}}\neq 0$. If $\psi$ is constant, we have $\psi\equiv 0$, which implies
$g=\tilde{g}$ and the result is already proved. Let us consider that
$y_{q}^{(s)}$ is the first variable in
$\psi(\tau^{q-1}\mathbf{y}_{1},\ldots,\tau^{q-1}\mathbf{y}_{r})$ such that
$\frac{\partial\psi}{\partial y_{q}^{(s)}}\neq 0$. Let us take the partial
derivative with respect to $y_{q}^{(s)}$, in both sides of (30). Since
$y_{q}^{(s)}$ only appears in
$\psi(\tau^{q-1}\mathbf{y}_{1},\ldots,\tau^{q-1}\mathbf{y}_{r})$ because the
first partial derivatives of $f$ are zero (i.e., $\frac{\partial f}{\partial
z_{w}}=0$ for $w=1,\ldots,q-1$), and the shift operator $\tau$ is applied in
the other arguments of $f$, we obtain

$\left(\frac{\partial f}{\partial z_{q}}\right)\left(\frac{\partial}{\partial
y_{q}^{(s)}}\psi(\tau^{q-1}\mathbf{y}_{1},\ldots,\tau^{q-1}\mathbf{y}_{r})\right)\equiv
0,$ (31)

where the partial derivative $\left(\frac{\partial f}{\partial z_{1}}\right)$
is evaluated at
$(\psi(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,\psi(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}))$.
In (31), we have the product of two analytic functions and one of them must be
zero everywhere to satisfy the equality. However, this is a contradiction. If
$\frac{\partial f}{\partial z_{q}}\neq 0$, there is no $z_{q}$ such that
$\frac{\partial f}{\partial z_{q}}\neq 0$ and therefore $f$ is constant. If
$\frac{\partial}{\partial
y_{q}^{(s)}}\psi(\tau^{q-1}\mathbf{y}_{1},\ldots,\tau^{q-1}\mathbf{y}_{r})=0$,
we have that $\psi$ is constant, which implies $g=\tilde{g}$.

###  -B Proof of Lemma 5

According to the hypothesis, the derivative of $f(z_{1},\cdots,z_{p})$ with
respect to at least one variable $z_{i}$ is not constant. Let us take the
derivative in both sides of (15) with respect to an arbitrary variable $z_{i}$
such that the derivative is not constant. Then, we have:

$\\!\\!\\!\\!\\!\\!\left(\frac{\partial f_{i}}{\partial
z_{i}}\right)\\!\\!(x_{1}\\!+\\!g(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,x_{p}\\!+\\!g(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r}))=\\\
\left(\frac{\partial f_{i}}{\partial
z_{i}}\right)\\!\\!(x_{1}\\!+\\!\tilde{g}(\mathbf{y}_{1},\ldots,\mathbf{y}_{r}),\ldots,x_{p}\\!+\\!\tilde{g}(\tau^{p-1}\mathbf{y}_{1},\ldots,\tau^{p-1}\mathbf{y}_{r})).$
(32)

Since the partial derivative of an analytic function is also an analytic
function, (32) is equivalent to (8) and we can apply Lemma 2 to guarantee that
either $g=\tilde{g}$ or $\left(\frac{\partial f_{i}}{\partial z_{i}}\right)$
is constant. But if $\left(\frac{\partial f_{i}}{\partial z_{i}}\right)$ is
constant, we have a contradiction and then we can conclude that $g=\tilde{g}$.

|  Renato Vizuete received the M.S. degree (très bien) in Systems, Control,
and Information Technologies from Université Grenoble Alpes, France (2019),
and the PhD degree in Automatic Control from Université Paris-Saclay, France
(2022). He is currently a FNRS postdoctoral researcher - CR at UCLouvain,
Belgium, in the ICTEAM Institute. His research interests include multi-agent
systems, distributed optimization, control theory and networked control
systems. He was the recipient of the Networks and Communication Systems TC
Outstanding Student Paper Prize of the IEEE Control Systems Society in 2022,
and the Second Thesis Prize in the category Impact Science of the Fondation
CentraleSupélec in 2023.
---|---
|  Julien M. Hendrickx is professor of mathematical engineering at UCLouvain,
in the Ecole Polytechnique de Louvain since 2010. He obtained an engineering
degree in applied mathematics (2004) and a PhD in mathematical engineering
(2008) from the same university. He has been a visiting researcher at the
University of Illinois at Urbana Champaign in 2003-2004, at the National ICT
Australia in 2005 and 2006, and at the Massachusetts Institute of Technology
in 2006 and 2008. He was a postdoctoral fellow at the Laboratory for
Information and Decision Systems of the Massachusetts Institute of Technology
2009 and 2010, holding postdoctoral fellowships of the F.R.S.-FNRS (Fund for
Scientific Research) and of Belgian American Education Foundation. He was also
resident scholar at the Center for Information and Systems Engineering (Boston
University) in 2018-2019, holding a WBI.World excellence fellowship. Doctor
Hendrickx is the recipient of the 2008 EECI award for the best PhD thesis in
Europe in the field of Embedded and Networked Control, and of the Alcatel-
Lucent-Bell 2009 award for a PhD thesis on original new concepts or
application in the domain of information or communication technologies.
---|---