TL;DR
This paper mathematically proves that "sufficient explanations"—subsets of input features that guarantee a specific prediction—are often impossible to achieve for structured data like graphs and text. By introducing the concept of co-bounds, the authors provide a framework to measure the intrinsic limits of explainability for any dataset, showing that for many real-world tasks, no explainer can ever be fully "sufficient."
What Problem Does This Paper Address?
In machine learning, we often want to know why a model made a specific prediction. A popular approach is to find a "sufficient explanation": a part of the input (like a functional group in a molecule or a phrase in a sentence) that, on its own, ensures the model's output remains the same.
While researchers have developed many "post-hoc" explainers to find these snippets, we haven't had a formal way to determine if a task allows for such explanations in the first place. Most existing theory focuses on simple, fixed-size data (like images of a set resolution). This paper tackles the more complex world of structured data—graphs and strings of varying sizes—where a "part" of one instance might also be a "part" of a completely different instance with a different label. The authors ask: Is the failure to find a perfect explanation a flaw in our algorithms, or is it an inherent property of the data itself?
Methods
The authors build a formal bridge between classifiers and explanation methods using three components:
- Instance Space ($X$): The set of all possible inputs (e.g., all possible molecules).
- Classifier ($f$): The model mapping inputs to labels.
- Select Relation ($\preceq$): A formal rule defining what can be chosen as an explanation. For example, in graph classification, an explanation might be restricted to being a "node-induced subgraph."
The core of their method is the discovery of co-bounds. A co-bound is an instance $x$ that can be "selected" from another instance $x'$ that has a different label.
The authors prove a fundamental theorem: A sufficient explainer exists if and only if there are no co-bounds in the task. They further extend this to "probabilistic sufficiency" (how likely a label is to stay the same under random perturbations) and "deletion sufficiency" (label stability when non-explanation parts are removed).
Datasets
The researchers evaluated their theory on ten diverse real-world datasets:
- Graphs: AIDS (antiviral activity), MCF-7 (anti-cancer), MUTAG & Mutagenicity (molecular properties), NCI1 (chemical compounds), ENZYMES, and PROTEINS.
- Strings: ToxinPred2 & ToxinPred3 (peptide toxicity) and SST-2 (sentiment analysis of text).
Key Insights and Ideas
- The "In-Distribution" Barrier: Unlike many explainability issues blamed on "out-of-distribution" data (where the model sees something it wasn't trained on), co-bounds represent a fundamental conflict within the data distribution. If "great" is a positive feature but appears in the negative phrase "not great," then "great" is a co-bound that prevents it from being a sufficient explanation for positive sentiment.
- Task-Level Limits: Sufficiency is not just a property of the explainer; it's a property of the task. The authors developed statistics like the Inter-class relation ratio ($\rho$) to quantify how "un-explainable" a dataset is before you even train a model.
- The ENZYMES Paradox: They found that even if only a few instances are co-bounds (2.2% in the ENZYMES dataset), the "ripple effect" can be massive. To make ENZYMES "co-bound free" (and thus perfectly explainable), you would have to relabel 82% of the instances.
- Selection Matters: Whether a sufficient explanation exists depends heavily on the "select relation." A task might be explainable if you only allow node-induced subgraphs but impossible if you allow any arbitrary subgraph.
Key Results
The empirical analysis (summarized in the table below) shows that perfect sufficiency is a myth for most structured data tasks.
- Ubiquity of Co-bounds: 9 out of 10 datasets contained co-bounds. In the SST-2 sentiment dataset, a staggering 21% of instances were co-bounds.
- Hard Upper Bounds: For the PROTEINS dataset, the authors calculated that the maximum achievable probabilistic sufficiency for certain instances is only 58%. No matter how good your explainer is, it cannot exceed this limit.
- MUTAG: 14% of instances are co-bounds, leading to a minimum accuracy loss of 23% if one were to force the dataset to be perfectly explainable.
Limitations and Future Work
The authors acknowledge that their work focuses specifically on sub-instance based explanations (selecting parts of the input). It does not yet cover other popular explanation styles, such as:
- Prototypes: Explaining by showing a similar example.
- Counterfactuals: Explaining by showing what would have to change to get a different result.
Future work involves extending this formal framework to these other modalities to create a truly unified theory of the limits of machine learning interpretability.
Summary updated