Learning Graphs from Noisy Epidemic Cascades
Learning Graphs from Noisy Epidemic Cascades
复制标题
DOI：
10.1145/3341617.3326155
复制
发表时间：
2019-03
期刊：
影响因子：
--
通讯作者：
Jessica Hoffmann;C. Caramanis
中科院分区：
文献类型：
--
作者：
Jessica Hoffmann;C. Caramanis
我们通过观察图上多个传染病级联的感染噪声时间来考虑学习图的加权边的问题。以往的工作在级联信息，即感染时间确切已知的情况下考虑了这一问题。虽然这种嘈杂的环境很好地受到了许多流行病过程(例如，大多数人类流行病)的推动，但就我们所知，人们对它何时可以解决知之甚少。之前关于无噪音设置的工作严格使用了排序信息。如果噪声可以逆转这一点--一个节点报告的(噪声)感染时间在它感染的某个节点的报告感染时间之后--那么我们就不能看到如何延长之前的结果。因此，我们处理两个版本的噪声设置：有限噪声设置和极端噪声设置，在有限噪声设置中，我们知道感染的噪声时间，在极端噪声设置中，我们只知道节点是否被感染。我们给出了一个在极端噪声环境下恢复双向树结构的多项式时间算法，并证明了我们的算法符合在无噪声环境下建立的下界，因此是最优的。我们将我们的结果推广到一般的度有界图，再次证明了我们的(多时间)算法能够以最优的样本复杂度恢复图的结构。我们还提出了在有限噪声环境下学习双向树的权值的第一个有效算法。最后，我们给出了在有限噪声环境下学习一般有界度图权的多项式时间算法。该算法推广到一般图(以指数运行时间为代价)，证明了该问题在一般情况下是可解的。我们的所有算法都适用于任何噪声分布，对方差没有任何限制。
We consider the problem of learning the weighted edges of a graph by observing the noisy times of infection for multiple epidemic cascades on this graph. Past work has considered this problem when the cascade information, i.e., infection times, are known exactly. Though the noisy setting is well motivated by many epidemic processes (e.g., most human epidemics), to the best of our knowledge, very little is known about when it is solvable. Previous work on the no-noise setting critically uses the ordering information. If noise can reverse this -- a node's reported (noisy) infection time comes after the reported infection time of some node it infected -- then we are unable to see how previous results can be extended. We therefore tackle two versions of the noisy setting: the limited-noise setting, where we know noisy times of infections, and the extreme-noise setting, in which we only know whether or not a node was infected. We provide a polynomial time algorithm for recovering the structure of bidirectional trees in the extreme-noise setting, and show our algorithm matches lower bounds established in the no-noise setting, and hence is optimal. We extend our results for general degree-bounded graphs, where again we show that our (poly-time) algorithm can recover the structure of the graph with optimal sample complexity. We also provide the first efficient algorithm to learn the weights of the bidirectional tree in the limited-noise setting. Finally, we give a polynomial time algorithm for learning the weights of general bounded-degree graphs in the limited-noise setting. This algorithm extends to general graphs (at the price of exponential running time), proving the problem is solvable in the general case. All our algorithms work for any noise distribution, without any restriction on the variance.