Structural Compactness as a Complementary Criterion for Explanation Quality

Mohammad Mahdi Mesgari; Jackie Ma; Wojciech Samek; Sebastian Lapuschkin; Leander Weber

cs.AIMar 31, 2026

Structural Compactness as a Complementary Criterion for Explanation Quality

Authors: Mohammad Mahdi Mesgari, Jackie Ma, Wojciech Samek, Sebastian Lapuschkin, Leander Weber

Organizations: Fraunhofer Heinrich Hertz Institute, Berlin, Germany · Technische Universität Berlin, Berlin, Germany · BIFOLD – Berlin Institute for the Foundations of Learning and Data, Berlin, Germany · Centre of eXplainable Artificial Intelligence, Technological University Dublin, Dublin, Ireland

Abstract

In the evaluation of attribution quality, the quantitative assessment of explanation legibility is particularly difficult, as it is influenced by varying shapes and internal organization of attributions not captured by simple statistics. To address this issue, we introduce Minimum Spanning Tree Compactness (MST-C), a graph-based structural metric that captures higher-order geometric properties of attributions, such as spread and cohesion. These components are combined into a single score that evaluates compactness, favoring attributions with salient points spread across a small area and spatially organized into few but cohesive clusters. We show that MST-C reliably distinguishes between explanation methods, exposes fundamental structural differences between models, and provides a robust, self-contained diagnostic for explanation compactness that complements existing notions of attribution complexity.

Figures & tables

Figure 1: Overview of MST-C workflow. Given a sample, a prediction (a) and different attributions (b) are obtained. (c) MST-C scores are derived from each attribution, by (1) converting it into a graph, (2) obtaining its MST preserving spatial structure (3) computing the MST length, (4) capturing attribution spread and cohesion , and (5) aggregating these properties into a final MST-C score.

Figure 2: Attribution heatmaps ( upper rows ) across XAI methods and models for a single sample, with corresponding MST graph visualizations (bottom row) highlighting structural differences. Refer to Figure A.1 in the appendix for additional examples.

XAI Method	Model	$\overline{\mathrm{\lx@glossaries@gls@link{acronym}{mstc}{{{}}MST-C}}}\uparrow$	$\overline{L_{T}}\downarrow$	$\overline{A_{\mathrm{hull}}}\downarrow$
GradCAM	ResNet	265.03 $\pm$ 48.33	10051.90 $\pm$ 3065.65	123.99 $\pm$ 46.45
GradCAM	VGG-16	197.82 $\pm$ 38.62	10129.17 $\pm$ 895.06	163.99 $\pm$ 30.03
Integrated Gradients	ResNet	116.03 $\pm$ 4.13	12463.19 $\pm$ 224.04	220.07 $\pm$ 0.99
	VGG-16	118.16 $\pm$ 7.12	12281.07 $\pm$ 397.23	219.67 $\pm$ 0.95
	SimCLR	119.22 $\pm$ 6.77	12364.08 $\pm$ 308.59	216.20 $\pm$ 1.13
SHAP	ResNet	116.31 $\pm$ 5.77	12469.56 $\pm$ 224.57	219.59 $\pm$ 0.98

Table 1: Comparison of MST-C and its main components across attribution methods and models. From left to right, we report the mean MST-C score (higher is better), mean MST length

L_{T}

(lower is better), and mean convex hull area

A_{\text{hull}}

(lower is better), together with the respective standard deviations, computed across 250 samples. For each XAI method, we underline the best values across models. For each model, we mark the best values across XAI methods in bold .

Figure 3: Correlation of MST-C with Sparseness, Complexity, and Effective Complexity across 250 samples, spanning different attribution methods and models. As shown, MST-C exhibits a strong positive correlation with Sparseness (up to 0.85 for LRP-

\varepsilon

z^{+}

- flat , on the SimCLR architecture) and negative correlations with Complexity and Effective Complexity.

Figure 4: Comparison of samples with similar complexity metric scores but divergent MST-C values on the SimCLR architecture. While the samples receive comparable evaluations under Complexity, Effective Complexity, and Sparsity, they differ substantially in MST-C . The dashed lines highlight pairs of samples that obtain similar scores under each complexity metric but exhibit noticeably different spatial structures. This indicates that MST-C can reveal nuanced structural (and visually meaningful) differences in attribution maps that are not captured by traditional complexity metrics.

Figure 5: Correlation of MST-C with RRA [ 1 ] ( left ) and ROAD [ 24 ] ( right ) across 250 samples, encompassing multiple attribution methods and models. As expected, no consistent correlation is observed between MST-C and metrics evaluating aspects of attribution correctness , such as localization ( RRA ) and faithfulness ROAD . In combination with results in Figure 3 , this underscores how MST-C captures aspects of attribution legibility , independent of attribution correctness.

Figure 6: Average MST-C scores for different choices of graph construction hyperparameter

k

. Scores are shown for several attribution methods for SimCLR ( left ), ResNet ( middle ), and VGG-16 ( right ), and avaraged across 250 samples.

k

is varied between

0

and

1500

. With a sufficiently large number of neighbors

k

, the MST-C scores stabilize, indicating convergence with respect to neighborhood size.

Figure 7: Number of connected components is shown in the left panel, averaged over 250 samples. For $k=500$ (illustrated as a black dashed line), all graphs form a single connected component. The right panel shows the runtime (seconds per iteration), which increases with $k$ , but remains reasonably fast at $k=500$ (approx. 2.5 seconds).

Figure 8: Sensitivity of MST-C ( top ) and its components ( bottom ) to threshold variation. The percentile-based threshold is varied between 10% and 90%. Especially at higher thresholds, MST-C scores are increasingly affected, with some variation in the size of this effect between attribution methods. Despite this, the ranking of attributions under MST-C remains relatively stable across thresholds.

Figure 9: Effect of bilinear interpolation for VGG-16 per attribution method ( left ) averaged over 250 samples. Effect of varying $k$ in the LRP- $\varepsilon$ - $z^{+}$ - $K\text{flat}$ composite ( right ), via example heatmaps and graph plots (top) and averaged MST-C scores (bottom) .

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 11 — Figure A.1: Additional examples, cf. Figure 2 .

Explainability Evaluation

Explainability evaluation tests whether AI explanations are faithful, stable, understandable, useful, and reliable across models and settings.

See all 321 papers

Measuring Explainer Stability via Attribution Separability
Aug 3, 2026Eddie Conti, Álvaro Parafita, Axel BrandoFeature Attribution Explanation Stability
Barcelona Supercomputing Center, Barcelona, Spain
From Mechanistic to Compositional Interpretability
May 9, 2026Ward Gauderis, Thomas Dooms, Steven T. Homer +2Mechanistic Interpretability Neural Network Interpretability
Vrije Universiteit Brussel, Brussels, Belgium · Independent · UK AI Security Institute, London, United Kingdom.
Not All Explanations Simulate Equally: Comparing Verbalized Feature Attributions and Self-Generated Rationales
May 31, 2026Pingjun Hong, Benjamin RothFeature Attribution LLM Interpretability
Faculty of Computer Science, University of Vienna, Vienna, Austria · UniVie Doctoral School Computer Science, University of Vienna, Vienna, Austria · Faculty of Philological and Cultural Studies, University of Vienna, Vienna, Austria

Aug 3, 2026J/K move · Enter open · S save

Measuring Explainer Stability via Attribution Separability

Eddie Conti, Álvaro Parafita, Axel Brando

Barcelona Supercomputing Center, Barcelona, Spain

Feature Attribution Explanation Stability Explainability Evaluation

Open paper AskPDF arXiv

Attribution methods (AMs) assign an importance score to each feature and are widely adopted to explain black-box models. However, most methods can produce variable attribution scores due to stochastic components in their definition. In this paper, we propose a distribution-based framework to capture the stability of attribution scores. In particular, our approach allows to understand the degree of separability in the ranked attribution vector and obtain the largest index for which a feature ranking remains reliable. We further extend this framework to compare AMs based on the robustness of their rankings across a dataset. Through experiments, we demonstrate how to apply our method to evaluate explainer stability. Overall, our approach provides a complementary criterion for evaluating the stability of AMs.

Abstract

Explainability Evaluation

Explore similar work

Measuring Explainer Stability via Attribution Separability

From Mechanistic to Compositional Interpretability

Not All Explanations Simulate Equally: Comparing Verbalized Feature Attributions and Self-Generated Rationales