Root Cause Analysis of Outliers with Missing Structural Knowledge (2025)

We next define an outlier score which we use in the next sections for our method and analysis.Let $g:\mathcal{X}\rightarrow\mathbb{R}$ be an appropriate feature map. This feature map can be any existing outlier score function mapping elements of $\mathcal{X}$ to real values, for example, z-score⁴⁴4The z-score of a sample $x$ is $z=\frac{x-\mu}{\sigma}$ where $\mu$ is the population mean, and $\sigma$ is the population standard deviation..Further, define the event

of being more extreme than the observed event $x_{n}$ according to the feature function $g$.From the point of view of statistical testing, $g$ can be seen as test statistics for the null hypothesis that $x_{n}$ is drawn from $P(X_{n})$, i.e., $H_{0}:x_{n}\sim P(X_{n})$, and $P(g(X_{n})\geq g(x_{n}))=P(E)$ is the corresponding p-value.Note that small $P(E)$ indicates that the null hypothesis is rejected with high confidence⁵⁵5This interpretation is certainly invalid in a standard anomaly detection scenario where Eq.3 is repeatedly computed for every observation in a sequence. However, so-called anytime p-values [40] are outside of our scope. and we rather assume that the usual mechanism generating samples from $P(X_{n})$ has been corrupted for that specific statistical unit.Sincesmall p-values correspond to strong anomalies,we define the anomaly score by

Since the logarithm of the probability of an event measures its ‘surprise’ in information theory [13, 15], as in[23], we call anomaly scores with the above calibration ‘IT scores’ for information theoretic. Given $k$ observations $x_{n}^{1},\dots,x^{k}_{n}$ from $P(X_{n})$, wewill often usethe following simple estimator

It is important to note that this value can be at most $\log k$. As a result, for the estimate $\hat{S}(x_{n})$, at least $e^{\hat{S}(x_{n})}$ data samples must have been used.

Now the contribution of a node $j$ given the context $\bar{{\mathcal{S}}}$ is defined as:

Let $\Pi:\mathcal{U}\rightarrow\mathcal{U}$ be the set of all possible permutations of the nodes and $\pi\in\Pi$ be any permutation. One then defines the contribution of a node $j$ given permutation $\pi$ as

where $I^{\pi>j}$ denotes the set of nodes that appear after $j$ with respect to $\pi$, i.e., $I^{\pi<j}=\left\{i\in\mathcal{U}\,|\,\pi_{i}<\pi_{j}\right\}$.One can easily see that for each permutation $\pi$, $S(x_{n})$ decomposes into the contributions of each node:

To symmetrize over all the possible permutations in $\Pi$, the Shapley contribution is calculated as:

which is certainly expensive to compute[23].Here, however, motivated by the fact that in most real-world scenarios there is a single corrupted factor causing anomalies,we try to find the unique node $j$ with a corrupted mechanism, or the unique root cause of the outlier $x_{n}$. As our first result, we show that in this scenario, it is unlikely that nodes other than $j$ get a significant value for their contribution. Note that this directly allows us to identify the root cause without the need for quantitatively finding the contribution of each and every node in the outlier value of the target variable $X_{n}$, which saves us exponential computations. In addition to the computational load, the symmetrization suffers from a more fundamental issue, namely that for most permutations $\pi$, the contributions $C^{\pi}(j)$ rely on structural equations (rung 3 causal information according to the ladder of causation in [35]), while some $C^{\pi}(.)$ rely only on the graphical model (rung 2), which we explain in the next sub-section.

Proposition 2.1

Whenever $\pi$ is a topological order of the causal DAG, i.e., there are no arrows$X_{i}\to X_{j}$ for $\pi(i)>\pi(j)$, allcontributions $C^{\pi}(j)$ can be computed from observational conditional distributions.

Let the causal DAG be $X\to Y$ for two variables $X,Y$, where we observe anomalies with anomaly scores $S(x),S(y)$ that occur together.We argue now that, the anomaly $x$ is implausible to be the unique root cause of the anomaly $y$ if $S(x)\ll S(y)$.This can be proven subject to the following assumptions:

1. 1.

   Monotonicity: increasing the anomaly score of $X$ does not decreasethe probability of an anomaly event at $Y$:

   $\displaystyle P\left\{S(Y)\geq S(y)|S(X)=S(x)\right\}\leq P\left\{S(Y)\geq S(y$

   (16)

2. 2.

   Injectivity: the mapping $x\mapsto S(x)$ is one-to-one. This is the case, for instance, for scores obtained from one-sided tail probabilities, that is for $g(x):=x$.

We then define two different null hypotheses stating that the mechanisms $P(X)$ or $P(Y|X)$, respectively, worked as usual: $H^{X}_{0}$:$x$ has been drawn from $P(X)$, and $H^{Y}_{0}$: $y$ has been drawn from $P(Y|X=x)$ (where $P(X,Y)$denotes the joint distribution of $X,Y$ in the normal mode).Note that $H^{Y}_{0}$ allows that $X$ is drawn from an arbitrary distribution instead of $P(X)$, only the mechanism generating $y$ from $x$ has remained the same. We then have the following criteria for rejecting $H_{0}^{X}$and $H_{0}^{Y}$:

Lemma 4.1 (rejecting $H^{X}_{0}$)

$H^{X}_{0}$ can be rejected at level $p\leq e^{-S(x)}$.

Lemma 4.2 (rejecting $H_{0}^{Y}$)

Subject to Monotonicity and Injectivity assumptions, $H^{Y}_{0}$ can be rejected at level $p\leq e^{-(S(y)-S(x))}$.

To inferwhich node in a DAG with $n$ nodes has been corrupted,we start with thehypothesis that all nodes except $j$ worked as expected:$H^{j}_{0}$: for the anomaly event $(x_{1},\dots,x_{n})$ all $x_{i}$ with $i\neq j$ have been drawn from$P(X_{i}|Pa_{i}=pa_{i})$.To define a test statistics,we first introduce theconditional outlier scoresfrom [45]:

where $g$ is some feature function as before (we actually allow variable-dependent feature functions $g_{i}$, but they need to coincide between conditional and unconditional outlier scores).With variable input $x_{i},pa_{i}$, they definerandom variables $S(X_{i}|Pa_{i})$.Further, we add the following assumption to Monotonicity and Injectivity from Subsection4.1:

• 3.

  Continuity:all variables $X_{i}$ are continuous with density w.r.t. the Lebesgue measure, and alsoall conditional distributions $P(X_{i}|Pa_{i}=pa_{i})$ have such a density.

This condition ensures that all the conditional outlier scores are distributed according to the density $p(s)=e^{-s}$, because then the cumulative distribution function is uniformly distributed.It entails a property that will be convenient for testing $H^{j}_{0}$:

Lemma 4.3 (independence of conditional outlier scores)

Subject to the continuity assumption,
$\left\{S(X_{1}|Pa_{1}),\cdots,S(X_{n}|Pa_{n})\right\}$ are independent random variables.

Independence of conditional scoresenables the definition of a simple test statistics that is obtained by summing over the individual ones⁸⁸8Note that this resembles known methods of aggregating p-values, but on a logarithmic scale [46]. together with a correction term. With the cumulative score: $S_{cum}:=\sum_{i\neq j}S(X_{i}|Pa_{i})$, we have that:

To understand Eq.17,note that the second term is needed to ‘recalibrate’ since the sumof independent IT scores is no longer an IT score, but with the extra term, it is. Intuitively, one may think of the extra term as a multi-hypothesis testing correction:the sum of independent IT scores is likely to be large because it is not unlikely that the set contains one large term. The following result states that this is quantitatively the right correction:

Lemma 4.4 (distribution of cumulated score)

If $H^{j}_{0}$ holds, Eq.17is distributed according tothe density $p(s)=e^{-s}$.

Theorem 4.5 (p value for $H^{j}_{0}$ from conditional outlier scores)