A function to determine whether an inducing path exists between two nodes

[adam2392]

Is your feature request related to a problem? Please describe.
An inducing path defined in [1]_ is central to extending reasoning of DAGs to MAG/PAGs, so it makes sense that we should expose an algorithm for computing inducing paths

Describe the solution you'd like
Implement a function in the algorithms submodule with the API:

inducing_path(G, node_x, node_y, relative_to=None) -> Tuple[bool, path], which checks whether a path exists and if it does, it returns the path. We do not necessarily need to check all paths though(?) That is up for discussion I guess.

Additional context
[1]: https://reader.elsevier.com/reader/sd/pii/S0004370208001008?token=4B17FC536FD415013F477F7092BFDCC8861C4A6C05FB9562DA2A15DE777CD23D132FA76C0ECAE9B59FE84EADAC54959F&originRegion=us-east-1&originCreation=20230322132043

This will then enable someone to implement the DAGtoMAG algorithm.

[adam2392]

@aryan26roy perhaps you're interested in this issue first. As it is somewhat of a sub procedure that might be relevant in #73

I feel like #73 has a lot of moving components, so it might make sense to start with a more self-contained issue. Then, you can revisit #73 once the sub-parts are implemented.

Lmk wdyt.

[aryan26roy]

@adam2392 I don't mind taking this one up. Is there an implementation of this available somewhere?

[adam2392]

I think in Tetrad there is: existsInducingPath, if you want to take a look at that code for inspiration. You can also take a look at the graphical definition paraphrased here (you should take a look at the official one too tho):

• In an ancestral graph, let X, Y be any two vertices, and L, S be two disjoint sets of vertices not
  containing X, Y . A path p between X and Y is called an inducing path relative to〈L, S〉 if every non-endpoint vertex on p is either in L or a collider, and every collider on p is an ancestor of either X , Y , or a member of S.

L and S can be empty sets.

This is basically some graph traversal algorithm from X to Y where one needs to check if the nodes on the path satisfy the conditions stated.

[adam2392]

It is a sub-procedure because the existence of an inducing path between two nodes implies that they should be adjacent in a MAG and also, every pair of nodes in a MAG/PAG that are non-adjacent should not have an inducing path between them.

In other words, an inducing path is a path that cannot be blocked (hence the two endpoint nodes are always d-connected)

[aryan26roy]

@adam2392 I have a couple of questions:

• If the user doesn't provide L or S (we assume them to be empty sets) do I construct a maximal L and S? (By maximal I mean an L containing every non-collider and an S containing all colliders sans the ancestors of X and Y)
• Does the graph traversal need to happen through only directed and bi-directed edges? If yes, do we exclude graph types that have undirected or circle edges or just do the procedure on their directed and bi-directed sub-graphs?

[adam2392]

@adam2392 I have a couple of questions:

• If the user doesn't provide L or S (we assume them to be empty sets) do I construct a maximal L and S? (By maximal I mean an L containing every non-collider and an S containing all colliders sans the ancestors of X and Y)

L and S are user-provided. If they are not provided, they are the empty set. The rest of the algorithm works regardless E.g. a collider is still a collider.

• Does the graph traversal need to happen through only directed and bi-directed edges?

Yes.