Class Cpw

java.lang.Object
edu.cmu.tetrad.algcomparison.algorithm.AbstractBootstrapAlgorithm
edu.cmu.tetrad.algcomparison.algorithm.oracle.pag.Cpw
All Implemented Interfaces:
Algorithm, LatentStructureAlgorithm, ReturnsBootstrapGraphs, TakesCovarianceMatrix, HasParameters, TakesIndependenceWrapper, TetradSerializable, Serializable
@Algorithm(name="CPW", command="cpw", algoType=forbid_latent_common_causes, dataType=Continuous) @Bootstrapping @Experimental public class Cpw extends AbstractBootstrapAlgorithm implements Algorithm, TakesIndependenceWrapper, ReturnsBootstrapGraphs, TakesCovarianceMatrix, LatentStructureAlgorithm
Implements the CPW (Cyclic Pairwise) algorithm for causal discovery from continuous, causally sufficient observational data. CPW combines FCI with a pairwise left-right orientation rule to resolve edge directions that FCI leaves ambiguous, under the assumption of no latent common causes and no selection bias. Acyclicity is not assumed: the FCI output is read as a PAG in the sigma-separation sense (valid for cyclic linear models; cf. Mooij & Claassen, 2020), and the pairwise orientation phase may produce cycles in the final graph.

The algorithm runs in one pass:

  1. Pairwise forbidden knowledge construction. For every pair of variables (X, Y), a pairwise left-right statistic is computed on standardized data. If the statistic favors X → Y, the reverse edge Y → X is added to a forbidden knowledge object, which is passed to FCI. Note that these forbids do constrain the search beyond orientation: FCI's adjacency phase excludes a variable forbidden as a cause of X from X's separating-set candidates, so the skeleton itself is steered by the pairwise statistic (empirically a net benefit on skewed linear data; dropping the knowledge costs accuracy on every structure tested).
  2. FCI search. FCI is run with the pairwise forbidden knowledge, producing a PAG. The collider orientation strategy (SEPSETS, CONSERVATIVE, or MAX_P) and other FCI parameters are configurable. Optionally an FDR correction loop is applied to the independence tests.
  3. Two-cycle detection. When the two-cycle alpha is positive, each adjacent pair (other than a bidirected one) is first given FASK's two-cycle test, conditioning on the pair's adjacents in the PAG; a pair that passes is output as a 2-cycle (X → Y and Y → X) and is exempt from the pairwise orientation below. This is what lets CPW represent the smallest cycles at all: the pairwise rule by itself always commits to a single direction. The test is run with Fask.TwoCycleRule.SLOPE_SHIFT rather than FASK's published correlation comparison, which has no asymptotic level on acyclic data outside strongly right-skewed noise and so injected false 2-cycles at a rate that grew with sample size. See Fask.TwoCycleRule for the reasoning and CpwLingamStudy for the measurements.
  4. Pairwise edge orientation. Edges left ambiguous by FCI are further oriented using the pairwise left-right rule on standardized data, subject to the following case analysis:
    • Tail–tail (—): oriented fully as X → Y or Y → X per the pairwise statistic.
    • Tail–circle (—o) or circle–tail (o—): the circle end is resolved to a tail or arrow if the pairwise statistic provides clear evidence.
    • Circle–circle (o–o): one circle end is converted to an arrow in the preferred direction.
    • Circle–arrow (o→) or arrow–circle (←o): under causal sufficiency, the circle is resolved to a tail.
    Bidirected (↔) edges are never altered, and no single rule flips an existing arrow. Note, however, that rules can compose across sweeps: a tail–circle edge whose pairwise statistic opposes the tail direction is first demoted to tail–tail and may then be oriented against the original tail by the tail–tail rule. Under the cyclic interpretation this indicates possible 2-cycle involvement rather than a contradiction, but the ancestral information carried by the original tail is not retained in the output.

The pairwise left-right rule is selected via the PAIRWISE_RULE parameter (1=FASK1, 2=FASK2, 3=RSKEW, 4=SKEW, 5=TANH; default 2). Time-lagged data is supported via the TIME_LAG parameter, which prepends lag columns before search.

This algorithm is marked Experimental and is intended for linear, non-Gaussian, causally sufficient data.

See Also:

  • Constructor Details

    • Cpw

      public Cpw()
      Default constructor for the Cpw class. This constructor initializes the instance without any specific parameters or configurations. It is typically used for

    • Cpw

      public Cpw(IndependenceWrapper test)
      Constructor for the Cpw class that initializes the algorithm with a specified independence test wrapper.
      Parameters:
      test - The IndependenceWrapper instance used for conditional independence testing.

  • Method Details

    • runSearch

      public Graph runSearch(DataModel dataModel, Parameters parameters) throws InterruptedException
      Executes the search algorithm on a given data model and set of parameters, producing a partial ancestral graph (PAG) that represents the causal structure inferred from the data. The output graph may contain cycles.

      The underlying functionality includes handling time-lagged data, standardizing, generating internal knowledge, performing conditional independence tests, and refining the graph using pairwise adjustments based on standardization and rules.

      Parameters:
      dataModel - The data model to analyze, typically a DataSet, which contains the data from which causal relationships are inferred. Must be continuous for proper functioning.
      parameters - Algorithm parameter settings that control various aspects of the computation, such as time lagging, collider orientation style, pairwise rules, and limits on graph structure exploration.
      Returns:
      A Graph representing the causal structure inferred by the search algorithm, encoded as a PAG.
      Throws:
      InterruptedException - If the search process is interrupted during execution, possibly due to thread interruption.

    • getComparisonGraph

      public Graph getComparisonGraph(Graph graph)
      Generates a comparison graph for the given graph by transforming it into a partial ancestral graph (PAG) representation via dagToPag.

      Note that this transform assumes an acyclic true graph, so algcomparison runs against cyclic ground truth are not supported through this path.

      Specified by:
      getComparisonGraph in interface Algorithm
      Parameters:
      graph - The input Graph to be transformed into a comparison graph. This graph serves as the basis for creating the resulting PAG.
      Returns:
      A Graph representing the transformed partial ancestral graph (PAG) based on the input graph.

    • getDescription

      public String getDescription()
      Provides a textual description of the CPW algorithm, including its functionality and distinguishing features, such as the use of pairwise-derived forbidden knowledge and pairwise orientation for certain edges.
      Specified by:
      getDescription in interface Algorithm
      Returns:
      A string describing the CPW algorithm and its characteristics.

    • getDataType

      public DataType getDataType()
      Retrieves the data type associated with the current instance of the algorithm. The data type defines whether the dataset is continuous, discrete, mixed, or another recognized type.
      Specified by:
      getDataType in interface Algorithm
      Returns:
      The DataType representing the type of dataset required or handled by the algorithm.

    • getParameters

      public List<String> getParameters()
      Retrieves a list of parameter names required for the configuration of the CPW algorithm. These parameters control various aspects of the algorithm's execution, such as graph exploration limits, orientation styles, and additional settings affecting the causal inference process.
      Specified by:
      getParameters in interface HasParameters
      Returns:
      A list of strings, where each string represents a parameter name used by the CPW algorithm.

    • getIndependenceWrapper

      public IndependenceWrapper getIndependenceWrapper()
      Retrieves the current instance of the IndependenceWrapper used for conditional independence testing in the algorithm.
      Specified by:
      getIndependenceWrapper in interface TakesIndependenceWrapper
      Returns:
      The IndependenceWrapper instance being used by this algorithm.

    • setIndependenceWrapper

      public void setIndependenceWrapper(IndependenceWrapper test)
      Sets the IndependenceWrapper instance used for conditional independence testing in the algorithm.
      Specified by:
      setIndependenceWrapper in interface TakesIndependenceWrapper
      Parameters:
      test - The IndependenceWrapper instance to be used for testing conditional independence relations.