Characterization and Learning of Causal Graphs with Small Conditioning Sets

Summary

Besides computational complexity, the weak spot of constraint-based causal discovery is the assumption of having an independence oracle. Especially with large conditioning sets, independence testing is difficult. This paper aims to address this limitation by restricting the number of conditioning variables and provides a sound framework that allows us to study the guarantees one can obtain for constraint-based structure learning if one restricts the size of the conditioning sets. The authors show that the results can contain bi-directed edges and relate the obtained graph to maximal ancestral graphs. They further provide a sound algorithm to learn such graphs and evaluate it on a few synthetic and semi-synthetic examples. The theoretical contributions of the paper are interesting and presented clearly to most parts. The main limitation of the work are the points that I mention with respect to the empirical evaluation.

Strengths

- Rigorous definition of assumptions, goal, and solution that can be obtained under the concept of restricting the size of the conditioning set. - The new formulation of k-closed graphs was introduced well and discussed in the context of previous notions (ancestral graphs). Further, Markov equivalence and faithfulness are adapted for the introduced graphs. - The authors propose a learning algorithm k-PC to learn the Markov equivalence class of the introduced k-closure of the true DAG. - The proposed algorithm has been empirically evaluated to PC, LOCI and NOTEARS, and the code has been provided for reproducibility.

Weaknesses

- The performance gain seems to be only evident in small sample regimes. - The new approach does not clearly outperform LOCI & it would be interesting to see how PC performs when restricting the conditioning set, as well. - It would be interesting to study a real-world example, or DAGs with non-linear relations. I could imagine that on the latter, using a smaller conditioning set can be a more substantial advantage, as independence testing with large conditioning sets is especially difficult for arbitrary functional relationships. For more details on the problem and maybe a good source to motivate the proposed algorithm please consider Shah and Peters (2020) Shah, Peters, The Hardness of Conditional Independence Testing and the Generalised Covariance Measure, The Annals of Statistics, 2020 Minor (suggestions): - For easier comparison, it might be beneficial to compute the area under the curve for the metrics shown in Figure 3.

Questions

- What is the intuition of step 5 in the algorithm? Why do we have to exclude it for Corollary 4.2? Not much intuition is provided regarding this step, and it just occurs in Corollary 4.2. - I understand that if we just run the PC algorithm and restrict the conditioning set it does not inherit the same guarantees as PC-k, e.g., it would not find any bi-directed edges. What would be the other differences/failure cases of this naive approach? - Assume one naively restricts the maximum size of the conditioning set in the PC algorithm, which I think is an option in the pcalg package, for example. How does this version of PC perform if we restrict the conditioning size in a similar manner as for the proposed method (e.g., for the experiments shown in Fig. 3 & 4)? - How does the computational complexity or empirical runtime compare to PC?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Standard limitations occurring in constraint-based causal discovery (a variant of faithfulness, independence oracle).

Summary

A new structure learning approach is proposed in limited data settings. In these settings, existing constraint-based causal discovery approaches struggle with statistical tests of independence. The main insight is that we can define an equivalence class of graphs based on an upper bound on the size of the conditioning set. Using this, a new learning algorithm is presented to learn the equivalence class.

Strengths

The paper is well-motivated and clear in its contributions. The problem of causal discovery from limited datasets seems to be a significant one. The novel contributions include introducing the formalism of K-Markov equivalence which can then be used to derive a learning algorithm. The soundness of the algorithm is guaranteed and the completeness is shown in some cases. Overall the theoretical contributions seem strong in this work.

Weaknesses

On the empirical side, comparisons are performed with state of the art structure learners on synthetic and semi-synthetic datasets. Since the motivation of the work was causal discovery from limited data, using some more real-world cases could have made the experiments much stronger. Overall, perhaps the empirical evaluation is not as strong as the theoretical contributions of the paper.

Questions

Are there real-world examples of learning from limited conditioning sets that could perhaps be used to strengthen the experimental evaluation?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

There are no limitations that are explicitly mentioned in the paper.

Summary

The authors study the problem of causal learning with bounded conditioning sets. It is an important question that up to what set of equivalence graphs a learner can infer a causal graph when it can only perform conditional independence tests with limited size of the conditioning sets. They characterize the equivalence set and propose a sound constraint-based algorithm for learning it.

Strengths

The authors study an important research question. The paper is well-organized. The results are quite relevant and important. It nicely establishes the connections between the existing results about Markov equivalence class and newly define k- Markov equivalence class that is the set of causal graphs that have the same conditional independences with conditioning sets at most k. This results can be a foundation for further developments in causal graph learning.

Weaknesses

A discussion about the complexity of the proposed algorithm will improve the paper. For instance, what is the complexity of checking whether two given DAGs are k-Markov equivalent?

Questions

See above.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors adequately addressed the limitations.

Summary

While I have the background to understand this paper, I'm afraid I am not well positioned to judge its novelty and significance in the causal discovery subfield. In short, the PC algorithm struggle when conditioning sets are large, so the authors propose a modification of Markov equivalence for bounded conditioning sets, then graphically characterize this relationship, and then propose the k-PC algorithm that is more successful in synthetic small small regimes. Nothing in the math or presentation seems incorrect to me, though I did not closely examine the more technical parts of the paper. The experiments are on synthetic data, which is typical in this subfield, but that makes it difficult to know whether k-PC has practical advantages over PC in real-world cases, as there are likely regimes where PC is superior. Overall, this seems like competent well done work, but I lean towards rejection for this paper. The modification of PC and Markov equivalence for bounded conditioning sets seems like a straightforward and simple modification of existing definitions, so the contribution does not seem novel and significant to me. If there were convincing empirical results that showed this change makes causal discovery viable in new real-world contexts I might be convinced, but as it stands its unclear to me whether the synthetic experiments are good evidence of this, especially with how little prose was in the main text describing them. This might be more appropriate for a conference or workshop that is more narrowly focused on causality. I'm perfectly happy to be convinced otherwise, or have my opinion ignored in favor of reviewers/metareviewers with a better understanding of the subfield!

Strengths

See main

Weaknesses

See main

Questions

See main

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See main

Summary

This paper aims to address the problem that in constraint-based causal discovery based on conditional independence tests, the tests become statistically unreliable with limited data when the conditioning sets are large. The proposed solution is to use only conditional independence tests for relatively small conditioning sets. To facilitate this goal, this paper provides a characterisation of k-Markov equivalence between causal DAGs, in the sense of entailing the same conditional independence statements in which the conditioning set has a cardinality not exceeding k. Since the characterisation is in terms of maximal ancestral graphs, a FCI-like algorithm is proposed to learn such equivalence classes and is empirically evaluated against some benchmarks.

Strengths

This paper is well written and very readable. The technical results are sound and the empirical evaluation is reasonable.

Weaknesses

Unfortunately, as far as I can tell, this paper largely reproduces the results of an old paper by Peter Spirtes (2001), "An Anytime Algorithm for Causal Inference", Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics. It seems to me that all the main results and insights of this paper were already presented in Spirtes's paper. I may have missed something important. I will increase my score if the authors can convince me that their contributions remain sufficiently original and significant given Spirtes's paper.

Questions

Are the main results of this paper a reproduction of Spirtes's (2001) results?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

N/A

Thanks

Thanks for the response. I can understand the difficulty with "real-world" causal structures, but the availability of code should help follow-on work.

Score increased

Thanks for the helpful response to my question. I still think the results are fairly easy given what is already shown by Spirtes, but I agree that some of them are not simply corollaries of Spirtes's results. I have increased my score to 5.