  The network inference problem consists of reconstructing the edge set of a
network given traces representing the chronology of infection times as
epidemics spread through the network. This problem is a paradigmatic
representative of prediction tasks in machine learning that require deducing a
latent structure from observed patterns of activity in a network, which often
require an unrealistically large number of resources (e.g., amount of available
data, or computational time). A fundamental question is to understand which
properties we can predict with a reasonable degree of accuracy with the
available resources, and which we cannot. We define the trace complexity as the
number of distinct traces required to achieve high fidelity in reconstructing
the topology of the unobserved network or, more generally, some of its
properties. We give algorithms that are competitive with, while being simpler
and more efficient than, existing network inference approaches. Moreover, we
prove that our algorithms are nearly optimal, by proving an
information-theoretic lower bound on the number of traces that an optimal
inference algorithm requires for performing this task in the general case.
Given these strong lower bounds, we turn our attention to special cases, such
as trees and bounded-degree graphs, and to property recovery tasks, such as
reconstructing the degree distribution without inferring the network. We show
that these problems require a much smaller (and more realistic) number of
traces, making them potentially solvable in practice.
