diff options
| -rw-r--r-- | paper/sections/intro.tex | 30 |
1 files changed, 14 insertions, 16 deletions
diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index b84f562..695c084 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -18,34 +18,32 @@ the parameters of the cascade model. This problem is known in the literature as the \emph{Graph Inference problem}. More precisely, solving the Graph Inference problem involves designing -an algorithm taking as input as set of observed cascades (realisations of the +an algorithm taking as input a set of observed cascades (realisations of the diffusion process) and recovers with high probability a large fraction of the -graph edges. The goal is then to understand the relationship between the number +graph's edges. The goal is then to understand the relationship between the number of observations, the probability of success, and the accuracy of the reconstruction. -In most cases, the Graph Inference problem can be decomposed and analyzed -``node-by-node''. In this introduction, we will thus 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 typical required number of observed -cascades is $\O(poly(s)\log m)$. +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)$. A more recent line of research has focused on applying advances on sparse -inverse problems to the graph inference problem. Indeed, the graph can be -interpreted as a ``sparse signal'' that is sensed 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)$. +recovery to the graph inference problem. Indeed, the graph can be interpreted +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 contributions of this paper are the following: \begin{itemize} \item we formulate the Graph Inference problem in the context of - discrete-time influence cascades as a sparse inverse problem for + discrete-time influence cascades as a sparse recovery problem for a specific type of Generalized Linear Model. This formulation notably encompases the well-studied Independent Cascade Model and Voter Model. - \item we give a an algorithm which recovers the graph edges using $\O(s\log + \item we give an algorithm which recovers the graph's edges using $\O(s\log m)$ cascades. Furthermore, we show that our algorithm is also able to recover the edge weights (the parameters of the influence model), a problem which has been seemingly overlooked so far. |