Nonlinear identifiability of directed acyclic graphs with partial excitation and measurement
Renato Vizuete Julien M. Hendrickx


Enabling Practical and Privacy-Preserving Image Processing
    
Chao Wang
cwang17@wpi.edu

Worcester Polytechnic Institute
Shubing Yang
sueyoung@uw.edu

University of Washington
Xiaoyan Sun
xsun7@wpi.edu

Worcester Polytechnic Institute
Jun Dai
jdai@wpi.edu

Worcester Polytechnic Institute
Dongfang Zhao
dzhao@uw.edu

University of Washington

    
=============================================================================================================================================================================================================================================================================================

empty



§ ABSTRACT 
We analyze the identifiability of directed acyclic graphs in the case of partial excitation and measurement. We consider an additive model where the nonlinear functions located in the edges depend only on a past input, and we analyze the identifiability problem in the class of pure nonlinear functions satisfying f(0)=0. We show that any identification pattern (set of measured nodes and set of excited nodes) requires the excitation of sources, measurement of sinks and the excitation or measurement of the other nodes. Then, we show that a directed acyclic graph (DAG) is identifiable with a given identification pattern if and only if it is identifiable with the measurement of all the nodes. Next, we analyze the case of trees where we prove that any identification pattern guarantees the identifiability of the network. Finally, by introducing the notion of a generic nonlinear network matrix, we provide sufficient conditions for the identifiability of DAGs based on the notion of vertex-disjoint paths.






§ INTRODUCTION


Systems composed by single entities or units that interact in a network to generate a more complex global behavior are ubiquitous <cit.>. Many of these interactions are characterized by dynamics located at the level of edges, and the identification of these dynamics is essential to study the evolution, analyze the stability, and design control actions. Since the size of the networks can be really large and the design of experiments generally involves an economic cost, it is important to derive identifiability conditions that specify which nodes must be excited and measured to guarantee the identification of the network.
While the identifiability of linear interactions modeled by transfer functions have been extensively analyzed in recent years <cit.>, few works have focused in nonlinear networks due to the complexity of the dynamics. The case of nonlinear identifiability where all the nodes can be excited (full excitation) has been analyzed in <cit.>, where surprisingly, the identifiability conditions are weaker than in the linear case when pure nonlinear functions are considered. These differences between the linear and nonlinear cases can be explained by the consequences of the superposition principle that allows the mixing of certain information only in the linear case.

In many scenarios, due to physical limitations, some nodes might not be available to be excited, or the cost associated with the excitation of a node (actuator) might be greater than the cost associated with the measurement of a node (sensor). For instance, in an electrical network, the excitation of a node might require a power source while the measurement of a node might require only a sensor. 
Therefore, it is important to relax the full excitation assumption and guarantee at the same time the identifiability of all the network for more complex identification patterns (combination of excited nodes and measured nodes).

The identifiability of linear networks in the case of partial excitation and measurement has been well analyzed in several works <cit.>, where the symmetry excitation/measurement plays an important role. Nevertheless, even in the linear case, many problems are still open such as the minimum number of nodes that must be excited and measured, a characterization of the identification patterns that guarantee identifiability of the network, among others. 


In this work, we analyze the identifiability of nonlinear networks in the case of partial excitation and measurement. We consider a model where the dynamics depend only on a past input, and we restrict the analysis to the case of directed acyclic graphs (DAGs) and pure nonlinear surjective functions. 
We show that any identification pattern requires the excitation of sources, the measurement of sinks, and the excitation or measurement of the other nodes of the network. Then, we show that a DAG is identifiable with an identification pattern if and only if it is identifiable with the measurement of all the nodes, which is different from the linear case. In the case of trees, we show that there is a symmetry between the identifiability conditions for the full excitation and full measurement cases and that any identification pattern guarantees identifiability. Unlike the linear case, for more general DAGs, we show that the symmetry does not hold, and we derive sufficient conditions for identifiability based on the notion of vertex-disjoint paths and a generic nonlinear network matrix.







§ PROBLEM FORMULATION




 §.§ Model class


We consider a network characterized by a weakly connected digraph G=(V,E) composed by a set of nodes V={ 1,…,n} and a set of edges E⊆ V× V. The output of each node i in the network is given by:

    y_i^k=∑_j∈𝒩_if_i,j(y_j^k-m_i,j)+u_i^k-1,   for all   i∈ V,

where the superscripts of the inputs and outputs  denote the corresponding values at the specific time instants, the delay m_i,j∈ℤ^+ is finite, f_i,j is a nonlinear function, 𝒩_i is the set of in-neighbors of node i, and u_i is an arbitrary external excitation signal. If a node is not excited, its corresponding excitation signal is set to zero. Fig. <ref> presents an illustration of the model considered in this work. 
Our goal is to analyze a general nonlinear dynamics, but in this preliminary work, we will focus on the effect of the nonlinearities. The model  (<ref>) corresponds to a generalized version of the nonlinear static model in <cit.>, where m_i,j can take a value different from 1. 

The nonzero functions f_i,j between the nodes define the topology of the network G, forming the set of edges E. We do not consider multiple edges between two nodes since they would be indistinguishable and hence unidentifiable.


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



Assumption <ref> implies that we know which nodes are connected by nonzero functions. 
The objective of this work is to determine which nodes need to be excited and/or measured to identify all the nonlinear functions in the network. Our aim is to determine the possibility of identification and not to develop an algorithm or verify the accuracy of other identification methods.






Similarly to <cit.>, for the identification process we assume that the relations between the signals of excited nodes and the outputs of measured nodes have been perfectly identified. In addition, we restrict our attention to networks that do not contain any cycle (i.e., directed acyclic graphs). This implies that when we measure a node i, we obtain an identification of the function F_i:

    y_i^k=u_i^k-1+F_i(u_1^k-2,…,u_1^k-M_1,…,u_n_i^k-2,…,u_n_i^k-M_n_i),
    
        1,…,n_i∈𝒩^e→ i,

where 𝒩^e→ i is the set of excited nodes with a path to the node i. The function F_i determines the output of the node i based on the excitation signals and only depends on a finite number of inputs (i.e., M_1,…,M_n_i are finite) due to the finite delays m_i,j and the absence of cycles.
With a slight abuse of notation, we use the superscript in the function F_i^(s) to denote that all the inputs in (<ref>) are delayed by s:






    F_i^(s)=F_i(u_1^k-2-s,…,u_1^k-M_1-s,…,u_n_i^k-2-s,…,u_n_i^k-M_n_i-s).













 §.§ Identifiability




    We define an identification pattern as a pair (^e,^m) where ^e⊆ V is the set of excited nodes and ^m⊆ V is the set of measured nodes.



    We define the number of identification actions as N^m,e=^e+^m.


Clearly, if a node i is excited and measured at the same time (i.e., i∈^e and i∈^m), this increases N^m,e by 2.

Next, we define the relationships between the measurements of the nodes and the functions f_i,j.


    Given a set of measured nodes 𝒩^m, the set of measured functions F(𝒩^m) associated with 𝒩^m is given by:
    
    F(𝒩^m):={F_i | i∈𝒩^m}.





We say that a function f_i,j associated with an edge satisfies F(𝒩^m) if f_i,j can lead to F(𝒩^m) through (<ref>).

Since the identifiability problem can be hard or unrealistic for general functions, we restrict the problem to  a certain class of functions : the functions associated with the edges belong to  and that the identifiability is considered only among the functions belonging to . 


    Given a set of functions { f }={f_i,j∈ | (i,j)∈ E} that generates F(^m) and another set of functions {f̃}={f̃_i,j∈ | (i,j)∈ E} that generates F̃(^m). An edge f_i,j is identifiable in a class  if F(^m)=F̃(^m), implies that f_i,j=f̃_i,j.
    A network G is identifiable in a class  if 
    F(^m)=F̃(^m),
    implies that
    { f }={f̃}.


In this work, we will consider analytic functions with a Taylor series that converges to the function for all x∈ (possibly with a finite radius of convergence).
In the full excitation case <cit.>, it has been proved that a static component of a function could make the identifiability problem unsolvable. Also, when linear functions are allowed in a class , the identifiability conditions are similar to the linear case. However, it has been observed that the presence of nonlinearities change the identifiability conditions <cit.>. For this reason, we will focus on the class of pure nonlinear functions <cit.>.


Let  be the class of functions f:→ with the following properties:

    
  * f is analytic in .
    
  * f(0)=0.
    
  * The associated Taylor series f(x)=∑_n=1^∞ a_nx^n contains at least one coefficient a_n≠ 0 with n>1. 
    
  * The range of f is .



Therefore, in the rest of this work we will assume that f_i,j∈.




§ NECESSARY CONDITIONS FOR IDENTIFIABILITY


Since the sources and sinks play an important role in directed acyclic graphs, we first provide necessary conditions that these nodes must satisfy to guarantee identifiability.



For identifiability of a DAG, it is necessary to measure all the sinks and excite all the sources.


    The necessity of the measurement of all the sinks has been proved in <cit.>. For the necessity of the excitation of the sources, let us consider an arbitrary source i. 
    The measurement of an out-neighbor j of the source i provides the output:
    
    y_j^k   =∑_ℓ∈_j f_j,ℓ(y_ℓ^k-m_j,ℓ)+u_j^k-1
       =f_j,i(u_i^k-m_j,i-1)+∑_ℓ∈_j∖{i} f_j,ℓ(y_ℓ^k-m_j,ℓ)+u_j^k-1.

    Since the source i is not excited, (<ref>) becomes:
    
    y_j^k   =f_j,i(0)+∑_ℓ∈_j∖{i} f_j,ℓ(y_ℓ^k-m_j,ℓ)+u_j^k-1
       =∑_ℓ∈_j∖{i} f_j,ℓ(y_ℓ^k-m_j,ℓ)+u_j^k-1.

    Notice that any other function f̃_j,i∈ satisfies (<ref>), which implies that it is not possible to identify the edge f_j,i. 
    Thus, the excitation of all the sources is necessary for identifiability of the network. 




Next, we are interested in determining conditions that other nodes of the network must satisfy to guarantee identifiability.




    For identifiability of a DAG, it is necessary to either excite or measure each node.


    By Lemma <ref>, the excitation of sources and the measurement of sinks is necessary.
    Let us consider an arbitrary node i in a network which is neither a source nor a sink. Let us assume that we can excite or measure the other nodes and all the edges have been identified except the incoming and outgoing edges of i. The measurement of an out-neighbor j of the node i is given by:
    



    
    
    y_j^k   =u_j^k-1+f_j,i(y_i^k-m_j,i)+∑_p∈_j∖{i} f_j,p(y_p^k-m_j,p)
       =u_j^k-1+f_j,i(∑_ℓ∈_i f_i,ℓ(y_ℓ^k-m_j,i-m_i,ℓ))+∑_p∈_j∖{i}f_j,p(y_p^k-m_j,p).

    Notice that the same output (<ref>) can be obtained with the functions f̃_i,ℓ(x)=γ f_i,ℓ(x) and f̃_j,i(x)=f_j,i(x/γ), with γ≠ 0, which implies that the incoming edges and outgoing edges of i cannot be identified. Thus, all the nodes must be either excited or measured.


Similarly to the linear case <cit.>, Proposition <ref> shows that we need at least N^m,e=n to guarantee the identifiability of DAGs in . Nevertheless, unlike the linear case, where N^m,e>n could be necessary for some DAGs <cit.>, in the nonlinear case, we have a stronger result.


There exists an identification pattern with =n that guarantees the identifiability of a DAG.


    It is a direct consequence of the case of full excitation where we can guarantee identifiability by measuring all the sinks and exciting all the other nodes <cit.>.


However, the full excitation case could be restrictive since in many situations, the excitation of all the nodes could not be possible, or the cost of exciting a node could be significantly higher than the cost of measuring a node. For this reason, we are interested in other identification patterns (^e,^m) that guarantee identifiability of a DAG with only =n.

In the rest of this work, we will consider that in any identification pattern, all the sources are excited, all the sinks are measured, and the other nodes are either excited or measured.



§ FULL MEASUREMENT EQUIVALENCE


In the next proposition, we will prove a link between any identification pattern and the full measurement case.





A DAG is identifiable in the class  with the identification pattern (^e,^m) if and only if it is identifiable with the identification pattern (^e,V).

Before presenting the proof of Proposition <ref>, we introduce two lemmas.



    In the full excitation case, 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,ℓ and functions F_ℓ for ℓ∈_i, are identifiable in G if they are identifiable in the induced subgraph [An 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.] G_V∖{ j} with the measurement of i.



Given three nonzero analytic functions f:→ and g,g̃:^p→. Let us assume that  f is not linear
and they satisfy:

    f(0)= g(0)= g̃(0)=0;


    f(x+g(y))=     
    f(x+g̃(y))+h,

where h is an arbitrary function that does not depend on x.
Then g=g̃.




Proposition <ref>
Clearly, if the DAG is identifiable with (^e,^m), is also identifiable with (^e,V) since the full measurement case also includes the information of ^m used for the identifiability.
    Now, let us consider an arbitrary DAG with a set of measured nodes ^m and a set of excited nodes ^e where all the sources are excited and all the sinks are measured. Since any DAG can be sorted in topological order [A topological ordering of a digraph is a linear ordering of its nodes such that for every edge (i,j), j comes before i in the ordering.] <cit.>, let us consider a particular ordering where all the nodes located between two consecutive measured nodes p and q, have a path to q. 
    Notice that if there is a topological ordering with a node w between p and q that does not have a path to q, the node w could be shifted to the right of q in this topological ordering. 
    (For example, see Fig. <ref>). The measurement of the node q provides an output of the type:

    


    
    y_q^k   =F_q
       =∑_j∈_q^ef_q,j(u_j^k-m_q,j-1+F_j^(m_q,j))+∑_ℓ∈_q^mf_q,ℓ(F_ℓ^(m_q,ℓ)),

    
    where _q^e is the set of excited in-neighbors of q and _q^m is the set of measured in-neighbors of q. Since F_q∈ F(^m), let us assume that there exists a set {f̃}≠{ f} such that F_q=F̃_q. Then, we obtain:
    
    ∑_j∈_q^ef_q,j(u_j^k-m_q,j-1+F_j^(m_q,j))+∑_ℓ∈_q^mf_q,ℓ(F_ℓ^(m_q,ℓ))=
    ∑_j∈_q^ef̃_q,j(u_j^k-m_q,j-1+F̃_j^(m_q,j))+∑_ℓ∈_q^mf̃_q,ℓ(F̃_ℓ^(m_q,ℓ)).

    Clearly, the node before q denoted by q-1 has only one path to q. Then, we can set to zero all the inputs except by u_q-1^k-m_q,q-1-1, to have for all u_q-1^k-m_q,q-1-1∈:
    
    f_q,q-1(u_q-1^k-m_q,q-1-1)=f̃_q,q-1(u_q-1^k-m_q,q-1-1),

    which implies f_q,q-1=f̃_q,q-1. Then, by Lemma <ref>, we guarantee that F_q-1=F̃_q-1, which is equivalent to the measurement of the node q-1. Now, the identifiability problem becomes:





    ∑_j∈_q^e∖{q-1}f_q,j(u_j^k-m_q,j-1+F_j^(m_q,j))+∑_ℓ∈_q^mf_q,ℓ(F_ℓ^(m_q,ℓ))=
    ∑_j∈_q^e∖{q-1}f̃_q,j(u_j^k-m_q,j-1+F̃_j^(m_q,j))+∑_ℓ∈_q^mf̃_q,ℓ(F̃_ℓ^(m_q,ℓ)).

    By Lemma <ref>, this new identifiability problem can be solved if the induced subgraph G_V∖{ q-1} obtained with the removal of q-1 is identifiable. In this subgraph G_V∖{ q-1}, the node q-2 has only one path to q, and we can use a similar approach to prove that f_q,q-2=f̃_q,q-2 and F_q-2=F̃_q-2. By following the same procedure, we can guarantee that F_v=F̃_v for all v between p and q, which corresponds to the mathematical constraints obtained with the measurement of these nodes.  
    In the case of the first measured node in the topological ordering, we apply the procedure until the first node in the topological ordering. Notice that this procedure can be used for any measured node such that all the nodes of the network can be covered. This implies that if the DAG is identifiable with (^e,V), it is also identifiable with (^e,^m).




Since any identification pattern guarantees the access to the information corresponding to the measurement of all the nodes in the network, the measurement of an excited node does not change the identifiability of a DAG.




In an identification pattern (^e,^m) that satisfies N^m,e>n, there must be at least a node which is excited and measured at the same time. If a DAG is identifiable with (^e,^m), it is also identifiable with another identification pattern (^e,^m) given by ^e= ^e and ^m=^m∖{ℓ}, where ℓ∈^e and ℓ∈^m. In this way, the identification pattern (^e,^m) can generate a family of subpatterns by removing excited nodes from the set of measured nodes. 


Proposition <ref> illustrates that the information that can be obtained with the excitation of a node (extra input) is in some way more useful than the information that can be obtained with the measurement of a node.  
This notion will be also corroborated with the absence of symmetry full excitation/full measurement in the case of general DAGs. 











§ IDENTIFIABILITY CONDITIONS FOR PARTIAL EXCITATION AND MEASUREMENT




 §.§ Identifiability of trees


We start by deriving identifiability conditions for trees in the case of partial excitation and measurement.





    A tree is identifiable in the class  with =n, if and only if all the sources are excited, all the sinks are measured and the other nodes are either excited or measured. 


By Lemma <ref>, the excitation of all the sources and the measurement of all the sinks is necessary, and by Proposition <ref>, the other nodes must be either excited or measured. We will prove the sufficiency by induction. According to Proposition <ref>, the DAG is identifiable if (and only if) it is identifiable with ^m=V.
Let us assume that there exists a set { f }={f̃} such that F(^m)=F̃(^m).
    Let us consider an arbitrary path of the tree that begins in a source and ends in a sink, and let us set to zero all the inputs except by the excitation signal corresponding to the source (node 1). For any node i in the path that is not a source, the output is given by:
    
    y_i^k
               =f_i,i-1(Θ_i-1(u_1^k-M_i,1)),

    where u_1 is the excitation signal of the source with the corresponding delay M_i,1, and Θ_i-1 is a composition of nonlinear functions associated with the edges. Let us assume that all the edges until the node i-1 have been identified. This implies that we know the function Θ_i-1. Then, since F_i∈ F(^m), we have the identifiability problem:
    
    f_i,i-1(Θ_i-1(u_1^k-M_i,1))=f̃_i,i-1(Θ_i-1(u_1^k-M_i,1)).

    Since the range of all the nonlinear functions is , we have that the range of Θ_i-1 is also . Therefore, we obtain that f_i,i-1(x)=f̃_i,i-1(x) for all x∈, which implies that f_i,i-1=f̃_i,i-1. 
    
    Now, notice that when i=2, the function Θ_1 is the identity function, and clearly the edge f_2,1 can be identified. Then, by induction, all the edges of the path can be identified.
Finally, by considering other paths, we can identify all the tree.


This shows that similarly to the linear case <cit.>, any identification pattern with N^m,e=n, guarantees the identifiability of a tree. Notice that this also holds for path graphs and arborescences, which, unlike trees, necessarily have only one source.

According to Proposition <ref>, an identification pattern where all the sources are excited and the other nodes are measured, provides the identification of a tree. This corresponds to the symmetric result of the identifiability conditions for trees in the full excitation case where the measurement of the sinks is necessary and sufficient <cit.>. Therefore, symmetry holds for trees.



 §.§ Generic nonlinear network matrix




One of the main challenges in the identification of networks is to distinguish the information that arrives to a node i through different paths. For instance, let us consider again the graph in Fig. <ref> with functions f_2,1(y_1^k-m_2,1), f_3,2(y_2^k-m_3,2) and f_3,1(y_1^k-m_3,1). 
The measurement of node 3 provides the output:

    y_3^k   =f_3,1(y_1^k-m_3,1)+f_3,2(y_2^k-m_3,2)
       =f_3,1(u_1^k-m_3,1-1)+f_3,2(f_2,1(u_1^k-m_2,1-m_3,2-1)),

If m_3,1=m_2,1+m_3,2, the output (<ref>) becomes:

    y_3^k=f_3,1(u_1^k-m_2,1-m_3,2-1)+f_3,2(f_2,1(u_1^k-m_2,1-m_3,2-1))

which implies that the information coming through f_3,1 and f_3,2 cannot be distinguished for this particular choice of delays m_i,j. 
Notice that for many networks,
there are particular choices of the delays associated with the nonlinear functions such that for each node i in the network, the excitation signals corresponding to the same excited node in (<ref>) have the same delays.
For instance, this is the case for multipartite digraphs like the one in Fig. <ref>, when the delays of all the nonlinear functions are the same. This particular setting is important for the generalization of results to more general dynamical models where the nonlinear functions can depend on the outputs of nodes with several delays and the mixing of information is possible <cit.>. Furthermore, the identification of networks with this particular choice of delays is more challenging since the number of excitation variables that can be used is smaller. For this reason, we will analyze this worst-case scenario and we will consider that (<ref>) is given by:

    y_i^k=u_i^k-1+F_i(u_1^k-T_i,1,…,u_n_i^k-T_i,n_i),  for 
    
        1,…,n_i∈𝒩^e→ i.

Regarding the measurement of the node 3 in (<ref>), the function F_3 will be of the form:

    y_3^k=F_3(u_1^k-T_3,1),

where T_3,1=m_2,1+m_3,2+1. 


In a more general DAG, a node can have more than one in-neighbor that shares several excitation signals.
Unlike the full excitation case, where each node has its own excitation signal, and identifiability conditions are valid for any function in a specific class, in the case of partial excitation and measurement, particular choices of functions could make a network unidentifiable. 






    Let us consider the DAG in Fig. <ref>. Let us assume that the functions f_3,1, f_3,2, f_4,1, f_4,2 and f_5,3 have been identified.
    The measurement of the node 6 provides the output:
    
    y_6^k=f_6,5(f_5,3(f_3,1(u_1^k-T_5,1)+f_3,2(u_2^k-T_5,2)))
    +f_6,4(f_4,1(u_1^k-T_5,1)+f_4,2(u_2^k-T_5,2)).

    Notice that if f_3,1=γ f_4,1 and f_3,2=γ f_4,2 with γ≠ 0, the functions f_6,5 and f_6,4 cannot be identified since f̃_6,5(x)=f_6,4(f_5,3^-1(x/γ)) and f̃_6,4(x)=f_6,5(f_5,3(γ x)) also generates the output (<ref>).


Example <ref> shows that a DAG could be identifiable for most of the functions, except for particular choices
(e.g., two in-neighbors p and q of a node with outputs of the form y_p=γ y_q for γ≠ 0).
This is similar to the concept of generic identifiability in the linear case, where a network can be identifiable except for a particular choice of transfer functions that remains in a set of measure zero <cit.>. In the context of nonlinear identifiability, we will introduce a  notion similar to the linear case by defining a generic matrix.

For a network G, let us define the matrix J_∈^n× n, where [J_]_i,j=f'_i,j(y_j^k-m_i,j). This matrix can be considered as the adjacency matrix of a linear network G_, that preserves the same topology of G but with edges of the form f'_i,j(y_j^k-m_i,j). Since the output of any node can be expressed as a function of the excitation signals (see (<ref>)), the matrix J_ can also be expressed as a function of the excitation signals with the corresponding delays. Now, let us consider a modification of the matrix J_ where all the excitation signals corresponding to a node i, including different delays, are considered as the same input v_i. We call this new matrix the nonlinear network matrix and we denote it by J_G(), where ∈^^e.
Since J_G() is upper triangular in a DAG, we can guarantee that the matrix T_G():=(I-J_G())^-1=∑_n=0^∞ (J_G())^n is well defined <cit.>. Notice that an entry [T_G]_j,i corresponds to the sum of the product of the edges corresponding to all the walks from i to j in G_.

If we set free variables for the nonzero entries (i.e., edges) of the matrix J_G(), we say that for A,B⊆ V, the rank of a submatrix T_G^A,B() of  T_G()=(I-J_G())^-1 is maximal if it is maximal with respect to the free variablesof  J_G() <cit.>.




    We say that the nonlinear network matrix J_G() associated to the network is generic if there exists a point ^*∈^^e such that any submatrix T_G^A,B(^*) of T_G(^*)=(I-J_G(^*))^-1 has maximal rank.

This generic nonlinear network matrix will be used in the derivation of identifiability conditions for general DAGs.





 §.§ Identifiability of DAGs



Unlike trees, first, we will show that for more general DAGs, the identifiability conditions in the full excitation case do not have a symmetric equivalence in the full measurement case since the excitation of sources is not sufficient to guarantee identifiability.    




    Let us consider the DAG in Fig. <ref> with the functions f_2,1(x)=a_2,1x^3, f_3,1(x)=a_3,1x^3, f_4,2(x)=a_4,2x^3 and f_4,3(x)=a_4,3x^3, that belong to . If the symmetry full excitation/full measurement holds, the excitation of the source 1 should be sufficient to guarantee the identifiability of the network in the full measurement case. 
    The measurement of the node 2 provides the identification of f_2,1 and the measurement of the node 3 provides the identification of f_3,1. The measurement of the node 4 provides the output:   
    
    y_4^k
           =f_4,2(f_2,1(u_1^k-T_4,1))+f_4,3(f_3,1(u_1^k-T_4,1))
       =(a_4,2a_2,1^3+a_4,3a_3,1^3)(u_1^k-T_4,1)^9.

    Notice that the output (<ref>) can also be generated with the functions f̃_4,2(x)=(a_4,2+γa_3,1^3/a_2,1^3)x^3 and f̃_4,3(x)=(a_4,3-γ)x^3 with γ≠ 0, which implies that it is not possible to identify the functions f_4,2 and f_4,3. 
 

Unlike the DAG in Fig. <ref>, the DAG in Fig. <ref>  is unidentifiable for any choice of the parameters of the cubic functions, which shows that the excitation of the sources is not sufficient to guarantee identifiability of DAGs in the class  in the full measurement case. In order to discard cases where the identifiability is not possible only due to a particular choice of functions, we make the following assumption.






    The nonlinear network matrix J_G() associated with the network is generic.


 
Based on the notions of vertex-disjoint paths introduced in the linear case, we will provide sufficient conditions that guarantee identifiability of a DAG with a specific identification pattern.


    A group of paths are mutually vertex disjoint if no two paths of this group contain the same vertex.





    Under Assumption <ref>, a DAG is identifiable in the class  with =n, if:
    
        
  * All the sources are excited, all the sinks are measured and the other nodes are either excited or measured.
        
  * There are vertex-disjoint paths from excited nodes to the in-neighbors of each node.
    


Before presenting the proof of Theorem <ref>, we recall a technical result that will be used in the proof.


    Let H⊂^p and let f:H→^q, where p≥ q. If f is continuously differentiable at the point a∈int H and the linear mapping f'(a):^p→^q is surjective, then the range of f contains a neighborhood of f(a).





Theorem <ref>
We will prove it by induction.
Let us consider an arbitrary DAG and an arbitrary topological ordering of the nodes.
According to Proposition <ref>, the DAG is identifiable if (and only if) it is identifiable with ^m=V.
Let us consider an arbitrary node i. Without loss of generality, let us denote the set of in-neighbors of the node i as _i={1,…,m}. If we set to zero the possible excitation signal u_i of the node i, the measurement of i is given by:

    y_i^k   =∑_j=1^m f_i,j(ϕ_i,j(u_1^k-T_i,1,…,u_n_i^k-T_i,n_i))
       =F_i(ϕ_i,1,…,ϕ_i,m),

    where we use the same notation as in (<ref>). 
    Let us assume that there exists a set { f }={f̃} such that F(^m)=F̃(^m). Since F_i∈ F(^m), we have the identifiability problem:

    F_i(ϕ_i,1,…,ϕ_i,m)=F̃_i(ϕ̃_i,1,…,ϕ̃_i,m).

    Let us assume that all the incoming edges of the nodes at the left of the node i in the topological ordering have been identified. 
Then, the identifiability problem (<ref>) becomes:

    F_i(ϕ_i,1,…,ϕ_i,m)=F̃_i(ϕ_i,1,…,ϕ_i,m).

Now, let us consider the mapping: 



    Φ_i:^n_i→^m




    Φ_i(w_1,…,w_n_i)=(ϕ_i,1(w_1,…,w_n_i),…,ϕ_i,m(w_1,…,w_n_i)),

and the Jacobian matrix of Φ_i denoted by J_Φ_i() where =(w_1,…,w_n_i).
Notice that J_Φ_i() corresponds to the submatrix of the nonlinear network matrix T_G() where the rows are the in-neighbors of i and the columns are the nodes with the excitation signals. Under Assumption <ref>, there exists a point ^* such that T_G(^*) has maximal rank, which also determines a point ^* for J_Φ_i(^*).
According to <cit.>, since there are vertex-disjoint paths from excited nodes to the in-neighbors of i, the generic rank of J_Φ_i(^*) is m, which implies that J_Φ_i(^*) is surjective.
By virtue of Lemma <ref>, the range of Φ_i must contain a neighborhood of Φ_i(^*), which implies that (<ref>) holds in a set of positive measure. Then, by the Identifiy Theorem of analytic functions <cit.>, we guarantee that 



    F_i(z_1,…,z_m)=F̃_i(z_1,…,z_m)   for all  z_1,…,z_m∈,

since the range of all the functions ϕ_i,j is . From (<ref>), it follows that



    f_i,j=f̃_i,j  for all  j=1…,m,

so that all the incoming edges of i can be identified.

Now, notice that for i=2 in the topological ordering, if there is an edge f_2,1, the function ϕ_2,1 is the identity function and the edge f_2,1 can be clearly identified. Then, by induction, the identifiablity analysis is valid for any node in the DAG. Thus, all the DAG is identifiable.



Theorem <ref> implies that a DAG satisfies symmetry full excitation/full measurement if there are vertex-disjoint paths from the sources to the in-neighbors of each node of the network.
This is also consistent with the case of trees since from all the sources we have vertex disjoint paths that reach the in-neighbors of all the nodes of a tree.

When the functions are linear, the space of functions that do not satisfy Assumption <ref> has a dimension smaller than the dimension of the system (i.e., set of measure zero) <cit.>. In the case of nonlinear functions, to the best of our knowledge, the dimension of the space of functions that do not satisfy Assumption <ref> is still not known and its full characterization is left for future work.

Theorem <ref> provides sufficient conditions for the identifiability of DAGs that are weaker than in the linear case. 
For instance, let us consider the DAG in Fig. <ref>. In the linear case, the DAG requires N^m,e>n since the node 1 is a dource and a dink <cit.>, and must be measured and excited. However, in the nonlinear case, we only need N^m,e=n to guarantee identifiability. The node 3 has a vertex-disjoint path from the node 1 and the node 4 has a vertex-disjoint path from 2, so that the DAG satisfies the conditions of Theorem <ref> and it is identifiable with this identification pattern.






§ CONCLUSIONS


We analyzed the identifiability of DAGs with partial excitation and measurement. We showed that in the nonlinear case, a DAG is identifiable with an identification pattern if and only if it is identifiable with the full measurement of the nodes. For trees, we showed that the symmetry full excitation/full measurement holds and that any identification pattern guarantees identifiability.
Unlike the linear case, in the case of more general DAGs, we showed that symmetry does not hold. Finally, we introduced the notion of a generic nonlinear network matrix, and we derived identifiability conditions based on vertex-disjoint paths from excited nodes to the in-neighbors of each node in the 
network.


For future work, it would be important to characterize the space of functions that do not satisfy Assumption <ref>.
Also, it would be interesting to analyze the case when the range of the functions is not all . Finally, a generalization of the analysis to more general digraphs where cycles might exist (F_i depends on an infinite number of inputs), and more general models where the nonlinear function can depend on inputs with several delays <cit.> is definitely an interesting area of research.








IEEEtran






