FCI background-knowledge orientation overcommits PAG endpoints (fci_orient_bk places a spurious tail on forbidden directions)

I am submitting this bug report for Clark Glymour, who diagnosed the bug and reported it to me.

Summary

When FCI is run with tiered (or forbidden-edge) background knowledge, fci_orient_bk orients a constrained edge as a fully directed edge. This places an arrowhead at the constrained endpoint (correct) and a tail at the other endpoint (not licensed). The result is that a correct A o-> B is turned into A --> B, asserting more than the background knowledge supports — including the absence of latent confounding on that edge, which the circle was there to leave open.

Minimal symptom

Take a linear-Gaussian model over {X, Z, Q, Y} with an unmeasured confounder U:

X -> Z,  X -> Y,  U -> Z,  U -> Y,  Z -> Q,  Q -> Y     (U latent)

The correct PAG has Z o-> Y: Z is an ancestor of Y (via Z -> Q -> Y), so the arrowhead at Y is right, but the circle at Z is required because U -> Z together with U -> Y admits a hidden common cause of Z and Y in some MAGs of the class.

Now supply the background knowledge "Y is a sink" as tiers ({X, Z, Q} in tier 0, Y in tier 1). Running FCI with this knowledge returns Z --> Y instead of Z o-> Y. The tail at Z is wrong: it claims Z is a definite ancestor of Y with no latent confounding on the Z–Y path, which is false in this model.

Running FCI with no background knowledge returns the correct Z o-> Y, identical to TETRAD. Only the background-knowledge path is affected.

Why this is incorrect (PAG semantics)

Forbidding Y -> Z means Y is not an ancestor of Z. On the Y–Z edge that licenses exactly one mark: an arrowhead at Y. It says nothing about the endpoint at Z, which should remain whatever the orientation rules determine (here, a circle). Writing a tail at Z is an additional claim that the knowledge does not warrant.

Root cause

In causallearn/search/ConstraintBased/FCI.py, fci_orient_bk (currently around lines 269–291) handles a forbidden direction by removing the edge and calling add_directed_edge, which writes a tail at one end and an arrowhead at the other:

if bk.is_forbidden(edge.get_node1(), edge.get_node2()):
    graph.remove_edge(edge)
    graph.add_directed_edge(edge.get_node2(), edge.get_node1())   # full --> edge

Because this runs inside rule0 (right after everything is reset to circles) and before the R1–R10 loop, the spurious tail is planted early and the orientation rules never revert it. The two is_required branches are fine — a required edge genuinely is fully directed — so only the two forbidden branches are at issue.

For comparison, TETRAD enforces the same constraint with a single-endpoint write. In FciOrient.fciOrientbk, a forbidden from -> to is handled by setEndpoint(to, from, Endpoint.ARROW) — an arrowhead at from only, leaving the other endpoint untouched (required edges set tail-at-from plus arrow-at-to). TETRAD's surrounding ruleR0 runs the identical reorientAllWith(CIRCLE) -> BK -> collider-orientation sequence before its rule loop, so the two implementations differ only in this one step: the port substituted a full add_directed_edge for TETRAD's single setEndpoint(..., ARROW), and that substitution is the defect.

Suggested fix

Set only the arrowhead at the constrained endpoint and preserve the other endpoint, mirroring the idiom already used by ruleR2 (graph.add_edge(Edge(node_a, node_c, edge1.get_proximal_endpoint(node_a), Endpoint.ARROW))). Note GeneralGraph.set_endpoint is not implemented, so the remove-then-add_edge(Edge(...)) pattern is the established way to set a single endpoint.

for edge in edges:
    node1, node2 = edge.get_node1(), edge.get_node2()
    if bk.is_forbidden(node1, node2):
        # node1 cannot cause node2 -> arrowhead at node1, leave node2 endpoint alone
        far_end = edge.get_proximal_endpoint(node2)
        graph.remove_edge(edge)
        graph.add_edge(Edge(node1, node2, Endpoint.ARROW, far_end))
    elif bk.is_forbidden(node2, node1):
        far_end = edge.get_proximal_endpoint(node1)
        graph.remove_edge(edge)
        graph.add_edge(Edge(node1, node2, far_end, Endpoint.ARROW))
    elif bk.is_required(node1, node2):
        graph.remove_edge(edge)
        graph.add_directed_edge(node1, node2)
    elif bk.is_required(node2, node1):
        graph.remove_edge(edge)
        graph.add_directed_edge(node2, node1)

Since this runs after the reset to circles, far_end will be a circle in practice, yielding Z o-> Y. And because the arrowhead is now in place before R1–R10, the knowledge propagates through the rule loop normally rather than needing any post-hoc endpoint patch.

Related but distinct

This is distinct from the existing open background-knowledge issues and should not be folded into them:

• #219 ("Background knowledge not working") is about a forbidden direction not removing the adjacency — the report expects get_edge(...) to return None. That conflates forbidding an orientation (add_forbidden_by_node(a, b) forbids a -> b) with forbidding an edge; the adjacency comes from the skeleton, so the edge legitimately remains, oriented the only allowed way. The problem reported here is the opposite kind of error: the orientation that is applied writes more than the knowledge licenses (the extra tail). Note that the both-directions workaround suggested in that thread does not address this — for FCI the two forbidden branches are if/elif, so forbidding both directions still yields a directed edge and still injects the spurious tail described above.
• #171 and #90 concern forbidden pairs not being skipped during the skeleton (FAS) phase — a performance / CI-testing matter, not orientation.

None of these reaches the endpoint-semantics issue above.