{'fraction_non_alphanumeric': 0.05267814058227441, 'fraction_numerical': 0.016755133772988044, 'mean_word_length': 3.8577939835916135, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 45, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Causal Inference for Influence Propagation -- Identifiability of the Independent Cascade Model

Independent cascade (IC) model is a widely used influence propagation model for social networks. In this paper, we incorporate the concept and techniques from causal inference to study the identifiability of parameters from observational data in extended IC model with unobserved confounding factors, which models more realistic propagation scenarios but is rarely studied in influence propagation modeling before. We provide the conditions for the identifiability or unidentifiability of parameters for several special structures including the Markovian IC model, semi-Markovian IC model, and IC model with a global unobserved variable. Parameter identifiability is important for other tasks such as influence maximization under the diffusion networks with unobserved confounding factors.


Introduction
Extensive research has been conducted studying the information and influence propagation behavior in social networks, with numerous propagation models and optimization algorithms proposed (cf. [15,2]). Social influence among individuals in a social network is intrinsically a causal behavior -one's action or behavior causes the change of the behavior of his or her friends in the network. Therefore, it is helpful to view influence propagation as a causal phenomenon and apply the tools in causal inference to this domain.
In causal inference, one key consideration is the confounding factors caused by unobserved variables that affect the observed behaviors of individuals in the network. For example, we may observe that user A adopts a new product and a while later her friend B adopts the same new product. This situation could be because A influences B and causes B's adoption, but it could also be caused by an unobserved factor (e.g. an unknown information source) that affects both A and B. Confounding factors are important in understanding the propagation behavior in networks, but so far the vast majority of influence propagation research does not consider confounders in network propagation modeling. In this paper, we intend to fill this gap by explicitly including unobserved confounders into the model, and we borrow the research methodology from causal inference to carry out our research.
Causal inference research has developed many tools and methodologies to deal with such unobserved confounders, and one important problem in causal inference is to study the identifiability of the causal model, that is, if we can identify the certain effect of an intervention, or identify causal model parameters, from the observational data. In this paper, we introduce the concept of identifiability in causal inference research to influence propagation research and study whether the propagation models can be identified from observational data when there are unobserved factors in the causal propagation model. We propose the extend the classical independent cascade (IC) model to include unobserved causal factors, and consider the parameter identifiability problem for several common causal graph structures. Our main results are as follows. First, for the Markovian IC model, in which each unobserved variable may affect only one observed node in the network, we show that it is fully identifiable. Second, for the semi-Markovian IC model, in which each unobserved variable may affect exactly two observed nodes in the network, we show that as long as a local graph structure exists in the network, then the model is not parameter identifiable. For the special case of a chain graph where all observed nodes form a chain and every unobserved variable affect two neighbors on the chain, the above result implies that we need to know at least n/2 parameters to make the rest parameters identifiable, where n is the number of observed nodes in the chain. We then show a positive result that when we know n parameters on the chain, the rest parameters are identifiable. Third, for the global hidden factor model where we have an unobserved variable that affects all observed nodes in the graph, we provide reasonable sufficient conditions so that the parameters are identifiable.
Overall, we view that our work starts a new direction to integrate rich research results from network propagation modeling and causal inference so that we could view influence propagation from the lens of causal inference, and obtain more realistic modeling and algorithmic results in this area. For example, from the causal inference lens, the classical influence maximization problem [15] of finding a set of k nodes to maximize the total influence spread is really a causal intervention problem of forcing an intervention on k nodes for their adoptions, and trying to maximize the causal effect of this intervention. Our study could give a new way of studying influence maximization that works under more realistic network scenarios encompassing unobserved confounders.

Related Work
Influence Propagation Modeling. As described in [2], the main two models used to describe influence propagation are the independent cascade model and the linear threshold model. Past researches on influence propagation mostly focused on influence maximization problems, such as [15,22]. In these articles, they select seed nodes online, observe the propagation in the network, and opti-mize the number of activated nodes after propagation by selecting optimal seed nodes. Also, some works are studying the seed-node set minimization problem, such as [11]. However, in our work, we mainly consider restoring the parameters in the independent cascade model by observing the network propagation. After obtaining the parameters in the network, we can then base on this to accomplish downstream tasks including influence maximization and seed-node set minimization.
Causal Inference and Identifiability. For general semi-Markovian Bayesian causal graphs, [13] and [21] have given two different algorithms to determine whether a do effect is identifiable, and these two algorithms have both soundness and correctness. [14] also proves that the ID algorithm and the repeating use of the do calculus are equivalent, so for semi-Markovian Bayesian causal graphs, the do calculus can be used to compute all identifiable do effects.
In addition, for a special type of causal model, the linear causal model, articles [4] and [8] have given some necessary conditions and sufficient conditions on whether the parameters in the graph are identifiable with respect to the structure of the causal graph. However, the necessary and sufficient condition for parameter identifiability problem is not addressed and it remains an open question. In this paper, we study another special causal model derived from the IC model. Since the IC model can be viewed as a Bayesian causal model when the graph structure is a directed acyclic graph and it has some special properties, we try to give some necessary conditions and sufficient conditions for the parameters to be identifiable under some special graph structures.

Model and Problem Definitions
Following the convention in causal inference literature (e.g. [19]), we use capital letters (U, V, X, . . .) to represent variables or a set of variables, and their corresponding lower-case letters to represent their values. For a directed graph, we use U 's and V 's to represent nodes since each node will also be treated as a random variable in causal inference. For a node V i , we use N + (V i ) and N − (V i ) to represent the set of its out-neighbors and in-neighbors, respectively. When the graph is directed acyclic (DAG), we refer to a node's in-neighbors as its parents and denote the set as Pa(V i ) = N − (V i ). When we refer to the actual values of the parent nodes of V i , we use pa(V i ). For a positive integer k, we use [k] to denote {1, 2, . . . , k}. We use boldface letters to represent vectors, such as r = (r 1 , r 2 , . . . , r n ) = (r i ) i∈ [n] .
The classical independent cascade model [15] of influence diffusion in a social network is modeled as follows. The social network is modeled as a directed graph G = (V, E), where V = {V 1 , V 2 , · · · , V n } is the set of nodes representing individuals in the social network, and E ⊆ V ×V is the set of directed edges representing the influence relationship between the individuals. Each edge (V i , V j ) ∈ E is associated with an influence probability p(i, j) ∈ (0, 1] (we assume that . Each node is either in state 0 or state 1, representing the idle state and the active state, respectively. At time step 0, a seed set S 0 ⊆ V of nodes is selected and activated (i.e. their states are set to 1), and all other nodes are in state 0. The propagation proceeds in discrete time steps t = 1, 2, . . .. Let S t denote the set of nodes that are active by time t, and let S −1 = ∅. At any time t = 1, 2, . . ., the newly activated node V i ∈ S t−1 \S t−2 tries to activate each of its inactive outgoing neighbors V j ∈ N + (V i ), and the activation is successful with probability p(i, j). If successful, V j is activated at time t and thus V j ∈ S t . The activation trial of V i on its out-neighbor V j is independent of all other activation trials. Once activated, nodes stay as active, that is, S t−1 ⊆ S t . The propagation process ends at a step when there are no new nodes activated. It easy to see that the propagation ends in at most n − 1 steps, so we use S n−1 to denote the final set of active nodes after the propagation.
Influence propagation is naturally a result of causal effect -one node's activation causes the activation of its outgoing neighbors. If the graph is directed and acyclic, then the IC model on this graph can be equated to a Bayesian causal model. In fact, we can consider each node in the IC model as a variable, and for a node V i , it takes the value determined by P (V i = 1|pa(V i )) = 1 − j:Vj ∈Pa(Vi),vj =1 in pa(Vi) (1 − p j,i ). Obviously, this is equivalent to our definition in the IC model. IC model is introduced in [15] to model influence propagation in social networks, but in general, it can model the causal effects among binary random variables. In this paper, we mainly consider the directed acyclic graph (DAG) setting, which is in line with the causal graph setting in the causal inference literature [19]. We will discuss the extension to general cyclic graphs or networks in the appendix.
All variables V 1 , V 2 , . . . , V n are observable, and we call them observed variables. They correspond to observed behaviors of individuals in the social network. There are also potentially many unobserved (or hidden) variables that affecting individuals' behaviors. We use U = {U 1 , U 2 , . . .} to represent the set of unobserved variables. In the IC model, we assume each U i is a binary random variable with probability r i to be 1 and probability 1 − r i to be 0, and all unobserved variables are mutually independent. We allow unobserved variables U i 's to have directed edges pointing to the observed variables V j 's, but we do not consider directed edges among the unobserved variables in this paper. If U i has a directed edge pointing to V j , we usually use q i,j to represent the parameter on this edge. It has the same semantics as the p i,j 's in the classical IC model: if U i = 1, then with probability q i,j U i successfully influence V j by setting its state to 1, and with probability 1−q i,j V j 's state is not affected by U i , and this influence or activation effect is independent from all other activation attempts on other edges. Thus, overall, in a network with unobserved or hidden variables, we use G = (U, V, E) to represent the corresponding causal graph, where U is the set of unobserved variables, V is the set of observed variables, and E ⊆ (V × V ) ∪ (U × V ) is the set of directed edges. We assume that G is a DAG, and the state of every unobserved variable U i is sampled from {0, 1} with parameter r i , while the state of every observed variable V j is determined by the states of its parents and the parameters on the incoming edges of V j following the IC model semantics. In the DAG G, we refer to an observable node V i as a root if it has no observable parents in the graph. Every root V i has at least one unobserved parent. We use vectors p, q, r to represent parameter vectors associated with edges among observed variables, edges from unobserved to observed variables, and unobserved nodes, respectively. We refer to the model M = (G = (U, V, E), p, q, r) as the causal IC model. When the distinction is needed, we use capital letters P, Q, R to represent the parameter names, and lower boldface letters p, q, r to represent the parameter values.
In this paper, we focus on the parameter identifiability problem following the causal inference literature. In the context of the IC model, the states of nodes V = {V 1 , V 2 , . . . , V n } are observable while the states of U = {U 1 , U 2 , . . .} are unobservable. We define parameter identifiability as follows.
Definition 1 (Parameter Identifiability). Given a graph G = (U, V, E), we say that a set of IC model parameters Θ ⊆ P ∪ Q ∪ R on G is identifiable if after fixing the values of parameters outside Θ and fixing the observed probability distributions P (V = v ) for all V ⊆ V and all v ∈ {0, 1} |V | , the values of parameters in Θ are uniquely determined. We say that the graph G is parameter identifiable if Θ = P ∪ Q ∪ R. Accordingly, the algorithmic problem of parameter identifiability is to derive the unique values of parameters in Θ given graph G = (U, V, E), the values of parameters outside Θ, and the observed probability distributions P (V = v ) for all V ⊆ V and all v ∈ {0, 1} |V | . Finally, if the algorithm only uses a polynomial number of observed probability values P (V = v )'s and runs in polynomial time, where both polynomials are with respect to the graph size, we say that the parameters in Θ are efficiently identifiable.
Note that when there are no unobserved variables (except the unique unobserved variables for each root of the graph), the problem is mainly to derive the parameters p i,j 's from all observed P (V = v )'s. In this case, the parameter identifiability problem bears similarity with the well-studied network inference problem [10,16,9,7,18,1,3,6,5,17,20,12]. The network inference problem focuses on using observed cascade data to derive the network structure and propagation parameters, and it emphasizes on the sample complexity of inferring parameters. Hence, when there are no unobserved variables in the model, we could use the network inference methods to help to solve the parameter identifiability problem. However, in real social influence and network propagation, there are other hidden factors that affect the propagation and the resulting distribution. Such hidden factors are not addressed in the network inference literature. In contrast, our study in this paper is focusing on addressing these hidden factors in network inference, and thus we borrow the ideas from causal inference to study the identifiability problem under the IC model.
In this paper, we study three types of unobserved variables that could commonly occur in network influence propagation. They correspond to three types of IC models with unobserved variables, as summarized below.
Markovian IC Model. In the Markovian IC model, each observed variable V i is associated with a unique unobserved variable U i , and there is a directed edge from U i to V i . This models the scenario where each individual in the social network has some latent and unknown factor that affects its observed behavior. We use q i to denote the parameter on the edge (U i , V i ). Note that the effect of U i on the activation of V i is determined by probability r i · q i , and thus we treat r i = 1 for all i ∈ [n], and focus on identifying parameters q i 's. Thus the graph G = (U, V, E) has parameters q = (q i ) i∈[n] , and p = (p i,j ) (Vi,Vj )∈E . Figure 1 shows an example of a Markovian IC model. If some q i = 0, it means that the observed variable V i has no latent variable influencing it, and it only receives influence from other observed variables.  Semi-Markovian IC Model. The second type of unobserved variables is the hidden variables connected to exactly two observed variables in the graph. In particular, for every pair of nodes V i , V j ∈ V , we allow one unobserved variable U i,j that has two edges, one pointing to V i and the other pointing to V j . This models the scenario that two individuals in the social network has a common unobserved confounder that may affect the behavior of two individuals. We call this type of model semi-Markovian IC model, following the common terminology of the semi-Markovian model in the literature [19]. In this model, each U i,j has a parameter r i,j , and edges (U i,j , V i ) and (U i,j , V j ) have parameters q i,j,1 and q i,j,2 respectively. Therefore, the graph has parameters r = ( Within this model, we will pay special attention to a special type of graphs where the observed variables form a chain, i.e. V 1 → V 2 → · · · → V n , and the unobserved variables always point to the two neighbors on the chain. In this case, we use U i to denote the unobserved variable associated with edge (V i , V i+1 ), and the parameters on the edges (U i , V i ) and (U i , V i+1 ) are denoted as q i,1 and q i,2 , respectively. Figure 3 represents this chain model.

IC Model with A Global Unobserved
Variable. The third type of hidden variables is a global unobserved variable U 0 that points to all observed variables in the network. This naturally models the global causal effect where some common factor affects all or most individuals in the network. For every edge (U 0 , V i ), we use q 0,i to represent its parameter.
Moreover, we can combine this model with the Markovian IC model, where we allow both unobserved variable U i for each individual and a global unobserved varoable U 0 . Figure 2 represents this model.

Parameter Identifiability of the Markovian IC Model
For the Markovian IC model in which every observed variable has its own unobserved variable, we can fully identify the model parameters in most cases, as given by the following theorem.
Theorem 1 (Identifiability of the Markovian IC Model). For an arbitrary Markovian IC model G = (U, V, E) with parameters q = (q i ) i∈[n] and p = (p i,j ) (Vi,Vj )∈E , all the q i parameters are efficiently identifiable, and for ev- Proof. For an observed variable (node) V i , suppose that its observed parents are V i1 , V i2 , · · · , V it . Therefore, we have From Eq.(1), we can obtain the value of q i . Then if q i = 1, from Eq.(2), we can derive the value of p ij ,i . Moreover, for each root node V i , we can get q i by computing q i = P (V i = 1). The computational efficiency is obvious.
The theorem essentially says that all parameters are identifiable under the Markovian IC model, except for the corner case where some q i = 1. In this case, the observed variable V i is fully determined by its unobserved parent U i , so we cannot determine the influence from other observed parents of V i to V i . But the influence from the observed parents of V i to V i is not useful any way in this case, so the edges from the observed parents of V i to V i will not affect the causal inference in the graph and they can be removed.

Parameter Identifiability of the Semi-Markovian IC Model
Following the definition in the model section, we then consider the identifiability problem of the semi-Markovian models. We will demonstrate that in most cases, this model is not parameter identifiable. Actually, from [21] we know that the semi-Markovian Bayesian causal model is also not identifiable in general. Essentially, our conclusion is not related to their result. On the other side, we will show that with some parameters known in advance, the semi-Markovian IC chain model will be identifiable.

Condition on Unidentifiability of the Semi-Markovian IC Model
More specifically, the following theorem shows the unidentifiability of the semi-Markovian IC model with a special structure in it.
Theorem 2 (Unidentifiability of the Semi-Markovian IC Model). Suppose in a general graph G, we can find the following structure. There are three Suppose each of U 1 , U 2 only has two edges associated to it, the three nodes V 1 , V 2 , V 3 can be written adjacently in a topological order of nodes in U ∪ V . Then we can deduce that the graph G is not parameter identifiable.  Proof (Outline). To prove that the parameters in the model with this structure are not identifiable, we give two different sets of parameters directly. We show that these two different sets of parameters produce the same distribution of nodes in V , and thus the set of parameters is not identifiable by observing only the distribution of V . The details of these two sets of parameters and the distributions they produce are included in Appendix A.

Identifiability of the Chain Model
We now consider the chain model as described in Section 3 and depicted in Figure 3. In this structure, we present a conclusion of identifiability under the assumption that the valuations of some parameters are our prior knowledge. We divide the parameters of the graph into four vectors For the chain model, our theorem below shows that once the parameters p 1 is known, q 2 or r is known, the set consists of remaining parameters in the chain is efficiently identifiable.  1] , and suppose that all parameters are in the range (0, 1). If the values of parameter p 1 is known, q 2 or r is known, then the remaining parameters are efficiently identifiable.
Proof (Outline). We use induction to prove this theorem. Under the assumption that p 1 is known and q 2 or r is known, suppose p 1 , p 2 , · · · , p t−2 , r 1 , r 2 , · · · , r t−2 , q 1,1 , q 2,1 , · · · , q t−2,1 and q 1,2 , q 2,2 , · · · , q t−2,2 , r t−1 q t−1,1 has been determined by us, and we prove that q t−1,1 , r t−1 , p t−1 , q t−1,2 and r t q t,1 can also be determined. In fact, by the distribution of the first t nodes on the chain we can obtain three different equations, and after substituting our known parameters, the inductive transition can be completed. It is worthy noting that this inductive process can also be used to compute the unknown parameters efficiently.
The proof is lengthy because of the many corner cases considered and the need to discuss the cases t = n, t = 2 and 2 < t < n. The details of this proof are included in Appendix B.
According to Theorem 3 we get that the semi-Markovian chain is parameter identifiable in the case that n particular parameters are known. Simultaneously, by Theorem 2, we can show that if just less than n+1 2 parameters are known, then this semi-Markovian chain will not be parameter identifiable. Actually, if the chain model is parameter identifiable, utilizing Theorem 2, we know that for each 2 ≤ t ≤ n − 1, at least one of parameters between p t−1 , p t , r t−1 , r t , q t−1,1 , q t−1,2 , q t,1 and q t,2 should be known. Therefore, we let t = 2, 4, · · · , 2 n−1 2 , we can deduce that at least n−1 2 should be known. Formally, we have the following collary of Theorem 2 and Theorem 3. parameters are known in advance, the remaining parameters are unidentifiable; if it is allowed to know n parameters in advance, we can choose p 1 , q 2 or p 1 , r to be known, then the remaining parameters are identifiable.

Parameter Identifiability of Model with a Global Hidden Variable
Next, we consider the case where there is a global hidden variable in the causal IC model, defined as those in Section 3. If there is only one hidden variable U 0 in the whole model, we prove that the parameters in general in this model are identifiable; if there is not only U 0 , the model is also Markovian, that is, there are also n hidden variables U 1 , · · · , U n corresponding to V 1 , V 2 , · · · , V n , then the parameters in this model are identifiable if certain conditions are satisfied.

Observable IC Model with Only a Global Hidden Variable
Suppose the observed variables in the connected DAG graph G = (U, V, E) are V 1 , V 2 , · · · , V n in a topological order and there is a global hidden variable U 0 such that there exists an edge from U 0 to the node for each observable variable V i . Suppose the activating probability of U 0 is r and the activating probability from U to V i is q i ∈ [0, 1) (naturally, q 1 = 0 and there are at least 3 of nonzero q i 's). Now we propose a theorem according to these settings. Proof (Outline). We discuss this problem in two cases, the first one is the existence of two disconnected points V i , V j , i < j in V and q i , q j = 0. At this point we can use 1 − q j = P (V1=0,V2=0,··· ,Vi=1,Vi+1=0,··· ,Vj =0) P (V1=0,V2=0,··· ,Vi=1,Vi+1=0,··· ,Vj−1=0) to solve out q j , and then use P (V 1 = 0, V 2 = 0, · · · , V j = 0) and P (V 1 = 0, V 2 = 0, · · · , V j−1 = 0) to solve out r.
After getting r, by the quotients of probabilities of propagating results, we can get all the parameters.
Another case is that there is no V i , V j as described above. At this point there must exist three points V i , V j , V k that are connected with each other and q i , q j , q k = 0. We observe the probabilities of different possible propagating results of these three points with all other nodes are 0 after the propagation. From these, we can solve out q i , q j , q k , and then solve out all parameters by the same method as in the first case.

Markovian IC Model with a Global Hidden Variable (Mixed Model)
Suppose the model is Here, V 1 , V 2 , · · · , V n are in a topological order. The parameters are r 0 , q 0 = (q 0,i ) i∈[n] , q = (q i ) i∈[n] and p = (p i,j ) (Vi,Vj )∈E .
Theorem 5 (Identifiability of Markovian IC Model with a Global Hidden Variable (Mixed Model)). For an arbitrary Markovian IC Model with a Global Hidden Variable G = (U, V, E) with parameters r 0 , q 0 = (q 0,i ) i∈[n] , q = (q i ) i∈[n] and p = (p i,j ) (Vi,Vj )∈E , we suppose that all the parameters are not 1. If ∃i, j, k ∈ [n], i < j < k such that each pair in V i , V j , V k are disconnected and q 0,i , q 0,j , q 0,k = 0, then the parameters q 0,t , q t and p t,l , l > t > k are identifiable. Moreover, if V i , V j , V k can be adjacently continuous in some topological order, i.e. j = i + 1, k = i + 2 without loss of generality, all the parameters are identifiable.
Proof (Outline). Assuming that there exist V i , V j , V k that satisfy the requirements of the theorem, then we can write expressions for the distribution of these three parameters when all other nodes with subscripts not greater than l are equal to 0. In fact, we can see that with these 8 expressions, we can solve for P (V 1 = 0, · · · , V l = 0, U 0 = 1) and P (V 1 = 0, · · · , V l = 0, U 0 = 0). Since we have P (V 1 = 0, · · · , V l = 0, U 0 = 1) = r l t=1 (1 − q t )(1 − q 0,t ) and P (V 1 = 0, · · · , V l = 0, U 0 = 0) = (1 − r) l t=1 (1 − q t ), we will be able to obtain all the parameters very easily by dividing these equations two by two. This proof has some trivial discussion to show that this computational method does not fail due to corner cases.
Notice that the parameters in this model are identifiable when and only when a special three-node structure appears in it. Intuitively, this is because through this structure we can more easily obtain some information about the parameters, which does not contradict the intuition of Theorem 2.

Conclusion
In this paper, we study the parameter identifiability of the independent cascade model in influence propagation and show conditions on identifiability or unidentifiability for several classes of causal IC model structure. We believe that the incorporation of observed confounding factors and causal inference techniques is important in the next step of influence propagation research and identifiability of the IC model is our first step towards this goal. There are many open problems and directions in combining causal inference and propagation research. For example, seed selection and influence maximization correspond to the intervention (or do effect) in causal inference, and how to compute such intervention effect under the network with unobserved confounders and how to do influence maximization is a very interesting research question. In terms of identifiability, one can also investigate the identifiability of the intervention effect, or whether given some intervention effect one can identify more of such effects. One can also look into identifiability in the general cyclic IC models, for which we provide some initial discussions in Appendix E, but more investigations are needed. A Proof for Unidentifiability of the Semi-Markovian IC Model (Theorem 2) Theorem 2 (Unidentifiability of the Semi-Markovian IC Model). Suppose in a general graph G, we can find the following structure. There are three observable nodes Suppose each of U 1 , U 2 only has two edges associated to it, the three nodes V 1 , V 2 , V 3 can be written adjacently in a topological order of nodes in U ∪ V . Then we can deduce that the graph G is not parameter identifiable.
Proof. To prove that the parameters are unidentifiable, we will construct two different sets of valuations of parameters such that two distributions of values taken by the nodes in V are the same. In fact, we assume that the parent nodes of V i are V i,1 , V i,2 , · · · , V i,ti and U i,1 , · · · , U i,si for i = 1, 2, 3. And, the parameters are set as shown in Figure 4. One set of parameters is that all the parameters are set to 0.5. Another set of parameters is that all the parameters are set to be 0.5 except r 1 , r 2 , q 1,1 , q 1,2 , q 2,2 and q 2,3 . The exceptions are set to be where r 2 is an arbitrary number between 1 4 and 9 14 . Then we only need to prove that for an arbitrary distribution of the ancestors of V 1 , V 2 , V 3 except U 1 , U 2 , the distributions of V 1 , V 2 , V 3 are the same for the two parameter settings. This is because if this condition is satisfied, then the children of V 1 , V 2 , V 3 will not be affected by the differences of the parameter valuations because the parameters determining them are the same (only the distribution of U 1 , U 2 will change but each of them only has two children that are in {V 1 , V 2 , V 3 }). In fact, we have P (V1 = 1, V2 = 1, V3 = 1|pa(V1), pa(V2), pa(V3)) = 13 + 3P (V2 = 1|pa(V2) + 3P (V1 = 1|pa(V2)(11 + 5P (V2 = 1|pa(V2)) 128 , P (V1 = 0, V2 = 1, V3 = 1|pa(V1), pa(V2), pa(V3)) (12) = 3(1 + 5P (V1 = 1|pa(V1)))(1 − P (V2 = 1|pa(V2))) 128 , Notice that these equations are only related to P (V 1 = 1|pa(V 1 )) and P (V 2 = 1|pa(V 2 )), so until now, we have proved that the two sets of parameters produce two same distributions for observed variables and therefore G is parameter unidentifiable at this point.

Theorem 3 (Identifiability of the Semi-Markovian IC Chain Model).
Suppose that we have a semi-Markovian IC chain model with the graph G = (U, V, E) and the IC parameters p = (p i ) i∈[n−1] , q 1 = (q i,1 ) i∈[n−1] , q 2 = (q i,2 ) i∈[n−1] and r = (r i ) i∈[n −1] , and suppose that all parameters are in the range (0, 1). If the values of parameter p 1 is known, q 2 or r is known, then the remaining parameters are efficiently identifiable.
Proof. In the analysis, we use the following notations. For observed nodes V 1 , V 2 , . . . , V t , we use V 1 · · · V t to represent their collective states as a bit string. For a bit string γ of length t, we write Note that a γ is observable, but b γ and c γ are not observable. We will use induction method to prove this result. More specifically, we want to prove the base step that p 1 , r 1 , q 1,1 , q 1,2 and q 2,1 r 2 are known. Moreover, we will prove the induction step that if p 1 , p 2 , · · · , p t−2 , r 1 , r 2 , · · · , r t−2 , q 1,1 , q 2,1 , · · · , q t−2,1 and q 1,2 , q 2,2 , · · · , q t−2,2 , r t−1 q t−1,1 are already known, we can compute q t−1,1 , r t−1 , p t−1 , q t−1,2 and r t q t,1 using distributions of observed variables.
Initially, in order to complete the induction step, we divide the problem into two cases which are t = n and 3 ≤ t ≤ n − 1.
Firstly, if t = n, we only need to compute q t−1,1 , r t−1 , p t−1 , q t−1,2 . Actually, we have the following relations of a γ0 and other known variables. If γ[−1] = 0, we have We should notice that b β , c β are both determined by the parameters we already know, hence, we can see the three types of recursions as functions of q t−1,2 , q t−1,2 r t−1 and p t−1 . We only need to prove that we can solve the three parameters from these functions. In order to simplify the equations, we define some notations as below where |β| = t − 2.
It is easy to verify that Co 1 (β) + Co 2 (β) = −a β1 . According to these, we have which is equivalent to To show the relation of the coefficients of q t−1,2 r t−1 and q t−1,2 , we prove two lemmas at first. Lemma 1. For two arbitrary 0 − 1 string β 1 , β 2 with the same lengths, we prove that the equation a β 2 0 c β 2 0 = a β 1 1 c β 1 1 is impossible.
which is impossible if all the terms are not zero.
Lemma 2. As we defined above, we have the following equation if the denominators are not zero: Proof. Actually, we can compute the left hand side of Equation 2 as below: So the lemma is proved. We should also notice that this lemma holds not only for t = n, it is true for t = 2, 3, · · · , n − 1 because Co 1 and Co 2 are defined the same as Equation 28. Now we prove that Equation 25 and Equation 30 are two linear independent equations for unknown variables q t−1,2 r t−1 and q t−1,2 . We only need to prove that the ratio of coefficients of q t−1,2 r t−1 and q t−1,2 are different in these two equations. Because otherwise, we have Until now, we have proved that when t is equal to n, we can compute q t−1,1 , r t−1 , p t−1 , q t−1,2 if the other parameters are already known. Now we consider the case that 3 ≤ t ≤ n − 1, and we need to prove that if t < n, we can use p 1 , p 2 , · · · , p t−2 , r 1 , r 2 , · · · , r t−2 , q 1,1 , q 2,1 , · · · , q t−2,1 and q 1,2 , q 2,2 , · · · , q t−2,2 , r t−1 q t−1,1 to compute q t−1,1 , r t−1 , p t−1 , q t−1,2 and r t q t,1 . First, we propose a lemma to illustrate the recurrence relationship of the distributions.
Moreover, we have the following relations of a γ0 and other known variables. If γ[−1] = 0, we have If γ[−1] = 1 and γ = β1, β[−1] = 0, we have If γ[−1] = 1 and β[−1] = 1, we have Each of these equations is only one more factor compared to the t = n case, so we can still get the similar result which is an equation of q t−1,2 r t−1 and q t−1,2 . Since we assume that r t−1 or q t−1,2 is known, we can get both r t−1 and q t−1,2 by this equation. Then we can get r t q t,1 by Equation 39 using r t q t, Then all the terms in Equation 40 except p t−1 are known and not 0, so we can get p t−1 . This completes the inductive transition.
In conclusion, we have solved the identifiability problem of the model with a global hidden variable.

D Proof for the Mixed Model (Theorem 5)
Theorem 5 (Identifiability of Markovian IC Model with a Global Hidden Variable (Mixed Model)). For an arbitrary Markovian IC Model with a Global Hidden Variable G = (U, V, E) with parameters r 0 , q 0 = (q 0,i ) i∈[n] , q = (q i ) i∈[n] and p = (p i,j ) (Vi,Vj )∈E , we suppose that all the parameters are not 1. If ∃i, j, k ∈ [n], i < j < k such that each pair in V i , V j , V k are disconnected and q 0,i , q 0,j , q 0,k = 0, then the parameters q 0,t , q t and p t,l , l > t > k are identifiable. Moreover, if V i , V j , V k can be adjacently continuous in some topological order, i.e. j = i + 1, k = i + 2 without loss of generality, all the parameters are identifiable.
Proof. In order to simplify our proof, we introduce some new notations. Suppose we already have V i , V j , V k as required in description of this theorem.

E Discussion on the Cyclic Models
In the last section in appendix, we will introduce how to transform a general IC model to a causal model so that we can use do calculus method to identify do effects. In fact, since the propagation of the IC model takes place for at most n rounds [2], we formulate that the state of V i in round t is V i,t and that V i,t has three values, 0, 1 and 2, for three states. We construct a causal graph G = (V , E ) from these nodes with subscripts of time. Here, state 0 means that the node is not activated, 1 means that the node was activated at the last time point, and state 2 means that the node is activated and has already tried to activate its child nodes. Moreover, all edges are defined as (V i,t , V i,t+1 ), 1 ≤ i, t ≤ n and (V i,t , V j,t+1 ), 1 ≤ i, j, t ≤ n, (V i , V j ) ∈ E . Furthermore, we define the following propagating equations.
By definition, we obtain that G as a Bayesian causal model, so we can use the do calculus method [19] to solve out the identifiable do effects. For example, suppose G has V 1 , V 2 , V 3 as observed nodes and U 1 as an unobserved node. The edges in E are (U 1 , V 1 ), (U 1 , V 2 ), (V 1 , V 2 ), (V 2 , V 3 ) and (V 3 , V 1 ). There exists a cycle in G so it cannot be seen as a DAG. However, utilizing our transformation, the result graph G is in Figure 5, which is a Bayesian causal model.