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.

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. 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 in the seminal work \cite{Kempe:03}: the independent cascade model (IC) and the linear threshold model.

\subsection{Related Work}

\paragraph{Past work}

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.

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.

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. 

\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.