betaFeedback

WorksComputer Science

A Comparative Study of Importance Attribution to Columns in Deep Learning over Relational Databases

Abstract

Deep learning over relational databases has led to increasingly effective prediction models, motivating a growing need to explain their behavior. We study explanation methods that assign importance scores to individual database attributes, focusing on a fundamental question: to what extent does the choice of importance-attribution method matter? We develop a methodology to systematically compare importance-attribution methods and analyze their similarities and differences. In particular, we study two aspects of the explanations: which attributes they deem important, captured by differences in attribute rankings, and how importance scores vary across attributes, captured by differences in score distributions. We further investigate whether these differences are reflected in the conventional measure of explanation quality, fidelity. We apply our methodology in an extensive empirical study of four methods: Monte Carlo Shapley, Kernel SHAP, single-attribute impact, and mask learning. We experiment with multiple datasets and tasks using two RDL architectures: heterogeneous GraphSAGE and Relational Graph Transformers. Our experiments show that explanation methods behave differently depending on the prediction type: regression or classification. In regression, most methods exhibit high agreement in attribute rankings, whereas classification yields considerably less consensus. Notably, while mask learning frequently diverges in its importance distributions, Shapley-based methods and single-attribute impact often converge to similar explanations. This suggests that, in many settings, single-attribute impact can replace Shapley at substantially lower computational cost. Overall, our study provides methodological tools for comparing importance-attribution methods, and empirical evidence that their choice has important consequences for interpreting relational deep learning models.

Introduction

Modern machine learning (ML) is applied to relational databases through various common approaches. One approach represents a relational database as a graph, where nodes correspond to entities (tuples) and edges capture relationships between them (typically induced by foreign-key constraints); then, graph-based deep learning models (e.g., graph neural networks) are trained directly on this representation [11, 16, 22, 68, 70, 71]. A second approach designs neural architectures that operate directly over the database, explicitly modeling tuples, attributes, and their relationships; examples include Relational Transformers [56], KumoRFM-2 [40], and neuro-relational programs [48, 66]. A third approach transforms the database into a single flat table, using techniques such as deep feature synthesis [42] and the ACORA architecture [55], and then applies a model designed for tabular data [32, 51], such as TabPFN [38].

Importantly, the above approaches rely on modeling complex interactions among database components (e.g., records and cells), often using deep learning architectures that incorporate mechanisms like attention and transformers. While these interactions allow the models to exploit information distributed across the relational structure, they also make it difficult to understand how individual components of the database contribute to a prediction. To this end, the field of Explainable Artificial Intelligence (XAI) studies methods for clarifying the behavior of complex models [4, 35, 50, 53, 63]. Explanations can be local, seeking to explain a prediction for a particular input, or global, seeking to describe the behavior of the model more broadly. They may also differ in the type of information they provide. Contrastive (or counterfactual) explanations identify changes to the input that would lead to a different outcome [7], while abductive explanations identify a restricted part of the input that is sufficient to support the observed outcome [50].

In this paper, we present an experimental study of a particular class of global explanations—those that assign an importance score to each data attribute (i.e., column) in a relational database, quantifying its contribution to the model’s predictions [58]. Such explanations can help data owners understand what the model relies on when making predictions, which parts of the data are most influential in decisions concerning individuals, and whether unexpectedly high importance assigned to certain attributes may reveal data leakage or other artifacts in the dataset’s construction. This setting differs fundamentally from standard feature-importance analysis for single-table models [10, 24, 49]. In the latter, each column typically corresponds directly to a feature of the target instance being predicted. In a relational database, by contrast, an attribute may belong to a relation that is several foreign-key hops away from the target relation. Its values may therefore influence a target prediction only indirectly, through the relational structure and the model’s aggregation mechanisms. Moreover, the same attribute value may contribute to the predictions for one, several, or many target instances. Consequently, attributing importance to database columns sheds light not only on the predictive effect of a feature, but also on how information propagates and is reused across the relational structure.

But how should the importance of an attribute be measured? There are multiple approaches to this task, drawing on techniques developed in both ML and databases, each embodying a different notion of what it means for an attribute to be important [15]. Since all of these methods aim to quantify an attribute’s contribution to the model’s predictions, one might expect them to agree, at least broadly, on which attributes matter and how much. If, however, well-founded methods produce substantially different insights, then the choice of explanation method is not merely a technical detail: the same model may admit conflicting accounts of what drives its predictions, depending on the explanation method of choice, potentially leading to different operational or scientific conclusions [43]. Our study examines this question. We compare explanation methods along three dimensions: whether they induce similar rankings of the attributes, whether they produce similar distributions of importance scores, and how these differences relate to the conventional notion of fidelity [3, 47, 75], which evaluates the effect of retaining or removing (or masking) database attributes.

We study four explanation methods that embody different notions of importance. The first, single-column ablation, is a direct instantiation of removal-based explanations [10, 15], and quantifies the impact of an attribute by masking its column and quantifying the resulting change in the model’s predictions. Two more methods are based on the Shapley value [65]—a traditional contribution measure from cooperative game theory that has been applied in a plethora of domains, including ML [62] and databases [8]. We show that the exact Shapley value is computationally intractable even for extremely limited architectures (Theorem 4.1), and employ two distinct approximation strategies: Monte Carlo, which is the direct sampling approach to estimating the Shapley value’s expectation [62], and Kernel SHAP, which estimates the Shapley values through a weighted linear surrogate model fitted over sampled coalitions. The last method is Mask Learning, a recently proposed approach for relational deep learning that optimizes a sparse mask over the database attributes so as to preserve the model’s predictions while retaining only the most important attributes [58].

Our study considers two graph-based relational deep-learning architectures: Heterogeneous GraphSAGE (HGS) [23, 36] and the Relational Graph Transformer (RelGT) [19]. Using these architectures as experimental testbeds, we develop quantitative analyses and visualizations to characterize agreement among explanation methods along two dimensions: the rankings they induce over attributes and the distributions of the importance scores they assign (§ 5).

Our study leads to several conclusions. First, addressing the concern that different explanation methods might yield conflicting insights, we find that the extent and pattern of agreement are dominated by the nature of the predictive task rather than the underlying relational deep-learning architecture. In regression tasks, most methods exhibit high agreement, isolating a tight core of critical attributes. In contrast, explanations for classification tasks exhibit much more disagreement between the methods.

Within this task-driven context, we observe consistent behavioral patterns among the explanation methods themselves. Single-column ablation and the two Shapley-based approximations (Monte Carlo and Kernel SHAP) often converge to highly similar explanations, exhibiting strong alignment in both their attribute rankings and score distributions. Given this high level of agreement, our findings suggest that in many cases, practitioners can avoid the high computational cost of Shapley approximations in favor of the faster single-column ablation method, without sacrificing the quality of the explanation. Mask Learning, on the other hand, frequently diverges from this consensus in how it distributes importance scores. This is likely because it aims to identify a set of attributes that are jointly sufficient for the prediction by treating each attribute as either included or excluded. This contrasts with approaches that assign each attribute an individual contribution score to produce a fine-grained ranking. This indicates that the choice of an explanation method should be carefully aligned with the specific notion of importance the practitioner seeks to capture.

These findings suggest that importance-attribution methods should not be regarded as interchangeable ways of recovering a single explanation. Rather, the choice of method and the notion of importance it captures should be made explicit when interpreting the resulting scores. When conclusions depend on attribute importance, examining more than one explanation method may provide useful evidence about the extent to which these conclusions are robust to this choice. Our findings also reveal that, when associating an explanation with a model, it is important to examine the properties of the explainers with respect to different scenarios.

Contributions. In summary, our contributions are as follows:

  1. We present a framework for comparing attribute-importance explanations in relational deep learning, and study four representative methods within this framework: single-column ablation, Monte Carlo Shapley, Kernel SHAP, and mask learning.

  2. We develop methodologies and visualizations for systematically comparing importance attribution methods along two complementary dimensions: the rankings they induce over database attributes and the distributions of the scores they assign. We further examine how agreement along these dimensions relates to the conventional fidelity-based evaluation of explanations.

  3. We conduct an extensive empirical study of the four methods across multiple relational datasets and prediction tasks, using two different architectures for relational deep learning over databases: Heterogeneous GraphSAGE and Relational Graph Transformer.

  4. We observe that an explainer’s behavior depends heavily on the predictive task type (e.g., regression versus classification) and its underlying mathematical notion of importance (e.g., individual attribute ranking versus collective subset sufficiency). These results motivate practitioners to carefully consider the explanation’s objective and the nature of the predictive task when choosing a method.

Organization. The remainder of the paper is organized as follows. We review related work in § 2. § 3 introduces our relational database setting, prediction models, and attribute-importance explanations. § 4 presents the four explanation methods considered in our study and establishes the computational intractability of the exact Shapley value. § 5 describes our experimental setup and presents our analysis of attribute rankings, importance-score distributions, and fidelity. We conclude in § 7.

Related Work

Feature-importance explanations. We focus on global feature importance methods, which assign an importance score to each attribute, summarizing its influence across all predictions rather than on a single instance. A direct realization is Permutation Feature Importance (PFI) [10, 17, 24, 54], which breaks the association between an attribute and the prediction by shuffling its values, and reports the performance degradation, evaluating each attribute on its own and thus ignoring feature interaction. The Shapley value [49, 62] addresses this limitation by evaluating an attribute’s marginal effect across every coalition of the others, at a computational cost exponential in the number of attributes. Widely used approximations are employed in practice: Kernel SHAP [49] recovers the values as coefficients of a weighted linear regression over sampled coalitions, while Monte Carlo estimation samples permutations and averages marginal contributions [62]. We experiment with both of these approximations, which are discussed in detail in § 4.

These methods belong to a broader family of removal-based explanations [15], which simulate the absence of an attribute and observe the effect, and which differ in how the attribute is removed, which aspect of model behavior is examined, and how the effects are summarized. LIME [57] is another prominent method in this family; however, it is inherently local, fitting a surrogate to a neighborhood of a single instance. Another line of work quantifies importance through the gradient of the output with respect to the input, with integrated gradients [67] being the standard representative. Such methods are not well suited for tabular and relational data because the feature space is heterogeneous, i.e., categorical features, timestamps, and text do not belong to a real-valued differentiable space.

Finally, importance may be expressed as membership in a subset rather than as a score, identifying a small set of attributes that alone suffice to preserve the model’s output. L2X [13] learns such a selection through an information-theoretic objective, while an alternative is to learn a sparse mask directly [25, 73]. The latter has been adapted to relational deep learning [58], which is to our knowledge the only explanation method developed specifically for relational deep learning, which we include alongside the three removal-based methods above.

Explanations in databases. Database research has studied explanations as well, where the goal is to explain a query result with explanations found in the input or specific aspects of computation [29]. Different approaches explain the presence or absence of specific tuples in query results [12], outliers, trends, and bias in query outputs [52, 61, 72, 74], and performance anomalies [41, 76]. Various techniques have been employed, including provenance [28, 31], targeted interventions on the input [60, 72], and concise summaries [26, 44]. We refer the reader to [29] for a comprehensive survey.

In parallel to the feature importance literature, the Shapley value has been applied for database explanations, for instance to quantify the contribution of a fact [18, 45] or a parameter [33] to a query result. The complexity landscape has been studied extensively: for conjunctive queries without self-joins the exact computation admits a dichotomy separating polynomial-time from #P-hard cases [45], and tractability is governed by the complexity of probabilistic query evaluation [18]. On the machine learning side the analogous question has been tackled for classes of models rather than classes of queries, where exact computation is #P-hard over the empirical distribution and already for logistic regression under fully-factorized distributions [69], and remains tractable only under restricted model structure [5]. Our setting differs in that the players are attributes rather than facts and the game is a learned model rather than a query, and the payoff aggregates disagreement over an entire evaluation set. In Section A, we show that computing the exact Shapley value in our setting is #P-hard even for a linear model over a single-table database, and remains so when each table carries a bounded number of attributes.

Evaluating and comparing explanations. XAI literature has documented multiple modes of failure for explanations, e.g., attributions may be insensitive to randomization of the model’s parameters or training data [1] or biased by the distribution shift caused by feature ablation [39]. These findings justify the need to systematically evaluate explanations under common metrics [2, 9, 37]. Among them are the fidelity measures we adopt, which assess whether the attributes an explanation deems as important are sufficient to preserve the prediction and whether they are necessary for it [3, 47, 75]. The two are distinct properties, and a method optimizing one need not perform well on the other. Testing methods individually leaves open whether they agree with each other. Comparing explanations for tabular models has found that well-motivated explanation approaches often disagree on which features are important, with no principled basis for preferring one ranking over another [43]. In this work, we answer the same question for the case of relational deep learning.

Preliminaries

We begin by establishing the formal foundations of our relational database framework.

Relational databases. A database schema S\mathcal{S} is a collection of relation names. Each relation name RR in S\mathcal{S} is associated with a sequence att⁡(R)=(A1,…,Ak)\operatorname{att}(R) = (A_1,\ldots,A_k) of attributes, together with a designated sequence key⁡(R)\operatorname{key}(R) of primary key attributes from att⁡(R)\operatorname{att}(R). Each attribute AiA_i has an associated domain dom⁡(Ai)\operatorname{dom}(A_i). A tuple tt over RR is a sequence (c1,…,ck)(c_1,\ldots,c_k) of values such that ci∈dom⁡(Ai)c_i \in\operatorname{dom}(A_i) for each i∈{1,…,k}i \in\{1,\ldots,k\}. We write t[Ai]=cit[A_i] = c_i for the value assigned to attribute AiA_i, and, for a sequence X=(Aj1,…,Ajℓ)X = (A_{j_1},\ldots,A_{j_\ell}) of attributes, we write t[X]=(cj1,…,cjℓ)t[X] = (c_{j_1},\ldots,c_{j_\ell}) for the projection of tt onto XX. An instance rr over RR is a finite set of tuples over RR such that t[key⁡(R)]≠t′[key⁡(R)]t[\operatorname{key}(R)] \ne t'[\operatorname{key}(R)] for all distinct tuples t,t′∈rt,t' \in r.

Furthermore, a database schema S\mathcal{S} contains a set of foreign-key (FK) dependencies, denoted by FK⁡(S)\operatorname{FK}(\mathcal{S}). An FK dependency from a relation RR to a relation R′R' is of the form R[X]⊆key⁡(R′)R[X] \subseteq\operatorname{key}(R'), where XX is a sequence of attributes of RR of the same length as key⁡(R′)\operatorname{key}(R'). For instances rr over RR and r′r' over R′R', the dependency is satisfied if, for every t∈rt \in r, there exists t′∈r′t' \in r' such that t[X]=t′[key⁡(R′)]t[X] = t'[\operatorname{key}(R')].

A database DD over a schema S\mathcal{S} assigns to each relation name RR in S\mathcal{S} an instance D(R)D(R) over RR. The database DD is valid if, for every FK dependency R[X]⊑key⁡(R′)R[X] \sqsubseteq\operatorname{key}(R') in FK⁡(S)\operatorname{FK}(S), the instances D(R)D(R) and D(R′)D(R') satisfy the dependency.

Prediction model. Formally, let D(S)\mathcal{D}(S) denote the space of all valid databases over the schema SS, let RR be a relation name of SS, and let YY be the target variable domain (e.g., Y=RY = \mathbb{R} for regression, or a discrete set of classes for classification). A prediction model ff is a function that takes a database D∈D(S)D \in\mathcal{D}(S) and any tuple t∈D(R)t \in D(R) as input, and maps them to an estimated target value f(t,D)∈Yf(t,D) \in Y based on the underlying data in DD.

For the purpose of evaluation, we let Dtarget⊆D(R)D_{\mathrm{target}} \subseteq D(R) denote an evaluation set containing specific target tuples for which a target value needs to be predicted and assessed against ground truth labels.

Attribute-importance explanations. In this work, we focus on a specific class of explanations known as attribute-importance explanations [67]. This form of explanation quantifies the contribution of individual attributes to the model’s prediction by assigning a numeric score to each attribute. Structural keys (primary and foreign keys) are explicitly excluded from the explanations; since these keys dictate the structural topology of the relational schema, masking or perturbing them alters the underlying relational structure instead of modifying a data attribute value. Therefore, we focus on the remaining attributes, which we refer to henceforth as data attributes. We denote this set of data attributes in all relations of the schema SS by dat⁡(S)\operatorname{dat}(S) and its size by N=∣dat⁡(S)∣N = |\operatorname{dat}(S)|.

In this paper, by an explanation method we refer to a function EE that, given a prediction model ff and a database D∈D(S)D \in\mathcal{D}(S), assigns a numerical importance score to each attribute in dat⁡(S)\operatorname{dat}(S). Formally, E(f,D)E(f,D) maps the data attributes to an attribution function W:dat⁡(S)→RW : \operatorname{dat}(S) \to\mathbb{R} where W(Ai)W(A_i) represents the estimated contribution of the attribute Ai∈dat⁡(S)A_i \in\operatorname{dat}(S) to the model’s prediction.

With these foundations in place, our overarching goal is to systematically evaluate and compare the explanations generated by different methods when applied to a prediction model over a relational database.

Explanation Methods

In this section, we describe the explanation methods used in our evaluation. We selected four diverse methods originating from different interpretability frameworks. The methods we describe are fundamentally model-agnostic, and treat the underlying predictive model as a black box. Consequently, the proposed explanation framework is generalizable to any Relational Deep Learning (RDL) architecture that operates on structured, multi-table data.

Single Column Ablation

The Single Column Ablation explainer is a black-box framework grounded in the concept of Permutation Feature Importance (PFI) [53]. PFI quantifies the importance of an input attribute by measuring the change in a model’s prediction output after permuting the attribute’s values, which effectively breaks the attribute’s relationship with the target outcome. Our approach generalizes this principle in two key aspects to suit the complexity of relational data. First, while standard PFI relies exclusively on shuffling values (permutation), we expand the ablation operator α\alpha to structurally support a variety of type-specific strategies, such as mean imputation and noise injection. Second, we measure the direct prediction sensitivity of the model consistently across both classification and regression tasks by quantifying the average magnitude of the shift in the continuous output (raw prediction probabilities for classification and target predictions for regression).

Formal mechanism. For each attribute Ai∈dat⁡(S)A_i \in\operatorname{dat}(S), we define an ablation operator α(Ai)\alpha(A_i) that replaces the values of the column with a predefined baseline value. Let DtargetD_{\mathrm{target}} be the evaluation set, and let Di,αD_{i,\alpha} be the modified version of the database where only the ii-th attribute has been replaced by α(Ai)\alpha(A_i).

We define the attribution function W:dat⁡(S)→RW : \operatorname{dat}(S) \to\mathbb{R} by setting the importance score W(Ai)W(A_i) as the average absolute change in the model’s prediction output across all evaluated target tuples:

W(Ai)=1∣Dtarget∣∑t∈Dtarget∣f(t,D)−f(ti,α,Di,α)∣W(A_i) = \frac{1}{|D_{\mathrm{target}}|} \sum_{t \in D_{\mathrm{target}}} \left| f(t,D) - f(t_i,\alpha,D_{i,\alpha}) \right|

where ff is the prediction model, t∈Dtargett \in D_{\mathrm{target}} represents an original target tuple, and f(t,D)f(t,D) denotes the prediction for this tuple under the original database DD. Accordingly, let ti,αt_{i,\alpha} denote the perturbed target tuple where the ii-th attribute has been replaced by α(Ai)\alpha(A_i). In both task regimes, W(Ai)W(A_i) quantifies the dataset-level prediction sensitivity, where a higher value indicates greater overall importance of attribute AiA_i across the entire evaluation set.

Shapley Value

The Shapley value is a concept originating from cooperative game theory, providing a unique and axiomatic solution for fair credit assignment among players (e.g., input attributes) contributing to a total payout (e.g., the model’s prediction) [49, 62]. In the domain of relational databases, the Shapley value has been effectively employed to quantify the importance of specific database facts or query parameters [18, 33, 46]. We next describe an application of the Shapley value to attribute importance.

Formally, let dat⁡(S)\operatorname{dat}(S) be the set of NN data attributes as defined in Section 3. To capture the impact of these attributes on the model’s predictions, we define a dataset-wide characteristic function v(S):P(dat⁡(S))→Rv(S) : \mathcal{P}(\operatorname{dat}(S)) \to\mathbb{R} over the evaluation set DtargetD_{\mathrm{target}}. For a given coalition S⊆dat⁡(S)S \subseteq\operatorname{dat}(S) of attributes, the attributes excluded from the coalition (i.e., dat⁡(S)∖S\operatorname{dat}(S) \setminus S) are systematically ablated across the database.

For both classification and regression tasks, the global characteristic function v(S)v(S) measures the global mean absolute prediction shift over all target tuples. Let t∈Dtargett \in D_{\mathrm{target}} represent an individual target tuple, and let f(t,D)f(t,D) be the prediction of the original black-box model ff for tuple tt given the original database DD. Let DSD_S denote the perturbed database generated by replacing all the attributes of dat⁡(S)∖S\operatorname{dat}(S) \setminus S with their predefined baseline values. Accordingly, let tSt_S denote the perturbed target tuple where the same excluded attributes have been replaced by their baseline values. The characteristic function v(S)v(S) is formulated as:

v(S)=1∣Dtarget∣∑t∈Dtarget∣f(t,D)−f(tS,DS)∣.(1)v(S) = \frac{1}{|D_{\mathrm{target}}|} \sum_{t \in D_{\mathrm{target}}} \left| f(t,D) - f(t_S,D_S) \right|. \tag*{(1)}

Given this global characteristic function, we follow the definition of [62] for the global Shapley value W(Ai)W(A_i) for a specific input attribute Ai∈dat⁡(S)A_i \in\operatorname{dat}(S), which is formulated by averaging its marginal contribution over all possible permutations of the attributes:

W(Ai)=1N!∑π∈Π[ν(Sπ(i)∪{Ai})−ν(Sπ(i))]W(A_i)=\frac{1}{N!}\sum_{\pi\in\Pi}\left[\nu\left(S_{\pi}^{(i)}\cup\{A_i\}\right)-\nu\left(S_{\pi}^{(i)}\right)\right]

where Π\Pi is the set of all N!N! permutations of the attributes in dat⁡(S)\operatorname{dat}(S), and Sπ(i)S_{\pi}^{(i)} represents the set of attributes that precede attribute AiA_i in permutation π\pi. The resulting value W(Ai)W(A_i) is the average marginal contribution of attribute AiA_i to the model’s global prediction shift.

Computational intractability. While this approach offers a robust and theoretically sound foundation, naively calculating the Shapley value directly from its definition requires evaluating the characteristic function across all N!N! possible permutations. In fact, computing the exact Shapley value under our characteristic function ν\nu, which measures the global mean absolute prediction shift, is computationally intractable even in highly restricted settings.

Theorem 4.1. Computing the Shapley value of an attribute under the characteristic function ν\nu is #P-hard. This holds already for a linear model over a single-relation schema. It also holds when the schema consists of multiple relations, all of bounded arity, and the model is a message passing GNN with a single layer and no non-linear activations.

The complete proof is provided in Section A. The hardness result is also of independent interest beyond our specific setting: since the reduction applies to a single tuple in a single relation, it establishes #P-hardness of exact local/global attribute-level Shapley computation under natural ablation-based characteristic functions, even for a linear model. The proof is by a reduction from the counting version of Subset-Sum (i.e., how many subsets sum up to the given number?). This proof is intricate, since it requires carefully designing the schema and attribute values so that the marginal contribution of a designated probe attribute encodes exactly the subset-sum structure needed by the reduction.

To overcome their intractability, we approximate the Shapley values via two methods: Monte Carlo permutation sampling (denoted as Shapley-MC) and Kernel SHAP (denoted as Shapley-KS).

Monte Carlo Shapley (Shapley-MC)

Since evaluating all N!N! permutations is computationally prohibitive, Shapley-MC approximates the Shapley values by sampling PP random permutations and averaging the marginal contributions over them [18, 62]:

W(Ai)≈1P∑p=1P[ν(Sp(i)∪{Ai})−ν(Sp(i))]W(A_i)\approx\frac{1}{P}\sum_{p=1}^{P}\left[\nu\left(S_p^{(i)}\cup\{A_i\}\right)-\nu\left(S_p^{(i)}\right)\right]

where Sp(i)S_p^{(i)} represents the set of attributes that precede attribute AiA_i in the pp-th random permutation. By using our characteristic function ν\nu combined with a unified baseline ablation strategy (Section 5.1.3), this Shapley-MC method provides a consistent and unbiased statistical estimation of the exact Shapley values.

Convergence and empirical termination. Achieving strict theoretical convergence guarantees (such as Hoeffding-Chernoff bounds [27]) for Shapley-MC in complex relational schemas can require a computationally prohibitive number of permutations. Consequently, in

our experiments (§ 5) we adopt an empirical termination strategy based on stability over time. During execution, the explainer incrementally tracks the running mean of the Shapley estimates utilizing Welford’s online algorithm [64], a numerically stable method for computing the running variance and mean, and exports hourly checkpoints. To evaluate convergence, we measure the step-by-step stability by calculating the absolute difference in the estimated scores between consecutive checkpoints for all attributes:

ΔWShapley−MC(t)(Ai)=∣WShapley−MC(t)(Ai)−WShapley−MC(t−1)(Ai)∣\Delta W_{\mathrm{Shapley-MC}}^{(t)}(A_i)=\left|W_{\mathrm{Shapley-MC}}^{(t)}(A_i)-W_{\mathrm{Shapley-MC}}^{(t-1)}(A_i)\right|

where WShapley−MC(t)(Ai)W_{\mathrm{Shapley-MC}}^{(t)}(A_i) represents the estimated importance score at elapsed hour tt. By plotting the mean and maximum absolute differences over time, we generate a loss-style convergence curve. We terminate once this curve visibly flattens out, indicating that the maximum absolute shift across all attributes has diminished to a negligible noise floor, and the relative order of the most influential data attributes has sufficiently stabilized. A representative convergence curve is illustrated in Figure 1 (convergence plots for all other datasets are provided in Section B).

Figure 1. A representative empirical convergence curve (shown for HGS on the rel-trial dataset for the study-adverse task). The plot tracks the absolute difference in estimated scores (∣ΔShapley_value∣|\Delta\mathrm{Shapley\_value}|) between consecutive permutation checkpoints.

Kernel SHAP (Shapley-KS)

An alternative approximation method is Shapley-KS [49], which frames the explanation of a black-box model as a weighted linear regression. Unlike exact Shapley computations that require evaluating an exponentially large number of permutations, Shapley-KS estimates the importance scores by fitting an additive surrogate model on a bounded set C⊆P(dat⁡(S))C\subseteq\mathcal{P}(\operatorname{dat}(S)) of sampled attribute coalitions.

To construct the sample set CC, we adopt a structured sampling strategy aligned with the original Shapley-KS implementation [49], and adapted for our global evaluation setting. Coalitions are constructed by fully enumerating small (e.g., ∣S∣∈{1,2}|S|\in\{1,2\}) and large (e.g., ∣S∣∈{N−1,N−2}|S|\in\{N-1,N-2\}) subset sizes that naturally carry the highest SHAP kernel weights δ(S)\delta(S). These weights δ(S)\delta(S) are theoretically derived to recover the original Shapley values and are defined as:

δ(S)=N−1(N∣S∣)∣S∣(N−∣S∣)\delta(S)=\frac{N-1}{\binom{N}{|S|}|S|(N-|S|)}

The remaining evaluation budget is filled by randomly sampling coalitions such that the probability of drawing a coalition SS is proportional to its weight δ(S)\delta(S). Since δ(S)\delta(S) depends only on the coalition size ∣S∣|S|, this is efficiently implemented without explicitly enumerating the entire space: the explainer first samples a subset size kk according to the aggregate weights of each size, and then draws a combination of kk attributes uniformly at random.

For a sampled coalition S∈CS \in C, we evaluate the characteristic function ν(S)\nu(S) as defined in Equation (1). The surrogate explanation model approximates the global Shapley values W(Ai)W(A_i) for each attribute AiA_i via the optimized coefficients ϕi\phi_i, which are obtained by solving the following weighted least-squares optimization problem:

(ϕ0,…,ϕN)=arg⁡min⁡ϕ0′,…,ϕN′∑S∈C[ν(S)−(ϕ0′+∑Ai∈Sϕi′)]2δ(S)(\phi_0,\ldots,\phi_N)=\underset{\phi'_0,\ldots,\phi'_N}{\arg\min}\sum_{S\in C}\left[\nu(S)-\left(\phi'_0+\sum_{A_i\in S}\phi'_i\right)\right]^2\delta(S)

Comparing the two approximation strategies, Shapley-KS is generally more computationally efficient than Shapley-MC. This efficiency stems from Shapley-KS optimizing the variance of the estimates over a constrained sample space using weighted least-squares, whereas Shapley-MC averages marginal contributions over sampled permutations. While Shapley-KS provides a consistent estimator of the Shapley values, it is currently unknown whether it is an unbiased estimator [14].

Mask Learning

The Mask Learning explainer [58] is an optimization-based explanation method designed to identify a small subset of attributes that are sufficient to maintain the model’s original prediction. Unlike sampling-based methods (such as Shapley-MC and Shapley-KS), it formulates the explanation task as a mask-learning problem. For a given set of relational tables, the explainer learns a continuous mask vector m∈[0,1]Nm \in[0,1]^N corresponding to the attributes in dat⁡(S)\operatorname{dat}(S), where each element mim_i represents the importance of attribute Ai∈dat⁡(S)A_i \in\operatorname{dat}(S) across the entire relational schema. Upon convergence, these learned mask values directly serve as our attribution function, setting W(Ai)=miW(A_i)=m_i.

Optimization objective. Following [58], the mask mm is learned by solving a continuous optimization problem that minimizes the prediction error while encouraging mm to promote only a small set of attributes. Let tt be a target tuple, and let f(t,D)f(t,D) be the prediction of the model ff on the original input database DD. Let f(t,Dm,ω)f(t,D_{m,\omega}) be the prediction on the masked database Dm,ωD_{m,\omega} under a random perturbation distribution ω\omega, which we describe in detail below. The objective employs a loss function to penalize the discrepancy between the original and masked predictions, alongside an L1L_1 regularization weighted by a hyperparameter λ\lambda to encourage the mask mm to be sparse. Formally, the objective function is defined as:

min⁡m∈[0,1]NEtEω[loss⁡(f(t,D),f(t,Dm,ω))]+λ∥m∥1(2)\min_{m\in[0,1]^N}\mathbb{E}_t\mathbb{E}_\omega\left[\operatorname{loss}(f(t,D),f(t,D_{m,\omega}))\right]+\lambda\lVert m\rVert_1 \tag*{(2)}

Relational masking strategy. The transformation to the masked database Dm,ωD_{m,\omega} is achieved through a mapping function h(m)h(m) that applies the learned masks to the relational attributes. This mapping interpolates between the original value of an attribute AiA_i and an “uninformative” alternative state, denoted as Aˉi\bar{A}_i. At each optimization step, this alternative value Aˉi\bar{A}_i is randomly sampled for each tuple from the attribute’s empirical distribution over the entire database. The continuous mask value mim_i dictates the weighting between the original and sampled values to produce the masked representation A~i\tilde{A}_i. The masking operation for each attribute is computed as

A~i=mi⋅Ai+(1−mi)⋅Aˉi.\tilde{A}_i=m_i\cdot A_i+(1-m_i)\cdot\bar{A}_i.

This masking operation is performed directly on the real-valued learned feature embeddings inside the model’s forward pass, ensuring a fully differentiable formulation.

Implementation and hyperparameter selection. We incorporate an automated selection mechanism for the λ\lambda hyperparameter aiming to balance the two components of Equation (2) at the beginning of optimization. The optimization is performed using the Adam optimizer over a fixed number of iterations, adopting the optimization hyperparameters reported in [58].

Experimental Evaluation

We present comprehensive experiments to evaluate the alignment, consistency, and faithfulness of explanation methods applied to relational deep learning architectures. We aim to address three main research questions: (Q1Q_1) How do explanation methods differ in the ranking of the attributes? (Q2Q_2) How do they differ in the distribution of importance scores to the attributes? (Q3Q_3) How do they differ in their fidelity scores, and to what extent are these differences reflected in the ordinal and distributional comparisons?

Summary of results. Our empirical evaluation reveals that explainer consensus depends heavily on the nature of the predictive task. Across both ranking (§ 5.2) and score distribution (§ 5.3) evaluations, we observe that regression problems generally yield a unified subset of critical attributes across different methods, whereas classification tasks produce more varied importance assignments. Furthermore, while standard fidelity metrics (§ 6) broadly corroborate our direct comparisons, we also observe cases where divergent explanations achieve comparable fidelity. This demonstrates that comparing explainers by standard faithfulness evaluations alone can mask disagreements, making our alignment analysis a required complement to standard evaluations.

Experimental Setup

Next, we describe the general setup of our empirical study. The implementation is in Python 3.12 and publicly available.1

Datasets and Tasks

To evaluate the effectiveness of the explanation methods, we focus on predictive tasks from the RelBench framework, spanning datasets from both its initial release [59] and the updated version [34]. Each dataset represents a realistic relational database schema, and is associated with prediction tasks. We focus on entity-level tasks where the goal is to predict a specific outcome (classification or regression) for a target entity by aggregating information across multiple tables.

rel-trial. The rel-trial dataset [59] is a relational benchmark derived from clinical trial records, consisting of 15 interconnected tables, including studies, interventions, and outcomes. The schema comprises a total of 140 attributes, with approximately 5.5M rows across the entire relational structure. This dataset contains a rich set of attributes, including categorical study types, numerical participant counts, and textual descriptions of medical procedures.

We evaluate our methods on two distinct tasks within this dataset: (1) study-outcome, a binary classification task where the model predicts whether a clinical trial will achieve its primary outcome (defined as reaching a pp-value <0.05< 0.05), and (2) study-adverse, a regression task where the goal is to predict the exact number of affected patients with severe adverse events during the trial.

rel-arxiv. The rel-arxiv dataset [34] stores physics publications on arXiv between 2018 and 2023, consisting of 6 interconnected tables including papers, authors, and categories. The schema comprises 21 attributes with approximately 2M rows across all tables. This dataset contains diverse attributes such as paper titles and abstracts (represented as pretrained text embeddings).

We evaluate our methods on two tasks within this dataset: (1) paper-citation, a binary classification task predicting whether a paper will receive at least one citation within the next 6 months, and (2) author-publication, a regression task predicting how many papers a given author will publish within the next 6 months.

rel-f1. The rel-f1 dataset [59] is a relational benchmark based on Formula 1 racing data spanning over five decades, consisting of 9 interconnected tables including races, drivers, constructors, and results. The schema comprises a total of 67 attributes with approximately 98K rows across all tables.

We evaluate our methods on two tasks: (1) driver-dnf, a binary classification task predicting if a driver will get a "Did Not Finish" (DNF) status in a race within the next 1 month, and (2) driver-position, a regression task predicting the average finishing position of each driver across all races in the next 2 months.

rel-event. The rel-event dataset [59] is a relational benchmark derived from user activity on the Hangtime social event application, consisting of 5 interconnected tables including users, events, and event_attendees. The schema comprises a total of 128 attributes with approximately 41.3M rows across all tables.

We evaluate our methods on two tasks within this dataset: (1) user-repeat, a binary classification task where the model predicts whether a user that attended a recent event will attend a future event (i.e., respond "yes" or "maybe"), and (2) user-attendance, a regression task aiming to predict the total number of events to which a user will respond "yes" or "maybe" in the next 7 days.

5.1.2   Prediction Models. Following Fey et al. [22], a database is represented as a graph where each tuple corresponds to a node, and edges are established based on FK/PK relationships. We experiment with two models of different paradigms: a message passing GNN and a transformer-based architecture.

  • Message passing GNN (HGS): We follow the RelBench methodology [59] and use a model based on the heterogeneous GraphSAGE architecture [23, 36].

  • Relational graph transformer (RelGT): The second architecture is the state-of-the-art Relational Graph Transformer (RelGT) framework [19], which operates over the same tuple-level graph constructed via FK/PK relationships.

In both architectures, following the RelBench methodology [59], initial node embeddings are generated using a ResNet-based tabular encoder [30]. To support attribute-level explanations via masking, we utilize the implementation of [58] which augments the default tabular encoders with real-valued masking capabilities.

5.1.3   Explainer Configurations. To enable a methodological alignment among the removal-based explainers (Single Column Ablation, Shapley-MC, and Shapley-KS), we utilize a unified, deterministic ablation operator: mean imputation for numerical, temporal, and text attributes (computed over their pretrained embeddings), and the Most Frequent Value (MFV) for categorical attributes. This design choice is motivated by the foundational approximations of Shapley-KS [49], which simulates missing attributes using expected marginal values under the assumption of feature independence. Mask Learning inherently relies on a permutation-based masking strategy during its optimization, and is therefore not affected by this choice.

For the Shapley-KS explainer, we follow the standard sample-complexity heuristic [49] recommending 2N+20482N + 2048 samples. In our schemas N≤140N \le140, and we round up to enable robust empirical approximation, resulting in a fixed budget of 3,000 samples.

Explainer Ranking Alignment

Objectives. In this section, we aim to determine whether distinct explainability methods identify a consistent ranking of attribute importance (Q1Q_1). To that end, we focus on the attribute ranking and ignore the absolute importance scores given by each explanation method. We aim to examine whether different mathematical frameworks converge on the same prioritization of relational database attributes when interpreting identical model decisions.

Evaluation Methodology. Explainers produce an importance score for each attribute. To compare top-kk rankings with ties, we utilize the framework of Fagin et al. [20, 21]. There, tied elements are placed into equivalence classes (buckets) and assigned an average rank. Our importance scores may yield practically identical scores that are not exact ties. Therefore, we introduce a custom quantization step where attributes are grouped into equivalence classes using a dynamic, range-based threshold calculated individually for each explainer’s score distribution: τ=(wmax⁡−wmin⁡)/100\tau= (w_{\max} - w_{\min})/100. Bucketing is executed via a greedy pass over attributes sorted in descending order, where a new bucket is initiated only when a score drops by more than τ\tau from the highest score in the current bucket. We then follow Fagin’s methodology: average real-valued ranks are assigned to each bucket, and we apply the transformation to project the scores into a unified partial (top-kk) ranking σ\sigma, where σ(Ai)\sigma(A_i) represents the final rank assigned to attribute Ai∈dat⁡(S)A_i \in\operatorname{dat}(S). For each attribute Ai∈dat⁡(S)A_i \in\operatorname{dat}(S), its rank is projected to σ(Ai)=rank⁡(Ai)\sigma(A_i) = \operatorname{rank}(A_i) if its sorted position (from 1 to NN) after alphabetical tie-breaking falls within the top-kk window. Attributes falling outside the top-kk window are assigned a tied rank of ℓ=(N+k+1)/2\ell= (N + k + 1)/2, representing the neutral average rank of all unranked attributes.

To quantify pairwise alignment between two explainers, we follow Fagin et al. [20] and use the L1L_1 distance (generalized Spearman footrule) between the rankings σ1\sigma_1 and σ2\sigma_2. Specifically, for a prefix size kk, define a normalized similarity score using the top-kk distance:

Similarity⁡(σ1,σ2)=1−∑Ai∈dat⁡(S)∣σ1(Ai)−σ2(Ai)∣2kℓ−k(k+1)\operatorname{Similarity}(\sigma_1, \sigma_2) = 1 - \frac{\sum_{A_i \in\operatorname{dat}(S)} \left|\sigma_1(A_i) - \sigma_2(A_i)\right|}{2k\ell- k(k + 1)}

As expressed in the formula, the disagreement distance is the total sum of absolute rank differences across all attributes. The distance is normalized to [0,1][0, 1] by the maximum possible distance, 2kℓ−k(k+1)2k\ell- k(k + 1), which occurs when the top-kk sets are disjoint. We transform the distance to similarity by subtracting it from 1. The results are between 0 (complete disagreement) and 1 (full agreement).

We visualize alignments using pairwise similarity heatmaps (Figure 2 and Figure 3). As pairwise similarity is symmetric and the diagonal is always 1.0, we display only the lower-triangular matrix to reduce visual redundancy. To maintain structural relevance across varying schema scales, large schemas are evaluated using percentage-based prefixes (5% to 100% of attributes), while compact schemas are tracked via absolute attribute counts. Darker green cells indicate higher agreement, whereas red configurations signal disagreement.

Figure 2. Pairwise explainer similarity for regression, showing alignment on different prefixes (kk) for HGS and RelGT.

Figure 3. Pairwise explainer similarity for classification, showing alignment on different prefixes (kk) for HGS and RelGT.

Results. Our analysis reveals that agreement is primarily driven by the nature of the task rather than the choice of the neural architecture. In regression (Figure 2), we observe high agreement among most explanation methods, growing stronger at larger kk values. Specifically, Single Column Ablation, Shapley-MC, and Shapley-KS demonstrate strong alignment in their global and top-kk rankings while Mask Learning frequently diverges from this consensus. Conversely, classification tasks (Figure 3) exhibit markedly less agreement among the explainers, as evidenced by the consistently lower similarity scores (weaker green intensities) across all kk values.

Since Shapley-KS and Shapley-MC are both strategies designed to estimate the exact Shapley values, we often observe a perfect agreement score between them, especially over the top attributes. However, this is not always the case: for example, there were disagreements between the methods in the study-adverse task under RelGT, study-outcome and user-repeat for both architectures. To verify that these discrepancies are not simply artifacts of insufficient sampling, we empirically validated the convergence of both methods (convergence plots for Shapley-KS are provided in Section C alongside those for Shapley-MC in Section B). Therefore, these differences stem inherently from the distinct estimation mechanisms of the two explainers. Hence, while the two approximations reach strong agreement on the highest-ranked attributes (i.e., at lower kk values), their rankings frequently diverge as kk increases.

While Single Column Ablation, Shapley-KS, and Shapley-MC often behave similarly in their importance scores, their execution times differ significantly. The runtime of Single Column Ablation depends directly on the number of database columns, whereas Shapley-KS and Shapley-MC also depend on the number of samples. In our empirical evaluation, when measuring execution times at the point of empirical convergence for each method, Shapley-KS completed its execution a median of 37×37 \times faster than Monte Carlo sampling. However, the Single Column Ablation explainer remains the most computationally efficient, completing its execution a median of 9.3× faster than Shapley-KS. A more comprehensive evaluation of run times is left for future work. These significant runtime performance trade-offs highlight the practical advantages of the Single Column Ablation explainer in large-scale relational schemas.

Conclusions. The level of agreement among explanation methods depends heavily on the type of the predictive task. Regression tasks result in significantly higher explainer consensus than classification tasks. In scenarios where multiple methods produce highly similar rankings, they can be distinguished primarily by their computational efficiency. In these high-agreement regimes, Single Column Ablation emerges as an efficient proxy, delivering rankings that are highly aligned with the computationally prohibitive Shapley-MC and Shapley-KS methods. Finally, while Shapley-KS and Shapley-MC generally align closely on the top attributes, their distinct estimation strategies prevent strictly identical rankings.

Additionally, the persistent divergence of Mask Learning highlights that an explainer’s behavior is heavily dictated by its mathematical formulation. Specifically, Mask Learning evaluates collaborative impact by optimizing all attributes simultaneously to discover the most predictive joint subset, rather than isolating individual contributions. Furthermore, Mask Learning employs permutation-based masking instead of deterministic baseline imputation. These differences in core objectives and underlying ablation operators play a critical role in shaping the resulting importance rankings.

Explainer Score Distribution

Objectives. In this section, we aim to determine how explainability methods differ in the distribution of importance scores to attributes (Q2Q_2). We divide this analysis into two parts: (1) examining whether methods differ in their overall score distribution across the entire attribute space, and (2) determining whether they agree on the specific top relational attributes. Unlike the ranking evaluation (§ 5.2) which considers only ordinal positions, this analysis must also evaluate the actual importance scores, since attributes may hold similar ordinal ranks across different explainers, while receiving vastly different importance scores.

Evaluation methodology. To enable meaningful comparisons across explainers with different score distributions, we apply min-max normalization to map absolute attribution weights onto a standardized continuous scale [0,1][0, 1]:

W~(Ai)=∣W(Ai)∣−min⁡Aj∈dat⁡(S)∣W(Aj)∣max⁡Aj∈dat⁡(S)∣W(Aj)∣−min⁡Aj∈dat⁡(S)∣W(Aj)∣\widetilde{W}(A_i) = \frac{\lvert W(A_i)\rvert- \min_{A_j \in\operatorname{dat}(S)} \lvert W(A_j)\rvert}{\max_{A_j \in\operatorname{dat}(S)} \lvert W(A_j)\rvert- \min_{A_j \in\operatorname{dat}(S)} \lvert W(A_j)\rvert}

After the transformation, the most vital attribute receives a score of 1.0 and the least important one receives a score of 0.0. We compare the different explainers by inspecting their normalized score distributions and the individual attributes with the highest scores.

Results. We first examine the overall score distributions using the probability density function (PDF) of attribution weights (Figure 4), by dividing the normalized range of weights into discrete bins and measuring the percentage of attributes in each bin. Across both task types, most methods assign very low importance scores to the vast majority of attributes, reserving high scores for only a select few. However, in regression tasks (Figure 4a), Mask Learning exhibits a notably different behavior: it is more “generous,” assigning maximum importance values (in the 0.9–1.0 bin) to a considerably larger proportion of attributes compared to the other explainers.

Figure 4. Score distribution (PDF). Dots show the percentage of attributes within the normalized weight range.

To understand how these scores behave across individual attributes, we plot the individual normalized importance scores as a scatter (Figure 5), where the attributes along the x-axis are ordered by their cumulative normalized weight over all explainers. We observe a general consensus among all methods regarding which attributes are highly important versus those that are negligible. In regression tasks (Figure 5a), the individual explainer scores track closely together, forming a tight and steep decay curve, though Mask Learning maintains high scores for a wider range of attributes before decaying. Conversely, in classification tasks (Figure 5b), the scores are noticeably more dispersed, indicating lower explainer agreement on the exact importance magnitudes of the top attributes.

Figure 5. Normalized score scatter grid. Attributes along the x-axis are sorted by collective importance.

Finally, we construct an ensemble consensus score grid (Figure 6a and Figure 6b) to inspect the specific attributes driving the predictions. To do so, we isolate the union of attributes that rank within the top k=15k = 15 of at least one method and display the top 10 attributes from this union, ordered by the number of explainers that included them. Within each panel cell, we present the explainer’s

Figure 6. Consensus min-max normalized score grids across all tasks (top-15 evaluation, displaying top 10 consensus attributes). Cells display individual ranks (#) and bar widths represent normalized scores. Data type are in brackets: [N] Numerical, [C] Categorical, [D] Date, and [T] Text. Alphabetical tie-breaking may affect the exact top-kk choices (See § 5.2).

ordinal rank position (#) and the normalized score (encoded by the bar width). As previously noted, alphabetical tie-breaking is applied when attributes share identical importance scores. It is critical to keep this tie-breaking strategy in mind, as it heavily influences the exact top-kk choices when an explainer (such as Mask Learning in regression tasks) assigns the identical maximum score of 1.0 to a large number of attributes. These grids corroborate our previous findings while providing semantic insights into the model’s logic.

An inspection of these top-ranked attributes suggests that the explainers tend to prioritize historical indicators that directly relate to the target. For instance, in the rel-f1 driver-position regression task under the RelGT architecture, all explainers agree that res.posOrder (the finishing position in previous races) is the most critical attribute (Mask Learning also assigns it the maximum score of 1.0, placing it at #4 due to alphabetical tie-breaking). This aligns with the intuition that a driver’s past finishing positions are strong indicators of their future average position.

Similarly, in the rel-event user-attendance task under the RelGT architecture, we observe a strong preference for behavioral signals. Here, event_attendees.stat, representing the user’s historical RSVP responses (invited, yes, maybe, no), is unanimously identified as the leading attribute. This aligns with the intuition that a participant’s future event attendance is strongly influenced by their past attendance behavior.

Conclusions. The manner in which explainers distribute importance scores is driven by the predictive task. Regression tasks foster a strong consensus where multiple explainers agree on both the identity and the steep decay of the most critical attributes, providing practitioners with high confidence in the derived explanations. While Mask Learning tends to be more generous with its score distributions in these settings, its ordinal alignment across the top attributes remains consistent with the other methods. In contrast, classification tasks yield more scattered and inconsistent score distributions, reflecting higher uncertainty about the explanations. Despite the distribution differences, when methods converge on specific semantic attributes, such as a driver’s historical finishing order or a user’s past RSVP behavior, they reveal highly logical, intuitive insights into the underlying model’s predictive mechanisms.

explanation methods, with the exception of Mask Learning, which relies on its own permutation-based ablation during optimization.

Fidelity Metrics Evaluation

Objectives. Fidelity metrics are a widely used method to evaluate AI explainability tools [75]. fidelity aims to quantify explanation faithfulness, or, how well do the explanations capture and reflect the prediction model’s decisions. Following standard conventions [75], Fidelity+^{+} evaluates the necessity of the top-ranked attributes by measuring the absolute prediction shift when those specific attributes are ablated. Conversely, Fidelity−^{-} assesses the sufficiency of the top attributes by measuring the prediction shift when only those attributes are retained and the rest are ablated. We now investigate to what extent the differences and similarities among explanation methods are reflected in their fidelity scores (Q3Q_3).

Evaluation methodology. Across both classification and regression, fidelity (of either type) is evaluated via the absolute prediction shift induced on model output predictions. To enable the comparison over schemas with varying numbers of attributes, we evaluate the fidelity across relative kk values (5% to 100%) for schemas with a large number of data attributes, and with absolute counts for schemas with fewer attributes. It is important to note that our fidelity evaluation employs the same deterministic ablation strategy used by all

Results. We examine how explanation subsets impact model performance by comparing Fidelity+^{+} and Fidelity−^{-} scores across varying top-kk subsets in all combinations of tasks and models (Figure 7).

Figure 7. Explainer fidelity in regression (top 2 rows) and classification (bottom 2 rows) tasks, over HGS (left) and RelGT (right). Bars represent Fidelity+^{+} (necessity, higher is better) and Fidelity−^{-} (sufficiency, lower is better) across varying top-kk attribute subsets. The maximum y-axis value for each subplot is annotated in its top-left corner.

Overall, the fidelity scores are consistent with the results of our ranking analyses (Section 5.2). Methods that produce similar attribute rankings generally yield similar fidelity scores. For example, in the rel-trial study-adverse regression task under HGS, Single Column Ablation, Shapley-MC, and Shapley-KS achieve high ranking similarity, while Mask Learning receives very low agreement scores. This behavior is reflected in the fidelity metrics: the three aligned methods yield closely matched Fidelity+^{+} and Fidelity−^{-} scores, whereas Mask Learning produces significantly different fidelity scores. A similar pattern emerges in the rel-arxiv paper-citation classification task under RelGT, where Mask Learning diverges significantly in both ranking and fidelity across most kk values. The only exception occurs at k=1k = 1, where all four explainers reach full ranking agreement, which is directly mirrored by identical fidelity scores across all methods at that specific point.

While fidelity scores validate our previous findings, they evaluate the predictive utility of a subset rather than its exact content. Thus, fidelity can differ from ranking alignment. As aforesaid, Mask Learning’s tendency to assign identical maximum scores can trigger alphabetical tie-breaking, causing apparent fidelity deviations at small kk values (e.g., rel-arxiv author-publication at k=1k = 1). Furthermore, different subsets can sometimes have the same predictive power. For instance, in the rel-trial study-adverse regression task under RelGT at k=20%k = 20\%, we observe a ranking disagreement between Shapley-KS and Mask Learning (with a similarity score of 0.68), yet their fidelity is tightly clustered.

Conclusions. Fidelity metrics provide a valuable perspective that is broadly consistent with our direct explainer comparisons: Single Column Ablation and the Shapley-based approximations often group together in their predictive degradation profiles, while Mask Learning exhibits distinct behavior. However, as fidelity evaluates the predictive utility of a set rather than its specific composition, it does not replace direct ordinal and distributional comparisons. Similar fidelity can sometimes stem from different attributes. Thus, pairing fidelity with dedicated ranking and distributional evaluations provides a more comprehensive picture of explainer agreement.

Conclusions

We presented a systematic study of importance attribution methods for database columns in relational deep learning. We considered four representative methods and developed quantitative analyses and visualizations for comparing both the rankings they induce and the distributions of their importance scores. We applied these methods across multiple datasets and prediction tasks using two relational deep learning architectures, HGS and RelGT, and examined their relationship to conventional fidelity measures.

Our results demonstrate that the extent of agreement among explanation methods is context-dependent. Specifically, explainer agreement is driven by the nature of the predictive task, with regression tasks yielding a much higher consensus than classification tasks. Furthermore, the agreement depends on the underlying mathematical objective of the explainer. While Single Column Ablation and the two Shapley approximations often align closely, Mask Learning frequently diverges, reflecting its distinct focus on collective subset sufficiency rather than that individual marginal contributions.

Our findings do not imply that any one explanation method is universally preferable. Rather, they suggest that importance scores should be interpreted in light of the method that produces them. In cases where explanations play a substantive role, a system may benefit from presenting results from more than one method, or at least from clarifying the essence and notion of importance captured by the selected method. Similarly, scientific studies that draw conclusions from attribute-importance scores may strengthen their conclusions by examining whether they persist across alternative explanation methods. Finally, our results motivate considering the stability of explanations across different predictive tasks as a complementary aspect of model evaluation, alongside predictive performance. We view these as directions for practice and future investigation, rather than as general requirements.

Our study opens several directions for future investigation. First, while our empirical results often showed strong alignment between computationally expensive Shapley approximations and the highly efficient single-column ablation, a critical avenue for future work is identifying the specific dataset characteristics, model complexities, or problem domains where the rigorous game-theoretic properties of the Shapley value provide a tangible advantage that justifies its computational overhead. Second, as the ultimate goal of explainability is to provide actionable insights to users, our current evaluation is limited to quantitative algorithmic metrics. Future research should incorporate human-centric case studies to determine which mathematical notions of importance best align with user intuition and domain expertise. Finally, while our evaluation framework is broadly applicable to any predictive model operating over relational data (with the exception of Mask Learning, which requires architecture-specific integration), our experiments focused on graph-based neural networks. An important next step is to expand this methodology to encompass emerging architectures, such as relational foundation models and advanced tabular approaches (e.g., TabPFN), across a wider spectrum of relational datasets.

References

A Proof of Theorem 4.1

We now prove Theorem 4.1. We consider combined complexity, where the schema is part of the input, as under data complexity, the schema, and, in particular, the number of data attributes, is fixed; hence, the exact Shapley value can be computed in polynomial time in data complexity by enumerating all attribute subsets.

In the proofs below, we use the following equivalent subset-based formula for the Shapley value:

W(Ai)=∑S⊆dat⁡(S)∖{Ai}∣S∣!(N−∣S∣−1)!N![ν(S∪{Ai})−ν(S)].W(A_i)=\sum_{S\subseteq\operatorname{dat}(S)\setminus\{A_i\}}\frac{|S|!(N-|S|-1)!}{N!}\left[\nu(S\cup\{A_i\})-\nu(S)\right].

For simplicity, the reductions below use the Zero ablation strategy, in which every data attribute excluded from a coalition is replaced by 0. The proofs also apply to mean imputation, which is the strategy used in our experiments for numerical attributes; we explain the required adjustment after each proof.

Theorem 4.1. Computing the Shapley value of an attribute under the characteristic function ν\nu is #P-hard. This holds already for a linear model over a single-relation schema. It also holds when the schema consists of multiple relations, all of bounded arity, and the model is a message passing GNN with a single layer and no non-linear activations.

We prove Theorem 4.1 by considering the two restricted schema settings separately. We first establish hardness for a schema consisting of a single relation.

Lemma A.1. Computing the Shapley value of an attribute under the global characteristic function ν\nu is #P-hard when the prediction model is linear and the schema consists of a single relation.

Proof. We give a polynomial-time Turing reduction from the #P-hard problem #SUBSETSUM. An instance consists of a multiset B={{b1,…,bn}}B=\{\{b_1,\ldots,b_n\}\} of positive integers and a target integer TT, and the task is to count the subsets B′⊆BB'\subseteq B whose elements sum to TT. We may assume that ∑i=1nbi≥T\sum_{i=1}^{n}b_i\ge T, since otherwise the answer is 0.

For each m∈{0,…,n}m\in\{0,\ldots,n\}, we construct a database DmD_m over the same schema SS, which consists of a single relation RR. The relation Dm(R)D_m(R) contains one tuple t(m)t^{(m)}; its primary-key attribute has an arbitrary value, and there are no foreign-key dependencies. The fixed set of data attributes contains 2n+22n+2 numerical attributes:

  1. Item attributes: A1,…,AnA_1,\ldots,A_n, where t(m)[Ai]=bit^{(m)}[A_i]=b_i.

  2. Probe attribute: AprobeA_{\mathrm{probe}}, where t(m)[Aprobe]=1t^{(m)}[A_{\mathrm{probe}}]=1.

  3. Offset attribute: ATA_T, where t(m)[AT]=Tt^{(m)}[A_T]=T.

  4. Heavy and padding attributes: AH1,…,AHnA_{H_1},\ldots,A_{H_n}, where

t(m)[AHj]={bH=∑i=1nbi+T+100,j≤m,0,j>m.t^{(m)}[A_{H_j}]= \begin{cases} b_H=\sum_{i=1}^{n}b_i+T+100, & j\le m,\\ 0, & j>m. \end{cases}

Thus, the first mm of these attributes are heavy and the remaining n−mn-m are padding attributes. The evaluation set is V(m)={t(m)}V^{(m)}=\{t^{(m)}\}, and let Dm,SD_{m,S} denote the perturbed database obtained by applying Zero ablation to every data attribute outside the coalition SS.

We use the same linear prediction model ff for every DmD_m. Specifically, ff assigns weight +1+1 to every item attribute and to the probe attribute, and weight −1-1 to the offset and all heavy/padding attributes. The padding attributes have value 0, so they do not affect any prediction. Deleting them from a uniformly random permutation leaves a uniformly random permutation of the remaining Nm:=n+m+2N_m:=n+m+2 attributes, so the Shapley calculation below is unchanged. Let ν(m)\nu^{(m)} denote the characteristic function induced by DmD_m, ff, and V(m)={t(m)}V^{(m)}=\{t^{(m)}\}; it is simply the absolute prediction shift on t(m)t^{(m)}. Hence, for every coalition SS after omitting the padding attributes,

ν(m)(S)=∣f(t(m),Dm)−f(t(m),Dm,S)∣=∣(∑i=1nbi+1−T−mbH)−(∑Ai∈Sbi+1[Aprobe∈S]−T⋅1[AT∈S]−∑AHj∈SbH)∣=∣∑Ai∉Sbi+1[Aprobe∉S]−T⋅1[AT∉S]−∑AHj∉SbH∣.\begin{aligned} \nu^{(m)}(S)=\left|f(t^{(m)},D_m)-f(t^{(m)},D_{m,S})\right| \\ &=\left|\left(\sum_{i=1}^{n}b_i+1-T-mb_H\right)-\left(\sum_{A_i\in S}b_i+\mathbb{1}[A_{\mathrm{probe}}\in S]-T\cdot\mathbb{1}[A_T\in S]-\sum_{A_{H_j}\in S}b_H\right)\right| \\ &=\left|\sum_{A_i\notin S}b_i+\mathbb{1}[A_{\mathrm{probe}}\notin S]-T\cdot\mathbb{1}[A_T\notin S]-\sum_{A_{H_j}\notin S}b_H\right|. \end{aligned}

Define

XS(m):=∑Ai∉Sbi−T⋅1[AT∉S]−∑AHj∉SbH.X_S^{(m)}:=\sum_{A_i\notin S}b_i-T\cdot\mathbb{1}[A_T\notin S]-\sum_{A_{H_j}\notin S}b_H.

Thus,

ν(m)(S)=∣XS(m)+1[Aprobe∉S]∣.\nu^{(m)}(S)=\left|X_S^{(m)}+\mathbb{1}[A_{\mathrm{probe}}\notin S]\right|.

We now compute the Shapley value of AprobeA_{\mathrm{probe}}. Fix a predecessor coalition

S⊆{A1,…,An,Aprobe,AT,AH1,…,AHm}∖{Aprobe}.S\subseteq\{A_1,\ldots,A_n,A_{\mathrm{probe}},A_T,A_{H_1},\ldots,A_{H_m}\}\setminus\{A_{\mathrm{probe}}\}.

Its marginal contribution is

Δprobe(S)=ν(m)(S∪{Aprobe})−ν(m)(S)=∣XS(m)∣−∣XS(m)+1∣.\Delta_{\mathrm{probe}}(S)=\nu^{(m)}(S\cup\{A_{\mathrm{probe}}\})-\nu^{(m)}(S)=|X_S^{(m)}|-|X_S^{(m)}+1|.

Since XS(m)X_S^{(m)} is an integer,

Δprobe(S)={−1,XS(m)≥0,1,XS(m)≤−1.\Delta_{\mathrm{probe}}(S)= \begin{cases} -1, & X_S^{(m)}\ge0,\\ 1, & X_S^{(m)}\le-1. \end{cases}

We next characterize exactly when XS(m)≥0X_S^{(m)}\ge0. If any heavy attribute is excluded from SS, then

XS(m)≤∑i=1nbi−bH<0.X_S^{(m)}\le\sum_{i=1}^{n}b_i-b_H<0.

Thus, all heavy attributes must belong to SS. Subject to this condition, if AT∈SA_T\in S, then

XS(m)=∑Ai∉Sbi≥0.X_S^{(m)}=\sum_{A_i\notin S}b_i\ge0.

If instead AT∉SA_T\notin S, then

XS(m)=∑Ai∉Sbi−T,X_S^{(m)}=\sum_{A_i\notin S}b_i-T,

which is nonnegative exactly when the excluded item attributes have total value at least TT. Therefore, XS(m)≥0X_S^{(m)}\ge0 if and only if all heavy attributes are in SS and either (i) AT∈SA_T\in S, or (ii) AT∉SA_T\notin S and the excluded item attributes sum to at least TT.

For a predecessor coalition SS as above, the Shapley formula assigns its marginal contribution the weight

γ(m)(S):=∣S∣!(Nm−∣S∣−1)!Nm!.\gamma^{(m)}(S):=\frac{|S|!(N_m-|S|-1)!}{N_m!}.

Equivalently, γ(m)(S)\gamma^{(m)}(S) is the probability that, in a uniformly random permutation of all NmN_m attributes, the set of attributes appearing before AprobeA_{\mathrm{probe}} is exactly SS. Hence, the weights γ(m)(S)\gamma^{(m)}(S) over all predecessor coalitions sum to 1.

Let

Γ≥T(m):=∑S⊆{A1,…,An,AT,AH1,…,AHm}XS(m)≥0γ(m)(S)\Gamma_{\geq T}^{(m)} := \sum_{\substack{S \subseteq\{A_1,\ldots,A_n,A_T,A_{H_1},\ldots,A_{H_m}\} \\ X_S^{(m)} \geq0}} \gamma^{(m)}(S)

be the total Shapley weight of the predecessor coalitions for which XS(m)≥0X_S^{(m)} \geq0. As shown above, the marginal contribution of AprobeA_{\mathrm{probe}} is −1-1 for precisely these coalitions and is 11 for all remaining predecessor coalitions. Therefore,

W(m)(Aprobe)=−Γ≥T(m)+(1−Γ≥T(m))=1−2Γ≥T(m)W^{(m)}(A_{\mathrm{probe}}) = -\Gamma_{\geq T}^{(m)} + (1-\Gamma_{\geq T}^{(m)}) = 1 - 2\Gamma_{\geq T}^{(m)}

and therefore

Γ≥T(m)=1−W(m)(Aprobe)2.\Gamma_{\geq T}^{(m)} = \frac{1-W^{(m)}(A_{\mathrm{probe}})}{2}.

For k∈{0,…,n}k \in\{0,\ldots,n\}, let c≥Tkc_{\geq T}^k denote the number of subsets B′⊆BB' \subseteq B of size kk whose elements sum to at least TT. We now express Γ≥T(m)\Gamma_{\geq T}^{(m)} in terms of these unknown counts.

First, consider predecessor coalitions that contain ATA_T and all mm heavy attributes. For such a coalition, let kk be the number of item attributes excluded from SS. Then SS contains the remaining n−kn-k item attributes, and hence

∣S∣=m+n−k+1.|S| = m+n-k+1.

Its Shapley weight is therefore

(m+n−k+1)!k!(n+m+2)!.\frac{(m+n-k+1)!k!}{(n+m+2)!}.

There are (nk)\binom{n}{k} choices for the kk excluded item attributes. Moreover, when AT∈SA_T \in S and all heavy attributes belong to SS, we have XS(m)≥0X_S^{(m)} \geq0 regardless of which item attributes are excluded. Hence, the total contribution of these coalitions to Γ≥T(m)\Gamma_{\geq T}^{(m)} is the known quantity

Kbase(m):=∑k=0n(nk)(m+n−k+1)!k!(n+m+2)!.K_{\mathrm{base}}^{(m)} := \sum_{k=0}^{n} \binom{n}{k}\frac{(m+n-k+1)!k!}{(n+m+2)!}.

Now consider predecessor coalitions that exclude ATA_T, contain all heavy attributes, and exclude exactly kk item attributes. Such a coalition has size m+n−km+n-k. Consequently, its Shapley weight is

Cm,k:=(m+n−k)!(k+1)!(n+m+2)!.C_{m,k} := \frac{(m+n-k)!(k+1)!}{(n+m+2)!}.

By the characterization of XS(m)≥0X_S^{(m)} \geq0, precisely c≥Tkc_{\geq T}^k choices of the kk excluded item attributes contribute. Therefore,

Γ≥T(m)=Kbase(m)+∑k=0nCm,kc≥Tk.\Gamma_{\geq T}^{(m)} = K_{\mathrm{base}}^{(m)} + \sum_{k=0}^{n} C_{m,k}c_{\geq T}^k.

For each m∈{0,…,n}m \in\{0,\ldots,n\}, we therefore obtain the equation

Γ≥T(m)−Kbase(m)=∑k=0nCm,kc≥Tk.\Gamma_{\geq T}^{(m)} - K_{\mathrm{base}}^{(m)} = \sum_{k=0}^{n} C_{m,k}c_{\geq T}^k.

Evaluating the Shapley value of the probe for each m=0,…,nm=0,\ldots,n gives n+1n+1 linear equations in the n+1n+1 unknowns

c≥T0,…,c≥Tn.c_{\geq T}^0,\ldots,c_{\geq T}^n.

Let CC be the (n+1)×(n+1)(n+1) \times(n+1) coefficient matrix whose (m,k)(m,k)-entry is Cm,kC_{m,k}. To recover the unknown counts c≥Tkc_{\geq T}^k, it remains to show that CC is invertible. Multiply row mm by (n+m+2)!(n+m+2)!, divide column kk by (k+1)!(k+1)!, and then reverse the order of the columns. These are all invertible operations, and they transform CC into the matrix HH with

Hm,k=(m+k)!,0≤m,k≤n.H_{m,k} = (m+k)!, \qquad0 \leq m,k \leq n.

As shown in [6], the determinant of HH is

det⁡(H)=∏i=0n(i!)2≠0.\det(H) = \prod_{i=0}^{n}(i!)^2 \ne0.

Hence HH, and therefore CC, is invertible. We can thus recover all the values c≥Tkc_{\geq T}^k.

To recover the number of subsets of a given size summing exactly to TT, repeat the same computation with threshold T+1T+1, obtaining ck,≥T+1c_{k,\geq T+1}, and set

ck=c≥Tk−c≥T+1k.c_k = c_{\geq T}^k-c_{\geq T+1}^k.

If ∑i=1nbi<T+1\sum_{i=1}^{n} b_i < T+1, then all c≥T+1kc_{\geq T+1}^k are simply 0. Therefore, the number of subsets of BB whose elements sum exactly to TT is

∑k=0n(c≥Tk−c≥T+1k).\sum_{k=0}^{n}\left(c_{\geq T}^k-c_{\geq T+1}^k\right).

The construction uses polynomially many oracle calls, all numerical values have polynomial bit length, and the resulting rational linear systems can be solved in polynomial time. This concludes our proof.

□\square

Mean imputation. The same reduction works when an excluded numerical attribute is replaced by its mean rather than by 0. For each database DmD_m above, add two auxiliary tuples to RR, neither of which belongs to the evaluation set V(m)V^{(m)}: in the first, every data attribute whose value in t(m)t^{(m)} is vv is assigned the value −v-v, and in the second, every data attribute is assigned the value 0. Give the auxiliary tuples fresh primary-key values. Thus, for every data attribute, its three values in RR are v,−v,0v,-v,0, and hence its mean is 0. Mean imputation therefore induces exactly the same perturbed values on the evaluated tuple t(m)t^{(m)} as Zero ablation. The two auxiliary tuples do not affect the prediction on t(m)t^{(m)}, because the linear model used in the reduction depends only on the attributes of the tuple being evaluated. Consequently, the characteristic function and the Shapley value of AprobeA_{\mathrm{probe}} are unchanged.

Hardness for bounded arity. While the previous lemma establishes hardness for a schema consisting of a single relation, we now show that computing the Shapley value remains #P-hard even when the number of attributes in each relation is bounded by a constant, while the number of relations is unbounded. For this result, the prediction model must aggregate information across relations. We therefore first formalize the message-passing GNN (MPGNN) architecture used in the reduction.

Given a database DD over SS, we represent DD as a heterogeneous graph in the standard manner: every tuple is represented by a node, whose type is the relation containing the tuple. For every foreign-key dependency

λ:R[X]⊆key⁡(R′)\lambda: R[X] \subseteq\operatorname{key}(R')

and every pair of tuples u∈D(R)u \in D(R) and u′∈D(R′)u' \in D(R') satisfying u[X]=u′[key⁡(R′)]u[X] = u'[\operatorname{key}(R')], the graph contains an edge from uu to u′u'. We allow message passing both along this edge and in the reverse direction. Thus, a message-passing edge type is determined by a foreign-key dependency λ\lambda together with an orientation o∈{in,out}o \in\{\mathrm{in},\mathrm{out}\}.

An MPGNN consists of KK message-passing layers. For every tuple uu and every layer ℓ∈{0,…,K}\ell\in\{0,\ldots,K\}, let zu(ℓ)z_u^{(\ell)} denote the representation of the node corresponding to uu. The initial representation is obtained using a relation-specific encoder applied to the data attributes of the tuple. Thus, for a tuple uu of relation RR,

zu(0)=Enc⁡R(u).z_u^{(0)} = \operatorname{Enc}_R(u).

For every layer ℓ∈{1,…,K}\ell\in\{1,\ldots,K\}, messages are aggregated separately for each foreign-key dependency and orientation. Let Nλo(u)N_{\lambda}^{o}(u) denote the neighbors of uu connected through dependency λ\lambda in orientation oo. We define

mλ,o(ℓ)(u)=AGG⁡λ,o(ℓ)({zu′(ℓ−1)∣u′∈Nλo(u)}),m_{\lambda,o}^{(\ell)}(u) = \operatorname{AGG}_{\lambda,o}^{(\ell)}\left(\left\{z_{u'}^{(\ell-1)} \mid u' \in N_{\lambda}^{o}(u)\right\}\right),

where AGG⁡λ,o(ℓ)\operatorname{AGG}_{\lambda,o}^{(\ell)} is a permutation-invariant aggregation function.

The representation of uu is then updated by combining its previous representation with the aggregated messages for the different edge types:

zu(ℓ)=UPD⁡R(ℓ)(zu(ℓ−1),{mλ,o(ℓ)(u)}λ∈FK⁡(S), o∈{in,out}),z_u^{(\ell)} = \operatorname{UPD}_{R}^{(\ell)}\left(z_u^{(\ell-1)},\left\{m_{\lambda,o}^{(\ell)}(u)\right\}_{\lambda\in\operatorname{FK}(S),\,o \in\{\mathrm{in},\mathrm{out}\}}\right),

where RR is the relation containing uu and UPD⁡R(ℓ)\operatorname{UPD}_{R}^{(\ell)} is a learnable update function.

Finally, for a target tuple tt of the target relation, the prediction is obtained from its final representation through a task-specific prediction head:

f(t,D)=Head⁡(zt(K)).f(t,D) = \operatorname{Head}\left(z_t^{(K)}\right).

In the reduction below, we use a particularly simple instance of this architecture: K=1K=1, the encoders are identity maps, every aggregation function is SUM, and both the update function and the prediction head are linear.

Lemma A.2. Computing the Shapley value of an attribute under the global characteristic function ν\nu is #P\#\mathrm{P}-hard when the schema consists of multiple relations, all of bounded arity, and the MPGNN consists of a single layer without any non-linear activations.

Proof. We reduce from #SUBSETSUM. Let B={b1,…,bn}B = \{b_1,\ldots,b_n\} and TT be the input instance. For every m∈{0,…,n}m \in\{0,\ldots,n\}, we construct a database DmD_m over the same fixed star-shaped schema SS. The center of the star is a target relation RR containing a single tuple t(m)t^{(m)}. In addition to its primary-key attribute, RR has one data attribute AprobeA_{\mathrm{probe}}, with

t(m)[Aprobe]=1.t^{(m)}[A_{\mathrm{probe}}] = 1.

All remaining data attributes occur in separate relations, each containing a single tuple that references t(m)t^{(m)} through a foreign-key dependency. Specifically, DmD_m contains:

  1. Item relations: for every i∈{1,…,n}i \in\{1,\ldots,n\}, a relation RiR_i whose unique tuple has a data attribute AiA_i with value bib_i;

  1. Offset relation: a relation RTR_T whose unique tuple has a data attribute ATA_T with value TT;

(3) Heavy and padding relations: for every j∈{1,…,n}j \in\{1,\ldots,n\}, a relation RHjR_{H_j} whose unique tuple has a data attribute AHjA_{H_j} with value bHb_H if j≤mj \le m and value 00 otherwise, where

bH=∑i=1nbi+T+100.b_H = \sum_{i=1}^{n} b_i + T + 100.

Thus, the first mm of these relations are heavy and the remaining n−mn-m are padding relations. Each non-target relation has a single-attribute primary key and a single-attribute foreign key referencing the primary key of RR. The foreign-key value of its unique tuple is set to the primary-key value of t(m)t^{(m)}. Hence DmD_m is a valid database, and its tuple-level graph is a star centered at t(m)t^{(m)}. Each non-target relation has three attributes: a primary key, a foreign key, and one data attribute, while RR has two. Thus, every relation has at most three attributes, independently of nn and mm, and the schema is identical for every DmD_m.

The evaluation set is V(m)={t(m)}V^{(m)} = \{t^{(m)}\}, and let Dm,SD_{m,S} denote the perturbed database obtained by applying Zero ablation to every data attribute outside the coalition SS. In particular, structural key attributes are not ablated, so the relational topology is unchanged.

We use the same one-layer MPGNN ff for every DmD_m. It has the form described above: its relation-specific encoders are identity maps and its aggregation functions are SUM. Let λi\lambda_i, λT\lambda_T, and λHj\lambda_{H_j} denote the foreign-key dependencies from the corresponding non-target relations to RR.

Fix a coalition SS, and consider the perturbed database Dm,SD_{m,S}. Let uiu_i, uTu_T, and uHju_{H_j} denote the unique tuples of RiR_i, RTR_T, and RHjR_{H_j}, respectively. Since each of these relations contains a single tuple, the identity encoders and SUM aggregation give

mλi,in(1)(t(m))=zui(0)=bi 1[Ai∈S],i∈{1,…,n},m_{\lambda_i,\mathrm{in}}^{(1)}(t^{(m)}) = z_{u_i}^{(0)} = b_i\,\mathbb{1}[A_i \in S], \qquad i \in\{1,\ldots,n\},
mλT,in(1)(t(m))=zuT(0)=T 1[AT∈S],m_{\lambda_T,\mathrm{in}}^{(1)}(t^{(m)}) = z_{u_T}^{(0)} = T\,\mathbb{1}[A_T \in S],
mλHj,in(1)(t(m))=zuHj(0)={bH 1[AHj∈S],j≤m,0,j>m,j∈{1,…,n}.m_{\lambda_{H_j},\mathrm{in}}^{(1)}(t^{(m)}) = z_{u_{H_j}}^{(0)} = \begin{cases} b_H\,\mathbb{1}[A_{H_j} \in S], & j \le m,\\ 0, & j > m, \end{cases} \qquad j \in\{1,\ldots,n\}.

Similarly, the initial representation of the target tuple is

zt(m)(0)=1[Aprobe∈S].z_{t^{(m)}}^{(0)} = \mathbb{1}[A_{\mathrm{probe}} \in S].

We choose the linear update function at the target tuple to assign coefficient +1+1 to its previous representation and to the messages from the item relations, and coefficient −1-1 to the messages from the offset and heavy/padding relations. Hence,

zt(m)(1)=zt(m)(0)+∑j=1nmλi,in(1)(t(m))−mλT,in(1)(t(m))−∑j=1nmλHj,in(1)(t(m))=1[Aprobe∈S]+∑Ai∈Sbi−T⋅1[AT∈S]−∑1≤j≤mAHj∈SbH.\begin{aligned} z_{t^{(m)}}^{(1)} = z_{t^{(m)}}^{(0)} + \sum_{j=1}^{n}m_{\lambda_i,\mathrm{in}}^{(1)}(t^{(m)}) - m_{\lambda_T,\mathrm{in}}^{(1)}(t^{(m)}) - \sum_{j=1}^{n}m_{\lambda_{H_j},\mathrm{in}}^{(1)}(t^{(m)}) \\ &= \mathbb{1}[A_{\mathrm{probe}} \in S] + \sum_{A_i \in S} b_i - T \cdot\mathbb{1}[A_T \in S] - \sum_{\substack{1 \le j \le m\\ A_{H_j} \in S}} b_H. \end{aligned}

Finally, the prediction head applies unit weight. Therefore,

f(t(m),Dm,S)=∑Ai∈Sbi+1[Aprobe∈S]−T⋅1[AT∈S]−∑1≤j≤mAHj∈SbH.f(t^{(m)},D_{m,S}) = \sum_{A_i \in S} b_i + \mathbb{1}[A_{\mathrm{probe}} \in S] - T \cdot\mathbb{1}[A_T \in S] - \sum_{\substack{1 \le j \le m\\ A_{H_j} \in S}} b_H.

The zero-valued padding relations disappear from this expression. Thus, this is exactly the coalition-dependent prediction function used in the proof of Theorem 4.1. Hence, for every coalition SS, the induced characteristic function ν(m)(S)\nu^{(m)}(S) is identical to that in the previous construction. The reduction now continues exactly as in the proof of Theorem 4.1. □

Mean imputation. The reduction also applies when excluded numerical attributes are replaced by their mean values rather than by zero. For every database DmD_m constructed above, we add two auxiliary copies of each tuple, neither of which belongs to the evaluation set V(m)V^{(m)}. In the first copy, every data attribute whose value in the original tuple is vv is assigned the value −v-v; in the second copy, every data attribute is assigned the value 00. All auxiliary tuples receive fresh primary-key values. We assign the foreign-key values of the auxiliary tuples so that each negated tuple references the corresponding negated tuple in the referenced relation, and each zero tuple references the corresponding zero tuple. Hence, all foreign-key dependencies remain satisfied, and the auxiliary tuples form two components that are disconnected from the component containing the evaluated target tuple t(m)t^{(m)}.

For every numerical data attribute, the three values in its relation are therefore vv, −v-v, and 00, so its mean is 00. Consequently, mean imputation has exactly the same effect as Zero ablation on the component containing t(m)t^{(m)}. Moreover, since the two auxiliary components are disconnected from t(m)t^{(m)}, they do not affect the MPGNN prediction for t(m)t^{(m)}. Thus, for every coalition SS, the perturbed prediction f(t(m),Dm,S)f(t^{(m)},D_{m,S}), and therefore the characteristic function ν(m)(S)\nu^{(m)}(S) and the Shapley value of AprobeA_{\mathrm{probe}}, are identical to those in the Zero-ablation construction. The same reduction therefore establishes #P-hardness under mean imputation.

Monte Carlo Shapley Convergence Plots

As discussed in § 4.2, we employ an empirical termination strategy for the Monte Carlo permutation sampling. The sampling process is empirically terminated once the convergence curve visibly flattens out, indicating that the maximum absolute shift across all attributes has diminished to a negligible noise floor.

Figures 8 and 9 present the empirical convergence curves for all remaining tasks and architectures not shown in the main text. Each plot tracks the absolute difference in estimated scores between consecutive permutation checkpoints (∣Δshapley_value∣|\Delta\text{shapley\_value}|).

Kernel SHAP Convergence Plots

As discussed in § 5.2, to verify that the ranking discrepancies between Shapley-KS and Shapley-MC are not merely artifacts of insufficient sampling, we empirically validated the convergence of the Shapley-KS method across all tasks.

Figures 10 and 11 present the empirical convergence curves for Shapley-KS across all datasets and architectures. Similar to the Monte Carlo evaluation, each plot tracks the absolute difference in the estimated importance scores between consecutive sampling checkpoints (∣Δshap_value∣|\Delta\text{shap\_value}|). The stabilization of these curves confirms that the Shapley-KS estimates have empirically converged within the allocated evaluation budget.

Figure 8. Empirical convergence curves for the Monte Carlo Shapley approximation on the rel-f1 and rel-event datasets. (a) rel-f1, driver-position (HGS); (b) rel-f1, driver-position (RelGT); (c) rel-f1, driver-dnf (HGS); (d) rel-f1, driver-dnf (RelGT); (e) rel-event, user-attendance (HGS); (f) rel-event, user-attendance (RelGT); (g) rel-event, user-repeat (HGS); (h) rel-event, user-repeat (RelGT). The plots show Number of Permutations, ∣Δ|\Delta shapley_value∣|, Mean ∣Δ∣|\Delta| across features, Max ∣Δ∣|\Delta| across features, and Mean ±\pm 1 Std.

Figure 9. Empirical convergence curves for the Monte Carlo Shapley approximation on the rel-trial and rel-arxiv datasets. (a) rel-trial, study-adverse (RelGT); (b) rel-trial, study-outcome (HGS); (c) rel-trial, study-outcome (RelGT); (d) rel-arxiv, paper-citation (HGS); (e) rel-arxiv, paper-citation (RelGT); (f) rel-arxiv, author-publication (HGS); (g) rel-arxiv, author-publication (RelGT). The plots show Number of Permutations, ∣Δ|\Delta shapley_value∣|, Mean ∣Δ∣|\Delta| across features, Max ∣Δ∣|\Delta| across features, and Mean ±\pm 1 Std.

Figure 10. Empirical convergence curves for the Kernel SHAP approximation on the rel-f1 and rel-event datasets. (a) rel-f1, driver-position (HGS); (b) rel-f1, driver-position (RelGT); (c) rel-f1, driver-dnf (HGS); (d) rel-f1, driver-dnf (RelGT); (e) rel-event, user-attendance (HGS); (f) rel-event, user-attendance (RelGT); (g) rel-event, user-repeat (HGS); (h) rel-event, user-repeat (RelGT). The plots show ∣Δ|\Delta shapley_value∣| and Number of Coalitions (subsampled n=1n=1).

Figure 11. (a) rel-trial, study-adverse (HGS); (b) rel-trial, study-adverse (RelGT); (c) rel-trial, study-outcome (HGS); (d) rel-trial, study-outcome (RelGT); (e) rel-arxiv, paper-citation (HGS); (f) rel-arxiv, paper-citation (RelGT); (g) rel-arxiv, author-publication (HGS); (h) rel-arxiv, author-publication (RelGT). Figure 11: Empirical convergence curves for the Kernel SHAP approximation on the rel-trial and rel-arxiv datasets.

References

  1. [1]Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. 2018. Sanity Checks for Saliency Maps. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc.arxiv.org/abs/1810.03292
  2. [2]Chirag Agarwal, Satyapriya Krishna, Eshika Saxena, Martin Pawelczyk, Nari Johnson, Isha Puri, Marinka Zitnik, and Himabindu Lakkaraju. 2022. OpenXAI: Towards a Transparent Evaluation of Model Explanations. In Advances in Neural Information Processing Systems, S. Koyejо, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran Associates, Inc. 15784–15799.arxiv.org/abs/2206.11104
  3. [3]Kенза Amara, Zhitao Ying, Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang. 2022. GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks. In Proceedings of the First Learning on Graphs Conference (PLMR), Vol. 198. PMLR, 44:1–44:23.arxiv.org/abs/2206.09677
  4. [4]Plamen P. Angelov, Eduardo A. Soares, Richard Jiang, Nicholas I. Arnold, and Peter M. Atkinson. 2021. Explainable artificial intelligence: an analytical review. WIREs Data Mining Knowl. Discov. 11, 5 (2021).DOI
  5. [5]Marcelo Arenas, Pablo Barceló, Leopoldo Bertossi, and Mikael Monet. 2023. On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results. Journal of Machine Learning Research 24, 63 (2023), 1–58.
  6. [6]Roland Bacher. 2002. Determinants of matrices related to the Pascal triangle. Journal de Théorie des Nombres de Bordeaux 14 (01 2002).DOI
  7. [7]Pablo Barceló, Alexander Kozachinskiy, Miguel Romero, Bernardo Subercaseaux, and José Verschae. 2025. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations. Proc. ACM Manag. Data 3, 2, Article 97 (June 2025), 26 pages.
  8. [8]Leopoldo E. Bertossi, Benny Kimelfeld, Ester Livshits, and Mikaël Monet. 2023. The Shapley Value in Database Management. SIGMOD Rec. 52, 2 (2023), 6–17.DOI
  9. [9]Umang Bhatt, Adrian Weller, and José M. F. Moura. 2020. Evaluating and Aggregating Feature-based Model Explanations. In IJCAI. ijcai.org, 3016–3022.DOI
  10. [10]Leo Breiman. 2001. Random forests. Machine learning 45, 1 (2001), 5–32.
  11. [11]Riccardo Cappuzzo, Paolo Papotti, and Saravanan Thirumuruganathan. 2020. Creating Embeddings of Heterogeneous Relational Datasets for Data Integration Tasks. In SIGMOD (SIGMOD ’20). ACM, 1335–1349.DOI
  12. [12]Adriane Chapman and H. V. Jagadish. 2009. Why not?. In SIGMOD (SIGMOD ’09). ACM, 523–534.
  13. [13]Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. 2018. Learning to Explain: An Information-Theoretic Perspective on Model Interpretation. In ICML (PLMR), Vol. 80. PMLR, 883–892.arxiv.org/abs/1802.07814
  14. [14]Ian Covert and Su-In Lee. 2021. Improving KernelSHAP: Practical Shapley Value Estimation Using Linear Regression. In AISTATS (PLMR), Vol. 130. PMLR, 3457–3465.
  15. [15]Ian Covert, Scott Lundberg, and Su-In Lee. 2021. Explaining by Removing: A Unified Framework for Model Explanation. Journal of Machine Learning Research 22, 209 (2021), 1–90.arxiv.org/abs/2011.14878
  16. [16]Milan Cvitkovic. 2019. Supervised learning on relational databases with graph neural networks. In ICLR 2019 Workshop on Representation Learning on Graphs and Manifolds.arxiv.org/abs/2002.02046
  17. [17]Dries Debeer and Carolin Strobl. 2020. Conditional permutation importance revisited. BMC bioinformatics 21, 1 (2020), 307.DOI
  18. [18]Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mikaël Monet. 2022. Computing the Shapley Value of Facts in Query Answering. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD ’22). ACM, 1570–1583.arxiv.org/abs/2112.08874
  19. [19]Vijay Prakash Dwivedi, Sri Jaladi, Yangyi Shen, Federico Lopez, Charilaos Kanatsoulis, Rishi Puri, Matthias Fey, and Jure Leskovec. 2026. Relational Graph Transformer. In ICLR, C. Vondrick, B. Harhivan, C. Raffel, L. Pinto, D. Yang, and A. Faust (Eds.), Vol. 2026. 154348–154369.arxiv.org/abs/2505.10960
  20. [20]Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, and Erik Vee. 2004. Comparing and aggregating rankings with ties. In PODS (Paris, France) (PODS ’04). ACM, New York, NY, USA, 47–58.DOI
  21. [21]Ronald Fagin, Ravi Kumar, and Dakshnarmurthi Sivakumar. 2003. Comparing top k lists. SIAM journal on discrete mathematics 17, 1 (2003), 134–160.
  22. [22]Matthias Fey, Weihua Hu, Kexin Huang, Jeriс Lenesson, Rishabh Rajan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. 2024. Position: Relational Deep Learning - Graph Representation Learning on Relational Databases. In ICML (PLMR), Vol. 235. PMLR, 13592–13607.arxiv.org/abs/2312.04615
  23. [23]Matthias Fey and Jan Eric Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. arXiv preprint arXiv:1903.02428 (2019).arxiv.org/abs/1903.02428
  24. [24]Aaron Fisher, Cynthia Rudin, and Francesca Dominici. 2019. All Models are Wrong, but Many are Useful: Learning a Variable’s Importance by Studying an Entire Class of Prediction Models Simultaneously. Journal of Machine Learning Research 20, 177 (2019), 1–81.arxiv.org/abs/1801.01489
  25. [25]R. C. Fong and Andrea Vedaldi. 2017. Interpretable Explanations of Black Boxes by Meaningful Perturbation. In 2017 IEEE International Conference on Computer Vision (ICCV). 3449–3457.DOI
  26. [26]Kareem El Gebaly, Guyayo Feng, Lukasz Golab, Flip Korn, and Diveh Srivastava. 2018. Explanation Tables. IEEE Data Eng. Bull. 41, 3 (2018), 43–51.
  27. [27]Alexandros V. Gerbessiotis. 2025. A survey of Chernoff and Hoeffding bounds. arXiv:2506.15612 [cs.DM].
  28. [28]Boris Glavic. 2021. Data Provenance - Origins, Applications, Algorithms, and Models. Foundations and Trends® in Databases 9, 3-4 (2021), 209–441.DOI
  29. [29]Boris Glavic, Alexandra Meliou, and Sudeepa Roy. 2021. Trends in Explanations: Understanding and Debugging Data-driven Systems. Found. Trends Databases 11, 3 (Aug. 2021), 226–318.DOI
  30. [30]Yury Grinsztajn, Ivan Ruvachev, Valentin Khrulkov, and Artem Babenko. 2021. Revisiting deep learning models for tabular data. Advances in neural information processing systems 34 (2021), 18932–18943.
  31. [31]Todd J. Green and Val Tannen. 2017. The Semiring Framework for Database Provenance. In PODS (PODS ’17). ACM, 93–99.DOI
  32. [32]Léo Grinsztajn, Klemens Flöge, Oscar Key, Felix Birkel, Philipp Jund, Brendan Roof, Mihir Manium, Shi Bin Hoo, Magnus Bühler, Anurag Garg, Dominik Safaric, Jake Robertson, Benjamin Jäger, Simone Alessi, Adrian Hayler, Vladyslav Moroshan, Lennart Pruckner, Philipp Singer, Alan Arazi, Julien Siems, Jan Hendrik Metzen, Georg Grab, Nick Erickson, Siyuan Guo, Eliott Kalfon, Simon Bing, David Salinas, Clara Cornu, Lilly Charlotte Wehrhahn, Diana Kruchkova, Kursat Kaya, Lydia Sidhoum, Marie Salmon, Jerry Chen, Madelon Hulsebоs, Yann LeCun, Samuel Müller, Bernhard Schölkopf, Sauraj Gambhir, Noah Hollmann, and Frank Hutter. 2026. TabPFN-3: Technical Report. arXiv:2605.13986 [cs.LG]arxiv.org/abs/2605.13986
  33. [33]Martin Grohe, Benny Kimelfeld, Peter Lindner, and Christoph Standke. 2024. The Importance of Parameters in Database Queries. In ICDT (LIPIcs), Vol. 290. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14:1–14:17.arxiv.org/abs/2401.04606
  34. [34]Justin Gu, Rishabh Ranjan, Chariлаos Kanatsoulis, Haiming Tang, Martin Jurkovic, Valter Hudovernik, Mark Znidar, Pranshu Chaturvedi, Parth Shroff, Fengyu Li, and Jure Leskovec. 2026. RelBench v2: A Large-Scale Benchmark and Repository for Relational Data. arXiv:2602.12606 [cs.LG]
  35. [35]Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri, Franco Turini, Fosca Giannotti, and Dino Pedreschi. 2018. A Survey of Methods for Explaining Black Box Models. ACM Comput. Surv. 51, 5, Article 93 (Aug. 2018), 42 pages. https://doi.org/10.1145/3236009
  36. [36]Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017).arxiv.org/abs/1706.02216
  37. [37]Anna Hedström, Leander Weber, Daniel Krakowczyk, Dilyara Bareeva, Franz Motzkus, Wojciech Samek, Sebastian Lapuschkin, and Marina M.-C. Höhne. 2023. Quantus: An Explainable AI Toolkit for Responsible Evaluation of Neural Network Explanations and Beyond. J. Mach. Learn. Res. 24 (2023), 34:1–34:11.arxiv.org/abs/2202.06861
  38. [38]Noah Hollmann, Samuel Müller, Katharina Eggensperger, and Frank Hutter. 2023. TabPFN: A Transformer That Solves Small Tabular Classification Problems in a Second. In ICLR. OpenReview.net.arxiv.org/abs/2207.01848
  39. [39]Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. 2019. A Benchmark for Interpretability Methods in Deep Neural Networks. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc.arxiv.org/abs/1806.10758
  40. [40]Valter Hudovernik, Federico López, Vid Kocijan, Akihiro Nitta, Jan Eric Lenssen, Jure Leskovec, and Matthias Fey. 2026. KumoRFM-2: Scaling Foundation Models for Relational Learning. arXiv:2604.12596 [cs.LG]
  41. [41]Prajakta Kalmegh, Shivnath Babu, and Sudeepa Roy. 2018. iQCAR: Inter-Query Contention Analyzer. In Proceedings of the ACM Symposium on Cloud Computing (SoCC ’18). ACM, 532.DOI
  42. [42]James Max Kanter and Kalyan Veeramachaneni. 2015. Deep feature synthesis: Towards automating data science endeavors. In DSAA. IEEE, 1–10.DOI
  43. [43]Satyapriya Krishna, Tessa Han, Alex Gu, Steven Wu, Shahin Jabbari, and Himabindu Lakkaraju. 2024. The Disagreement Problem in Explainable Machine Learning: A Practitioner’s Perspective. Transactions on Machine Learning Research (2024).arxiv.org/abs/2202.01602
  44. [44]Seokki Lee, Bertram Ludäscher, and Boris Glavic. 2020. Approximate summaries for why and why-not provenance. Proc. VLDB Endow. 13, 6 (Feb. 2020), 912–924.DOI
  45. [45]Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag. 2020. The Shapley Value of Tuples in Query Answering. In 23rd International Conference on Database Theory (ICDT 2020) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 155. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 20:1–20:19. https://doi.org/10.4230/LIPIcs.ICDT.2020.20
  46. [46]Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag. 2021. Query Games in Databases. SIGMOD Rec. 50, 1 (June 2021), 78–85.DOI
  47. [47]Antonio Longa, Steve Azzolini, Gabriele Santin, Giulia Celencetti, Pietro Lio, Bruno Lepri, and Andrea Passerini. 2025. Explaining the Explainers in Graph Neural Networks: a Comparative Study. ACM Comput. Surv. 57, 5, Article 120 (Jan. 2025), 37 pages.DOI
  48. [48]Yuval Lev Lubarsky, Dean Light, Boaz Berger, Shunit Agmon, and Benny Kimelfeld. 2026. Incorporating Deep Learning Design in Database Queries. CoRR abs/2605.24207 (2026). Tabular Data Analysis Workshop at VLDB.arxiv.org/abs/2605.24207
  49. [49]Scott M M Lundberg and Su-In Lee. 2017. A Unified Approach to Interpreting Model Predictions. In Advances in Neural Information Processing Systems, Vol. 30. Curran Associates, Inc.arxiv.org/abs/1705.07874
  50. [50]Joao Marques-Silva. 2023. Logic-Based Explainability in Machine Learning. Springer Nature Switzerland, 24–104.arxiv.org/abs/2211.00541
  51. [51]Je Meyer, Tomasz Paczewlski, Afreen Shaikh, Mahmoud Mohammadi, Dinesh Kattupurthur Ramprasa th, Karan Paresh, Roshan Reddy Upendra, and Mark Li. 2026. Relational In-Context Learning on Structured Data via Neighborhood Aggregation and Structural Information (Extended Abstract). In AAAI Summer Symposia.
  52. [52]Zhengjie Miao, Qitian Zeng, Chenjie Li, Boris Glavic, Oliver Kennedy, and Sudeepa Roy. 2019. CAPE: explaining outliers by counterbalancing. Proc. VLDB Endow. 12, 12 (Aug. 2019), 1806–1809.DOI
  53. [53]Christoph Molnar. 2025. Interpretable Machine Learning (3rd ed.). Accessed: 2025.
  54. [54]Christoph Molnar, Gunnar König, Bernd Bischl, and Giuseppe Casalicchio. 2024. Model-agnostic feature importance and effects with dependent features: a conditional subgroup approach. Data Min. Knowl. Discov. 38, 5 (2024), 2903–2941.DOI
  55. [55]Claudia Perlich and Foster J. Provost. 2006. Distribution-based aggregation for relational learning with identifier attributes. Mach. Learn. 62, 1-2 (2006), 65–105.DOI
  56. [56]Rishabh Ranjan, Valter Hudovernik, Mark Znidar, Charilaos Kananoulis, Roshan Upendra, Mahmoud Mohammadi, Joe Meyer, Tom Paczewlski, Carlos Gue strin, and Jure Leskovec. 2026. Relational Transformer: Toward Zero-Shot Foundation Models for Relational Data. In ICLR, C. Vondrik, B. Hariharan, C. Raffel, L. Pinto, D. Yang, and A. Faust (Eds.), Vol. 2026. 69149–69174.arxiv.org/abs/2510.06377
  57. [57]Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. 2016. “Why Should I Trust You?: Explaining the Predictions of Any Classifier. In KDD (KDD ’16). ACM, 1135–1144.arxiv.org/abs/1602.04938
  58. [58]Agapi Rissakis, Ilias Fountalis, Wolfgang Gatterbauer, and Benny Kimelfeld. 2026. Database Views as Explanations for Relational Deep Learning. Proc. VLDB Endow. 19, 7 (2026), 1643–1658.
  59. [59]Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan Eric Lenssen, Yiwen Yuan, Zhecheng Zhang, Xinwei He, and Jure Leskovec. 2024. RelBench: A Benchmark for Deep Learning on Relational Databases. In NeurIPS.arxiv.org/abs/2407.20060
  60. [60]Sudeepa Roy, Laurel Orr, and Dan Suciu. 2015. Explaining query answers with explanation-ready datasets. Proc. VLDB Endow. 9, 4 (Dec. 2015), 348–359.DOI
  61. [61]Sudeepa Roy and Dan Suciu. 2014. A formal approach to finding explanations for database queries. In SIGMOD (SIGMOD ’14). ACM, 1579–1590.DOI
  62. [62]Benedek Rozemberczki, Lauren Watson, Péter Bayer, Hao-Tsung Yang, Olivér Kiss, Sebastian Nilsson, and Erik Thost. 2022. The Shapley Value in Machine Learning. In IJCAI, Lud De Raedt (Ed.). IJCAI, 5572–5579. Survey Track.arxiv.org/abs/2202.05594
  63. [63]Wojciech Samek and Klaus-Robert Müller. 2019. Towards explainable artificial intelligence. In Explainable AI: interpreting, explaining and visualizing deep learning. Springer, 5–22.DOI
  64. [64]Erich Schubert and Michael Gertz. 2018. Numerically stable parallel computation of (co-) variance. In Proceedings of the 36th international conference on scientific and statistical database management. 1–12.DOI
  65. [65]Lloyd S Shapley. 1953. A Value for n-Person Games. In Contributions to the Theory of Games II, Harold W. Kuhn and Albert W. Tucker (Eds.). Princeton University Press, Princeton, 307–317.
  66. [66]Arie Soeteman, Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, and Moritz Schönherr. 2026. Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data. CoRR abs/2606.11946 (2026).DOI
  67. [67]Mukund Sundararajan, Ankur Taly, and Qiqi Yan. 2017. Axiomatic Attribution for Deep Networks. In ICML (PLMR), Vol. 70. PMLR, 3319–3328.arxiv.org/abs/1703.01365
  68. [68]Jan Tönshoff, Neta Friedman, Martin Grohe, and Benny Kimelfeld. 2023. Stable Tuple Embeddings for Dynamic Databases. In ICDE. IEEE, 1286–1299.
  69. [69]Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. 2022. On the Tractability of SHAP Explanations. J. Artif. Int. Res. 74 (Sept. 2022), 36.
  70. [70]Minjie Wang, Quan Gan, David Wipf, Zhenkun Cai, Ning Li, Jianheng Tang, Yanlin Zhang, Zihua Zhang, Zunyu Mao, Yakun Song, Yanbo Wang, Jiaheng Li, Han Zhang, Guang Yang, Xiao Qin, Chuan Lei, Muhan Zhang, Weinan Zhang, Christos Faloutsos, and Zheng Zhang. 2024. 4DBInfer: A 4D Benchmarking Toolbox for Graph-Centric Predictive Modeling on RDBs. In Advances in Neural Information Processing Systems, Vol. 37. Curran Associates, Inc., 27236–27273.DOI
  71. [71]Yanbo Wang, Xiyuan Wang, Quan Gan, Minjie Wang, Qibin Yang, David Wipf, and Muhan Zhang. 2025. Griffin: Towards a Graph-Centric Relational Database Foundation Model. In ICML (PLMR). PMLR / OpenReview.net.arxiv.org/abs/2505.05568
  72. [72]Eugene Wu and Samuel Madden. 2013. Scorpion: explaining away outliers in aggregate queries. Proc. VLDB Endow. 6, 8 (June 2013), 553–564.DOI
  73. [73]Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019. GNNExplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc.
  74. [74]Brit Youngmann, Michael Cafarella, Yuval Movshovitz, and Babak Salimi. 2023. On Explaining Confounding Bias. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). 1846–1859.arxiv.org/abs/2210.02943
  75. [75]Hao Yuan, Haiyang Yu, Shurui Gui, and Shihuiang Ji. 2022. Explainability in graph neural networks: A taxonomic survey. IEEE transactions on pattern analysis and machine intelligence 45, 5 (2022), 5782–5799.DOI
  76. [76]Haopeng Zhang, Yanlei Zhao, and Alexandra Meliou. 2017. Exstream: Explaining anomalies in event stream monitoring. In Proceedings of the 20th international conference on extending database technology (EDBT). 156–167.DOI

Paper details

vlnc:W_3h6xaqjj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents