  A key challenge in wireless networking is the management of interference
between transmissions. Identifying which transmitters interfere with each other
is a crucial first step. In this paper we cast the task of estimating the a
wireless interference environment as a graph learning problem. Nodes represent
transmitters and edges represent the presence of interference between pairs of
transmitters. We passively observe network traffic transmission patterns and
collect information on transmission successes and failures. We establish bounds
on the number of observations (each a snapshot of a network traffic pattern)
required to identify the interference graph reliably with high probability.
  Our main results are scaling laws that tell us how the number of observations
must grow in terms of the total number of nodes $n$ in the network and the
maximum number of interfering transmitters $d$ per node (maximum node degree).
The effects of hidden terminal interference (i.e., interference not detectable
via carrier sensing) on the observation requirements are also quantified. We
show that to identify the graph it is necessary and sufficient that the
observation period grows like $d^2 \log n$, and we propose a practical
algorithm that reliably identifies the graph from this length of observation.
The observation requirements scale quite mildly with network size, and networks
with sparse interference (small $d$) can be identified more rapidly.
Computational experiments based on a realistic simulations of the traffic and
protocol lend additional support to these conclusions.
