Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a conditional independence test in a linear Gaussian setting but the variance of the error term may not be a constant but affected by a function of a subset of its parents or sampling index (e.g., individual-dependent variance or a time-series like setting). Hence, the authors designed heteroskedasticity-aware weighted partial correlation where the weights come from inverse of variances, which is estimated using a windowing approach. However, this test works with expert knowledge about heteroskedasticity (whether it is caused by sampling index or heteroskedastic parent). In a causal discovery setting, not knowing the parents of variables, it only assumes that the heteroskedasticy comes from sampling index.
strengths_and_weaknesses: 
Strengths
- well-motivated problem and a theoretically correct solution (under some assumptions.)
- a simple solution to an important problem.

Weaknesses

- As the authors acknowledged, Assumption 1 (and 5 for PC algorithm) requires expert knowledge.

It seems hard for me to find weaknesses of the paper considering that the authors did a right thing to solve a problem and acknowledged limitations clearly that are not due to the authors but comes from the nature.

questions: 
- What if we can use non-parametric conditional independence test? Will it be (certainly) even weaker than OLS?
- Can we combine both heteroskedastic parent and sampling index? In such a case, can we just use “sampling index” approach? (or impossible to combine them?) 
- In estimating weights, no clear justification is given for sorting residuals with respect to the values of H. I understand that being closer in H values implies having similar variances. But I would like to see more formal statements on this. 
- I am not sure whether a similar idea is employed in a similar or different setting. Like, transforming data in a way to be more homoskedastic, and then applying ParCorr-OLS.

limitations: 
- Requires prior knowledge on the reasons for heteroskedasticity.
review_title: null

final_score: 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.
review_content: summary: A conditional independence test is proposed based on partial correlation, but adapted to the case of heteroskedasticity. It is also studied how this test can be used in the PC algorithm. All results a rigorously proved, as well as illustrated using experiments.
strengths_and_weaknesses: This contribution is of high theoretical quality. It is also of great practical relevance, as homoskedasticity assumptions are often violated in real datasets. There are currently some major limitations (which are clearly mentioned in the paper), mainly that the proposed partial correlation test only works if for each variable, there is at most one source of heteroskedasticity, and for theoretical consistency of the PC algorithm, that this source is not another variable. Improvement in these areas is listed as future work.

The paper is clearly written; I especially appreciate the illustrations of the problems in Figure 1. The application to causal discovery is original, though if I understand correctly, the test itself is quite similar to existing work on heteroskedasticity.
questions: * On line 102, I was confused by the $[0, \infty)$. This seems to be the domain of $t$, though as far as I can tell, this is always a discrete sampling index, not a continuous value.

* On line 270-271, it is described that the case of "parent and child being affected by the same kind of heteroskedasticity" is being avoided.  I suppose this is simply because that could lead to much larger heteroskedasticity strengths than what is supposed to happen for a given value of the parameter $s$. Or is there a  more fundamental problem with this case?

Minor:

* Line 122-123: "the" missing before "hat operator"
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this work, authors consider heteroskedasticity in a structural causal model (SCM) and develop an adapted weighted least-squares (WLS) partial correlation variant as a conditional independence (CI) test which is able to deal with heteroskedastic noise with expert knowledge about the heteroskedastic relationships are given. Combined with the PC algorithm, the proposed CI test can also identify the causal relationships between variables under some assumptions regarding the heteroskedastic relationships. Both theoretical consistency analysis and simulation experiments demonstrate that the proposed CI test achieves better false positive rates and also improves upon the detection power as compared to the standard partial correlation CI test. 
strengths_and_weaknesses: Strengths:

1. The authors propose an adapted WLS partial correlation test for conditional independence testing in the presence of heteroskedastic noise.

2. The authors provide a detailed analysis of the WLS method's consistency with the proposed weight approximation method, and further inject the proposed CI test into the PC algorithm to learn the causal structure.

3. Experiments on simulated datasets demonstrate that the proposed WLS partial correlation CI test achieves better performance than the OLS partial correlation CI test in the presence of heteroskedastic noise. Combined with the PC algorithm, the proposed WLS partial correlation CI test has a smaller false positive rate in identifying causal relationships.

Weaknesses:

1. The idea of using the inverse of error's variance is intuitive, however, it would be great if the authors could further discuss why WLS can deal with heteroskedastic noise and some possible better re-weighting strategies in detail.

2. The authors formulate several assumptions in the paper, however, the heteroskedastic relationships require expert knowledge. The reviewer wonders if the authors could discuss further how to relax the heteroskedastic relationships assumption.
questions: 1. The authors did not mention the computational complexity of the proposed causal discovery algorithm (i.e., inject the proposed CI test into the PC algorithm), and it would be great if the authors could discuss the computational complexity of the proposed algorithm.

2. Since only simulated experiments are conducted in the paper, the reviewer wonders whether the proposed algorithm works well on real-world datasets?
limitations: Authors have discussed the Limitations and societal impacts in the Conclusion Section.
review_title: null

Meta-review: metareview: In real problems, data often exhibit the heterogeneity property. As a consequence, conditional independence tests that rely on the data homoskedasticity assumption may perform suboptimally, leading to inaccurate causal discovery results. This paper adapts the partial correlation tests to account for heteroskedastic noise and provides some necessary theoretical guarantees and empirical results. Reviewers agree that the studied problem is well motivated and that the solution is sensible.
confidence: Less certain
Decision: Accept