Organizations: Graduate University of Advanced Studies / The Institute of Statistical Mathematics, Tokyo, Japan · East China Normal University, Shanghai, China · The Institute of Statistical Mathematics, Tokyo, Japan
Constraint-based causal discovery requires many conditional independence (CI) tests. Generative CI tests are attractive in nonlinear and high-dimensional settings because they can model complex conditional distributions, but often suffer from high per-test costs and limited reusability across query-dependent conditional resampling tasks in graph search. We propose a generative nonlinear CI testing and graph search framework for PC-style causal discovery. We introduce Langevin-RePaint for conditional imputation. Building on Langevin-RePaint and joint flow matching modeling, we propose the Flow Matching based Conditional Independence Test (FMCIT), which reformulates generative CI testing from query-specific conditional modeling into a reusable conditional resampling framework. We establish theoretical guarantees for FMCIT's type-I error control. FMCIT reuses a single trained generative model to generate randomized copies throughout graph search. We then introduce GPC-FMCIT, which embeds FMCIT into a guided PC pipeline with screening, guidance, refinement, and orientation. By using low-cost screening to shrink the search space, constructing edge-specific candidate conditioning sets from local graph structure, and invoking FMCIT only in a budget-controlled refinement stage, GPC-FMCIT reduces both the deployment cost of individual nonlinear CI queries and the overall query complexity. On synthetic nonlinear structural equation models, GPC-FMCIT improves CPDAG recovery over PC-stable baselines and requires far fewer FMCIT queries than direct FMCIT-based PC search, and on hESC gene-expression data it yields smaller graphs than PC/FisherZ in a descriptive comparison. Overall, our results suggest that, through the joint design of reusable conditional resampling and controlled graph search, generative nonlinear CI testing can become a practical component of PC-style causal discovery.
Figures & tables
Figure 1: An illustration of Langevin-RePaint.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Method
Time (s)
FisherZ
0.01
KCIT
0.38
GCIT
2.36
CDCIT
14.36
Appendix
Table 6: Average computational time for a single CIT test over 100 repetitions with dz=50 and n=500 .
Experiment
Group
Changed / total
Table 2
GPC-FMCIT, FisherZ screen, α=0.05
10/10
GPC-FMCIT, KCI screen, α=0.05
10/10
GPC-FMCIT, FisherZ screen, α=0.10
9/10
GPC-FMCIT, KCI screen, α=0.10
10/10
PC-stable (FisherZ and KCI), both levels
12/40
Table 9
n=200 / 500 / 1000
2/3, 3/3, 3/3
Appendix
Table 7: Number of final graphs changed by CPDAG completion (changed / total runs). GPC-FMCIT rows use the completed-PDAG projection; PC-stable rows use the separate baseline repair.
Figure 2: Directed edges of the hESC CPDAG learned by triangle-guided GPC-FMCIT (full-joint B39, mcs=−1 , αscr=0.10 , αfm=0.05 ). Of the 124 directed edges, the 30 that involve ERCC spike-in controls are omitted, as are the six undirected edges.
Method
LPIPS ( ×10−2 ) ↓
PSNR ↑
SSIM ( ×10−1 ) ↑
RePaint
3.073±2.377
27.118±5.213
9.226±0.547
Langevin-RePaint (Ours)
2.621±2.040
27.550±4.980
9.211±0.536
Paired win rate (Ours)
90.892%
81.282%
34.008%
Appendix
Table 14: ImageNet-256 imputation results (mean ± std). The paired win rate indicates the percentage of images where Langevin-RePaint outperforms RePaint.
Figure 3: Comparison of Langevin-RePaint and RePaint on ImageNet-256 imputation with 40% random masking.
Conditional Independence (CI) tests are the statistical engine of constraint-based causal discovery: in algorithms such as PC (Peter-Clark) and FCI (Fast Causal Inference), skeleton pruning and key orientations follow directly from CI decisions. This survey reviews CI testing with emphasis on assumptions, robustness, and scalability in high-dimensional and mixed-type settings common in biomedical domains. The survey organizes widely used CI methods into six families: partial-correlation, contingency-table, regression, nearest-neighbor, kernel, and machine-learning-based. Special emphasis is provided on the robustness layers that address the limitations of these families. For each family, the survey examines when CI decisions reflect the data-generating distribution and when they fail. By this, we link test-level properties, including power decay with conditioning set size and asymmetric type I/II error consequences, to graph-level errors in skeleton recovery and v-structure orientation. The survey also compares adoption across major R and Python libraries and summarizes open challenges, including mixed-type CI testing without discretization, small-sample error control, and strategies for improving scalability of CI-testing.
Pavel Averin, Theodoros Moysiadis, Ioannis Katakis
Department of Computer Science School of Sciences and Engineering University of Nicosia 2417, Nicosia, Cyprus
Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph. Despite extensive research, it remains unclear if there exist algorithms with better complexity without additional assumptions. Here, we establish an algorithm that achieves a better complexity of pO(s) tests, where p is the number of nodes in the graph and s denotes the maximum undirected clique size of the underlying essential graph. Complementing this result, we prove that any constraint-based algorithm must perform at least 2Ω(s) conditional independence tests, establishing that our proposed algorithm achieves exponent-optimality up to a logarithmic factor in terms of the number of conditional independence tests needed. Finally, we validate our theoretical findings through simulations, on semi-synthetic gene-expression data, and real-world data, demonstrating the efficiency of our algorithm compared to existing methods in terms of number of conditional independence tests needed.
Marc Franquesa Monés, Jiaqi Zhang, Caroline Uhler
Eric and Wendy Schmidt Center, Broad Institute of MIT and Harvard · Centre de Formació Interdisciplinària Superior, Universitat Politècnica de Catalunya · Laboratory for Information and Decision Systems, Massachusetts Institute of Technology
Constraint-based causal discovery relies on repeated conditional independence tests, but fast nonparametric tests often sacrifice calibration, especially when variables depend on the conditioning set through nonlinear relationships. We introduce BLITZ (Broad-to-Local Independence Testing via residualiZation), a nonparametric conditional independence test designed to run well under a second while maintaining the accuracy needed for the thousands of queries performed by constraint-based causal discovery algorithms. BLITZ first removes broad smooth dependence on the conditioning set using low-order polynomial regression, then applies a small nonlinear feature map and residualizes those features with shallow tree regressions. The resulting statistic tests residual cross-covariance, with a moment-matched chi-square approximation to the null distribution. We show theoretically that the two-stage design reduces the effective complexity faced by the tree residualizers, allowing shallow trees to control residual conditional-mean bias while avoiding excessive overfitting. In simulations, BLITZ provides better null calibration than fast kernel, random-feature, and regression-based competitors while remaining among the fastest methods tested. In causal discovery experiments on synthetic graphs and flow-cytometry data, BLITZ yields more reliable endpoint orientations among retained adjacencies and competitive structural recovery. These results suggest that broad-to-local residualization is a practical route to calibrated, scalable nonparametric conditional independence testing for causal discovery.
Eric V. Strobl
Department of Biomedical Informatics, University of Pittsburgh, Pittsburgh, PA 15213, USA