PaperlayerView exact revision on arXiv

Source-linked AI summary

Witnesses Explain Anomalies

Lamine Diop

arXiv:2609.03826v1cs.LGcs.AI

TL;DR

Unsupervised anomaly detectors often provide scores without explaining which features drive them, while post-hoc SHAP and LIME require repeated queries and approximate detector behavior. WAND builds explanations into directional scoring through witness vectors and differentiability, and across 47 ADBench datasets it achieves competitive detection with native explanations and lower query cost. Its guarantees concern probe budget rather than runtime, and its theory is most informative under the stated dimensional and tail assumptions.

  • Problem

    Dominant unsupervised anomaly detectors return scores without identifying responsible features, while SHAP and LIME provide approximate explanations through repeated detector queries.

  • Method

    WAND scores projected extremes against a sub-Gaussian baseline and uses the witness directions that flag points as native feature explanations, with gradients providing an additional attribution.

  • Results

    Across 47 ADBench datasets, WAND attains the best mean Friedman rank, with mean ROC-AUC 0.777 on the fair-comparison subset, while matching strong baselines and improving explanation quality at lower query cost.

  • Takeaways & Limitations

    WAND combines competitive unsupervised detection with built-in, faithful explanations rather than adding attribution as a separate black-box procedure.

  • Takeaways & Limitations

    Probe efficiency bounds directions rather than runtime, the worst-case guarantee weakens in high dimensions, and the theory assumes sub-Gaussian inliers.

Abstract

from arXiv · show

Unsupervised anomaly detection scores each point of an unlabelled, contaminated sample in a single pass, and increasingly must also explain why a point is flagged. Yet the dominant detectors give a score with no account of which features drive it, and explanations are bolted on post-hoc with SHAP or LIME, which re-query the detector thousands of times per point and only approximate it. We introduce WAND, an unsupervised tabular anomaly detector that is explainable by design. WAND organises its computation around directions on the unit sphere, scoring each point by how far its projection escapes a sub-Gaussian extreme-value baseline. The originality of our approach is that the witness directions that flag a point, being vectors in feature space, are its explanation, a per-feature attribution obtained at no cost over scoring and, since the score is differentiable, recoverable by gradients. Scoring is linear in the sample size, and a probe-efficiency bound guarantees every anomaly a witness, hence an explanation. Across 47 ADBench datasets WAND attains the best mean Friedman rank at ROC-AUC parity with 16 unsupervised baselines, so the gain is interpretability at no accuracy cost; its native explanations are more accurate and faithful than post-hoc SHAP/LIME and ECOD at a fraction of the query cost. WAND is thus a practical, interpretable solution for explainable anomaly detection.

I. INTRODUCTION

WAND addresses the gap between unsupervised anomaly scores and explanations by making feature attribution intrinsic to directional scoring. It combines witness-based interpretability with probe-efficiency and competitive detection across broad benchmarks.

  • Motivation and contribution: WAND scores contaminated, unlabelled tabular samples in one pass while exposing which features drive each flagged point.Existing detectors generally return scores without feature accounts, while SHAP and LIME approximate explanations through repeated detector queries.
  • Motivation and contribution: Witness directions on the unit sphere identify extreme projected points, and their feature-space coordinates directly provide per-feature explanations.The same explanations can also be recovered through gradients because the score is differentiable.
  • Guarantees: The number of required directions depends on anomaly count and depth margin rather than sample size, while scoring remains linear in the sample size.The guarantee bounds probe budget, not runtime, because each direction still scans the data.
  • Empirical evaluation: Across 47 ADBench datasets, WAND is competitive with sixteen unsupervised baselines and produces more accurate, faithful explanations at a fraction of post-hoc query cost.The study compares detection with classical and deep detectors and explanation quality with SHAP, LIME, and ECOD.
  • Positioning: WAND combines native witness attribution, differentiability, robust directional statistics, and anomaly-count-bounded probe efficiency within the shallow unsupervised setting.Its comparison profile distinguishes built-in exact attribution from axis-only explanations and identifies the shallow family as the comparison set.

B. Inlier Assumption

WAND assumes isotropic sub-Gaussian inlier tails and uses directional extreme-value exceedances to define anomalies. Its pipeline then supplements tail excess with spacing evidence, guarded probe pathways, seed averaging, and a differentiable score.

  • Inlier Assumption: The inlier distribution is centered and sub-Gaussian in every unit direction, an assumption satisfied by several bounded or light-tailed families.The stated assumption is not satisfied by power-law tails, although the paper reports empirical effectiveness under heavy tails.
  • Extreme-value baseline: A directional extreme-value envelope supplies the baseline against which projected observations are measured.In implementation, the theoretical envelope is replaced by an empirical-null quantile from a Gaussian copy.
  • Anomaly Definition: A τ-margin anomaly is a point exposed beyond the baseline by at least a directional margin, corresponding to separation from the inlier bulk in MAD units.The threshold is used theoretically, while the algorithm calibrates with an empirical null quantile.
  • Pipeline Overview: WAND processes each candidate direction through tail excess and a complementary k-spacings component for multimodal projections.The spacing component addresses cases where separated modes inflate MAD and hide a rare mode.
  • Pipeline Overview: Uniform-sphere and axis-aligned probes are scored separately, combined with a guarded additive rule, and averaged across independently seeded passes.The pathway split limits the influence of noisy axes, while seed averaging suppresses Monte Carlo variance.
  • Pipeline Overview: A soft-extreme surrogate makes the complete score differentiable in the data.This supports use inside larger trainable systems, although the paper primarily uses differentiability for explanations.

B. Per-Direction Tail-Excess

WAND’s per-direction statistic measures projected tail excess against a robust sub-Gaussian baseline, then adds spacing evidence when multimodality defeats MAD-based standardization.

  • Tail-excess statistic: For each unit direction, WAND projects the data and measures how far each projection exceeds a sub-Gaussian extreme-value baseline.The projection is centered and scaled using robust univariate statistics.
  • Robust calibration: Median/MAD scaling gives the directional statistic a 1/2 breakdown point, preventing a single outlier from inflating the scale.Under the inlier null, the directional excess is asymptotically negligible, whereas a sufficiently large excess signals a margin anomaly.
  • Failure mode: MAD-based tail excess can fail when projections contain multiple separated modes because the inter-mode gap inflates MAD.This failure can suppress the signal from a rare mode even when it is isolated.
  • Spacing component: Two-sided k-spacings identify points in sparse projected regions by comparing their local spacing with the median spacing.The method uses k = ⌈√n⌉ as the classical one-dimensional density-estimation choice.
  • Component combination: The tail-excess and spacing components are combined by a maximum so that evidence from either component is preserved.A small ε keeps the rescaling defined for degenerate projections and places both components on a common scale.
  • Direction sampling: WAND samples candidate directions uniformly on the unit sphere by default because adaptive sampling showed no measurable mean-AUC gain on ADBench.Uniform sampling retains the output-sensitive guarantee while providing the default probe strategy.

E. Split Pathway and Guarded Additive Mix

WAND protects directional scoring against complementary probe failures by combining uniform-sphere and axis pathways, then turns the resulting directional contributions into native feature explanations.

  • Pathway split: Random sphere probes can miss single-feature anomalies, so WAND adds axis-aligned probes while guarding against noise in either pathway.The two probe families are scored separately before additive mixing.
  • Guarded additive mix: Each pathway is normalized and combined with a guarded additive rule using a mixing weight λ.The implementation fixes λ = 1/4 after observing mean AUC flat within ±0.003 over λ ∈ [0.1, 0.5].
  • Implementation: The algorithm builds separate random and standard-basis probe pools, computes per-direction excesses, aggregates each pathway, and then mixes them.The reported score averages multiple seeded calls of the complete algorithm.
  • Computational profile: The method uses inner products, median/MAD, one-dimensional order statistics, and a Gaussian-copy bootstrap rather than densities, graphs, clusters, or whitening.These primitives support operation even when d ≥ n and provide per-direction and joint breakdown guarantees.
  • Directional witnesses: A point’s score is a weighted sum of directional excesses, so directions with large contributions already identify the feature combinations responsible for its anomaly.Witness contributions and dominant witnesses are defined from direction weights and pointwise excesses.
  • Feature attribution: Feature attribution decomposes each firing direction using |u_k,j| |x_i,j − m_j|, weighting feature deviations by how strongly directions fire.The deviation sign indicates whether each responsible feature is anomalously high or low, and the attribution requires no extra detector evaluations.
  • Gradient and coverage: Gradient attribution provides an independent explanation, and it agrees strongly with witness attribution with mean rank correlation 0.80 across ADBench.A probe-budget guarantee further ensures that every designed-to-be-exposed anomaly has a witness with high probability.

V. THEORETICAL ANALYSIS

The theoretical analysis bounds the spherical witness coverage of anomalies and derives a probe budget that exposes every anomaly with high probability. It also clarifies that this guarantee concerns probe count rather than runtime, with dimension limiting the bound’s usefulness.

  • The spherical-cap lemma lower-bounds the witness probability as pτ ≥ 1/2 (sin θτ)^(d−1).This is the probability that a uniformly sampled direction lies in an anomaly’s witness cone.
  • The displacement threshold is only a few σ for n around 10^6, while the witness-cone half-angle scales as Θ(τ/d).The shrinking half-angle explains why the theoretical coverage bound becomes loose as dimension increases.
  • Theorem 1 guarantees that uniformly sampled directions expose every anomaly with probability at least 1−δ.The guarantee depends on anomaly count k, margin τ, and dimension d through pτ, but not sample size n.
  • A union-bound argument yields K = (1/pτ) log(k/δ) probes to make the probability that any anomaly lacks a witness at most δ.Independence gives per-anomaly failure at most e^(−Kpτ), followed by a union bound over k anomalies.
  • The stated runtime is O(K · n (d + log n)), so output-sensitive probe efficiency alone provides no runtime advantage.A runtime benefit would require a sub-linear per-probe index; the theorem’s central value is instead its coverage guarantee and resulting explanation.
  • The worst-case probe bound is independent of n but grows with d for fixed τ, making it most informative in low-to-moderate dimensions.In high-dimensional datasets, the paper instead relies on empirical scaling with a fixed practical probe budget.

B. Consistency and Convergence Rate

The consistency analysis treats WAND’s score as a Monte Carlo estimate over random probe directions. It establishes a convergence rate for the unweighted estimator and extends the same rate, up to constants, to the implemented weighted aggregator under a conditioning event.

  • Estimator: The unweighted estimator averages τ(x, u_k) over K uniformly sampled directions to estimate the population mean score.The population target is s*(x) = E_u[τ(x, u)].
  • Weighted variant: The implemented weighted aggregator preserves the same Hoeffding-based convergence rate up to constants when at least one direction exceeds the null threshold.Its data-dependent weights lie in [0, 1] and sum to 1.

C. Differentiability

WAND uses differentiable relaxations for end-to-end learning while its exact algorithm supports the empirical results. Across 47 ADBench datasets, it achieves strong detection performance with a single default configuration and linear-in-sample-size scoring.

  • Differentiability: The exact algorithm uses non-smooth median, MAD, sorting, ranking, and maximum operations, while training replaces them with standard differentiable relaxations.The surrogate is continuously differentiable in X and converges to the exact score as temperature decreases.
  • Robustness: The breakdown proof establishes 1/(d+1) robustness for the uniform-sphere pathway, while the mixed axis-augmented estimator remains theoretically open.The fixed axis pathway is not affine-equivariant, so the composition argument does not extend directly.
  • Evaluation: 47 ADBench datasets are evaluated against 16 unsupervised baselines using a single CPU core, shared seeds, and no per-dataset tuning.WAND uses one default configuration with K = 1024, axis probes, λ = 1/4, α = 0.05, and S = 3.
  • Runtime: O(Knd) scoring is linear in n, and WAND scores all 47 datasets in approximately 1.7 minutes of single-CPU time in the batched path.Quadratic-cost baselines are skipped on n > 20,000 under the five-minute budget.
  • Sensitivity: +0.023 AUC is obtained by an oracle selecting one hyperparameter per dataset, raising mean AUC from 0.777 to 0.800.This diagnostic uses test-label access and is not an unsupervised comparator.

E. Probe Budget in Practice

WAND’s probe budget provides an accuracy–runtime trade-off while its witness directions yield native explanations. Experiments show accurate, faithful explanations at zero extra detector-query cost, including under oblique anomalies and heavy-tailed inliers.

  • Probe budget: K ≈ 4|H| marks AUC saturation on high-hull-complexity datasets, supporting a probe budget that tracks output complexity rather than n.WAND occupies the top-left of the AUC–runtime Pareto frontier on the shared subset.
  • Synthetic ground truth: 0.99/0.98 attribution-AUC makes WAND-gradient and WAND-witness strongest on axis anomalies, while WAND reaches 0.68 on oblique anomalies.ECOD reaches 0.97 on axis anomalies but its detection falls to AUC 0.53 on oblique anomalies, versus WAND’s 0.91.
  • Faithfulness: 0.63 mean faithfulness for witness explanations exceeds SHAP 0.52, LIME 0.34, and ECOD 0.29 across 33 ADBench datasets.WAND’s native mode is at least as faithful as SHAP on 29/33 datasets, and witness beats ECOD on 31/33.
  • Cost and coverage: Zero extra detector queries are required by native explanations, versus approximately 9.7 × 10^3 for SHAP and approximately 600 for LIME per point.The native modes agree with mean rank correlation 0.80, and the witness guarantee supplies an explanation for every τ-margin anomaly.
  • Heavy-tail robustness: At df=2, WAND reaches AUC 0.94 versus IForest 0.86 and ECOD 0.75; at Cauchy, it reaches 0.85 versus 0.79 and 0.68.Witness attribution-AUC remains ≥0.91, although formal guarantees are not claimed outside the sub-Gaussian regime.
  • Deep detectors: Mean ROC-AUC is 0.821 for WAND and VAE, compared with 0.790 for AutoEncoder, 0.798 for Deep SVDD, and 0.854 for IForest.The comparison uses a representative 16-dataset subset, and the deep baselines provide no native explanation.
  • Case study: AUC 1.0 is achieved on ANOCUB, where WAND uses named attributes and witness directions to explain bird-image anomalies.The case study compares flagged non-sparrow birds with a normal sparrow using concept-level rather than pixel-location explanations.
  • Interpretability: WAND combines detection and explanation in the same witness directions, making attribution free over scoring and recoverable by gradients.Its probe-count guarantee ensures every anomaly has a witness and therefore an explanation.

APPENDIX A DEFERRED PROOFS

The deferred proofs establish concentration and geometric coverage properties for WAND’s directional statistics. They bound sampled-score error and show how spherical caps expose sufficiently displaced anomalies.

  • Extreme-value bound: For a fixed direction u, projected observations remain sub-Gaussian with proxy variance bounded by σ^2, enabling a maximal sub-Gaussian bound on the projection extreme.The proof calibrates the extreme-value envelope using the projected sample under Assumption 1.
  • Robust calibration: Median and MAD consistently estimate projected location and scale with O_P(n^-1/2) error under the sub-Gaussian assumption.An ε-net over the sphere controls uniformity across directions, with residual terms depending on d and log n.
  • Geometric coverage: A displacement is exposed when a sampled direction lies within a spherical cap of angular radius θ_τ = Θ(τ/√d).The projected displacement then exceeds the extreme-value threshold by the required τ-margin in MAD units.
  • Sampled score: For each point, the sampled score s_K(x) averages K independent uniform-sphere directional excesses, while s*(x) is their expectation.The directional excess is bounded by M_n under Assumption 1.
  • Concentration: Hoeffding’s inequality gives P[|s_K(x)−s*(x)| > t] ≤ 2 exp(−2Kt^2/M_n^2) for the bounded directional excesses.A union bound over n points converts the per-point concentration result into a simultaneous control statement.

APPENDIX B EXTENDED TABLES

The extended experiments fix one default configuration across datasets and examine detection, explanations, embeddings, and metric robustness. WAND produces interpretable results on both tabular and image-derived tasks, with complementary concept- and pixel-level explanation modes.

  • A single default configuration is used in all experiments without per-dataset tuning.
  • Detection and explanation results are reported across 47 ADBench datasets, ANOCUB embeddings, and Breast Cancer Wisconsin.
  • AUC 1.0 ranks all 15 ANOCUB concept-space anomalies in the top 15, with 14/15 attributing most strongly to bill length.
  • AUC 0.99 is achieved for ANOCUB ResNet-18 embeddings, while a small hummingbird remains harder to separate from sparrow inliers.
  • AUC 0.933 is obtained on Breast Cancer Wisconsin, with attributions concentrating on recognised size, shape, and malignancy markers.
  • The AUPR/AP ranking mirrors the ROC-AUC ordering, indicating that the detector ordering is consistent across these metrics.

I. Scalability to large n

WAND’s scoring runtime grows linearly with sample size, while its probe guarantee is a budget rather than a sub-linear runtime guarantee. The appendix also identifies high-dimensional and protocol boundaries relevant to interpreting scalability and explanation coverage.

  • Scalability to large n: O(Knd) scoring is linear in n after one-time calibration, with independent rows enabling streaming and parallel execution.
  • Scalability to large n: Throughput remains flat in n: K=1024 processes 107 points in 164 s, while K=256 processes them in 47 s after 1.1 s calibration.
  • Scalability to large n: The probe-efficiency theorem bounds K independently of n, but each direction still requires a full data scan and the worst-case bound grows with dimension.
  • Scalability to large n: A fixed K=1024 works empirically through dimensions near 1.5k, although adaptive direction sampling showed no measurable mean-AUC gain over uniform draws.
  • Scalability to large n: The spacings component acts as a local switch through τi = max(τ mad, suτ spc), contributing only when its rescaled signal exceeds the MAD term.
  • Scalability to large n: The faithfulness study uses median replacement and does not sweep alternative imputations or feature-subset sizes.

APPENDIX D ADDITIONAL EXPERIMENTS (POST-ACCEPTANCE)

Additional experiments test native explanations for Isolation Forest, parameter robustness, and runtime–accuracy trade-offs. They show that native attribution quality is detector-specific, while WAND remains accurate across fixed parameter sweeps and shared benchmark subsets.

  • A. A native explanation baseline for a second detector: Isolation Forest native attribution is close to chance on synthetic ground truth and only marginally above random on real-data faithfulness.
  • A. A native explanation baseline for a second detector: Isolation Forest’s native explainer achieves attr-AUC 0.498/0.499 and mean faithfulness 0.031 under the reported protocols.
  • Parameter robustness: All four swept WAND knobs stay within 0.015 mean AUC across tested ranges, supporting the fixed default without per-dataset tuning.
  • Runtime and accuracy: WAND attains the best mean AUC among 17 methods on the shared 22-dataset subset in 0.220 s.
  • Runtime and accuracy: The fastest baseline within 0.02 AUC of WAND is Isolation Forest, which is only 1.6× faster; other methods are both slower and less accurate.
Loading 2609.03826v1…