diff options
Diffstat (limited to 'paper')
| -rw-r--r-- | paper/paper.tex | 13 | ||||
| -rw-r--r-- | paper/sections/intro.tex | 33 | ||||
| -rw-r--r-- | paper/sparse.bib | 48 |
3 files changed, 50 insertions, 44 deletions
diff --git a/paper/paper.tex b/paper/paper.tex index 04717b1..04bb46f 100644 --- a/paper/paper.tex +++ b/paper/paper.tex @@ -44,7 +44,7 @@ % The \icmltitle you define below is probably too long as a header. % Therefore, a short form for the running title is supplied here: -\icmltitlerunning{Cracking Cascades: Sparse Recovery for Graph Inference} +\icmltitlerunning{Sparse Recovery for Graph Inference} \usepackage{amsmath, amsfonts, amssymb, amsthm} \newcommand{\reals}{\mathbb{R}} @@ -66,7 +66,7 @@ \begin{document} \twocolumn[ -\icmltitle{Cracking Cascades: Sparse Recovery for Graph Inference} +\icmltitle{Sparse Recovery for Graph Inference} % It is OKAY to include author information, even for blind % submissions: the style file will automatically remove it for you @@ -88,7 +88,14 @@ ] \begin{abstract} -blabla +Summarize contributions: + +\begin{itemize} +\item First ${\cal O}(\Delta \log n)$ algorithm +\item First study of edge weight recovery +\item First study of relaxed sparsity +\item First practical lower bounds? +\end{itemize} \end{abstract} \section{Introduction} diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index 8e03394..5f507d9 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -1,37 +1,20 @@ Many real-world phenomena can be modeled as complex diffusion processes on networks: from behavior adoption, sharing of internet memes, citations of articles, and the spread of infectious diseases. Oftentimes, the exact network is unknown to us: we observe only the behavior of the nodes through time, without knowledge of who `influenced' whom. 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 to recover the edges of the graph from the observation of few influence cascades. -In this context, an effective algorithm will recover a large majority of edges correctly from very few cascades. It has shown that the graph inference problem can be solved, under various assumptions, in $\Omega(poly(\Delta) \log p)$ number of observed cascades, where $\Delta$ is the maximum degree of the graph and $p$ is the number of nodes. In other words, the dependence of the number of cascades required to reconstruct the graph is (almost miraculously) logarithmic in the number of nodes of the graph. +Recent research efforts have focused on constructing an effective algorithm which recovers a large majority of edges correctly from very few cascades. It has shown that the graph inference problem can be solved, under various assumptions, in ${\cal O}(poly(\Delta) \log m)$ number of observed cascades, where $\Delta$ is the maximum degree oand $m$ the number of nodes in the graph. In other words, the dependence of the number of cascades required to reconstruct the graph is (almost miraculously) logarithmic in the number of nodes of the graph. -Since the first few papers on link prediction in networks, the research community has made good progress in defining the Graph Inference problem more clearly and suggesting effective algorithms. However, not only can the known results be improved to $\Omega(\Delta \log p)$, but it can be shown that this is tight to a certain extent. Furthermore, not only can the support of the graph be recovered effectively, but it can be shown that the edge weights themselves can be estimated under the same assumptions, and that this is also tight to a certain extent. +Since the first few papers on link prediction in networks, the research community has made good progress in defining the Graph Inference problem more clearly and suggesting effective algorithms. We show that these results can be improved to ${\cal O}(\Delta \log m)$, which is tight to a certain extent. We also that the edge weights themselves can be estimated under the same assumptions. -Throughout this paper, we focus on the two main diffusion processes, outlined by Kempe et al. (...) in their seminal work [cite]: the independent cascade model (IC) and the linear threshold model. More generally, we aim to cast the graph inference problem as a {\it generalized linear model} regression problem. - -\paragraph{Cascades and parameters} +Throughout this paper, we focus on the two main diffusion processes, outlined in the seminal work \cite{Kempe:03}: the independent cascade model (IC) and the linear threshold model. \subsection{Related Work} \paragraph{Past work} -\begin{itemize} -\item Gomez -\item Netrapalli: $d^2 $log n + correlation decay + very bad dependence on -\item Kleinberg/Abrahao: $d^9$ log n: single source model... -\item Gomez: $d^3$ log n + assumptions on Hessian of diffusion process: upper and lower bound on eigenvalues + same proof concept as Netrapalli -\end{itemize} +The study of edge prediction in graph has been an active field of research for over a decade. \cite{GomezRodriguez:2010} was one of the first papers to study graph prediction from cascades. They introduce the {\scshape netinf} algorithm, which approximates the likelihood of cascades represented as a continuous process. The algorithm was later improved/modified in later work. Beside validation on generic networks, {\scshape netinf} is not known to have any theoretical recovery guarantees. \cite{Netrapalli:2012} studied solely the independent cascade model and obtained the first ${\cal O}(\Delta^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 restricts the number of new infections at every step. In this restricted setting, they show a complex lower bound, which is roughly $\Omega(\Delta \log (m/\Delta))$ lower bound for perfect support recovery with constant probability. -\paragraph{Our contribution} +The work of \cite{Abrahao:13} study the same continous-model framework as \cite{GomezRodriguez:2010} and obtain a ${\cal O}(\Delta^9 \log^2 \Delta \log m)$ support recovery algorithm. 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 `infections' of the cascade. We will reach a similar conclusion in section~\ref{sec:assumptions}. However, their model supposes a single-source model, where only one source is selected at random, which is less realistic in practice. Oftentimes, the `patient 0' is unknown to us, and a multi-source model intuitively models the more common situation of a delayed observation of the cascade. -\begin{itemize} -\item Better assumptions: easy to understand, verify?, and much less restrictive -\item Oracle inequality rather than support recovery -> First one -\item Algorithm for recovery in Omega(d log n) -> First one -\item Practical Confidence Intervals -\item Practical Lower bound -\item Compare on generic networks -\end{itemize} +The recent work of \cite{Daneshmand:2014} is very similar to our own, in fact we only grew aware of their contribution at a late stage in the writing of this paper. Similarly to our approach, they consider a $\ell1$-norm penalty to their objective function, adapting standard results from sparse recovery to obtain a ${\cal O}(\Delta^3 \log m)$ algorithm under an irrepresentability condition. With stronger assumptions, they match the \cite{Netrapalli:2012} bound of ${\cal O}(\Delta^2 \log m)$, by exploiting a similar proof technique based around the KKT conditions of the objective function. Their work has the merit of studying a general framework of continuous functions. However, they also place themselves in the restrictive single-source context. -To justify: -\begin{itemize} -\item why discrete isn't so bad; -\item why Gomez's assumptions are not reasonable; -\end{itemize} +\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, to the best of the authors' knowledge, ${\cal O}(\Delta \log m)$ algorithm for graph inference from cascades, which is tight to a certain extent. We also study the seemingly overlooked problem of weight recovery as well as the setting of the relaxed sparsity setting. 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. diff --git a/paper/sparse.bib b/paper/sparse.bib index 969e45d..10ae8ca 100644 --- a/paper/sparse.bib +++ b/paper/sparse.bib @@ -80,26 +80,42 @@ year = {2006}, {ICML} 2014, Beijing, China, 21-26 June 2014}, pages = {793--801}, year = {2014}, - crossref = {DBLP:conf/icml/2014}, url = {http://jmlr.org/proceedings/papers/v32/daneshmand14.html}, timestamp = {Fri, 07 Nov 2014 20:42:30 +0100}, biburl = {http://dblp.uni-trier.de/rec/bib/conf/icml/DaneshmandGSS14}, bibsource = {dblp computer science bibliography, http://dblp.org} } -\bibitem{abrahao} -Abrahao, B., Chierichetti, F., Kleinberg, R., and Panconesi, A. -\newblock{\it Trace Complexity of Network Inference} -\newblock In Proc. 19th ACM SIGKDD international conference on Knowledge discovery and data mingin, KDD'13, pages 491--499, -\newblock 2013 - -\bibitem{candes} -Candès, E., and Plan, Y. -\newblock {\it A Probabilistic and RIPless Theory of Compressed Sensing} -\newblock Information Theory, IEEE Transactions on, 57(11): 7235--7254, -\newblock 2011. +@inproceedings{Kempe:03, + author = {David Kempe and + Jon M. Kleinberg and + {\'{E}}va Tardos}, + title = {Maximizing the spread of influence through a social network}, + booktitle = {Proceedings of the Ninth {ACM} {SIGKDD} International Conference on + Knowledge Discovery and Data Mining, Washington, DC, USA, August 24 + - 27, 2003}, + pages = {137--146}, + year = {2003}, + url = {http://doi.acm.org/10.1145/956750.956769}, + doi = {10.1145/956750.956769}, + timestamp = {Mon, 13 Feb 2006 15:34:20 +0100}, + biburl = {http://dblp.uni-trier.de/rec/bib/conf/kdd/KempeKT03}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} -\bibitem{snap} -Leskovec, J., and Krevl, A., -\newblock {\it SNAP Datasets: Stanford Large Network Dataset Collection}, -\newblock 2014.
\ No newline at end of file +@inproceedings{Abrahao:13, + author = {Bruno D. Abrahao and + Flavio Chierichetti and + Robert Kleinberg and + Alessandro Panconesi}, + title = {Trace complexity of network inference}, + booktitle = {The 19th {ACM} {SIGKDD} International Conference on Knowledge Discovery + and Data Mining, {KDD} 2013, Chicago, IL, USA, August 11-14, 2013}, + pages = {491--499}, + year = {2013}, + url = {http://doi.acm.org/10.1145/2487575.2487664}, + doi = {10.1145/2487575.2487664}, + timestamp = {Tue, 10 Sep 2013 10:11:57 +0200}, + biburl = {http://dblp.uni-trier.de/rec/bib/conf/kdd/AbrahaoCKP13}, + bibsource = {dblp computer science bibliography, http://dblp.org} +} |