Class FlopInitialOrder

java.lang.Object
edu.cmu.tetrad.search.utils.FlopInitialOrder
public final class FlopInitialOrder extends Object
Computes the principled initial variable order proposed in Section 4.1 of Wienobst, Henckel, and Weichwald (2026), "Embracing Discrete Search: A Reasonable Approach to Causal Structure Learning" (the FLOP paper), for use with order-based permutation searches such as BOSS or FLOP.

The order is constructed so that strongly correlated variables are placed adjacent to one another: it begins with the two most correlated variables and then repeatedly appends the unplaced variable with the smallest residual variance when regressed on the variables already placed. This is computed via a pivoted Cholesky decomposition of the correlation matrix, requiring O(p^3) time and O(p^2) memory in the worst case.

The motivation is that order-based searches using grow-shrink parent selection can fail on far-apart ancestor-descendant pairs whose marginal dependence is too weak to detect in finite samples (path graphs are the canonical hard case). Placing strongly correlated variables adjacently in the initial order avoids asking grow-shrink to detect such weak long-range dependencies.

The correlation matrix (rather than the covariance matrix) is used throughout, which makes the resulting order invariant to the scaling of the individual variables.

Typical usage with BOSS: 

    PermutationSearch search = new PermutationSearch(new Boss(score));
    search.setOrder(FlopInitialOrder.initialOrder(dataSet));
    Graph cpdag = search.search();
Version:
$Id: $Id
Author:
josephramsey
See Also:

  • Method Details

    • initialOrder

      public static List<Node> initialOrder(DataSet dataSet)
      Computes the FLOP initial order for the variables in the given data set.
      Parameters:
      dataSet - A continuous data set.
      Returns:
      The variables of the data set, in the FLOP initial order.

    • initialOrder

      public static List<Node> initialOrder(ICovarianceMatrix covariances)
      Computes the FLOP initial order for the variables of the given covariance matrix. The matrix is first converted to a correlation matrix, so the result is scale-invariant.
      Parameters:
      covariances - A covariance (or correlation) matrix.
      Returns:
      The variables of the covariance matrix, in the FLOP initial order.