Causal Graph Learning via Distributional Invariance of Cause-Effect Relationship
Causal Graph Learning;Invariance
Yes
No ethics review needed.
## Questions:
* How are the authors resampling the datasets?
* Do you have to perform this invariance test for all possible parent sets?
* Why is $Pa[B] = \emptyset$ in the definition of set $\mathbf{B}$ (section 4.1)? What does that imply?
* In practice with real-world data, is the variance always zero for all true parents (equation 1)? Why or why not? Should a threshold be used?
* How expensive is it to compute $\phi(X)$? Do we have to iterate over all $X$? And do it again after performing step ii in Theorem 3?
The paper is well written. The figure is helpful for understanding the algorithm. The experiments are extensive.
The paper utilizes the invariance property of $P(X \mid \text{Pa}(X))$ despite having different $P(\text{Pa}(X))$ to find the causal parents. For this purpose, they choose some source priors, generate corresponding datasets, and verify the invariance. Finally, they show their performance on a variety of synthetic and real-world setups.
## Minor weaknesses:
* The authors mentioned “finding the maximum clique in an augmented bidirectional graph” multiple times but without a proper definition or example/visualization.
* The source variables should be defined in a little more detail.
* What does $P'$ in equation 2 refer to? It should be precise.
* “The intuition is if we can re-sample $D_i$ from $D \sim P(X)$ such that $D_i \sim P_i(X)$,” This is a little unclear. How are $D \sim P(\mathbf{X})$ and $D_i \sim P_i(\mathbf{X})$ different?
* It is unclear how $D_1, D_2, \dots, D_M$ are sampled. How are the $m$ source priors ($P_i(\mathbf{B})$) obtained? Although these are discussed later, some hints/intuitive discussion should be provided earlier in the paper.
* “We cannot compute $P_i(X)$, … we can re-sample $D_i$ from $D$ so that $D_i \sim P_i(X)$” – based on my understanding, the first case is computing the numerical probability table, and the second case is sampling without any such table. This difference should be made clear.
* More details on "downsampling without replacement" are needed.
* An intuitive explanation of the “minimal downsampled rate” is required.


## Major weaknesses
* Suppose $Z$ is not a parent but an ancestor. Shouldn’t we also get variance = 0 (equation 1) in such cases? Does a change in $P(\text{Ancestor})$ affect $P(\text{descendant} \mid \text{ancestor})$?
* Many important concepts are delayed until section 4.2. The authors should consider introducing them earlier in the paper.

I will consider increasing the score after seeing author's response and reviewer discussion.
Yes
No ethics review needed.
- Does the proposed causal discovery algorithm work for time-series data? What are the challenges?

I would be very glad to increase my score if the authors could resolve my concerns.
- This paper is written well, with clear descriptions and motivations. 

- The authors propose practical algorithms for causal discovery, with some interesting theoretical findings, e.g., the basis of a DAG, the minimal downsampling rate, etc. 

- The experiments under synthetic datasets and real-world networks are extensive, which verified the advantages in large-scale datasets.
Based on the fact that the distribution of an effect, conditioned on its causes, remains invariant to changes in the prior distribution of those causes, this paper proposes a causal discovery algorithm for large-scale datasets. Specifically, it designs an invariance test, which is achieved by a downsampling scheme. It also makes the best of searching Markov blankets of all variables, to reduce the time complexity. Experiments on synthetic datasets and real-world networks show better scalability.
- Some details seem to be missing in the paper.
For example, 

i) Footnote 2 and Theorem 1 tell how to find non-parent sets, whereas how to set the threshold for the variance is not clear. Please give the details in the paper.

ii) How to learn the different priors $P_i(X)$, with the estimated $m$? Did the authors assume some distributions?

- Theorem 2 provides a necessary condition to test whether a subset $Z$ is the parent set of X. However, it is not a sufficient condition. Although the authors stated, “When m is infinitely large, the implication in Eq. (1) becomes bi-directional and $V[P+(X | Z)] = 0$ definitively implies $Z = Pa[X]$”. It is not that clear why this implication we can get. Please elaborate on it more.

- It is better to perform some real-world datasets for validation. This is because bnlearn provides real networks and it generates the data based on the networks. These datasets look like semi-synthetic. BTW, in Table 2, when dealing with small-scale datasets (or even a large-scale dataset Munin), the runtime all seem not to be satisfactory. Please explain it.
Yes
No ethics review needed.
(See above)
1. The proposed method is rather novel.   
2. Overall, the paper is well-structured and clearly written.    
3. The experiments are extensive, covering 3 types of functional causal models, 6 causal discovery baseline methods, and varying graph sizes.
This paper introduces a novel approach to causal learning through a new invariance test for causality, which underpins a reliable and scalable algorithm for reconstructing causal graphs from observational data. This method leverages a core insight that the conditional distribution of the effect given the cause remains invariant under changes in the prior distribution of the cause. This insight enables a parent-identification process for each variable using synthetic data augmentation. This process is integrated with an efficient search algorithm that utilizes prior knowledge of each effect variable’s Markov blanket, along with the empirically observed sparsity of causal graphs, to significantly reduce computational complexity.
Any thoughts on how to extend your method to handle heterogeneous or time-series datasets?
Yes
No ethics review needed.
See the weakness above.
- This work leverages the invariance of conditional distribution and then proposes a downsampling method, combining them to find the parent set.
This paper proposes a new framework that leverages the invariance of effect conditioned on its causes for causal discovery from observational data. The main idea is it try to disturb the p(cause) distribution and see whether the p(effect|cause) would change after the disturbance.
- The main issue is that since the real intervention is not applicable to the observational data, it provides a downsampled technique to approximate the p(effect|cause) after the disturbance, which, however, has no theoretical guarantee. This is, how to guarantee such a downsampled correctly corresponds to the real distribution after the disturbance?
- Since the basis variables would include the leaf vertices, in such a case, changing the prior basis variables will not affect the distribution of their ancestors, and thus it may not have a similar effect to changing prior over source variables.

Typos:
- "Theorem 2" -> "Theorem 4" in Theorem 5
@inproceedings{
anonymous2024causal,
title={Causal Graph Learning via Distributional Invariance of Cause-Effect Relationship},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=Lxst78Rrwj},
note={under review}
}
This paper introduces a new framework for recovering causal graphs from observational data, leveraging the fact that the distribution of an effect, conditioned on its causes, remains invariant to changes in the prior distribution of those causes. This insight enables a direct test for potential causal relationships by checking the variance of their corresponding effect-cause conditional distributions across multiple downsampled subsets of the data. These subsets are selected to reflect different prior cause distributions, while preserving the effect-cause conditional relationships. Using this invariance test and exploiting an (empirical) sparsity of most causal graphs, we develop an algorithm that efficiently uncovers causal relationships with quadratic complexity in the number of observational features/variables, reducing the processing time by up to 25x compared to state-of-the-art methods. Our empirical studies on a diverse benchmark of large-scale datasets demonstrate that the developed algorithm consistently performs better or comparable to existing works while generally achieving better scalability.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Causal Graph Learning Invariance
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/61d9490fbe1e3bc6421724bb2e591764d97723d8.pdf
causal reasoning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
Causal Graph Learning via Distributional Invariance of Cause-Effect Relationship
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission