Graph-based Complexity for Causal Effect by Empirical Plug-in
This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom, which assumes that high dimensional probabilistic functions will lead to exponential evaluation time of the estimand. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph. In particular, we show that both the treewidth and hypertree width of the estimand's structure bound the evaluation complexity of the plug-in estimands, analogous to their role in the complexity of probabilistic inference in graphical models. Often, the hypertree width provides a more effective bound, since the empirical distributions are sparse.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Causal Graph Learning via Distributional Invariance of Cause-Effect Relationship
This paper introduces a new framework for recovering causal graphs from observational data, leveraging the observation that the distribution of an effect, conditioned on its causes, remains invariant to changes in the pr…
Graph LearningCLEAR: Can Language Models Really Understand Causal Graphs?
Causal reasoning is a cornerstone of how humans interpret the world. To model and reason about causality, causal graphs offer a concise yet effective solution. Given the impressive advancements in language models, a cruc…
PhilosophyAdvancing Edge Classification through High-Dimensional Causal Modeling of Node-Edge Interplay
Edge classification, a crucial task for graph applications, remains relatively under-explored compared to link prediction. Current methods often overlook the potential causal influences of node features on edge features,…
Graph Neural NetworkCausal InferenceLink PredictionCausal inference using the algorithmic Markov condition
Inferring the causal structure that links n observables is usually based upon detecting statistical dependences and choosing simple graphs that make the joint measure Markovian. Here we argue why causal inference is also…
Causal InferenceA Closer Look at the Application of Causal Inference in Graph Representation Learning
Modeling causal relationships in graph representation learning remains a fundamental challenge. Existing approaches often draw on theories and methods from causal inference to identify causal subgraphs or mitigate confou…
Graph Representation LearningCausal InferenceGraph Learning