Do Feature Interactions Break Explainability? Provable Explanations for Any-Order Neural Additive Models
Abstract
Post-hoc explanation methods for neural networks are often heuristic and lack provable guarantees. A common alternative to such methods that was studied in recent years is to compute a cardinally-minimal subset of input features that is provably sufficient to determine the model's prediction. For general neural networks, however, finding such explanations is computationally intractable. In contrast, recent work showed that this problem becomes more tractable for a particular family of neural networks, namely neural additive models (NAMs), though standard NAMs are highly restrictive because they exclude feature interactions altogether. In this work, we study the computation of provably minimal and sufficient explanations for neural networks with restricted feature interactions, bridging the gap between fully general neural networks and purely additive models. We first prove that even with constant-order interactions, the problem is $Σ_2^P$-hard, implying that worst-case exponential complexity is unavoidable. We then identify two provably tractable settings: one based on sparsity in the interaction structure and another based on a stronger interaction-aware notion of sufficiency. Under either of these settings, we develop algorithms that compute provable explanations for neural networks with any-order interactions while retaining much of the computational efficiency of additive models. Empirically, we show that these explanations are significantly smaller and faster to obtain than those produced by standard algorithms, while being derived from models that achieve much higher accuracy than standard NAMs. Overall, our results help expand the class of neural networks that admit efficient provable explanations, while clarifying the fundamental role of feature interactions in shaping their complexity.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper provides a rigorous theoretical analysis of the complexity of provable explanations for neural additive models with interactions, proving $\Sigma_2^P$-hardness for constant-order interactions and identifying two tractable settings (strong sufficiency and sparse interaction graphs) that enable efficient computation of cardinally-minimal explanations.
Methodology
The paper introduces a rigorous theoretical framework for computing provably minimal sufficient explanations for Neural Additive Models (NAMs) with feature interactions (Any-Order NAMs). The methodology is sound and well-structured. It begins by establishing a sharp hardness result: proving that even constant-order interactions make the problem $\Sigma_2^P$-hard, which is a significant theoretical contribution that clarifies the boundary between tractable and intractable explanation problems. The authors then propose two distinct tractable settings: (1) a "strongly sufficient" explanation notion that decouples component interactions, allowing for linear-query complexity via MILP formulation, and (2) a sparse interaction graph setting where merging connected components allows the reuse of additive model algorithms. The use of neural network verification (CROWN) combined with MILP solvers is a standard but effective approach in this subfield. The theoretical proofs are detailed and appear correct, bridging the gap between the intractability of general DNNs and the tractability of pure additive models.
Results & evaluation
The experimental evaluation is solid, covering 9 standard benchmarks. The paper compares the proposed methods against greedy baselines (canonical and sensitivity-guided) and exact brute-force methods where feasible. The results demonstrate that the sparse setting yields significantly smaller explanations and faster runtimes than greedy baselines, while the strong-sufficiency setting offers competitive performance with stronger theoretical guarantees. The ablation study on interaction order (2, 3, 4) provides useful insights into scalability limits. However, the empirical gains, while statistically significant, are not transformative; the primary value lies in the theoretical guarantees rather than a massive leap in practical explanation quality or speed compared to state-of-the-art heuristic methods.
Reproducibility
The paper provides sufficient detail for reproducibility, including the specific verifiers used ($\alpha,\beta$-CROWN), the MILP solver (Gurobi), and the algorithmic steps. The appendices contain additional details on dataset splits and hyperparameters. The reliance on standard tools (CROWN, Gurobi) enhances reproducibility. However, the specific code implementation is not linked in the provided text, which is a minor drawback for immediate replication, though the algorithms are clearly specified.
Limitations
The primary limitation is the reliance on neural network verification, which does not scale to very large, deep, or dense networks. The method is restricted to Any-Order NAMs, which are a specific class of models; while the paper suggests a pipeline to fit such models to DNNs (SIAN), this adds an approximation step. The "strong sufficiency" notion, while tractable, is conservative and may not always yield the smallest possible explanations compared to the true optimum, though it is guaranteed to be sufficient.
Broader impact
This work contributes to the growing field of formal XAI, providing a clearer understanding of when and why provable explanations are computationally feasible. By identifying sparsity and specific sufficiency notions as key to tractability, it guides the design of future interpretable models. The hardness result is particularly impactful as it prevents researchers from expecting efficient exact explanations for arbitrary interaction structures, focusing effort on structured or sparse models. The paper provides a rigorous theoretical analysis of the complexity of provable explanations for neural additive models with interactions, proving $\Sigma_2^P$-hardness for constant-order interactions and identifying two tractable settings (strong sufficiency and sparse interaction graphs) that enable efficient computation of cardinally-minimal explanations.
Author of this paper? Send a correction.