Introduction
As machine learning models grow in complexity, the need for interpretable explanations becomes paramount. One prominent approach in Explainable AI (XAI) is the use of anchors—small subsets of features that sufficiently explain a model's prediction. For a local explanation to be useful, it must be concise (small enough for human cognition) and have high coverage (applicable to many similar instances). However, finding the minimum anchor that satisfies these conditions is a significant computational challenge. This paper provides the first rigorous theoretical mapping of the computational landscape of the MINIMUM ANCHOR (MA) problem.
Problem Formulation and Parameters
The authors formalize the MA problem and analyze it through the lens of parameterized complexity. Rather than treating the problem as a monolithic "hard" task, they investigate how its difficulty scales with specific problem parameters:
- $k$: The size of the anchor (number of features).
- $c$: The required coverage (number of examples explained).
- $\delta_{max}$: The maximum number of feature differences between any two examples.
- Graph Width Parameters: The data is represented as an incidence graph, and its structural complexity is measured using metrics like rank-width ($rw$) and twin-width ($tww$).
The Complexity Landscape of Local Explanations
The core contribution of this work is the identification of the boundaries between tractability and intractability. The authors demonstrate that simply limiting the anchor size ($k$) is insufficient for efficiency; the problem remains W[2]-hard, meaning the computation time grows exponentially with the number of features even for small $k$.
As shown in Figure 1, the landscape is divided into three primary regions:
- Fixed-Parameter Tractable (FPT): Efficiently solvable when parameters like $k + \delta_{max}$ or rank-width ($rw$) are small.
- W[2]-hard in XP: Solvable in polynomial time only if the parameter is fixed, but the exponent depends on that parameter (e.g., for parameter $k$).
- paraNP-hard: Computationally impossible to solve efficiently even if the parameter (like $tww$ alone) is small.
Structural Parameters and Graph Width
A key insight of the paper is that the underlying structure of the data—not just the size of the explanation—determines complexity. By representing datasets as graphs, the authors leverage advanced graph theory to find tractable solutions. Specifically, they prove that if the data's incidence graph has low rank-width, a sophisticated dynamic programming algorithm can find the optimal anchor efficiently.
Figure 3 illustrates the hierarchy of these parameters. While powerful modern metrics like twin-width ($tww$) do not guarantee tractability on their own (rendering the problem paraNP-hard), combining $tww$ with a limit on anchor size ($k$) brings the problem back into the realm of solvability.
Key Findings and Implications
- Coverage is "Free": Interestingly, requiring an anchor to cover a specific number of examples ($c$) does not significantly increase computational difficulty compared to finding an anchor for a single instance.
- The Importance of Data Structure: The results suggest that XAI tools can be made more efficient by exploiting the inherent structural properties of the datasets they analyze, such as low rank-width.
- Theoretical Limits: The paper establishes "worst-case" performance limits, providing a roadmap for where heuristic-based XAI methods are likely to fail or succeed.
Conclusion and Future Work
This research provides a foundational theoretical framework for local explanations. While the current study treats machine learning models as black boxes, future work could investigate whether internal model structures (e.g., neural network architectures or decision trees) offer additional pathways to tractability. Furthermore, applying this rigorous parameterized analysis to other XAI methods, such as counterfactual explanations or SHAP values, remains an open and promising area of research.
Summary updated