From 6636688e2cdf0757741af973be1ff57f1d2c22e0 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Fri, 11 Dec 2015 20:34:00 -0500
Subject: Related work cleanup

---
 finale/sections/related.tex | 55 +++++++++++++++------------------------------
 1 file changed, 18 insertions(+), 37 deletions(-)

(limited to 'finale/sections/related.tex')

diff --git a/finale/sections/related.tex b/finale/sections/related.tex
index 59fb759..5f0289a 100644
--- a/finale/sections/related.tex
+++ b/finale/sections/related.tex
@@ -1,41 +1,22 @@
 \paragraph{Related works.}
 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, relying on
-Maximum-Likelihood and convex relaxations was improved in later
-work~\cite{gomezbalduzzi:2011}, but is not known to have any theoretical
-guarantees beside empirical validation on synthetic networks.
+over a decade~\cite{Nowell08, Leskovec07, AdarA05}. MLE estimation (regularized
+and un-regularized) for Graph Inference has been studied both for discrete-time
+models \cite{Netrapalli:2012, pouget} and continous-time models
+\cite{GomezRodriguez:2010, gomezbalduzzi:2011, Abrahao:13}
 
-Let us denote by $m$ the number of nodes in the graph and for a given node, we
-denote by $s$ its in-degree. In what follows, we call a \emph{recovery
-guarantee} an upper bound on the number of observations required (expressed as
-a function of $s$ and $m$) to learn the incoming edges of a node to a fixed
-arbitrary accuracy level. \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, by using unregularized MLE and
-making a {\it correlation decay\/} assumption, which limits the number of new
-infections at every step.  They also suggest a {\scshape Greedy} algorithm,
-with provably good performance in tree graphs, which maintains a counter of
-each node's antecedents, i.e. the set of nodes infected at a prior time step to
-its infection time. 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.  \cite{du2013uncover,Daneshmand:2014}
-propose Lasso regularization of MLE for recovering the weights of the graph
-under a continuous-time independent cascade model. The work
-of~\cite{du2014influence} is slightly orthogonal to ours since they suggest
-learning the \emph{influence} function, rather than the parameters of the
-network directly.
-
-More recently, the continuous process studied in previous work has been
-reformulated as a Hawkes process, with recent papers
+More recently, the continuous-time processes studied in previous work have been
+reformulated as a Hawkes processes, with recent papers
 \cite{linderman2014discovering, linderman2015scalable, simma2012modeling},
-focusing on Expectation-Maximization, and Variational Inference methods to learn
-these processes. Because of the discrete nature of the GLC model, we hope to
-bring a better understanding to the link between the properties of a graph and
-its \emph{learnability}. We wish to further explore the idea of non-product
-priors raised in \cite{linderman2014discovering, linderman2015scalable}, since
-the experimental validation of their work focused on simple graph priors.
-Finally, the \emph{Active Learning} formulation is, to the best of the
-authors' knowledge, novel in this context.
+focusing on Expectation-Maximization, Gibbs sampling and Variational Inference
+methods. In comparison the discrete-time nature of the GLC model allows us to
+scale the inference methods to larger graphs. Furthermore, while the works on
+Hawkes processes exclusively used factorized graph priors, we hope that
+Bayesian Inference for the GLC model will be able to accommodate more
+expressive graph priors more easily. This is a direction we wish to explore in
+future works.
+
+The Active Learning formulation is, to the best of the authors' knowledge,
+novel in this context. The Active Learning approach of \cite{shababo} share
+some similarities with ours even though their model is not, strictly speaking,
+a cascade model (in particular, the time steps are independent).
-- 
cgit v1.2.3-70-g09d2

