Active Structure Learning of Causal DAGs via Directed Clique Tree (2020-11-01T00:00:00.000000Z)

TL;DR

This work develops a universal lower bound for single-node interventions that establishes that the largest clique is always a fundamental impediment to structure learning and presents a two-phase intervention design algorithm that matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques.

Abstract

A growing body of work has begun to study intervention design for efficient structure learning of causal directed acyclic graphs (DAGs). A typical setting is a causally sufficient setting, i.e. a system with no latent confounders, selection bias, or feedback, when the essential graph of the observational equivalence class (EC) is given as an input and interventions are assumed to be noiseless. Most existing works focus on worst-case or average-case lower bounds for the number of interventions required to orient a DAG. These worst-case lower bounds only establish that the largest clique in the essential graph could make it difficult to learn the true DAG. In this work, we develop a universal lower bound for single-node interventions that establishes that the largest clique is always a fundamental impediment to structure learning. Specifically, we present a decomposition of a DAG into independently orientable components through directed clique trees and use it to prove that the number of single-node interventions necessary to orient any DAG in an EC is at least the sum of half the size of the largest cliques in each chain component of the essential graph. Moreover, we present a two-phase intervention design algorithm that, under certain conditions on the chordal skeleton, matches the optimal number of interventions up to a multiplicative logarithmic factor in the number of maximal cliques. We show via synthetic experiments that our algorithm can scale to much larger graphs than most of the related work and achieves better worst-case performance than other scalable approaches. A code base to recreate these results can be found at this https URL

Authors

K. Greenewald

2 papers

Karthikeyan Shanmugam

2 papers

C. Squires

1 papers

TL;DR

Abstract

Authors

References33 items

Competitive ratio versus regret minimization: achieving the best of both worlds

Handbook of Graphical Models

Experimental Design for Cost-Aware Learning of Causal Graphs

Counting and Sampling from Markov Equivalent DAGs Using Clique Trees

Elements of Causal Inference: Foundations and Learning Algorithms

Budgeted Experiment Design for Causal Structure Learning

Cost-Optimal Learning of Causal Graphs

Optimal Experiment Design for Causal Discovery from Fixed Number of Experiments

Learning Causal Graphs with Small Interventions

Chordal Graphs and Semidefinite Optimization

Two optimal strategies for active learning of causal models from interventional data

Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning

Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data

Causation, Prediction, and Search

Clique tree generalization and new subclasses of chordal graphs

Enumerating Markov Equivalence Classes of Acyclic Digraph Models

Using Bayesian Networks to Analyze Expression Data

Causal inference and causal explanation with background knowledge

Chordal Graphs and Their Clique Graphs

An optimal on-line algorithm for metrical task system

Sample Efficient Active Learning of Causal Trees

Causation and intervention

Experiment selection for causal discovery

Active Learning of Causal Networks with Intervention Experiments and Optimal Designs

N-1 Experiments Suffice to Determine the Causal Relations Among N Variables

show that n − 1 single-node interventions suffice to determine the orientations of all edges between n nodes. We sum this value over all residuals

Causality : Models , Reasoning , and Inference

paΓD (C). Proof. We begin by citing a useful result on the relationship between clique trees and clique graphs when the clique contains an intersection-comparable edge: Lemma 7 (Galinier et al

Assuming Γ G is intersection-incomparable, Algorithm 1 uses at most (3 log 2 C max +

D) m(D ), the total number of interventions used by Algorithm 1 is the sum over the number interventions used for each chain component, and C max ≥ |C(E(D))| for all D

The second phase of Algorithm 1 (line 6-8) uses at most C∈C(D ) | ResT D (C)| − 1 single-node interventions for the moral DAG D ∈ CC(D)

We start by proving bounds for each of the two phases: Lemma 8. Algorithm 2 uses at most log 2 |C| clique-interventions. Moreover, assuming T G is intersection-incomparable

We will show that Algorithm 1 uses at most (3 log 2 |C(E(D))| + 2)m(D ) single-node interventions

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names