Measuring Explainer Stability via Attribution Separability

Technical Summary: Measuring Explainer Stability via Attribution Separability

Problem Definition
Attribution Methods (AMs), or explainers, are widely used to interpret black-box models by assigning importance scores to input features. However, many popular AMs (e.g., SHAP, LIME, DiCE) incorporate stochastic components, such as Monte Carlo sampling or random perturbations. This stochasticity leads to variability in attribution scores across different execution runs, raising concerns regarding reproducibility and the reliability of the resulting feature rankings. While previous work has addressed stability through input-level perturbations (testing how explanations change when the input is slightly altered), this paper addresses a distinct challenge: quantifying the stability of the ranking itself derived from a single instance across multiple runs of the same explainer. The core research question is: given an ordered vector of feature importances produced by an AM, to what extent can we trust that the top-ranked features are truly more important than the subsequent ones?

Methodology
The authors propose a distribution-based framework to quantify the stability of feature rankings by analyzing the separability of attribution score distributions.

1. Distributional Modeling: Instead of treating attribution scores as deterministic values, the method models the score for each feature $i$ as a probability distribution $p_i$, estimated from multiple runs of the AM on a specific instance $x$.
2. Attribution Separability Metric: To measure the distinguishability between two features in the ranked list, the authors employ a distance metric $d(p, q)$ based on the continuous generalization of the Jaccard distance. This metric calculates the overlap between two distributions $p$ and $q$:
   $$d(p, q) = 1 - \frac{\int_{\text{supp}(p) \cap \text{supp}(q)} \min(p(x), q(x))dx}{\int_{\text{supp}(p) \cup \text{supp}(q)} \max(p(x), q(x))dx}$$
   A value of $d(p, q)$ close to 1 indicates high separability (low overlap), while a value close to 0 indicates significant overlap.
3. k-Stability Definition: The framework defines k-stability as the largest prefix length $k$ of the ranked feature list such that all consecutive pairs of features in the top-$k$ have a distributional distance $d(p_i, p_j)$ exceeding a user-defined threshold $l$. This identifies the point in the ranking where the ordering becomes unreliable due to overlapping distributions.
4. Comparative Framework: The method allows for the comparison of different AMs by calculating the proportion of instances in a dataset where one method achieves a higher $k$-stability than another.

Key Contributions

• Novel Stability Metric: The paper introduces a mathematically grounded approach to quantify the stability of AM rankings based on distributional analysis rather than input perturbations.
• Formal Validation: The authors prove that in an ideal case where an AM is perfectly faithful and stochasticity vanishes, the proposed distance metric converges to 1 (maximum separability). They further demonstrate empirically that the metric is sensitive to the degree of separation between feature importance values.
• Comparative Evaluation Tool: The framework provides a mechanism to compare the robustness of different explainers (LIME, SHAP, DiCE) across various models and datasets without claiming universal superiority for any single method.

Experimental Results
The authors evaluated the framework on four benchmark datasets (Diabetes, Heart Disease, Mobile, Churn) using Random Forest, SVM, Logistic Regression, and Decision Tree models.

• Separability Analysis: Experiments showed that SHAP generally produced near-deterministic attributions (separability value of 1) on simpler datasets, while LIME and DiCE exhibited more variability. In complex datasets, separability tended to decrease toward the "tail" of the ranking (less relevant features).
• k-Stability Comparisons: SHAP consistently demonstrated higher $k$-stability values compared to LIME, DiCE, and a random baseline (RAND) across most datasets and models. DiCE showed stability levels close to the random baseline in several cases.
• Run Sensitivity: The study found that the metric exhibits limited sensitivity to the number of runs for LIME, SHAP, and DiCE, suggesting reliable estimates can be obtained with a moderate number of executions (e.g., 15–30 runs), whereas the random baseline required more runs to stabilize.

Significance and Claims
The paper positions this work as a complementary criterion for evaluating AMs, focusing specifically on the reliability of the induced feature ranking. The authors explicitly state that their goal is not to declare one AM universally superior, acknowledging the "No Free Lunch Theorem" for explainability. Instead, they argue that stability is a prerequisite for user trust and the generalizability of insights.

The proposed method offers a principled way to determine the "point of diminishing returns" in a feature ranking—identifying how many top features can be trusted before the ordering becomes ambiguous due to stochastic noise. The authors note limitations, including the focus on tabular data and the necessity of selecting density estimation parameters and thresholds. They emphasize that low $k$-stability does not necessarily imply unfaithfulness to the model's decision process but rather indicates that the stochastic nature of the explainer makes the specific ordering of features unreliable. Thus, this metric should be used in conjunction with other evaluation dimensions like faithfulness and simplicity.