1 files changed, 84 insertions, 61 deletions
diff --git a/paper/sections/model.tex b/paper/sections/model.tex
index e35aa4a..44236da 100644
--- a/paper/sections/model.tex
+++ b/paper/sections/model.tex
@@ -1,65 +1,55 @@
-We consider a graph ${\cal G}= (V, E, \Theta)$, where $\Theta$ is a $|V|\times
-|V|$ matrix of paremeters describing the edge weights of $\mathcal{G}$. We
-define $m\defeq |V|$. A \emph{cascade model} is a Markov process over the
-finite state space $\{0, 1, \dots, K\}^V$. An \emph{influence cascade} is
-a realisation of the random process described by a cascade model.
+We consider a graph ${\cal G}= (V, E, \Theta)$, where $\Theta$ is a $|V|\times |V|$ matrix of parameters describing the edge weights of $\mathcal{G}$. Let $m\defeq |V|$. For each node $j$, let $\Theta_{j}$ be the $j^{th}$ column vector of $\Theta$. Intuitively, $\Theta_{i,j}$ captures the ``influence'' of node $i$ on node $j$. A \emph{Cascade model} is a Markov process over a finite state space $\{0, 1, \dots, K-1\}^V$ with the following properties:
+\begin{enumerate}
+\item Conditioned on the previous time step, the transition probabilities for each node $i \in V$ are mutually independent.
+\item Of the $K$ possible states, there exists a \emph{contagious state} such that all transition probabilities of the Markov process can be expressed as a function of the graph parameters $\Theta$ and the set of ``contagious nodes'' at the previous time step.
+\item The initial probability over $\{0, 1, \dots, K-1\}^V$ of the Cascade Model is such that all nodes can eventually reach a \emph{contagious state} with non-zero probability. The ``contagious'' nodes at $t=0$ are called \emph{source nodes}.
+\end{enumerate}
 
-In practice, we restrict ourselves to discrete-time homogeneous cascade models.
-At $t=0$, each node in the graph has a constant probability $p_{init}$ of being
-in the ``active state''. The active nodes at $t=0$ are called the source nodes.
-Our probabilistic model for the source nodes is more realistic and less
-restrictive than the ``single source'' assumption made in \cite{Daneshmand:2014}
-and \cite{Abrahao:13}.
+In other words, a cascade model describes a diffusion process, whereby a set of contagious nodes ``influence'' other nodes in the graph to adopt or not their behavior. An \emph{influence cascade} is a realisation of this random process: the successive states of the nodes in graph ${\cal G}$. Note that both the ``single source'' assumption made in \cite{Daneshmand:2014} and \cite{Abrahao:13} as well as the ``uniformly chosen source set'' assumption made in \cite{Netrapalli:2012} verify condition 3.
 
+In the context of Graph Inference, \cite{Netrapalli:2012} focuses specifically on the well-known discrete-time independent cascade model recalled below, which \cite{Abrahao:13} and \cite{Daneshmand:2014} generalize to continuous time. Whilst we restrict ourselves to discrete-time processes, we consider both the independent cascade model and the linear voter model, and show they can be solved by a very similar maximum-likelihood program. The linear threshold model is a special case and is discussed in Section~\ref{sec:linear_threshold}.
 
-\subsection{Generalized Linear Cascade Models}
-
-Denoting by $X^t$ the state of the cascade at time step $t$, we interpret
-$X^t_j = 1$ for node $j\in V$ as ``node $j$ is active'', \emph{i.e}, ``$j$
-exhibits the source nodes' behavior at time step $t$''.  We draw inspiration
-from \emph{generalized linear models} (GLM) to define a generalized linear
-cascade.
+% Denoting by $X^t$ the state of the cascade at time step $t$, we interpret
+% $X^t_j = 1$ for node $j\in V$ as ``node $j$ is contagious'', \emph{i.e}, ``$j$
+% exhibits the source nodes' behavior at time step $t$''.  We draw inspiration
+% from \emph{generalized linear models} (GLM) to define a generalized linear
+% cascade.
 
-\begin{definition}
-    \label{def:glcm} 
-    Let us denote by $\{\mathcal{F}_t, t\in\ints\}$ the natural
-    filtration induced by $\{X_t, t\in\ints\}$. A \emph{generalized linear
-    cascade} is characterized by the following equation:
-    \begin{displaymath}
-        \P[X^{t+1}=x\,|\, \mathcal{F}_t] =
-        \prod_{i=1}^m f(\inprod{\theta_i}{X^{t}})^{x_i}
-        \big(1-f(\inprod{\theta_i}{X^{t}}\big)^{1-x_i}
-    \end{displaymath}
-where $f:\mathbb{R}\to[0,1]$ and $\theta_i$ is the $i$-th column of $\Theta$.
-\end{definition}
+% \begin{definition}
+%     \label{def:glcm} 
+%     Let us denote by $\{\mathcal{F}_t, t\in\ints\}$ the natural
+%     filtration induced by $\{X_t, t\in\ints\}$. A \emph{generalized linear
+%     cascade} is characterized by the following equation:
+%     \begin{displaymath}
+%         \P[X^{t+1}=x\,|\, \mathcal{F}_t] =
+%         \prod_{i=1}^m f(\inprod{\theta_i}{X^{t}})^{x_i}
+%         \big(1-f(\inprod{\theta_i}{X^{t}}\big)^{1-x_i}
+%     \end{displaymath}
+% where $f:\mathbb{R}\to[0,1]$ and $\theta_i$ is the $i$-th column of $\Theta$.
+% \end{definition}
 
-It follows immediately from this definition that a generalized linear cascade
-satisfies the Markov property:
-\begin{displaymath}
-    \P[X^{t+1}=x\,|\mathcal{F}_t] = \P[X^{t+1}=x\,|\, X^t]
-\end{displaymath}
-Note also that $\E[X^{t+1}_i\,|\,X^t] = f(\inprod{\theta_i}{X^t})$. As such,
-$f$ can be interpreted as the inverse link function of our generalized linear
-cascade model.
+% It follows immediately from this definition that a generalized linear cascade
+% satisfies the Markov property:
+% \begin{displaymath}
+%     \P[X^{t+1}=x\,|\mathcal{F}_t] = \P[X^{t+1}=x\,|\, X^t]
+% \end{displaymath}
+% Note also that $\E[X^{t+1}_i\,|\,X^t] = f(\inprod{\theta_i}{X^t})$. As such,
+% $f$ can be interpreted as the inverse link function of our generalized linear
+% cascade model.
 
-\subsection{Examples}
-\label{subsec:examples}
+\subsection{Independent Cascade Model}
 
-In this section, we show that the well-known Independent Cascade Model and the Voter model are Generalized Linear Cascades. The Linear Threshold model will be discussed in Section~\ref{sec:linear_threshold}.
-
-\subsubsection{Independent Cascade Model}
-
-In the independent cascade model, nodes can be either susceptible, active or
-inactive. At $t=0$, all source nodes are ``active'' and all remaining nodes are
+In the independent cascade model, nodes can be either susceptible, contagious or
+immune. At $t=0$, all source nodes are ``contagious'' and all remaining nodes are
 ``susceptible''. At each time step $t$, for each edge $(i,j)$ where $j$ is
-susceptible and $i$ is active, $i$ attempts to infect $j$ with probability
+susceptible and $i$ is contagious, $i$ attempts to infect $j$ with probability
 $p_{i,j}\in[0,1]$, the infection attempts are independent of each other. If $i$
-succeeds, $j$ will become active at time step $t+1$. Regardless of $i$'s
-success, node $i$ will be inactive at time $t+1$. In other words, nodes stay
-active for only one time step. The cascade process terminates when no active
+succeeds, $j$ will become contagious at time step $t+1$. Regardless of $i$'s
+success, node $i$ will be immune at time $t+1$. In other words, nodes stay
+contagious for only one time step. The cascade process terminates when no contagious
 nodes remain.
 
-If we denote by $X^t$ the indicator variable of the set of active nodes at time
+If we denote by $X^t$ the indicator variable of the set of contagious nodes at time
 step $t$, then if $j$ is susceptible at time step $t+1$, we have:
 \begin{displaymath}
     \P\big[X^{t+1}_j = 1\,|\, X^{t}\big]
@@ -72,24 +62,57 @@ Defining $\Theta_{i,j} \defeq \log(1-p_{i,j})$, this can be rewritten as:
     = 1 - \prod_{i = 1}^m e^{\Theta_{i,j}X^t_i}
     = 1 - e^{\inprod{\theta_j}{X^t}}
 \end{equation}
-which is a Generalized Linear Cascade model with inverse link function $f(z)
-= 1 - e^z$.
 
-\subsubsection{The Voter Model}
+\subsection{The Linear Voter Model}
 
-In the Voter Model, nodes can be either red or blue, where ``blue'' is the
-source state. The parameters of the graph are normalized such that $\forall i,
+In the Linear Voter Model, nodes can be either \emph{red} or \emph{blue}. Both states verify the properties of a contagious state, but for ease of presentation, we will suppose that the contagious nodes are the \emph{blue}. The parameters of the graph are normalized such that $\forall i,
 \ \sum_j \Theta_{i,j} = 1$. Each round, every node $j$ independently chooses
-one of its neighbors with probability $\Theta_ij$ and adopts their color. The
+one of its neighbors with probability $\Theta_{ij}$ and adopts their color. The
 cascades stops at a fixed horizon time T or if all nodes are of the same color.
 If we denote by $X^t$ the indicator variable of the set of blue nodes at time
 step $t$, then we have:
 \begin{equation}
-\mathbb{P}\left[X^{t+1}_j = 1 | X^t \right] = \sum_{i=1}^m \Theta_{i,j} X_i^t = \inprod{\theta_j}{X^t}
+\mathbb{P}\left[X^{t+1}_j = 1 | X^t \right] = \sum_{i=1}^m \Theta_{i,j} X_i^t = \inprod{\Theta_j}{X^t}
 \tag{V}
 \end{equation}
-which is a Generalized Linear Cascade model with inverse link function
-$f(z) = z$.
+
+% \subsection{The Linear Threshold Model}
+
+% In the Linear Threshold Model, each node $j\in V$ has a threshold $t_j$ from the interval $[0,1]$ and for each node, the sum of incoming weights is less than $1$: $\forall j\in V$, $\sum_{i=1}^m \Theta_{i,j} \leq 1$. 
+
+% Nodes have two states: susceptible or contagious. At each time step, each susceptible
+% node $j$ becomes contagious if the sum of the incoming weights from contagious parents is greater than $j$'s threshold $t_j$. Nodes remain contagious until the end of the cascade, which is reached when no new susceptible nodes become contagious.
+
+% As such, the source nodes are chosen, the process is entirely deterministic. Let $X^t$ be the indicator variable of the set of contagious nodes at time step $t-1$, then:
+% \begin{equation}
+% \nonumber
+%     X^{t+1}_j = \mathbbm{1}_{\sum_{i=1}^m \Theta_{i,j}X^t_i > t_j}
+%     = \mathbbm{1}_{\inprod{\theta_j}{X^t} > t_j}
+% \end{equation}
+% where we defined again $\theta_j\defeq (\Theta_{1,j},\ldots,\Theta_{m,j})$. In other words, for every step in the linear threshold model, we observe the following signal:
+
+% \begin{equation}
+%     \label{eq:lt}
+%     \tag{LT}
+%     \mathbb{P} \left[X^{t+1}_j = 1 | X^t\right] = \text{sign} \left(\inprod{\theta_j}{X^t} - t_j \right)
+% \end{equation}
+% where ``sign'' is the function $\mathbbm{1}_{\cdot > 0}$.
+
+\subsection{Generalized Linear Cascade Models}
+\label{sec:GLC}
+
+Despite their obvious differences, both models share a common similarity: conditioned on node $j$ being susceptible at time step $t$, the probability that node $j$ becomes infected at time step $t+1$ is a bernoulli of parameter $f(\Theta_j \cdot X^t)$, where $f:\mathbb{R} \rightarrow [0,1]$. In the case of the voter model, $f_{\text{V}}$ is the identify function, and in the case of the independent cascade model $f_{\text{ICC}} : z \rightarrow 1 - e^z$. We draw inspiration from generalized linear models to introduce \emph{Generalized Linear Cascades}:
+
+\begin{definition}
+\label{def:glcm}
+Let us denote by $\{\mathcal{F}_t, t\in\ints\}$ the natural filtration induced by the state of ${\cal G}$ up to time step t. A \emph{generalized linear cascade} is a cascade model characterized by the following equation:
+\begin{displaymath}
+    \P[X^{t+1}=x\,|\, \mathcal{F}_t] =
+    \prod_{i=1}^m f_{X^t_i,x_i}(\Theta_i \cdot X^t)
+\end{displaymath}
+where $f_{s,p}:\mathbb{R}\to[0,1]$ for each state pair $(s,p) \in \{0, \dots, K-1 \}$
+\end{definition}
+
 
 \subsection{Maximum Likelihood Estimation}
 
@@ -124,7 +147,7 @@ $\Theta$ can be estimated by a separate optimization program:
     \hat{\theta}_i \in \argmax_{\theta}\frac{1}{n_i}\mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n)
     + \lambda\|\theta_i\|_1
 \end{equation}
-where we denote by $n_i$ the first step at which node $i$ becomes active and
+where we denote by $n_i$ the first step at which node $i$ becomes contagious and
 where:
 \begin{multline}
     \mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n) = \frac{1}{n_i}