The Path-Driven Independence Testing (PIT) Algorithm

• $\mathcal{I}(\mathcal{G})$ is not defined in the background.
• The phrase "activate the trail” is not defined in the background.
• The idea seems to be overlapping significantly with the work by Li et al. [1], which says to implement the CI tests for a pair X, Y with the conditioning set that contains only variables along the path between X and Y. Also, [1] is not cited in the paper. Please see the first condition of defining a consistent set which is Definition 1 in [1]. The difference is that the proposed method tries to include more nodes to ensure the path is blocked whereas Li et al. exclude nodes that are common children from the conditioning set between the pair. In other words, Li et al.’s algorithm should subsume the proposed Algorithm 1, which is the main algorithm that shows significant improvement in reducing the number of CI tests.
• Although Algorithm 2 BPIT saves the number of CI tests, it also increases the conditioning set size which may lose statistical power more quickly in practice with a small sample size. This is evident by looking at the performance in Table 4 for the dataset DIABETES, which has 413 nodes and 602 arcs.
• There are plenty of algorithms that aim to reduce the number of CI tests by using a divide-and-conquer strategy for large-scale causal discovery [2,3,4,5] and none of them is cited and no discussion is presented to address the gap between the proposed method and these works. If the proposed method can be plugged into this line of work, then it is fair to pick a SOTA method and integrate the proposed strategy into it to show how much of a difference it can make.
• The experiment uses only Structual Hamming Distance as the only metric for evaluating model accuracy.

Reference:

[1] Li, Honghao, et al. "Constraint-based causal structure learning with consistent separating sets." Advances in neural information processing systems 32 (2019).

[2] Zhang, Hao, et al. "Learning causal structures based on divide and conquer." IEEE Transactions on Cybernetics 52.5 (2020): 3232-3243.

[3] Cai, Ruichu, Zhenjie Zhang, and Zhifeng Hao. "Sada: A general framework to support robust causation discovery." International conference on machine learning. PMLR, 2013.

[4] Zhang, Hao, et al. "Recursively learning causal structures using regression-based conditional independence test." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.

[5] Zhang, Hao, et al. "Towards Effective Causal Partitioning by Edge Cutting of Adjoint Graph." IEEE Transactions on Pattern Analysis and Machine Intelligence (2024).

• The paper is dense in notation and new concepts in nature. A runnning example when introducing these concepts and algorithms will be helpful to illustrate the idea.
• The experiments and showcase of improvement leave some doubt. See questions.

• My main concern with the manuscript is the relevance of its main contribution when compared to existing methods in the literature. The paper could benefit from an in-depth related work analysis on methods that had proposed time savings when testing independence, such as [1] or [2] and others. The relevance of the method proposed here could be better demonstrated when concepts in the manuscripts are compared to existing concepts. For instance, the idea of Covering Path (Definition 1) and the result in Lemma 3 would fare in comparison with other algorithms' active/relevant nodes.
• Although experimental results are encouraging, the paper is unclear if the wins are consistent or significant in structural learning timings. Table 2, for instance, shows favorable results, although for larger datasets, the gains could be significant in some networks while very close to others. The manuscript could benefit from a thorough analysis of the results so that algorithm users might manage expectations when using it in specific circumstances or applications.

[1] Shachter, Ross D. "Bayes-ball: The rational pastime (for determining irrelevance and requisite information in belief networks and influence diagrams)."

[2] Butz, Cory J., André E. dos Santos, and Jhonatan S. Oliveira. "Relevant path separation: A faster method for testing independencies in Bayesian networks."

Although the proposed method is theoretically sound and Table 1 presents the number of CI tests required by PIT for certain network structures, there is no guarantee for general structures. As a result, it is unclear whether PIT is faster than PC or other constraint-based methods. An analysis of the worst-case number of CI tests is missing. For example, in "A Recursive Markov Boundary-Based Approach to Causal Structure Learning" by Mokhtarian et al., the authors propose a recursive method, analyze the worst-case number of CI tests, compare it with other methods (not only PC), and introduce a lower bound. How does PIT compare to these methods?

The empirical results are limited, as the authors only compare PIT with PC and omit comparisons with other relevant methods such as Marvel, GS, and CS.

The complexity of constraint-based methods depends not only on the number of CI tests but also on the size of the conditioning set. How large could the conditioning sets be in the PIT algorithm?

This method, like many other constraint-based approaches, requires the causal sufficiency assumption, which often does not hold in practice. However, some relevant algorithms can be extended to handle cases with latent confounders. Based on PIT's logic, it is unclear whether the notion of path-driven independence tests can be extended to networks with latent confounders. Do the authors have any insights on how this method might be generalized?