path: root/ic_theory/main.tex

\documentclass[10pt]{article}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[english]{babel}
\usepackage[capitalize, noabbrev]{cleveref}
\usepackage{algorithm}
\usepackage{algpseudocode}

\newenvironment{enumerate*}%
  {\vspace{-2ex} \begin{enumerate} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{enumerate}}
 
\newenvironment{itemize*}%
  {\vspace{-2ex} \begin{itemize} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{itemize}}
 
\newenvironment{description*}%
  {\vspace{-2ex} \begin{description} %
     \setlength{\itemsep}{-1ex} \setlength{\parsep}{0pt}}%
  {\end{description}}

\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{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
\newcommand{\llbracket}{[\![}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\algrenewcommand\algorithmicensure{\textbf{Output:}}
\algrenewcommand\algorithmicrequire{\textbf{Input:}}
\DeclareMathOperator*{\argmax}{arg\,max}

\author{}
\title{}
\date{}

\begin{document}

\section{Probabilistic Model}
During the last decade, a growing body of work has focused on the graph
inference problem: how can an unknown graph be recovered from the observation
of cascades propagating along it? (CITE). While our probabilistic model for
cascades of violence strongly relies on this line of work, we depart from it in
the following ways:
\begin{itemize}
    \item in our case, the graph along which the cascades of violence propagate
        (the co-offending network) is known, and we are only interested in
        recovering (and ultimately predicting) the edges of the cascade, that
        is, identifying who influenced whom.
    \item the previous models treat multiple cascades as independent
        observations which occur sequentially. In our case, cascades can die
        and spawn at all time and temporally overlap. This need to be carefully
        accounted for in our generative model and the resulting inference
        algorithms.
\end{itemize}

\subsection{Pairwise Propagation}
\label{sec:edge}

For a pair $(u,v)$ of nodes, we model the propagation of the cascade
from $u$ to $v$ as the sequence of the following two probabilistic events:
\begin{enumerate}

    \item \emph{structural propagation:} a Bernouilli variable dictates whether
        or not a propagation occurs. The parameter of this Bernouilli variable
        is computed from the edge weights of the co-offending network as
        follows:
        \begin{equation}\label{eq:structural}
            p_{u,v}^s \eqdef \prod_{e\in P(u,v)}
            \frac{1}{1+e^{-\frac{w_e}{\lambda}}}
        \end{equation}
        where $P(u,v)$ denotes the shortest path from $u$ to $v$ and $\lambda$
        is the \emph{structural parameter}. That is, the weight $w_e$ of each
        edge $e$ on the  path from $u$ to $v$ is mapped to a probability
        $p_e\in [0,1]$ through the logistic function:
        \begin{displaymath}
            p_e \eqdef \frac{1}{1+e^{-\frac{w_e}{\lambda}}}
        \end{displaymath}
        Note that the probability of structural propagation both \emph{(a)}
        decreases as the distance between $u$ and $v$ in the co-offending
        network increases, and \emph{(b)} increases as the weights of the edges
        on the path from $u$ to $v$ increase. The structural parameter
        $\lambda$ controls how quickly the probability $p_e$ of a given edge
        converges to one as the weight $w_e$ increases.

    \item \emph{temporal propagation:} if the structural propagation occurs,
        then the propagation time $\Delta_{u,v}$ between $u$ and $v$ is drawn
        from a continuous distribution with support in $\R_+$. We denote by
        $f(t)$ the density function of this probability distribution and by
        $F(t)$ its cumulative function. Table TODO gives the expression of $f$
        and $F$ for the different temporal distributions considered in this
        work.

        In our data, the infection times are only observed with a temporal
        resolution of one day. As a consequence, for two nodes $u$ and $v$
        whose \emph{observed} infection times are respectively $t_u$ and $t_v$
        (days), the \emph{real} propagation time could be anything in the
    interval $(t_v-t_u-1, t_v-t_u]$. Hence, the probability of observing
    a propagation time $\Delta_{u,v} = t_v - t_u$ is given by:
    \begin{equation}\label{eq:temporal}
        p_{u,v}^t(\Delta_{u,v}) \eqdef \int_{\Delta_{u,v}-1}^{\Delta_{u,v}} f(t)dt
    \end{equation}
\end{enumerate}

\paragraph{Successful propagation.} For two nodes $u$ and $v$ with observed
infection times $t_u$ and $t_v$, the probability $p_{u,v}$ that $u$ infected
$v$ is obtained by multiplying the structural and temporal probabilities given
by \eqref{eq:structural} and \eqref{eq:temporal}:
\begin{displaymath}
    p_{u,v}(t_u, t_v)  \eqdef p_{u,v}^s\cdot p_{u,v}^t(\Delta_{u,v})
\end{displaymath}

\subsection{Failed Propagations and Spawning of New Cascades}
\label{sec:roots}

\paragraph{Failed propagation.}
When an edge fails to propagate the violence cascade, it could be either
because the structural propagation did not occur, or because the structural
propagation occurred, but the temporal propagation didn't occur in time.

For an edge $(u,v)$ with infection times $t_u$ and $t_v$, it follows directly
from Section~\ref{sec:edge} that structural propagation does not occur with
probability $1-p_{u,v}^s$.

If structural propagation occurs, but temporal propagation does not occur in
time, it means that node $v$ was infected at time $t_v$ (through other means)
\emph{before} $u$ succeeds in infecting $v$. That is, the propagation time was
larger than $\Delta_{u,v}$. This occurs with probability:
\begin{displaymath}
    \int_{\Delta_{u,v}}^{+\infty} f(t)dt = 1-F(\Delta_{u,v})
\end{displaymath}

Overall, the probability of a failed propagation over an edge $(u,v)$ is given
by:
\begin{displaymath}
    \tilde{p}_{u,v}(t_u, t_v)
    \eqdef 1 - p_{u,v}^s + p_{u,v}^s\left(1-F(\Delta_{u,v})\right)
    = 1 - p_{u,v}^s F(\Delta_{u,v})
\end{displaymath}

\paragraph{}For an edge $(u,v)$ where $u$ is a victim node and $v$ is a not
a victim, the situation is similar: either the structural propagation failed,
or it succeeded but the temporal propagation did not occur in time. In the
latter case, since we did not observe an infection at all for $v$, this means
that the propagation time between $u$ and $v$ was such that the infection time
of $v$ would have fallen after the end of the study period. Denoting by $T$ the
observation horizon (the end of the study period), the probability of a failed
propagation for an edge $(u,v)$ where $v$ is not a victim is:
\begin{displaymath}
    \tilde{p}_{u,v}(t_u, T) \eqdef 1-p_{u,v}^s F(T-t_u)
\end{displaymath}

\paragraph{Spawning of New Cascades.}

Our probabilistic model considers another cause of infection for victim nodes:
beyond pairwise propagation of the violence cascade, nodes can also
spontaneously become infected and spawn a new violence cascade. We simply model
this by a Bernouilli variable of parameter $\beta$: for any node, the
probability that it becomes infected spontaneously is $\beta$.

\subsection{The Directed Acyclic Vector of Infection}
\label{sec:dag}

Given a vector of infection times denoted by $\textbf{t}$, it follows from
Sections~\ref{sec:edge} and \ref{sec:roots} that \emph{(1)} no infection can
occur between two non victim nodes, \emph{(2)} no infection can occur along an
edge $(u,v)$ where $t_u > t_v$.

This suggests to orient and trim the co-offending network $G$ to construct the
following directed graph $D_{\mathbf{t}}$ by applying the following rules:
\begin{enumerate}
    \item remove edges between non-victim nodes.
    \item orient edges from victim nodes to non-victim nodes.
    \item for any edge $(u,v)$ between two victims, orient it in the direction
        from smallest infection time to largest infection time.
\end{enumerate}

The resulting graph $D_{\mathbf{t}}$ only contains edges along with the
propagation of violence can possibly occur. Furthermore the edges are oriented
in the direction of propagation.

It has been observed in (CITE) that $D$ is acyclic. For completeness we
reproduce their proof here and adapt it to account for non-victim nodes (which
do not exist in the original paper).

\begin{theorem}
    The graph $D_{\mathbf{t}}$ obtained from $G$ by applying rules 1. to 3. is
    acyclic.
\end{theorem}

\begin{proof}
    Assume by contradiction that $D$ contains a cycle $(u_1,\ldots, u_n)$ where
    $(u_1, u_2),\dots,(u_{n-1}, u_n), (u_n, u_1)$ are edges of $D$. Because of
    rule 1., all nodes $u_1,\dots, u_n$ are victim nodes.

    Applying rule 3. to all edges in the cycle implies that
    $t_1<t_2<\dots<t_n<t_1$. The two extremal terms of this chain of
    inequalities implie $t_1<t_1$ which is a contradiction.
\end{proof}

\subsection{Cascade Model}

Using Sections~\ref{sec:edge} to \ref{sec:dag}, we can now fully specify our
cascade model.

The violence propagation proceeds as follows: every time a node becomes
infected, it attempts to infect all its neighbors which are not infected yet
according to the pairwise model of Section~\ref{sec:edge}. In other words, at
a given time, a node is subjected to the ongoing infection attempts of all its
neighbors which have been infected in the past. Because of the temporal
component of the pairwise propagation probabilities, these attempts will
succeed at different times. The infection is attributed to the first neighbor
who succeeds.Furthermore, all the infection attempts are independent from each
other.  

\paragraph{Example.} Let us consider a node $v$ with $n$ neighbors $u_1,\dots,
u_n$. For simplicity, let us assume that the structural propagation
probabilities are the same and equal to one for all edges $(u_i, v)$. We also
assume that all neighbors of $v$ were infected at time $0$ and we use the
exponential temporal model with parameter $\alpha$. Then, the probability that
$v$ is infected at time larger than $t$ is given by:
\begin{displaymath}
    p_v(t) \eqdef \P\left[\min_{1\leq i\leq n} Z_i \geq t\right]
    = e^{-n\alpha t}
\end{displaymath}
where $Z_i$ is an exponential variable of parameter $\alpha$ and where we used
that the law of the minimum of exponential variables is also exponential with
parameter equal to the sum of the individual variables' parameters.

This example shows that the larger the neighborhood the more likely it is that
a node will be infected quickly. The parameter $\alpha n$ of the resulting
exponential variable captures the aggregated infection potential of the
neighborhood.

\paragraph{} Since the infection of a node $v$ is always attributed to the
first neighbor which succeeds in infecting it, a victim node
can have either one parent (when it is infected by it) or no parent (when it
spawns a cascade spontaneously). Because the graph $D$ along which the cascades
of violence occur is acyclic, it follows that the violence propagates along $D$
by forming trees.

Formally, if we denote by $(V, E)$ the vertices and edges of $D$, and we write
$V = R\cup T$ where $R$ are the victim nodes and $T$ the non-victim nodes
($R\cap T=\emptyset$), then \emph{the violence cascades form a random forest
spanning $R$ in $D$}.

\paragraph{Likelihood.} Given pairwise parameters $(\alpha, \lambda, \beta)$
and a random forest $\mathcal{T} = (T_1,\ldots, T_r)$, we can compute the
probability of observing the infection times given by the vector $\textbf{t}$:
\begin{equation}
    \label{eq:model}
    \P[\mathbf{t}, \mathcal{T}\,|\, \beta, \alpha, \lambda]
    = \beta^r(1-\beta)^{n-r}\prod_{e\in E_{\mathcal{T}}} p_e
    \prod_{e\in E_{D_{\mathcal{\mathbf{t}}}}\setminus E_{\mathcal{T}}}
    \tilde{p}_e
\end{equation}
where $E_{\mathcal{T}}$ denotes the edge set of the forest $\mathcal{T}$ and
$E_{D_{\mathbf{t}}}$ denotes the edge set of the DAG $D_{\mathbf{t}}$ defined
in Section~\ref{sec:dag}.

\section{Maximum Likelihood Inference}

The probabilistic model \eqref{eq:model} defines the joint probability of
a pair $\mathbf{t}, \mathcal{T}$ of infection times and cascades. However, we
are interested in situations where only the infection times are observed.

A direct application of maximum likelihood estimation would recover the
parameters $\beta, \alpha$ and $\lambda$ by solving the following optimization
program:
\begin{displaymath}
    \max_{\alpha,\beta,\lambda}\sum_{\mathcal{T}}
    \P[\mathbf{t}, \mathcal{T}\,|\, \beta, \alpha, \lambda]
\end{displaymath}
However, since we are also interested in recovering the infection edges, we
solve the following optimization program instead:
\begin{equation}
    \label{eq:program}
    \mathcal{T}^*, \beta^*, \alpha^*, \lambda^* \in
    \argmax_{\mathcal{T},\beta,\alpha,\lambda}
    \P[\mathbf{t}, \mathcal{T}\,|\, \beta, \alpha, \lambda]
\end{equation}
When solving this optimization program, the optimal forest $\mathcal{T}^*$ will
indicate the most likely edges along which the infection could have propagated,
while $\beta$, $\alpha$ and $\lambda$ will give us information about the
temporal and structural scale of pairwise infection.

\subsection{Finding the Cascades}

We first assume that $\beta$, $\alpha$ and $\lambda$ are fixed and solve
\eqref{eq:program} for $\mathcal{T}$:
\begin{equation}\label{eq:program2}
    \mathcal{T}^*\in\argmax_{\mathcal{T}}
    \beta^r(1-\beta)^{n-r}\prod_{e\in E_{\mathcal{T}}} p_e
    \prod_{e\in E_{D_{\mathcal{\mathbf{t}}}}\setminus E_{\mathcal{T}}}
    \tilde{p}_e
\end{equation}
Note that the solution $\mathcal{T}^*$ depends on the value of $(\beta, \alpha,
\lambda)$. We will then optimize over these parameters in the following
sections.

By multiplying and dividing each term by $\tilde{p}_e$ in the first product, we
can rewrite the objective function:
\begin{displaymath}
    \mathcal{T}^*\in\argmax_{\mathcal{T}}
    \left(\frac{\beta}{1-\beta}\right)^r(1-\beta)^n
    \prod_{e\in E_{\mathcal{T}}} \frac{p_e}{\tilde{p}_e}
    \prod_{e\in E_{D_{\mathcal{\mathbf{t}}}}} \tilde{p}_e
\end{displaymath}
Note that now, the last product, as well as the $(1-\beta)^n$ do not depend on
the choice of $\mathcal{T}$ and can be dropped without changing the
optimization program. Then, by taking the $\log$, we obtain the following
equivalent optimization program:
\begin{displaymath}
    \mathcal{T}^*\in\argmax_{\mathcal{T}}\; r\log\frac{\beta}{1-\beta}
    +\sum_{e\in E_{\mathcal{T}}} \log\frac{p_e}{\tilde{p}_e}
\end{displaymath}

As mentioned in Section XXX, $\mathcal{T}$ is a random forest spawning $R$, the
set of victim nodes, in $D_{\mathbf{t}}$. So choosing $\mathcal{T}$ amounts to
choosing for each node in $R$:
\begin{itemize}
    \item either to make it the root of a new tree, in which case it will
        contribute a term $\log\frac{\beta}{1-\beta}$ to the objective
        function.
    \item either to make it part of an existing tree, by including one of its
        incoming edge $e$ in the edge set $E_{\mathcal{T}}$. In this case, the
        node contributes a term $\log\frac{p_e}{\tilde{p}_e}$ to the objective
        function.
\end{itemize}

Since our goal is to solve \eqref{eq:program2}, in the second case, it is
sufficient to consider the incoming edge which maximizes the quantity
$\frac{p_e}{\tilde{p}_e}$. For this edge $e$, deciding between the two cases
then amounts to comparing $\frac{p_e}{\tilde{p}_e}$ to $\frac{\beta}{1-\beta}$.
This leads to a simple thresholding algorithm for solving \eqref{eq:program2}. 

\begin{algorithm}
    \caption{Thresholding algorithm for cascade recovery}
    \begin{algorithmic}[1]
    \Require graph $G$, infection times $\mathbf{t}$, $\alpha$, $\beta$, $\lambda$
    \Ensure cascades $\mathcal{T}$
    \State $D_{\mathbf{t}}\gets$ acyclic graph obtained by trimming $G$
    \State $R\gets\{u\in G: t_u < \infty\}$
    \State $E\gets\emptyset$
    \For{$v\in R$}
    \State $u\gets\argmax\left\{\frac{p_{u,v}}{\tilde{p}_{u,v}}: (u,v)\in
    D_t\right\}$
    \If{$\frac{p_{u,v}}{\tilde{p}_{u,v}}\geq \frac{\beta}{1-\beta}$}
    \State $E\gets E\cup \{(u,v)\}$
    \EndIf
    \EndFor
    \State \textbf{return} $\mathcal{T} = (R, E)$
    \end{algorithmic}
\end{algorithm}

\subsection{Finding the Spawning Parameter}

In this section, we consider the value of $\alpha$ and $\lambda$ fixed and try
to optimize \eqref{eq:program} jointly over $\mathcal{T}$ and $\beta$.

For a node $v\in R$, let us define:
\begin{displaymath}
    q_v \eqdef \max\left\{\frac{p_{u,v}}{\tilde{p}_{u,v}}:(u,v)\in E_{\mathbf{t}}\right\}
\end{displaymath}
and denote by $E_{\beta}$ the set:
\begin{displaymath}
    R_{\beta} \eqdef \left\{v\in R:q_v\geq \frac{\beta}{1-\beta}\right\}
\end{displaymath}
Then it follows from the analysis of Section XXX, that for a fixed value of
$\beta$, the optimal value of \eqref{eq:program} when optimizing over
$\mathcal{T}$ is given by:
\begin{displaymath}
    f(\beta) = (|R|-|R_\beta|)\log\frac{\beta}{1-\beta}
    + n\log(1-\beta)+ \sum_{v\in R_\beta} \log q_v
\end{displaymath}
Hence our goal is to find the maximum of $f(\beta)$ over the interval $(0,1)$.
Note that the maximum exists since $f$ diverges to $-\infty$ as $\beta$
approaches $0$ or $1$. Furthermore $f$ is continuous over $(0,1)$ since we can
rewrite it:
\begin{displaymath}
    f(\beta) = n\log(1-\beta) + \sum_{v\in R}
    \log\max\left\{\frac{\beta}{1-\beta}, q_v\right\}
\end{displaymath}

\subsection{Finding the Pairwise Propagation Parameters}

\end{document}