1
$\begingroup$

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? BTW, I'm talking about a large graph, with maybe 1M or 10M non-zero edges.

An hacky but maybe worthwhile quick approach:

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.

Anyway, I'm curious about alternate ideas or refinements to the above.

$\endgroup$
3
  • $\begingroup$ I don't understand what you mean by "combined with the...". Can you define the objective function you are trying to maximize, mathematically? $\endgroup$
    – D.W.
    Commented Jul 12, 2023 at 17:35
  • $\begingroup$ It sounds like you have a (possibly negative) weight $w(u,v)$ for each pair of vertices $u$, and you want to find a dag $(V,E)$ that maximizes the value of $\sum_{(u,v)\in E} w(u,v)$. (Here $w(u,v) = 2 x[u,v] -1$. Also there is some additional sparsity guarantee, presumably that most values $w(u,v)$ are equal to $-1$.) Is that right? $\endgroup$
    – D.W.
    Commented Jul 12, 2023 at 17:39
  • 2
    $\begingroup$ I don't understand why you mention "probabilities". Are you trying to construct a random DAG, i.e. some probability distribution over DAGs? Or are you trying to find a single DAG which maximises some objective function? Perhaps the phrase "If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr" is just intended to be background motivation which doesn't form part of the optimisation problem you're trying to solve? $\endgroup$ Commented Jul 13, 2023 at 15:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.