Class FcitSepsets

java.lang.Object
edu.cmu.tetrad.search.utils.FcitSepsets

public final class FcitSepsets extends Object
FCIT's separator search: recursive blocking with an enumerated not-followed set, spanned over all subsets of the common neighbours of the pair.
Author:
josephramsey
  • Method Details

    • spanningSepsetSearch

      public static FcitSepsets.SepsetSearch spanningSepsetSearch(Graph graph, IndependenceTest test, Node x, Node y, int recursiveDepth, int depth, int rbRadius, long deadline, Runnable onTest) throws InterruptedException
      Searches for a set S with x _||_ y | S in the given graph.

      The candidate family is built in two nested layers. Outer: recursive blocking is run once with no constraints to collect the AMBIGUOUS members of its blocking set (those with at least one circle endpoint), and every subset of those is tried as a "not-followed" set, each producing its own blocking set B. Inner: every common neighbour of (x,y) is forced into B, all of them are removal candidates, and the removed subset is enumerated from empty upward -- so "all common neighbours in" is tried first. This guarantees that if the full-retention candidate (every common neighbour in) separates, it is the one returned. It does NOT guarantee retention pairwise: with common = {c, d}, the order tries removing {c} before {d}, so a valid separator excluding c can be returned while an equal-size one retaining c exists. (Harmless for soundness: on the true skeleton a real non-collider c lies in every separator of the pair, and off the true skeleton R0 stamps are not sound in general anyway.)

      The first set the test confirms independent is returned.

      Parameters:
      graph - the graph to search (FCIT passes its working PAG)
      test - the independence test (an oracle, in harness use)
      x - one endpoint
      y - the other endpoint
      recursiveDepth - recursive-blocking depth, -1 for unlimited
      depth - maximum conditioning-set size, -1 for unlimited
      rbRadius - recursive-blocking radius, -1 for unlimited
      deadline - absolute wall-clock deadline in ms; Long.MAX_VALUE for none
      onTest - run once per executed independence test, or null
      Returns:
      the three-valued outcome: found, not-found, or indeterminate; see FcitSepsets.SepsetSearch
      Throws:
      InterruptedException - if interrupted
    • spanningSepset

      public static FcitSepsets.SepsetResult spanningSepset(Graph graph, IndependenceTest test, Node x, Node y, int recursiveDepth, int depth, int rbRadius, long deadline, Runnable onTest) throws InterruptedException
      Searches for a separating set S such that x and y are conditionally independent given S within the specified constraints. The method uses a recursive-blocking approach to explore potential separating sets in the graph. Returns the result including the found separating set and the corresponding p-value of the test that confirmed it, or indicates failure to find such a set.
      Parameters:
      graph - the graph in which the separator search is performed
      test - the independence test used to evaluate conditional independence
      x - one endpoint node of the pair being tested
      y - the other endpoint node of the pair being tested
      recursiveDepth - the maximum recursive-blocking depth; use -1 for no limit
      depth - the maximum size of the conditioning set; use -1 for no limit
      rbRadius - the recursive-blocking radius; use -1 for no limit
      deadline - the absolute wall-clock deadline in milliseconds; use Long.MAX_VALUE for no deadline
      onTest - a callback function executed once per independence test; may be null
      Returns:
      a SepsetResult containing the found separating set and p-value, or indicating indeterminate/no result
      Throws:
      InterruptedException - if the thread executing the method is interrupted