# Library

## (Partially) directed acyclic graphs (PDAGs and DAGs)

`CausalInference.has_a_path`

— Function`has_a_path(g::AbstractGraph, U::Vector, V::VectorOrVertex, exclude_vertices::AbstractVector = T[], nbs=Graphs.outneighbors)`

Find if there is a (semi-directed) path connecting U with V not passing `exclude_vertices`

, where `nbs=Graphs.outneighbors`

determines the direction of traversal.

`CausalInference.graph`

— Function`graph(E)`

Create `Graph`

from edge-list.

`CausalInference.isclique`

— Function`isclique(g, nodes)`

Return `true`

if all vertices in `nodes`

are adjacent to each other in the graph `g`

. Chickering, "Learning equivalence classes" (2002). Note that a 3-clique with already two undirected edges is also a clique in the neighbor sense.

`CausalInference.parents`

— Function`parents(g, x)`

Parents are vertices y such that there is a directed edge y –> x. Returns sorted array.

`CausalInference.children`

— Function`children(g, x)`

Children of x in g are vertices y such that there is a directed edge y <– x. Returns sorted array.

`CausalInference.isundirected`

— Function```
isundirected(g, edge::Edge)
isundirected(g, x, y)
```

Test if `x`

and `y`

are connected by a undirected edge in the graph `g`

.

`CausalInference.isparent`

— Function`isparent(g, x, y)`

Test if `x`

is a parent of `y`

in the graph `g`

, meaning x→y.

`CausalInference.neighbors_undirected`

— Function`neighbors_undirected(g, x)`

All vertices in `g`

connected to `x`

by an undirected edge. Returns sorted array.

`CausalInference.isoriented`

— Function```
isoriented(g, edge::Edge)
isoriented(g, x, y)
```

Test if `x`

and `y`

are connected by a directed edge in the graph `g`

, either x←y OR x→y. Can also perform the same test given an `edge`

.

`CausalInference.orientedge!`

— Function`orientedge!(g, x, y)`

Update the edge `x`

-`y`

to `x`

→`y`

in the graph `g`

. Throws error if not `x - y`

`CausalInference.neighbors_adjacent`

— Function`neighbors_adjacent(g, x)`

All vertices in `g`

connected to `x`

by an any edge. Returns sorted array.

`CausalInference.isadjacent`

— Function`isadjacent(g, x, y)`

Test if `x`

and `y`

are connected by a any edge in the graph `g`

(i.e. x –- y, x –> y, or x <– y .)

`CausalInference.ischild`

— Function`ischild(g, x, y)`

Test if `x`

is a child of `y`

in the graph `g`

, meaning x←y.

## Causal graphs

`CausalInference.dsep`

— Function`dsep(g::AbstractGraph, u, v, s; verbose = false)`

Check whether `u`

and `v`

are d-separated given set `s`

. Algorithm: unrolled https://arxiv.org/abs/1304.1505

`CausalInference.cpdag`

— Function`cpdag(skel::DiGraph)`

Computes CPDAG from a DAG using Chickering's conversion algorithm (equivalent to the PC algorithm with `d`

-seperation as independence test, see `pc_oracle`

.)

Reference: M. Chickering: Learning equivalence classes of Bayesian network structures. Journal of Machine Learning Research 2 (2002). M. Chickering: A Transformational Characterization of Equivalent Bayesian Network Structures. (1995).

Note that the edge order defined there is already partly encoded into the representation of a DiGraph.

`CausalInference.alt_cpdag`

— Function`alt_cpdag(g::DiGraph)`

Computes CPDAG from a DAG using a simpler adaption of Chickering's conversion algorithm without ordering all edges (equivalent to the PC algorithm with `d`

-separation as independence test, see `pc_oracle`

.)

Reference: M. Chickering: Learning equivalence classes of Bayesian network structures. Journal of Machine Learning Research 2 (2002). M. Chickering: A Transformational Characterization of Equivalent Bayesian Network Structures. (1995).

`CausalInference.vskel`

— Function`vskel(g)`

Reduce a (P)DAG to skeleton and `v`

-structures.

`CausalInference.has_recanting_witness`

— Function`has_recanting_witness(g::AbstractGraph, u, v, blocked_edges::AbstractGraph) -> Bool`

In a causal DAG with edges `g`

, determine whether path-specific causal effect from vertex `u`

to `v`

with edges in `blocked_edges`

blocked can be can be computed uniquely from the data available to the investigator (assuming complete observations), which is the case if there is no "recanting witness". Essentially this means that `blocked_edges`

could equivalently be replaced by a blocking only outgoing edges of `u`

.

See Alvin, Shpitser, Pearl (2005): "Identifiability of Path-Specific Effects", https://ftp.cs.ucla.edu/pub/stat_ser/r321-L.pdf.

`CausalInference.backdoor_criterion`

— Function`backdoor_criterion(g::AbstractGraph, u::Integer, v::Integer, Z; verbose = false)`

Test that given directed graph `g`

, no node in `Z`

is descendant of `u`

and `Z`

d-separates `u`

from `v`

in the subgraph that only has the backdoors of `u`

left (outgoing edges of `u`

removed).

If so, the causal effect of `u`

on `v`

is identifiable and is given by the formula:

`∑{z∈Z} p(v | u, z)p(z)`

In the linear Gaussian model, find `E[Y | X = x, Z = z] = α + βx + γ'z`

and obtain `E[Y | do(x)] = α + βx + γ'E[Z].

`CausalInference.meek_rules!`

— Function`meek_rules!(g; rule4=false)`

Apply Meek's rules 1-3 or 1-4 with rule4=true to orient edges in a partially directed graph without creating cycles or new v-structures. Rule 4 is needed if edges are compelled/preoriented using external knowledge.

`CausalInference.meek_rule1`

— Function`meek_rule1(g, v, w)`

Rule 1: Orient v-w into v->w whenever there is u->v such that u and w are not adjacent (otherwise a new v-structure is created.)

`CausalInference.meek_rule2`

— Function`meek_rule2(g, v, w)`

Rule 2: Orient v-w into v->w whenever there is a chain v->k->w (otherwise a directed cycle is created.)

`CausalInference.meek_rule3`

— Function`meek_rule3(g, v, w)`

Rule 3 (Diagonal): Orient v-w into v->w whenever there are two chains v-k->w and v-l->w such that k and l are nonadjacent (otherwise a new v-structure or a directed cycle is created.)

`CausalInference.meek_rule4`

— Function`meek_rule4(g, v, w)`

Rule 4: Orient v-w into v→w if v-k→l→w where adj(v,l) and not adj(k,w) [check].

`CausalInference.pdag2dag!`

— FunctionDeprecated alias for `pdag_to_dag_meek!`

.

`CausalInference.pdag_to_dag_dortarsi!`

— Function`pdag_to_dag_dortarsi!(g)`

Complete PDAG to DAG using Dor & Tarsi (1992).

`CausalInference.pdag_to_dag_meek!`

— Function`pdag_to_dag_meek!(g, rule4=false)`

Complete PDAG to DAG using meek_rules.

## PC algorithm

`CausalInference.pcalg`

— Function```
pcalg(n::V, I, par...; stable=true)
pcalg(g, I, par...; stable=true)
```

Perform the PC algorithm for a set of 1:n variables using the tests

`I(u, v, [s1, ..., sn], par...)`

Returns the CPDAG as DiGraph. By default uses a stable and threaded versions of the skeleton algorithm.

`pcalg(t, p::Float64, test::typeof(gausscitest); kwargs...)`

Run PC algorithm for tabular input data t using a p-value p to test for conditional independeces using Fisher's z-transformation.

`pcalg(t::T, p::Float64; cmitest::typeof(cmitest); kwargs...) where{T}`

Run PC algorithm for tabular input data t using a p-value p to detect conditional independeces using a conditional mutual information permutation test.

`CausalInference.orient_unshielded`

— Function`orient_unshielded(g, dg, S)`

Orient unshielded triples using the separating sets. `g`

is an undirected graph containing edges of unknown direction, `dg`

is an directed graph containing edges of known direction and both `v=>w`

and `w=>v`

if the direction of `Edge(v,w)`

`is unknown.`

S` are the separating sets of edges.

Returns `g, dg`

.

`CausalInference.apply_pc_rules`

— Function`apply_pc_rules(g, dg)`

`g`

is an undirected graph containing edges of unknown direction, `dg`

is an directed graph containing edges of known direction and both `v=>w`

and `w=>v`

if the direction of `Edge(v,w)`

` is unknown.

Returns the CPDAG as DiGraph.

`CausalInference.skeleton`

— Function```
skeleton(n::Integer, I) -> g, S
skeleton(g, I) -> g, S
```

Perform the undirected PC skeleton algorithm for a set of `1:n`

variables using the test `I`

. Start with a subgraph `g`

or the complete undirected graph on `n`

vertices. Returns skeleton graph and separating set.

`CausalInference.skeleton_stable`

— Function```
skeleton_stable(n::Integer, I) -> g, S
skeleton_stable(g, I) -> g, S
```

Perform the undirected stable PC skeleton algorithm for a set of `1:n`

variables using the test `I`

. Start with a subgraph `g`

or the complete undirected graph on `n`

vertices. Returns skeleton graph and separating set.

`CausalInference.dseporacle`

— Function`dseporacle(i, j, s, g)`

Oracle for the `skeleton`

and `pcalg`

functions using `dsep`

on the true graph `g`

`CausalInference.unshielded`

— Function`unshielded(g)`

Find the unshielded triples in the cyclefree skeleton. Triples are connected vertices v-w-z where z is not a neighbour of v. Uses that `edges`

iterates in lexicographical order.

`CausalInference.orientable_unshielded`

— Function`orientable_unshielded(g, S)`

Find the orientable unshielded triples in the skeleton. Triples are connected vertices v-w-z where z is not a neighbour of v. Uses that `edges`

iterates in lexicographical order.

`CausalInference.plot_pc_graph_tikz`

— Function`CausalInference.plot_pc_graph_tikz(g, node_labels::AbstractVector{<:AbstractString}=String[])`

Plot the output of the PC algorithm (TikzGraphs backend).

Requires TikzGraphs to be imported

`CausalInference.plot_pc_graph_recipes`

— Function`plot_pc_graph_recipes(g, node_labels::AbstractVector{<:AbstractString}=String[])`

Plot the output of the PC algorithm (GraphRecipes backend).

Requires GraphRecipes and Plots to be imported

`CausalInference.plot_pc_graph_text`

— Function`plot_pc_graph_text(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])`

Plot the output of the PC algorithm (text-based output).

See also: `plot_pc_graph`

and `plot_pc_graph_tikz`

(for TikzGraphs.jl-based plotting), `plot_pc_graph_recipes`

(for GraphRecipes.jl-based plotting)

`CausalInference.prepare_pc_graph`

— Function`prepare_pc_graph(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])`

Prepare resulting graph for plotting with various backends.

## Statistics

`CausalInference.gausscitest`

— Function`gausscitest(i, j, s, (C,n), c)`

Test for conditional independence of variable no i and j given variables in s with Gaussian test at the critical value c. C is covariance of n observations.

`CausalInference.partialcor`

— Function`partialcor(i, j, s, C)`

Compute the partial correlation of nodes `i`

and `j`

given list of nodes `s`

using the correlation matrix `C`

.

`CausalInference.cmitest`

— Function`cmitest(i,j,s,data,crit; kwargs...)`

Test for conditional independence of variables i and j given variables in s with permutation test using nearest neighbor conditional mutual information estimates at p-value crit.

keyword arguments: kwargs...: keyword arguments passed to independence tests

## KL Entropy Estimators

`CausalInference.n_ball`

— Function`n_ball(n::Number)`

Computes the volume of a n-dimensional unit sphere.

`CausalInference.kl_entropy`

— Function`kl_entropy(data::Array{Float64, 2}; k=5)`

Compute the nearest-neighbor estimate of the differential entropy of data.

data is a 2d array, with every column representing one data point. For further information, see

"A class of Rényi information estimators for multidimensional densities" Nikolai Leonenko, Luc Pronzato, and Vippal Savani The Annals of Statistics, 2008 https://projecteuclid.org/euclid.aos/1223908088

keyword arguments: k=5: number of nearest neighbors

`CausalInference.kl_renyi`

— Function`kl_renyi(data::Array{Float64, 2}, q; k=5)`

Compute the nearest-neighbor estimate of the Renyi-alpha entropy of data.

data is a 2d array, with every column representing one data point. For further information, see

"A class of Rényi information estimators for multidimensional densities" Nikolai Leonenko, Luc Pronzato, and Vippal Savani The Annals of Statistics, 2008 https://projecteuclid.org/euclid.aos/1223908088

keyword arguments: k=5: number of nearest neighbors

`CausalInference.kl_mutual_information`

— Function`kl_mutual_information(x, y; k=5, bias_correction=true)`

compute the nearest-neighbor 'KGS' estimate of the mutual information between x and y.

x and y are 2d arrays, with every column representing one data point. For further information, see

"Estimating Mutual Information" Alexander Kraskov, Harald Stoegbauer, and Peter Grassberger Physical Review E https://arxiv.org/pdf/cond-mat/0305641.pdf

"Demystifying Fixed k-Nearest Neighbor Information Estimators" Weihao Gao, Sewoong Oh, Pramod Viswanath EEE International Symposium on Information Theory - Proceedings https://arxiv.org/pdf/1604.03006.pdf

keyword arguments: k=5: number of nearest neighbors bias_correction=true: flag to apply Gao's bias correction

`CausalInference.kl_cond_mi`

— Function`kl_cond_mi(x, y, z; k=5, bias_correction=true)`

compute the nearest-neighbor 'KGS' estimate of the conditional mutual information between x and y given z.

x, y, and z are 2d arrays, with every column representing one data point. keyword arguments: k=5: number of nearest neighbors bias_correction=true: flag to apply Gao's bias correction

`CausalInference.kl_perm_mi_test`

— Function`kl_perm_mi_test(x, y; k=5, B=100, bias_correction=true)`

compute permutation test of independence of x and y.

keyword arguments: k=5: number of nearest neighbors to use for mutual information estimate B=100: number of permutations bias_correction=true: flag to apply Gao's bias correction

`CausalInference.kl_perm_cond_mi_test`

— Function`kl_perm_cond_mi_test(x, y, z; k=5, B=100, kp=5, bias_correction=true)`

compute permutation test of conditional independence of x and y given z.

For further information, see: "Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information" Jakob Runge Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. http://proceedings.mlr.press/v84/runge18a/runge18a.pdf

keyword arguments: k=5: number of nearest neighbors to use for mutual information estimate B=100: number of permutations bias_correction=true: flag to apply Gao's bias correction

## FCI algorithm

`CausalInference.has_marks`

— Function`has_marks(dg, v1, v2, t::Tuple{Symbol, Symbol}`

Test if the edge between node v1 and v2 has the edge markers given by the tuple t (use the arrow macro to simplify use)

Example: `has_marks(dg, 1, 2, arrow"o->")`

`CausalInference.set_marks!`

— Function`set_marks!(dg, v1, v2, t::Tuple{Symbol, Symbol})`

Set edge marks between node v1 and v2.

Example: `set_marks!(dg, 1, 2, arrow"*->")`

`CausalInference.is_collider`

— Function`is_collider(dg, v1, v2, v3)`

Check if egde v1, v2 and v3 form a collider.

`CausalInference.is_parent`

— Function`is_parent(dg, v1, v2)`

Check if v1 is a parent of v2.

`CausalInference.is_triangle`

— Function`is_triangle(dg, v1, v2, v3)`

Check if v1, v2 and v3 form a triangle.

`CausalInference.is_discriminating_path`

— Function`is_discriminating_path(dg, path)`

Check if `path`

is a discriminating path.

`CausalInference.is_uncovered_circle_path`

— Function`is_uncovered_circle_path(dg, path)`

Check if `path`

is an uncovered circle path.

`CausalInference.is_uncovered_PD_path`

— Function`is_uncovered_PD_path(dg, path)`

Check if `path`

is an uncovered potentially directed path.

`CausalInference.fcialg`

— Function`fcialg(n::V, I, par...; augmented=true, verbose=false, kwargs...)`

Perform the FCI algorithm for a set of `n`

variables using the test

`I(u, v, [s1, ..., sn], par...)`

Returns the PAG as a MetaDiGraph

`CausalInference.plot_fci_graph_tikz`

— Function`plot_fci_graph_tikz(g, node_labels::AbstractVector{<:AbstractString}=String[])`

Plot the output of the FCI algorithm (TikzGraphs backend).

Requires TikzGraphs to be imported

`CausalInference.plot_fci_graph_recipes`

— Function`plot_fci_graph_recipes(g, node_labels::AbstractVector{<:AbstractString}=String[])`

Plot the output of the FCI algorithm (GraphRecipes backend).

Requires GraphRecipes and Plots to be imported

`CausalInference.plot_fci_graph_text`

— Function`plot_fci_graph_text(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])`

Plot the output of the FCI algorithm (text-based output).

See also: `plot_fci_graph`

and `plot_fci_graph_tikz`

(for TikzGraphs.jl-based plotting), `plot_fci_graph_recipes`

(for GraphRecipes.jl-based plotting)

`CausalInference.prepare_fci_graph`

— Function`prepare_fci_graph(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=String[])`

Prepare the output of the FCI algorithm for plotting with various backends.

## Miscellaneous

`CausalInference.digraph`

— Function`digraph(E)`

Create `DiGraph`

from edge-list.

`CausalInference.vpairs`

— Function`arrows(g)`

Return the edge-list as `Pair`

s.

`CausalInference.pc_oracle`

— Function`pc_oracle(g; stable=true)`

Compute CPDAG using the PC algorithm using the `dseporacle`

on the DAG `g`

.

`CausalInference.skel_oracle`

— Function`skel_oracle(g; stable=true)`

Compute the `skeleton`

using the `dseporacle`

for the DAG `g`

.

`CausalInference.randdag`

— Function`randdag(n, alpha = 0.1)`

Create Erdős–Rényi random DAG from randomly permuted random triangular matrix with edge probability `alpha`

.

`CausalInference.disjoint_sorted`

— Function`disjoint_sorted(u, v)`

Check if the intersection of sorted collections is empty. The intersection of empty collectios is empty.

`CausalInference.ordered_edges`

— Function`ordered_edges(dag)`

Iterator of edges of a dag, ordered in Chickering order:

```
Perform a topological sort on the NODES
while there are unordered EDGES in g
Let y be the lowest ordered NODE that has an unordered EDGE incident into it
Let x be the highest ordered NODE for which x => y is not ordered
return x => y
end
```

`CausalInference.removesorted!`

— Function`removesorted(collection, item) -> contains(collection, item)`

Remove item from sorted collection.

`CausalInference.graph_to_text`

— Function`graph_to_text(g::AbstractGraph, node_labels::AbstractVector{<:AbstractString}=[]; edge_styles::AbstractDict=Dict())`

Print out a graph `g`

as a table of edges labeled by `node_labels`

.

**Arguments**

`g::AbstractGraph`

: a graph to print`node_labels::AbstractVector{<:AbstractString}=[]`

: labels for nodes (same order as indices of nodes in`g`

)`edge_styles::AbstractDict=Dict()`

: dictionary of edge styles (e.g.`Dict((1, 2) => "->", (2, 3) => "<->")`

)

**Example**

```
g = DiGraph(4)
for (i, j) in [(1, 2), (2, 3), (2, 4)]
add_edge!(g, i, j)
end
graph_to_text(g)
```

`CausalInference.kwargs_pdag_graphmakie`

— Function`kwargs_pdag_graphmakie(g; ilabels=1:nv(g), arrowsize=25, ilabels_fontsize=25)`

Generates the keywords for `GraphMakie.graphplot`

to plot causal graphs and (C)PDAGs represented as `SimpleDiGraph`

as partially directed graphs.

Usage:

`graphplot(g; kwargs_pdag_graphmakie(g)...)`

`CausalInference.combinations_without`

— Function`combinations_without(a, n::Integer, w)`

Generate all combinations of `n`

elements from an indexable object except those with index `w`

. Note that the combinations are modified inplace.

## Bayes ball

`CausalInference.bayesball`

— Function`bayesball(g, X, S = Set{eltype(g)}())`

Return the set of vertices d-connected to the set of vertices X given set of vertices S in dag g.

`CausalInference.bayesball_graph`

— Function`bayesball_graph(g, X, S = Set{eltype(g)}(); back=false)`

Return an mixed graph `b`

containing edges for possible moves of the Bayes ball. Vertex `x`

of `g`

is vertex "`x`

forward" at `2x-1`

of `b`

if entered forward and "`x`

backward" at `2x`

if entered backward. `y`

is d-connected to `x`

given `S`

if and only if there is a semi-directed path in `b`

from "`x`

backward" to "`y`

forward" or "`y`

backward"). `back=true`

allows path through `X`

## Adjustment

`CausalInference.ancestors`

— Function`ancestors(g, X, veto = no_veto)`

Return the set of ancestors of the set of vertices `X`

in graph `g`

.

Every vertex is an ancestor of itself.

`CausalInference.descendants`

— Function`descendants(g, X, veto = no_veto)`

Return the set of descendants of the set of vertices `X`

in graph `g`

.

Every vertex is a descendant of itself.

`CausalInference.alt_test_dsep`

— Function`alt_test_dsep(g, X, Y, S, veto = no_veto)`

Check if sets of vertices `X`

and `Y`

are d-separated in `g`

given `S`

.

An alternative to the `test_dsep`

function, which uses gensearch under the hood. Might be (a bit) slower.

`CausalInference.test_covariate_adjustment`

— Function`test_covariate_adjustment(g, X, Y, S)`

Check if `S`

is a covariate adjustment set relative to `(X, Y)`

in graph `g`

.

Based on the sound and complete graphical criterion for covariate adjustment given in https://arxiv.org/abs/1203.3515 using the algorithmic approach proposed in https://arxiv.org/abs/1803.00116. Output is a boolean.

`CausalInference.alt_test_backdoor`

— Function`alt_test_backdoor(g, X, Y, S)`

Check if `S`

satisfies the backdoor criterion relative to `(X, Y)`

in graph `g`

.

The generalization to sets X and Y differs from, e.g., Pearl (2009). See the Example section (TODO: ref).

`CausalInference.find_dsep`

— Function`find_dsep(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y), veto = no_veto)`

Find a d-separator `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else return `false`

.

Based on the algorithmic approach proposed in https://arxiv.org/abs/1803.00116.

`CausalInference.find_min_dsep`

— Function`find_min_dsep(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y), veto = no_veto)`

Find an inclusion minimal d-separator `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, i.e., one for which no subset is a d-separator, else return `false`

.

Based on the algorithmic approach proposed in http://auai.org/uai2019/proceedings/papers/222.pdf.

`CausalInference.find_covariate_adjustment`

— Function`find_covariate_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

Find a covariate adjustment set `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else return `false`

.

Based on the algorithmic approach proposed in https://arxiv.org/abs/1803.00116.

`CausalInference.find_backdoor_adjustment`

— Function`find_backdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

Find a backdoor adjustment set `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else return `false`

.

The generalization to sets X and Y differs from, e.g., Pearl (2009). See the Example section (TODO: ref).

`CausalInference.find_frontdoor_adjustment`

— Function`find_frontdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

Find a frontdoor adjustment set `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else return `false`

.

Based on the algorithm given in https://arxiv.org/abs/2211.16468.

`CausalInference.find_min_covariate_adjustment`

— Function`find_min_covariate_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

Find an inclusion minimal covariate adjustment set `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else return `false`

.

Based on the algorithmic approach proposed in https://arxiv.org/abs/1803.00116.

`CausalInference.find_min_backdoor_adjustment`

— Function`find_min_backdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

Find an inclusion minimal backdoor adjustment set `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else return `false`

.

The generalization to sets X and Y differs from, e.g., Pearl (2009). See the Example section (TODO: ref).

`CausalInference.find_min_frontdoor_adjustment`

— Function`find_min_frontdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

Find an inclusion minimal frontdoor adjustment set `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

, else returns `false`

.

Based on the algorithm given in https://arxiv.org/abs/2211.16468.

`CausalInference.list_dseps`

— Function`list_dseps(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

List all d-separators `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

.

`CausalInference.list_covariate_adjustment`

— Function`list_covariate_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

List all covariate adjustment sets `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

.

`CausalInference.list_backdoor_adjustment`

— Function`list_backdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

List all back-door adjustment sets `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

.

`CausalInference.list_frontdoor_adjustment`

— Function`list_frontdoor_adjustment(g, X, Y, I = Set{eltype(g)}(), R = setdiff(Set(vertices(g)), X, Y))`

List all front-door adjustment sets `Z`

with $I ⊆ Z ⊆ R$ for sets of vertices `X`

and `Y`

in `g`

.

## GES

`CausalInference.ges`

— Function`ges(X; method=:gaussian_bic, penalty=0.5, parallel=false, verbose=false)`

Compute a causal graph for the given observed data `X`

(variables in columns) using GES. Returns the CPDAG, the score improvement relative to the empty graph and time measurements of first and second phase.

`ges(n, local_score; score=0.0, parallel=false, verbose=false)`

Internal method called by `ges`

.

`CausalInference.local_score`

— Function`local_score(os::GaussianScore, p, v)`

Local Gaussian BIC score. Memoized for `GaussianScore{Float64, Symmetric{Float64, Matrix{Float64}}}`

.

`CausalInference.Insert!`

— Function`Insert!(g, x, y, T)`

Inserts x->y and directs previously undirected edges t->y, t ∈ T. Here x and y are not adjacent and T are undirected-neighbors of y that are not adjacent to x.

`CausalInference.Delete!`

— Function`Delete!(g, x, y, H)`

Deletes x-y or x->y and directs previously undirected edges x->h and y->h for h in H.

## Causal Zig-Zag

`CausalInference.nup`

— Function`nup(g, total)`

Number of directed edges that can be add to a PDAG `g`

with `total`

number of edges.

`CausalInference.ndown`

— Function`ndown(g, total)`

Number of edges that can be removed from a `pdag`

counting undirected edges twice.

`CausalInference.count_moves_uniform`

— Function`count_moves_uniform(g, κ=nv(g) - 1) = s1, s2, (x1, y1, T1), (x2, y2, H2)`

Counts and samples operator in polynomial-time by avoiding full enumeration (only works for uniform score.) Count the number `s1`

of Insert and `s2`

of Delete operators for CPDAG `g`

with degree bound `κ`

and return a uniformly selected `Insert(x1, y1, T1)`

`and a uniform selected`

Delete(x2, y2, H2)` operator.

`CausalInference.causalzigzag`

— Function```
causalzigzag(n, G = (DiGraph(n), 0); balance = metropolis_balance, prior = (_,_)->1.0, score=UniformScore(),
coldness = 1.0, σ = 0.0, ρ = 1.0, naive=false,
κ = min(n - 1, 10), iterations=10, verbose=false, save=true)
```

Run the causal zigzag algorithm starting in a cpdag `(G, t)`

with `t`

oriented or unoriented edges, the balance function `balance ∈ {metropolis_balance, barker_balance, sqrt}`

, `score`

function (see `ges`

algorithm) coldness parameter for iterations. `σ = 1.0, ρ = 0.0`

gives purely diffusive behaviour, `σ = 0.0, ρ = 1.0`

gives Zig-Zag behaviour.

Returns a vector of tuples with information, each containing a graph, spent time, current direction, number of edges and the score.

`CausalInference.keyedreduce`

— Function`keyedreduce(op, key::AbstractVector{T}, a, init=0.0) where T`

Similar to `countmap`

returning a dictionary mapping unique key in `key`

to the reduction the given collection itr with the given binary operator `op`

.

```
julia> keyedreduce(+, [:a, :b, :a], [7, 3, 2])
Dict{Symbol, Float64} with 2 entries:
:a => 9.0
:b => 3.0
```

`CausalInference.ne_total`

— Function`ne_total(g)`

Number of directed or undirected edges in a PDAG represented as DiGraph.

`CausalInference.arrows`

— Function`arrows(g)`

Return the edge-list as `Pair`

s.

`CausalInference.remove!`

— Function`remove!(dg::DiGraph, x => y)`

Removes directed edge.

`CausalInference.count_moves`

— Function`count_moves(g, κ, balance, prior, score, coldness, dir=:both)`

Return

`CausalInference.ne_undirected`

— Function`ne_undirected(g)`

Number of undirected edges in a PDAG represented as DiGraph.

`CausalInference.operator_mcs`

— Function`operator_mcs(G, K)`

Perform a Maximum Cardinality Search on graph G. The elements of clique K are of prioritized and chosen first.

`CausalInference.InsertIterator`

— Type`InsertIterator{T<:Integer}`

Lists all insert operators for pair x,y (needs semidirected from prev point)

`CausalInference.DeleteIterator`

— Type`DeleteIterator{T<:Integer}`

Lists all delete operators for pair x,y.

`CausalInference.count_mcs`

— Function`count_mcs(G)`

Perform a Maximum Cardinality Search on graph G.

`CausalInference.precompute_semidirected`

— Function`precompute_semidirected(g, y)`

Computes for vertex y all vertices reachable via semidirected path from any undirected neighbor and y itself with all vertices in this same set blocked.

`CausalInference.next_CPDAG`

— Function`next_CPDAG(g, op, x, y, S)`

`next_CDPAG`

applies an operator and computes the resulting CPDAG in linear-time

## DAG Zig-Zag

`CausalInference.dagzigzag`

— Function```
dagzigzag(n, G = DiGraph(n); balance = metropolis_balance, prior = (_,_)->1.0, score=UniformScore(),
coldness = 1.0, σ = 0.0, ρ = 1.0,
κ = min(n - 1, 10), iterations=10, verbose=false, save=true)
```

Run the causal zigzag algorithm starting in a dag `G`

the balance function `balance ∈ {metropolis_balance, barker_balance, sqrt}`

, `score`

function (see `ges`

algorithm) coldness parameter for iterations. `σ = 1.0, ρ = 0.0`

gives purely diffusive behaviour, `σ = 0.0, ρ = 1.0`

gives Zig-Zag behaviour.

Returns a vector of tuples with information, each containing a graph, spent time, current direction, number of edges and the score.

`CausalInference.count_dag_moves`

— Function`count_dag_moves(g, κ, balance, prior, score, coldness, dir=:both)`

Return

## Exact

`CausalInference.exactscorebased`

— Function`exactscorebased(X; method=:gaussian_bic, penalty=0.5, parallel=false, verbose=false)`

Compute a CPDAG for the given observed data `X`

(variables in columns) using the exact algorithm proposed by Silander and Myllymäki (2006) for optimizing the BIC score (or any decomposable score). The complexity is n*2^n and the algorithm should scale up to ~20-25 variables, afterwards memory becomes a problem.

- Silander, T., & Myllymäki, P. (2006). A simple approach for finding the globally optimal Bayesian network structure. In Uncertainty in Artificial Intelligence (pp. 445-452).