Active Structure Learning of Causal DAGs via Directed Clique Tree

• URL: http://arxiv.org/abs/2011.00641v1
• Date: Sun, 1 Nov 2020 23:11:17 GMT
• Title: Active Structure Learning of Causal DAGs via Directed Clique Tree
• Authors: Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, Karthikeyan Shanmugam
• Abstract summary: 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. We also present 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.
• Score: 28.637447727749
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 https://github.com/csquires/dct-policy

Related papers

• A Full DAG Score-Based Algorithm for Learning Causal Bayesian Networks with Latent Confounders [0.0]
  Causal Bayesian networks (CBN) are popular graphical probabilistic models that encode causal relations among variables. This paper introduces the first fully score-based structure learning algorithm searching the space of DAGs that is capable of identifying the presence of some latent confounders.
  arXiv  Detail & Related papers  (2024-08-20T20:25:56Z)
• Interventional Causal Discovery in a Mixture of DAGs [34.82590796630406]
  This paper addresses the hitherto unknown role of interventions in learning causal interactions among variables governed by a mixture of causal systems. It aims to identify edges that exist in at least one component DAG of the mixture, referred to as true edges.
  arXiv  Detail & Related papers  (2024-06-12T22:12:03Z)
• Causality is all you need [63.10680366545293]
  Causal Graph Routing (CGR) is an integrated causal scheme relying entirely on the intervention mechanisms to reveal the cause-effect forces hidden in data. CGR can surpass the current state-of-the-art methods on both Visual Question Answer and Long Document Classification tasks.
  arXiv  Detail & Related papers  (2023-11-21T02:53:40Z)
• Discovering Dynamic Causal Space for DAG Structure Learning [64.763763417533]
  We propose a dynamic causal space for DAG structure learning, coined CASPER. It integrates the graph structure into the score function as a new measure in the causal space to faithfully reflect the causal distance between estimated and ground truth DAG.
  arXiv  Detail & Related papers  (2023-06-05T12:20:40Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Subset verification and search algorithms for causal DAGs [13.108039226223793]
  We study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges) We prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here.
  arXiv  Detail & Related papers  (2023-01-09T06:25:44Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• GFlowCausal: Generative Flow Networks for Causal Discovery [27.51595081346858]
  We propose a novel approach to learning a Directed Acyclic Graph (DAG) from observational data called GFlowCausal. GFlowCausal aims to learn the best policy to generate high-reward DAGs by sequential actions with probabilities proportional to predefined rewards. We conduct extensive experiments on both synthetic and real datasets, and results show the proposed approach to be superior and also performs well in a large-scale setting.
  arXiv  Detail & Related papers  (2022-10-15T04:07:39Z)
• Explainable Sparse Knowledge Graph Completion via High-order Graph Reasoning Network [111.67744771462873]
  This paper proposes a novel explainable model for sparse Knowledge Graphs (KGs) It combines high-order reasoning into a graph convolutional network, namely HoGRN. It can not only improve the generalization ability to mitigate the information insufficiency issue but also provide interpretability.
  arXiv  Detail & Related papers  (2022-07-14T10:16:56Z)
• Effect Identification in Cluster Causal Diagrams [51.42809552422494]
  We introduce a new type of graphical model called cluster causal diagrams (for short, C-DAGs) C-DAGs allow for the partial specification of relationships among variables based on limited prior knowledge. We develop the foundations and machinery for valid causal inferences over C-DAGs.
  arXiv  Detail & Related papers  (2022-02-22T21:27:31Z)
• Almost Optimal Universal Lower Bound for Learning Causal DAGs with Atomic Interventions [2.750124853532831]
  We prove a new universal lower bound on the number of atomic interventions that an algorithm would need to perform in order to orient a given MEC. Our lower bound is provably better than previously known lower bounds.
  arXiv  Detail & Related papers  (2021-11-09T11:58:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.