Sample Efficient Bayesian Learning of Causal Graphs from Interventions

We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.

Weakness of Writing:

We will rearrange the related work section in the revision to position the previous works and our study better.

Questions of Overall Significance:

The main contribution of this study is the Bayesian learning algorithm for causal discovery. We use DAG sample to efficiently compute the interventional distributions. With section 6, we want to show that the DAG sampler could be used in more general cases to estimate general causal queries and the case of "a set being a valid adjustment set" is presented as an example. We mentioned real-world scenarios of cloud computing and cancer detection. They can also be transformed into such causal queries without learning the whole graph. To elaborate more, for the root cause analysis in for cloud computing, we could estimate the posterior of the configuration of a vertex to be all outgoing from that vertex to its neighbors. For direct cause analysis in cancer research, we could estimate the posterior of that edge being directed from the potential cause to the cancer variable. Regarding the study of interventional experimental design, there have been plenty of works in the literature ([1], [2], [3], [4], ...), while few of them consider the cases of limited interventional samples. However, these cases are common in real-world settings since interventional samples are usually a lot more costly to retrieve then observational samples. Thus, in this paper we assume the access to observational distribution while limited intervetinoal samples to reflect such scenarios and our proposed algorithm outperforms previous works.

[1] Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.

[2] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926–939, 2014.

[3] Yang-Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(Nov):2523–2547, 2008.

[4] Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 33:21500–21511, 2020.

We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.

We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.

Weakness of Objective:

There are indeed plenty of studies in the literature that use Bayesian methods for causal discovery, but most of them have parametric assumptions like a linear causal model or additive Gaussian noise (see related works section). These methods fail when the assumptions do not hold. Our approach differs in that we do not make such assumptions, and we show the convergence rate theoretically.

In our study, we assume access to the observational distribution, which naturally leads to the CPDAG. Our work can be extended to the setting of uncertain CPDAGs by updating and tracking the posteriors of the CPDAGs together with the configurations.

Weakness of writing:

We will try to improve the writing and clarity of the paper to make it easier to follow. We will move some content from the introduction to the related works section to better position our paper.

Section 4.1 is intended to briefly describe the separating system since it is used in the algorithm and the analysis in Section 5.

Weakness of citation:

We will fix the citations.

Questions:

In practice, we can list all the configurations and examine them in parallel which is fast since cycle detection and unshielded collider detection algorithms are efficient. The suggested approach saves memory but has to be performed in sequence.

Additional Thoughts

While we value constructive criticism that can help us improve our work, we believe that the weaknesses mentioned are generic and can be easily fixed. For instance, comments regarding typos and writing, while valid for copyediting purposes, do not significantly impact the contributions of the paper. The reviewer mentions a lack of novelty as a weakness but does not provide specific points to substantiate this claim. In fact, our work has a clear position, which we state in the introduction and related works section.

A score of 3 suggests significant issues with the paper's contributions, methodology, or results. However, the reviewer does not articulate any major flaws that would warrant such a score. We thus kindly request that the reviewer reconsider the score or provide more justification for the decision to reject our paper. We thus kindly request that the reviewer reconsider the score or provide additional justification for their decision.

We thank the reviewer for the increasing the score. We want to briefly clarity the concerns below.

Although Bayesian causal discovery is not new, a fully non-parametric Bayesian approach is not tractable. Our work introduces a novel idea by using the $(n, k)$-separating system, followed by an enumeration of causal effects to partition the set of all possible DAGs into tractable sets. At the prediction stage, we combine the configurations with high posterior to return a DAG. Furthermore, we show in theory that our method is guaranteed to converge to the true DAG as sample size $m\rightarrow \infty$ in Lemma 1. Additionally, we show that when the sample size is large, the predicted graph would be the true graph with a high probability as shown in Theorem 3. This is the first work to show such guarantees in the context of sample-efficient causal discovery problems under mild faithfulness assumptions.

We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.

Weakness of Major 1:

Our approach differs from most of the Bayesian causal discovery paper in that we do not have a parametric representation of the structure. We do not directly calculate the posterior of each DAG since the size of MEC could be large and intractable [1]. Instead, we partition the DAGs into different configurations of a given target set to avoid keep tracking of posteriors of all the DAGs in an Bayesian approach. We could explicitly mention this difference in the paper.

Weakness of Major 2:

In our implementation, the interventional target is selected randomly. If the maximum posterior of a configuration is close to 1 ($>0.99$ for example), we remove this target to improve efficiency. This target selection process could be made adaptive to further improve the algorithm.

Weakness of major 3:

In our work, we assume the access to observational distribution. In our simulation, we use binary variables, so it takes $2^n$ in memory. When the graph is large, it is intractable. For a target of $k$ vertices, in the initialization step where we need to enumerate all the configurations, the complexity would be up to $2^{kd}$ where $d$ is the maximum degree. This can be large when the graph is large and dense. If the graph is large, our algorithm can only work when it is sparse, i.e., the maximum degree is less than $\log n$. However, usually causal graphs are sparse, and can be divided into smaller chain components with observational distribution, which can be oriented independently.

Weakness of major 4:

We can also compare the algorithms on other graphs like BA graph. We show the results in the extra pdf in Figure 1. We can see that our algorithm still outperforms others for scale-free graphs. In fact, with the access to the observational distribution, our algorithm does not rely on the type of graphs since the chain components are proved to be chordal [2] and can be oriented independently [3]. We could not run our algorithm with the mentioned real-world simulator since it does not provide the observational distribution.

Weakness of major 5:

We compared with the Avici model in [4] and the result if shown in the 1-page pdf of Figure 2. We compare with both 'scm-v0' and 'neurips-rff' model and the result shows that our method performs better. In fact, Avici does not seem to be converging with our simulated data. There could be several reasons for that. First, Avici has no guarantee of performance as mentioned in the paper, thus it might not perform well for some data. Besides, Avici may not work well with discrete data. Also, Avici could not take in too large data since it only loads data once, while our approach has this anytime property to return the optimal DAG with any amount of samples available.

[5] is also an important work. As it assume unknown interventions, we did not compare with it here, but we will add it in the related work section in revision.

Weakness of minor 1, 2:

We will fix these typos in the revision.

Question 2:

In the experiments, we use $k=3$ for small graphs ($n\leq10$) and $k=1$ for $n=20$. When the graph is small, using a slightly larger $k$ could make the algorithm more efficient, but when the graph gets large, we just use atomic interventions to avoid using too much memory.

Question 3:

In this study, we assume that at the beginning, all the DAGs in the MEC are equally likely to be the causal graph. Thus, we use equation 7 to calculate the prior of each configuration. More specifically, we divide the MEC size of the configuration by the MEC size of the whole graph. The MEC size could be efficiently calculated using algorithm in [6].

[1] He, Yangbo, Jinzhu Jia, and Bin Yu. "Counting and exploring sizes of Markov equivalence classes of directed acyclic graphs." The Journal of Machine Learning Research 16, no. 1 (2015): 2589-2609.

[2] Steen A Andersson, David Madigan, and Michael D Perlman. A characterization of markov equiva-389 lence classes for acyclic digraphs. The Annals of Statistics, 25(2):505–541, 1997.

[3] Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning, 55(4):926–939, 2014.

[4] Lorch, L., Sussex, S., Rothfuss, J., Krause, A., and Schölkopf, B. (2022). Amortized inference for causal structure learning. Advances in Neural Information Processing Systems, 35, 13104-13118.

[5] Hägele, A., Rothfuss, J., Lorch, L., Somnath, V. R., Schölkopf, B., and Krause, A. (2023, April). Bacadi: Bayesian causal discovery with unknown interventions. In International Conference on Artificial Intelligence and Statistics (pp. 1411-1436). PMLR.

[6] Marcel Wienöbst, Max Bannach, and Maciej Li ́skiewicz. Polynomial-time algorithms for counting and sampling markov equivalent dags with applications. Journal of Machine Learning Research, 24(213):1–45, 2023.

We hope that our rebuttal has clarified the reviewer's concerns and would request that they reconsider their score. We would be more than happy to engage in further discussions if the reviewer has additional questions.

We thank the reviewer for increasing our score but would like to briefly address the concerns highlighted by reviewer.

AVICI experiment details

In our experiment, we did not fine-tune the pre-trained models using observational samples. We directly feed them with the interventional samples. We will try to fine-tune the pre-trained model first with the observational samples.

Question of real-world application

In real-world applications, if we have access to large number of observational samples, we can apply our algorithm on a set of candidate CPDAGs, We will also add a few simple experiments to validate the case study in section 6.

Experiments with real-world simulators

We will add experiments using real-world simulators.

We thank the reviewers for their thorough and constructive feedback. Below, we address each of the points raised.

Weakness of "small scale" experiments:

In this work, we assume the access to the joint observational distribution. When the graph is large, it is intractable in practice to handle the joint distribution. For example, in our implementation, we use binary variables. A graph of 50 vertices would lead to a table of $2^{50}$ numbers. Also, to enumerate the configurations of a set of target of $k$ vertices, we have to consider up to $2^{kd}$ configurations in the worst case where $d$ is the maximum degree of the target. This will be huge complexity for large dense graphs, so we just experimented on "small scale" graphs. Although in practice, causal graphs can be large, they are usually sparse and with observational distribution, it can be divided into small chain components and orient independently.

Question about citations:

We will add this mentioned paper to this section.

Questions about typos:

Thanks for pointing out the typos. We will fix them in revision.

We hope that our rebuttal has clarified the reviewer's concerns, and we would be more than happy to engage in further discussions if the reviewer has additional questions.