5. CCD — Cyclic Causal Discovery

Type: Constraint-based (DCG / cyclic)
Output: Cyclic PAG (partial ancestral graph for directed cyclic graphs)

Ccd implements Richardson’s Cyclic Causal Discovery algorithm for directed cyclic graphs (DCGs).
Given a conditional independence test that is valid for data generated by a DCG, CCD returns a cyclic PAG: a mixed graph (with circles, arrowheads, and special underline / dotted-underline marks) that represents the Markov equivalence class of DCGs compatible with the observed independences.

5.1. Key Idea

The original CCD algorithm generalizes PC-style reasoning to graphs with feedback loops.

In Tetrad’s implementation:

Skeleton via FAS
- Runs the standard Fast Adjacency Search (Fas) over the variables using the provided IndependenceTest.
- Produces an undirected skeleton, then reorients all endpoints to circles (o-o).
Step B – Unshielded triples: underline vs collider
- For each unshielded triple A–B–C, looks up a separating set S(A, C).
- If B is in S(A, C): record A–B–C as a non-collider (underline triple).
- If B is not in S(A, C): record A–B–C as a collider, attempting to orient A → B ← C (subject to forbidden-edge knowledge).
Step C – Orientation propagation
- Iteratively uses modified CCD rules and further independence checks to orient additional edges, respecting underline and collider markings and background knowledge.
Steps D–F – Dotted underlines and sup-sepsets
- Introduces dotted underlines and constructs sup-sepsets (augmented separating sets) to encode more refined d-connection information.
- Uses these to further orient edges both into and out of marked triples, again respecting knowledge.
R1 “push-away” rule
- Optionally applies an R1-style push-away rule: arrowheads into a node B induce orientations away from B along certain underlined structures, propagating directionality in a way that is sound for DCGs.

The result is a cyclic PAG with:

arrowheads and tails indicating required orientations,
circles for ambiguous endpoints, and
underline/dotted-underline annotations encoding non-colliders and special CCD constraints.

5.2. When to Use

Use Ccd when:

You believe your system may have feedback loops or instantaneous cycles (for example, economic models, biological regulation, or control systems).
You want a constraint-based method that is sound for DCGs, rather than forcing a DAG approximation.
You have a CI test appropriate for DCGs (often a standard CI test is used as an approximation, but CCD’s guarantees presume an oracle for DCG Markov properties).
You want an equivalence-class representation (cyclic PAG) rather than a single oriented graph.

It is especially useful when:

You want to distinguish between purely acyclic explanations and those that genuinely require cycles.
You want a principled alternative to running DAG-only algorithms on systems you know are cyclic.

Related algorithms:

PC / FCI / RFCI: acyclic or PAG-based; do not directly target DCGs.
Dagma / score-based DAG learners: assume acyclicity.
SingleGraphAlg: for analyzing a fixed imported cyclic graph, not learning it.

5.3. Prior Knowledge Support

Does it accept background knowledge?
Yes, but only forbidden edges are honored.

Knowledge may specify forbidden directed edges X → Y.
- CCD will then refuse to orient X → Y and may instead leave the endpoint ambiguous.
Required edges are explicitly disallowed in this implementation:
- If you supply required edges, CCD will throw an error.
- This is intentional: forcing orientations not justified by CCD can break correctness for DCGs.

5.4. Strengths

Designed for cyclic causal structure
- One of the few algorithms explicitly targeting directed cyclic graphs.
Equivalence-class output
- Produces a cyclic PAG that encodes all DCGs consistent with the discovered independences.
Richer edge semantics
- Underlines and dotted underlines provide nuanced information about non-colliders and special separation properties.
Respects forbidden edges
- Lets you rule out impossible directions while preserving CCD’s theoretical guarantees.

5.5. Limitations

No required edges
- Cannot enforce X → Y; only forbid directions.
Assumes a DCG-appropriate independence oracle
- Theoretical guarantees rely on an oracle-level CI notion for DCGs; practical tests are approximations.
Complex output
- Cyclic PAGs with underline/dotted-underline annotations are harder to interpret than standard DAGs/CPDAGs.
Same sensitivity to CI-test errors as other constraint-based methods
- Finite-sample noise can affect adjacency and orientation decisions.

5.6. Key Parameters in Tetrad

Ccd is configured via its setters and the underlying IndependenceTest.

All important controls:

Parameter (camelCase)	Description
`depth`	Maximum conditioning-set size used for CCD-specific separation checks (e.g., Steps D and F). A value of `-1` means no depth limit.
`applyR1`	Boolean. If `true`, applies the R1 push-away rule, which orients arrowheads away from tails in certain underline structures, matching the CCD-specific adaptation of Zhang’s propagation rules.
`fdrQ`	The false discovery rate threshold q for FDR-controlled independence testing. If set, CCD uses FDR-adjusted p-values to decide conditional independence.
`verbose`	Boolean. If `true`, prints detailed diagnostic output about Steps A–F, collider detection, underline detection, orientation rules, and FDR-adjusted decisions.

You indirectly control:

The significance level and behavior of CI tests via the chosen IndependenceTest (for example, Fisher Z with its alpha).
Any caching / performance behavior via CachingIndependenceTest.

5.7. Reference

Richardson, T. S. (2013).
A discovery algorithm for directed cyclic graphs.
arXiv:1302.3599.

5.8. Summary

Ccd is Tetrad’s implementation of Richardson’s cyclic discovery algorithm, taking a conditional independence test for DCGs and returning a cyclic PAG with underline and dotted-underline annotations, while honoring forbidden directions but refusing required edges—your go-to constraint-based learner when feedback loops are part of the story.