Learning Identifiable Causal Structures with Pairwise Representation

Reviewer JJmt wonders whether the mentioned heuristic and Meek rules are applied for the baseline algorithms.

As detailed in Appendix Sec. A3, we have employed the implementation provided by the gCastle repository for multiple baseline methods. In the case of AVICI, the heuristic and Meek rules are not applicable, as AVICI directly predicts the Directed Acyclic Graph (DAG).

Reviewer JJmt wonders why classical algorithms perform worse on the experiments.

We adhere to the default settings provided in the gCastle library, and detailedly check their predictions to ensure correctness. The relevant codes and datasets will be made available for release.

Reviewer JJmt wonders more details about the experiments on Sachs dataset.

As demonstrated in Sec. 5.2, we trained the PAIRE model on randomly generated scale-free (SF) graphs and then used it to predict the causal graph based on observational data from the Sachs dataset. The observational data, sourced from the Bnlearn repository, is readily compatible and can be directly processed by our trained PAIRE model.

Reviewer JJmt has suggestions on paper writing.

Thanks for your careful reading and suggestions. We have revised the paper according to your suggestions.

Reviewer JJmt wonders the theoretical guarantee of PAIRE.

Reviewer 4F7j has expressed a concern similar to yours and we'd like to provide a same response:

• Theoretical Guarantee. As outlined in Sec. 3 and further elaborated upon in the revised Appendix Sec. A1, our model is based on three assumptions which are commonly used in the causal discovery domain: causal sufficiency, Markovian property, and faithfulness. These assumptions are widely recognized and employed in related work (Ma et al., 2022)(Dai et al., 2023). Furthermore, by assuming that the neural network functions as a universal approximator, we provide a theoretical foundation for the asymptotic correctness w.r.t. sample size and consistency of our method in Appendix Sec. A1.
• Discussion on Practicability. Even though our method has a theoretical guarantee of the correctness with infinite samples, it has distinct advantages as a kind of Supervised Causal Learning (SCL) method under the finite samples conditions. For example, traditional constraint-based methods usually suffer from the unreliablity of conditional independence test in practice. Additionally, search-based methods tend to underperform because of the exponential growth of the search space, which is also mentioned in related work (Ke et al., 2023). However, SCL methods can learn from supervised training data about how to make predictions from practical finite samples, which makes the causal structure learning more robust and general. We have elaborated the contents above in the revised Appendix Sec. A1.4.

Reviewer JJmt wonders more experiments on larger graphs.

As evidenced in Sec. 5, we have verified that PAIRE outperform other methods on the 30-node graphs, which is a typical setting of the graph size in the literature (Ke et al., 2023)(Lorch et al., 2022). Currently we do not have the capability for experiments on the larger graphs due to the limited computational resource, and the improvement of the scalability is left as interesting future work.

Reviewer JJmt wonders the difference between PAIRE and AVICI.

• As we summarize in Sec. 1, we design pairwise representations to capture essential causal information, and propose to use a skeleton matrix with a v-tensor as the learning target. Our ablation study shown in Sec. 5.3 - 5.4 verify the effectiveness of these innovations.

Reviewer JJmt wonders how PAIRE handles the higher-dimensional variables.

• In the standard framework of causal discovery, each variable constitutes a unidimensional probability distribution. When dealing with high-dimensional variables, the graph representation and the corresponding causal structures are unclear. We leave it as interesting future work.

Reviewer JJmt wonders more details about the standard forward sampling.

As detailed in Appendix Sec. A3, we apply both the linear Gaussian mechanism and a general nonlinear mechanism for continuous data generation. The Random Fourier Function mechanism is used for the general nonlinear data following the previous paper (Lorch et al., 2022). For discrete data, the Bernoulli distribution is employed. We have revised Appendix Sec. A3 to further clarify it.

Reviewer JJmt wonders what the node feature refers to in Sec. 4.2.

• As elaborated in the final paragraph of Sec. 4.2, the node features refer to the features of each individual variable. These are derived from the node feature encoder module within our model. We have revised Appendix Sec. 4.2 to further clarify it.

Reviewer JJmt wonders more reasons of using the unidirectional attention operation.

The unidirectional attention operation is motivated by two key insights:

• As highlighted in Sec. 1, it is crucial to incorporate both pairwise and node information to effectively capture essential causal information, such as persistent dependency and orientation asymmetry. To this end, unidirectional attention is employed to utilize information from both pairwise features and node features and represent the essential causal informtion.
• In terms of computational complexity, unidirectional attention is less demanding than an alternative self-attention operation involving pairwise features alone. Consequently, this approach also serves to reduce the overall computational costs.

We have further clarified it in the revised Sec. 4.2.

Reviewer JJmt wonders how to obtain sufficient high-quality training data for our DNN model.

• As mentioned in Sec. 1, the training data for SCL methods can be readily obtained via synthetic generation. Different with some other tasks, we are able to generate infinite observations for a given causal graph with an approximate free cost. Therefore, it offers the significant advantage of the acquisition of training data, allowing for extensive and sufficient training of the models. The effectiveness of this paradigm has been verified in previous SCL methods (Dai et al., 2023; Ke et al., 2023; Ma et al., 2022).

Thank you for your constructive comments and suggestions, which have been immensely helpful in enhancing our paper. We have meticulously integrated your feedback into the revised manuscript. Below, we first restate your comments, followed by our detailed responses to each point.

Reviewer JJmt wonders how PAIRE handles cycles.

Firstly, in the task of skeleton learning, the predicted skeleton is an undirected graph, thereby precluding the presence of cycles. We assume the reviewer questions how to handle cycles in CPDAG prediction. Theoretically, our updated analysis in Appendix Sec. A1 shows that PAIRE is theoretically proven to be asymptotically correct and consistency. This implies that cycles are never predicted under ideal cases. Practically, the occurrence of cycles is also rare in our predictions and PAIRE performs well in our experiments.

Reviewer JJmt wonders the transferability of PAIRE (The test distribution is different with the training distribution).

The PAIRE model, trained on randomly generated datasets, is specifically designed to adeptly capture causal relations through our pairwise representations. As detailed in the Appendix Sec. A3, in our experimental evaluations, we primarily focus on out-of-distribution (OOD) settings, where the test distribution is distinct from the training distribution. As the experimental results presented in Sec. 5 indicate, PAIRE exhibits strong generality under this OOD setting. It is worth to note that the transferability of Supervised Causal Learning is also evidenced in previous work (Dai et al., 2023).

Reviewer JJmt wonders more experiments about the performance with varying edge density and sample size.

Varying Sample Size. We assessed PAIRE across various quantities of observational samples per graph during testing (100, 200, ..., 1000). Owing to space limitations, we showcase four key metrics in the table below: AUC and ACC for skeleton prediction, along with V-structure F1 and Identifiable Edges F1 for CPDAG prediction. The visualized figures for all metrics are provided in the revised Appendix Sec. A4. The model's performance enhances with the augmentation of sample size. These consistent upward trends suggest that PAIRE exhibits stability and is not overly sensitive to changes in sample size.

• WS Dataset

• SBM Dataset

Varying Edge Density. We evaluated PAIRE over a range of edge densities in the test graphs, utilizing the SBM dataset, as it allows for the direct setting of average edge densities. Owing to space limitations, we showcase four key metrics in the table below: AUC and Acc. for skeleton prediction, along with V-structure F1 and Identifiable Edges F1 for CPDAG prediction. The visualized figures for all metrics are provided in the revised Appendix Sec. A4. It's apparent that the task is becomes more difficult as edge densities increase. However, the performance decline is not abrupt, indicating that PAIRE's performance remains relatively stable across various edge densities, thereby confirming its versatility.

We thank you for your further response and we answer the remaining questions below.

Reviewer JJmt wonders more details to make sure PAIRE will not yield cycles.

To substantiate the chaim that cycles are infrequent in the final predictions, we quantified the occurrence of cycles within the predictions:

Furthermore, to address the occasional emergence of cycles, we propose a straightforward algorithm to ensure acyclicity:

For each detected cycle composed of edges from multiple v-structures:
    Identify the v-structure with the lowest prediction score.
    Remove the identified v-structure.
End For

This procedure iteratively eliminates the least confident v-structures, thereby resolving cycles effectively.

We have revised the Appendix Sec. A4 to further clarify the acyclicity of the PAIRE predictions.

Reviewer JJmt wonders more about how does baselines in gCastle apply meek rules.

The application of Meek rules is in line with the standard procedures for general constraint-based causal discovery methods, as also depicted in Fig. 2 and Sec. 2.1 of [2]. Among all of the baselines, only PC belongs to constraint-based methods, and the Meek rules are not applicable to other non-contraint-based methods. We check the codes and find that the PC implementation in gCastle applys Meek rules at https://github.com/huawei-noah/trustworthyAI/blob/master/gcastle/castle/algorithms/pc/pc.py#L203.

[2] Yu, K., Li, J., & Liu, L. (2016). A review on algorithms for constraint-based causal discovery. arXiv preprint arXiv:1611.03977. Avaiable at: https://arxiv.org/abs/1611.03977v1

Thank you for your constructive comments and suggestions, which have been immensely helpful in enhancing our paper. We have meticulously integrated your feedback into the revised manuscript. Below, we first restate your comments, followed by our detailed responses to each point.

Reviewer mhH7 wonders more comparison on the number of parameters and FLOPs.

As outlined in Sec. 5.3, our experiments with PAIRE utilize a 6-layer node feature encoder, amounting to 2.8 million trainable parameters. In comparison, the AVICI method comprises 3.2 million trainable parameters. It's important to note that this comparison of parameter count is not directly applicable to other baseline methods, as they do not employ SCL techniques. Regarding the FLOPs, PAIRE requires 38M FLOPs while AVICI requires 33M FLOPs in processing one batch of graphs. Although PAIRE's computational cost is marginally higher, it remains within a similar range.

Reviewer mhH7 wonders more about the unidirectional attention.

The unidirectional attention means only using the pairwise features as the Query, and the node features as both Key and Value. This approach is motivated by two key insights:

• As highlighted in Sec. 1, it is crucial to incorporate both pairwise and node information to effectively capture essential causal details, such as persistent dependency and orientation asymmetry. To this end, unidirectional attention is employed to utilize information from both pairwise features and node features.
• In terms of computational complexity, unidirectional attention is less demanding than a self-attention operation involving pairwise features alone. Consequently, this approach also serves to reduce the overall computational costs.

We have further clarified it in the revised Sec. 4.2.

Reviewer mhH7 suggests to add some explanation in certain parts of the paper.

Thanks for your suggestion. We have revised the figure captions and the expression in Sec. 4.1 accrodingly.

Reviewer t5Qz concerns 100 simulated graph is insufficient for PAIRE training.

As noted in Sec. 4.1, both the training graph $G$ and the corresponding dataset matrix $D$ are generated in real-time. They are not reused during training. Consequently, this approach potentially provides an infinite amount of training data for the model. A typical PAIRE model is trained for 300 epochs, with each epoch comprising 6,000 training graphs. This results in a cumulative total of 1,800,000 training graphs throughout the training process. As we mentioned in Appendix Sec. A3, each synthetic test datasets contain 100 graphs. We have further clarified this in the revised Appendix Sec. A3.

Reviewer t5Qz wonders more details about data generation and average degree of graphs.

Comprehensive details regarding our experimental setup can be found in Appendix Section A3. As discussed in the 'Synthetic Data' paragraph, we adopted the Random Fourier Function mechanism for generating general nonlinear data, in line with the approach used by Avici (Lorch et al. 2022). The degree of training graphs in our experiments varies randomly among 1, 2, and 3. For testing, the average degree of Watts-Strogatz (WS) graphs is about 4.9, while the average degree of Stochastic Block Model (SBM) graphs is 2, following the settings in the aforementioned study. We have revised the Appendix Sec. 3 to include the average degrees of the graphs.

Reviewer t5Qz wonders why GES failed on the WS dataset.

GES aims to identify an optimal DAG based on a specific score function. This search process, however, can be time-intensive and encounter computational challenges. In our experiments, we utilized the default settings from the gCastle library. It indeed failed to produce results within 24 hours. This experience underscores the benefits of employing DNN-baed SCL: once trained, these models offer a significantly faster inference process.

Reviewer t5Qz concerns the scalability of PAIRE on larger graph.

In the whole paper, we have revealed the significance and potential of pairwise representations, as they are crucial for capturing essential information such as persistent dependency and orientation asymmetry. As specifically evidenced in Sec. 5.3, we have proved that models incorporating pairwise representations outperform the original models on the 30-node problems, which is a typical setting of graph size in the literature (Ke et al., 2023)(Lorch et al., 2022). The improvement of the scalability on larger graphs is left as interesting future work.

Thank you for your constructive comments and suggestions, which have been immensely helpful in enhancing our paper. We have meticulously integrated your feedback into the revised manuscript. Below, we first restate your comments, followed by our detailed responses to each point.

Reviewer t5Qz concerns PAIRE lacks theoretical consistency guarantee.

Reviewer 4F7j has expressed a concern similar to yours and we'd like to provide a same response:

• Theoretical Guarantee. As outlined in Sec. 3 and further elaborated upon in the revised Appendix Sec. A1, our model is based on three assumptions which are commonly used in the causal discovery domain: causal sufficiency, Markovian property, and faithfulness. These assumptions are widely recognized and employed in related work (Ma et al., 2022)(Dai et al., 2023). Furthermore, by assuming that the neural network functions as a universal approximator, we provide a theoretical foundation for the asymptotic correctness w.r.t. sample size and consistency of our method in Appendix Sec. A1.
• Discussion on Practicability. Even though our method has a theoretical guarantee of the correctness with infinite samples, it has distinct advantages as a kind of Supervised Causal Learning (SCL) method under the finite samples conditions. For example, traditional constraint-based methods usually suffer from the unreliablity of conditional independence test in practice. Additionally, search-based methods tend to underperform because of the exponential growth of the search space, which is also mentioned in related work (Ke et al., 2023). However, SCL methods can learn from supervised training data about how to make predictions from practical finite samples, which makes the causal structure learning more robust and general. We have elaborated the contents above in the revised Appendix Sec. A1.4.

Reviewer t5Qz wonders more about the compairson with the listed methods.

We present the comparison between PAIRE and the aforementioned methods on the WS dataset, following the default settings in the gCastle library.

PAIRE consistently demonstrates superior performance in comparison with these methods. We have included the above results in the revised Appendix Sec. A4. Note that the RL-BIC method is time-consuming and fails to produce results within a reasonable timeframe.

Reviewer t5Qz suggests us to discuss two related papers [1, 2].

• [1] causal discovery with reinforcement learning, ICLR 2020
• [2] Neural Causal Structure Discovery from Interventions

Our work is more related to CSIvA compared with the two mentioned papers. Paper [1] is a score-based method rather than a supervised causal learning method. It suggests to use Reinforcement Learning (RL) in the search process, employing a transformer network in the encoder and outputs Bernoulli distributions for the adjacency matrix. Unlike CSIvA (Ke et al., 2023), AVICI (Lorch et al., 2022), and our approach, their transformer network lacks sample-wise and node-wise attention mechanisms. We have add a relevant discussion in Sec. 2 in our revised manuscript. Paper [2] introduces a continuous optimization method named Structure Discovery from Interventions (SDI). Its setup is different with PAIRE as it integrates both observational and interventional data.

Reviewer t5Qz wonders why CSIvA reports a seemingly better result than PAIRE on Sachs.

As noted in Appendix Sec. A3, additional data of single interventions on each variable is available under the CSIvA settings hence CSIvA predicts the DAG. Our PAIRE is designed to learn from observational data and predicts CPDAG. Therefore, a direct comparison is not meaningful. Moreover, as noted in Appendix Sec. A3, since the code for CSIvA has not been made publicly available, we are unable to modify it for a comparative analysis with PAIRE.

Reviewer t5Qz concerns the scalability of PAIRE on larger graphs.

Even though we cannot train models on larger datasets due to the limitation of time and computational resouce currently, we present the performance of the PAIRE model when applied to larger WS graphs in the Table below. The models were initially trained on graphs comprising 30 vertices, positioning this task within an OOD setting in terms of graph size. To establish a point of reference, we also include results from the PC algorithm as a baseline comparison. Despite the OOD conditions, PAIRE maintains robust performance, verifying its scalability and the model’s general applicability across varying graph sizes.

Reviewer t5Qz concerns PAIRE cannot handle interventional data.

Causal discovery from observational data is a well-established and extensively studied problem, which serves as the primary focus of our paper as shown in Sec. 1. Therefore, this paper does not target causal learning from interventional data.

Nevertheless, extending PAIRE to support interventional data is an interesting future work. The two key components of PAIRE, i.e., pairwise representation and learning the identifiable causal structures, can both be extended to interventional data. When we can additionally access interventional data, the identifiable causal structure is up to an I-MEC (short for Interventional-Markov equivalence class) [1], which is a generalization of MEC. It is characterized by skeleton and v-structures as proved by Theorem 3.9 in [1]. Thus, identifiability is a unique characteristic of causal structure learning that we should respect.

Regarding the pairwise representation, we present an ablation study of it in the simple setting of causal discovery from interventional data: We simulated single interventions with targets on all nodes separately so the i-MEC here is exactly the DAG. As shown in the table, the model with pairwise representation clearly outperforms the one without using pairwise representation. Further exploration of DNN-based SCL methods on interventional data is left as our future work.

[1] Karren D. Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions. In ICML, 2018.

Thank you for your constructive comments and suggestions, which have been immensely helpful in enhancing our paper. We have meticulously integrated your feedback into the revised manuscript. Below, we first restate your comments, followed by our detailed responses to each point.

Reviewer 4F7j wonders our assumptions and more theoretical guarantee.

• Theoretical Guarantee. As outlined in Sec. 3 and further elaborated upon in the revised Appendix Sec. A1, our model is based on three assumptions which are commonly used in the causal discovery domain: causal sufficiency, Markovian property, and faithfulness. These assumptions are widely recognized and employed in related work (Ma et al., 2022)(Dai et al., 2023). Furthermore, by assuming that the neural network functions as a universal approximator, we provide a theoretical foundation for the asymptotic correctness w.r.t. sample size and consistency of our method in Appendix Sec. A1.
• Discussion on Practicability. Even though our method has a theoretical guarantee of the correctness with infinite samples, it has distinct advantages as a kind of Supervised Causal Learning (SCL) method under the finite samples conditions. For example, traditional constraint-based methods usually suffer from the unreliablity of conditional independence test in practice. Additionally, search-based methods tend to underperform because of the exponential growth of the search space, which is also mentioned in related work (Ke et al., 2023). However, SCL methods can learn from supervised training data about how to make predictions from practical finite samples, which makes the causal structure learning more robust and general. We have elaborated the contents above in the revised Appendix Sec. A1.4.

Reviewer 4F7j suggests to clarify the assumptions to criticize the Bernoulli-sampling adjancency matrix approach.

We clarify that when the final prediction is up to a Markov Equivalence Class (MEC) rather than a fully identifiable DAG, the Bernoulli-sampling adjacency matrix approach may result in inconsistency for Unshielded Triples formed by non-identifiable edges. For instance, with linear Gaussian and discrete data, it is established that only the MEC consisting of skeleton and v-structure is identifiable. This Bernoulli-sampling adjancency matrix approach, as demonstrated in Sec. 1, leads to inconsistency in such cases. We have further clarified it in the revised Sec. 4.3.1.

Reviewer 4F7j wonders more experimental results under other settings, like linear non-Gaussian models.

As shown in Sec. 5.1 - 5.2, we have conducted experiments in more general setups, such as general nonlinear and discrete data. We believe these settings are more general and difficult than the linear non-Gaussian models.

Thanks for your detailed response.

I align with Reviewer t5Qz in key concerns, particularly regarding the theoretical guarantees and the method's capacity to seamlessly integrate key assumptions, such as conditional independence, for identifiability. Unfortunately, after reviewing the responses to both Reviewer t5Qz's comments and mine, I have not received clear clarification.

Further, from a modeling perspective, nonlinear models offer a broader scope than linear models. However, considering information content, nonlinear models provide richer information that can contribute to causal discovery. Therefore, it remains valuable to assess the performance of your method on standard linear non-Gaussian models.

Given these considerations, I maintain my current rating.