Root Cause Analysis of Outliers with Missing Structural Knowledge

Addressing weaknesses

1. Thank you for raising this issue, it’s of course very important that the paper is as easy to follow as possible. For the Experiments section we propose stating, in bullet points, for each experiment: how it is performed, why it is performed, the range of synthetic parameters used and the methods compared including the assumptions each makes. In addition, we propose including a new table which summarises this information and where to find the corresponding results figures. Thank you as well for pointing out where we can optimise space. For the Introduction, we propose reorganising Subsection 1.1 to give a more detailed breakdown of the following sections, including a summary of the main results from each, and the motivations for each. We hope this will better motivate the work and allow the reader to better anticipate what results are coming and why. Finally, you are absolutely right that the Conclusion is unhelpfully brief. This was an unfortunate mistake arising from last minute changes to meet the page limit. We will expand the conclusion, and suggest the following: “We have explored several directions in which the practical limitations of RCA can be addressed: first by avoiding estimation of conditional distributions in the setting that the causal graph is known, and second by avoiding needing the causal graph at all, in the setting that it is a polytree. To do so, we leverage information theoretic (IT) anomaly scores, and prove general laws about their typical decay along causal paths. Using our results, we then propose two novel algorithms: SMOOTH TRAVERSAL and SCORE ORDERING, give probabilistic guarantees for the correctness of their outputs, and show they have competitive performance in both synthetic and real-world data despite their simplicity. To our knowledge, our work is the only which provides guarantees for RCA in the non-linear setting from a single anomalous point without requiring knowing the full structural causal model.”

2. You are absolutely right that monotonicity is unrealistic in practical settings, and you have noticed how important it was to us to stress that this assumption is not required, hence the repeated statements throughout Section 3. We felt it was very unfortunate that we had to reserve the theory without the assumption for Appendix B. This was done because we worried that the theory would become more difficult to follow as all of the Lemmas and Theorems following the assumption must be stated more intricately, and the bounds presented become slightly less concise as the inequalities hold up to some small $\epsilon$. We accept your criticism nonetheless. We propose instead to move Lemma B.2 from Appendix B into the main text so as to explain why the inequalities hold up to some $\epsilon$, and subsequently state the results as they are currently presented but without monotonicity and using the slightly less concise inequalities. We will then continue to refer to the Appendix for the full detail for each Lemma and Theorem without monotonicity. This should be possible with the extra space afforded by the camera-ready version of the manuscript, should it be accepted, without significant loss of clarity.

3. You are right to raise the issue of robustness. To expand our evaluation to more real-world scenarios, we will in addition to the experiments we have already included using the PetShop dataset and the ProRCA package, we will evaluate each of the algorithms on the Sock-shop 2 dataset (Pham et al, 2024, Root Cause Analysis for Microservice System based on Causal Inference: How Far Are We?). We will also expand the synthetic experiments in two ways: first we will repeat the experiments, but restricting the causal graph to be polytree or a collider-free polytree (as currently in no experiment to impose this constraint) to see how performance may be affected when this assumption is met, second, we propose comparing the performance of each of the algorithms which depend on being given the causal graph (i.e. Traversal, Counterfactual, SMOOTH TRAVERSAL, and Circa) after introducing an increasing number of random edge additions/deletions/reversals to the graph they are given, simulating the case where the assumed graph does not perfectly match the true graph. This will not affect the performances of SCORE ORDERING and Cholesky which do not rely on the causal graph, but should allow us to test how robust SMOOTH TRAVERSAL is to misspecification of the graph compared to the other algorithms, and to assess at what point it is preferable to use a method which does not rely on the causal graph, such as SCORE ORDERING, compared to one that does. Finally, we will include an expanded discussion on when we expect our proposed algorithms to fail with a focus on guiding practical application. In particular, we will discuss what our theory shows about the difficulty of RCA in settings where the causal graph is very large (as note that both the bounds in Theorem 3.9 and Theorem 3.10 become weaker for larger $n$, though note as well that this challenge is not unique to our algorithms), and when the sample size for the normal period is low. Note that in Subsection 3.5 and Appendix D we discuss one particularly important case where the polytree assumption is violated and there is strong confounding, and why in practice it may not pose a significant problem. We will move some of the discussion from Appendix D into the main text as there we show that we expect SCORE ORDERING to fail only rarely when the polytree assumption is violated (at least in the linear setting).

Addressing questions

1. Please see our reply to point 1 in "Addressing weaknesses" above
2. Please see our reply to point 3 in "Addressing weaknesses" above
3. Please see our reply to point 1 "Addressing weaknesses" above

Addressing limitations

1. This is a very important point, I hope that you will feel that our reply to point 3 in "Addressing weaknesses" above already largely encompasses the issue you raise here. Nonetheless, let us provide some further information on two points. First, the polytree assumption: the polytree assumption is indeed restrictive ). In subsection 3.5 and Appendix D we give some justification for the application of our algorithms even in cases where this assumption is violated, and in all experiments we do not restrict the causal graph to be a polytree, and both of our algorithms show competitive performance. Note also that the only other Root Cause Analysis approach which operates in the setting we study (Li et al, 2025, “Root cause discovery via permutations and Cholesky decomposition”), the method we refer to as “Cholesky” in the Experiments section, assumes that the causal model is linear, while our approach does not. As such, we still believe that our work is an important contribution to the current state of root cause analysis research, despite this assumption. Regarding the single fault setting: if this is referring to our assumption that there is only a single root cause, in fact our theory readily generalises to the case where there are multiple. Olease see the detailed reply we gave to reviewer D5Fu above concerning this (and sorry for sending you to one of our replies to another reviewer, they raised the same point, and we are running out of characters!).

2. Thank you for raising the point of sample-complexity guidance. Given as low sample sizes in the normal period can pose issues for use of estimated IT anomaly scores in practice, it would certainly be worth providing some guidance on this. We propose including the following additional result in the appendix, with proof: if we use at least $k =\frac{3 e^{S_{\max}}}{\delta^2} \log\left(\frac{2n}{\alpha}\right)$ samples, then the estimated anomaly scores $\hat{S}(x_i)$ satisfy $P\left(|\hat{S}(x_i) - S(x_i)| < \delta \right) \quad \forall i \in \{1, \dots, n\}$ with probability at least $1 - \alpha$, where $S_{\max} := \max_i S(x_i)$, and $S(x_i)$ and $\hat{S}(x_i)$ are as defined in Equations 4 and 5 in the main text. The result follows from applying the (multiplicative form of) the Chernoff bound for small $\delta$, the full proof of which we will provide in the appendix.

Causal Graph Perturbation Validity

That is a good point, yes that would absolutely be the case. We propose the following outline approach to graph perturbations: generate a random “ground truth” DAG, introduce random edge additions/deletions/reversals subject to a given Structural Hamming Distance (SHD) constraint, check if acyclic (and if not, reject and repeat), evaluate each algorithm using the perturbed graph. The idea is to enforce acyclicity via rejection sampling, and to enforce how “big” the perturbation is by fixing the SHD from the ground truth graph (in practice this is simple as it need only count the number of random edge changes we introduce). This can then be repeated many times for several SHD values. This way we can precisely test how robust each of the methods are to increasingly large perturbations from ground truth. The SHD is convenient for quantifying perturbation size as it is the standard metric in the literature for evaluating the performance of causal discovery algorithms, and so our results should be directly comparable to those in the literature if one is choosing a causal discovery algorithm.

Application to Black-box Systems

This is a good question. You are right that causal graphs are often unavailable in practice, so a natural suggestion would be to perform causal discovery first. The first thing to note is that SMOOTH TRAVERSAL and SCORE ORDERING are closely related and follow from the same theoretical insights into anomaly propagation (Lemmas 3.2, 3.7, B.1 and B.2). In this sense, SCORE ORDERING is akin to a graph-free “version” of SMOOTH TRAVERSAL. So rather than introducing a potentially unreliable causal discovery step, our recommendation would be to use SCORE ORDERING when the causal graph is unknown.

That said, as your question on robustness importantly highlights, the situation is rarely binary. One may have a causal graph (e.g. from domain expertise) but not know whether it can be trusted, and in which case, not know which of our proposed algorithms should be used. The theory we present suggests a way to assess it: anomalies scores should propagate along edges and generally decay along causal paths, so if one observes many large score “jumps” from parent to child, or disconnected anomalies, this would suggest there are orientation errors in the given graph unless the “sparse mechanism shift hypothesis” (Schölkopf et al. 2021) is violated. SCORE ORDERING may then be preferable. We will certainly include a discussion of this point in the revised manuscript.

With this in mind, we don’t propose integrating a causal discovery step into our framework for three main reasons: one because of the above, two as we worry that doing so would limit its application by committing to a particular existing causal discovery algorithm, and three, relatedly to points one and two, existing causal discovery algorithms tend to be highly unreliable. Finally, while formal robustness guarantees would likely be challenging to obtain (we are not aware of any such results in existing RCA literature) we hope the newly proposed experiments will thoroughly address this empirically!

Addressing weaknesses

1. You are right, the polytree assumption is indeed restrictive (though note that it does not restrict nodes to having only a single parent, it rather means there are no undirected cycles, but you are right that for Theorem 3.9 we additionally assume only a single parent). In subsection 3.5 and Appendix D we give some justification for the application of our algorithms even in cases where this assumption is violated, and in all experiments we do not restrict the causal graph to be a polytree, and both of our algorithms show competitive performance. Note also that the only other root cause analysis approach which operates in the setting we study (Li et al, 2025, “Root cause discovery via permutations and Cholesky decomposition”), the method we refer to as “Cholesky” in the Experiments section, assumes that the causal model is linear, while our approach does not. As such, we still believe that our work is an important contribution to the current state of root cause analysis research. To better highlight are discussion of the polytree assumption, we will move some of the discussion from Appendix D into the main text as there we show that we expect SCORE ORDERING to fail only rarely when the polytree assumption is violated (at least in the linear setting).

2. This is a good observation. Generating challenging synthetic data that is both realistic, but whose simulation parameters are interpretable (so that we can study why and when our algorithms fail), is often a challenge, but note that we do see considerable performance differences between even the top performing algorithms when applied to real-world (and semi-synthetic) datasets in Appendix E. Nonetheless, we will expand the synthetic data experiments to address this shortcoming. In particular, we propose comparing the performance of each of the algorithms which depend on being given the causal graph (i.e. Traversal, Counterfactual, SMOOTH TRAVERSAL, and Circa) after introducing an increasing number of random edge additions/deletions/reversals to the graph they are given, simulating the case where the assumed graph does not perfectly match the true graph. This will not affect the performances of SCORE ORDERING and Cholesky which do not rely on the causal graph, but should allow us to test how robust SMOOTH TRAVERSAL is to misspecification of the graph compared to the other algorithms, and to assess at what point it is preferable to use a method which does not rely on the causal graph, such as SCORE ORDERING, compared to one that does.

3. Thank you for raising this point as it is of particular importance to our work. Budhathoki et al not only assumes that you know the causal graph, but assumes you know the full structural causal model. Such an assumption is extremely prohibitive as in practice the structural causal model cannot be estimated from either observational or interventional data. We will better emphasise the differences of our work from that of Budhathoki et al in the introduction. Note that we devote Appendix A to showing how our work relates to that of Budhathoki et al even though we do not need the structural causal model (or even the causal graph in the case of SCORE ORDERING).

Addressing questions

1. Please see answer to point 2 in "Addressing weaknesses" above
2. Please see answer to point 3 in "Addressing weaknesses" above
3. The estimator in Equation 5 corresponds to applying the $\tau$ feature map to each sample in the normal period, and to the single sample from the anomalous distribution, and counting the number of points which are equal or greater in the normal period, to the anomalous sample, followed by taking the negative logarithm. In other words, it is the negative log of the quantile with respect to the empirical distribution. We will include this additional description following Equation 5 in the text to aid with clarity.
4. This is a good question. Although we have focused on the case where there is only a single anomalous sample, as this is a more difficult setting, the theory we present is equally suitable in the setting where one has more than one anomalous sample. One must instead define multi-dimensional feature maps ($\tau$ in Equation 3), $\tau: \mathcal{X}^{m} \rightarrow \mathbb{R}$ where $m$ is the number of anomalous samples. In this case, in effect one treats the collection of anomalous samples as being a single multi-dimensional sample and so the subsequent theory is unchanged. The advantage in this setting is that an appropriately defined feature map can enable the detection of more general distribution changes than are possible from a single sample. For example, if the anomalous distribution for a variable were to reduce in variance, but be unchanged in mean, each individual sample drawn from it would not appear anomalous, but together multiple samples would have an “unusually” low variance, and so collectively the samples would receive a high anomaly score for an appropriately defined feature map. Alternatively, if one assumes that samples are drawn iid from the anomalous distribution, as is often assumed in RCA literature, then one can define joint anomaly scores (joint over the $m$ samples) for each variable, similarly to Equation 7 in subsection 3.2 (or in the arXiv version of Budhathoki et al, which you have cited above) by taking the convolution of the individual sample anomaly scores. Although defining a multi-dimensional feature map would be preferable, another option as a simple heuristic in practice could be to apply our algorithms to each sample individually, and then pick a variable as root cause according to a rule such as majority-vote.

Addressing weaknesses

1. You are right that we could do more to evaluate on a wider variety of real-world scenarios. To expand our evaluation to more real-world scenarios, we will in addition to the experiments we have already included using the PetShop dataset and the ProRCA package, we will evaluate each of the algorithms on the Sock-shop 2 dataset (Pham et al, 2024, “Root Cause Analysis for Microservice System based on Causal Inference: How Far Are We?”), and additional Top-1 and Top-3 recall performance tables in the Appendix.

2. We apologise for its omission upon submission. We would have shared it as part of our rebuttal if it were not this year’s changes to the rebuttal format. We will include a link to the source code should the paper be accepted.

Addressing detailed feedback

You raise an important point regarding our algorithms flagging up many potential root causes. This occurs due anomalies receiving tied anomaly score estimates, however, the issue actually stems not from too few samples in the anomalous period (but too few samples in the normal period), nor from anomaly scores being too low (in fact rather when anomalies are too strong). As noted on line 105 below Equation 5, the maximum (estimated) IT anomaly score that can be achieved in a sample of size k is $\log k$. This corresponds to the case where the sample being scored is more anomalous than any sample observed in the normal period. As such, a very strong anomaly at the root cause may not only receive the maximum anomaly score, but also cause anomalies in its descendants which also receive the maximum score (even if the caused events are considerably less rare) if the sample size in the normal period is too low. For example, if one has 1000 samples in the normal period, a 1/1000 anomaly event will receive the same (maximum) estimated score as an 1/10,000 event. Note that this is not an issue with the anomaly score itself, but with the estimates given by the estimator in Equation 5. For example, if one had a parametric estimate of the tail of the distribution, then tied score estimates would not occur. Tied score estimates are less of an issue in settings where many samples are available from the normal period, but are prohibitive in our real-world PetShop experiments wherein there are no more than ~600 normal period samples (and often far fewer due to missingness). Regarding low anomaly scores, note that we assume that we are performing root cause analysis due to a (sufficiently) large anomaly being detected at a target node. Such an anomaly could not be explained if all nodes received a low score. Finally, it is important to note that in noisy systems the problem is actually also less pronounced. In a highly deterministic system, anomalies will propagate (close to) perfectly from root cause to descendants, resulting in anomaly scores which decay slowly along paths. In more noisy systems, anomaly scores decay rapidly along paths, further reducing the risk of descendants receiving the maximum possible estimated score even if the root cause does. Interestingly then our results may be expected to actually perform better in larger, more noisy systems when more normal period data is available.

Addressing questions

1. This is an important point you are right to raise as although the single-sample setting is more challenging, and is the focus of the work, it is nonetheless true that in many settings one may have access to more than one sample. Note that we do compare our algorithms to RCD and epsilon-Diagnosis in Tables 1 and 2 on the PetShop data wherein all methods that require multiple anomalous samples are given access to between two and five samples in the anomalous period (depending on how many samples were missing in the dataset). However, we will extend the comparisons made using synthetic data to RCD and epsilon-diagnosis as you have suggested. It is important to note, however, that RCD is a conditional independence-based and as such performs poorly when the sample size in the anomalous period is too small. For example, Figure 2 in the supplementary material for the paper presenting RCD (Ikram et al, 2022, ​​Root Cause Analysis of Failures in Microservices through Causal Discovery) shows that in synthetic data the recall for RCD only becomes competitive (>0.7) once there are thousands of samples for the anomalous period, whereas both SCORE ORDERING and SMOOTH TRAVERSAL exceed this recall in our own experiments (Figure 1 of our paper) for only a single anomalous sample, but we agree a combined comparison with our own algorithms should certainly be done nonetheless.

2. This is certainly an important question, and as noted above, the issue is exacerbated in the PetShop dataset due to the relatively low sample size in the normal period (due to high missingness) and relatively strong anomalies at the root cause. Below is a table summarising the average number of nodes which receive the same maximum estimated IT anomaly score, therefore will all be flagged by SCORE ORDERING, split according to issue type in the PetShop dataset. Note that the PetShop graph contains 41 nodes. We will include this table in Appendix E alongside Table 3 and 4. The table reveals what a challenge tied maximum estimated scores are in the PetShop dataset.

Addressing weaknesses

1. Thank you for this suggestion, this is indeed an interesting question to address. It is worth noting that in all experiments presented in the manuscript (both synthetic and real-world), we do not constrain the causal graph to be a polytree and already both of our proposed algorithms have competitive performance. In particular, it will be difficult to detect any improvements in the performance of SMOOTH TRAVERSAL were we to constrain the causal graphs to be polytrees, however, it remains an open question as to how much SCORE ORDERING could benefit (and whether any benefit exceed that for the other algorithms against which we compare). We will therefore repeat the experiments in figure 1 for polytrees and collider-free polytrees and include two extra figures in the manuscript should it be accepted.

2. We agree this is definitely an interesting question! Please see the detailed reply we gave to reviewer D5Fu to their question three at the end of our reply to them as it concerns exactly the same question of how to generalise to the cases of multiple root causes (and apologies for sending you to look at our replies to other reviewers!)

Addressing questions

1. Thank you for raising this issue, we admit that it is often not clear which assumptions are required for which results. In the revised manuscript we will state next to each assumption exactly which Lemmas and Theorems rely on them. For the question of continuity in particular: we use continuity as a concise condition as it is sufficient to ensure conditional anomaly scores are statistically independent (Lemma 3.4). We need this for Theorem 3.6 later in the section and again for Theorem 3.8. However, continuity is not actually strictly necessary, more generally, any condition which would sufficient to ensure the conditional anomaly scores are statistical independent would do. We will clarify this in the text following the statement of the assumption.

Addressing weaknesses:

1. Thank you for raising this point. Let’s say a root cause analysis algorithm is sound if every variable it returns is a root cause, and say it is complete if every root cause among the input variables is returned. As our algorithms take marginal anomaly scores, which are only defined with respect to particular samples, it is not possible to define soundness/completeness independently of sample variation during the anomalous period. In this sense we cannot guarantee soundness/completeness. Literature on algorithms for causal discovery often define an oracle with respect to which soundness/completeness are defined in order to circumvent this caveat, but it is not clear what a suitable oracle would be in our setting. Nonetheless, Theorem 3.10 can be interpreted as a soundness result for SCORE ORDERING as it shows that if the largest anomaly score exceeds the next largest by a large amount, then the probability that the top-scoring variable is not the root cause is small—i.e. SCORE ORDERING is sound with high probability in this case. For SCORE ORDERING to be complete we would need to show that any root cause variable will have (with high probability) a larger score than non-root causes (as otherwise SCORE ORDERING will not return every root cause with high probability). As such, a priori we cannot expect completeness without further assumptions as in deterministic causal systems, anomalies are perfectly propagated, so downstream nodes will receive the same score as the root cause. To guarantee the anomaly score decays, we need to postulate constraints on the minimal noise level. For instance, for a linear Gaussian cause-effect relation, $X \to Y$, with Pearson correlation $\rho$, the $z^2$ score of $Y$ is with high probability close to $\rho^2$ times the $z^2$ of $X$, which can be translated into a decay of IT anomaly scores by recalibration. We are happy to include such model-dependent guarantees for score differences, but we currently have no idea for a concise general constraint on the noise level. For SMOOTH TRAVERSAL, we have shown (Lemma 3.7) that the score of a non-root cause is unlikely to exceed that of its parent by a large amount, i.e. if the score difference is large, SMOOTH TRAVERSAL is likely to be sound. Completeness would mean that every root cause exceeds the score of its parents by a large amount, which also requires additional assumptions. It is not obvious to find an assumption that does not trivially imply what is supposed to be shown.

2. Our apologies, you are quite right of course that the polytree assumption is not weak. Indeed on lines 282–283 we note that it is a strong assumption. Lines 56-58 were rather poorly phrased: the intention was to say that the assumptions on the anomaly scores are weak, first applied to cause-effect pairs and then to polytrees, but we accept that this was unintentionally misleading. We will remove the word “weak” and state explicitly that our results require so-called “information theoretic (IT)” anomaly scores as well as additional assumptions on them.

3. N is an independent noise variable, as in a structural causal model, and id is the identity function. We will alter the text to define both as suggested.

4. Thank you for raising this issue, we admit that it is often not clear which assumptions are required for which results. In the revised manuscript we will state next to each assumption exactly which Lemmas and Theorems rely on them. For the question of continuity in particular: yes we still use the continuity assumption for the results concerning marginal anomaly scores in subsection 3.3. This is because to obtain the bound on the p-value in Theorem 3.8, we need (in addition to Lemma 3.7) Theorem 3.6 which itself follows from Lemmas 3.4 and 3.5 under the assumption of continuity in the previous subsection. However, continuity is not strictly necessary: we use it as a concise condition as it is sufficient to ensure conditional anomaly scores are statistically independent (Lemma 3.4). More generally, any condition which is also sufficient would do. Note we do not use continuity in subsection 3.4 for the results concerning using marginal anomaly scores for SCORE ORDERING.

5. On line 248 the assumption in question is that we know the causal graph, stated in the previous sentence, but we agree this should be clarified: we will change the text accordingly.

6. Thank you for the recommendation, we agree that this would improve understanding of the paper. To illustrate the difference between conditional and marginal score we will introduce an example where we consider a linear Gaussian cause-effect pair. This is because in the linear Gaussian setting, marginal IT anomaly scores can be derived via re-calibrating $z^2$ scores on the variables themselves, while conditional scores are derived from $z^2$ scores of the regression residual. To illustrate the key graphical concepts, we will add an additional figure showing an example of a polytree, collider-free polytree and a DAG, and highlight their differences.

7. Thank you for raising this, you are right, the conclusion is unhelpfully brief. This was an unfortunate mistake arising from cutting text to meet the page limit. We will expand the conclusion, and suggest the following: “We have explored several directions in which the practical limitations of RCA can be addressed: first by avoiding estimation of conditional distributions in the setting that the causal graph is known, and second by avoiding needing the causal graph at all, in the setting that it is a polytree. To do so, we leverage information theoretic (IT) anomaly scores, and prove general laws about their typical decay along causal paths. Using our results, we then propose two novel algorithms: SMOOTH TRAVERSAL and SCORE ORDERING, give probabilistic guarantees for the correctness of their outputs, and show they have competitive performance in both synthetic and real-world data despite their simplicity. To our knowledge, our work is the only which provides guarantees for RCA in the non-linear setting from a single anomalous point without requiring knowing the full structural causal model.”

Addressing questions:

1. Estimating conditional anomaly scores is hard as it requires estimation of conditional probabilities, which is statistically ill-posed, as noted on lines 111-112 at the top of Section 3. We will clarify this point at the end of subsection 3.2 to motivate the approach followed in subsection 3.3.

2. We agree this is unclear. The inequalities are neither derived from structural properties nor are they assumptions, rather, when the inequalities hold, the root cause is the unique node which maximises the score difference with its parent from among the ancestors of the target node. The theorem then establishes a lower bound on the probability that the inequalities hold (and thus the root cause is correctly identified) subject to the structural assumptions on the DAG and the previously stated assumptions on the anomaly scores. We will rephrase the theorem to avoid confusion and suggest the following: “Let the causal DAG for $X_1,\dots,X_n$ be a collider-free polytree and node $j\in \{1,\dots,n\}$ be the unique root cause of the anomaly $x_n$, then the following inequalities hold with probability at least $1 - (n-1)\cdot e^{-\frac{1}{4}S(x_n)}$: $S(x_j) - S(pa_j) \geq S(x_n)/2$, $S(x_{i}) - S(pa_i) \leq S(x_n)/4 \forall i\neq j$, and hence root cause $j$ is the unique node that maximises the anomaly score difference with its parent.”

3. This is a very good question and we agree it’s important that we include a discussion as suggested. The results in subsection 3.4, concerning SCORE ORDERING, already apply to the case of having multiple root causes (i.e. more than one variable whose causal mechanism is corrupted for the single sample from the anomalous regime). This is because Theorem 3.10 is stated in terms of rejecting the hypothesis that none of the top-k highest scoring anomalies, as such, rejecting this hypothesis does not imply that there is only a single root cause among the top-k, but rather at least one. SCORE ORDERING therefore remains a suitable approach in this more general setting. We can say something similar concerning SMOOTH TRAVERSAL by slightly altering the null hypothesis given at the beginning of subsection 3.2 (lines 174-175). Instead of rejecting the hypothesis that all causal mechanisms worked as normal, except possibly the one for $X_j$, we can reject the hypothesis that all causal mechanisms worked as normal except for possibly $X_j$ and $X_l$. Following exactly the same steps as before in subsections 3.2 and 3.3 (i.e. defining the joint anomaly score but now excluding both $X_j$ and $X_l$ from $S_{\rm sum}$), we will arrive at a corresponding version of Theorem 3.8 wherein the bound on the likelihood is weakest if we infer the top two variables with the largest score difference from their parents as root causes. Similarly we could do the same for three root causes and so on. In other words, Theorem 3.8 justifies taking the top-k variables with the largest score differences from their parents whenever one suspects there are k root causes. The important caveat here is that while this approach for selecting k is suitable for small k, one incurs a larger multiple testing burden as k increases, and this would need to be accounted for. It would also be possible to adapt Theorem 3.9, but this is more intricate. In a similar spirit to SCORE ORDERING, when k is unknown, one could choose the minimum k for which the likelihood bound in Theorem 3.8 is now “acceptably” weak for some combination of k variables.

Thanks for the explanations. My concerns have been addressed. For weakness 1, I was initially expecting a result similar to Theorem 3.9, but for polytrees. Based on the authors' response, I now see that such a result may be difficult to establish without stronger assumptions about the causal model. That said, I agree it would be helpful to include some concrete examples illustrating when the proposed algorithms are guaranteed to be correct (such as the 2-node example mentioned by the authors) and when they can fail.

Based on the response, I have increased my score.