Abstract
We consider the problem of learning the weighted edges of a graph byobserving the noisy times of infection for multiple epidemic cascades on thisgraph. Past work has considered this problem when the cascade information,i.e., infection times, are known exactly. Though the noisy setting is wellmotivated by many epidemic processes (e.g., most human epidemics), to the bestof our knowledge, very little is known about when it is solvable. Previous workon the no-noise setting critically uses the ordering information. If noise canreverse this -- a node's reported (noisy) infection time comes after thereported infection time of some node it infected -- then we are unable to seehow previous results can be extended. We therefore tackle two versions of the noisy setting: the limited-noisesetting, where we know noisy times of infections, and the extreme-noisesetting, in which we only know whether or not a node was infected. We provide apolynomial time algorithm for recovering the structure of bidirectional treesin the extreme-noise setting, and show our algorithm almost matches lowerbounds established in the no-noise setting, and hence is optimal up tolog-factors. We extend our results for general degree-bounded graphs, whereagain we show that our (poly-time) algorithm can recover the structure of thegraph with optimal sample complexity. We also provide the first efficientalgorithm to learn the weights of the bidirectional tree in the limited-noisesetting. Finally, we give a polynomial time algorithm for learning the weightsof general bounded-degree graphs in the limited-noise setting. This algorithmextends to general graphs (at the price of exponential running time), provingthe problem is solvable in the general case. All our algorithms work for anynoise distribution, without any restriction on the variance.