Technical Summary: Distribution-Free Root Cause Analysis (CROC)

1. Problem Formulation

The paper addresses the problem of root-cause analysis in multi-stream data. In this setting, an underlying system is monitored through $K$ independent data streams, each potentially undergoing a distributional change at an unknown time point. The goal is to identify the root-cause index $k^\star$, defined as the stream whose distribution changes earliest (i.e., $k^\star = \arg\min_{k \in [K]} \xi_k$, where $\xi_k$ is the changepoint time for stream $k$).

The framework operates under minimal assumptions:

1. Independence: Data streams are mutually independent.
2. Exchangeability: Within each stream, pre-change and post-change observations are sampled exchangeably from arbitrary, unknown distributions.
3. Constraint Set: The changepoint configuration $\xi$ belongs to a known constraint set $\mathcal{R} \subseteq [n]^K$ (e.g., allowing arbitrary configurations or enforcing synchronization).

The challenge lies in achieving finite-sample validity without relying on parametric models (e.g., Gaussian shifts) or strong structural assumptions about the data-generating process, which are often unreliable in practice.

2. Methodology: Conformal Root Cause Analysis (CROC)

The authors propose Conformal Root Cause Analysis (CROC), a framework that leverages conformal p-values to construct valid confidence sets for the root-cause index. The methodology extends the single-stream Conformal Changepoint Localization (CONCH) framework to the multi-stream setting.

Core Components

1. Hypothesis Testing Correspondence:
   The problem of constructing a confidence set for $k^\star$ is framed as testing null hypotheses $H_{0,k}$ for each candidate stream $k$. $H_{0,k}$ posits that stream $k$ is the root cause, implying the true changepoint configuration $\xi$ lies in the set $\mathcal{I}_k = \{t \in \mathcal{R} : t_k < t_j, \forall j \neq k\}$.

2. Changepoint Plausibility (CPP) Score:
   A scoring function $S(\mathbf{X}, t)$ is defined to quantify the plausibility that a specific changepoint configuration $t$ is the true one. The score is designed such that larger values indicate stronger evidence for $t$.

3. Split-Permutation Groups:
   For a candidate configuration $t$, a permutation group $\Pi_t$ is constructed. Elements of $\Pi_t$ permute observations within the pre-change and post-change segments of each stream independently but do not mix observations across these segments. Under the null hypothesis that $t$ is the true changepoint, the joint distribution of the data is invariant under permutations in $\Pi_t$.

4. Conformal P-Values:
   For each candidate $t$, a p-value $p_t$ is computed by comparing the observed score $S(\mathbf{X}, t)$ against scores obtained from permuting the data:
   $$p_t = \frac{1}{|\Pi_t|} \sum_{\pi \in \Pi_t} \mathbb{1}\{S(\pi(\mathbf{X}), t) \leq S(\mathbf{X}, t)\}$$
   To handle computational complexity, a Monte Carlo approximation is used.

5. Aggregation:
   To test $H_{0,k}$, the p-values for all configurations in $\mathcal{I}_k$ are aggregated using a maximum operator: $p^{(k)} = \max_{t \in \mathcal{I}_k} p_t$. The final confidence set is defined as:
   $$K_{1-\alpha}^{\text{CROC}} = \{k \in [K] : p^{(k)} > \alpha\}$$

Handling Dependence

While the primary framework assumes independent streams, the paper extends CROC to cross-stream dependence (Algorithm 2, CROC-dep). If streams can be partitioned into groups of mutually independent streams, the method computes group-level p-values and aggregates them via a Bonferroni correction, retaining validity while improving efficiency over naive aggregation.

3. Key Contributions

The paper establishes four primary theoretical and practical contributions:

1. Finite-Sample Validity:
   Theorem 3.1 proves that $K_{1-\alpha}^{\text{CROC}}$ is a valid distribution-free confidence set. For any $\alpha \in (0,1)$, the set contains the true root-cause index $k^\star$ with probability at least $1-\alpha$, provided only the exchangeability and independence assumptions hold. This holds for any choice of CPP score.

2. Universality Property:
   Theorem 4.1 demonstrates that CROC is a universal framework. Any distribution-free procedure for root-cause analysis can be represented as a specific instance of CROC with an appropriately chosen CPP score. This implies that CROC captures the entire class of distribution-free methods.

3. Optimal Score Design and Asymptotic Sharpness:
   The paper characterizes the optimal CPP score under an i.i.d. changepoint model (Theorem 5.2). The optimal score is a transformation of the log-likelihood ratio (LLR) comparing the likelihood of the data under the hypothesized changepoint configuration versus the true configuration.

   • Practical Implementation: Since the true distributions are unknown, the authors propose data-driven approximations (e.g., using learned densities or classifiers).
   • Asymptotic Sharpness: Theorem 5.3 shows that under mild regularity conditions (separation of changepoints, distinguishable distributions), the confidence sets constructed using the oracle LLR score become asymptotically sharp, isolating the true root cause with probability approaching $1-\alpha$.

4. Extension to Dependence:
   The paper provides a principled extension (CROC-dep) to handle structured cross-stream dependence, offering a trade-off between the conservatism of Bonferroni corrections and the efficiency of exploiting known independence structures.

4. Experimental Results

The authors validate CROC through extensive simulations:

• Gaussian Mean-Shift: In settings with varying signal strengths, CROC successfully isolates the root stream. Even when the root stream's signal is weaker than subsequent changes (a challenging regime), the method maintains valid coverage, adaptively widening the confidence set when necessary.
• Image Corruption (MNIST): Applied to a high-dimensional setting where images undergo blurring. CROC correctly identified the root stream despite subtle corruption signals and the use of a pre-trained CNN for scoring, demonstrating robustness in weak-signal, high-dimensional scenarios.
• Multi-Domain Sentiment: Using a sentiment analysis dataset across four domains, CROC successfully identified the domain where a sentiment shift first occurred, outperforming naive point-estimate approaches.
• Dependence Handling: Comparisons between the baseline CONCH-agg (naive aggregation) and CROC-dep show that leveraging known independence structures yields significantly sharper confidence sets while maintaining validity.

5. Significance and Claims

The paper claims that CROC provides a rigorous, distribution-free solution to root-cause analysis, addressing a gap in existing literature where methods often rely on parametric assumptions or lack finite-sample guarantees.

• Robustness: By requiring only exchangeability and independence, the method is applicable to diverse data types (images, text, sensor data) without needing to specify the underlying distribution.
• Theoretical Completeness: The universality result establishes CROC as the canonical framework for this problem class.
• Practical Utility: The ability to construct valid confidence sets that are asymptotically sharp allows practitioners to not only identify the root cause but also quantify the uncertainty of the identification, even in complex, high-dimensional, or weak-signal environments.

The authors conclude that while the framework extends to dependent streams, future work is needed to improve efficiency under structured dependence and to handle within-stream dependence.