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. Complicating the task is the fact that the topology of wireless networks changes with time, and so identification may need to be performed on a regular basis. Injecting probing traffic to assess interference can lead to unacceptable overhead, and so this paper focuses on interference estimation based on passive traffic monitoring. We concentrate on networks that use the CSMA/CA protocol, although our model is more general. We cast the task of estimating the 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 required to identify the interference graph reliably with high probability. Our main results are scaling laws telling 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 on the observation requirements are also quantified. We show that 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.