D-connecting paths

[kenneth-lee-ch]

@phwuil Do you know if there is a way to output all d-connecting paths from X to Y relative Z given a PDAG in pyagrum oncecSeparation(X, Y, Z) returns true?

[phwuil]

It is an interesting but unusual question. So there is no direct way to find them. The question is to find all the paths between X and Y in the moralized ancestral graph which are not using nodes in Z. Unfortunately, PDAG.moralizedAncestralGraph() is not wrapped (yet) in pyAgrum. So you have to do it by yourself...

[kenneth-lee-ch]

How come I can see that this function PDAG.moralizedAncestralGraph() is available under PDAG documentation?

[phwuil]

Creating a wrapper is partially automatic with swig. So the function has been wrapped but we have to write a piece of code in order to correctly transform the parameters. If you try to use it, you will see a C++ error about the argument that has to be a gum::NodeSet (or something like that). We have to transform a python sequence of int into this NodeSet. I will try to do that for this function a.s.a.p and you will find it in the pyAgrum-nightly package (you are doomed to stay on a development version :-)

[phwuil]

This should be done in pyAgrum-nightly.

[phwuil]

By the way, for your initial question, just a first answer ... may not be correct, but it is the idea :

def DFS(g,src,target):
    """
    Parameters
    -----------------
    g: undirected graph
    src,target : nodeId
    
    Returns
    -----------
    List[List[int]] : a list of paths (as list of nodes) from src to target in g.
    """
    def recDFS(g,src,target,current,mark,res):
        if src==target:
            res.append(current)
        elif src not in mark:
            mark[src]=1
            for n in g.neighbours(src):
                recDFS(g,n,target,current+[n],mark,res)
            del(mark[src])
    
    res=[]
    current=[src]
    mark={}
    recDFS(g,src,target,current,mark,res)
    return res

For instance :

[phwuil]

This is the generalization of the d-separation(in a DAG)/separation (in an undirected graph)/C-separation (in a PDAG) :

X and Y are separated by Z if all the paths from X to Y in MAG(X+Y+Z) contains node(s) of Z. (if X and Y are not connected in the MAG mutilated by Z).

You can find many references to this on internet (https://arxiv.org/abs/1302.3606v1)

[kenneth-lee-ch]

@phwuil In your first example, [1,3,4,6,7,8,9] and [1,3,4,6,9] don't seem to the d-connecting paths for x=1, y= 9, z= 2 in the original graph. Also, I think 2 should be included in the path.

[phwuil]

These are paths in the moralized ancestral graph ... Particularly, they do not include v-structures that are part of Z (or one of their descendants).

For instance, the path 1-3-4-6-9 in the moralized ncestral graph represent the path 1->2<-3-4<-6<-8-9 in the CPDAG (2 is in Z, and then 9 is connected to 8 by moralization, as ancestors of 2)

[kenneth-lee-ch]

Thanks for the reply! I am not familiar enough with the moralized ancestral graph idea. How can I possibly tweak your code to have the return paths be the d-connecting paths that can be directly read off from the original graph e.g. 1->2<-3-4<-6<-8-9?

[phwuil]

it is complicated. You have to differentiate in the path the real 'edges' and the edges due to moralization (fill-ins). And when the path use such a fill-in, you have to figure out in the PDAG why it exists and then re-build the "true" path in the PDAG.

[kenneth-lee-ch]

It would be great if this can be part of pyagrum functions in the future!

…

On Thu, May 25, 2023, 3:58 AM Pierre-Henri Wuillemin < ***@***.***> wrote: This is the generalization of the d-separation(in a DAG)/separation (in an undirected graph)/C-separation (in a DAG) : X and Y are separated by Z if all the paths from X to Y in MAG(X+Y+Z) contains node(s) of Z. (if X and Y are not connected in the MAG mutilated by Z). You can find many references to this on internet ( https://arxiv.org/abs/1302.3606v1) — Reply to this email directly, view it on GitHub <#15 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AF3Z3CRWSX6TIBELE6FNKXLXH4GL7ANCNFSM6AAAAAAYNYE4J4> . You are receiving this because you authored the thread.Message ID: ***@***.***>

[kenneth-lee-ch]

When should I expect to see the next release that has moralizedAncestralGraph available :) ?

[phwuil]

:-) not so far in june.

pyAgrum-nightly has been correctly updated ?

[kenneth-lee-ch]

Is it the latest release 1.8.1.9.dev202305261685000343?

[phwuil]

yes

[phwuil]

1.8.2 is out ! :-)