On Learning Necessary and Sufficient Causal Graphs

Summary

The paper introduces a novel method to identify causally relevant variables with respect to a specific target node. Leveraging the concept of probabilities of causation, the authors propose an approach that efficiently and systematically identifies a subgraph containing the relevant ancestors of the target node. This method has been evaluated using both artificial and real-world datasets.

Strengths

* The paper is well written and motivated. In particular, the problem setting is nicely introduced. * Comprehensive mathematical definitions and explanations. * The method is relevant for different causal inference problems. See the Question section for further remarks.

Weaknesses

* The paper has a slightly confusing mixture of the potential outcome (PO) framework (for instance, using A1 and A2) and the graphical causal model framework. The notation from the PO framework doesn't seem essential here, especially considering that the majority of the work is based on graphical causal models. * It seems there is an implicit assumption that the target variable of interest is a leaf node in the graph (i.e., it has no descendants). While this aligns with the typical PO causal effect estimation setup, the proposed method could also be beneficial for other causal inference questions beyond effect estimation. * Unclear if the proposed method is scale invariant, which would be an important property to avoid arbitrary changes in the result due to (often) unknown rescalings. This concern mostly stems from the references to NOTEARS, which is not scale invariant (see “Unsuitability of NOTEARS for Causal Graph Discovery” by Kaiser et al.). This could be discussed more clearly. * Although the empirical results are convincing, the number of baseline methods is quite limited. Here, more and newer causal discovery algorithms could be included in the evaluation. See the Question section for additional points and remarks.

Questions

A few general remarks and questions: * The abstract is excellent, being very concise, nicely motivating the problem, and describing the goal of the paper. * The title could be more precise in mentioning that it pertains to a specific target variable, especially since causal discovery algorithms typically don’t have that (simplifying) restriction. * The beer and diapers example is engaging, but it implies that we either do not observe the hidden confounder or would incorrectly learn a model that includes "diapers" to predict "beer". Is this meant as an example of including unnecessarily many variables or as an example where causal discovery fails due to hidden confounders? * Related to the previous point, it appears that the authors have a typical PO setting of "treatment, covariates, and outcome" in mind. I might have missed this detail, but for instance, it seems (implicitly) assumed that no variable is a causal child of the target. The general setting could be introduced more clearly. * The scoring method appears to target effect estimation tasks. If that is indeed the causal inference question you're aiming for, this should be discussed more explicitly. Generally, the proposed methods might also be interesting for other causal questions, such as contribution or root cause analysis. * The works “Quantifying causal influences” and “Quantifying intrinsic causal contributions via structure-preserving interventions” by Janzing et al. might provide an interesting alternative for more general (and non-linear) measures for quantifying causal influences. * The limitation to a discrete target variable is relatively stringent. Perhaps the previously mentioned work could inspire ideas on how to generalize this further in follow-up research. * A minor point: The edges D_X are not formally introduced in detail. * In Definition 3.1, does this only include direct parents and grandparents but not all other (potentially further) ancestors? * In the discussion of Example 4.7, it's somewhat confusing why one would include X_D in the first place if the graph is known. And if it is unknown, why would one even "blindly" include all variables in the model, considering that there could also be variables that are causal children of the target? Again, this seems to implicitly assume that the target node of interest is a leaf node. * Section 5 is insightful, effectively blending the mathematical details with the overall procedure. * It's unclear if your method only works for linear relationships/linear structural causal models (SCMs). Could you provide clarification? * Overall, the experimental results are compelling, but the selection of baseline methods could be broader given the significant advances in recent causal discovery approaches. --Update after rebuttal-- I have read the rebuttal and further discussed with the authors. Since there are several smaller points that need to be revised in the final version, I stick to my initial (positive) score.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

3 good

Limitations

There are no concerns regarding societal impact. For technical limitations, refer to the points raised in the Questions and Weakness sections.

Summary

The paper deals with proposing a necessary and sufficient causal graph that explicitly only model the causal variables required rather than the complete causal graphs that can be inefficient and also introduce spurious correlations between variables.

Strengths

1. Important problem, well-defined and well written. The NSC is intuitive and makes perfect sense. 2. Using or rather extending the POC concept to assess the necessity and sufficiency of features in determining the outcome is very interesting.

Weaknesses

1. I have some concerns regarding the scalability of the method and the max number of samples considered is 100. Also it would have been ideal if some real world example was shown and experimented with. 2. Assuming Markovian condition limits the overall applicability of the methods especially in the real world scenarios. 3. Conclusion section reduced to only limitations and future work hindering the overall completeness of the paper. I know this would have been done due to the space limit but in my personal opinion every paper should have a proper conclusion section.

Questions

1. Can the authors comment on how the Markovian assumption limits the applicability of their method? 2. Another factor is that the variables considered are only binary. This again effects the applicability and it would be nice to see some discussion on this. 3. Considering 100 samples does not explicitly show the scalability of the method. Can some more large scale experiments be shown? Overall a nice paper with a simple yet nice idea but not without its flaws. I lean towards acceptance as of now but have concerns about the applicability of the method in real world scenarios and will wait for the authors replies to make a final decision.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

2 fair

Contribution

3 good

Limitations

No concerns here.

Summary

This paper is concerned with learning causal graphs from observational data. In particular, the authors propose to learn a subgraph of the full causal graph, which they refer to as necessary and sufficient causal graphs (NSCGs). They propose an algorithm which measures conditional probabilities of causation between variables to measure the causal effect of some treatment variable on the target variable. They evaluate their algorithm on synthetic and one real dataset and compare its performance against three other popular CD algorithms.

Strengths

The paper is well written and interesting to read. The authors provide illustrative examples that help understand the theory and practical implications!

Weaknesses

- Not all causal discovery algorithms assume causal sufficiency, e.g. FCI [A] and related algorithms, output a CPDAG without assuming causal sufficiency. There exists some other notable work on this topic [e.g. B, C] - I find the experimental evaluation on synthetic data to be too limited. The authors compare their method only to three other Causal Discovery Algorithms (including NOTEARS, which is actually not suitable for causal discovery because of missing scale-invariance [D]). In particular, they do not compare their method to algorithms that do not assume causal sufficiency (e.g. FCI). - On the one real-world dataset, the authors compare their method to NOTEARS only. - I find it difficult to follow their arguments, why the proposed algorithm performs better than NOTEARS on the real-world dataset. Statements like “This gene is required for sulfur amino acid synthesis” (L. 349) need a reference and further explanation. [A] P. Spirtes, C. Glymour, and R. Scheines, Causation, Prediction, and Search. The MIT Press, 2001. doi: 10.7551/mitpress/1754.001.0001. [B] J. M. Ogarrio, P. Spirtes, and J. Ramsey, “A Hybrid Causal Search Algorithm for Latent Variable Models,” in Proceedings of the Eighth International Conference on Probabilistic Graphical Models, PMLR, Aug. 2016. [C] R. Bhattacharya, T. Nagarajan, D. Malinsky, and I. Shpitser, “Differentiable Causal Discovery Under Unmeasured Confounding,” Proceedings of the International Conference on Artificial Intelligence and Statistics, vol. 130, Apr. 2021. [D] M. Kaiser and M. Sipos, “Unsuitability of NOTEARS for Causal Graph Discovery when Dealing with Dimensional Quantities,” Neural Processing Letters, vol. 54, no. 3, 2022.

Questions

- I found a small typo in L. 105: “while keeping the rest [of the] model unchanged” - Could the authors comment on whether they think using the Structural Intervention Distance (SID) [E] would be a meaningful additional metric for their empirical evaluation? - Why do the authors evaluate their algorithm on a single real-world dataset only? Why did they choose this particular dataset and not one of the more famous ones, e.g. [F]? - Can the authors comment on whether their algorithm is scale-invariant, given NSCSL uses absolute causal effects? [E] Jonas Peters and Peter Bühlmann. Structural intervention distance for evaluating causal graphs. Neural Computation, 27(3):771–799, 2015. [F] K. Sachs, O. Perez, D. Pe’er, D. A. Lauffenburger, and G. P. Nolan, “Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data,” Science, vol. 308, no. 5721, pp. 523–529, Apr. 2005.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

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

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The authors provide an open discussion on the limitations of their proposed algorithm, which is greatly appreciated! Another limitation might be the strong assumptions on conditionals, however, this is a limitation of most causal discovery algorithms.

Summary

This paper studies the problem of feature selection when performing causal discovery and contributes to the limited literature in this field. Given a set of features, the main goal is to learn a causal graph from a subset of these features such that the learned graph only contains features that are “necessary and sufficient” for explaining an outcome of interest. This paper then develops two notions of quantifying the necessary and sufficient features using POC (probability of causation) and DE (direct effect)/TE (total effect). Given the measures to quantify the relevant features, they formulate a learning algorithm that jointly selects these relevant features (including the outcome of interest) and learns the causal graph. They also experimentally verify their method on four synthetic and one real-world dataset and show improvement over other baselines.

Strengths

1. **Clarity**: This paper is clearly written and easy to follow. Though there is one limitation to the motivation of using POC (probability of causation) as the main metric to quantify the spurious features (see comment1 in the weakness part of the review). 2. **Significance**: This paper brings the notion of variable selection when learning the causal graph which is less explored in the literature. 3. **Theory:** Theorem 4.6 connects the two possible quantities i.e. POC and DE/TE, that can be used to quantify the spuriousness of each other and gives an expression for their lower bound in terms of marginals from the observational distribution which is novel. 4. **Experiment**: Across synthetic and real datasets one of their method i.e. NSCSL-TE shows consistent improvement compared to other baselines considered over different considered metrics (FDR, TPR, and SHD).

Weaknesses

1. **Why POC instead of directly considering DE/TE**: Shouldn’t all the features with non-zero DE/TE on the outcome of interest should be considered in the final selected graph? Why POC is more fundamental than DE/TE is not properly motivated. I understand that both quantities are related (as stated in Theorem 4.6) but if the goal is to remove the spurious features when creating the causal graph then shouldn’t we directly use the TE/DE? 2. **Theory**: There is no guarantee that selecting the features based on the POC/DE/TE will converge towards the actual set of necessary and sufficient features as admissible by Definition 3.2. 3. **Experiment**: The synthetic setup considered in the paper assumes linear SEM as the data-generating process that might be limiting for the real-world DGPs (data-generating process). In the appendix, the author extends their algorithm for non-linear DGPs. It would be interesting to see some results on synthetic datasets with non-linear DGPs that could further attest to the applicability of their method in real-world scenarios in addition to one real-world dataset already considered in the paper.

Questions

1. **Theory**: Line 125-126 state that Definition 3.1 refer to the sub-structure in the whole graph $G_{O}$ containing directed edges or path towards Y. It is not clear how the constraint on conditional probability distribution in Definition 3.1 allows $G_{V}$ to have features/nodes from $G_{O}$ that have a path towards Y. An example or an explanation will be helpful. 2. **Experiment**: Why does TPR decrease for NSCSL-DE for the S2-S4 on increasing the sample size?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

3 good

Presentation

3 good

Contribution

2 fair

Limitations

NA

Summary

This paper addresses the challenge of discovering causal relationships among variables within a complex graph by proposing the learning of necessary and sufficient causal graphs (NSCGs). Unlike existing methods that consider all variables in the graph, NSCGs exclusively consist of causally relevant variables for a specific outcome of interest, referred to as causal features. The authors introduce the concept of probabilities of causation to assess the importance of features in the causal graph and identify a subgraph relevant to the outcome.

Strengths

1. The problem (i.e., learning a class of necessary and sufficient causal graphs) studied in this paper is interesting; 2. The necessary and sufficient causal structural learning (NSCSL) algorithm offers a new method to learn NSCGs from data; 3. The authors have provided theoretical support for their approach; 4. The experiments were conducted on both synthetic and real data.

Weaknesses

1. This paper does not explicitly discuss the computational complexity of the NSCSL algorithm compared to other existing algorithms. Causal structure learning is often computational expensive, which significantly restricts its practical utility when the real system is complex with hundreds or even thousands of features. Providing a comparison of the computational requirements and runtime of the proposed algorithm could further enhance the assessment of its workload. This becomes particularly important when considering variable selection methods in causal graphs. Without such a comparison, it remains uncertain whether NSCSL would be practically viable, as it might prove to be more computationally expensive than other established methods. Thus, addressing this aspect is paramount to establishing the practical utility and potential applicability of NSCSL in real-world scenarios. 2. The current experimental results do not convincingly demonstrate the effectiveness of the proposed method. Concerning the synthetic data, the authors have not provided a clear explanation of the ER model and the reasons for choosing it over other models such as the Barab´asi–Albert model or scale-free model. It would be more appropriate to utilize different models to generate diverse synthetic data. Additionally, the generated data is limited to only 100 samples or features for the first three scenarios, making it less practically applicable. Moreover, the evaluation's reliance on relatively old baselines (NOTEARS, PC, ICA) is questionable, and it should include state-of-the-art algorithms like DYNOTEARS, DAG-GNN, and GSGES. Regarding the real data, the paper relies solely on one gene data without a ground-truth causal structure. To enhance the validity, benchmark data sets like the real dataset from Sachs et al. (2005) should be incorporated, as it comes with a consensus network that is accepted by the biological community. Finally, there are several parameters in the proposed method. Parameter sensitivity analysis should be included. K. Sachs, O. Perez, D. Pe’er, D. A. Lauffenburger, and G. P. Nolan. Causal Protein-Signaling Networks Derived from Multiparameter Single-Cell Data. Science, 2005. 3. This paper is not easy to follow due to so many abbreviations and mathematical notations. To enhance the paper's readability, including a notation table and full form of abbreviations on the current page would be beneficial, ensuring that readers can easily understand the content without the need for constant cross-referencing.

Questions

1. What are the computational complexity and runtime of the NSCSL algorithm compared to other existing algorithms? 2. Why choosing ER model, not the other models, to generate the data? 3. Why not consider more recent algorithms as the baselines? 4. The pros and cons of NSCSL vs. variable selection methods in causal graphs or backtracking on causal graphs from the outcomes of interest. 5. The authors should conduct parameter sensitivity analysis in the experiment. I have read the author’s rebuttal. Some of my concerns have been addressed.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

2 fair

Contribution

2 fair

Limitations

As pointed out by the authors, one potential limitation is the assumption of no unmeasured confounders, which may not always hold in real-world scenarios.

Thank you for your response

I would like to thank the authors for their response and the new results. My concerns are clarifies and thus I have raised my score accordingly to 6.

Eagerly Looking Forward to Feedback on Our Response

We deeply appreciate the time and effort you have devoted to reviewing our work and providing us with insightful, detailed, and encouraging feedback. Following your constructive suggestions, we have conducted six additional sets of experiments and have further clarified our computational complexity and advancements. All of these details can be found in our response and within the one-page PDF file. We sincerely hope our further clarifications and experiments can fully address your concerns. We are eagerly looking forward to your kind feedback!

Eagerly Looking Forward to Feedback on Our Response

We greatly appreciate the time and effort you've invested in reviewing our work and providing insightful and constructive feedback! In response to your valuable suggestions, we have conducted additional experiments on the non-linear case and further clarified our motivation, definition, and simulation results, followed by an additional theory for graph consistency. We earnestly hope that these clarifications and expanded experiments will thoroughly address your concerns. We are eagerly looking forward to your kind feedback!

Eagerly Looking Forward to Feedback on Our Response

We sincerely appreciate the time and effort you've devoted to reviewing our work, and to providing many valuable and insightful feedback! Following your constructive suggestions, we have conducted five additional sets of experiments and have further clarified our assumptions, base learner, scale-invariance, and real data evaluation. All of these details can be found in our response and within the one-page PDF file. We sincerely hope our further clarifications and experiments can fully address your concerns and can be helpful in the evaluation of our work. We are eagerly looking forward to your kind feedback!