Do Feature Interactions Break Explainability? Provable Explanations for Any-Order Neural Additive Models
Organizations: The Hebrew University of Jerusalem · Masaryk University
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 -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.
Figures & tables
| Dataset | Acc. | Size mean sd (%) (Ours / greedy / sens.) | Time mean sd (s) (Ours / greedy / sens.) |
|---|---|---|---|
| Adult | 0.8635 | 25.7 13.2 / 45.2 21.7 / 52.8 29.1 | 62.943 364.322 / 2199.624 1060.915 / 2267.351 1467.501 |
| Bike Sharing | 0.9232 | 33.5 17.8 / 36.3 19.6 / 44.5 15.7 | 61.279 314.891 / 1137.386 1351.496 / 2666.257 1261.087 |
| Breast Cancer | 0.9825 | 4.0 16.3 / 3.5 15.9 / 2.7 13.2 | 126.792 447.934 / 3082.496 402.879 / 3098.785 365.728 |
| California Housing | 0.8886 | 19.7 21.8 / 16.7 19.7 / 16.0 18.8 | 71.860 412.863 / 18.732 6.640 / 17.525 5.692 |
| COMPAS | 0.6742 | 50.6 23.7 / 50.3 10.1 / 39.9 12.0 | 26.411 113.220 / 2805.141 1357.731 / 1806.214 1535.080 |
| Diabetes | 0.7273 | 10.2 16.6 / 11.1 19.4 / 9.8 17.0 | 38.469 42.145 / 169.473 105.444 / 141.862 79.488 |
| Dataset | Acc. | Size mean sd (%) (Ours / greedy / sens.) | Time mean sd (s) (Ours / greedy / sens.) |
|---|---|---|---|
| Adult | 0.8647 | 19.5 16.0 / 25.7 18.3 / 23.7 18.8 | 866.652 1397.304 / 1070.071 994.654 / 1090.491 951.636 |
| Bike Sharing | 0.9163 | 23.5 13.7 / 29.1 18.1 / 32.7 17.0 | 242.984 580.558 / 582.489 1059.078 / 2215.734 1224.846 |
| Breast Cancer | 0.9825 | 1.6 7.7 / 2.4 11.0 / 1.7 8.0 | 46.244 78.272 / 171.785 102.700 / 166.080 97.569 |
| California Housing | 0.8777 | 15.7 18.5 / 16.9 19.9 / 15.8 18.6 | 49.813 201.815 / 9.818 2.837 / 9.802 2.841 |
| COMPAS | 0.6799 | 19.7 18.5 / 31.5 20.1 / 23.7 18.5 | 40.424 33.006 / 1334.135 1050.061 / 167.761 260.991 |
| Diabetes | 0.7273 | 8.8 14.2 / 11.6 18.7 / 9.7 15.3 | 68.908 63.193 / 78.631 58.277 / 59.267 40.367 |
Appendix figures & tables19 assets
Supplementary material from the paper’s appendix.
Appendix
| Setting | Ours | Greedy | Greedy Sensitivity |
|---|---|---|---|
| 29.1 14.4% / 130.5 54.8 / 61/61 | 27.1 10.3% / 2765.5 1121.9 / 48/61 | 34.2 7.5% / 3369.3 695.3 / 11/61 | |
| Whole admissible space | 61.2 10.5% / 303.0 453.1 / 60/61 | 53.5 8.8% / 2820.5 1223.1 / 51/61 | 53.5 7.5% / 3196.4 996.5 / 13/61 |
| Dataset | Model | Acc. | Size mean | Size med | Time mean (s) | Time med (s) |
|---|---|---|---|---|---|---|
| Bike Sharing | First-order | 0.8800 | 1.74 | 1.0 | 1.651 | 1.082 |
| Bike Sharing | Second-order | 0.9232 | 4.02 | 4.0 | 61.279 | 26.505 |
| Bike Sharing | Sparse second-order | 0.9163 | 2.82 | 3.0 | 242.984 | 118.560 |
| California Housing | First-order | 0.8619 | 1.22 | 1.0 | 5.786 | 1.767 |
| California Housing | Second-order | 0.8886 | 1.57 | 1.0 | 71.860 | 7.564 |
| California Housing | Sparse second-order | 0.8777 | 1.26 | 1.0 | 49.813 | 18.113 |
| Dataset | (gap, ) | |
|---|---|---|
| Adult | 6477 | 0.233 |
| Bike Sharing | 3017 | 0.057 |
| Breast Cancer | 105 | 0.138 |
| California Housing | 4070 | 0.360 |
| COMPAS | 357 | 0.787 |
| Diabetes | 154 | 0.055 |
| Order | Acc. | Size mean | Size med | Time mean (s) | Time med (s) |
|---|---|---|---|---|---|
| 2 | 0.9163 | 2.82 | 3.0 | 242.984 | 118.560 |
| 3 | 0.9180 | 2.90 | 3.0 | 913.630 | 634.051 |
| 4 | 0.9295 | 3.37 | 3.0 | 3500.879 | 3735.853 |
| Dataset (# features) | Ours | Brute force | MHS |
|---|---|---|---|
| Diabetes (8) | 0.82 1.33 / 29.0 / 154/154 | 0.62 1.13 / 41.0 / 154/154 | 4.81 3.52 / 3600.1 / 72/154 |
| California Housing (8) | 1.57 1.74 / 7.6 / 4070/4125 | 1.26 1.49 / 6.5 / 4128/4128 | 1.17 1.41 / 324.9 / 4128/4128 |
| German Credit (20) | 12.99 2.85 / 110.3 / 199/200 | n/a / n/a / 0/200 | 18.85 3.40 / 3607.2 / 23/200 |
| Heart Disease (13) | 3.79 1.87 / 116.8 / 61/61 | 2.07 0.27 / 2783.6 / 14/61 | 11.77 3.32 / 3603.1 / 8/61 |
| Dataset | DNN acc. | SIAN acc. | Order | Size mean sd (%) / Runtime mean sd (s) | |
|---|---|---|---|---|---|
| Diabetes | 0.7532 | 0.7273 | 4 | 4 | 8.4 15.0 / 66.1 63.7 |
| Heart Disease | 0.8689 | 0.8361 | 3 | 3 | 16.5 12.8 / 59.3 40.6 |
Neural Network Interpretability
Neural network interpretability studies how models represent information and make predictions, and how to explain, test, or control their internal computations.
See all 361 papers