Class FcitKeepKnowledgeOrientations

java.lang.Object
edu.cmu.tetrad.search.FcitKeepKnowledgeOrientations
All Implemented Interfaces:
IGraphSearch
public final class FcitKeepKnowledgeOrientations extends Object implements IGraphSearch
The FCI Targeted Testing (FCIT) algorithm: learns a PAG from observational data with latent variables. BOSS/GRaSP supplies the initial CPDAG; its DAG member is projected to the initial Markov PAG G_0 (dagToPag); a testing phase then removes spurious edges one at a time, retaining a removal only when the from-scratch reorientation passes the PAG legality check, and closes with a saturating pass.

KEEP-KNOWLEDGE VARIANT. This class is the knowledge-orientation-keeping variant of Fcit, applying to FCIT the same treatment StarFciKeepKnowledgeOrientations applies to StarFci (formerly StarFciGuaranteePag). In Fcit, background knowledge enters the initial PAG (dagToPag is knowledge-aware) but is then lost at the first committed removal: the from-scratch reorientation (redoGfciOrientation) does not apply fciOrientbk, and the strict legality certificate (PagLegalityCheck.isLegalPag, whose final step is exact equality with the canonical PAG of the implied Zhang MAG) rejects any graph carrying knowledge marks beyond the invariant marks, so committed graphs are always canonical. Changes from Fcit (2026-8): (1) redoGfciOrientation applies fciOrientbk immediately after the reorient-to-circles step, so every candidate reorientation carries the knowledge marks; (2) both commit gates (single-edge and saturating) use the modulo-knowledge certificate legalPagModuloKnowledge instead of the strict one: the candidate must equal the canonical PAG of its implied Zhang MAG after that canonical PAG is re-refined with fciOrientbk and re-closed under the final rules, so every mark is either invariant or knowledge-forced. When knowledge is empty the certificate degenerates to exactly PagLegalityCheck.isLegalPag and this class behaves like Fcit. The illegal-state memo remains sound: knowledge is a fixed input for the run, so the certificate is still a deterministic function of (skeleton, sepsets). As in the Star variant, when knowledge conflicts with data-derived invariant structure the knowledge-refined candidate fails the certificate and the removal is reverted -- knowledge loses conservatively; that is a deliberate, contestable modeling choice.

Conformance to the RB paper's theory. This implementation realizes the FCIT (PAG -> PAG) procedure of the Algorithmic Consequences section:

  1. Deletion step (Def. rb-step). Each candidate removal is proposed by a single shared sweep (sweepForSepset(Graph, Node, Node, long, Set)): recursive blocking supplies a base blocking set; a not-followed (NF) outer layer enumerates subsets of the ambiguous (circle-bearing) members of that set; an inner layer enumerates removals over the whole base (common neighbors first) and additions over common neighbors omitted from the base. Every candidate is adjudicated by the independence test; the graph view only proposes, never decides.
  2. Conflict-driven mark-flip escalation (Rem. mark-flip). When the sweep against the live, marked PAG finds nothing, the walk reports the arrowheads its blocked-collider verdicts relied on, and the sweep is re-run on views that each distrust exactly one of those marks (arrowhead -> circle). This repairs the displacement mechanism -- a propagated unsound arrowhead whose false definite collider hides the true blocker -- with hypotheses nominated by the failure itself, bounded by the load-bearing marks encountered rather than by any pool's powerset.
  3. Recorded, not live (P1/P2). Committed separators live in sepsets; separators recorded by R4 during a candidate reorientation are written to a per-candidate scratch copy of that map, adopted wholesale on commit and discarded wholesale on revert, so no entry recorded against a rejected state survives. Unrecorded R4 endpoint pairs are additionally computed against the frozen initial PAG G_0 (setSepsetGraph), never the live mid-reorientation graph.
  4. Saturating pass (Cor. saturation / Thm. algorithm, phase 2). When no single-edge removal commits, every still-adjacent pair whose separator has been test-confirmed (the foundSepsets record, which survives reverts) is deleted simultaneously and the graph reoriented once from scratch. Under the oracle and out-of-B coverage the result is the legal Markov PAG G*; the pass is therefore accepted when legal, and a loud diagnostic is emitted when it is not (finite-sample test error, coverage failure, or a bug -- exactly what an oracle harness should catch).
  5. Detection and discharge. The final scan over discriminating-path legs confirms spuriousness by the same sweep plus the test (never by a graphical proposal alone); a newly confirmed leg is recorded and fed back to the removal/saturation machinery. Indeterminate outcomes (deadline expiries, cap truncations) are propagated into the final report rather than the graph being certified phantom-free (Rem. three-valued / Rem. one-copy).
  6. Determinism. All candidate lists are name-sorted, edges are scanned in a canonical order, and only the winning (lowest-index) speculative search of each parallel lookahead phase records its separator, so the recorded separator for a pair is a deterministic function of the committed history -- the one-canonical-separator convention.
Author:
josephramsey

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static enum 
    FcitKeepKnowledgeOrientations.START_WITH
    Enumeration representing different start options.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static boolean
    useTestCache
    Whether the constructor wraps the supplied test in CachedIndependenceQueries.

  • Constructor Summary

    Constructors
    Constructor
    Description
    FcitKeepKnowledgeOrientations(IndependenceTest test, Score score)
    FCIT constructor.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    getRecursiveDepth()
    Retrieves the current depth of recursion.
    IndependenceTest
    getTest()
    Gets the test used by the search.
    Graph
    search()
    Run the search and return a PAG.
    void
    setAuditLegalityMemo(boolean auditLegalityMemo)
    Turns the legality memo into an audit: hits are recomputed and mismatches logged, verifying that reorientation is deterministic given (skeleton, sepsets).
    void
    setCompleteRuleSetUsed(boolean completeRuleSetUsed)
    Sets whether the Zhang complete rule set should be used; false if only R1-R4 (the rule set of the original FCI) should be used.
    void
    setDepth(int depth)
    Sets the depth of search, which is the maximum number of variables conditioned on in any test.
    void
    setDetectionEnabled(boolean detectionEnabled)
    Sets whether the final discriminating-path detection scan runs.
    void
    setExcludeSelectionBias(boolean excludeSelectionBias)
    Sets whether selection bias should be excluded during the search process.
    void
    setGraspUseRaskuttiUhler(boolean graspUseRaskuttiUhler)
    Sets whether GRaSP, when used as the starting algorithm, should use the Raskutti-Uhler test-based method instead of the score-based method.
    void
    setImapAlpha(double imapAlpha)
    Sets the significance level of the I-map gate's tests (default 0.001); see CorrectnessGates.setImapAlpha(double).
    void
    setKnowledge(Knowledge knowledge)
    Sets the knowledge used in search.
    void
    setLogFinalOrientations(boolean logFinalOrientations)
    Sets whether the FCI orientation engine logs its rule-by-rule output (R1-R4 firings, discriminating-path stamps).
    void
    setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)
    Sets the maximum length of the discriminating path.
    void
    setMaxMarkFlips(int maxMarkFlips)
    Caps the number of single-mark flip hypotheses tried per pair by the mark-flip escalation.
    void
    setMaxTestsPerPair(long maxTestsPerPair)
    Sets a deterministic per-pair budget on independence tests, across all views.
    void
    setNumStarts(int numStarts)
    Sets the number of starts for BOSS.
    void
    setQuickSubsetDepth(int quickSubsetDepth)
    Sets the cap for the small-subset shortcut pass; -1 disables it.
    void
    setRbRadius(int rbRadius)
    Sets the radius for the RB (Recursive Blocking) conditioning pool.
    void
    setRecursiveDepth(int recursiveDepth)
    Sets the depth level for recursive operations.
    void
    setReplicatingGraph(boolean replicatingGraph)
    Sets the flag indicating whether the graph should be replicated during the search process.
    void
    setRequireImapStates(boolean requireImapStates)
    Turns the I-map gate on or off (default off); see CorrectnessGates.setRequireImapStates(boolean).
    void
    setRequireNoScoreDrop(boolean requireNoScoreDrop)
    Turns the score step on or off (default off).
    void
    setRetrySepsetsOnRevert(boolean retrySepsetsOnRevert)
    Sets whether, after a gated removal reverts, the remaining data-valid separators for the pair are tried in canonical order until one commits.
    void
    setStartWith(FcitKeepKnowledgeOrientations.START_WITH startWith)
    Sets the algorithm to use to get the initial CPDAG.
    void
    setSuperVerbose(boolean superVerbose)
    Sets the verbosity level of the search algorithm.
    void
    setSweepAddMaxSize(int sweepAddMaxSize)
    Caps the size of addition subsets in the sweep's inner layer.
    void
    setSweepNfMaxSize(int sweepNfMaxSize)
    Caps the size of not-followed subsets in the sweep's outer layer.
    void
    setSweepRemoveMaxSize(int sweepRemoveMaxSize)
    Caps the size of removal subsets in the sweep's inner layer.
    void
    setTimeout(long timeout)
    Sets the timeout for per-edge separator searches, or -1 for unlimited.
    void
    setUseBes(boolean useBes)
    Sets whether to use the BES (Backward Elimination Search) algorithm during the search.
    void
    setUseDataOrder(boolean useDataOrder)
    Sets the flag indicating whether to use data order.
    void
    setUseMarkFlipEscalation(boolean useMarkFlipEscalation)
    Sets whether the conflict-driven mark-flip escalation runs when the live-view sweep fails for a pair.
    void
    setUseSaturatingStep(boolean useSaturatingStep)
    Sets whether the saturating pass (joint removal of all test-confirmed spurious pairs when no single-edge removal commits) runs.
    void
    setVerbose(boolean verbose)
    True just in case good and restored changes are printed.

    Methods inherited from class Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface IGraphSearch

    setTest

  • Field Details

    • useTestCache

      public static boolean useTestCache
      Whether the constructor wraps the supplied test in CachedIndependenceQueries. Static because it must be decided before construction. Set false for tests with internal randomness where repeated-query consistency is not wanted.

  • Constructor Details

    • FcitKeepKnowledgeOrientations

      public FcitKeepKnowledgeOrientations(IndependenceTest test, Score score)
      FCIT constructor.
      Parameters:
      test - The IndependenceTest object to be used for testing independence between variables.
      score - The Score object to be used for scoring DAGs.
      Throws:
      NullPointerException - if the test or score is null.

  • Method Details

    • getTest

      public IndependenceTest getTest()
      Description copied from interface: IGraphSearch
      Gets the test used by the search.
      Specified by:
      getTest in interface IGraphSearch
      Returns:
      The test used by the search.

    • search

      public Graph search() throws InterruptedException
      Run the search and return a PAG.
      Specified by:
      search in interface IGraphSearch
      Returns:
      The PAG.
      Throws:
      InterruptedException - if any

    • setStartWith

      public void setStartWith(FcitKeepKnowledgeOrientations.START_WITH startWith)
      Sets the algorithm to use to get the initial CPDAG.
      Parameters:
      startWith - the algorithm to use to get the initial CPDAG.

    • setKnowledge

      public void setKnowledge(Knowledge knowledge)
      Sets the knowledge used in search.
      Parameters:
      knowledge - This knowledge.

    • setSuperVerbose

      public void setSuperVerbose(boolean superVerbose)
      Sets the verbosity level of the search algorithm.
      Parameters:
      superVerbose - true to enable superVerbose mode, false to disable it

    • setLogFinalOrientations

      public void setLogFinalOrientations(boolean logFinalOrientations)
      Sets whether the FCI orientation engine logs its rule-by-rule output (R1-R4 firings, discriminating-path stamps). Independent of verbose; OR'd with superVerbose for the engine, so superVerbose alone behaves as before.
      Parameters:
      logFinalOrientations - True, if so.

    • setVerbose

      public void setVerbose(boolean verbose)
      True just in case good and restored changes are printed.
      Parameters:
      verbose - True if changes to the graph should be printed.

    • setNumStarts

      public void setNumStarts(int numStarts)
      Sets the number of starts for BOSS.
      Parameters:
      numStarts - The number of starts.

    • setUseBes

      public void setUseBes(boolean useBes)
      Sets whether to use the BES (Backward Elimination Search) algorithm during the search.
      Parameters:
      useBes - true to use the BES algorithm, false otherwise

    • setUseDataOrder

      public void setUseDataOrder(boolean useDataOrder)
      Sets the flag indicating whether to use data order.
      Parameters:
      useDataOrder - true if the data order should be used, false otherwise.

    • setGraspUseRaskuttiUhler

      public void setGraspUseRaskuttiUhler(boolean graspUseRaskuttiUhler)
      Sets whether GRaSP, when used as the starting algorithm, should use the Raskutti-Uhler test-based method instead of the score-based method. Ignored unless the start-with option is GRaSP.
      Parameters:
      graspUseRaskuttiUhler - True to use the Raskutti-Uhler method.

    • setCompleteRuleSetUsed

      public void setCompleteRuleSetUsed(boolean completeRuleSetUsed)
      Sets whether the Zhang complete rule set should be used; false if only R1-R4 (the rule set of the original FCI) should be used. True by default.
      Parameters:
      completeRuleSetUsed - True for the complete Zhang rule set.

    • setDepth

      public void setDepth(int depth)
      Sets the depth of search, which is the maximum number of variables conditioned on in any test.
      Parameters:
      depth - This maximum.

    • setReplicatingGraph

      public void setReplicatingGraph(boolean replicatingGraph)
      Sets the flag indicating whether the graph should be replicated during the search process.
      Parameters:
      replicatingGraph - true to enable graph replication, false otherwise.

    • setExcludeSelectionBias

      public void setExcludeSelectionBias(boolean excludeSelectionBias)
      Sets whether selection bias should be excluded during the search process.
      Parameters:
      excludeSelectionBias - True to exclude selection bias, false otherwise.

    • setRbRadius

      public void setRbRadius(int rbRadius)
      Sets the radius for the RB (Recursive Blocking) conditioning pool.
      Parameters:
      rbRadius - the radius to be set (-1 for unlimited)

    • getRecursiveDepth

      public int getRecursiveDepth()
      Retrieves the current depth of recursion.
      Returns:
      the depth of recursion as an integer

    • setRecursiveDepth

      public void setRecursiveDepth(int recursiveDepth)
      Sets the depth level for recursive operations.
      Parameters:
      recursiveDepth - the maximum depth to which the recursion is allowed

    • setMaxDiscriminatingPathLength

      public void setMaxDiscriminatingPathLength(int maxDiscriminatingPathLength)
      Sets the maximum length of the discriminating path.
      Parameters:
      maxDiscriminatingPathLength - the maximum number of steps or nodes allowed in the discriminating path.

    • setTimeout

      public void setTimeout(long timeout)
      Sets the timeout for per-edge separator searches, or -1 for unlimited. Wall-clock, hence nondeterministic; prefer setMaxTestsPerPair(long) in experiments that must be reproducible.
      Parameters:
      timeout - the maximum time in milliseconds per edge.

    • setSweepNfMaxSize

      public void setSweepNfMaxSize(int sweepNfMaxSize)
      Caps the size of not-followed subsets in the sweep's outer layer.
      Parameters:
      sweepNfMaxSize - the cap, or -1 for unlimited (the full family).

    • setSweepAddMaxSize

      public void setSweepAddMaxSize(int sweepAddMaxSize)
      Caps the size of addition subsets in the sweep's inner layer.
      Parameters:
      sweepAddMaxSize - the cap, or -1 for unlimited.

    • setSweepRemoveMaxSize

      public void setSweepRemoveMaxSize(int sweepRemoveMaxSize)
      Caps the size of removal subsets in the sweep's inner layer.
      Parameters:
      sweepRemoveMaxSize - the cap, or -1 for unlimited.

    • setMaxTestsPerPair

      public void setMaxTestsPerPair(long maxTestsPerPair)
      Sets a deterministic per-pair budget on independence tests, across all views. Exhaustion yields an indeterminate sweep.
      Parameters:
      maxTestsPerPair - the cap, or -1 for unlimited.

    • setAuditLegalityMemo

      public void setAuditLegalityMemo(boolean auditLegalityMemo)
      Turns the legality memo into an audit: hits are recomputed and mismatches logged, verifying that reorientation is deterministic given (skeleton, sepsets). Slower than either memo-on or memo-off; diagnostic use only.
      Parameters:
      auditLegalityMemo - false by default.

    • setDetectionEnabled

      public void setDetectionEnabled(boolean detectionEnabled)
      Sets whether the final discriminating-path detection scan runs.
      Parameters:
      detectionEnabled - true by default.

    • setUseSaturatingStep

      public void setUseSaturatingStep(boolean useSaturatingStep)
      Sets whether the saturating pass (joint removal of all test-confirmed spurious pairs when no single-edge removal commits) runs. With it off, such pairs are reported by the final scan as undischarged rather than removed, and the oracle-correctness guarantee is forfeited.
      Parameters:
      useSaturatingStep - true by default.

    • setRetrySepsetsOnRevert

      public void setRetrySepsetsOnRevert(boolean retrySepsetsOnRevert)
      Sets whether, after a gated removal reverts, the remaining data-valid separators for the pair are tried in canonical order until one commits. Changes trajectories; re-certify (PKE12) before trusting a configuration with this on.
      Parameters:
      retrySepsetsOnRevert - false by default.

    • setQuickSubsetDepth

      public void setQuickSubsetDepth(int quickSubsetDepth)
      Sets the cap for the small-subset shortcut pass; -1 disables it. Non-default values change trajectories and require re-validation.
      Parameters:
      quickSubsetDepth - the cap, or -1 for off (default).

    • setRequireImapStates

      public void setRequireImapStates(boolean requireImapStates)
      Turns the I-map gate on or off (default off); see CorrectnessGates.setRequireImapStates(boolean).
      Parameters:
      requireImapStates - true to require every committed state to introduce no uncertified independence.

    • setRequireNoScoreDrop

      public void setRequireNoScoreDrop(boolean requireNoScoreDrop)
      Turns the score step on or off (default off). Kept under its historical name; since 2026-11-08 the rule is the one shared with the *-FCI family through CorrectnessGates: a legal candidate's Zhang MAG must score STRICTLY above the committed state's by more than SCORE_EPSILON, not merely not drop. Requires a SemBicScore built on a covariance matrix with zero structure prior; refused with the time-lag replicating-graph wrapper.
      Parameters:
      requireNoScoreDrop - true to turn the score step on.

    • setImapAlpha

      public void setImapAlpha(double imapAlpha)
      Sets the significance level of the I-map gate's tests (default 0.001); see CorrectnessGates.setImapAlpha(double).
      Parameters:
      imapAlpha - a level in [0, 1].

    • setUseMarkFlipEscalation

      public void setUseMarkFlipEscalation(boolean useMarkFlipEscalation)
      Sets whether the conflict-driven mark-flip escalation runs when the live-view sweep fails for a pair. False gives the trajectory-trusting core alone (the ablation baseline).
      Parameters:
      useMarkFlipEscalation - true by default.

    • setMaxMarkFlips

      public void setMaxMarkFlips(int maxMarkFlips)
      Caps the number of single-mark flip hypotheses tried per pair by the mark-flip escalation.
      Parameters:
      maxMarkFlips - the cap, or -1 for unlimited; 16 by default.