47. SP-FCI β€” Sparsest-Permutation FCI

Type: Hybrid (Score + Constraint)
Output: PAG
Takes Knowledge: βœ”οΈ fully knowledge-aware
Parent Algorithms: FCI, SP
Sibling Variants: BOSS-FCI, GRaSP-FCI, FCIT

SP-FCI is an FCI-style latent-variable causal discovery algorithm that swaps FCI’s exhaustive adjacency search for a permutation-based score search (the Sparsest Permutation algorithm, SP).
It follows the same design philosophy as BOSS-FCI and GRaSP-FCI: use a model-based adjacency search to obtain a high-precision skeleton, then run FCI’s orientation procedures (including all latent-variable edge marks).

Because SP evaluates every variable permutation, SP-FCI is only usable for very small models (β‰ˆ10 variables)β€”but within that regime it is extremely accurate, often outperforming all other FCI-style methods.

47.1. Key Idea

  1. Permutation-based adjacency search (SP)

    • Consider all permutations of the variables.

    • For each permutation, fit linear regressions parent-set-by-parent-set.

    • Score each DAG via BIC (or score equivalent).

    • Choose the DAG with the fewest edges among all BIC-optimal graphs.

    • Extract the adjacencies from this DAG.

  2. Latent-variable refinement (FCI)

    • Start from the SP skeleton.

    • Run the FCI orientation rules.

    • Produce a PAG representing the latent variable equivalence class.

47.2. When to Use

  • Very small models (5–10 variables)

  • High accuracy desired despite high cost

  • Need for latent-variable robustness

  • Want a non-CI-test adjacency phase

47.3. Strengths

  • Extremely accurate for small p

  • CI-test-free adjacency search

  • Clean skeleton for FCI refinement

  • Fully knowledge-aware

  • Useful as a gold-standard baseline

47.4. Limitations

  • Exponential in variable count β€” limited to ≀10

  • Typically linear-Gaussian scoring

  • Orientation still uses CI tests

  • Not for moderate or large graphs

47.5. Key Parameters in Tetrad

Parameter

Meaning

penaltyDiscount

BIC penalty discount for SP

semBicStructurePrior

Prior weight for SP scoring

semBicRule

Scoring rule for permutations

faithfulnessAssumed

Enforce faithfulness in scoring

maxDegree

Optional parent-set pruning

numThreads

Parallel scoring

allowBidirected

Allow ↔ during FCI orientation

verbose

Log SP + FCI operations

47.6. Knowledge Support

βœ” Fully supports background knowledge:

  • Required/forbidden edges

  • Tier/ancestral constraints

  • Forbidden arrowheads

  • Temporal/ordering constraints

47.7. Relation to Other Algorithms

  • FCI β€” SP-FCI replaces CI-test adjacency with SP

  • BOSS-FCI β€” scalable SP-free score-first variant

  • GRaSP-FCI β€” scalable permutation-relaxation variant

  • FCIT β€” BOSS-guided targeted testing

  • SP β€” adjacency-only version

47.8. References

  • Raskutti & Uhler (2018). Learning directed acyclic graphs based on sparsest permutations. Biometrika.

  • Spirtes et al. (2000). Causation, Prediction, and Search (2nd ed.).

  • Ramsey, Andrews & Spirtes (2025). Efficient Latent Variable Causal Discovery. arXiv:2510.04263.

47.9. Summary

SP-FCI is the high-accuracy, small-variable-count member of the hybrid FCI family, using SP to generate precise adjacencies and FCI to infer a PAG that accounts for latent confounding.