- 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
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+ is always better or equal to subroutine 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 to solve then discards edges within and between . By solving smaller subproblems first, edges within and between are already known, which gives amber evidences for to quickly solves . However, this would also mean that 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.
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:
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 (76 nodes), Andes (223), and Diabetes (413). Each dataset is limited to 1000 observations and the results are reported from 10 independent seeds. We use PC as the subroutine. The results are summarized below.
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% 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.