In the Network Inference problem, one seeks to recover the edges of an unknown
graph from the observations of cascades propagating over this graph.  In this
paper, we approach this problem from the sparse recovery perspective.  We
introduce a general model of cascades, including the voter model and the
independent cascade model, for which we provide the first algorithm which
recovers the graph's edges with high probability and ${\cal O}(s\log m)$
measurements where $s$ is the maximum degree of the graph and $m$ is the number
of nodes.  Furthermore, we show that our algorithm also recovers the edge
weights (the parameters of the diffusion process) and is robust in the context
of approximate sparsity. Finally we prove an almost matching lower bound of
$\Omega(s\log\frac{m}{s})$ and validate our approach empirically on synthetic
graphs.
