Learning Mixtures of Graphs from Epidemic Cascades
Learning Mixtures of Graphs from Epidemic Cascades
复制标题
DOI：
--
复制
发表时间：
2019-06
影响因子：
2.4
通讯作者：
Jessica Hoffmann;S. Basu;Surbhi Goel;C. Caramanis
中科院分区：
文献类型：
--
作者：
Jessica Hoffmann;S. Basu;Surbhi Goel;C. Caramanis
我们考虑了从流行病级联中学习两个无向图的平衡混合的加权边的问题。虽然混合模型是流行的建模工具，但具有严格保证的算法开发滞后。图混合显然也不例外：到目前为止，我们对这个问题是否可以解决所知甚少。据我们所知，我们建立了该问题在边分离图上多项式时间内可解的第一个充分必要条件。当条件满足时，即当图至少有三条边相连时，我们给出了一种有效的算法来学习两个图的权值，并具有最优的样本复杂度（高达对数因子）。我们给出了互补的结果，并为出度至少为3的有向图的混合，不平衡和/或未知先验的无向图的混合提供了样本最优（高达对数因子）算法。
We consider the problem of learning the weighted edges of a balanced mixture of two undirected graphs from epidemic cascades. While mixture models are popular modeling tools, algorithmic development with rigorous guarantees has lagged. Graph mixtures are apparently no exception: until now, very little is known about whether this problem is solvable. To the best of our knowledge, we establish the first necessary and sufficient conditions for this problem to be solvable in polynomial time on edge-separated graphs. When the conditions are met, i.e., when the graphs are connected with at least three edges, we give an efficient algorithm for learning the weights of both graphs with optimal sample complexity (up to log factors). We give complimentary results and provide sample-optimal (up to log factors) algorithms for mixtures of directed graphs of out-degree at least three, for mixture of undirected graphs of unbalanced and/or unknown priors.