Updating poster

1 files changed, 125 insertions, 114 deletions

diff --git a/notes/cracking_cascades_classposter.tex b/notes/cracking_cascades_classposter.tex
index 2b29109..52fd78d 100644
--- a/notes/cracking_cascades_classposter.tex
+++ b/notes/cracking_cascades_classposter.tex
@@ -75,25 +75,30 @@
 
 %\vspace{4.6 cm}
 
-\begin{block}{Introduction}
+\begin{block}{Problem Statement}
+\begin{center}
+\bf{How can we reconstruct a graph on which observed cascades spread?}
+\end{center} 
+\end{block}
 
-{\bf Graph Reconstruction}:
 
-\begin{itemize}
-\item \{${\cal G}, \vec p$\}: directed graph, edge probabilities
-\item $F$: cascade generating model
-\item ${\cal M} := F\{{\cal G}, \vec p\}$: cascade
-\end{itemize}
+%{\bf Graph Reconstruction}:
 
-{\bf Objective}:
-\begin{itemize}
-\item Find algorithm which computes $F^{-1}({\cal M}) = \{{\cal G}, \vec p\}$ w.h.p., i.e. recovers graph from cascades.
-\end{itemize}
+%\begin{itemize}
+%\item \{${\cal G}, \vec p$\}: directed graph, edge probabilities
+%\item $F$: cascade generating model
+%\item ${\cal M} := F\{{\cal G}, \vec p\}$: cascade
+%\end{itemize}
 
-{\bf Approach}
-\begin{itemize}
-\item Frame graph reconstruction as a {\it Sparse Recovery} problem for two cascade generating models.
-\end{itemize}
+%{\bf Objective}:
+%\begin{itemize}
+%\item Find algorithm which computes $F^{-1}({\cal M}) = \{{\cal G}, \vec p\}$ w.h.p., i.e. recovers graph from cascades.
+%\end{itemize}
+
+%{\bf Approach}
+%\begin{itemize}
+%\item Frame graph reconstruction as a {\it Sparse Recovery} problem for two cascade generating models.
+%\end{itemize}
 
 %Given a set of observed cascades, the \textbf{graph reconstruction problem} consists of finding the underlying graph on which these cascades spread. We assume that these cascades come from the classical \textbf{Independent Cascade Model} where at each time step, newly infected nodes infect each of their neighbor with some probability.
 
@@ -101,47 +106,65 @@
 
 %We formulate a novel approach to this problem in which we use \textbf{Sparse Recovery} to find the edges in the unknown underlying network. Sparse Recovery is the problem of finding the sparsest vector $x$ such that $\mathbf{M x =b}$. In our case, for each node $i$, we wish to recover the vector $x = p_i$ where $p_{i_j}$ is the probability that node $j$ infects node $i$ if $j$ is active. To recover this vector, we are given $M$, where row $M_{t,k}$ indicates which nodes are infected at time $t$ in observed cascade $k$,  and $b$, where $b_{t+1,k}$ indicates if node $i$ is infected at time $t+1$ in cascade $k$. Since most nodes have a small number of neighbors in large networks, we can assume that these vectors are sparse. Sparse Recovery is a well studied problem which can be solved efficiently and with small error if $M$ satisfies certain properties. In this project, we empirically study to what extent $M$ satisfies the Restricted Isometry Property.
 
-\end{block}
 
 %---------------------------------------------------------------------------------
 %---------------------------------------------------------------------------------
 
 \begin{block}{Voter Model}
+
+\begin{figure}
+\centering
+\includegraphics[width=0.6\textwidth]{voter.png}
+\end{figure}
+
+
+
+\vspace{0.5 cm}
 {\bf Description}
 
+\vspace{0.5 cm}
+
 \begin{itemize}
 \item Two types of nodes, {\color{red} red} and {\color{blue} blue}.
 \item $\mathbb{P}$(node is {\color{blue} blue} at $t=0) = p_{\text{init}}$
 \item $\mathbb{P}$(node is  {\color{blue} blue} at t+1) =  $\frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$
-\item Observe until horizon T
 \end{itemize}
 
+\vspace{0.5 cm}
+
 {\bf Sparse Recovery Formulation}
-\begin{itemize}
-\item Definitions:
-\end{itemize}
-\begin{align}
-(\vec m^t_k)_j &:= \left[\text{node j is  {\color{blue} blue} at t in cascade k}\right] \nonumber \\
-(\vec x_{i})_j &:= \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of i in }{\cal G}\right] \nonumber \\
-b^t_{k,i} &:= \text{node i is {\color{blue} blue} at t+1 in cascade k} \nonumber 
-\end{align}
 
-\begin{itemize}
-\item Observation:
-\end{itemize}
-\begin{align}
-\langle \vec m^t_k, \vec x_i \rangle &= \mathbb{P}(\text{node i is {\color{blue} blue} at t+1 in cascade k}) \nonumber \\
-&=: w^{t+1}_{k,i} \nonumber
-\end{align}
+\vspace{0.5 cm}
+
+
+To recover the neighbors of $v_1$:
+
+Observe which nodes are  {\color{red} red} (1) or {\color{blue} blue} (0) in the two first iterations:
+\begin{align*}
+&v_2 \hspace{0.2 cm}  v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 \\
+\vspace{1 cm}
+M  = &  \left( \begin{array}{cccc}
+0 & 0 & 1 & 1 \\
+1 & 1 & 0 & 0 \\
+\end{array} \right) 
+\end{align*}
+
+and which color $v_1$ is in the two last iterations:
+
+\begin{align*}
+b_1  = &  \left( \begin{array}{c}
+1 \\
+1 \\
+\end{array} \right) 
+\end{align*}
+
+If $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $, then our goal is to solve:
 
-\begin{itemize}
-\item We observe $M := \text{vstack}(\vec m^t_k)$
-\item We observe $b_i := \text{vstack}(b^t_{k,i})$ where $$b^t_{k,i} \sim {\cal B}(w^t_{k,i}) = w^t_{k,i} - \epsilon$$
-\item For each node i, solve for $\vec x_i$:
 \begin{equation}
-\boxed{M \vec x_i = \vec b_i + \epsilon \nonumber}
+\boxed{M \vec x_1 = \vec b_1 + \epsilon \nonumber}
 \end{equation}
-\end{itemize}
+
+This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. 
 \end{block}
 
 
@@ -155,37 +178,6 @@ b^t_{k,i} &:= \text{node i is {\color{blue} blue} at t+1 in cascade k} \nonumber
 %---------------------------------------------------------------------------------
 %---------------------------------------------------------------------------------
 
-\begin{block}{Independent Cascade Model}
-
-{\bf Description}
-\begin{itemize}
-\item Three possible states: susceptible, infected, inactive
-\item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently
-\item $\mathbb{P}$(inactive at t+1| infected at t) = 1
-\item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$
-\end{itemize}
-
-
-{\bf Sparse Recovery Formulation}
-\begin{itemize}
-
-\item Definitions:
-\begin{align}
-(\vec \theta_i)_j &:= \log ( 1 - p_{j,i}) \nonumber \\
-(\vec m^t_k)_j &= \left[\text{node j is infected at t in cascade k}\right] \nonumber
-\end{align}
-
-\item Observation:
-\begin{equation}
-\langle \vec m^t_k, \vec x_i \rangle = \log \mathbb{P}(\text{node i {\it not} infect. at t+1 in casc. k}) \nonumber
-\end{equation}
-\item With same notations, we solve for each node i:
-\begin{equation}
-\boxed{e^{M \vec \theta_i} = (1 - \vec b_i) + \epsilon} \nonumber
-\end{equation}
-where: $e^{M \vec \theta_i}$ is taken element-wise
-\end{itemize}
-\end{block}
 
 
 
@@ -205,34 +197,60 @@ where: $e^{M \vec \theta_i}$ is taken element-wise
 %----------------------------------------------------------------------------------------
 %	CONSTRAINT SATISFACTION - BACKTRACKING
 %----------------------------------------------------------------------------------------
-\begin{block}{Example}
-
+\begin{block}{Independent Cascades Model}
 \begin{figure}
 \centering
-\includegraphics[width=0.6\textwidth]{cascades.png}
-\caption{Two cascades with two time steps each. Red nodes are the infected and active nodes.}
+\includegraphics[width=0.6\textwidth]{icc.png}
 \end{figure}
 
-Figure 1 illustrates two cascades. In this case, if we wish to recover $p_A$, then our problem would be is given by the formula
-\[ \left( \begin{array}{cccc}
+{\bf Description}
+
+
+
+\begin{itemize}
+\item Three possible states: susceptible  {\color{blue} blue}, infected  {\color{red} red}, inactive  {\color{yellow} yellow}
+\item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$
+\item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently
+\end{itemize}
+
+
+{\bf Sparse Recovery Formulation}
+
+To recover the neighbors of $v_5$:
+
+Observe which nodes are  {\color{red} red} (1), {\color{blue} blue} (0), or yellow {\color{yellow} yellow} (0) in the two first iterations:
+\begin{align*}
+&v_1 \hspace{0.2 cm}  v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\
+\vspace{1 cm}
+M  = &  \left( \begin{array}{cccc}
 1 & 0 & 0 & 0 \\
-0 & 1 & 0 & 0 \\
-\end{array} \right) x_A =  \left( \begin{array}{c}
+0 & 1 & 1 & 0 \\
+\end{array} \right) 
+\end{align*}
+
+and if $v_5$ is infected in the two last iterations:
+
+\begin{align*}
+b_1  = &  \left( \begin{array}{c}
 0 \\
-1 \\\end{array} \right)\]
+1 \\
+\end{array} \right) 
+\end{align*}
+
+If $(\vec \theta_i)_j := \log ( 1 - p_{j,i})  $, then our goal is to solve:
+
+\begin{equation}
+\boxed{e^{M \vec \theta_i} = (1 - \vec b_i) + \epsilon} \nonumber
+\end{equation}
+
+
+
 
 \end{block}
 
 %----------------------------------------------------------------------------------------
 
-\begin{block}{Motivation}
-\begin{itemize}
-\item Vectors $\vec x_i$ are deg(i)-sparse.
-\item Matrix $M$ is well-conditioned (see experimental section)
-\item Voter model: quasi-textbook noisy sparse recovery
-\item Independent cascade: if $p_{j,i} < 1 - \eta$, exponential can be approximated by affine function
-\end{itemize}
-\end{block}
+
 
 \begin{block}{Algorithms}
 
@@ -252,7 +270,6 @@ Figure 1 illustrates two cascades. In this case, if we wish to recover $p_A$, th
 \begin{equation}
 \min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - \vec b_i \|_2 \nonumber
 \end{equation}
-where: $e^{M \vec \theta_i}$ is taken element-wise
 \end{itemize}
 
 \end{block}
@@ -291,35 +308,9 @@ where: $e^{M \vec \theta_i}$ is taken element-wise
 %----------------------------------------------------------------------------------------
 
 
-\begin{block}{Theoretical Guarantees}
 
-{\bf Assumptions}
-\begin{itemize}
-\item Suppose that each row of $M$ is taken from a distribution $F$, such that
-\begin{itemize}
-	\item $\mathbb{E}_{a \in F}(a a^T) = I_n$
-	\item $\|a\|_{\infty} \leq \mu$
-\end{itemize}
-\item Suppose that w.h.p $\| M^T \epsilon \|_{\infty} \leq 2.5 \sqrt{\log n} $
-\end{itemize}
-
-{\bf Theorem \cite{candes}}
-
-If node $i$ has degree $\Delta$  and $n_{\text{rows}}(M) \geq C \mu \Delta \log n$, then, w.h.p.,
-
-$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$$
-
-{\bf Discussion}
-
-\begin{itemize}
-\item If we consider $M/p_{init}$, then $\mathbb{E}_{a \in F}(a a^T) \approx I_n$
-\item $\mathbb{E}(\epsilon) = 0$, hence $\| M^T \epsilon \|_{\infty} \leq 2.5 \sqrt{\log n}$ should hold w.h.p
-\end{itemize}
-
-\end{block}
 
-
-\begin{block}{Restriced Isometry Property (RIP)}
+\begin{block}{Restricted Isometry Property (RIP)}
 {\bf Definition}
 \begin{itemize}
 \item The Restricted Isometry Property (RIP) characterizes a quasi-orthonormality of the measurement matrix M on sparse vectors. 
@@ -343,6 +334,20 @@ $$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$
 
 \end{block}
 
+\begin{block}{Theoretical Guarantees}
+
+In the case of small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$:
+
+{\bf Theorem \cite{candes}}
+
+If node $i$ has degree $\Delta$  and $n_{\text{rows}}(M) \geq C_1 \mu \Delta \log n$, then, w.h.p.,
+
+$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$$
+
+
+\end{block}
+
+
 
 
 %----------------------------------------------------------------------------------------
@@ -351,6 +356,12 @@ $$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{m}}$
 
 \begin{block}{Description of Experiments}
 
+\begin{tabular}{ c | c | c | c | c }
+& c = 100, &c = 1000,&c = 100, &c = 1000,\\
+&  i = 0.1&i = 0.1& i = 0.05& i = 0.05\\
+ \hline
+  $\delta_4$ & 0.54 & 0.37 &0.43&0.23 \\
+\end{tabular}
 
 
 \end{block}