Perhaps more importantly, I think with Node Introduction we really don’t need M←X→N after all?
With Node Introduction and some bookkeeping, we can get the N and M graphs topologically compatible, and Frankenstein them. We can’t get as neat a merge as if we also had M←X→N - in particular, we can’t get rid of the arrow M→N. But that’s fine, we were about to draw that arrow in anyway for the next step!
Is something invalid here? Flagging confusion. This is a slightly more substantial claim than the original proof makes, since it assumes strictly less. Downstream, I think it makes the Resample unnecessary.
ETA: it’s cleared up below—there’s an invalid Reorder here (it removes a v-structure).
Mhm, OK I think I see. But X¯i,N,M appear to me to make a complete subgraph, and all I did was redirect the N→M. I confess I am mildly confused by the ‘reorder complete subgraph’ bookkeeping rule. It should apply to the A→B in A→B←C, right? But then I’d be able to deduce A←B←C which is strictly different. So it must mean something other than what I’m taking it to mean.
Maybe need to go back and stare at the semantics for a bit. (But this syntactic view with motifs and transformations is much nicer!)
Oh you’re right, the rule about reordering complete subgraphs is missing some constraints. That’s a mistake on my part.
Thinking about it for ~60 seconds: when reordering a complete subgraph, arrows going out of the subgraph stay the same, but if there’s arrows going in then we may need to introduce new arrows between (former) spouses.
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.
Perhaps more importantly, I think with Node Introduction we really don’t need M←X→N after all?
With Node Introduction and some bookkeeping, we can get the N and M graphs topologically compatible, and Frankenstein them. We can’t get as neat a merge as if we also had M←X→N - in particular, we can’t get rid of the arrow M→N. But that’s fine, we were about to draw that arrow in anyway for the next step!
Is something invalid here? Flagging confusion. This is a slightly more substantial claim than the original proof makes, since it assumes strictly less. Downstream, I think it makes the Resample unnecessary.
ETA: it’s cleared up below—there’s an invalid Reorder here (it removes a v-structure).
I think one of the reorder steps on the bottom line is invalid.
Stock counterexample:
Let Xi and X¯i each be strings of bits. The zeroth bit of each is equal (i.e. X0i=X0¯i); the rest are independent.
M is another bitstring with zeroth bit equal to the zeroth bit of Xi, and all other bits independent of X.
N is a bitstring with zeroth bit equal to the zeroth bit of Xi, with the rest of the bits given by:
odd-numbered bits are the odd-numbered independent bits of M xor independent bits of Xi
even-numbered bits are the even-numbered independent bits of M xor independent bits of X¯i
Then the starting diagrams in your proof are all satisfied, but the final diagram is not.
The step which breaks for this counterexample is the first reorder step on the bottom line.
Mhm, OK I think I see. But X¯i,N,M appear to me to make a complete subgraph, and all I did was redirect the N→M. I confess I am mildly confused by the ‘reorder complete subgraph’ bookkeeping rule. It should apply to the A→B in A→B←C, right? But then I’d be able to deduce A←B←C which is strictly different. So it must mean something other than what I’m taking it to mean.
Maybe need to go back and stare at the semantics for a bit. (But this syntactic view with motifs and transformations is much nicer!)
Oh you’re right, the rule about reordering complete subgraphs is missing some constraints. That’s a mistake on my part.
Thinking about it for ~60 seconds: when reordering a complete subgraph, arrows going out of the subgraph stay the same, but if there’s arrows going in then we may need to introduce new arrows between (former) spouses.
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.