\documentclass[10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath, amssymb, amsthm, microtype}
\usepackage[pagebackref=false,breaklinks=true,colorlinks=true,citecolor=blue]{hyperref}
\usepackage[capitalize, noabbrev]{cleveref}
\usepackage{graphicx}
\usepackage{bbm}

\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator{\E}{\mathbb{E}}
\let\P\relax
\DeclareMathOperator{\P}{\mathbb{P}}
\newcommand{\ex}[1]{\E\left[#1\right]}
\newcommand{\prob}[1]{\P\left[#1\right]}
\newcommand{\inprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\R}{\mathbf{R}}
\newcommand{\N}{\mathbf{N}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\eps}{\varepsilon}
\newcommand{\bt}{\boldsymbol{\theta}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\cl}[1]{\text{\textbf{#1}}}
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem*{example}{Example}
\newtheorem*{remark}{Remark}

\title{Regression Analysis with Network Data}
\author{Thibaut Horel \and Jean Pouget-Abadie}

\begin{document}

\maketitle

\begin{abstract}

\end{abstract}

\section{Introduction}

Central question: \emph{relating properties of the graph to the difficulty of
doing graph inference from cascades.}

Two subquestions:
\begin{itemize}
    \item which properties of the graph make it impossible or hard to learn
        (identifiability, convergence rate)?
    \item which properties of the graph can be exploited to learn better or
        faster (use a Bayesian prior)?
\end{itemize}

\section{Model}

Weighted directed graph $G = (V, \Theta)$. $k=|V|$ is the number of nodes.
$\Theta\in\R_{+}^{k\times k}$. $\Theta$ implicitly defines the edge set $E$ of
the graph.

Discrete time model, $t\in\N$.  Nodes can be in one of two states:
\emph{susceptible}, \emph{infected} or \emph{immune}.  $S_t:$ nodes susceptible
at the beginning of time step $t\in\N$.  $I_t$ nodes infected at time step $t$.
\begin{displaymath}
    S_0 = V,\quad S_{t+1} = S_t \setminus I_t
\end{displaymath}
Nodes which are no longer susceptible are immune.

The dynamics of $I_t$ is described by a random Markovian process. Let us denote
by $x_t$ the indicator vector of $I_t$ at time step $t\in\N$. $x_0$ is drawn
from the \emph{source distribution} $p_s:\{0,1\}^n\to[0,1]$. For $t\geq 1$,
Markovian process:
\begin{equation}
    \label{eq:markov}
    \forall i\in S_t,\quad
    \P\big(x_{i}^{t} = 1\,|\, x^{t-1}\big) = f(\bt_i\cdot x^{t-1})
\end{equation}
$\bt_i$ is the $i$th column of $\Theta$, $f:\R\to[0,1]$, plus independence for
$i$. A cascade continues until no more infected nodes. 


\section{Identifiability}

A given source distribution $p_s$ and \cref{eq:markov} completely specifies the
distribution $p$ of a cascade $\mathbf{x} = (x_t)_{t\geq 0}$:
\begin{displaymath}
    p(\bx;\Theta) = p_s(x^0)\prod_{t\geq 1}\prod_{i\in S_t}
    f(\bt_i\cdot x^{t-1})^{x^t_i}\big(1-f(\theta_i\cdot x^{t-1})\big)^{1-x_i^t}
\end{displaymath}

We see this model as parametrized by $\Theta$. $f$ and $p_s$ are considered
fixed.

\begin{definition}
    We say that the model $\mathcal{P}
    = \big\{p(\cdot\,;\,\Theta)\,|\,\Theta\in\R_+^{k\times k}\big\}$ is
    identifiable iff:
    \begin{displaymath}
        \forall \Theta,\Theta'\in\R_+^{k\times k},\quad
        p(\cdot\,;\,\Theta) = p(\cdot\, ;\, \Theta') \Rightarrow \Theta = \Theta'
    \end{displaymath}
\end{definition}

In our case, identifiability is not guaranteed. In fact there are two factors
which can lead to unidentifiability: lack of information or ambiguity. We
illustrate both factors in the subsequent two examples.

\begin{figure}
\begin{center}
    \includegraphics[scale=0.8]{example.pdf}
\end{center}
\caption{Example of a graph which can be unidentifiable, both because of lack
    of information or parent ambiguity if the source distribution is chosen
adversarially.}
\label{fig:ident}
\end{figure}

\vspace{.5em}

\begin{example}[Lack of information]
    Let us consider the graph in \cref{fig:ident} and the source distribution
    $p_s$ defined by $p_s\big((0, 1, 0)\big) = 1$. In other words, node $2$ is
    always the only infected node at $t=0$. Then it is clear that all
    casacades die at $t=1$ at which node 3 becomes infected with probability
    $f(\theta_{2,3})$. This probability does not depend on $\theta_{1,3}$.
    Hence all matrices $\Theta$ compatible with the graph and for which
    $\theta_{2,3}$ is fixed yield the same cascade distribution.
\end{example}

\vspace{.5em}

\begin{example}[Parent ambiguity]
Let us consider again the graph in \cref{fig:ident} and let us consider the
case where the source distribution is such that $p_s\big((1,1,0)\big) = 1$,
\emph{i.e} nodes 1 and 2 are always jointly infected at time $t=0$. Then it is
clear that cascades will all die at time $t=1$ where node 3 becomes infected
with probability $f(\theta_{1,3} + \theta_{2,3})$. This implies that all
matrices $\Theta$ which are compatible with the graph in \cref{fig:ident}
(defining the same edge set) and for which $\theta_{1,3} + \theta_{2,3} = c$
for some $c\in \R_+$ define the same cascade probability distribution.
\end{example}

\vspace{.5em}

The examples show that for a model to be identifiable, we need conditions on
the source distribution, in particular in relation to how well it plays with
the reachability structure of the graph.

We will abuse the notation $p_s$ and for $u\in V$ write:
\begin{displaymath}
    p_s(w) \eqdef \sum_{\bx: \bx_w = 1} p_s(\bx)
\end{displaymath}
Furthermore we write $u\leadsto v$ if there is a directed path from $u$ to $v$
in $G$ and $u\leadsto v\leadsto w$ if there is a directed path from $u$ to $w$
passing through $v$ in $G$.

\begin{proposition}
Under the assumptions:
\begin{enumerate}
    \item $\forall z\in \mathbf{\R_+},\; f(z)< 1$
    \item for all $S\subseteq V$ with $|S|\geq 2$, $p_s(S)<1$.
    \item $\forall (u,v)\in V^2$, there exists $w$ such that $p_s(w)\neq 0$ and
        $w\leadsto u\leadsto v$.
\end{enumerate}
then the model is identifiable.
\end{proposition}

2. prevents parent ambiguity at the source. 1. prevents parent ambiguity from
   occurring later on in the cascade even when there is no ambiguity at the
   source (could be relaxed to ``absence of forks''). 3. prevents lack of
   information.

\begin{proof}

\end{proof}

\begin{remark} The conditions are the weakest under which there is
    identifiability (we can show that they are necessary and sufficient).
    Reasonable source distributions which imply the conditions are uniform
    random, independent Bernouilli.
\end{remark}

\section{Inference}

\subsection{Maximum-Likelihood Estimation}

Because transitions occur independently for each node $i$, the log-likelihood
is a sum of $k$ terms, each term $i$ only depending on $\bt_i$. Hence, each
$\bt_i$ can be learnt separately by solving a node-specific optimization
problem:

We assume $f$ log-concave to have a concave optimization problem. Depending on
the model, $\theta_{i,j}$ can either be restricted to live in a compact subset
of $\R_+$. Otherwise, we need to assume that $\lim_{z\to\infty} f(z) = 1$.
Then, we can apply standard results on consistency and asymptotic normality of
MLE estimator.

\subsection{Bayesian Approach}


\end{document}
