Partially directed cycles in PDAG

[kenneth-lee-ch]

I have the following PDAG

pdag = gum.PDAG()
pdag.addNodes(6)

pdag.addEdge(0,4)
pdag.addEdge(4,3)
pdag.addEdge(3,2)
pdag.addEdge(2,1)
pdag.addEdge(4,1)

pdag.addArc(5,1)
pdag.addArc(5,0)
pdag.addArc(5,4)
pdag.addArc(5,2)

When I try to add an directed edge pdag.addArc(3,1),

it throws an error saying I create a partially directed cycle.I think this is a bug because I think the code how come reasons there can be directed cycle, but if that's the case, I can form a undirected triangle and the code should the same error as well, but it doesn't.

[phwuil]

Hi @kenneth-lee-ch , as far as I understand PDAG, 1--2--3->1 is not allowed. On the other hand, adding the edge 3--1 is allowed since there are several ways to orient the undirected cycle 1--2--3--1 without creating a directed cycle. Please tell me if you disagree !

[kenneth-lee-ch]

@phwuil I disagree. Why is 1--2--3->1 not allowed since there also exists several ways to orient the graph without creating a directed cycle?

[phwuil]

Ok, so, according to Interpreting and using CPDAGs with background knowledge, there is a confusion in pyAgrum between PDAG and CPDAG. PDAG accept partially directed cycle and cpdag does not.

Indeed if you add 3->1, following the Meek rules, you should finish with 2->3->1<-2

So I guess that we should clarify and create a class for PDAG and a class for CPDAG ...
If you agree, I will do that for the next release (1.11, before 2024)

[kenneth-lee-ch]

I am a bit confused why you need to create a separate class for CPDAG because every CPDAG is a PDAG. I think the interpretation of partially directed cycle is off. CPDAG still allows the structure I previously described. In your example,1--2--3->1 is still allowed in CPDAG so long we don't have `1->2' or '2->3' because Meek rule would have oriented '2<-3' (in the case of '1->2') or '1<-2' (in the case of '2->3')

[phwuil]

I think we have to create different class because of the different forbidden cycles.

We already have a class DAG which is a DiGraph that does not allow cycle.
We should have a class PDAG which is a mixed graph that does not allow directed cycle and CPDAG which is a mixed graph that does not allow partially directed cycle.

Indeed we may have different behaviour. For instance : the layout of a CPDAG will not be the same as the layout for a PDAG)

The idea of layers of undirected connected subgraph is correct only for CPDAG, isnt it ?

[kenneth-lee-ch]

I think p.cSeparation(0,2,[1,3,4]) should be True.

[phwuil]

0 and 2 are parents of the same unoriented (chain) component (1-3). Then by moralization, they are linked in the moralized ancestral graph. Since they are linked in the ancestral graph, they are not separated by 1,3,4 and then they are not c-separated.

[kenneth-lee-ch]

@phwuil Do you have a d-separation function for the classes of CPDAG/MPDAG? In this example, I would imagine that 1<-3 cannot happen so that you can only have 1->3 and therefore conditioning on 1 completely blocks the path from 0 to 2.

[phwuil]

In the nightly builds (and in the next release), you can

1. complete your CPDAG with the class MeekRules and then
2. use dSeparation

By the way, the current nightly build (and the next tag) also introduces

• gum::fastGraph (as you can see) that can build DiGraph, MixedgGraph and UndiGraph.
• graph (and GraphicalModesl) are now "pickelable" :-)

[phwuil]

... and you also have g.adjacencyMatrix() now