Skip to main content
Back to timeline
arXivSource publication:

Sufficient explanations can be impossible: nine of ten classification datasets contain co-bounds that block any sufficient explainer

Synopsis

For structured inputs such as graphs and strings, post-hoc explainers often select part of the input as a sufficient explanation, meaning that part alone guarantees the prediction. A formal framework places what an explainer may select and the classifier side by side and shows that a sufficient explainer exists exactly when there is no co-bound, an instance selectable from a differently labeled instance. Across ten language, protein, peptide and molecular classification datasets, nine contain co-bounds; ENZYMES has only 2.2% of instances as co-bounds, yet removing them requires relabeling 82% of its instances.

Source-provided article image: On the Limits of Sufficient Explanations
arXiv

Interpretation

Whether sufficient explanations can exist depends on how the classifier and the select relation fit together, not only on how an explainer is designed; the select relation says which sub-structures an explainer may pick from each instance as an explanation. Earlier formal analyses concentrated on fixed-dimensional feature spaces and logical reasoning systems, and did not answer whether sufficient explainers exist on structured data such as graphs and strings. An instance that can be selected from a differently labeled instance forms a co-bound; a single co-bound rules out sufficiency even for the trivial explainer that returns the whole instance, so a sufficient explainer exists if and only if there is no co-bound.

Relaxing sufficiency to probabilistic sufficiency and deletion sufficiency leaves limits in place, though of a different form. Probabilistic sufficiency requires perturbations outside the explanation to leave the prediction unchanged, while deletion sufficiency only requires the prediction to survive removing everything outside the explanation, which is strictly weaker than sufficiency. Probabilistic sufficiency can be bounded away from one by an instance- and task-dependent constant, so every explainer falls at or below that bound; deletion sufficiency is always achievable, but on some tasks deletion-sufficient explanations carry no information about the classifier.

The distance from a task to admitting sufficient explanations can be computed from the dataset alone, without fixing a classifier or an explainer. Prior evaluations asked whether a given explainer is sufficient; these statistics give a task-level reference instead. On the ten datasets AIDS, MCF-7, MUTAG, Mutagenicity, NCI1, ENZYMES, PROTEINS, ToxinPred2, ToxinPred3 and SST-2, nine contain co-bounds and seven have them in every class; ENZYMES has only 2.2% of instances as co-bounds, yet removing them requires relabeling 82% of its instances, so the co-bound count alone can understate their effect.

Perspective

The analysis targets post-hoc explainers that use sub-instances as explanations, covering select relations such as subgraphs on graphs and substrings on strings; the statistics are computed on the ten datasets AIDS, MCF-7, MUTAG, Mutagenicity, NCI1, ENZYMES, PROTEINS, ToxinPred2, ToxinPred3 and SST-2, where ToxinPred2 contains no co-bounds and AIDS and ENZYMES have them only for some classes.

These limits are an in-distribution phenomenon, distinct from the out-of-distribution problems caused by perturbation; deletion sufficiency is always achievable but can be vacuous on some tasks. The framework does not cover similar-instance explainers, prototypes or counterfactuals, and analogous formal frameworks for other explainer types remain future work.