[ENH] Add the ability to convert an MAG to a PAG.

[aryan26roy]

Closes #85

Changes proposed in this pull request:

• Adds a function to convert an MAG to PAG.

Before submitting

• [ ] I've read and followed all steps in the Making a pull request section of the CONTRIBUTING docs.
• [ ] I've updated or added any relevant docstrings following the syntax described in the Writing docstrings section of the CONTRIBUTING docs.
• [ ] If this PR fixes a bug, I've added a test that will fail without my fix.
• [ ] If this PR adds a new feature, I've added tests that sufficiently cover my new functionality.

After submitting

• [ ] All GitHub Actions jobs for my pull request have passed.

[aryan26roy]

@adam2392 I will look for the exact algorithm and add it to the PR description.

[aryan26roy]

@adam2392 I can't find an implementation in the tetrad code base. Do you know where might I find it?

[adam2392]

@adam2392 I can't find an implementation in the tetrad code base. Do you know where might I find it?

Sorry you're right. They have a pagToMag algorithm which references Zhang 2008 Theorem 2. Let's go for this one then.

The MAG to PAG algorithm is just turning a normal DAG to a PAG (since a MAG Is a DAG, but with some extra restrictions). The DAG to PAG algorithm would leverage the orientation rules of the FCI algorithm, so Idk if it's worth adding here since we implemented that in dodiscover. FYI it is DagToPag class and then calling the convert function.

[codecov[bot]]

Codecov Report

Merging #87 (410d6ef) into main (96e58b9) will decrease coverage by 0.02%. The diff coverage is 50.00%.

@@            Coverage Diff             @@
##             main      #87      +/-   ##
==========================================
- Coverage   77.01%   76.99%   -0.02%     
==========================================
  Files          42       42              
  Lines        3358     3360       +2     
  Branches      965      965              
==========================================
+ Hits         2586     2587       +1     
- Misses        570      571       +1     
  Partials      202      202              

Files Changed	Coverage Δ
pywhy_graphs/algorithms/pag.py	90.68% <50.00%> (-0.34%)	:arrow_down:

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[aryan26roy]

@adam2392 for converting an MAG to PAG, do you want me to implement the FCI rules here? Or can we use the DagToPag class from dodiscover?

[adam2392]

@adam2392 for converting an MAG to PAG, do you want me to implement the FCI rules here? Or can we use the DagToPag class from dodiscover?

Hmm good question. So the issue is that some of the rules rely on knowledge of the separating set, which basically requires re-running FCI with the graph as an oracle for the Conditional independence (CI) test.

For now, you can just import dodiscover and run FCI. However, this might result in a bit of an annoyance as dodiscover API is relatively unstable. I am disinclined to add this to the pywhy-graphs codebase as a result.

Sorry for bouncing you around, but perhaps we can revisit the PAG_to_MAG algorithm? https://github.com/py-why/pywhy-graphs/issues/67#issue-1632126474

To perform the check on a PAG, it seems you have:

• [x] check for some validity that it is a PAG (e.g. circle edges); you should be able to do this pretty easily
• [ ] convert the PAG to a MAG using the theorem linked in the issue in Zhang's 2008 paper (we don't have a MAG class, but we can just use an ADMG class for now)
• [x] check the validity of the MAG
• [ ] convert the MAG back to a PAG
• [x] check if PAG is same as the PAG fed in; easy to do.

The MAG to a PAG is technically implemented in dodiscover via FCI with the graph as an oracle. I will need to think about how to best add this in. I would now focus on the PAG to MAG case. To setup the unit-tests, we can use dodiscover to convert DAGs to PAGs.

[adam2392]

Basically tldr: @aryan26roy let's start a new PR on doing PAG to MAG. In the unit-tests you can use dodiscover for now if you need to construct a valid PAG from a DAG. Alternatively, you can use Tetrad GUI to come up with some random PAGs.

[aryan26roy]

For now, you can just import dodiscover and run FCI. However, this might result in a bit of an annoyance as dodiscover API is relatively unstable. I am disinclined to add this to the pywhy-graphs codebase as a result.

Should I go ahead with this @adam2392 ?

[adam2392]

For now, you can just import dodiscover and run FCI. However, this might result in a bit of an annoyance as dodiscover API is relatively unstable. I am disinclined to add this to the pywhy-graphs codebase as a result.

Should I go ahead with this @adam2392 ?

This meaning adding FCI rules to the codebase?

[aryan26roy]

This meaning adding FCI rules to the codebase?

No, I meant importing dodiscover in pywhy-graphs. I was assuming that the API would have stabilised by now.

[adam2392]

This meaning adding FCI rules to the codebase?

No, I meant importing dodiscover in pywhy-graphs. I was assuming that the API would have stabilised by now.

It is not yet, so you can just add the FCI rules temporarily here to help convert a MAG to a PAG

[aryan26roy]

@adam2392 iirc, the FCI algorithm only converts a DAG to a PAG. Won't I need to convert the MAG to a DAG first?

[adam2392]

@adam2392 iirc, the FCI algorithm only converts a DAG to a PAG. Won't I need to convert the MAG to a DAG first?

nope. I would remind yourself what the difference in skeleton structure between a DAG and a MAG ;)

[aryan26roy]

nope. I would remind yourself what the difference in skeleton structure between a DAG and a MAG ;)

It's just that an MAG has more kinds of edges, right?

[adam2392]

What invariances does an equivalence class like a MAG encode? Do those invariances mean anything probabilistically and graphically? How does the skeleton of the PAG compare to the MAG and DAG? Finally, does it matter for FCI what is fed in? I'll let you explore the rest as I think the answer will be enlightening!

Feel free to ping me about this PR when it's ready to review.

[adam2392]

I resolved CI issues in #99 . Feel free to merge/rebase changes

[aryan26roy]

@adam2392 I will read up on this and then implement the algorithms. Thanks for the help!

[adam2392]

@adam2392 I will read up on this and then implement the algorithms. Thanks for the help!

The FCI rules can prolly be copied over as a refactored version from dodiscover. But yes agreed that reading up on this will help you understand how to test the MAG -> PAG properly and later PRs

[aryan26roy]

@adam2392 I noticed that the FCI implementation in Dodiscover is a seperate file and a class. Should I do the same in pywhy-graphs?

[adam2392]

Sure

[aryan26roy]

@adam2392 The FCI implementation in dodiscover uses a lot of utilities from the dodiscover library. It is also a sub-class of another class called BaseConstraintDiscovery. Should I implement all of these things in pywhy-graphs or simply import them from dodiscover?

[adam2392]

Hmm okay I see, then perhaps let's forego this. It's too much work to replicate the code here and not worth it since it's already in dodiscover.

We need this I guess for #67 ?

I think at that step, we can just use dodiscover code for now.

[adam2392]

Hmm okay I see, then perhaps let's forego this. It's too much work to replicate the code here and not worth it since it's already in dodiscover.

We need this I guess for #67 ?

I think at that step, we can just use dodiscover code for now.

@aryan26roy just checking in here. Just wanted to make sure this seems fine to you?

[aryan26roy]

@adam2392 sorry for the late reply, it was Diwali this weekend and I was travelling. Yes, this seems alright to me. Will use the dodiscover code for now.