Revisiting Causal Discovery from a Complexity-Theoretic Perspective
Authors: Robert Ganian, Viktoriia Korchemna, Stefan Szeider
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper investigates the complex relationship between the graph structure and the efficiency of constraint-based causal discovery algorithms. Our main contributions include (i) a near-tight characterization of which causal graphs admit a small d-separating set for each pair of vertices and thus can potentially be efficiently recovered by a constraintbased causal discovery algorithm, (ii) the explicit construction of a sequence of causal graphs on which the influential PC algorithm might need exponential time, although there is a small d-separating set between every pair of variables, and (iii) the formulation of a new causal discovery algorithm which achieves fixed-parameter running time by considering the maximum number of edge-disjoint paths between variables in the (undirected) super-structure as the parameter. A distinguishing feature of our investigation is that it is carried out within a more fine-grained model which more faithfully captures the infeasibility of performing accurate independence tests for large sets of conditioning variables. |
| Researcher Affiliation | Academia | Robert Ganian , Viktoriia Korchemna , Stefan Szeider Algorithms and Complexity Group, TU Wien, Vienna, Austria {rganian,vkorchemna,sz}@ac.tuwien.ac.at |
| Pseudocode | Yes | The PC algorithm... This phase consists of the following sequence of procedures [Glymour et al., 2019]: 1. Construct a complete undirected graph over the provided set of variables. 2. Eliminate edges between variables that are either unconditionally independent or are known to be independent due to expert knowledge (non-adjacent in the super-structure). 3. For each pair of variables {X, Y } having an edge between them, and for each variable Z with an edge connected to either of them, eliminate the edge between X and Y if X is conditionally independent of Y given Z. 4. For each pair of variables {X, Y } having an edge between them, and for each pair of variables {Z, W} with edges both connected to X or both connected to Y , eliminate the edge between X and Y if X Y | {Z, W}. 5. Continue checking independencies conditional on subsets of variables of size 3, . . . , i until there are no more adjacent pairs X, Y , such that there is a subset of variables of size i such that all of the variables in the subset are adjacent to X or all adjacent to Y . |
| Open Source Code | No | The paper does not provide any link or explicit statement about the availability of source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on complexity analysis and algorithm design, not empirical evaluation on datasets. Therefore, no public dataset access information is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper focusing on algorithm design and complexity analysis. It does not describe any empirical experiments or the hardware used to run them. |
| Software Dependencies | No | This is a theoretical paper and does not describe empirical experiments or specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not provide details on an experimental setup, hyperparameters, or training configurations. |