  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.
