[ENH] Add the ability to check the validity of a PAG

[aryan26roy]

Fixes #67

Changes proposed in this pull request:

• Add a function that takes in a PAG and checks if it is valid or not.

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]

Just to list the procedure out:

• Convert the PAG to MAG
• Check if the MAG is valid or not
• Convert the MAG back to PAG
• Check if the converted and original PAGs are equivalent or not

@adam2392 is this the right pseudo-algorithm?

[adam2392]

Just to list the procedure out:

• Convert the PAG to MAG
• Check if the MAG is valid or not
• Convert the MAG back to PAG
• Check if the converted and original PAGs are equivalent or not

@adam2392 is this the right pseudo-algorithm?

Yes with the added check at the very beginning that the graph is a valid PAG.

[aryan26roy]

Yes with the added check at the very beginning that the graph is a valid PAG.

For this, is it enough to check if the graph has any circle edges or not?

[adam2392]

Same skeleton as MAG so checking acyclicity, ancestral, and maximalist of the non-circle edge subgraph.

A PAG could be fully oriented which results in no circle edges.

[aryan26roy]

• Check if the converted and original PAGs are equivalent or not

For this, I think I have to determine that the two PAGs have the same set of conditional independence relations since they might be structurally different yet markov equivalent?

[adam2392]

• Check if the converted and original PAGs are equivalent or not

For this, I think I have to determine that the two PAGs have the same set of diff conditional independence relations since they might be structurally different yet markov equivalent?

No that is only the case for MAGs.

The two PAGs should be exactly the same, otherwise they encode some set of conditional independences. This assumes that all of the FCI orientation rules no longer can be applied to the PAG (i.e. it is as oriented as possible).

[aryan26roy]

Ah so simply checking that all of the edges are the same in both the PAGs should suffice.

[aryan26roy]

Same skeleton as MAG so checking acyclicity, ancestral, and maximalist of the non-circle edge subgraph.

Hey @adam2392 I am done with the applications, so back to work! One question though, when checking acyclicity in the non-circle edge subgraph, do I only look for directed cycles? Or is the cycle supposed to be direction agnostic?

[adam2392]

Nice! Congrats.

Can you remind me what part requires the acyclicity check?

[aryan26roy]

Yes with the added check at the very beginning that the graph is a valid PAG.

Before actually checking for the validity, you asked me to check if it was valid-valid.

[aryan26roy]

Maybe there is a better term for it somewhere.

[adam2392]

Ah I see. Yeah it's just the same check as a MAG

That's cuz we can't have cycles in the directed edges or almost directed cycles.

You would only do this for the non circle edges tho. So any edge with a circle endpoint is dropped.

A fully oriented PAG is just a MAG

[aryan26roy]

Ah I see. Yeah it's just the same check as a MAG

That's cuz we can't have cycles in the directed edges or almost directed cycles.

You would only do this for the non circle edges tho. So any edge with a circle endpoint is dropped.

A fully oriented PAG is just a MAG

Got it!

[aryan26roy]

@adam2392 right now I am checking for cycles, almost directed cycles and for inducing paths between any two non-adjacent nodes. Is that enough?

[adam2392]

Yep!

[aryan26roy]

@adam2392 How do I add dodiscover to the list of dependencies?

[adam2392]

For now, just run locally and check it.

Dodiscover isn't on pypi yet but planning on making a release.

[aryan26roy]

@adam2392 can you describe how to convert a mag back to pag? Is it simply running the FCI algorithm using dodiscover?

[adam2392]

@adam2392 can you describe how to convert a mag back to pag? Is it simply running the FCI algorithm using dodiscover?

Yes

[aryan26roy]

@adam2392 I am trying to test the changes and keep getting the following error:

Traceback (most recent call last):

File "", line 189, in _run_module_as_main

File "", line 148, in _get_module_details

File "", line 112, in _get_module_details

File "/Users/aryanroy/Projects/causality/lib/python3.11/site-packages/pytest/init.py", line 5, in from _pytest._code import ExceptionInfo

File "/Users/aryanroy/Projects/causality/lib/python3.11/site-packages/_pytest/_code/init.py", line 2, in from .code import Code

File "/Users/aryanroy/Projects/causality/lib/python3.11/site-packages/_pytest/_code/code.py", line 16, in from typing import Any

File "/Users/aryanroy/Projects/causality/pywhy-graphs/pywhy_graphs/typing.py", line 1, in from typing import Any, Tuple, Union

ImportError: cannot import name 'Any' from partially initialized module 'typing' (most likely due to a circular import) (/Users/aryanroy/Projects/causality/pywhy-graphs/pywhy_graphs/typing.py)

Can you see any reason for this error?

[adam2392]

@adam2392 I am trying to test the changes and keep getting the following error:

Traceback (most recent call last): File "", line 189, in _run_module_as_main

File "", line 148, in _get_module_details

File "", line 112, in _get_module_details

File "/Users/aryanroy/Projects/causality/lib/python3.11/site-packages/pytest/init.py", line 5, in from _pytest._code import ExceptionInfo

File "/Users/aryanroy/Projects/causality/lib/python3.11/site-packages/_pytest/_code/init.py", line 2, in from .code import Code

File "/Users/aryanroy/Projects/causality/lib/python3.11/site-packages/_pytest/_code/code.py", line 16, in from typing import Any

File "/Users/aryanroy/Projects/causality/pywhy-graphs/pywhy_graphs/typing.py", line 1, in from typing import Any, Tuple, Union

ImportError: cannot import name 'Any' from partially initialized module 'typing' (most likely due to a circular import) (/Users/aryanroy/Projects/causality/pywhy-graphs/pywhy_graphs/typing.py)

Can you see any reason for this error?

This is the live code currently on this PR? I don't see any issue off the top of my head. But a circular import usually means somewhere something is getting imported by each other. So usually it's solvable if you do a relative import.

[aryan26roy]

@adam2392 Is it possible that one of the dodiscover modules is importing one of these files and that is what is causing this error?

[adam2392]

Ah yes that is possible. Is the code you're running on the PR? Can you write down the CLI code you use that produces the error?

[aryan26roy]

@adam2392 this is extremely weird but I cannot reproduce the error anymore. Will investigate it some more and let you know if I can get it to show again.

[adam2392]

Sounds good!

Feel free to put up code onto the PR and you can always easily revert commits. In addition, if you have exps that ran that you can describe to put confidence that the code works as intended, that also helps.

[aryan26roy]

@adam2392 The local tests that I am running are working fine. I will add them to the repo one by one after verifying that most of the code branches are being hit. Thanks for the help!

[aryan26roy]

@adam2392 I think this PR is in a good state. All the tests have worked and I have beautified it as well. Want to take a look?

[aryan26roy]

@adam2392 I think I have incorporated all the suggestions you made.

[adam2392]

Sorry for the delay and long wait on this PR @aryan26roy.

In order to make this work, we should take a soft-import strategy on the mag_to_pag and then install it in the CI when using it.

See aecebeb.

Some suggestions

As one last change, it would be useful to see this as an example under examples/intro/checking_validity_of_a_pag.py. Are you up for adding a simple example there in the style that the other examples are shown? Then in the CI config for circleCI, we will need to add a similar step for git installing dodiscover to make the documentation work since you'll be using dodiscover.

In addition, you'll need to add a changelog entry under doc/whats_new/v0.2.rst

Lmk what you think and if there are any questions?

[aryan26roy]

Sounds straightforward @adam2392. Do you need the example and CI changes to go into this PR itself?