Sampling DAGs from MPDAG

[wwwwwyyyyyxxxxx]

Thanks for creating CliquePicking, nice work!

I noticed that currently CliquePicking only supports sampling DAGs from MECs. And in [Issue #9](#9), you mentioned you're working on supporting sampling from MPDAGs.

After reading your paper "Efficient Enumeration of Markov Equivalent DAGs," I see that Algorithms 6-7 already provide a method for sampling DAGs from MPDAGs. Have you implemented this functionality, and if so, is it possible to access and use this code?

Thanks for your help!

[mwien]

Hi, thanks for reaching out!

I'm not actively working on implementing a DAG sampler for MPDAGs right now, but as you noticed its on my list of potential additions. That this functionality would help you definitely gives me some motivation to code this at some point :) I'm not promising a timeline because I don't want to get your hopes up, it's not very likely I'll get to this soon.

Still, some quick remarks/questions:

• Algorithms 6-7 list all DAGs represented by an MPDAG. While such an algorithm could be used for sampling DAGs randomly, listing all (and then taking some random subset) is much more expensive. Also note that if one directly uses the first k DAGs the listing algorithm outputs, those would not be uniformly random (quite the opposite, the listing is very systematic). Do you need k random DAGs or do any k DAGs suffice?
• What you could (potentially) do: Find the CPDAG that corresponds to the MPDAG you have (there are reasonable ways to do this, e.g. keep only orientations of edges in v-structures, then perform the Meek rules). Then use the sampling algorithm from cliquepicking for CPDAGs and simply reject all produced DAGs which violate some edges in the MPDAG. Voilà, there's your sampler for MPDAGs (of course whether that works well, depends on the rejection rate).
• Another thing: There are some classes of MPDAGs for which you can directly use the current CPDAG sampler implemented in cliquepicking. This is possible if the background knowledge has specific structure, such that e.g. all edges incident to some node are oriented based on background/interventional knowledge (as is common in Active Learning). Basically, the CPDAG sampler works for MPDAGs too if every connected component with regard to the undirected edges has no directed edge inside of it.

[wwwwwyyyyyxxxxx]

Thank you for your response!

For the first point, I only need any k DAGs from the equivalence class - they don't necessarily need to be uniformly random samples.

About the rejection sampling approach: I'm concerned about efficiency since my MPDAGs have substantial background knowledge, which would likely lead to high rejection rates.

On your third point: I'm actually dealing with exactly that scenario - MPDAGs where edges around individual nodes aren't fully oriented. My current approach is:

1. Start with the MPDAG
2. Randomly select an undirected edge and orient it in a random direction
3. Apply Meek's rules to propagate constraints
4. Repeat until no undirected edges remain

While this doesn't produce uniform samples, it works for my application since I just need to find valid DAGs within the equivalence class. Not the most elegant solution, but it's functional for now!

Looking forward to your future code on this topic!

[mwien]

Ah, interesting that you just need any k DAGs from the class, didn't have such an application in mind.

Coding the listing algo for that is also much more manageable compared to the uniform sampler. Will write here when I get to implementing it.

Until then, I think what you're doing currently is absolutely reasonable if performance is acceptable! Looking forward to seeing the end results :)