I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over these edges.
Most importantly, I want a solution that maintains the DAG property, i.e. no cycles. Given that constraint, I want to maximize the total probability of edges kept in the DAG combined with the (1 - probability) edges removed from the graph.
Any suggestions on how to implement this optimization algorithm?
Perhaps I could use an ELO or TrueSkill ranking as an approximation. The difficulty is sampling matches, but perhaps it makes sense to sample non-zero edges randomly, uniformly. So nodes with high in-degree or high out-degree are selected more frequently, since they are more likely to impose constraints on the graph. The probability of winning is determined by the edge probability.
This doesn't guarantee a DAG but would be a great initialization point. Anyway, I'm curious about alternate ideas or refinements to the above.