[ENH] Add required/excluded edge directions in the orientation phase of PC/FCI

[adam2392]

Summary

Required and excluded edges are not taken into account at the orientation phase (i.e. setting edge directions) of constraint-based structure learning algos.

There are a few challenges though to tackle:

1. how to warn users that the resulting object may not obey the definition of a CPDAG/PAG
2. whether or not to set these in the skeleton phase (so they are not tested with CI tests), or to set these at the orientation level after CI tests have been run

Misc. reference

"Required edges and excluded edges are built into the LearnSkeleton class rn meaning they do not account for directionality. However, these can also be taken into account at the orientation phase...

There currently is a tradeoff that theory has yet to answer:

• inside skeleton phase: you just initially set the adjacencies based on this prior info.
• inside orientation phase: you could orient additional edges

^ the nuanced challenge here is that the resulting object is NOT a CPDAG/PAG, and thus would not be expected to work with the downstream ID/Estimation algorithms that assume an input CPDAG/PAG. I'm leaning towards passing in a warning str to the graph object that when printed out, warns users to not use them in ID/estimation if they set prior edges that might break the conditional-independence statements.

Originally posted by @adam2392 in #30 (comment)"

[jaron-lee]

Would this be the right place to include the knowledge tiers functionality that TETRAD currently has? E.g. I group variables into X groups, where variables in group i can only point to groups i+1 or greater. In some sense you could implement tiers by excluding a whole lot of edges but maybe a nicer API could be exposed to do this instead.

This would also require directional excluded edges, so I would vote for doing so in the orientation phase.

[jaron-lee]

Also is there a technical reason that would prevent us implementing both kinds of prior knowledge?

As a concrete example I've done some structure learning applied to cardiac data. When talking to physicians the kinds of knowledge I was able to solicit was grouping variables into tiers (e.g. pre, intra, and post operation), and also ruling out certain edge directions (due to medical domain knowledge). I don't think we ruled out adjacencies between any variables in that particular example, but in general I could see this happening if the domain knowledge was weaker.

[adam2392]

@jaron-lee

Would this be the right place to include the knowledge tiers functionality that TETRAD currently has? E.g. I group variables into X groups, where variables in group i can only point to groups i+1 or greater. In some sense you could implement tiers by excluding a whole lot of edges but maybe a nicer API could be exposed to do this instead.

I think the idea of placing edges into knowledge tiers would be nice, and could potentially be represented graphically (in code) perhaps as a Cluster-DAG? Or perhaps, ex/included_edges is a list of tuples of ... sets? Where each element in the list is a tuple of variable(s), and within each tuple is a set of variables representing included/excluded edges between the two sets. E.g.

# x has an edge to y and z
# z has an edge to w
included_edges = [
  ( {'x'}, {'y', 'z'}),
  ({'z'}, {'w'}),
]

This would also require directional excluded edges, so I would vote for doing so in the orientation phase.

You mean including directional excluded edge information in the orientation phase and not skeleton phase?

Also is there a technical reason that would prevent us implementing both kinds of prior knowledge?

No. Not really imo. We can really come up with an arbitrary API for all sorts of background knowledge to stick into the learning algorithm, but the one thing to be cognizant of is that the resulting object may not be a CPDAG/PAG, and hence the resulting equivalence-class ID/estimation algorithms cannot be used on those objects off the shelf. But for the purposes of just structure learning, yeah sure. I think we just stuck in what was common so far in #30

[jaron-lee]

Regarding your first point the list of tuples of sets would probably work in the first instance. You could have an included_edges and excluded_edges list. It's not clear to me at this stage that using a graph data structure would help but that will probably become clear in the implementation.

Regarding your second point, yes.

Regarding your third point, that's probably true in general but I could probably see instances where you do end up with a CPDAG/PAG anyways. Then I assume the downstream algorithms would have the responsibility of checking that their input is not a CPDAG/PAG and fail there?

Happy to try implementing this issue.

[adam2392]

Regarding your first point the list of tuples of sets would probably work in the first instance. You could have an included_edges and excluded_edges list. It's not clear to me at this stage that using a graph data structure would help but that will probably become clear in the implementation.

Yes you're right, I just opted for a graph structure to be very explicit about what edges are passed in. The nice thing with an explicit graph structure, is that you have access to the networkx API to do any type of error checking, or utility functions on the included/excluded_edges, such as make sure there are no extra nodes that are not present in the dataset. Using a list of tuples is prolly fine too...

Regarding your third point, that's probably true in general but I could probably see instances where you do end up with a CPDAG/PAG anyways. Then I assume the downstream algorithms would have the responsibility of checking that their input is not a CPDAG/PAG and fail there?

True, but I suppose what we really want then is a utility function somewhere to check the validity of a CPDAG/PAG? However, I'm not aware of a solution to this problem. Do you need the dataset? Is it something you can check just based on the structure?

Either way, I'm pretty keen on the ability for the included/excluded_edges to also have the option to be implemented on the orientation phase, rather than skeleton phase and figuring out how to validate CPDAG/PAG later on...

Happy to try implementing this issue.

There are a few separate things being discussed here.

Firstly is the inclusion/exclusion of edges at the orientation phase. How should the API look like? Should it be separate from the inclusion/exclusion at the skeleton phase, which is what is implemented right now? Would this be a kwarg inside the structure learning algorithms themselves? e.g.

alg = PC(..., apply_prior_edge='orientation') vs alg = PC(..., apply_prior_edge='skeleton')

or would this be applied somewhere else?

Secondly, you are proposing knowledge tiers, which are just "sets" of included/excluded edges I think... This might be doable by just extending the inclusion/exclusion edges for skeleton/orientation phase into a new data structure. That is a list of tuples of sets?

Then the following would be a "knowledge tier"

# x and w cannot point to y and z
excluded_edges = [
  ( {'x', 'w'}, {'y', 'z'}),
]

whereas this would just be the normal inclusion/exclusion of edges

# x has an edge to y and z
# z has an edge to w
included_edges = [
  ( {'x'}, {'y'}), 
  ({'x'}, {'z'}),
  ({'z'}, {'w'}),
]

Misc.

Ideally I can merge in #30 so that way you can build on the PC algo implementation.

[jaron-lee]

Yes you're right, I just opted for a graph structure to be very explicit about what edges are passed in. The nice thing with an explicit graph structure, is that you have access to the networkx API to do any type of error checking, or utility functions on the included/excluded_edges, such as make sure there are no extra nodes that are not present in the dataset. Using a list of tuples is prolly fine too...

Hmm good point. I'll keep that in mind.

True, but I suppose what we really want then is a utility function somewhere to check the validity of a CPDAG/PAG? However, I'm not aware of a solution to this problem. Do you need the dataset? Is it something you can check just based on the structure?

Yeah I am not totally sure either. Maybe a good reason to leave this out in the first pass.

Either way, I'm pretty keen on the ability for the included/excluded_edges to also have the option to be implemented on the orientation phase, rather than skeleton phase and figuring out how to validate CPDAG/PAG later on...

Is this the kind of paper you have in mind when talking about orientation and knowledge? Perkovic et al. 2017

I think this paper talks about background knowledge consisting of directed edges, so this seems like an implementation on the orientation phase. Is there a good paper I should read on orientation in the skeleton phase?

Happy to try implementing this issue.

There are a few separate things being discussed here.

Firstly is the inclusion/exclusion of edges at the orientation phase. How should the API look like? Should it be separate from the inclusion/exclusion at the skeleton phase, which is what is implemented right now? Would this be a kwarg inside the structure learning algorithms themselves? e.g.

alg = PC(..., apply_prior_edge='orientation') vs alg = PC(..., apply_prior_edge='skeleton')

or would this be applied somewhere else?

Is it insane to support certain edges being applied at different phases?

Secondly, you are proposing knowledge tiers, which are just "sets" of included/excluded edges I think... This might be doable by just extending the inclusion/exclusion edges for skeleton/orientation phase into a new data structure. That is a list of tuples of sets?

Yes, knowledge tiers would probably be implemented by just having a utility function that creates the right set of included/excluded edges.

I should also review the TETRAD implementation to see how that is implemented. This issue seemed useful:
cmu-phil/tetrad#1147. First, it notes that tier knowledge is just a list of forbidden edges, which confirms what we were thinking. Also, it seems to indicate that the background knowledge implementation in TETRAD differs from that of pcalg, which means we should probably tread carefully. In particular the Perkovic et al. 2017 paper about PC and background knowledge that I linked above was the basis of implementation in pcalg.

Joe Ramsey gives the following (somewhat cryptic) note on PC's background knowledge:

For PC, you have to start off by orienting all edges whose directions are required by knowledge. Then when checking whether X || Y | S at any point, you have to make sure
S consists only of variables that could potentially be parents of X, IF
parents of X are being considered, or PARENTS of Y, if parents of Y are
being considered. So, for instance, if you have X->Y required by knowledge,
then you can't coNdition on Y if you're coN ditioning on parents of X; it's
not one.
Then all you need to complete the idea is a function called "is arrowpoint allowed" which you can implement in terms of what you know about the background knowledge. Then from there on out, in the final orientation step, you never orient an arrow that doesn't pass this test. I think you can quickly write out a proof that if you follow this advice you will never contravene background knowledge. Exercise left to the reader.

Note that the pcalg implementation can fail if background knowledge is inconsistent with the CPDAG, but it seems like the TETRAD implementation doesn't. And if I understand correctly I think both would be considered orientation phase?