{'fraction_non_alphanumeric': 0.028762002820243077, 'fraction_numerical': 0.00552857174832688, 'mean_word_length': 4.778323848939472, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Attributions Beyond Neural Networks: The Linear Program Case

Linear Programs (LPs) have been one of the building blocks in machine learning and have championed recent strides in differentiable optimizers for learning systems. While there exist solvers for even high-dimensional LPs, understanding said high-dimensional solutions poses an orthogonal and unresolved problem. We introduce an approach where we consider neural encodings for LPs that justify the application of attribution methods from explainable artificial intelligence (XAI) designed for neural learning systems. The several encoding functions we propose take into account aspects such as feasibility of the decision space, the cost attached to each input, or the distance to special points of interest. We investigate the mathematical consequences of several XAI methods on said neural LP encodings. We empirically show that the attribution methods Saliency and LIME reveal indistinguishable results up to perturbation levels, and we propose the property of Directedness as the main discriminative criterion between Saliency and LIME on one hand, and a perturbation-based Feature Permutation approach on the other hand. Directedness indicates whether an attribution method gives feature attributions with respect to an increase of that feature. We further notice the baseline selection problem beyond the classical computer vision setting for Integrated Gradients.


Introduction: Explaining an LP
With the great rise in popularity of Deep Learning in recent years which was corroborated by its tremendous success in various applications [Krizhevsky et al., 2012, Mnih et al., 2013, Vaswani et al., 2017, the popularity of methods which help to understand such models has increased as well [Sundararajan et al., 2017, Selvaraju et al., 2017, Hesse et al., 2021. The latter works constitute a new sub-field within artificial intelligence (AI) research often referred to as explainable AI (XAI). While XAI has tried a vast variety of methods and techniques to unravel the "blackbox" of deep learning models, many restrictions can be found when it comes to the notion of explainability or interpretability that is expected and sought [Stammer et al., 2021]. To therefore move beyond simple "heat-map" type of attributions, explainable interactive learning research (XIL; see for instance Teso et al.Teso and Kersting [2019]) poses one such alternative. In this work, however, we move "beyond" classical attribution in the sense that we consider alternate models instead of alternate data streams or alternate definitions. That is, we consider Linear Programs (LP). While there has been considerable progress in increasing the understanding of neural networks (NNs), the complexity of deep models has received significant attention from the field of XAI, even though other fields might benefit from such techniques as well-for example LPs from mathematical optimization.
Interestingly, LPs are-at first glance-on the opposite spectrum of model complexity, they give the impression of being "whitebox". Representing problems with linear constraints and relationships, LPs can be useful and in fact are used for a multitude of real world problems and there exist many solvers capable of solving even high-dimensional LPs. It is even possible to use, solve, and backpropagate through LPs in a NN Paulus et al. [2021], Ferber et al. [2020]. While such a solver can be used to calculate the optimal solution of a LP, some applications could benefit from an increased understandability of their underlying LPs. If LPs were to be "properly explainable", such that this refers to an intuitive, human level understanding, then this would have incredible implications for science and industry (well beyond AI research). For instance, energy systems researcher could design sustainable infrastructure to cover long-term energy demand [Schaber et al., 2012]. Also, LP explainability naturally comes with strong implications within AI research, for instance in quantifying uncertainty and probabilistic reasoning as in MAP inference [Weiss et al., 2007].  Figure 1: Schematized overview. For the first time, we apply XAI to LPs. To justify said application, we first propose an encoding φ of the initial LP which is then being used for learning a NN. Subsequently, said NN is analyzed using XAI.
(Best viewed in color.) To facilitate such understanding, we propose to combine the field of XAI and LPs with the goal of utilizing the methods from XAI in order to increase the understanding of LPs. Figure 1 illustrates our basic approach. Given an LP, we use an encoding function φ to create data based on that LP which is then used to train a NN. In the second step, we use common XAI methods mostly designed for use in Deep Learning to analyze the so trained NN. Our work sets itself apart from previous work on sensitivity analysis Bazaraa et al. [2008] or infeasibility analysis Chinneck [2007] by considering properties beyond feasibility and enabling the use of XAI methods on linear programs.
Overall, we make the following contributions: (1) We introduce an encoding function which distinguishes feasible from infeasible instances, a function which includes the cost of LP solutions, two functions focusing on the constraints, and a function using the LP vertices.
(2) We look at the attribution methods and compare them depending on these encodings. (3) We once again explain the importance of the selection of an appropriate baseline for IG. (4) We show similarities between Saliency and LIME and we propose the property of Directedness as the main discriminative criterion between Saliency and LIME on one hand, and our Feature Permutation approach on the other hand.
We make our code publicaly available at: https://cutt.ly/gHE0Nkx 2 Background and Related Work Optimization Using Linear Program. A linear program (LP) consists of a cost vector c ∈ R n and a number of inequality constraints specified by A ∈ R m×n and b ∈ R m . The objective of an LP is to find a point (or instance) x ∈ R n which minimizes the cost c T x, is non-negative (x ≥ 0), and does not violate the constraints specified by A and b in the form of Ax ≤ b. In short, given c, A, b find an instance x such that c T x is minimal, subject to Ax ≤ b and x ≥ 0.
There can either be no solution, one solution or infinitely many solutions [Hoffman et al., 1953]. The minimization task is the objective function and can also be written as a maximization task of the negative cost (i.e. maximizing the gain instead of minimizing the cost). In this paper, unless stated otherwise, when talking about the constraints we refer to Ax ≤ b and not x ≥ 0. When referring to a certain number of constraints in a specific LP, we refer to such a number of rows in A and corresponding elements b.
Attribution Methods from XAI. We follow the standard notion defined in Sundararajan et al. [2017]: Definition 1 Let F : R n → R be a NN and x = (x 1 , . . . , x n ) ∈ R n denote an input. Then we call A F (x) = (a 1 , . . . , a n ) ∈ R n attribution where a i is the contribution of x i for prediction F (x).
Therefore, the attribution A F (x) for the instance x consists of one attribution value for each feature of x. Such an attribution value a i for the i-th feature describes the contribution of that feature for the output. How exactly this contribution should be understood depends on the attribution method.
The attribution methods here were chosen with the aim of enabling a comparison of different approaches. "Captum" was used to apply these methods [Kokhlikyan et al., 2020]. Subsequently, we briefly cover each of the attribution methods relevant in this works analysis.
Integrated Gradients Sundararajan et al. [2017] proposed an attribution method for deep networks which calculates attribution relative to a baseline. Formally, we are given dα where x i is the i th element of x and x is the baseline.
Saliency Simonyan et al. [2014] proposed a straight forward approach in which the attribution is obtained by taking the predictive derivative with respect to the input. Therefore SAL i (x) = dF dxi (x). Feature Permutation. In the following we consider a perturbation-based notion to feature permutation, to allow for comparison in later sections. Feature Permutation [Breiman, 2001] requires multiple instances for calculating the attribution. The general idea is to use a batch of instances, iterate over every feature, permute the values of the respective feature in that batch, and then derive the attribution for each feature and instance by calculating the difference in predictive quality before and after the permutation. Since we want to have attributions for only single instances, we first define the feature importance (F I) function as acting on batches, that is F I : X ⊂ R m×n → R m×n , where X is the space of all batches of m instances with n features. F I takes a batch of instances and calculates attribution for each instance and feature by applying permutation. In order to obtain attribution for a single instance, we generate instances around the input instance using perturbation. We say that function p(x, m) ∈ R (m+1)×n generates m ∈ N random perturbations of x and returns those perturbations and x (x in the last column). With F I and p, we can now apply the feature permutation algorithm of "Captum" on a single instance using F I • p but we still need to decide on how we use this attribution for this batch to obtain an attribution for just one instance. To this end, we generate one perturbed instance around the input point, calculate the attribution of this batch of two points using feature permutation P = (F I i • p)(x, 1) (where F I i returns the feature importances of feature i only) and return only the attribution with respect to the original input instance. In order to decrease the impact of randomness, this is done 10 times and the attributions are averaged. Therefore, this feature permutation approach FP is given by FP i (x) = 10 j=1 P:,2 10 , where P :,2 is the second column of P (the column representing the attribution with respect to the original input instance). LIME Ribeiro et al. [2016] used a strategy entirely different from the aforementioned attribution methods. The key idea of LIME is to train a surrogate model. While this model will only be able to reliably predict accurate results for the area around the input instance, this reduced complexity aims to make this additional model more interpretable. We have LIME i (x) = w IM where w IM are the weights of the linear interpretable model surrounding x. Then we simply state LIME i (x) = R(p(x), F B (p(x))) where p : R n → R j×n is a function which generates a batch of perturbed data X P ∈ R j×n , F B is a batch-version of F (F B : R j×n → R j , F B (X P ) = (F (x 1 ), . . . , F (x j ))) and R is a ridge regression model (R(X P , F B (X P )) = argmin w ||F B (X P ) − X P w|| 2 2 + ||w|| 2 2 ). General Properties of Attribution Methods. The are several well known properties of attribution methods which will be useful later. An attribution method is (a) Gradient Based, if the attribution method relies on calculating gradients [Ancona et al., 2019]. It is (b) Perturbation Based, if the attribution method uses perturbations to generate data around the input point [Zeiler and Fergus, 2014]. (c) Completeness, is satisfied if the attribution method relies on a baseline x , and [Sundararajan et al., 2017]. And we refer to (d) Randomness, if randomness is involved in the calculation for the attribution. The impact of randomness can be reduced at cost of calculation time by increasing number of samples, steps, etc.

Encoding Priors for Linear Programs
In recent times, XAI methods have come to be primarily focused on neural methodologies [Gunning and Aha, 2019]. To justify the usage of XAI for LPs, we consider their similarities with neural models. Therefore, we first will consider how to encode LPs in a "neural" manner. One of the most obvious approaches here could be to use c, A, and b as inputs for the NN and the optimal solution x * for the output. This approach would give us attribution for the inputs, so c, A, and b. While we believe that such attributions would also carry valuable information, in this paper we focus on the information we can obtain from looking at one specific, single LP, so we consider c, A, and b fixed.
If we only train with a constant c, A, and b as inputs, the NN will simply learn to output the optimal solution x * without actual "learning". Therefore, we need a task from which we can construct a dataset with different inputs and corresponding outputs. We do so by inputting instances from the LP (x ∈ R n ). Now, we can define what the output should be and thus the corresponding learning problem. We refer to such a problem as an encoding (φ) of the original LP. Note, that this approach requires a new NN to be trained for each encoding and LP, thereby learning the relevant properties of the respective encoding well enough so that XAI methods can be applied correctly. Obtaining enough useful data and finding good NN hyperparameters can be challenging. Following paragraphs cover various reasonable encodings that we initially propose and then systematically investigate.
Feasibility Encoding. In a straight forward manner, we can simply distinguish between feasible instances, i.e. instances which do not violate any constraints, and infeasible instances, i.e. instances which violate at least one constraint. Using binary coding, we have φ( . Note that for any LP encoding we will keep the LP constraints A, b constant, therefore, in our notion the encoding function only depends on the optimization variable x. Gain-Penalty Encoding. In this approach, the feasible instances get assigned their corresponding gain and the score of an infeasible instance now depends on how much it violates the constraints. This is done by finding an -close (ideally the closest) feasible point, calculating the gain of that point and reducing it, depending on the distance between these two points. As a consequence, infeasible instances with only a small constraint violation have almost the same gain as the closest feasible instances but infeasible instances with large violations get assigned increasingly smaller scores (gains). To some degree, real world applications might justify this approach since the constraints are not completely prohibitive but rather that violations of them are simply too costly to be efficient. The Gain-Penalty encoding is defined as , where x f =argmin xi ||x i − x|| 2 is the closest feasible instance in the setting where c, A, b, > 0. Naturally, there exist various, sensible variations to this formulation.
Boundary Distance Encoding. For this encoding, we investigate the boundary between feasible and infeasible instances. By calculating the minimum of b − Ax, we can find out if an instance lies on the boundary and also obtain a score indicating how large the biggest violation is or, for feasible instances, how much space there is until the closest constraint would be violated: φ(x) = min(b − Ax). We can also take the absolute of this encoding |φ(x)| (Absolute Boundary Distance encoding) such that we can treat the output as a distance to the boundary (margin), changing attribution method behavior.
Vertex Distance Encoding. Here, the distance to the nearest vertex is used. A vertex of an LP is any feasible point which lies on either the intersection of two constraints or on the intersection of a constraint with an axis (or at the origin). Note, that any optimal solution has to lie on one of those vertices but since this approach does not include the cost vector c, it does not contain any information about which of those vertices is an optimal solution. Overall, the Vertex Distance encoding is defined

Properties of LP Encodings and Attribution Methods
Upon establishing various, sensible encodings φ, we now move on to the proposal of reasonable key properties for the discussed φ that we can come back to when we discuss how attribution methods behave on different encodings. To ease notation later on, we define the set X ⊂ R n ≥0 such that the properties are only related to instances which are not infeasible for every single LP by construction (since x ≥ 0). We propose the following key properties.
Distinguish Class/Distinguish Boundary. If an LP encoding φ computes values in such a way that feasibility of the point can be inferred from its output, we say that φ satisfies Distinguish Class. Table 1: Properties of encodings and attribution methods. On the left: properties of encodings, on the right: properties of attribution methods. The abbreviations are: F = Feasibility, G = Gain-Penalty, B = Boundary Distance, A = Absolute Boundary Distance, V = Vertex Distance, S = SAL, L = LIME. Regarding Neighborhoodness (*): Not binary, thus requires alternate interpretation. We argue that IG generally has the least Neighborhoodness because the path from baseline to input can be very long. Saliency always considers a smaller area than the perturbation-based approaches FP and LIME.
. In a similar way, Distinguish Boundary is satisfied if we can infer whether a point lies on the decision boundary: ∃g, ∀x ∈ X . (Ax = b ↔ g(φ(x))).
Boundary Extrema. This property is concerned with whether the boundaries of the LP are at the extrema of φ. There are multiple possibilities to define such a property. We postulate that a method satisfies Boundary Extrema if an extremum (maximum or minimum) of φ lies on the decision boundary and if this extremum does not appear outside the boundary. The extremum may appear more than once on the boundary itself.
Previously, we stated some well known properties of attribution methods. In addition to those, we now propose a new concept as well as another property for attribution methods which will be useful for discussing differences of attribution methods afterwards.
Neighborhoodness. Being more of a concept rather than a property, Neighborhoodness describes how large a region around the input point is considered for the attribution. For example, Neighborhoodness of perturbation-based approaches usually depends on the perturbation's "strength".
Directedness. We say that Directedness is satisfied if the attribution for a feature indicates how increasing that feature would change the output. The direction here is important, so the attribution is always considered with an increase of that feature in mind (for example, attribution would be negative if increasing that feature decreases the output). This increase might be local or over a larger interval, therefore the property does not directly depend on the Neighborhoodness of the attribution method.
We give an overview of the previously introduced properties of our LP encodings and on how the considered attribution methods fall into properties such as Neighborhoodness, Directedness, and other established properties in Table 1.

Empirical Illustration
We analyze the encodings, the properties, and the implications from the previous three sections empirically using an illustrative LP setting.

Experimental Setup.
To compare different encodings, we consider an LP that allows for 2dvisualization of its polytope. Further, we use a NN with 7 layers to train a model for each encoding introduced in Section 3. Another experiment only trains a NN for the feasibility encoding but uses an LP with 5 dimensions. For all experiments, we generate 100,000 random instances such that the complete LP polytope (set of feasible solutions) is covered and that about as many feasible and infeasible instances are being generated. For integrated gradients we use the baseline x = 0. In our experiments, FP and LIME use perturbations by generating instances around the input point, up to a set maximum perturbation. We use a Ridge Regression model with 2 dimensions for LIME.  The LP: The third constraint is a redundant constraint. Overview of Results. In Fig.2 we show the encodings versus attribution methods matrix (here only with the summed up feature attributions, refer to Supplementary for an example showing single feature attributions on the same LP). We approximate the regions we generated data for with 100 × 73 pixels. Note, that we ignored the vertex (0, 0) for the Vertex Distance encoding by including our prior knowledge that it cannot be the optimal solution. We refer to n i=1 A F (x) as the attribution sum. Q1. Integrated Gradients. The attribution sum for Integrated Gradients follows from its Completeness property: . Therefore, if Continuity, Distinguish Class, Distinguish Boundary, or Boundary Extrema is satisfied on φ, that same property also applies to IG. A benefit of Completeness is that the attribution for each feature indicates how large its contribution relative to the change in output compared to the baseline output is. In contrast to other methods with no such property, this makes it so that every attribution has a tangible meaning and that the attribution for a single instance can be understood without other instances as a comparison. 2 Of course, if Completeness is satisfied, the important part of any attribution is how the contribution is divided amongst the individual features. For example, consider the Vertex Distance encoding in Figure 2. Our baseline lies at (0, 0), a point with a relatively large distance to any of the three vertices. Here, the vertex on the bottom right only gets attribution for the horizontal feature, the vertex on the top left only attribution for the vertical feature as these respective features differ from the baseline (see this visualized in Supplementary). This would be different if a baseline on the top right was chosen. Therefore, the main challenge when applying IG is choosing a sensible baseline. Coming back to our previous example, maybe using a vertex as the baseline could carry more meaning, however then you would still have to decide which vertex to choose as this also influences the resulting attributions.
Overall, applying IG on LP encodings can result in useful and understandable attributions but those always must be interpreted with respect to the respective baseline. In addition, choosing an appropriate baseline is often not obvious.
Q2. Saliency. Since Salience simply calculates the local gradient, its general behavior is easily explained. In accordance with satisfying Directedness, attribution for a feature is positive if the feature impact on the respective point is positive, negative if it is negative, and 0 otherwise. Notably, this also means that there is no attribution on local extrema (see encodings satisfying Boundary Extrema in Figure 2). Since Saliency has a very small Neighborhoodness, attribution usually requires a certain amount of additional information to be useful. For example, attributions on and around a local maximum have different values, ranging from positive attribution where the value increases towards the maximum, to 0 exactly on the maximum, and to negative attribution afterwards. All those attributions are "correct" but if you were to consider only one of those points and have no knowledge about the maximum there, you might draw false conclusions about the feature impact in that area. In this example, prior knowledge about that local maximum or at least considering multiple other points reduces that risk.
One interaction worth discussion is how Saliency behaves on points where the encoding function is not differentiable. We can see this for the Absolute Boundary Distance encoding in Figure 2. Due to the absolute value function, points on the boundary are not differentiable. Still, the NN approximates this function in a differentiable way. Not only does this result in a 0 attribution (gradient) exactly on the boundary but there is also a small area around the boundary where the gradient quickly, but not instantly, changes from 0 to the true gradient of the area around. Other not differentiable points appear whenever an encoding does not satisfy Continuity. For the Feasibility encoding, this results in an extreme attribution very close to the boundary, where the NN approximates this discontinuity with a very steep function.
To sum up, attribution here reflects very local changes w.r.t. an increase of input features. Approximations of non-differentiable points by the NN influence Saliency attributions near those points.
Q3. Feature Permutation. Due to its perturbations, FP focuses on the change of the output around the input point. Since it does not satisfy Directedness, attribution in areas with a steadily changing output in one direction can average to 0, as the positive change in one and the negative change in the opposite direction cancel each other out. If that change in both directions is equal, the only remaining attribution is a result of the Randomness in the perturbation process.
Even though Directedness is not satisfied, there is a difference between negative and positive attribution but it has to be understood differently. Because FP considers the area around it without consideration of direction, local minima (maxima) can be observed to have negative (positive) attribution because permuting features of instances around it increases (decreases) their function output. 3 The degree of perturbation can be seen as a trade-off between precise, local results on the one hand and robust and emphasized attribution for larger areas on the other hand. All in all, attributions given by Feature Permutation consider any direction equally, thereby resulting in a focus on local minima and maxima of the encoded function.
Q4. LIME. In Figure 2, we can now observe how LIME with smaller perturbation (Neighborhoodness) look increasingly similar to Saliency. This is just as much true for the attributions of the features alone which, as described by Directedness, indicate how a feature impacts the output with respect to an increase of that feature. The major difference when comparing the results of Saliency and LIME is that we can choose how large of an area around the input point should be considered by LIME. So while small perturbations behave like Saliency, larger perturbations can help to focus on the more overarching characteristics and also make the procedure more robust against local errors and bad approximations of the NN. On the other hand, small, local perturbations allow for a more precise attribution of the respective points. Based on our experiments, the nature of LPs, and our noiseless data generation, we argue that usual downsides of very local perturbations might not be as significant.
On discontinuities, LIME, just like any method with a certain Neighborhoodness, can have very large attributions. Here, the attribution, so the slope of the linear model, is steeper the smaller the perturbations. Overall, LIME attributions show the same characteristics as those generated by  Figure 4: "LIME ≡ Saliency." With increasingly smaller perturbations, LIME comes visibly closer to Saliency. The decrease in attribution scores for smaller perturbation is due to the regularizer of the Ridge Regression model. Saliency. However, LIME allows for changing the Neighborhoodness of the attribution, making it possible to both consider only very local changes or include a larger area around the point of interest.
Q5. Higher dimensional Experiment. To show that we can handle higher dimensions we consider an input x consisting of five dimensions and three constraints. Figure 3 shows one infeasible and one feasible instance with the corresponding constraints and constraint violations. Attributions are shown for all four attribution methods, with an individual color scale for each method and input. As before, red indicates negative attribution, white zero attribution, and blue positive attribution. The left instance in Figure 3 is infeasible as it violates the third constraint (1.51 1.44). All attribution methods here focus on the last three features which have the highest impact on the violation of that third constraint. For the feasible instance (right), the second feature has the least attribution (remember that FP has a different sign in such a scenario). Here, both the second and the third constraint are somewhat close to violation and while the last three features are important for the last constraint, the first feature is important for the second constraint. The Saliency (S) attributions and one IG attribution are marked with dotted lines indicating small attribution values (under 0.01). This is the result of the same type of behavior previously mentioned in Q2. The discontinuous decision boundary is approximated by the NN in a continuous manner, resulting in instances close to the boundary to have outputs close to, but not exactly 0 or 1. This effect can even be useful, as the ratio of the feature attributions still contains information (without it, these attributions would all be 0).

Q6. Relationships between Attribution Methods.
Having examined the general behavior of the four attribution methods considered in this paper, we now go into detail about how they relate to each other. First of all, we argue that IG differs from the other methods significantly. While the "information" that IG uses to calculate its attribution consists of the path between baseline and input, all other three methods base their attribution on the area around the input. Looking at our results in Figure 2, we can see that especially Saliency and LIME show noticeable similarities, particularly if smaller perturbations are used for LIME.
Similarity of Saliency and LIME. The high-level description of how LIME functions is arguably similar to the underlying functioning of Saliency. Could this intuitive similarity on a high-level hint towards more, possibly an equivalence under certain circumstances?  : FP→LIME. If we make it so that FP distinguishes between forward and backward perturbations and scales attributions according to their distance from the input point, we can get results similar or even identical to LIME.
Both approaches calculate a value for a specific point with respect to how the output values around this point change, in other words, they both satisfy Directedness. So if we would perturb instances for LIME in such a way that they are infinitely close to the original input but not on the input itself (in which case we would simply have no attribution), then LIME approaches Saliency in the limit. We support this conjecture empirically (Fig.4). From that perspective, the main difference between LIME and Saliency is that former allows for considering a larger area (perturbation function as a hyperparameter). But even though attribution computation is different, we know from our experiments that FP and LIME use the same perturbations. So if both those methods use the same "information" to calculate attributions, how can FP look different?
How Feature Permutation differs from Saliency and LIME. Just like Saliency and LIME, FP uses nearby regions to determine attributions. Since all those three methods appear to base their attribution on similar information, could we again postulate a result on the triangular relationship? Again, we conjecture on the approaches's similarity: Conjecture 2 The main difference between Saliency and LIME on the one hand and FP on the other hand is Directedness. If you were to "insert" Directedness into FP, you would get an approach which behaves almost identically to LIME and, thereby, also to Saliency (for small perturbations).
Usually FP does not consider "how", i.e. in which direction a change happened, but only that it happened. For example, on a maximum, both Saliency and LIME (with small enough perturbations) would return little or no attribution because increase leading up to the maximum is canceled out by decrease going away from it. 4 However, FP only considers that there is an average decrease in any direction if a feature is changed, so if that decrease is large, then that feature must be important. You can see that FP is not necessarily worse, you might very well argue that it should be preferred in this example. But if FP would consider that decreasing the feature decreases the output and increasing the feature also decreases the output it could use this information of direction (Directedness) to also return an attribution akin to Saliency and LIME.
An example of the FP relation to LIME can be seen in Figure 5. This is a simplified example with only four perturbations, each of which only changes a single feature by 0.1. For this special case, we even reach identical attributions and while this is not generally true, the difference of LIME and FP after this transformation is also barely visible in most other cases. Also note that we used Linear Regression instead of Ridge Regression to easier show the equality after the transformation.

Conclusions and Future Work
We investigated the question of whether, and if so how, common attribution methods from XAI literature could be applied to settings beyond neural networks. Specifically, we looked at linear programs where we introduce various, sensible neural-encodings for representing the original LP. We show LIME and Saliency have very similar results if small perturbations are used for LIME. By introducing the property of Directedness, we also found out how a perturbation-based Feature Attribution approach can be transformed to behave very similarly to LIME and, hence (for small perturbations), also to Saliency. We believe that the discriminative properties (Tab. 1) can guide the development of transparent and understandable attribution methods, while also paving the road for more general application in machine learning.
For future work, we can consider explaining special types of LPs as those used for quantifying uncertainty such as in MAP inference [Weiss et al., 2007]. The application to mixed-integer LPs or integer LPs such as Shortest Path or Linear Assignment might prove valuable. Furthermore, investigating the scaling behavior of explanations generated for LPs or the cognitive aspects of whether and how LP attributions could be more "human understandable" seems critical.

A Appendix for "Attributions Beyond Neural Networks: The Linear
Program Case" This appendix contains an example of single feature attributions for the experiment shown in Figure 2 and some technical details.

A.1 Single Feature Attributions
In Figure 6, feature attributions for both features on the example of the Vertex Distance encoding are shown. These plots have been created using the same experiment as in Figure 2. Generally, it can be seen how the methods also differ in their single feature attributions and that feature attributions can vary significantly depending on the respective feature. The goal of this section is to inspect the results shown in Figure 6 to go into detail about the behavior of the attribution methods used in this paper and to explain the differences between the attributions for the two features here. 5

The LP:
The third constraint is a redundant constraint. Figure 6: Single feature attributions for the Vertex Distance encoding. The data is from the same experiment as in Figure 2. The LP has two features, one horizontal and one vertical, where the grey lines indicate the constraints for that LP. The line on the top shows the summed up attribution of all features for the Vertex Distance encoding. Each column shows a different attribution method (or configuration). For FP and LIME, p indicates the maximum possible perturbation in any direction. The (rounded) numbers for the constraints of that LP are shown on the bottom right. The part enclosed in the grey box titled "Feature Attributions" shows attribution for both single features on the Vertex Distance encoding. (Best viewed in color.) Integrated Gradients. Attribution for IG is obtained by calculating gradients on the path from a baseline to the input vector. As mentioned in the paper, this experiment uses the origin as its baseline: (0, 0). To illustrate this calculation, consider points which only differ from the baseline on the vertical feature (the far left of the shown plots). Here, the attribution for the horizontal feature remains at 0, as there is no change of this feature compared to the baseline, so it can not be responsible for any change in the output. Moving up towards the top left vertex however, the vertical feature gets an increasingly larger negative attribution. Since the attributions of IG sum up to the difference in output between baseline and input instance (Completeness), this difference has to be reflected by the feature attributions. In this encoding, the function values encode the distance to the nearest vertex. The encoding at the baseline (origin) has some positive value and the lowest values (the smallest possible distance, i.e. 0) can be found on any of the vertices. Therefore, the attribution for the vertical feature on the left vertex (where the horizontal feature remains unchanged compared to the baseline) must equal the negative difference between baseline output and 0, since otherwise the Completeness property would be violated. Another interesting region in Figure 6 can be found on the top, roughly in the middle of our plot. Here is the same kind of negative attribution for the vertical feature but also some positive attribution for the horizontal feature. While the increased vertical feature decreases the distance to that vertex, the increased horizontal feature increases the distance which results in positive attribution for that feature. In other words, the horizontal feature being larger than its baseline value (0) has a positive (the distance increases) impact on the output. This same reasoning also applies to other regions but there, the attribution can be influenced by other vertices, resulting in different attributions. For example, being on the bottom right indicates a small distance to the nearest vertex there (one of the two vertices on the bottom right), which is why for such instances positive horizontal feature values can have negative attributions.
Saliency. Since Saliency uses the local gradient for its attributions, understanding gradients is mostly sufficient for understanding this attribution method. To put it simply, on a specific point, if a feature has a positive impact on the output, then the gradient is positive, and if a feature has a negative impact on the output, then the gradient is negative. This impact and therewith the gradient can also be 0. Let us consider the Saliency feature attributions in Figure 6. In accordance with Directedness, if increasing a feature would get the point closer to a vertex (decrease the distance), it gets negative attribution. If increasing a feature would get the point further away from a vertex (increase the distance), it gets positive attribution. 6 The white areas in this figure might benefit from some further explaining. First of all, on and around the vertices, there is (close to) 0 attribution. The vertices are points where in theory the gradient should be undefined (because of the absolute value function used in the encoding). However, the NN approximates the true underlying function in a continuous way, leading to a continuously changing gradient and an attribution of 0 on the vertices which rather quickly reaches the "normal" gradient when moving away from those vertices in either direction. The white line starting at the bottom (somewhat left) and ending on the top (somewhat right) also has many points with (close to) 0 attribution because in this region, the gradient switches signs. For the single feature attributions, there are also some white lines moving away from the vertices: to the top/bottom for the horizontal feature and to the left/right for the vertical feature. Those are areas where only that respective feature changes its gradient from one sign to another. For example, if a point is below the nearest vertex, then its vertical feature attribution is negative first and once the point is above the closest vertex, the attribution becomes positive. At some point in between, when the point is on the same height as the vertex, its feature attribution is 0. This is true both if these points are exactly under/above the vertex or slightly on one side. Combining this behavior for points on the left and right of the vertices results in a horizontal white line indicating no attribution next to the vertex. The explanation for the horizontal feature can be done the same way. Such white lines resulting from this type of behavior are not necessarily visible in the plot for the attribution sum, since here the other features can have non-zero attributions. However, the attribution sum can also contain areas with no attribution even though there are single feature attributions because in such situations, these get averaged out to 0 overall (this can also be seen in Figure 6).
Feature Permutation. The attributions of FP need to be interpreted differently as they are unlike the other attribution methods in Figure 6. For FP, the output of the input point is compared to the outputs of neighboring points (perturbations). If, on average, their output is larger, then the attribution of the input instance is negative which describes the behavior seen around the vertices. If the neighboring points are, on average, smaller, then the attribution is positive. For the Vertex Distance encoding, this blue (positive) attribution can be observed on the line which has an equal distance to both nearest vertices, as here perturbing any feature in any direction creates a point closer to a vertex. Note, that FP always considers only one feature changed at a time since perturbations are only created by perturbing a single feature. The single feature attributions also indicate how important the features are compared to each other. For example, on this aforementioned blue line, the attribution is larger for the horizontal feature. This makes sense, as moving to the left or right has a higher impact than moving up or down by the same distance. 7 The noise visible in many regions is a result of the randomness in the FP perturbations. For example, in many areas the score increases roughly the same in one direction as it decreases in the other direction, therefore the FP attribution should be around 0. But if due to randomness, perturbations are created more strongly in one direction, the average output is now predominantly influenced by that direction, resulting in an average positive or negative change and an attribution not close to 0. This can happen in either direction, which in Figure 6 results in noisy areas with many red and blue dots in an otherwise rather white region. Interestingly enough, the strength of this noise for both features here indicates in which areas which feature has a higher impact (this even compares to the respective Saliency feature attributions). The larger the perturbations (p in Figure 6), the broader the area considered for the attributions, resulting in less accurate (local) but increasingly robust attributions that represent more general changes. LIME. The similarity between LIME and Saliency is not only present for the attribution sum but also for the single feature attributions. Instead of using the local gradient, LIME creates a small model for the input point based on perturbed instances around it. To summarize the resulting attributions briefly: feature attribution for LIME is positive if larger (smaller) instances have larger (smaller) outputs, negative if larger (smaller) instances have smaller (larger) scores and zero if either their outputs are smaller in one but equally larger in the other direction or if instances around the input have the same output as the input itself. Note, that, as with Saliency, the direction of the change around the input instance matters (Directedness). Also keep in mind that, unlike FP, LIME uses perturbations for multiple features at a time. For larger perturbations, it can be seen that the attribution patterns become more blurred and local details are disappearing. In some situations, this could possibly be an advantage and protect against noise, making the results more robust. There can be some slightly differing attributions of similar points due to the randomness in the perturbations.

A.2 Technical Details
Our code is available at https://cutt.ly/gHE0Nkx. All experiments were run on a desktop machine with an Intel(R) Core(TM) i5-7500 CPU processor, 16GB RAM, and a NVIDIA GeForce GTX 1070 graphics card.