Cardinality-Minimal Explanations for Monotonic Neural Networks

1 Introduction

Deep Neural Networks have experienced unprecedented success in areas such as image analysis, NLP, speech recognition, and data science, with systems outperforming humans in a wide range of tasks [Krizhevsky et al., 2012; Hannun et al., 2014; LeCun et al., 2015; Schmidhuber, 2015; Silver et al., 2016]. As the use of neural models becomes widespread, however, task performance is no longer the only driver of system design, and criteria such as safety, fairness, and robustness have gained prominence in recent years [Kazim and Koshiyama, 2021]. Improving model interpretability is an important step towards fulfilling these criteria: if models can explain their predictions, it becomes easier to ensure that they are safe, fair and robust. This is, however, notoriously challenging, as neural models are 'black boxes' where predictions rely on complex numeric calculations.

A wealth of explanation methods have been proposed in recent years: attribution-based methods assign a score to input features quantifying their contribution to the prediction relative to a baseline [Sundararajan et al., 2017; Sundararajan and Najmi, 2020; Ancona et al., 2018]; example-based methods explain predictions by retrieving training examples that are most similar to the input [Koh and Liang, 2017;

Li et al., 2018]; and perturbation-based methods generate small corrections to the input causing the output to change [Zhang et al., 2018; Goyal et al., 2019; Lucic et al., 2022; Bajaj et al., 2021]. These methods, however, have been criticised for their lack of formal guarantees [Darwiche, 2020; Blanc et al., 2021; Marques-Silva, 2022], which handicaps their applicability to high-risk or safety-critical scenarios.

As a result, there is increasing interest in explanation methods providing rigorous formal guarantees [Darwiche, 2020; Marques-Silva, 2022; Cucala et al., 2022a; Ignatiev et al., 2019; Shih et al., 2018]. Rule-based methods generate explanations in the form of logic rules which are sufficient to derive a given prediction [Cucala et al., 2022a; Dhurandhar et al., 2018; Cucala et al., 2022b]. Abductive methods [Ignatiev et al., 2019; Shih et al., 2018; Barcel ´o et al., 2020] aim to compute 'Why?' explanations-minimal subsets of input features that are sufficient for deriving the prediction; dually, contrastive methods compute 'Why Not?' explanationsminimal subsets of input features so that some change in their value yields a change in the model's prediction. The formal guarantees provided by these methods are given by both the soundness requirement (i.e., the explanation is guaranteed to preserve or change the prediction) and the minimality requirement, where minimality can be understood in terms of set inclusion (subset-minimal explanations) or number of elements (cardinality-minimal explanations); the latter leads to smaller explanations in general since every cardinality-minimal explanation is also subset-minimal but not vice-versa. Furthermore, the size of cardinality-minimal explanations is also related to measures of robustness of neural predictions proposed in the literature [Shi et al., 2020].

Abductive and contrastive explanations can be formalised as explainability queries-Boolean questions that can be posed to a model and an input feature vector [Barcel´o et al., 2020]-, and the computational complexity of the corresponding decision problem for different types of models can be rigorously studied [W¨aldchen et al., 2021; Barcel´o et al., 2020]. In this paper, we focus on two explainability queries in the context of neural models [Barcel ´o et al., 2020]. The Minimum Change Required (MCR) query can be used to compute minimal contrastive explanations: given a model, an input vector x, and k ∈ N, the query is true if there exists an input vector y differing from x in at most k components and which yields a different prediction. Dually, the Minimum Sufficient Reason (MSR) query can be used to compute minimal abductive explanations, also called minimal prime-implicants [Shih et al., 2018]; given a model, an input vector x, and k ∈ N, the query is true if there is a subset y of the components of x of size at most k that suffices to obtain the current prediction (i.e., such that the prediction remains the same regardless of the values assigned to the components not in y).

Unfortunately, MCR and MSR are NP-complete and Σp2 - complete respectively, already for neural models with ReLU activations implementing a Boolean function [Barcel´o et al., 2020]. Although different techniques have been proposed to cope with intractability [Shi et al., 2020; Ignatiev et al., 2022; Izza and Marques-Silva, 2021], these complexity results may still constitute a challenge in practical scenarios.

A way to recover tractability is to focus on neural models implementing functions satisfying additional properties, such as monotonicity [Marques-Silva et al., 2021; Cano et al., 2019; Cucala et al., 2022a]; although this restricts the model's expressive power, the monotonicity assumption remains appropriate for a wide range of learning tasks. Furthermore, it was shown that subset-minimal abductive explanations can be computed in polynomial time if the model implements a monotonic real-valued function [Marques-Silva et al., 2021].

In this paper, we study cardinality-minimal abductive and contrastive explanations for monotonic neural architectures. We first show that MCR and MSR remain intractable for fully-connected neural networks implementing monotonic Boolean functions. Thus, although subset-minimal abductive and contrastive explanations can be computed in polynomial time [Marques-Silva et al., 2021], cardinality-minimal abductive or contrastive explanations cannot be efficiently computed under standard complexity assumptions.

Our hardness proofs, however, rely on neural models equipped with the step activation function. We then focus our attention on monotonic neural networks where the non-linear activations are continuous everywhere and differentiable almost everywhere (as is the case with most practical activations such as ReLU and sigmoid). We show that, in this setting, both cardinality-minimal contrastive explanations (and hence the MCR query) and abductive explanations (thus the MSR query) can be computed in polynomial time by means of a greedy algorithm. Our tractability results not only apply to models implementing Boolean functions, but also to more general settings involving real-valued functions. To show correctness of our greedy algorithms, we exploit the theoretical properties of the integrated gradients method [Sundararajan et al., 2017], thus establishing a connection between the theory of attribution methods developed by the ML community and the theory of abductive and contrastive explanations developed by the KR community. We note, however, that our algorithms do not rely on the application of attribution methods, but only on the ability to apply the model as a black box.

We conducted experiments on two partially monotonic datasets commonly used as benchmarks for designing monotonic and partially-monotonic models [Liu et al., 2020]: Blog Feedback Regression [Buza, 2014], a regression dataset with 276 features and Loan Defaulter 1 , a classification dataset with

1 https://www.kaggle.com/datasets/wordsforthewise/lending-

28 features. We trained monotonic FCNs to reach acceptable performance and we computed both contrastive and abductive explanations. The experiments showed that contrastive explanations are typically of small cardinality, whereas abductive explanations are typically larger, which is expected for a partially monotonic dataset. In both cases, the explanations could be efficiently computed.

2 Preliminaries and Background

In this section, we fix the notation used in the remainder of the paper and define the basic neural models that we consider. We also introduce attribution-based methods as well as the MCR and MSR explainability queries underpinning the theoretical analysis of contrastive and abductive explanations.

Notation. We let bold-face lowercase letters denote realvalued vectors. Given vector x, we use xi to denote its i-th component. Given x, x′ ∈ Rn and a subset S ⊆ {1, ..., n} of their components, we denote with xS|x′ the vector obtained from x by setting each component xi with i ∈ S to x′i . The complement x of a a Boolean vector x ∈ {0, 1}n is obtained from x by replacing each 0 with 1 and vice-versa. We denote with 0m the m-dimensional column null vector. We use boldface capital letters for matrices and denote the (i, j) component of a matrix M as Mi,j . Given function f : Rn ↦→ R, we denote with (∇f)i the ith component of its gradient.

Fully-ConnectedNetworks. A fully-connected neural network (FCN) with L ≥ 1 layers and input dimension n is a tuple N = ⟨{Wℓ }1≤ℓ≤L, {bℓ }1≤ℓ≤L, {σℓ }1≤ℓ≤L}, cls⟩. For each layer ℓ ∈ {1, . . . ,L}, the integer dℓ ∈ N is the width of layer ℓ and we require dL = 1 and define d0 = n; matrix Wℓ ∈ Rdℓ×dℓ-1 is a weight matrix; vector bℓ ∈ Rdℓ is a bias vector; σℓ : R ↦→ R is a polytime-computable activation function applied component-wise to vectors; and cls : R ↦→ {0, 1} a polytime-computable and monotonic classification function. The domain ∆ ⊆ Rn of N specifies the set of input feature vectors to which the network is applicable. The application of N to x ∈ ∆ generates a sequence x1 , . . . , xL of vectors defined as xℓ = σℓ (hℓ ), where x0 = x and hℓ = Wℓ · xℓ-1 + bℓ . The result N(x) of applying N to x is the scalar cls(xL). Thus, the neural network realises a function N : ∆ ↦→ {0, 1}. We denote with ˜N(x) := xL the output of the last layer (before classification). The monotonicity of function cls implies that there exists a prediction threshold t := infz∈R (cls(z) = 1), such that ˜N(x) > t implies N(x) = 1 and ˜N(x) < t implies N(x) = 0.

When σℓ is the rectified linear unit (ReLU) for each ℓ ∈ {1, . . . , L}, i.e. σℓ (x) = max(0, x), we say that N is a ReLU FCN. When σℓ is a step function for each ℓ ∈ {1, . . . , L}, i.e. σℓ (x) = 1 if x ≥ z and 0 otherwise for some z ∈ R, we say that N is a step-function FCN. A FCN N with domain ∆ is monotonic is it satisfies the following property: for all x, x′ ∈ ∆, if xi ≤ x′i for all i ∈ {1, ..., n}, then ˜N(x) ≤ ˜N(x′ ). Monotonicity is syntactically ensured by requiring that the weight matrices in all layers of the network are non-negative and that the activation functions in all layers are monotonic.

club AttributionMethods. Attribution methods [Sundararajan et al., 2017; Sundararajan and Najmi, 2020; Shapley, 1953] are a family of explanation techniques which, given as input function f : Rn ↦→ R, a vector x ∈ Rn and a baseline vector x′ ∈ Rn , assign a numerical score or contribution C f i (x, x′ ) to each component i ∈ {1, ..., n}. Attribution methods fulfil some (or all) of the following axioms for all functions Rn ↦→ R and vectors x, x′ ∈ Rn , components 1 ≤ i ≤ n and coefficients λ1, λ2 ∈ R: (i) Completeness: f(x) - f(x′ ) = ∑nj=1 C f j (x, x′ ); (ii) Zero-contribution: C f i (x, x′ ) = 0 whenever f(y) = f(y1, ..., yi-1, z, yi+1, ...yn) for each y ∈ Rn and each z ∈ R; (iii) Symmetry: C f i (x, x′ ) = C f j (x, x′ ) if xi = xj, x′i = x′j and f(y1, ..., yi, ..., yj, ...yn) = f(y1, ..., yj, ..., yi, ...yn) for each y ∈ Rn ; and (iv) Linearity: C λ1f1+λ2f2 i (x, x′ ) = λ1C f1 i (x, x′ ) +λ2C f2 i (x, x′ ).

Completeness ensures that contributions add up to the change in value of the function. Zero-contribution ensures that arguments not influencing the value of the function are assigned 0 as contribution. Symmetry ensures that arguments playing a symmetric role are assigned the same contribution. Finally, linearity ensures that contributions for a function expressed as a linear combination of other functions can be computed as a linear combination of their contributions.

A wide range of attribution-based methods has been proposed. The Shapley values method [Shapley, 1953] is one of the most popular thanks to its nice properties. Calculating Shapley values is, however, intractable, which has motivated research on approximations [Ancona et al., 2019]. Other popular attribution methods have been designed for neural networks; these include Layer-wise Relevance Propagation [Bach et al., 2015], DeepLIFT [Shrikumar et al., 2017], Deep Taylor decompositions [Montavon et al., 2017], and Saliency Maps [Simonyan et al., 2014; Adebayo et al., 2018; Dabkowski and Gal, 2017; Chang et al., 2017].

We will exploit the properties of Integrated Gradients [Sundararajan et al., 2017; Aumann and Shapley, 1974], which is applicable to continuous functions differentiable almost everywhere. The contribution of argument i of function f for input vector x and baselinex′ is defined as follows:

Integrated gradients is the only path-based attribution method satisfying all of the aforementioned axioms [Friedman, 2004]. Furthermore, it is well-suited for functions realised by neural networks, which typically satisfy its continuity and differentiability requirements.

Explainability queries and explanations. An explainability query is a Boolean question, formalised as a decision problem, that we ask about a model and an input vector.

Consider a domain ∆ ⊆ Rn . Given vector x ∈ ∆ and function f : ∆ ↦→ {0, 1}, a contrastive explanation is a subset S ⊆ {1, . . . , n} such that f(xS|y ) ̸= f(x) for some vector y ∈ ∆. The Minimum Change Required (MCR) query is to decide whether there exists a contrastive explanation for the given f and x of size at most a given number 1 ≤ k ≤ n.

Given e ∈ ∆ and f : ∆ ↦→ {0, 1}, an abductive explanation is a subset S ⊆ {1, . . . , n} such that f(eS|z ) = f(e) for all z ∈ ∆, where S = {1, . . . , n} \ S. The Minimum Sufficient Reason (MSR) query is to decide whether there exists an abductive explanation for the given function f and vector e of size at most a given number 1 ≤ k ≤ n.

A contrastive (respectively, abductive) explanation is cardinality-minimal if there exists no contrastive (respectively, abductive) explanation of smaller cardinality for the same function and input vector.

3 Intractability for Monotonic Networks

MCR is known to be NP-hard already for FCNs implementing a Boolean function and equipped with ReLU activations only and a threshold-based classification function [Barcel´o et al., 2020]. In turn, MSR is ΣP2 -hard for the same setting. A natural way to recover tractability is to focus on models implementing functions with specific properties, where monotonicity is a natural requirement in many applications.

It was shown in [Marques-Silva et al., 2021] that subsetminimal abductive explanations for any ML classifier implementing a monotonic function can be computed in polynomial time. This tractability result is encouraging as well as rather general: it makes no assumptions on the type and structure of the monotonic classifier, or on the domain (e.g., realvalued or Boolean) of the corresponding monotonic function.

The complexity of MCR and MSR in the monotonic setting, however, remains unclear. On the one hand, the algorithms in [Marques-Silva et al., 2021] cannot be used to compute cardinality-minimal explanations and thus their tractability results do not imply tractability of MCR and MSR. On the other hand, the neural networks used in the hardness proofs in [Barcel´o et al., 2020] are non-monotonic.

In this section we close this gap and show that, surprisingly, both MCR and MSR remain intractable in general for monotonic neural networks, already in the Boolean case.

Theorem 1. MCR is NP-complete for monotonic Boolean functions implemented by FCNs.

Proof. We show hardness by reduction from SET-COVER, which is the problem of checking, given as input m subsets E1, ...,Em of {1, ..., n} such that ⋃i∈{1,...,m} Ei = {1, ..., n} whether there exists S ⊆ {1, . . . ,m} of size at most K such that ⋃i∈S Ei = {1, ..., n}.

We map an instance E1, ..., Em,K of SET-COVER to an instance of MCR for monotonic Boolean functions implemented by FCNs by setting k = K, x = 0m, and N the 2-layer monotonic step-function FCN defined as given next.

In the first layer, W1 is a (n × m) matrix with values Wj,i = 1 if j ∈ Ei and 0 otherwise, b1 = 0n and the activation function σ1 is a step function σ1 (z) = 1 if z > 0 and 0 otherwise. In the second layer, W2 = 1n, b2 = 0, σ2 is the step function σ2 (z) = 1 if z ≥ n and 0 otherwise, and cls{0,1} is the identity. One can verify that N(x) = 0.

Assume there exists S ⊆ {1, ...,m} of cardinality at most k = K and y ∈ {0, 1}m satisfying N(xS|y ) ̸= N(x). We claim that, by construction of N, S is a solution to the corresponding SET-COVER instance. Given that N can only take values 0 and 1, we must have N(xS|y ) = 1, thus h2 ≥ n. This enforces that h1j > 0 for all j ∈ {1, ..., n}. By construction, for all j ∈ {1, ..., n}, there exists i ∈ S such that j ∈ Ei, and yi > 0. In particular, this gives us ⋃i∈S Ei = {1, ..., n}.

For the converse, let S be a solution to SET-COVER. We claim that S and vector y = 0m constitute a certificate for the constructed MCR instance. Indeed, ⋃i∈S Ei = {1, ..., n} thus for all j ∈ {1, ..., n}, there exists i ∈ S such that j ∈ Ei. Thus, with input xS|0m , h1j > 0 for all j ∈ {1, ..., n}. This yields h2 = n and hence N(xS|y ) = 1 ̸= N(x).

Membership in NP follows since S ⊆ {1, . . . ,m} of cardinality at most k and y ∈ {0, 1}m provide a certificate: (S, y) witnesses a solution of MCR for input N, x and k if N(xS|y ) ̸= N(x), which is polytime verifiable.

Theorem 2. MSR is NP-complete for monotonic Boolean functions implemented by FCNs.

Proof. We again show NP-hardness by reduction from SETCOVER. We map an instance E1, ..., Em, K of SET-COVER to an instance of MSR by setting k = K, e = 0m, and N the 2-layer monotonic step-function FCN described in the proof of Theorem 1. One can verify that N(e) = 1.

Assume there exists S ⊆ {1, ...,m} of cardinality at most k = K satisfying N(eS|z ) = N(e) for all z ∈ {0, 1}m. We claim that S is a solution to the corresponding SET-COVER instance. In particular, we have N(eS|0m ) = 1, thus h2 ≥ n. This enforces h1j > 0 for all j ∈ {1, ..., n}. By construction, for all j ∈ {1, ..., n}, there exists i ∈ S such that j ∈ Ei, which is equivalent to ⋃i∈S Ei = {1, ..., n}.

For the converse, let S be a solution to SET-COVER. We claim that S is a certificate for the constructed MSR instance. Indeed, ⋃i∈S Ei = {1, ..., n} thus for all j ∈ {1, ..., n}, there exists i ∈ S such that j ∈ Ei. Thus, with input eS|0m , h1j > 0 for all j ∈ {1, ..., n}. This yields h2 = n and hence N(eS|0m ) = 1 = N(e). By monotonicity, we thus have N(eS|z ) ≥ N(eS|0m ) = 1 for all z ∈ {0, 1}m.

Membership in NP follows since a set S ⊆ {1, . . . ,m} of cardinality at most k provides a certificate. Indeed, MSR is true if N(eS|0m ) = N(e) = 1, or N(eS|0m ) = N(e) = 0, which is verifiable in polynomial time.

Note that, although MSR remains intractable, monotonicity does bring its complexity down from the second level of the polynomial hierarchy to NP for Boolean functions.

4 Achieving Tractability of MCR andMSR

The hardness proofs in Section 3 rely on the use of the step activation function which, in contrast to the activations used in practice such as ReLU, is a discontinuous function.

In this section, we show that cardinality-minimal abductive and contrastive explanations become polytime computable (and hence MSR and MCR become tractable) if we additionally assume that the activations in the FCNs implementing the monotonic function of interest are continuous everywhere and differentiable almost everywhere; these are mild restrictions that are satisfied by most practical activation functions.

Definition 1. An activation function is admissible if it is continuous everywhere, differentiable almost everywhere, and non-decreasing.

Furthermore, our tractability results can be extended beyond the Boolean setting to real-valued functions over a bounded domain as defined next.

Definition 2. A domain ∆ ⊂ Rn is bounded if there exist lower and upper bound vectors l ∈ ∆ and u ∈ ∆ such that, for all x ∈ ∆ and each i ∈ {1, ..., n}, we have li ≤ xi ≤ ui.

Note that Boolean domains are bounded by the null vector of the relevant dimension and its complement.

4.1 Properties of Monotonic Networks with Admissible Activation

In the remainder of this section, we focus on FCNs where all activations are admissible and where monotonicity is ensured syntactically by requiring that weight matrices in all layers contain only non-negative weights. Let us therefore fix an arbitrary FCN N over a domain ∆ ⊆ Rn of dimension n satisfying these requirements, which we exploit in the formulation of our results; furthermore, assume that ∆ is bounded by a lower bound vector l and upper bound vector u.

The continuity and differentiability requirements of the activation functions ensure that the gradient of ˜N can be computed for each input feature vector x. In turn, as we show next, the monotonicity requirement ensures that each component of the gradient of ˜N (the output of the last layer) at x can be expressed as a sum where (1) the number of elements in the sum is fixed for N (i.e., it does not depend on x) and it is the same for all vector components; and (2) each element of the sum consists of a product involving a value that depends on x but which is always non-negative, and two coefficients that do not depend on x. This key property of the gradient allows us to exploit the theoretical properties of the integrated gradients attribution method. In particular, we can show that, by setting a component xi of the input vector x to the corresponding component of the lower or upper bound vector, depending on whether the prediction for x is 1 or 0, we are not altering the relative order of the integrated gradient attributions for the remaining components.

These properties, which are established by the following technical lemma, constitute the basis of our greedy algorithms for answering explainability queries.

Lemma 1. There exists an integer M ∈ Z≥0, positive coefficients {Am}1≤m≤M, and {Bi}1≤i≤n, and functions {gm}1≤m≤M from∆ to R≥0, such that the following identities are satisfied for each x, x′ ∈ ∆ and each i, j ∈ {1, ..., n}

Proof. We show (2) by induction on the number of layers L in ˜N. If L = 1, then ˜N = ⟨W, b, σ⟩ with W ∈ Rn , b ∈ R and σ : R ↦→ R. By the chain rule, (∇ ˜N)i(x) = Wi · (Dσ)(W· x+b), with Dσ the derivative of σ in Euler's notation. This is of the form (2) with M = 1, A1 = 1 ≥ 0, Bi = Wi, and g1(x) = (Dσ)(W · x + b). Monotonicity of σ ensures g1(x) ≥ 0 for any x.

For the inductive case, assume (2) holds for each network with L-1 layers satisfying the same requirements as N . The application of ˜N = ⟨{Wℓ }1≤ℓ≤L, {bℓ }1≤ℓ≤L, {σℓ }1≤ℓ≤L}⟩ with L layers to x is defined as σL(hL(x)). By the chain rule and the definition of hL we obtain the following identity:

Here, ˜N j is given by weight matrices {Wℓ }1≤ℓ≤L-2 and WL-1 j (representing the j-th row of WL-1 ), bias vectors {bℓ }1≤ℓ≤L-2 and bL-1 j (representing the j-th element of bL-1 ), and activations {σℓ }1≤ℓ≤L-1}. We apply the inductive hypothesis to compute the gradient for each 1 ≤ j ≤ dL - 1, which is (∇ ˜N j )i(x) = Bj i ∑Mj mj=1 Ajmj gjmj (x). But now, we can replace the value of the gradients in the sum of (4) with these values and show the statement of the lemma by instantiating (2) with M = ∑dL-1 j=1 Mj, Am = W L j Ajmj , Bi = Bj i and gm(x) = gjmj (x) · (DσL)(hL(x)). Again, by induction, Am ≥ 0 and gm(x) ≥ 0 for each m and x.

We now show (3). Let us consider the attribution for ˜N defined in (1). Assume i ̸= j (otherwise the equation holds trivially). By replacing the gradient in (1) with (2), the value of C ˜N i (x, x′ ) is Bi(xi -x′i ) ∑Mm=1 Am ∫ 1 0 gm(x′ + τ(xx′ ))dτ. Since integrated gradients satisfy the completeness and zero contribution axioms, we can compute the difference ˜N(x{i}|x′ ) - ˜N(x{j}|x′ ) as the sum of contributions C ˜N i (x{i}|x′ , x{j}|x′ ) and C ˜N j (x{i}|x′ , x{j}|x′ ) to obtain

The gradients (∇ ˜N)i(pij (τ)) and (∇ ˜N)j(pij (τ)) are provided by (2); when replaced in (5), they yield (3).

4.2 Algorithms for Computing Explanations

We are now ready to present our greedy algorithms for computing cardinality-minimal explanations in polynomial time.

Algorithm 1 takes as input a monotonic FCN N with admissible activation functions over a bounded domain ∆ with lower bound l and upper bound u, and an input feature vector x ∈ ∆, and computes a cardinality-minimal contrastive explanation as detailed next.

Algorithm 1 Computing contrastive explanations.

Input: vector x ∈ ∆ with ∆ bounded by vectors l, u, and monotonic FCN N : ∆ ↦→ {0, 1} with admissible activation functions.

Output: A cardinality-minimal contrastive explanation S for N and x

• 1: if N(x) = 1 then
• 2: x′ ← l
• 3: else
• 4: x′ ←u
• 5: end if
• 6: for 1 ≤ j ≤ n do
• 7: cj ← ˜N(x{j}|x′ )
• 8: end for
• 9: I ← list of indices obtained from sorting {cj}1≤j≤n in ascending (respectively, descending) order with ties broken arbitrarily if N(x) = 1 (respectively, if N(x) = 0).
• 10: S ← ∅
• 11: for 1 ≤ j ≤ n do
• 12: S ←S ∪ I[j]
• 13: if N(xS|x′ ) ̸= N(x) then return S
• 14: end for

The algorithm first applies the model N to the input vector x and, based on the obtained prediction, chooses to consider the domain's lower bound vector l (if N(x) = 1) or the upper bound vector u (if N(x) = 0) when searching for vectors that change the model's prediction. The monotonicity requirement will ensure that no other vectors need to be considered. Then, in each iteration of the first loop, the algorithm sets each individual input feature to the value of the relevant bound vector (while leaving the remaining components unchanged) and applies the input model to the resulting vector. The values obtained by each of these applications of the model are then sorted in ascending or descending order depending on the value of N(x). In the second loop, the algorithm successively assigns the components of x to the chosen bound vector in the order established in the previous step until the prediction changes. The algorithm then returns S consisting of all features that were set to the chosen bound.

Our algorithm is quadratic in the number of input features: both loops require linearly many applications of the FCN, and each application is feasible in linear time in the number of features [Goodfellow et al., 2016]. The algorithm's correctness relies on (3) in Lemma 1, which ensures that, when set to the chosen bound, each of the features selected by the algorithm in the second loop yields the largest change (amongst all other possible feature choices) in the application of the model, thus getting as close as possible to the prediction threshold. As a result, the output subset S is guaranteed to contain a smallest number of features.

Theorem 3. Algorithm 1 computes a cardinality-minimal contrastive explanation for the input N and x.

Proof. By symmetry of the algorithm, we can assume, without loss of generality that N(x) = 1. By monotonicity of cls, it suffices to show that, for each j ∈ {1, ..., n}, the choice of I[j] in the second loop yields the largest change in the evaluation of ˜N (the output of the last layer). That is, for each 1 ≤ j ≤ n and j ≤ k ≤ n we have ˜N(xS|x′ )- ˜N(x(S∪I[j])|x′ ) ≥ ˜N(xS|x′ ) - ˜N(x(S∪I[k])|x′ ). By construction of list I, the inequality ˜N(xI[j]|x′ ) - ˜N(xI[k]|x′ ) ≤ 0 holds for each 1 ≤ j ≤ k ≤ n. We apply (3) in Lemma 1 together with the fact that Am ≥ 0 and gm(x) ≥ 0 for each m and x (and hence ∫ 1 0 gm(pI[j] I[k] (τ))dτ ≥ 0) to obtain (BI[j](x′I[j] - xI[j]) -BI[k](x′I[k] - xI[k])) ≤ 0. Since {I[j], I[k]} ⊆ S, we have (xS|x′ )I[j] = xI[j] and (xS|x′ )I[k] = xI[k]. By applying (3) and the previous inequality, we finally obtain ˜N(x(S∪I[j])|x′ ) ≤ ˜N(x(S∪I[k])|x′ ). This ensures that the output S is a cardinality-minimal contrastive explanation for N and x, as required.

Contrastive and abductive explanations are dual to one another. Therefore, as we show next, a minor modification of Algorithm 1 that exchanges the roles of vectors x and x′ in the second loop can be used to compute cardinality-minimal abductive explanations.

Theorem 4. A modified version of Algorithm 1 where x and x′ are interchanged in Lines 7, 9 and 13 computes a cardinality-minimal abductive explanation for the given input N and x.

Proof. The proof is anlaogous to that of Theorem 3 in showing that the choice of I[j] in the second loop yields the largest change in the evaluation of ˜N, thus ensuring that S is a cardinality-minimal subset such that N(x′S|x ) ̸= N(x′ ). By the choice of x′ , we have ensured that N(x′ ) ̸= N(x), which gives us that N(xS|x′ ) = N(x). Furthermore, by monotonicity, N(xS|z ) = N(x) for all z ∈ ∆ if and only if N(xS|l ) = N(x) = 1 or N(xS|u ) = N(x) = 0. This ensures that S is a minimal abductive explanation.

Note that, although the correctness of our algorithms relies on the properties of integrated gradients, the algorithms themselves do not compute attribution values, and only rely on the ability to apply the input model as a 'black box'.

5 Discussion and Further Implications

The notion of cardinality-minimal contrastive explanation is closely related to existing notions of robustness for ML model predictions proposed in the literature. In particular, the minimality requirement ensures that no smaller subset of the features can be used to change the prediction for a given model N and input feature vector x; thus, the larger the size of the smallest contrastive explanation, the more robust the prediction of N on x is. The notion of D-robustness [Shi et al., 2020] is an instance-based robustness measure based precisely on this idea. The D-ROBUST query can be formalised as the complement of the MCR query: given N, x, and k, decide whether the size of a cardinality-minimal contrastive explanation for N and x is at least k. It was shown in [Shi et al.,

2020] that D-ROBUST is coNP-complete for Boolean functions. Thus, Theorem 1 in Section 3 refines the complexity lower bound in [Shi et al., 2020] to monotonic Boolean functions realised by FCNs with step activations. Furthermore, our results in Section 4.2 imply tractability of D-ROBUST for monotonic functions implemented by FCNs with admissible activations and bounded domains.

Our results also have interesting implications on the problem of constructing neural networks that exactly replicate a given function [Blum and Rivest, 1988; Judd, 1988; Jones, 1997; Kumar et al., 2019]. In particular, our results imply that, unless P = NP, there is no polynomial time algorithm that, given as input a monotonic FCN with step activations, constructs an FCN with admissible activations realising the same function. Indeed, otherwise we could solve in polynomial time the MCR query for monotonic FCNs with step functions by first rewriting the model using admissible activations and then applying our greedy algorithm to the transformed model.

6 Experiments

We have implemented our greedy algorithms for computing cardinality-minimal explanations in Section 4.2 and assessed their practical suitability on well-known benchmark datasets commonly used to evaluate monotonic models. To the best of our knowledge, our implementation is the only one available for computing cardinality-minimal explanations and hence we could not find a suitable benchmark for comparison. All experiments were conducted using Google Colab with GPU.

Datasets. The Blog Feedback Regression dataset [Buza, 2014] is a numeric dataset assembled from 37, 279 blog pages extracted from 1, 200 different sources. The objective is to predict the number of feedbacks that a blog page will receive in a given time window. The 276 features include the number of links and feedbacks in the past, time and day of publication, discriminative bag of words, etc.

Loan Defaulter is a numeric dataset assembled from LendingClub (a large online loan marketplace). The objective is to predict if the applicant will repay the loan or default. The 28 features include loans executed in the past, amount of the loan and instalments, applicant's address and zip code, etc.

The features in both datasets are preprocessed and bounded between 0 and 1.

Methodology. We trained monotonic FCN models on both datasets with PyTorch [Paszke et al., 2019] using the meansquared error loss for the Blog Feedback dataset and the binary cross entropy loss for the Loan Defaulter dataset. We trained the models with Adam [Kingma and Ba, 2014] for 10 epochs, setting all negative weights to 0 after each iteration of Adam to ensure monotonicity. We were able to reach a root mean-squared error (RMSE) of 0.175 on the test set for the Blog Feedback regression (an acceptable performance given that the state-of-the-art is at 0.158 [Liu et al., 2020]) and reached an accuracy of 60% on Loan Defaulter (state-of-the-art performance is 65.2%). Since the datasets are only partially-monotonic, we should not expect state-ofthe-art performance with a fully-monotonic model; please note, however, that the objective of our experiments is not to improve on the state-of-the-art regression and classification metrics, but rather to show that cardinality-minimal explanations for the trained models can be efficiently computed.

Using the trained monotonic FCNs, we then computed cardinality-minimal abductive and contrastive explanations using the greedy algorithms in Section 4.2. Note that, although the models for Blog Feedback are trained for regression, our algorithms can still seamlessly be applied provided that we introduce a threshold. Indeed, given a FCN N : ∆ ↦→ R, an input vector x ∈ ∆ and a numeric threshold t such that N(x) > t (respectively, ≤ t), Algorithm 1 can be used to compute a cardinality-minimal subset S such that N(xS|x′ ) ≤ t (respectively, > t) and a cardinality-minimal S such that N(xS|z ) > t (respectively, ≤ t) for all z ∈ ∆.

Results. For Loan Defaulter, contrastive explanations took 1.5s on average to compute and contained 1.8 out of 28 features on average; in turn, abductive explanations took 5s on average to compute and contained 27.6 features on average. Note that contrastive explanations were much smaller than abductive explanations; this is not unexpected in a partially monotonic dataset since the condition required from abductive explanations requires the prediction to hold for all possible values of the features outside the explanation (a very strong condition). Figure 1 depicts the cardinalities and computation times for both types of explanations.

For the Blog Feedback Regression dataset, we varied the threshold between the lower bound and the upper bound of the targets and computed the average cardinality and computation time with respect to the threshold for both types of explanations. For contrastive explanations, the cardinality remained constant equal to 1: it was always possible to modify one feature and change the prediction. In the plots of Figure 2, we focused on abductive explanations and instances x such that N(x) ≤ t and, as expected, we can see that the sizes of explanations decrease as the threshold increases.

7 Conclusion and FutureWork

In this paper, we have studied the problem of computing cardinality-minimal contrastive and abductive explanations for the predictions of monotonic neural models. We have strengthened existing intractability results [Barcel´o et al., 2020] to the context of monotonic fully-connected networks and proposed additional requirements to regain tractability.

Our results are of practical interest for the computation of explanations with formal guarantees in the context of monotonic or partially-monotonic tasks. Furthermore, from a theoretical perspective, our results not only strengthen existing intractability results, but to the best of our knowledge they also provide the first polytime algorithms for computing cardinality-minimal explanations in the context of neural models. Finally, our results also establish a novel connection between the theory of attribution methods and the theory of abductive and contrastive explanation methods, and have interesting implications for other related problems. We hope that our work will motivate further studies on the mathematical properties of explanation methods in Machine Learning.

Acknowledgments

This research was supported in whole or in part by the EPSRC projects OASIS (EP/S032347/1), ConCuR (EP/V050869/1) and UK FIRES (EP/S019111/1), the SIRIUS Centre for Scalable Data Access, and Samsung Research UK. For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission.