From 7fd038c7b0f00f6db411e9c5037133fd09509a8d Mon Sep 17 00:00:00 2001
From: Jean Pouget-Abadie <jean.pougetabadie@gmail.com>
Date: Wed, 29 Apr 2015 20:58:17 -0400
Subject: small reviewer updates

---
 paper/sections/intro.tex | 116 +++++++++++++++++++++++++++++++++--------------
 1 file changed, 82 insertions(+), 34 deletions(-)

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

diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex
index d263860..a04b5f1 100644
--- a/paper/sections/intro.tex
+++ b/paper/sections/intro.tex
@@ -1,11 +1,41 @@
 \begin{comment}
-A recent line of research has focused on applying advances in sparse recovery to graph analysis. A graph can be interpreted as a signal that one seeks to `compress' or `sketch' and then `recovered'. However, we could also consider the situation where the graph is unknown to us, and we dispose of few measurements to recover the signal. Which real-life processes allow us to `measure' the graph?
+A recent line of research has focused on applying advances in sparse recovery to
+graph analysis. A graph can be interpreted as a signal that one seeks to
+`compress' or `sketch' and then `recovered'. However, we could also consider the
+situation where the graph is unknown to us, and we dispose of few measurements
+to recover the signal. Which real-life processes allow us to `measure' the
+graph?
 
-A diffusion process taking place on a graph can provide valuable information about the existence of edges and their edge weights. By observing the sequence of nodes which become `infected' over time without knowledge of who has `infected' whom, can we recover the graph on which the process takes place? The spread of a particular behavior through a network is known as an {\it Influence Cascade}. In this context, the {\it Graph Inference} problem is the recovery of the graph's edges from the observation of few influence cascades. We propose to show how sparse recovery can be applied to solve this recently introduced graph inference problem.
+A diffusion process taking place on a graph can provide valuable information
+about the existence of edges and their edge weights. By observing the sequence
+of nodes which become `infected' over time without knowledge of who has
+`infected' whom, can we recover the graph on which the process takes place? The
+spread of a particular behavior through a network is known as an {\it Influence
+Cascade}. In this context, the {\it Graph Inference}\ problem is the recovery of
+the graph's edges from the observation of few influence cascades. We propose to
+show how sparse recovery can be applied to solve this recently introduced graph
+inference problem.
 
-Tackling the graph inference problem means constructing a polynomial-time algorithm which recovers with high probability a large majority of edges correctly from very few observations or {\it cascades}. Prior work shown that the graph inference problem can be solved in ${\cal O}(poly(s) \log m)$ number of observed cascades, where $s$ is the maximum degree and $m$ is the number of nodes in the graph. Almost miraculously, the number of cascades required to reconstruct the graph is logarithmic in the number of nodes of the graph. Results in the sparse recovery literature lead us to believe that $\Omega(s \log m/s)$ cascade observations should be sufficient to recover the graph. In fact, we prove this lower bound in a very general sense: any non-adaptive graph inference algorithm which succeeds in recovering the graph with constant probability requires $\Omega(s \log m/s)$ observations. We show an almost tight upper-bound by applying standard sparse recovery techniques and assumptions: ${\cal O}(s \log m)$ are sufficient to recover the graph. We show that the edge weights themselves can also be recovered under the same assumptions.
+{\color{red} Graph inference to Network inference}
+Tackling the graph inference problem means constructing a polynomial-time
+algorithm which recovers with high probability a large majority of edges
+correctly from very few observations or {\it cascades}. Prior work shown that
+the graph inference problem can be solved in ${\cal O}(poly(s) \log m)$ number
+of observed cascades, where $s$ is the maximum degree and $m$ is the number of
+nodes in the graph. Almost miraculously, the number of cascades required to
+reconstruct the graph is logarithmic in the number of nodes of the graph.
+Results in the sparse recovery literature lead us to believe that $\Omega(s \log
+m/s)$ cascade observations should be sufficient to recover the graph. In fact,
+we prove this lower bound in a very general sense: any non-adaptive graph
+inference algorithm which succeeds in recovering the graph with constant
+probability requires $\Omega(s \log m/s)$ observations. We show an almost tight
+upper-bound by applying standard sparse recovery techniques and assumptions:
+${\cal O}(s \log m)$ are sufficient to recover the graph. We show that the edge
+weights themselves can also be recovered under the same assumptions.
 
- 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...
+ 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\dots
  \end{comment}
 
 Graphs have been extensively studied for their propagative abilities:
@@ -31,7 +61,8 @@ reconstruction.
 The Graph Inference problem can be decomposed and analyzed ``node-by-node''.
 Thus, we will focus on a single node of degree $s$ and discuss how to identify
 its parents among the $m$ nodes of the graph. Prior work has shown that the
-required number of observed cascades is $\O(poly(s)\log m)$.
+required number of observed cascades is $\O(poly(s)\log m)$. {\color{red} Add
+reference}
 
 A more recent line of research has focused on applying advances in sparse
 recovery to the graph inference problem. Indeed, the graph can be interpreted
@@ -39,7 +70,9 @@ as a ``sparse signal'' measured through influence cascades and then recovered.
 The challenge is that influence cascade models typically lead to non-linear
 inverse problems. The sparse recovery literature suggests that
 $\Omega(s\log\frac{m}{s})$ cascade observations should be sufficient to recover
-the graph. However, the best known upper bound to this day is $\O(s^2\log m)$.
+the graph. However, the best known upper bound to this day is $\O(s^2\log
+m)$.{\color{red} Add reference}
+
 
 The contributions of this paper are the following:
 \begin{itemize}
@@ -69,44 +102,59 @@ Section~\ref{sec:experiments}.
 \paragraph{Related Work}
 
 The study of edge prediction in graphs has been an active field of research for
-over a decade \cite{Nowell08, Leskovec07, 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 theoretical guarantees beside empirical validation on synthetic
-networks. \citet{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 on a
-likelihood function similar to the one we propose, 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 achieves a ${\cal O}(s \log m)$ guarantee in the case
-of tree graphs. The work of \cite{Abrahao:13} studies the same continuous-model framework as
-\cite{GomezRodriguez:2010} and obtains an ${\cal O}(s^9 \log^2 s \log m)$ support
-recovery algorithm, without the \emph{correlation decay} assumption.
+over a decade~\cite{Nowell08, Leskovec07, 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 theoretical
+guarantees beside empirical validation on synthetic networks.
+\citet{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 on a likelihood function similar to
+the one we propose, 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
+achieves a ${\cal O}(s \log m)$ guarantee in the case of tree graphs. The work
+of~\cite{Abrahao:13} studies the same continuous-model framework as
+\cite{GomezRodriguez:2010} and obtains an ${\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.
+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}
 
-Closest to this work is a recent paper by \citet{Daneshmand:2014}, wherein the authors
-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)$ under an irrepresentability condition \cite{Zhao:2006}. Under stronger
-assumptions, they match the \cite{Netrapalli:2012} bound of ${\cal O}(s^2 \log
+{\color{red} say they follow the same model as Gomez and abrahao}
+Closest to this work is a recent paper by \citet{Daneshmand:2014}, wherein the
+authors 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)$ under an irrepresentability condition~\cite{Zhao:2006}. 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.
+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.
 
 \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.
+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.
 \end{comment}
 
 \begin{comment}
 \paragraph{Our contributions}
-Though our work follows closely the spirit of \cite{Netrapalli:2012} and \cite{Daneshmand:2014}, we believe we provide several significant improvements to their work. We study sparse recovery under less restrictive assumptions and obtain the first ${\cal O}(s \log m)$ algorithm for graph inference from cascades. We also study the seemingly overlooked problem of weight recovery as well as the setting of the relaxed sparsity setting. Finally, we show these results are almost tight, by proving in section~\ref{sec:lowerbound} the first lower bound on the number of observations required to recover the edges and the edge weights of a graph in the general case. We study the case of the two best known diffusion processes for simplicity as outlined in \cite{Kempe:03}, but many arguments can be extended to more general diffusion processes.
+Though our work follows closely the spirit of \cite{Netrapalli:2012} and
+\cite{Daneshmand:2014}, we believe we provide several significant improvements
+to their work. We study sparse recovery under less restrictive assumptions and
+obtain the first ${\cal O}(s \log m)$ algorithm for graph inference from
+cascades. We also study the seemingly overlooked problem of weight recovery as
+well as the setting of the relaxed sparsity setting. Finally, we show these
+results are almost tight, by proving in section~\ref{sec:lowerbound} the first
+lower bound on the number of observations required to recover the edges and the
+edge weights of a graph in the general case. We study the case of the two best
+known diffusion processes for simplicity as outlined in \cite{Kempe:03}, but
+many arguments can be extended to more general diffusion processes.
 \end{comment}
-- 
cgit v1.2.3-70-g09d2

