1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
\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 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.
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}
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 diffusions processes in which a particular infection behavior
spreads over the nodes of the graph. By only observing the ``infection times''
of the nodes in the graph, one might hope to recover the underlying graph and
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 a set of observed cascades (realisations of the
diffusion process) and recovers with high probability a large fraction of the
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.
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 in sparse
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 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 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.
\item we show that our algorithm is robust in cases where the signal to
recover is approximately $s$-sparse by proving guarantees in the
\emph{stable recovery} setting.
\item we provide an almost tight lower bound of $\Omega(s\log \frac{m}{s})$
observations.
\end{itemize}
The organization of the paper is as follows: ...
\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 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}, 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
the restrictive single-source context.
TODO: add related works on lower bounds.
\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.
\end{comment}
|
