acceptodds
Under review as a conference paper at ICLR 2027

Scalable Causal Discovery via Vertical Partitioning of Data Features

Abstract

Causal discovery (CD) methods often incur exponential time complexity in the number of variables which is not scalable. To cope with this problem, recent research has proposed to leverage divide-and-conquer strategies to boost the scalability of a wide variety of existing CD algorithms. However, these strategies require significant overhead to either divide the original problem into sub-problems or aggregate the conquered local solutions into a global solution. Furthermore, failing to assert locally statistical properties such as correctness-and-completeness often impairs the performance of many algorithms. In this paper, we present a novel divide-and-conquer framework that provably performs both problem decomposition and solution aggregation in quadratic time complexity. Furthermore, our framework theoretically guarantees that the local solutions are consistent with the global solution. Finally, extensive evaluation on a wide variety of benchmark datasets show that our framework consistently and significantly and consistently improves the scalability and performance of various CD algorithms.

Primary area:
causal reasoning
Keywords:
scalable causal discovery, divide-and-conquer

Reviews

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

This paper discusses causal discovery in settings with a large number of variables. A common approach to improving scalability is to use divide-and-conquer methods, which partition the variables into smaller subsets, perform causal discovery on each subset, and then aggregate the resulting causal graphs. However, major existing divide-and-conquer approaches rely on finding partitions under which subsets of variables become conditionally independent, making the search and optimization over candidate cut sets itself computationally expensive.

This paper proposes a more direct divide-and-conquer strategy that groups variables with identical dependency patterns and orders the resulting groups using their characteristic numbers, while still providing identifiability guarantees. The key theoretical results show that the characteristic numbers of the groups can be used to determine a topological order among them, and that conditional independencies present in the global graph can also be identified within the corresponding local subproblems, thereby guaranteeing the correctness-and-completeness property. As a result, the number of conditional independence tests required for decomposition and aggregation can be reduced to quadratic order, substantially improving the computational scalability of divide-and-conquer causal discovery.

In the experiments, under a setting where the ground-truth causal graph is known and oracle conditional independence tests are used for decomposition and aggregation, the proposed framework substantially outperforms both standalone causal discovery methods and existing divide-and-conquer approaches on datasets with large numbers of variables. The experiments further suggest that this performance improvement is enabled by the framework's ability to decompose the original problem into very small subproblems.

Critical strengths

A major strength of this paper is that it introduces a simple divide-and-conquer strategy that is fundamentally different from major existing approaches, while reducing the number of conditional independence tests to quadratic order and thereby enabling substantial computational speedups. Importantly, the core of the proposed algorithm is supported by simple and intuitive theoretical guarantees rather than relying only on heuristic design. I view this combination of conceptual simplicity, theoretical grounding, and scalability as highly novel. It suggests a new direction for the causal discovery community and has the potential to provide a new design principle for future large-scale causal discovery methods.

Critical weaknesses

The main weakness of this paper is that the primary experiments rely on oracle conditional independence tests, leaving the evaluation under realistic conditions relatively weak. In practical applications, the ground-truth causal structure is unknown, and oracle CI tests are therefore unavailable. I understand the motivation for using oracle CI tests to isolate the effect of the proposed framework from errors in CI estimation, but relying mainly on this idealized setting limits the practical evidence supporting the method. Although the appendix includes experiments with sample-based CI tests, these evaluations are fairly limited in scope. This weakness could be substantially mitigated by conducting sample-based CI experiments at a scale comparable to the main SOTA comparisons and promoting those results to the main paper.

A second weakness is that the scalability benefit of the proposed framework depends strongly on its ability to decompose the original problem into sufficiently small subproblems. While Figure 4 and related experiments provide encouraging empirical evidence, it remains unclear how general this behavior is across different graph structures. Even a small number of very large groups could become major computational bottlenecks. A more systematic evaluation of how the maximum subproblem size affects scalability, together with a discussion of how oversized subproblems could be handled, would significantly strengthen the practical applicability of the proposed method.

Questions for authors

Can the authors provide some theoretical characterization showing that the subproblems generated by the proposed method are expected to remain small? If small subproblems are not guaranteed, can the authors discuss under what graph structures large subproblems may arise, whether such cases can be identified in advance, and what strategies could be used to handle them?

3 comments
AuthorsOpenReview ↗

Response to Reviewer rPjT (1/2)

We thank the reviewer for the positive rating and constructive feedback. We address the reviewer's questions as follows:

The main weakness of this paper is that the primary experiments rely on oracle conditional independence tests, leaving the evaluation under realistic conditions relatively weak. In practical applications, the ground-truth causal structure is unknown, and oracle CI tests are therefore unavailable. I understand the motivation for using oracle CI tests to isolate the effect of the proposed framework from errors in CI estimation, but relying mainly on this idealized setting limits the practical evidence supporting the method. Although the appendix includes experiments with sample-based CI tests, these evaluations are fairly limited in scope. This weakness could be substantially mitigated by conducting sample-based CI experiments at a scale comparable to the main SOTA comparisons and promoting those results to the main paper.

To address the reviewer's concern, we conducted additional experiments using sample-based CI tests throughout the decomposition and aggregation stages.

Due to limited time, we conducted additional experiments comparing DEFT, HCD, and CPA on the Win95pts (7676 nodes), Andes (223223), and Diabetes (413413). Each dataset is limited to 10001000 observations and the results are reported from 1010 independent seeds. We use PC as the subroutine. The results are summarized below.

DatasetFrameworkPrecision ↑\uparrowRecall ↑\uparrowF1-score ↑\uparrowSpurious ↓\downarrowSHD ↓\downarrow
Win95ptsCPA0.37 ±\pm 0.050.55 ±\pm 0.050.44 ±\pm 0.050.47 ±\pm 0.04132.4 ±\pm 13.0
Win95ptsHCD0.25 ±\pm 0.050.22 ±\pm 0.040.23 ±\pm 0.040.33 ±\pm 0.05136.6 ±\pm 6.5
Win95ptsDEFT0.51 ±\pm 0.040.75 ±\pm 0.040.61 ±\pm 0.040.38 ±\pm 0.0494.4 ±\pm 10.4
AndesCPA0.16 ±\pm 0.010.33 ±\pm 0.020.21 ±\pm 0.010.75 ±\pm 0.01785.8 ±\pm 25.7
AndesHCD0.26 ±\pm 0.020.23 ±\pm 0.020.24 ±\pm 0.020.51 ±\pm 0.03427.7 ±\pm 12.0
AndesDEFT0.47 ±\pm 0.020.37 ±\pm 0.030.42 ±\pm 0.020.33 ±\pm 0.04315.9 ±\pm 13.3
DiabetesHCD0.21 ±\pm 0.050.27 ±\pm 0.030.24 ±\pm 0.040.61 ±\pm 0.08971.5 ±\pm 124.9
DiabetesDEFT0.30 ±\pm 0.050.34 ±\pm 0.060.32 ±\pm 0.050.48 ±\pm 0.05771.0 ±\pm 56.2

Results. Under finite-sample CI testing, DEFT consistently achieves higher F1-scores and lower SHD than both HCD and CPA on the evaluated networks. On Win95pts, DEFT achieves an F1-score of 0.61, compared with 0.23 for HCD and 0.44 for CPA, while reducing SHD to 94.4. Similarly, on Andes, DEFT achieves an F1-score of 0.42, compared with 0.24 and 0.21 for HCD and CPA, respectively, with the lowest SHD of 315.9. In Diabetes, DEFT outperforms HCD almost 50%50\% in F1-score.

Manuscript revision. We thank the reviewer for this valuable suggestion. We will incorporate these additional finite-sample experiments into Appendix B.2 and highlight the findings in the main text. We believe these additions will strengthen the practical evaluation of DEFT.

AuthorsOpenReview ↗

Response to Reviewer rPjT (2/2)

Can the authors provide some theoretical characterization showing that the subproblems generated by the proposed method are expected to remain small? If small subproblems are not guaranteed, can the authors discuss under what graph structures large subproblems may arise, whether such cases can be identified in advance, and what strategies could be used to handle them?

At the moment, we do not have a clear characterization of the size of the subproblems generated by DEFT. This is because DEFT does not decide the size of subproblems, but the data itself.

As we have investigated in Section 4.3, in the common setting with Erdos Reyni graphs, the size of subproblems forms a long tail distribution (Figure 4.b). Nontheless, we observe that the maximum size is relatively small compared to the number of nodes. Beyond synthetic Erdos-Reyni graphs, we observe the same on real-world graphs (Figure 6, Appendix B.7). This is an observation, not a definitive proof.

There is a sign for a graph with large subproblems: too few sources. Indeed, a graph of only one source node has all nodes dependent on each other, thus creating one group. Such a case reduced DEFT to the standalone subroutine. This worst case scenario is already discussed in Remark 5, Appendix B.6. In the remark we also note that theoretically, using DEFT+AA is always better or equal to subroutine AA in term of scalability.

Regarding a remedy for the size-anomaly phenomenon, it is possible that a reodering of the sequence which we solve subproblems can be a potential approach. DEFT uses subroutine AA to solve Rk∪Pa[Rk]R_k\cup Pa[R_k] then discards edges within and between Pa[Rk]Pa[R_k]. By solving smaller subproblems first, edges within and between Pa[Rk]Pa[R_k] are already known, which gives amber evidences for AA to quickly solves Rk∪Pa[Rk]R_k\cup Pa[R_k]. However, this would also mean that AA needs to be able to handle prior knowledge. None of the subroutines we studied in this research has this capacity.

Thank you for the careful and detailed response. The additional experiments address my concern to a reasonable extent, and I also find the discussion regarding the size of the subproblems reasonably convincing. With these additions incorporated into the paper, my concerns are largely resolved. Since my original assessment was already in favor of acceptance, I will keep my rating unchanged.

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

DEFT is a divide-and-conquer framework for scaling Causal Discovery (CD) to larger datasets with more variables. It uses unconditional independence tests for grouping variables and yields the corresponding topological order. The dataset is then split into per-group subproblems that can be solved using existing CD algorithms to recover the underlying causal subgraphs and merge the results. In Theorems 2, 3, and 4, the authors prove that the decomposition loses no information, that the causal graph merge is acyclic without additional conflict, and that the framework's computational complexity is O(d^2) regardless of the CD algorithm. Across synthetic and real-world benchmarks, DEFT consistently outperforms the tested CD algorithms and existing divide-and-conquer baselines while using fewer independent tests.

Critical strengths

1- The authors present an interesting, well-motivated framework to enable the scalability of CD methods to larger datasets with better runtime and accuracy. 2- The paper is well written and presented with good illustrations that make it easy for the reader to follow and read end to end. 3- Theoretical proofs are used to prove the findings, not only empirical results: decomposition is lossless (Theorem 2), the global merged causal graph is acyclic (Theorem 3), without a high computational complexity (Theorem 4).
4- DEFT is evaluated comprehensively under different CD algorithms across synthetic and real-world benchmarks with non-Gaussian/nonlinear noise and multiple graph topologies.

Critical weaknesses

1- Certain subroutines have limitations under the DEFT framework, limiting its benefits: GraNDAG’s runtime increases under DEFT due to repeated neural network re-initialization (Table 2), and GOLEM’s spurious relations rate rises under non-Gaussian noise (Table 7, Appendix). This shows the framework gains are not universal across all CD methods. 2- The step that determines the causal relations between groups (Algorithm 1) depends on conditional independence tests (CITs), so DEFT reliability and computational cost at this stage are tied to the CIT quality. As the authors note, DEFT may require larger conditioning sets, which will, in turn, increase complexity. 3- The actual gain of DEFT depends on how much real group structure exists in the data; the authors prove that there is no worst-case penalty (Remark 5), but the actual runtime speed and performance accuracy improvements are dataset-dependent. 4- Minor Issues: larger figures would improve the readability to the reader.

Questions for authors

1- Could the authors clarify more about how DEFT determines which specific variables are connected between two groups/sub-graphs and the direction of their edges when aggregating the results and assembling the global graph? 2- Could DEFT be adapted differently for neural-network subroutines like GraNDAG such that the network re-initialization cost is reduced, hence reducing the framework runtime ? 3- Does the framework performance under the different evaluation metrics actually degrade relative to the baseline CD method at very low or very high K? Could the authors report empirical results on such extreme cases and report the K value for the different experiments performed in their analysis?

3 comments
AuthorsOpenReview ↗

Response to Reviewer YEFZ (1/2)

We thank the reviewer for the positive rating.

We address the reviewer's questions as follows:


Certain subroutines have limitations under the DEFT framework, limiting its benefits: GraNDAG’s runtime increases under DEFT due to repeated neural network re-initialization (Table 2), and GOLEM’s spurious relations rate rises under non-Gaussian noise (Table 7, Appendix B.2). This shows the framework gains are not universal across all CD methods. 

In our current experiments, repeated network initialization and optimization across subproblems can increase GraNDAG’s runtime [1], as discussed in Section 4.1. Remark 4 explains that DEFT is most beneficial when the solver’s cost is primarily driven by graph size.

[1] Lachapelle, Sébastien, Philippe Brouillard, Tristan Deleu, and Simon Lacoste-Julien. "Gradient-based neural dag learning." arXiv preprint arXiv:1906.02226 (2019).


Could DEFT be adapted differently for neural-network subroutines like GraNDAG such that the network re-initialization cost is reduced, hence reducing the framework runtime ? 

We thank the reviewer for this constructive suggestion. This can be an interesting future work.

One potential direction is to exploit the overlap between local subproblems by reusing pre-trained network parameters or shared neural representations, rather than initializing and training a separate network from scratch for each subproblem.

Importantly, we emphasize that DEFT is a model-agnostic framework, and such adaptations would not require modifications to its underlying decomposition strategy. We view these optimizations as promising directions for improving the integration of DEFT with neural-network-based causal discovery algorithms and will discuss them in the revised manuscript.


The step that determines the causal relations between groups (Algorithm 1) depends on conditional independence tests (CITs), so DEFT reliability and computational cost at this stage are tied to the CIT quality. As the authors note, DEFT may require larger conditioning sets, which will, in turn, increase complexity. 

The size of the conditioning set limits the application of all constraint-based methods and can be considered as an orthogonal challenge itself. Some methods sidestep this challenge, including CAPA and CPA, by adopting a limit on the size of the conditioning set. Some methods side-step this challenge, including CAPA and CPA, by adopting a limit on the size of the conditioning set. Rather than imposing such restrictions, DEFT can incorporate alternative CI testing procedures designed for high-dimensional conditioning, such as Categorical residualization [2] or Sparse Regression [3], in place of traditional CITs (for example, chi-squared test).

Manuscript revision. We thank the reviewer for raising this question. We have addressed it in Appendix C.1 of the revised manuscript.

[2] Ankan, Ankur, and Johannes Textor. "A simple unified approach to testing high-dimensional conditional independences for categorical and ordinal data." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 10. 2023.

[3] Ning, Yang, and Han Liu. "A general theory of hypothesis tests and confidence regions for sparse high dimensional models." (2017): 158-195.

AuthorsOpenReview ↗

Response to Reviewer YEFZ (2/2)

Does the framework performance under the different evaluation metrics actually degrade relative to the baseline CD method at very low or very high K? Could the authors report empirical results on such extreme cases and report the K value for the different experiments performed in their analysis?

First, we want to clarify that KK is not a controllable parameter. That is, we cannot fix a desired KK and generate a dataset with it. Instead, we generate the data and its inner structure determines KK via grouping using Def. 2. For your question, we investigated Erdős–Rényi graphs with different structures, each with d=100d=100 nodes and n=1000n=1000 samples (non-oracle setting). Given the time available, we evaluated two base solvers, PC and Varsort. For each solver, we used the same parameter settings in the standalone and DEFT runs.

SubroutineKFrameworkPrecision ↑Recall ↑F1 ↑SHD ↓Runtime (s) ↓
Varsort82Standalone0.59290.92500.72271293.46
Varsort82+DEFT0.90610.96500.9346222.39
Varsort19Standalone0.38070.91500.537612174.10
Varsort19+DEFT0.39810.92500.556611447.35
PC82Standalone0.42000.42000.420019784.95
PC82+DEFT0.82940.87500.8516555.89
PC19Standalone0.26920.04380.0753832259.56
PC19+DEFT0.37130.09380.1497819284.99

At K=82K=82, most variables formed singleton groups, and the largest subproblem contained 14 variables. DEFT improved all four graph recovery metrics and reduced runtime for both solvers. At K=19K=19, the largest subproblem contained all 100 variables. Both solvers took longer with DEFT, while all four graph recovery metrics still improved. DEFT took more time because there existed a subproblem being the original problem. Even then, solving other smaller subproblems proves to bring great accuracy boosts.

To avoid spending the extra time solving a subproblem that equals the original problem, it would require a subroutine that can leverage prior knowledge of solved smaller subproblems. There is no such a subroutine in our tested subroutines.

Manuscript revision. We thank the reviewer for raising this important question. We have incorporated these additional experiments into Appendix B.6 of the revised manuscript.


Minor Issues: larger figures would improve the readability to the reader.

We thank the Reviewer for the constructive comment. We have improve the figure quality in the revised manuscript.


Could the authors clarify more about how DEFT determines which specific variables are connected between two groups/sub-graphs and the direction of their edges when aggregating the results and assembling the global graph?

The following response has been added to our revised manuscript:

For each target group RkR_k, the local solver receives the variables in RkR_k together with those in its parent groups, denoted by Pa[Rk]Pa[R_k].

After applying the subroutine AA on the subproblem, we have a graph consisting of edges between all nodes in Rk∪Pa[Rk]R_k\cup Pa[R_k]. Existing edges within RkR_k are kept, existing edges within and between Pa[Rk]Pa[R_k] are discarded, existing edges between Pa[Rk]Pa[R_k] and RkR_k will be reoriented in the direction Pa[Rk]→RkPa[R_k]\to R_k regardless of the orientation made by AA.

Manuscript revision. We thank the reviewer for raising this question. We have added this explanation to Appendix C.3 of the revised manuscript.

Thank you for your rebuttal and for clarifying my questions. I appreciate the updated manuscript and I have no further questions

Reviewer_m2MQOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This article proposes DEFT, a constraint-based divide-and-conquer causal discovery framework. The author first computes the set of variables related to each variable's edges, groups variables with identical sets, and uses the set size to order groups topologically. Subsequently, the author constructs a "Causal Graph of Groups" using conditional independence testing in this order. Each subproblem consists of a group and its parent group and is solved using an existing causal discovery algorithm. Finally, the local results are merged by edges.

Critical strengths
  1. The idea of defining variable groups using edge-related sets and directly exporting the topological order between groups is concise and novel, avoiding the high cost of recursively searching for cut sets in previous methods.
  2. The framework is independent of specific solvers and can serve as a plugin to enhance various algorithms such as PC, LiNGAM, GOLEM, SCORE, etc. Its practical value is clear.
  3. The experimental coverage is wide, including various basic algorithms, multi-class diagram structures, non-Gaussian and nonlinear noise, as well as limited sample settings, and the advantages over existing divide-and-conquer frameworks are obvious on large-scale real networks.
Critical weaknesses
  1. The main experiment used pre-conditional independent testing in the decomposition and aggregation stages, and the grouping and graph construction were therefore completely error-free, which greatly overestimated the performance of the method on real data. In the limited sample experiment in the appendix, the SHD of DEFT in a larger dimension has been inferior to HCD, indicating that the robustness of the main conclusion is questionable.
  2. Grouping requires that the correlation sets of two variables are "the same", making them highly sensitive to single test errors in limited samples, and a single misjudgment may change the topological order and parent group relationship. The article lacks analysis on how this error propagates along the process.
  3. Algorithm 1 takes all variables of the parent group, child group, and spouse group as the condition set, which may be very large. The complexity analysis only counted the number of tests and did not take into account the cost and statistical power reduction of high-dimensional conditional tests themselves, so the term 'squared complexity' is not complete enough.
  4. A subproblem contains multiple parent groups, and there may be confounding between parent group variables from external ancestors of the subproblem. The sufficiency of local causality does not necessarily hold, and Theorem 2 only discusses variable pairs within groups and between groups and parent groups, which requires more rigorous argumentation.
  5. The basic algorithm uses different hyperparameters when running separately and embedding DEFT, such as different learning rates and iteration times for GOLEM; Some baselines show abnormally low performance, for example, SCORE's accuracy is only 0.02. These factors weaken the conclusion that 'improvement comes from decomposition itself'.
  6. There are many problems with the writing: the main text and appendix of Theorem 2 are inconsistent, Shen and Shah's citations are mixed in multiple places, and some references lack author names. The front- and back-door path proofs used in topological order proofs are also intuitive and not rigorous enough.
Questions for authors
  1. If finite sample tests are used in both the decomposition and aggregation stages, how much advantage can DEFT maintain over HCD and CPA on the real network in Table 3?
  2. How to determine the topological order when the related sets of multiple groups have the same size? Will this tie result in Algorithm 1 checking for pairs in the wrong direction?
  3. If there is a common external cause of the subproblem between the parent group variables, is the intra-group edge direction given by the local algorithm still reliable? Can you provide a formal guarantee or counterexample analysis?
  4. In a dense graph driven by a few root nodes and where almost all variables are pairwise correlated, what does grouping degenerate into? Can you provide an experiment on this diagram?
  5. Can you report the end-to-end running time, including the actual time spent on conditional independence testing, rather than just the number of tests?
6 comments
AuthorsOpenReview ↗

Response to Reviewer m2MQ (1/5)

We appreciate the reviewer’s thorough feedback, and would like to address the remaining concerns as follows:


The main experiment used pre-conditional independent testing in the decomposition and aggregation stages, and the grouping and graph construction were therefore completely error-free, which greatly overestimated the performance of the method on real data. In the limited sample experiment in the appendix, the SHD of DEFT in a larger dimension has been inferior to HCD, indicating that the robustness of the main conclusion is questionable.

We thank the reviewer for raising this question.

In finite-sample settings (without oracle CIT), we note that while DEFT's SHD becomes higher than HCD's at larger dimensions, DEFT consistently maintains substantially better precision, recall, and F1-score across all evaluated dimensions. In particular, at 500 variables, DEFT achieves an F1-score of 0.38 compared with 0.03 for HCD, with recall values of 0.44 and 0.01, respectively. This indicates that HCD's lower SHD at higher dimensions is accompanied by the failure to recover nearly all true causal edges.

In particular, the results in Table 6 demonstrate DEFT's robustness to imperfect CI estimation, as it consistently retains substantial advantages over HCD in recovering true causal relationships, even when its theoretical guarantees cannot be fully realized in practice. Although imperfect CI estimation affects DEFT's grouping and graph construction, the resulting degradation does not negate the effectiveness of our framework. Rather, the consistently superior precision, recall, and F1-score highlight DEFT's robustness in causal structure recovery, even when its grouping and graph construction are imperfect.


If finite sample tests are used in both the decomposition and aggregation stages, how much advantage can DEFT maintain over HCD and CPA on the real network in Table 3?

Additional experiments under finite-sample CI testing. Due to limited time, we conducted additional experiments comparing DEFT, HCD, and CPA on the Win95pts (7676 nodes), Andes (223223), and Diabetes (413413). Each dataset is limited to 10001000 observations and the results are reported from 1010 independent seeds.

DatasetFrameworkPrecision ↑\uparrowRecall ↑\uparrowF1-score ↑\uparrowSpurious ↓\downarrowSHD ↓\downarrow
Win95ptsCPA0.37 ±\pm 0.050.55 ±\pm 0.050.44 ±\pm 0.050.47 ±\pm 0.04132.4 ±\pm 13.0
Win95ptsHCD0.25 ±\pm 0.050.22 ±\pm 0.040.23 ±\pm 0.040.33 ±\pm 0.05136.6 ±\pm 6.5
Win95ptsDEFT0.51 ±\pm 0.040.75 ±\pm 0.040.61 ±\pm 0.040.38 ±\pm 0.0494.4 ±\pm 10.4
AndesCPA0.16 ±\pm 0.010.33 ±\pm 0.020.21 ±\pm 0.010.75 ±\pm 0.01785.8 ±\pm 25.7
AndesHCD0.26 ±\pm 0.020.23 ±\pm 0.020.24 ±\pm 0.020.51 ±\pm 0.03427.7 ±\pm 12.0
AndesDEFT0.47 ±\pm 0.020.37 ±\pm 0.030.42 ±\pm 0.020.33 ±\pm 0.04315.9 ±\pm 13.3
DiabetesHCD0.21 ±\pm 0.050.27 ±\pm 0.030.24 ±\pm 0.040.61 ±\pm 0.08971.5 ±\pm 124.9
DiabetesDEFT0.30 ±\pm 0.050.34 ±\pm 0.060.32 ±\pm 0.050.48 ±\pm 0.05771.0 ±\pm 56.2

Results. Under finite-sample CI testing, DEFT maintains strong advantages in graph recovery over both HCD and CPA on these two network structures. On Win95pts, DEFT achieves an F1-score of 0.61, compared with 0.23 for HCD and 0.44 for CPA, while reducing SHD to 94.4. Similarly, on Andes, DEFT achieves an F1-score of 0.42, compared with 0.24 and 0.21 for HCD and CPA, respectively, with the lowest SHD of 315.9. On Diabetes, DEFT produce almost 50%50\% higher F1-score compared to HCD.

Manuscript revision. We thank the reviewer for this valuable suggestion. We will incorporate these additional finite-sample experiments into Appendix B.2 and highlight the findings in the main text. We believe these additions will strengthen the practical evaluation of DEFT.

AuthorsOpenReview ↗

Response to Reviewer m2MQ (2/5)

Grouping requires that the correlation sets of two variables are "the same", making them highly sensitive to single test errors in limited samples, and a single misjudgment may change the topological order and parent group relationship. The article lacks analysis on how this error propagates along the process.

We acknowledge that inaccurate CITs can affect grouping and propagate to subsequent stages of DEFT. We analyze two principal grouping failure modes, examine their consequences through controlled experiments, and demonstrate that DEFT retains substantial advantages over existing decomposition frameworks under finite-sample CITs.

  • Failure modes: Similar to all methods that rely on hypothesis testing, our method is subject to errors under the finite sample regime. There are two kinds of hypothesis testing failures: F1 (truth:dependence, result:independence) and F2 (truth:independence, result:dependence). F1 makes the dependence set of a variable smaller than its ground-truth, thus producing many small groups. F2 make the dependence set of a variable larger than its ground-truth, thus producing few large groups.

  • Consequences: in F1, a sub-problem may be a subset of what is required in Remark 1 (Sect 3.3). This means Theorem 2 will not hold for such a sub-problem: there will be spurious connections that the subroutine may not be able to rule out. In contrast, in F2, a sub-problem may be a superset of what is required in Remark 1. This means the subroutine have more than enough evidence to rule out spurious connections (because it contains the ground-truth set). Theoretically, we expect far more F2 than F1: a small, finite volume of data often results in concluding dependence due to the lack of evidence to conclude otherwise.

  • Empirically: DEFT remains advantageous over existing decomposition frameworks (HCD, CPA). Existing constraint-based decomposition frameworks, including HCD and CPA, are subject to finite-sample errors as well. Empirical results in Appendix B.2 (Table 6), together with our additional experiments using finite-sample CITs on Win95pts and Andes, demonstrate that DEFT consistently achieves superior performance over HCD and CPA.

Manuscript revision. We thank the reviewer for the valuable suggestion to discuss the effects of inaccurate CITs. We have added this discussion to Appendix C.2 of the revised manuscript.


Algorithm 1 takes all variables of the parent group, child group, and spouse group as the condition set, which may be very large. The complexity analysis only counted the number of tests and did not take into account the cost and statistical power reduction of high-dimensional conditional tests themselves, so the term 'squared complexity' is not complete enough.

Regarding complexity, our quadratic complexity analysis specifically characterizes the number of CI queries required for decomposition and the computational cost of aggregation, rather than claiming quadratic end-to-end runtime. As established in Theorems 4 and 6, DEFT requires O(d2)O(d^2) CI queries, while its overall complexity is O(d2T+KTA+d2)O(d^2T+KT_A+d^2), where TT denotes the cost of a CI test and TAT_A the cost of solving a local subproblem.

As for the size of the conditioning set, this limits the application of all constraint-based methods and can be considered as an orthogonal challenge. Some methods side-step this challenge, including CAPA and CPA, by adopting a limit on the size of the conditioning set. Rather than imposing such restrictions, DEFT can incorporate alternative CI testing procedures designed for high-dimensional conditioning, such as Categorical residualization [1] or Sparse Regression [2], in place of traditional CITs (for example, chi-squared test).

Manuscript revision. We have addressed it in Appendix C.1 of the revised manuscript.

[1] Ankan, Ankur, and Johannes Textor. "A simple unified approach to testing high-dimensional conditional independences for categorical and ordinal data." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 10. 2023.

[2] Ning, Yang, and Han Liu. "A general theory of hypothesis tests and confidence regions for sparse high dimensional models." (2017): 158-195.

AuthorsOpenReview ↗

Response to Reviewer m2MQ (3/5)

A subproblem contains multiple parent groups, and there may be confounding between parent group variables from external ancestors of the subproblem. The sufficiency of local causality does not necessarily hold, and Theorem 2 only discusses variable pairs within groups and between groups and parent groups, which requires more rigorous argumentation.

First, we want to clarify that Theorem 2 establishes that for the subproblem Rk∪Pa[Rk]R_k\cup Pa[R_k], all spurious edges within RkR_k and from Pa[Rk]Pa[R_k] to RkR_k are identifiable. Equivalently, the remaining edges are guaranteed true edges. Theorem 2 does not discuss the orientation of these edges, just the fact that they are identifiable.

Secondly, regarding the effect of confounders of parent groups, suppose RuR_u and RvR_v are two confounded groups in Pa[Rk]Pa[R_k]. The fact that some parents of RuR_u and RvR_v is not within Pa[Rk]Pa[R_k] will lead the subroutine AA mistakenly concludes some spurious connections between the two groups. However, since DEFT discards these connections anyway, they are inconsequential. So, confounders of parent groups have no effect on the skeleton of the solution.

The fact that DEFT discards all edges within and between Pa[Rk]Pa[R_k] is decisive to your question, but is not clearly stated in the manuscript. We have clarified it in Appendix C.3 and C.4 of the revised manuscript.


If there is a common external cause of the subproblem between the parent group variables, is the intra-group edge direction given by the local algorithm still reliable? Can you provide a formal guarantee or counterexample analysis?

As discussed above, Theorem 2 assures the correct skeleton of the local solution. As for the direction of the edges within that skeleton, let us consider the following example:

U→A,U→B,L→A,M→B,A→X,B→X,X→Y.U\to A,\quad U\to B,\quad L\to A,\quad M\to B,\quad A\to X,\quad B\to X,\quad X\to Y.

Under Def. 2: There are 6 groups, i.e., {(L),(U),(M),(A),(B),(X,Y)}\{(L),(U),(M),(A),(B),(X,Y)\}. Group (X,Y)(X,Y) has 2 parent groups (A)(A) and (B)(B). The subproblem involving (X,Y)(X,Y) is {(X,Y),(A),(B)}\{(X,Y),(A),(B)\}, while UU lies outside the subproblem.

By using CITs, the subroutine finds the following skeleton: A−X,A−B,B−X,X−YA-X,A-B,B-X,X-Y. Because A−BA-B is the edge between parent groups, DEFT discards it. The final skeleton is A−X,B−X,X−YA-X,B-X,X-Y, which is the ground-truth skeleton. The direction of which is undetermined. However, since (A),(B)(A),(B) are the parent groups of (X,Y)(X,Y), the inter-group edges A−X,B−XA-X,B-X are automatically oriented by DEFT: A→X,B→XA\to X,B\to X.

A local solver that ignores the known inter-group orientations can select any CI-compatible local DAG Y→X, X→A, X→B, A→BY\to X,\ X\to A,\ X\to B,\ A\to B. If aggregation subsequently corrects only the inter-group directions, it recovers A→XA\to X and B→XB\to X but retains the incorrect intra-group direction Y→XY\to X.

This counterexample does not indicate missing causal information: enforcing A→XA\to X during local orientation excludes Y→XY\to X, because it would introduce the collider A→X←YA\to X\leftarrow Y, contradicting A⊥Y∣XA\perp Y\mid X.

Conclusions. The above failure arises when a local solver does not incorporate available group-level orientation constraints, rather than from a loss of CI information during decomposition. A principled remedy is to incorporate these directions as background knowledge during local orientation, rather than only at aggregation. Edges that remain observationally non-identifiable, such as covered edges, still require additional assumptions for unique orientation. As clarified in Remark 3, DEFT's full-graph identifiability ultimately depends on the designated local solver and its assumptions.

Manuscript revision. We have addressed it in Appendix C.4 of the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.