<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>An hacky but maybe worthwhile quick approach:</p>
<p>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.</p>
<p>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.</p>
<p>Anyway, I'm curious about alternate ideas or refinements to the above.</p>

CC BY-SA 4.0
2023-07-12T17:35:24.493Z
I don't understand what you mean by "combined with the...".  Can you define the objective function you are trying to maximize, mathematically?
D.W.
CC BY-SA 4.0
2023-07-12T17:39:21.713Z
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?
D.W.
CC BY-SA 4.0
2023-07-13T15:09:37.870Z
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?
James Martin
<optimization><pr.probability><directed-acyclic-graph><csp><sparse-matrix>
Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG
Joseph Turian
# Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG

(Asked by: username_0 on 2023-07-12)

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.

**Tags:** optimization, pr.probability, directed-acyclic-graph, csp, sparse-matrix

> **Comments:**
> **username_1**: I don't understand what you mean by "combined with the...".  Can you define the objective function you are trying to maximize, mathematically?  
> **username_1**: 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?  
> **username_2**: 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?  

---

## 0 answers

