Causal Inference for Influence Propagation — Identifiability of the Independent Cascade Model

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.

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.

Following the convention in causal inference literature (e.g. [19]), we use capital letters ($U,V,X,\ldots$) 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 ${\it Pa}(V_{i})=N^{-}(V_{i})$. When we refer to the actual values of the parent nodes of $V_{i}$, we use ${\it pa}(V_{i})$. For a positive integer $k$, we use $[k]$ to denote $\{1,2,\ldots,k\}$. We use boldface letters to represent vectors, such as $\boldsymbol{r}=(r_{1},r_{2},\ldots,r_{n})=(r_{i})_{i\in[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},\cdots,V_{n}\}$ is the set of nodes representing individuals in the social network, and $E\subseteq V\times V$ is the set of directed edges representing the influence relationship between the individuals. Each edge $(V_{i},V_{j})\in E$ is associated with an influence probability $p(i,j)\in(0,1]$ (we assume that $p(i,j)=0$ if $(V_{i},V_{j})\notin E$). 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}\subseteq 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,\ldots$. Let $S_{t}$ denote the set of nodes that are active by time $t$, and let $S_{-1}=\emptyset$. At any time $t=1,2,\ldots$, the newly activated node $V_{i}\in S_{t-1}\setminus S_{t-2}$ tries to activate each of its inactive outgoing neighbors $V_{j}\in 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}\in 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}\subseteq 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|{\it pa}(V_{i}))=1-\prod_{j:V_{j}\in{\it Pa}(V_{i}),v_{j}=1\text{ in }{\it pa}(V_{i})}(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},\ldots,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},\ldots\}$ 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\subseteq(V\times V)\cup(U\times 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 $\boldsymbol{p},\boldsymbol{q},\boldsymbol{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),\boldsymbol{p},\boldsymbol{q},\boldsymbol{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 $\boldsymbol{p},\boldsymbol{q},\boldsymbol{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},\ldots,V_{n}\}$ are observable while the states of $U=\{U_{1},U_{2},\ldots\}$ are unobservable. We define parameter identifiability as follows.

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^{\prime}=v^{\prime})$’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.

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}\rightarrow V_{2}\rightarrow\cdots\rightarrow 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.

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.

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.

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.

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.

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},\cdots,U_{n}$ corresponding to $V_{1},V_{2},\cdots,V_{n}$, then the parameters in this model are identifiable if certain conditions are satisfied.

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 0.E, but more investigations are needed.