acceptodds
Under review as a conference paper at ICLR 2027

Conditional Independence Testing from Dependent Samples with Applications in Causal Discovery from Time-series Data

Abstract

Causal discovery from time-series data is a fundamental problem with many applications in several industries. Most causal discovery algorithms use conditional independences, explicitly or implicitly, between observed variables to learn the causal graph. Directly applying these algorithms to time-series data is challenging due to the dependence across samples created through the causal effects over time. The landmark PCMCI algorithm addresses this issue by a two-stage approach: While the first stage is a conservative edge pruning stage, the critical second stage tests independence between two variables by conditioning on the union of parents of both variables. This removes the dependence between samples through time, allowing us to plug in conditional independence tests designed for IID data. However, large conditioning sets in the second stage often have low statistical power with finite data since few samples are left per stratum. To address this issue, we first analyze the chi-square independence test from dependent samples. For stationary, rapidly mixing processes, we show that the test statistic still converges to a chi-square distribution when conditioning on the parents of one variable, allowing the other variable to be dependent through time. Our work, to the best of our knowledge, provides the first explicit dependence of the chi-square test on the mixing time of the underlying time series. Based on this, we develop a causal discovery algorithm, which, in its second stage, conditions on the parents of only one of the variables. The smaller conditioning set significantly improves statistical power and causal discovery performance. We show through synthetic experiments that our algorithm outperforms PCMCI and other baselines.

Primary area:
causal reasoning
Keywords:
independence testing, causal discovery, time-series

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_5bZCOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigate and contribute to conditional independence testing with dependent time-series observations, with applications to causal discovery. The authors propose PC-OP, a modification of PCMCI algorithm that conditions on the parents of the candidate effect rather than both variables. They establish asymptotic validity of the chi-square test under specific assumptions and evaluate the resulting algorithm on synthetic and real-world data.

Critical strengths

The paper targets a relevant statistical problem by proposing a simple modification to an established algorithm. The theoretical analysis is extensive, and the synthetic experiments report substantial improvements over PCMCI. The oracle-parent ablation is useful for isolating the effect of the conditioning strategy.

Critical weaknesses

W1: empirical results do not sufficiently support the proposed motivation. The method is motivated by improved statistical power through smaller conditioning sets, yet Tables 2–3 show nearly identical power for the two strategies. In contrast, the downstream synthetic experiments show large improvements, without sufficiently explaining when or why these arise. The improvements on CausalRivers are relatively modest, making it difficult to assess the practical significance of the method.

W2: scope and applicability of the theoretical results. The analysis focuses on a specific class of stationary, rapidly mixing processes with independent innovations, rather than general dependent observations. Furthermore, the main theorem assumes a fixed parental conditioning set, whereas the proposed algorithm estimates this set from the same data. The authors acknowledge that calibration after selection is not established. It remains unclear how much of the theoretical analysis carries over to the implemented procedure.

W3: problem formulation and presentation could be clearer. The assumptions underlying the causal model are introduced across different sections, without clearly distinguishing those required for the statistical test from those needed for causal discovery. The extensive theoretical development also makes it difficult to identify the central new insights and their relationship to the empirical findings.

Questions for authors

Q1: What explains the substantial downstream improvements when the isolated CI tests show nearly identical power? Can the authors better characterize the settings in which PC-OP is expected to outperform PCMCI?

Q2: How sensitive is the method to violations of the structural assumptions and errors in the estimated parent sets? To what extent do the theoretical guarantees support the practical algorithm?

Q3: Can the authors clarify the novelty of the theoretical results relative to existing martingale-based inference, and distinguish the main new arguments from standard tools?

Q4: In Section 4, why does PC-OP+ use a threshold of 1/M, rather than \alpha/M, for its Bonferroni-style correction?

2 comments

We would like to thank the reviewer 5bZC for their time and detailed, constructive feedback. Please find our replies to your questions below. We also updated the manuscript to address comments from all reviewers.

Q1. Power of the test.

Tables 2 and 3 focus on a single pairwise test conditioned on one variable, generally demonstrating equal or superior performance for our methods when the sample size is n<1000n < 1000 or the effect size is small (β≤0.1\beta \le 0.1). When applied to synthetic graph discovery problems, however, both the number of variables and the size of the conditioning sets can be substantially larger. The table below evaluates the performance of PC-OP variants (PC-OP, PC-OP+, PC-OP-M) against PCMCI across different graph dimensions (dd) and maximum in-degrees, reporting the F1 score, mean conditioning set size (mean ∣Z∣|Z|), d-separation accuracy, and final test power.

For this evaluation, we use primary datasets (5 seeds each) executed with our updated implementation (incorporating lag fixes and a Step 2 threshold of α=0.05\alpha = 0.05). To establish ground truth, we generate an independent reference dataset of 10710^7 samples simulated directly from the true conditional probability tables (CPTs) and compute conditional mutual information (CMI) and chi-square tests as our reference benchmark. Verification on a d=5d=5, L=1L=1 system confirms that this reference dataset matches the exact stationary Markov chain to within 0.0002 on the marginals and 0.0001 on the mutual information of a true edge. A test is counted as correct if a "dependent" decision aligns with CMI >ϵ> \epsilon, and test power/accuracy is measured by whether decisions match the most likely outcome of a chi-square test at particular sample and alpha values, derived from the true distribution.

As shown in the table below, PC-OP and its variants consistently achieve high performance—maintaining roughly 94% to 96% power across settings and superior F1 scores—while PCMCI's power drops significantly in denser graphs (ranging from 36.9% to 81.1% depending on the setting) and tends to select much larger conditioning sets (mean ∣Z∣|Z|). This showcases the effectiveness and power gain of the methods over PCMCI.

SettingMethodF1mean |Z|d-sepCMI>1e-4CMI>1e-3CMI>1e-2power
d=10, in-deg 2PC-OP0.8794.186.7%94.5%95.0%94.6%95.0%
PC-OP+0.8994.495.5%95.5%95.5%95.5%95.5%
PCMCI0.6838.179.0%80.8%81.1%80.9%81.1%
d=10, in-deg 3PC-OP0.9225.468.5%92.1%95.5%94.1%95.8%
PC-OP+0.9386.395.0%95.8%96.0%96.0%96.0%
PC-OP-M0.8575.250.1%87.1%93.0%86.1%93.8%
PCMCI0.48810.750.5%43.2%39.0%36.1%36.9%
d=20, in-deg 2PC-OP0.7654.784.1%94.2%94.3%93.8%94.6%
PC-OP+0.7925.194.7%94.7%94.7%94.7%94.7%
PC-OP-M0.7184.378.8%93.5%93.1%91.1%94.2%
PCMCI0.3949.468.2%68.5%68.7%68.2%68.6%

Q2. Wrong parent set.

We don't have any formal guarantees when even the parents of the target variable is false. Note that a conservative estimate, a superset of parents of YY, does not affect soundness, and the PC stage is purposefully using a loose alpha value precisely to deal with this in practice.

Q3. Novelty.

As far as we know, this is the first rigorous result for independence testing under a causal time series assumption. While what translates to practice is not settled, we feel theory is important here. In regard to technical novelty: Our proof combines several insights we came up with for the first time: The shortfall concept, viewing the data generative process as sampling rows first, then columns randomly, carefully positioning and handling the conditional sampling process as a martingale, and so on. The existing martingale-based inference results cannot be directly applied in this setting.

Q4. PC-OP+ Threshold

1/M1/M was a typo and has now been corrected. Algorithm 1 showed the correct computation.

We hope that our rebuttal addressed the reviewer's concerns. Thank you again for your time.

The additional experiments and analysis substantially address W1, clarifying when and why the proposed approach improves over PCMCI. I also appreciate the improved exposition and clarification of the contributions (W3).

My main remaining concern is W2: the theoretical guarantees still do not cover the data-dependent parent selection used by the practical algorithm. Together with the relatively modest real-world improvements, this leaves me inclined to maintain my original assessment.

Reviewer_d23eOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes PC-PO, a causal discovery algorithm for discrete time-series data. The key theoretical contribution is establishing the asymptotic validity of chi-square conditional independence tests under temporal dependence. Based on this result, the proposed algorithm condtions only on the parents of the response variable, thereby improving statistical power. Experiments on synthetic and real-world datasets demonstrate improved causal discovery performance compared with existing methods.

Critical strengths

This paper provides a theoretically motivated improvement to PCMCI by reducing the conditioning set, potentially improving the statistical power of causal discovery for discrete time-series data.

Critical weaknesses

The theoretical novelty appears limited, as the main result largely relies on standard maritingale asymptotic theory.

Questions for authors
  1. Could the authors clarify the main theoretical advances of Theorem 3.1 beyond existing results, particularly given that its proof relies on standard martingale CLT arguments?
  2. Theorem 3.1 assumes a fixed parental conditioning set. Do the theoretical guarantees remain valid when the parent sets are estimated from the same data?
  3. Since the theoretical results focus on categorical time series, can the proposed approach be extended to continuous variables or more general conditonal independence tests?
2 comments

We thank reviewer d23e for their comments. Please find our replies to your questions below.

On Novelty Assessment

We strongly disagree with the assessment reviewer posted about novelty. Calling novelty limited because it uses existing techniques sets up a harmful, unrealistic standard from human research output. We will explain in simple terms why this result does not trivially follow from standard martingale asymptotic theory.

Q1. Technical Novelty

To our knowledge, this is the first rigorous result for independence testing under a causal time-series assumption. The key idea and proof outline we formalized in this paper was not known before: This is that filling one of the two dimensions of a contingency table randomly while the other is sampled in an autocorrelated manner does not automatically yield the computed chi square statistic to be chi square distributed. Our proof combines several insights we came up with for the first time: The shortfall concept, viewing the data generative process as sampling rows first, then columns randomly, carefully positioning and handling the conditional sampling process as a martingale, and so on. The existing martingale-based inference results cannot be directly applied in this setting. Therefore, we believe calling the whole result and the proof not novel because it uses standard martingale arguments smooths out key intellectual contributions which made this result possible.

Q2. On end-to-end guarantees

Our work proves soundness of a modified MCI stage, which constitutes the first concrete step towards an end-to-end sound discovery algorithm. Our result does not yet guarantee end-to-end soundness or PCMCI variants including ours. The PC stage does not condition on the correct parents of either variable, and no known guarantee exists about this stage. The first stage’s soundness is still an open problem when we don’t assume “a consistent CI test from dependent samples,” which, to the best of our knowledge, does not exist.

Q3. Extension to other test statistics

Yes, we strongly believe the theoretical results can be extended to any ff-divergence instead of just the chi-square statistic. This extension is left for future work.

Thank you for your time.

Authors‘ responses do not address my main concerns. Therefore, I will maintain my original rating.

Reviewer_6v5LOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

When testing if candidate cause have a causal arrow to response variable (also called target variable), traditional PCMCI need to use a big conditional set in the stage 2 (MCI stage). This big conditional set consist of all the parents of the response variable and all the parents of the candidate cause. This paper proposed PC with One-parent-set (PC-OP) to only include all the parents of the response variable. They prove some theoretical properties of this new approach. They also show the experiments that PC-OP perform better than PCMCI in the finite sample size cases. The intuition is that PC-OP can use more data due to smaller conditional set.

Critical strengths

This paper proposed a more effective PCMCI variant. And they prove some useful theoretical results for this new approach. The theoretical analysis is solid and makes the reader more confident when using their new method. The experiments are comprehensive, which include a synthetic dataset and a real dataset. In both scenarios, PC-OP performs better than PC.

Critical weaknesses

When I check the original PCMCI paper, I find that the PCMCI paper already observes that only controlling the parents of the target variable is sufficient to assess conditional independence (in the section "choice of p_x" in the main text of the PCMCI paper). And they proposed the PCMCI variant that does not control the parents of the candidate cause, and named this variant as "PCMCI_0", and discussed this variant in the supplement section S3.1. In this supplement section, PCMCI's authors define MCI_0 in equation S5. And this equation is the same as Equation (3) of the present submission.

However, the current submission omits discussion of PCMCI_0. If PCMCI_0 is taken into account, when evaluating the 3 contributions claimed in the introduction of the current submission, I think the first and second contributions still hold, but the third contribution, which is in the method part, does not seem to hold. This paper can be regarded as an article that discusses the theoretical properties of PCMCI_0 and conducts comprehensive evaluation experiments on PCMCI_0, and also involves small modifications to the implementation of PCMCI_0, but the basic idea and approach are the same as those of PCMCI_0.

Questions for authors

Can you discuss the possible reason that the PCMCI authors notice PCMCI_0 but finally they don't use it for the standard method in the main text? If this is due to some issues of PCMCI_0, have these issues been resolved or clarified through your theoretical analysis?

2 comments

We thank reviewer 6v5L for their time in reviewing our paper and for the detailed feedback. All the changes have been implemented in the updated PDF we uploaded. We would like to make two important points:

1. The observation of the PCMCI author in the main paper that the parents of the target are sufficient: This is orthogonal to the problem we are solving here. His remark is simply that this gives a valid separating set. But the author acknowledges that the parents of the cause are needed to account for autocorrelation, and that the variant without them likely has inflated false positives. Our Theorem 3.1 shows that, for the chi-square test on discrete data, the test is calibrated without them, even though the samples of the cause variable remain dependent.

2. We checked, and the reviewer is right that PCMCI’s appendix does contain several variants, and one of them is the one that only conditions on parents of the target. We were not aware that the appendix contained a named algorithm, which he called PCMCI$_0$. We verified and indeed this is identical to our basic algorithm we named PC-OP. We made this clear in our updated revision.

Our + version PC-OP+ proposed an additional step that is not anywhere in the PCMCI paper, so this would be the extent of our algorithmic novelty. Thus, we agree with the reviewer that our main contribution is to provide the first proof that chi-square CI testing is consistent in the time-series causal discovery context without having to condition on parents of the cause variable, proving soundness of the MCI stage of PCMCI$_0$; this is correct. We have revised the claims in the paper accordingly, and we now avoid claiming that PC-OP is the first algorithm that does this.

Finally, on your question of why PCMCI authors did not use PCMCI$_0$/PC-OP:

The authors expected the test to be poorly calibrated under autocorrelation without the parents of the cause, and they report inflated false positives for this variant with partial correlation. The PCMCI paper’s simulations mostly focus on continuous/Gaussian data. Stratification really hurts for discrete variables since data is sliced exponentially in size of the conditioning set. For Gaussian/parametric models, partial correlation computation might be easier. We now explain this distinction in the updated PDF to highlight the regimes where PC-OP/PCMCI$_0$ would be most advantageous.

Thank you again for your time.

Thanks for addressing my noverlty concern and clarifying the contribution in the revised version. I raise my score from 2 to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.