Aha. Preserving v-structures (colliders like X→Y←Z) is necessary and sufficient for equivalence[1]. So when rearranging fully-connected subgraphs, certainly we can’t do it (cost-free) if it introduces or removes any v-structures.
Plausibly if we’re willing to weaken by adding in additional arrows, there might be other sound ways to reorder fully-connected subgraphs—but they’d be non-invertible. Haven’t thought about that.
Either that’s wrong or I’m misinterpreting it, because a fully-connected DAG should be equivalent to any other fully-connected DAG but they all have different v-structures.
Mmm, I misinterpreted at first. It’s only a v-structure if X and Z are not connected. So this is a property which needs to be maintained effectively ‘at the boundary’ of the fully-connected cluster which we’re rewriting. I think that tallies with everything else, right?
ETA: both of our good proofs respect this rule; the first Reorder in my bad proof indeed violates it. I think this criterion is basically the generalised and corrected version of the fully-connected bookkeeping rule described in this post. I imagine if I/someone worked through it, this would clarify whether my handwave proof of Frankenstein ⟹ Stitch is right or not.
That’s concerning. It would appear to make both our proofs invalid.
But I think your earlier statement about incoming vs outgoing arrows makes sense. Maybe Verma & Pearl were asking for some other kind of equivalence? Grr, back to the semantics I suppose.
Aha. Preserving v-structures (colliders like X→Y←Z) is necessary and sufficient for equivalence[1]. So when rearranging fully-connected subgraphs, certainly we can’t do it (cost-free) if it introduces or removes any v-structures.
Plausibly if we’re willing to weaken by adding in additional arrows, there might be other sound ways to reorder fully-connected subgraphs—but they’d be non-invertible. Haven’t thought about that.
Verma & Pearl, Equivalence and Synthesis of Causal Models 1990
Either that’s wrong or I’m misinterpreting it, because a fully-connected DAG should be equivalent to any other fully-connected DAG but they all have different v-structures.
Mmm, I misinterpreted at first. It’s only a v-structure if X and Z are not connected. So this is a property which needs to be maintained effectively ‘at the boundary’ of the fully-connected cluster which we’re rewriting. I think that tallies with everything else, right?
ETA: both of our good proofs respect this rule; the first Reorder in my bad proof indeed violates it. I think this criterion is basically the generalised and corrected version of the fully-connected bookkeeping rule described in this post. I imagine if I/someone worked through it, this would clarify whether my handwave proof of Frankenstein ⟹ Stitch is right or not.
Unironically, I think it’s worth anyone interested skimming that Verma & Pearl paper for the pictures :) especially fig 2
That’s concerning. It would appear to make both our proofs invalid.
But I think your earlier statement about incoming vs outgoing arrows makes sense. Maybe Verma & Pearl were asking for some other kind of equivalence? Grr, back to the semantics I suppose.