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
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
\lx@glossaries@gls@linkacronymmstcMST−C↑
LT↓
Ahull↓
GradCAM
ResNet
265.03 ± 48.33
10051.90 ± 3065.65
123.99 ± 46.45
VGG-16
197.82 ± 38.62
10129.17 ± 895.06
163.99 ± 30.03
Integrated Gradients
ResNet
116.03 ± 4.13
12463.19 ± 224.04
220.07 ± 0.99
VGG-16
118.16 ± 7.12
12281.07 ± 397.23
219.67 ± 0.95
SimCLR
119.22 ± 6.77
12364.08 ± 308.59
216.20 ± 1.13
SHAP
ResNet
116.31 ± 5.77
12469.56 ± 224.57
219.59 ± 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 LT (lower is better), and mean convex hull area Ahull (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- ε - 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- ε - z+ - Kflat composite ( right ), via example heatmaps and graph plots (top) and averaged MST-C scores (bottom) .
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.
Mechanistic interpretability aims to explain neural model behaviour by reverse-engineering learned computational structure into human-understandable components. Without a formal framework, however, mechanistic explanations cannot be objectively verified, compared, or composed. We introduce compositional interpretability, a category-theoretic framework grounded in the principles of compositionality and minimum description length. Compositional interpretations are pairs of syntactic and semantic mappings that must commute to enforce consistency between a model's decomposition and its observed behaviour. We deconstruct explanation quality into measures of faithfulness and complexity to cast interpretability as a constrained optimisation problem, and introduce compressive refinement to systematically restructure models into simpler parts without altering their function. Finally, we derive a parsimony criterion under which syntactic compression theoretically guarantees more concise, human-aligned explanations. Our framework situates prominent mechanistic methods as subclasses of refinement, and clarifies why their compressibility heuristics tend to align with human interpretability. Our work provides a measurable, optimisable blueprint for automating the discovery and evaluation of mechanistic explanations.
Ward Gauderis, Thomas Dooms, Steven T. Homer +2
Vrije Universiteit Brussel, Brussels, Belgium · Independent · UK AI Security Institute, London, United Kingdom.
Natural-language explanations are often treated as a unified interface for understanding model behavior, but different explanation sources may support simulation in different ways. This paper compares two families of explanations for question answering models: verbalized feature attributions and self-generated rationales. We evaluate them under a shared counterfactual simulation setting, using an LLM judge as predictor and measuring whether it can better predict a model's answers to follow-up questions when given its explanation. Across multiple instruction-tuned models, we analyze how explanation source, verbalization strategy, and feature granularity affect the simulatability of explanations. Our results show that explanation format and granularity affect simulatability: attribution-based explanations and self-generated rationales differ in how much they improve counterfactual prediction, with effects that vary across models and formats.
Pingjun Hong, Benjamin Roth
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