# Combinatorial Characterization for Global Identifiability
of Separable Networks with Partial Excitation and Measurement

Antoine Legat and Julien M. Hendrickx A. Legat and J. M. Hendrickx are with
ICTEAM Institute, UCLouvain, Belgium. Work supported by the “RevealFlight” ARC
at UCLouvain, by the Incentive Grant for Scientific Research (MIS) “Learning
from Pairwise Data” and by the KORNET project from F.R.S.-FNRS
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This work focuses on the generic identifiability of dynamical networks with
partial excitation and measurement: a set of nodes are interconnected by
transfer functions according to a known topology, some nodes are excited, some
are measured, and only a part of the transfer functions are known. Our goal is
to determine whether the unknown transfer functions can be generically
recovered based on the input-output data collected from the excited and
measured nodes.

We introduce the notion of separable networks, for which global and so-called
local identifiability are equivalent. A novel approach yields a necessary and
sufficient combinatorial characterization for local identifiability for such
graphs, in terms of existence of paths and conditions on their parity.
Furthermore, this yields a necessary condition not only for separable
networks, but for networks of any topology.

##  I INTRODUCTION

This paper addresses the identifiability of dynamical networks in which node
signals are connected by causal linear time-invariant transfer functions, and
can be excited and/or measured. Such networks can be modeled as directed
graphs where each edge carries a transfer function, and known excitations and
measurements are applied at certain nodes.

###  I-A Problem Statement

We consider the identifiability of a network matrix $G(q)$, where the network
is made up of $n$ node signals stacked in the vector $w(t)=[w_{1}(t)\quad
w_{2}(t)\ \cdots\ w_{n}(t)]^{\top}$, known external excitation signals $r(t)$,
measured node signals $y(t)$ and unmeasured noise $v(t)$ related to each other
by:

$\displaystyle\begin{split}w(t)&=G(q)w(t)+Br(t)+v(t)\\\
y(t)&=Cw(t),\end{split}$ (1)

where matrices $B$ and $C$ are binary selections indicating respectively the
$n_{B}$ excited and $n_{C}$ measured nodes, forming sets $\mathcal{B}$ and
$\mathcal{C}$ respectively. Matrix $B$ is full column rank and each column
contains one $1$ and $n-1$ zeros. Matrix $C$ is full row rank and each row
contains one $1$ and $n-1$ zeros.

The nonzero entries of the transfer matrix $G(q)$ define the network topology:
$G_{ij}(q)$ is the transfer function from node $j$ to node $i$. It is
represented by an edge $(j,i)\in\mathcal{E}$ in the graph, where $\mathcal{E}$
is the set of all edges, each corresponding to a nonzero entry of $G(q)$. Some
of those transfer functions are known and collected in the matrix
$G^{\bullet}(q)$, and the others unknown, collected in matrix $G^{\circ}(q)$,
such that $G(q)=G^{\bullet}(q)+G^{\circ}(q)$. The known edges (i.e. the edges
corresponding to known transfer functions) are collected in set
$\mathcal{E}^{\bullet}$, the unknown ones in $\mathcal{E}^{\circ}$, and they
form a partition of the set of all edges
$\mathcal{E}=\\{\mathcal{E}^{\bullet},\mathcal{E}^{\circ}\\}$. We denote the
number of unknown transfer functions by
$m_{\circ}\triangleq|\mathcal{E}^{\circ}|$.

We assume that _the input-output relations between the excitations $r$ and
measurements $y$ have been identified_, and that the network topology is
known. From this knowledge, we aim at recovering the unknown transfer
functions $G^{\circ}(q)$.

###  I-B State of the Art

The model (1) has recently been the object of a significant research effort.
Network identifiability was first introduced in [1], in case the whole network
is to be recovered. Conditions for the identification of a single transfer
function are derived in [2, 3]. Studying the influence of rank-reduced or
correlated noise under certain assumptions yields less conservative
identifiability conditions [4, 5, 6, 7].

It turns out that under some assumptions, identifiability of the network, i.e.
the ability to recover a transfer function or the whole network from the
input-output relation, is a generic notion: Either _almost all_ transfer
matrices corresponding to a given network structure are identifiable, in which
case the structure is called _generically identifiable_ , or none of them are.
A number of works study generic identifiability when all nodes are excited or
all nodes are measured, i.e. when $B$ or $C=I$ [8, 9]. Considering the graph
of the network, path-based conditions on the allocation of measurements (resp.
excitations) in the case of full excitation (resp. measurement) are derived in
[10] (resp. [11]). Reformulating these conditions by means of disjoint trees
in the graph, the authors of [12, 13, 14] develop scalable algorithms to
allocate excitations/measurements in case of full measurement/excitation. In
case of full measurement, [15] derives path-based conditions for the generic
identifiability of a subset of transfer functions, with noise.

While the conditions in [10, 11] apply to generic identifiability i.e. for
almost all transfer functions, [16] extends these results to the stronger
requirement of identifiability _for all_ (nonzero) transfer matrices
corresponding to a given structure, and [17] provides conditions for the
outgoing edges of a node, and the whole network under the same conditions.

As mentioned, the common assumption in all these works is that is that either
all nodes are excited, or they are all measured. In [18], this assumption is
relaxed and generic identifiability with partial excitation and measurement is
addressed for particular network topologies. For acyclic networks, [19] gives
necessary conditions, introduces the transpose network and shows that
identifiability of the transpose network and its original network is
equivalent.

For an arbitrary topology, [20] provides for noise exploitation an elegant
reformulation as an equivalent network model, where noise is cast into
excitation signals. [21, 22, 23] provide necessary conditions for network
identifiability, but do not handle a priori known/fixed transfer functions,
which could lead to less conservative conditions.

In the general case of arbitrary topology, partial excitation and measurement,
we introduced in [24] the notion of local identifiability, i.e. only on a
neighborhood of $G(q)$. Local identifiability is a generic property, necessary
for generic identifiability and no counterexample to sufficiency is known to
the authors, i.e. no network which is locally identifiable but not globally
identifiable. We derived algebraic necessary and sufficient conditions for
generic local identifiability for both the whole network, and a single
transfer function.

The algebraic conditions of [24] allow rapidly testing local identifiability
for any given network, but finding a graph-theoretical characterization, akin
to what was done in the full excitation case [10], remains an open question,
even though it is known that the property depends solely on the graph. Such
characterization would in particular pave the way for optimizing the selection
of nodes to be excited and measured, alike the work in [11] in the full
measurement case.

In this line of work, we introduced in [25] _decoupled_ identifiability,
necessary for local identifiability, see Section II. We extended the algebraic
characterization of [24] when some transfer functions are known/fixed a
priori, and developed it in terms of closed-loop transfer matrices
$T(G)=(I-G)^{-1}$, which led to some necessary and some sufficient path-based
conditions for decoupled identifiability.

An approach different to all that precedes is to that network dynamics are
known, and aim at identifying the topology from input/output data. This
problem is referred to as topology identification, and is addressed in e.g.
[26, 27]. [28] studies diffusively coupled linear networks, which can be
represented by undirected graphs.

In this paper, we introduce _separable networks_ , which are a generalization
of the decoupled version of the network, allowing for different topologies in
excited and measured subgraphs, see Section III and Fig. 1. Thanks to their
particular structure, global and local identifiability are equivalent on those
networks, thus global identifiability can be studied with the algebraic tools
of [24].

We obtain a necessary and sufficient _combinatorial characterization_ of
global identifiability, in terms of existence of paths and conditions on their
parity. Since the decoupled network is a particular case of separable network,
this condition can be formulated on the decoupled network of networks of any
topology, _not only separable networks_. And generic decoupled identifiability
is necessary for generic global identifiability [25], hence the necessary
condition applies to a network of any topology.

###  I-C Framework

Assumptions:  We consider model (1). Consistently with previous work (e.g.[10,
17, 9]), we assume:

  1. 1)

The network is well-posed and stable, that is $(I-G(q))^{-1}$ is proper and
stable.

  2. 2)

All the entries of $G(q)$ are proper transfer functions.

  3. 3)

The network is stable in the following sense : $|\lambda_{i}|<1$ for each
eigenvalue $\lambda_{i}$ of $G$.

Throughout the paper, we develop our results without exploiting noise signals.
However, under some mild assumptions, noise signals $v(t)$ can play the same
role as excitation signals, as [20]: the network is reformulated as an
equivalent network model, where noise is cast into excitations.

We suppose that there are exactly $n_{B}n_{C}$ unknown transfer functions,
i.e. as many as the number of (excitation - measurement) pairs, and we address
the identifiability of the _whole_ network, i.e. all unknown transfer
functions. If there are more unknown transfer functions, then it is not
identifiable since there are more unknowns than (input, output) data.

Genericity: We will focus on _generic_ properties: we say that a property is
generic if it either holds (i) for _almost all_ variables, i.e for all
variables except possibly those lying on a lower-dimensional set[29, 30] (i.e.
a set of dimension lower than $m_{\circ}$, the number of unknown transfer
functions), or (ii) for no variable. For example, take a polynomial $p$. The
_nonzeroness_ of $p(x)$ is a generic property of $x$: either (i) $p(x)\neq 0$
for all $x$ except its roots, or (ii) $p$ is the zero polynomial, which
returns zero for all $x$.

Consistently with [24, 25], we consider a single frequency: instead of working
with transfer functions $G_{ij}(q)$ and their transfer matrix $G(q)$, we work
with scalar values $G_{ij}$ and their matrix $G\in\mathbb{C}^{n\times n}$.
Conceptually, our generic results directly extend to the transfer function
case: if one can recover a $G_{ij}(z)$ at a given frequency $z$ for almost all
$G$ consistent with a network, then one can also recover it at all other
frequencies. In the remainder, for the sake of simplicity, we work in the
scalar setup, hence omit the $(q)$.

The framework of this paper is summarized below:

  * •

Partial excitation and measurement

  * •

Allows for the presence of known transfer functions next to the unknown ones

  * •

No use of noise, scalar setup

  * •

_Global_ identifiability on _separable_ networks

    * $\Rightarrow$

Applies on decoupled identifiability of all networks

  * •

_Generic_ identifiability of the _whole_ network

  * •

We assume $n_{B}n_{C}=m_{\circ}$, i.e. as much data as unknowns

##  II IDENTIFIABILITY

We remind different notions of identifiability relevant to our work [1, 10,
24, 25]. In order to lighten notations, we denote $T(G)=(I-G)^{-1}$.

###### Definition 1

A network is _globally identifiable_ at $G$ from excitations $\mathcal{B}$ and
measurements $\mathcal{C}$ if, for all network matrix $\tilde{G}$ with same
zero and known entries as $G$, there holds

$\displaystyle
C\,T(\tilde{G})\,B=C\,T(G)\,B\Rightarrow\tilde{G}^{\circ}=G^{\circ},$ (2)

where matrices $B$ and $C$ are binary selections indicating respectively the
excited and measured nodes, forming sets $\mathcal{B}$ and $\mathcal{C}$
respectively. $C\,T(G)\,B$ is the global transfer matrix between input and
output. The network is _generically globally identifiable_ if it is
identifiable at _almost all_ $G$.

This definition extends [10] to the case where some transfer functions are
known ($G^{\bullet}$), and some are not ($G^{\circ}$), as in [2]. We call
_global identifiability_ this standard notion of identifiability, to avoid
confusion with _local_ identifiability [24], which corresponds to
identifiability provided that $\tilde{G}$ is sufficiently close to $G$. Local
identifiability is necessary for global identifiability, and no counter-
example to sufficiency is known.

###### Definition 2

A network is _locally identifiable_ at $G$ from excitations $\mathcal{B}$ and
measurements $\mathcal{C}$ if there exists $\epsilon>0$ such that for any
$\tilde{G}$ with same zero and known entries as $G$ satisfying
$||\tilde{G}-G||<\epsilon$, there holds

$\displaystyle
C\,T(\tilde{G})\,B=C\,T(G)\,B\Rightarrow\tilde{G}^{\circ}=G^{\circ}.$ (3)

The network is _generically locally identifiable_ if it is locally
identifiable at _almost all_ $G$.

Local identifiability can be characterized algebraically based on the matrix
$K$:

$\displaystyle K(G)\triangleq\left(B^{\top}T^{\top}(G)\otimes
C\,T(G)\right)I_{G^{\circ}},$ (4)

where we remind that $T(G)=(I-G)^{-1}$, symbol $\otimes$ denotes the Kronecker
product and the matrix $I_{G^{\circ}}\in\\{0,1\\}^{n^{2}\times m_{\circ}}$
selects only the columns of the preceding $n_{B}n_{C}\times n^{2}$ matrix
corresponding to unknown modules [25].

###### Theorem II.1

(Corollary 4.1 in [24])
Exactly one of the two following holds:

  1. (i)

$\operatorname{rank}\,K=m_{\circ}$ for almost all $G$ and $G^{\circ}$ is
locally identifiable at almost all $G$;

  2. (ii)

$\operatorname{rank}\,K<m_{\circ}$ for all $G$ and $G^{\circ}$ is locally
_non-_ identifiable at all $G$, therefore globally non-identifiable at all
$G$.

Moreover, $\operatorname{rank}\,K=m_{\circ}$ is equivalent to the following
implication holding for all $\Delta$ with same zero entries as $G^{\circ}$:

$\displaystyle C\,T(G)\,\Delta\,T(G)\,B=0\Rightarrow\Delta=0.$ (5)

Equation (5) suggests the definition of a new notion, where the two matrices
$T(G)$ of (5) do not need to have the same parameters anymore: this notion is
_decoupled_ identifiability.

###### Definition 3

A network is _decoupled-identifiable_ at $(G,$ $G^{\prime})$, with $G$ and
$G^{\prime}$ sharing the same zero entries, if for all $\Delta$ with same zero
entries as $G^{\circ}$, there holds:

$\displaystyle C\,T(G)\,\Delta\,T(G^{\prime})\,B=0\Rightarrow\Delta=0.$ (6)

Decoupled identifiability, initially introduced for purely algebraic reasons,
can be interpreted in terms of the identifiability of a larger network: the
_decoupled network._

###### Definition 4

Consider a network of $n$ nodes with excitation matrix $B$, measurement matrix
$C$ and network matrix $G=G^{\bullet}+G^{\circ}$, where $G^{\bullet}$ collects
the known modules and $G^{\circ}$ collects the unknown modules. Its _decoupled
network_ is composed of $2n$ nodes:
$\\{1,\dots,n,1^{\prime},\dots,n^{\prime}\\}$. Its network matrix is defined
by

$\displaystyle\hat{G}(G,G^{\prime})\triangleq\begin{bmatrix}G&G^{\circ}\\\
0&G^{\prime}\end{bmatrix},$

where $G^{\prime}$ has the same zero entries as $G$. Transfer matrices $G$ and
$G^{\prime}$ are considered as known, while $G^{\circ}$ contains the unknown
modules. Excitations are applied on the first subgraph ($G^{\prime}$), and
measurements on the second one ($G$), i.e. its excitation and measurement
matrices are

$\displaystyle\hat{B}\triangleq\begin{bmatrix}0&0\\\ 0&B\end{bmatrix},$
$\displaystyle\hat{C}\triangleq\begin{bmatrix}C&0\\\ 0&0\end{bmatrix}.$

The proposition below relates the notion of decoupled identifiability with the
decoupled network we just introduced.

###### Proposition II.1

(Proposition 3.3 in [25]) The network $G$ is generically decoupled-
identifiable if and only if its decoupled network $\hat{G}$ is generically
globally identifiable.

Generic decoupled identifiability is necessary for generic local
identifiability (which is itself necessary for generic global identifiability)
[25]. No counterexample to sufficiency is known to the authors, despite
extensive systematic numerical tests, available in [31].

###### Proposition II.2

(Proposition 3.2 in [25]) If a network is generically locally identifiable,
then it is generically decoupled-identifiable.

##  III SEPARABLE NETWORKS

We now introduce separable networks, which are a generalization of decoupled
networks, where the excited and measured subgraphs are not required to have
the same topology anymore. A _separable network_ is a network for which
excitations and measurement can be isolated in two distinct subgraphs, with no
known transfer function linking the two subgraphs. Between the two subgraphs
lie all the unknown transfer functions, going from the excited subgraph to the
measured one. A formal definition in terms of network matrices is given below,
and an example is given in Fig. 1.

$\mathcal{C}$$\mathcal{B}$$G_{B}$$G_{C}$$G^{\odot}$ Figure 1: An example of
separable network: the excitations $\mathcal{B}$ are isolated in one subgraph,
and the measurements $\mathcal{C}$ in another subgraph. The unknown transfer
functions, in dashed orange, link the excited subgraph to the measured one.

###### Definition 5

A _separable network_ is a network whose matrices have the following block
structure:

$\displaystyle G=\begin{bmatrix}G_{C}&G^{\odot}\\\ 0&G_{B}\end{bmatrix},$
$\displaystyle G^{\bullet}=\begin{bmatrix}G_{C}&0\\\ 0&G_{B}\end{bmatrix},$
$\displaystyle G^{\circ}=\begin{bmatrix}0&G^{\odot}\\\ 0&0\end{bmatrix},$
$\displaystyle B=\begin{bmatrix}0&0\\\ 0&B^{\dagger}\end{bmatrix},$
$\displaystyle C=\begin{bmatrix}C^{\dagger}&0\\\ 0&0\end{bmatrix}.$ (7)

We have the following important property: on separable networks, global and
local identifiability are equivalent.

###### Proposition III.1

A separable network is locally identifiable at $G$ at if and only if it is
globally identifiable at $G$.

Proof: Consider a separable network: its matrices have the block structure
described in (5). From Definition 1, the network is generically identifiable
at $G$ if, for all $\tilde{G}^{\circ}$ with same zero entries as $G^{\circ}$,
there holds

$\displaystyle
C\,(I-\tilde{G})^{-1}\,B=C\,(I-G)^{-1}\,B\Rightarrow\tilde{G}^{\circ}=G^{\circ}$
(8)

where matrices $C,B,G$ and $G^{\circ}$ have the block structure of (5), and
$\tilde{G}=\begin{bmatrix}G_{C}&\tilde{G}^{\odot}\\\ 0&G_{B}\end{bmatrix}.$

Developing (8) from the block structure of (5) yields

$\displaystyle
C^{\dagger}\,T(G_{C})\,\tilde{G}^{\odot}\,T(G_{B})\,B^{\dagger}=C^{\dagger}\,T(G_{C})\,G^{\odot}\,T(G_{B})\,B^{\dagger}$
$\displaystyle\Rightarrow\tilde{G}^{\odot}=G^{\odot},$

and bringing out common terms gives

$\displaystyle
C^{\dagger}\,T(G_{C})\,\underbrace{(\tilde{G}^{\odot}-G^{\odot})}_{\triangleq\Delta}\,T(G_{B})\,B^{\dagger}=0$
$\displaystyle\Rightarrow\underbrace{\tilde{G}^{\odot}-G^{\odot}}_{=\Delta}=0,$

which is exactly what we obtain by developing (5) with the block structure of
(5). To conclude, we know from Theorem II.1 that (5) is a necessary and
sufficient condition for local identifiability.

Since $m_{\circ}=n_{B}n_{C}$, $K$ introduced in (4) is a square matrix, hence
$\operatorname{rank}\,K=m_{\circ}$ is equivalent to $\det K\neq 0$. Theorem
II.1 can then be rewritten in terms of the determinant. In addition, since we
work on separable networks, global and local identifiability are equivalent,
hence the theorem below characterizes global identifiability.

###### Theorem III.1

Consider a separable network. Exactly one of the two following holds:

  1. (i)

$\det K\neq 0$ for almost all $G$ and $G^{\circ}$ is globally identifiable at
almost all $G$;

  2. (ii)

$\det K=0$ for all $G$ and $G^{\circ}$ is globally _non-_ identifiable at all
$G$.

Moreover, $\det K=m_{\circ}$ is equivalent to the following implication
holding for all $\Delta$ with same zero entries as $G^{\circ}$:

$\displaystyle
C^{\dagger}\,T(G_{C})\,\Delta\,T(G_{B})\,B^{\dagger}=0\Rightarrow\Delta=0.$
(9)

##  IV COMBINATORIAL CHARACTERIZATION

We are now going to derive a combinatorial characterization based on a re-
expression of the determinant of $K$. The closed-loop transfer function
$T_{ji}$ is expressed in terms of transfer functions $G_{ji}$ in the following
way. The analytic matrix $T(G)$ can be expanded in the Taylor series

$\displaystyle T(G)=(I-G)^{-1}=I+\sum_{k=1}^{\infty}G^{k},$ (10)

which converges since the spectral radius of $G$ is strictly smaller than one,
see Assumption 3) in Section I-C. A classical result in graph theory is that
$[G^{k}]_{ji}$ is the sum of all paths from $i$ to $j$ of length $k$:

$\displaystyle[G^{k}]_{ji}=\sum_{\begin{subarray}{c}\text{all $k$-paths}\\\
i\rightarrow j\end{subarray}}\underbrace{G_{j*}\ \dots\ G_{*i}}_{k\text{
terms}},$ (11)

where the notation $*$ denotes some node of the network, which can be
different for each occurence of $*$. Combining (10) and (11) gives the
following lemma, which extends Lemma 2 of [19] for networks with cycles.

###### Lemma IV.1

[19] Consider the closed-loop transfer matrix $T(G)=(I-G)^{-1}$. Its entries
are given as follows:

  1. 1.

if there is no path from $i$ to $j$, $T_{ji}=0$

  2. 2.

otherwise, $T_{ji}$ is the (possibly infinite) sum of all the paths from $i$
to $j$:

$\displaystyle T_{ji}=\sum_{\begin{subarray}{c}\text{all paths}\\\
i\rightarrow j\end{subarray}}G_{j*}\ \dots\ G_{*i}.$ (12)

In the sequel we refer to the unknown transfer functions $G^{\circ}_{ji}$ as
unknown edges $\alpha$. We develop $\det K$ as the sum over all possible row-
column permutations by Leibniz formula111$T_{\alpha,\sigma_{B}(\alpha)}$ is
the transfer function between $\sigma_{B}(\alpha)$, and _start node of_ edge
$\alpha$, and $T_{\sigma_{C}(\alpha),\alpha}$ is the one between _end node of_
edge $\alpha$ and $\sigma_{C}(\alpha)$.:

$\displaystyle\det K=\sum_{\sigma\in
S}\operatorname{sgn}(\sigma)\prod_{\alpha\in\mathcal{E}^{\circ}}T_{\sigma_{C}(\alpha),\alpha}\
T_{\alpha,\sigma_{B}(\alpha)},$ (13)

where each row-column permutation corresponds to a bijective assignation
$\sigma:\mathcal{E}^{\circ}\rightarrow\mathcal{B}\times\mathcal{C}$, i.e.
between unknown edges and (excitation - measurement) pairs. $S$ denotes the
set of all such bijective assignations, $\sigma_{B}(\alpha)$ is the excitation
assigned to edge $\alpha$ by assignation $\sigma$ and $\sigma_{C}(\alpha)$ is
its measurement. The sign $\operatorname{sgn}(\sigma)$ equals $+1$ if the
number of transpositions in assignation $\sigma$ is even, and $-1$ otherwise.
A transposition is the swap of two elements, and each $\sigma$ is obtained by
combining a certain number of transpositions.

The Leibniz formula (13) can be further developed by plugging (12) in the
equation. The analysis is no longer made on the $T_{ji}$, $\det K$ is now
expressed in terms of paths of transfer functions $G_{ji}$222$G_{\alpha,*}$
stands for the transfer function from a node $*$ to _start node of_ edge
$\alpha$, and $G_{*,\alpha}$ denotes the one from _end node of_ edge $\alpha$
to a node $*$.:

$\displaystyle\det K=\sum_{\sigma\in
S}\operatorname{sgn}(\sigma)\prod_{\alpha\in\mathcal{E}^{\circ}}\Biggl{[}$
$\displaystyle\biggl{(}\sum_{\begin{subarray}{c}\text{all paths}\\\
\alpha\rightarrow\sigma_{C}(\alpha)\end{subarray}}G_{\sigma_{C}(\alpha),*}\
\dots\ G_{*,\alpha}\biggr{)}$ $\displaystyle\cdot$
$\displaystyle\biggl{(}\sum_{\begin{subarray}{c}\text{all paths}\\\
\sigma_{B}(\alpha)\rightarrow\alpha\end{subarray}}G_{\alpha,*}\ \dots\
G_{*,\sigma_{B}(\alpha)}\biggr{)}\Biggr{]}$

This expression can be conveniently re-expressed using the notion of
_collections of paths_ , that we introduce below.

###### Definition 6

A collection of paths $\pi$ is a set of $m^{\circ}$ paths $\pi_{i}$ (one
$\pi_{i}$ for each unknown edge), where each path $\pi_{i}$ is a sequence of
connected edges that starts at an excited node (i.e. in $\mathcal{B}$), and
ends at a measured node (i.e. in $\mathcal{C}$). Since we work on separable
networks, each $\pi_{i}$ goes through one and only one unknown edge.

We say that $\pi$ is _bijective_ if no two paths of $\pi$ start at the same
excitation and end at the same measurement.

Distributing the product over all unknown edges $\alpha$ gives

$\displaystyle\det K=\sum_{\sigma\in
S}\operatorname{sgn}(\sigma)\sum_{\pi\in\Pi_{\sigma}}\mu(\pi),$

where $\pi$ is a bijective collection of paths, as defined in Definition 6,
$\Pi_{\sigma}$ is the set of all $\pi$ corresponding to assignation $\sigma$
and $\mu(\pi)$ is the _monomial_ corresponding to $\pi$:

$\displaystyle\mu(\pi)\triangleq\prod_{\alpha\in\mathcal{E}^{\circ}}G_{\pi_{C}(\alpha),*}\
...\ G_{*,\alpha}\cdot G_{\alpha,*}\ ...\ G_{*,\pi_{B}(\alpha)}$ (14)

where $\pi_{B}(\alpha)$ and $\pi_{C}(\alpha)$ are respectively the starting
and ending node of the path going through $\alpha$ in $\pi$, and the transfer
functions $G_{ji}$ may appear several times in $\mu(\pi)$, which would mean
that it is taken several times by $\pi$.

From (14), we group by monomials of same $\pi$: instead of summing over
$\sigma$ and then over $\pi$, we sum directly over $\pi$:

$\displaystyle\det K=\sum_{\pi\in\Pi}\operatorname{sgn}(\pi)\,\mu(\pi),$ (15)

where $\Pi$ is the set of all bijective collection of paths $\pi$. As $\pi$
derives from an assignation $\sigma$, its monomial has a sign, denoted by
$\operatorname{sgn}(\pi)$.

Observe that from a same group of edges it may be possible to build different
bijective $\pi$ (this will be the case e.g. when two paths cross multiple
times), so that these different $\pi$ will have the same monomial $\mu$. Hence
we regroup the same monomials together:

$\displaystyle\det K=\sum_{\mu\in
M}\biggl{(}\sum_{\pi\in\Pi_{\mu}}\operatorname{sgn}(\pi)\biggr{)}\ \mu,$ (16)

where $M$ is the set of all monomials $\mu$ corresponding to bijective
collections of paths, and $\Pi_{\mu}$ is the set of all bijective collections
of paths $\pi$ corresponding to monomial $\mu$. We define the _repetition_
$r(\mu)\triangleq\sum_{\pi\in\Pi_{\mu}}\operatorname{sgn}(\pi)$, which allows
to rewrite (16) in a compact way:

$\displaystyle\det K=\sum_{\mu\in M}r(\mu)\,\mu.$ (17)

As seen in Theorem III.1, $\det K$ encodes the global (non)-identifiability of
separable networks. Hence equation (17) allows providing a necessary and
sufficient combinatorial characterization of global identifiability, in terms
of the repetition $r(\mu)$.

###### Theorem IV.1

Consider a separable network. It is generically globally identifiable if and
only if there is at least one monomial $\mu\in M$ such that its repetition
$r(\mu)\neq 0$.

Proof: From Theorem III.1, we know that a separable network is generically
globally identifiable if and only if $\det K\neq 0$ for almost all $G$.
Equation (17) expresses $\det K$ as a sum over all monomials $\mu$, weighted
by their repetition $r(\mu)$. A sum of distinct monomials is generically
nonzero if and only if at least one of the monomials has a nonzero
coefficient. Therefore, for this sum to be nonzero for almost all $G$, at
least one $\mu$ must have a nonzero repetition $r(\mu)$

Since the decoupled network is a particular case of separable network, this
condition can be formulated on the decoupled network of a network $G$ of any
topology, _not only separable networks_. And generic decoupled identifiability
is necessary for generic global identifiability [25], hence the necessary
condition of Theorem IV.1, formulated on decoupled network $\hat{G}$, applies
to a network $G$ of any topology.

Theorem IV.1 gives a necessary and sufficient combinatorial characterization,
but building an efficient algorithm to check this condition remains an open
question.

##  V CONCLUSION

This work was motivated by one main open question: determining path-based
conditions for generic identifiability of networked systems.

Introducing separable networks allowed to address global identifiability of
such graphs using the algebraic tools of local identifiability. A new approach
led to a necessary and sufficient combinatorial characterization of
identifiability, in terms of existence of paths and conditions on their
parity.

Furthermore, this necessary condition not only applies to separable networks,
but to networks of _any topology._ It follows from the fact that the decoupled
network is a particular case of separable networks, and generic decoupled
identifiability is necessary for generic global identifiability.

A further open question is whether our necessary and sufficient combinatorial
characterization can be algorithmically checked. Also, we would like to
establish the equivalence (or not) between the notions introduced here and
local identifiability for a general network.

##  VI ACKNOWLEDGMENTS

The authors gratefully acknowledge Federica Garin (Inria, Gipsa-lab, France)
for the interesting, insightful discussions.

## References

  * [1] H. H. Weerts, A. G. Dankers, and P. M. Van den Hof, “Identifiability in dynamic network identification,” IFAC-PapersOnLine, 2015.
  * [2] H. Weerts, P. M. Van den Hof, and A. Dankers, “Single module identifiability in linear dynamic networks,” in 2018 IEEE Conference on Decision and Control (CDC), pp. 4725–4730, IEEE, 2018.
  * [3] M. Gevers, A. S. Bazanella, and G. V. da Silva, “A practical method for the consistent identification of a module in a dynamical network,” IFAC-PapersOnLine, vol. 51, no. 15, pp. 862–867, 2018.
  * [4] H. H. Weerts, P. M. Van den Hof, and A. G. Dankers, “Prediction error identification of linear dynamic networks with rank-reduced noise,” Automatica, vol. 98, pp. 256–268, 2018.
  * [5] M. Gevers, A. S. Bazanella, and G. A. Pimentel, “Identifiability of dynamical networks with singular noise spectra,” IEEE Transactions on Automatic Control, vol. 64, no. 6, pp. 2473–2479, 2018.
  * [6] P. M. Van den Hof, K. R. Ramaswamy, A. G. Dankers, and G. Bottegal, “Local module identification in dynamic networks with correlated noise: the full input case,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 5494–5499, IEEE, 2019.
  * [7] K. R. Ramaswamy and P. M. Vandenhof, “A local direct method for module identification in dynamic networks with correlated noise,” IEEE Transactions on Automatic Control, 2020.
  * [8] A. S. Bazanella, M. Gevers, J. M. Hendrickx, and A. Parraga, “Identifiability of dynamical networks: which nodes need be measured?,” in IEEE 56th Annual Conference on Decision and Control (CDC), 2017.
  * [9] H. H. Weerts, P. M. Van den Hof, and A. G. Dankers, “Identifiability of linear dynamic networks,” Automatica, vol. 89, pp. 247–258, 2018.
  * [10] 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, 2018.
  * [11] S. Shi, X. Cheng, and P. M. Van den Hof, “Excitation allocation for generic identifiability of a single module in dynamic networks: A graphic approach,” in Proc. 21st IFAC World Congress, 2020.
  * [12] X. Cheng, S. Shi, and P. M. Van den Hof, “Allocation of excitation signals for generic identifiability of dynamic networks,” in Proceedings of the IEEE Conference on Decision and Control, 2019.
  * [13] X. Cheng, S. Shi, and P. M. Van den Hof, “Allocation of excitation signals for generic identifiability of linear dynamic networks,” IEEE Transactions on Automatic Control, vol. 67, no. 2, pp. 692–705, 2021.
  * [14] H. Dreef, S. Shi, X. Cheng, M. Donkers, and P. M. Van den Hof, “Excitation allocation for generic identifiability of linear dynamic networks with fixed modules,” IEEE Control Systems Letters, vol. 6, pp. 2587–2592, 2022.
  * [15] S. Shi, X. Cheng, and P. M. Van den Hof, “Generic identifiability of subnetworks in a linear dynamic network: the full measurement case,” arXiv preprint arXiv:2008.01495, 2020.
  * [16] H. J. van Waarde, P. Tesi, and M. K. Camlibel, “Topological conditions for identifiability of dynamical networks with partial node measurements,” IFAC-PapersOnLine, vol. 51, no. 23, pp. 319–324, 2018.
  * [17] 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, 2019.
  * [18] A. S. Bazanella, M. Gevers, and J. M. Hendrickx, “Network identification with partial excitation and measurement,” in 58th Conference on Decision and Control (CDC), pp. 5500–5506, IEEE, 2019.
  * [19] 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.
  * [20] S. Shi, X. Cheng, and P. M. Van den Hof, “Single module identifiability in linear dynamic networks with partial excitation and measurement,” IEEE Transactions on Automatic Control, 2021.
  * [21] X. Cheng, S. Shi, I. Lestas, and P. M. Van den Hof, “A necessary condition for network identifiability with partial excitation and measurement,” arXiv preprint arXiv:2105.03187, 2021.
  * [22] E. Mapurunga, M. Gevers, and A. S. Bazanella, “Identifiability of dynamic networks: the essential r$\backslash$^ ole of dources and dinks,” arXiv preprint arXiv:2211.10825, 2022.
  * [23] 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), pp. 1616–1621, IEEE, 2022\.
  * [24] A. Legat and J. M. Hendrickx, “Local network identifiability with partial excitation and measurement,” in 2020 59th IEEE Conference on Decision and Control (CDC), pp. 4342–4347, IEEE, 2020.
  * [25] A. Legat and J. M. Hendrickx, “Path-based conditions for local network identifiability – full version,” arXiv preprint, 2021.
  * [26] H. J. van Waarde, P. Tesi, and M. K. Camlibel, “Topology identification of heterogeneous networks of linear systems,” in 58th Conference on Decision and Control (CDC), pp. 5513–5518, IEEE, 2019.
  * [27] H. J. van Waarde, P. Tesi, and M. K. Camlibel, “Topology reconstruction of dynamical networks via constrained lyapunov equations,” IEEE Transactions on Automatic Control, vol. 64, pp. 4300–4306, 2019.
  * [28] E. L. Kivits and P. M. Van den Hof, “Local identification in diffusively coupled linear networks,” in 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 874–879, IEEE, 2022.
  * [29] E. J. Davison, “Connectability and structural controllability of composite systems,” Automatica, vol. 13, no. 2, pp. 109–123, 1977.
  * [30] J.-M. Dion, C. Commault, and J. Van der Woude, “Generic properties and control of linear structured systems: a survey,” Automatica, 2003.
  * [31] A. Legat and J. M. Hendrickx, Identifiability test.  https://github.com/alegat/identifiable.