📚Books

Appendix B: Causal Orderings and Adjacency Matrices

This appendix provides mathematical background on graph-theoretic concepts that are fundamental to causal modeling, particularly focusing on causal orderings and their representation through adjacency matrices.

B.1 Basic Graph Theory

Directed Acyclic Graphs (DAGs)

A directed acyclic graph G = (V, E) consists of:

  • A set of vertices (nodes) V = {X₁, X₂, ..., X_d}
  • A set of directed edges E ⊆ V × V

The graph is acyclic if it contains no directed cycles.

Causal Orderings

Definition B.1 (Topological ordering) A topological ordering of a DAG G is a linear ordering of its vertices such that for every directed edge (X_i, X_j), vertex X_i comes before X_j in the ordering.

Definition B.2 (Causal ordering) A causal ordering is a topological ordering that reflects the causal relationships: if X_i causally precedes X_j, then X_i appears before X_j in the ordering.

Properties of Causal Orderings

  1. Existence: Every DAG has at least one topological ordering.
  2. Non-uniqueness: A DAG may have multiple valid topological orderings.
  3. Causal interpretation: In causal DAGs, a valid causal ordering ensures that causes precede their effects.

B.2 Adjacency Matrix Representation

Definition

For a directed graph G with vertices {X₁, ..., X_d}, the adjacency matrix A is a d × d binary matrix where:

$$ A_{ij} = \begin{cases} 1 & \text{if there is an edge } X_i \to X_j \ 0 & \text{otherwise} \end{cases} $$

Properties

  • Acyclicity condition: A directed graph is acyclic if and only if its adjacency matrix can be permuted to upper triangular form.
  • Causal relationships: A_{ij} = 1 indicates that X_i is a direct cause of X_j.
  • Path relationships: The (i,j)-th entry of A^k counts the number of directed paths of length k from X_i to X_j.

B.3 Algorithms for Causal Ordering

Kahn's Algorithm

A standard algorithm for finding topological orderings:

  1. Start with all vertices that have no incoming edges
  2. Remove a vertex with no incoming edges and add it to the ordering
  3. Remove all outgoing edges from this vertex
  4. Repeat until all vertices are ordered

Application to Causal Discovery

In causal structure learning:

  1. Constraint-based methods use conditional independence tests to determine edge orientations
  2. Score-based methods search over possible orderings and structures
  3. Hybrid methods combine both approaches

B.4 Markov Equivalence

Definition

Two DAGs are Markov equivalent if they entail the same set of conditional independence relationships.

Completed Partially Directed Acyclic Graph (CPDAG)

A CPDAG represents an equivalence class of Markov equivalent DAGs by:

  • Using directed edges for orientations that are the same in all equivalent DAGs
  • Using undirected edges for orientations that differ across equivalent DAGs

Implications for Causal Learning

  • Identifiability limitations: Some causal relationships cannot be determined from observational data alone
  • Intervention design: Strategic interventions can help orient undirected edges
  • Equivalence class representation: CPDAGs provide a compact representation of the set of possible causal structures

B.5 Special Cases and Extensions

Trees and Forests

  • Tree: Connected acyclic undirected graph
  • Forest: Collection of disjoint trees
  • Directed tree: DAG where each node has at most one parent

Trees have unique causal orderings up to the choice of root node.

Partially Directed Graphs

  • Mixed graphs: Contain both directed and undirected edges
  • Chain graphs: Sequence of chain components connected by directed edges
  • Ancestral graphs: Allow bidirected edges representing confounding

Cyclic Graphs

While structural causal models typically assume acyclicity:

  • Cyclic SCMs: Can represent feedback loops but require special treatment
  • Equilibrium analysis: Focus on steady-state solutions
  • Dynamic models: Unfold cycles over time

B.6 Computational Complexity

Counting Problems

  • Counting topological orderings: #P-complete for general DAGs
  • Counting Markov equivalent DAGs: Exponential in worst case
  • Structure learning complexity: Generally NP-hard for exact methods

Approximation Approaches

  • Greedy algorithms: Polynomial-time approximations for structure learning
  • MCMC methods: Sample from the space of possible structures
  • Constraint propagation: Efficiently enforce consistency conditions

B.7 Connections to Linear Algebra

Matrix Properties

For adjacency matrix A of a DAG:

  • Nilpotency: A^d = 0 for some finite d
  • Spectral properties: All eigenvalues have zero real part
  • Determinant: det(I - A) ≠ 0

Structural Equation Perspective

The linear SEM Y = BY + ε corresponds to:

  • (I - B)Y = ε
  • Solution: Y = (I - B)⁻¹ε when I - B is invertible
  • Causal interpretation: B represents direct causal effects

Path Analysis

Wright's path analysis uses the adjacency matrix to:

  • Compute path coefficients: Products along directed paths
  • Calculate correlations: Sum over all connecting paths
  • Decompose effects: Separate direct and indirect causal effects

This mathematical framework provides the foundation for understanding how causal structures can be represented, manipulated, and learned from data.