pywhy-graphs
pywhy-graphs copied to clipboard
py-why
Convert MAG to PAG
Is your feature request related to a problem? Please describe. A MAG is a mixed-edge graph with directed and bidirected edges and has the 'maximality' property.
This is a sub-procedure of https://github.com/py-why/pywhy-graphs/pull/73 and will enable that to function properly.
Describe the solution you'd like
Implement a function mag_to_pag, which takes in a valid MAG and outputs the corresponding PAG.
Additional context @aryan26roy if you're still interested, this can be the next step before revisiting #73.
I presume tetrad has a function written in java. More importantly, the paper linked in the issue for #73 should contain the relevant algorithm written in the paper to convert a MAG to a PAG.
Perhaps it might make sense to also add a function that takes in a mixed-edge graph with directed and/or bidirected edges (e.g. an ADMG without undirected edges) and checks if it is a valid MAG.
According to Zhang 2008 (https://www.jmlr.org/papers/volume9/zhang08a/zhang08a.pdf), check:
- does graph contain any directed, or almost directed cycles?
- between any two non-adjacent nodes, is there an inducing path? (this is now possible because you have implemented the inducing path algorithm)
This is probably pretty expensive because it scales poorly wrt node count, but imo it's fine as long as we document it because I'm not aware of another cheaper way to check if a MAG is valid. I'm sure a way exists using some fancy Breadth-first-search.
@adam2392 so do you want me to add a method for converting PAG to MAG first or the method for checking the validity of an MAG?
Perhaps checking validity of a MAG(?). There are some graphical examples in the paper.