Summary
The paper studies the setting where data is generated from a mixture of DAGs and one wishes to recover the "true edges" (edges that exist in at least one of the underlying DAGs). Similar to the usual causal discovery setting, observational data alone is insufficient and interventions are required. The paper characterize the set of interventions needed to learn these true edges and provide an algorithm for doing so. Some small scale experiments and source code were given.
Strengths
The concept of mixture of DAGs provide an alternative framework to capture cyclic causal system and, to my understanding, is under-explored. This paper aims to fill some of these gaps.
Weaknesses
The paper strives to recover "true edges" (objective 1 on Line 195) but I don't think they can map these edges to the appropriate underlying DAG within within the mixture of DAGs. It is unclear why it is interesting to be able to know these edges without the context of the DAG they belong to. To me, this severely weakens the motivation/usefulness of this work.
The experimental evaluation felt rather weak.
Questions
General questions:
- [1] also studied the universal lower bound problem that you mentioned on Line 92, and [2] eventually provided an exact characterization for the number of interventions required to recover the DAG from the observational essential graph. You may want to consider adding these references in your revision.
- Can you motivate why it is sufficient/useful enough to recover "true edges" (objective 1 on Line 195)? Your approach cannot identify which DAG each of the recovered edges belong to within the mixture of DAGs, right?
- Is the number $K$ of mixture models given to the algorithm as input? The phrase "a priori knowledge of the number of mixture components" on Line 251-252 seem to suggest that $K$ is typically not given. Also, Algorithm 1 is independent of $K$. However, $K$ features prominently in the characterization (e.g. Theorem 2), so how does one perform the correct set of interventions without $K$ as input?
- On Line 282, you mention "intervening on any set $I$ that contains $B(i)$ breaks all the cyclic relationships in $C(i)$". Why is this so? I thought some "edge cutting" (i.e. exactly one endpoint of the edge is in intervention set) is needed in order to distinguish edge directions? For example, intervening on the entire set of vertices will trivially include $B(i)$ but this does not provide any useful information, right?
- In Line 290, do you want to perhaps write $(A \setminus (S_1(i) \cup \ldots \cup S_{n-1}(i)))$ since the algorithm is "removing the layer $S_u(i)$ from $A$ after each iteration", or at least reference Line 26 in Algorithm 1?
- In equations (23) and (24) of Appendix C, shouldn't are you missing $\cup \{i\}$? I don't think you defined descendants and ancestors to include $i$ itself, or maybe I'm mistaken?
- On Line 620, you wrote $S_1$. I don't see this defined anywhere (please correct me if I missed it). I don't think this is a typo of $S_1(i)$ here since $j \in S_1(i)$ and $j \not\in pa_m(j)$. This undefined notation also appears in the remaining of this proof and is inhibiting my ability to verify Theorem 3.
- The mixture in Figure 2 assumes that $P_{G_1}(1) = P_{G_2}(1)$ since the $y$ node does not point to the $I$-mixture DAG (definition 5 and equation (2)), right? This assumption was not mentioned in Appendix D.
Experiment questions:
- The graph sizes in the experimental evaluation were extremely small. Is there a reason for this? In Appendix E (line 727), you say "only a marginal decrease in performance" when $K = \{2,3,4\}$ and $n \in \{5,\ldots,10\}$. I'm not sure if that is enough scale to draw such a conclusion...
- By setting p = 2/n in the Erdos-Renyi G(n,p) graph generation, the graphs will likely be disconnected (random graph theory tells us we need about p ~= log n / n for the graph to be connected). Will this be a problem for your experiments if you scale to larger graphs?
- Consider mentioning the edge weights of your linear Gaussian model in the main paper instead of the appendix. Line 348 claims that s = 1000 samples are sufficient for almost perfect precision but finite sample guarantees for "good recovery of the graph" scale non-trivially with the correlation strength, e.g. see the finite sample analysis for linear Gaussians in [3].
- What is the mixture skeleton learning algorithm?
- In Appendix E, you mentioned that "the same edge weight is assigned to all realizations of a true edge across all component DAGs". Why is this reasonable? I thought the whole point of mixture models is that $p_\ell \neq p_{\ell'}$ in general? See Line 117.
Possible typos:
- Extra bold of "ixture" on Line 255?
- Equation (57): Do you mean $C(5) = \emptyset$?
References:
[1] Porwal, Vibhor, Piyush Srivastava, and Gaurav Sinha. "Almost Optimal Universal Lower Bound for Learning Causal DAGs with Atomic Interventions." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.
[2] Choo, Davin, Kirankumar Shiragur, and Arnab Bhattacharyya. "Verification and search algorithms for causal DAGs." Advances in Neural Information Processing Systems 35 (2022): 12787-12799.
[3] Kalisch, Markus, and Peter Bühlman. "Estimating high-dimensional directed acyclic graphs with the PC-algorithm." Journal of Machine Learning Research 8.3 (2007).