From 190cd5633e7e3237be118c18d374b5542aa38be4 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Thu, 5 Feb 2015 23:22:36 -0500
Subject: Polishing

---
 paper/sections/intro.tex | 55 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 40 insertions(+), 15 deletions(-)

(limited to 'paper/sections/intro.tex')

diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex
index f4f2bd5..bbbed11 100644
--- a/paper/sections/intro.tex
+++ b/paper/sections/intro.tex
@@ -8,11 +8,11 @@ Tackling the graph inference problem means constructing a polynomial-time algori
  Throughout this paper, we focus on the three main discrete-time diffusion processes: the independent cascade model, the voter model, and the linear threshold model...
  \end{comment}
 
-Graphs have been extensively studied in their ability to propagate 
-
-Networks and social networks in particular have become an increasingly common
-subject of study in the recent years. 
-
+Graphs have been extensively studied for their propagative abilities:
+connectivity, routing, gossip algorithms, etc.
+%One question is: can we
+%understand and predict a diffusion process from the graph? Conversely, can we
+%learn a graph from the diffusion process?
 A diffusion process taking place over a graph provides valuable information
 about the presence and weights of its edges. \emph{Influence cascades} are a
 specific type of diffusion processes in which a particular infection behavior
@@ -68,19 +68,44 @@ Section~\ref{sec:experiments}.
 
 \paragraph{Related Work}
 
-The study of edge prediction in graph has been an active field of research for over a decade \cite{Nowell08} \cite{Leskovec07} \cite{AdarA05}. \cite{GomezRodriguez:2010} introduced the submodular {\scshape netinf} algorithm, which approximates the likelihood of cascades represented as a continuous process. The algorithm was later improved in later work \cite{gomezbalduzzi:2011}, but is not known to have any recovery guarantees beside empirical validation on synthetic networks. \cite{Netrapalli:2012} studied the discrete-time version of the independent cascade model and obtained the first ${\cal O}(s^2 \log m)$ guarantee on general networks. The algorithm is based around the same likelihood function we suggest, without the $\ell1$-norm penalty. However, the analysis depended strongly on a restrictive {\it correlation decay} assumption, which strongly limits the number of new infections at every step. In this restricted setting, they show a complex lower bound of the number of cascades needed for perfect support recovery with constant probability of the order $\Omega(s \log (m/s))$. They also suggest a {\scshape greedy} algorithm, which matches ${\cal O}(s \log m)$ guarantee in the case of \emph{tree} graphs.
+The study of edge prediction in graphs has been an active field of research for
+over a decade \cite{Nowell08} \cite{Leskovec07} \cite{AdarA05}.
+\cite{GomezRodriguez:2010} introduced the {\scshape Netinf} algorithm, which
+approximates the likelihood of cascades represented as a continuous process.
+The algorithm was improved in later work \cite{gomezbalduzzi:2011}, but is not
+known to have any recovery guarantees beside empirical validation on synthetic
+networks. \cite{Netrapalli:2012} studied the discrete-time version of the
+independent cascade model and obtained the first ${\cal O}(s^2 \log m)$
+recovery guarantee on general networks. The algorithm is based around the same
+likelihood function we suggest, without the $\ell_1$-norm penalty. Their
+analysis depends on a {\it correlation decay} assumption, which limits the
+number of new infections at every step. In this setting, they show a lower
+bound of the number of cascades needed for support recovery with constant
+probability of the order $\Omega(s \log (m/s))$. They also suggest a {\scshape
+Greedy} algorithm, which matches the ${\cal O}(s \log m)$ guarantee in the case
+of tree graphs. The work of \cite{Abrahao:13} study the same continuous-model framework as
+\cite{GomezRodriguez:2010} and obtain a ${\cal O}(s^9 \log^2 s \log m)$ support
+recovery algorithm without the \emph{correlation decay} assumption.
+
+\begin{comment}
+They assume a single-source model, where only one source is selected at random, which is less realistic in practice since `patient 0' is rarely unknown to us.
+\end{comment}
 
-The work of \cite{Abrahao:13} study the same continuous-model framework as \cite{GomezRodriguez:2010} and obtain a ${\cal O}(s^9 \log^2 s \log m)$ support recovery algorithm without the \emph{correlation decay} assumption. Their work also studies the information leveraged by different `parts' of the cascade, showing that a surprisingly important amount of information can be gleaned from the first and last `infections' of the cascade. They assume a single-source model, where only one source is selected at random, which is less realistic in practice since `patient 0' is rarely unknown to us.
+Closest to this work is a recent paper by \cite{Daneshmand:2014}, wherein they
+consider a $\ell_1$-regularized objective function. They adapt standard results
+from sparse recovery to obtain a recovery bound of ${\cal O}(s^3 \log m)$ on
+their algorithm under an irrepresentability condition. Under stronger
+assumptions, they match the \cite{Netrapalli:2012} bound of ${\cal O}(s^2 \log
+m)$, by exploiting similar properties of the convex program's KKT conditions.
+In contrast, our work studies discrete-time diffusion processes including the
+Independent Cascade model under weaker assumptions. Furthermore, we analyze
+both the recovery of the graph's edges and the estimation of the model's
+parameters and achieve close to optimal bounds.
 
-Closest to this work is a recent paper by \cite{Daneshmand:2014}, they consider
-a $\ell_1$-norm penalty to their objective function, adapting standard results
-from sparse recovery to obtain a ${\cal O}(s^3 \log m)$ algorithm under an
-irrepresentability condition. With stronger assumptions, they match the
-\cite{Netrapalli:2012} bound of ${\cal O}(s^2 \log m)$, by exploiting
-a similar properties of the objective's KKT conditions. Their work has the merit of studying a generalization of the discrete-time independent cascade model to continuous functions. Similarly to \cite{Abrahao:13}, they place themselves in
+\begin{comment}
+Their work has the merit of studying a generalization of the discrete-time independent cascade model to continuous functions. Similarly to \cite{Abrahao:13}, they place themselves in
 the restrictive single-source context.
-
-TODO: add related works on lower bounds.
+\end{comment}
 
 \begin{comment}
 \paragraph{Our contributions}
-- 
cgit v1.2.3-70-g09d2

