Verification and search algorithms for causal DAGs
Authors: Davin Choo, Kirankumar Shiragur, Arnab Bhattacharyya
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We implement our verification algorithm and test its correctness on some well-known graphs such as cliques and trees, for which we know the exact verification number. In addition, we implement Algorithm 1 and compare its performance with other known atomic search algorithms [HG08, HB14, SKDV15, SMG+20] via the experimental setup of [SMG+20]: on synthetic graphs of varying sizes, we compare the runtime and total number of interventions performed compared to the verification number of the underlying DAG. In Appendix H, we provide the full experimental details and results of running various search algorithms (including ours) on different graphs. Qualitatively, our algorithm is competitive with the state-of-the-art search algorithms while being 10x faster in some experiments. Fig. 2 shows a subset of these results. |
| Researcher Affiliation | Academia | National University of Singapore, Stanford University |
| Pseudocode | Yes | Algorithm 1 Search algorithm via graph separators. 1: Input: Essential graph E(G ), intervention size k. Output: A fully oriented graph G 2 [G ]. 2: Initialize i = 0 and I0 = ;. 3: while EIi(G ) still has undirected edges do 4: For each H 2 CC(EIi(G )) of size |H| 2, find a 1/2-clique separator KH using Theorem 20. Define Q = {KH}H2CC(EIi(G )),|H| 2 as the union of clique separator nodes. 5: if k = 1 or |Q| = 1 then Define Ci = Q as an atomic intervention set. 6: else Define k0 = min{k, |Q|/2}, a = d|Q|/k0e 2, and = dloga ne. Compute labelling scheme of [SKDV15, Lemma 1] on Q with (|Q|, k0, a), and define Ci = {Sx,y}x2[ ],y2[a], where Sx,y Q is the subset of vertices whose xth letter in the label is y. 7: Update i i + 1, intervene on Ci to obtain EIi(G ), and update Ii Ii 1 [ Ci. 8: end while |
| Open Source Code | Yes | The implementations, along with entire experimental setup, are available at https: //github.com/cxjdavin/verification-and-search-algorithms-for-causal-DAGs. |
| Open Datasets | No | The paper mentions using 'synthetic graphs' for experiments but does not provide specific access information (link, DOI, formal citation) for a publicly available dataset. |
| Dataset Splits | No | The paper mentions using 'synthetic graphs' but does not specify any dataset splits (e.g., percentages, sample counts, or references to predefined splits) for training, validation, or testing. |
| Hardware Specification | No | The paper does not specify any details about the hardware (e.g., specific GPU/CPU models, memory) used for conducting the experiments. It only refers to 'running various search algorithms'. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers (e.g., Python, PyTorch, or other libraries with their versions) that would be needed to replicate the experiments. |
| Experiment Setup | No | The paper states that full experimental details are in Appendix H, which is not provided. The main text does not contain specific hyperparameters, training configurations, or system-level settings for the experiments, only mentioning 'synthetic graphs of varying sizes'. |