Shapley Value Computation in Ontology-Mediated Query Answering (Extended Abstract)

1 Introduction

The Shapley value [Shapley, 1953] was originally proposed in the context of cooperative game theory as a method for fairly distributing the wealth of a coalition of players based upon their respective contributions, but has since found application in numerous domains. In artificial intelligence, the Shapley value has been utilized for defining inconsistency measures of propositional [Grant and Hunter, 2006; Hunter and Konieczny, 2010] and description logic knowledge bases [Deng et al., 2007], and more recently for defining explanations of machine learning models [Lundberg and Lee, 2017]. The Shapley value has also gained attention in the database area [Bertossi et al., 2023], where it has been employed both for defining inconsistency values of databases [Livshits and Kimelfeld, 2022] and also for providing quantitative explanations of query answers [Livshits et al., 2021].

In general, Shapley value computation is known to be computationally challenging, being #P-hard in data complexity for common classes of queries, like conjunctive queries (CQs). This has motivated non-uniform complexity studies aimed at pinpointing which queries admit tractable Shapley value computation [Reshef et al., 2020; Khalil and Kimelfeld, 2023], in particular, by establishing connections with probabilistic query evaluation and model counting [Deutch et al., 2022; Kara et al., 2024; Bienvenu et al., 2024b].

∗Extended abstract of [Bienvenu et al., 2024a] from KR 2024.

In the present paper, we revisit the use of the Shapley value in the ontology setting, building upon these recent advances in the database area. We shall mostly focus on how the Shapley value can be employed for explaining answers in the context of ontology-mediated query answering (OMQA) [Poggi et al., 2008; Cal`ı et al., 2011; Mugnier and Thomazo, 2014; Bienvenu and Ortiz, 2015; Xiao et al., 2018]. We recall that the OMQA is used to improve access to incomplete and possibly heterogeneous data through the addition of ontology layer, which provides a user-friendly vocabulary for query formulation as well as domain knowledge that is taken into account when computing the query answers. With the increasing maturity and deployment of OMQA techniques, there is an acknowledged need to help users understand the query results. Various notions of explanations with different levels of detail can be considered for OMQA, ranging from providing proofs of how an answer can be derived [Borgida et al., 2008; Alrabbaa et al., 2022] to generating minimal subsets of the KB that suffice to obtain the answer or identifying the assertions and/or axioms that are relevant in the sense that they belong to such a minimal subset [Bienvenu et al., 2019; Ceylan et al., 2019; Ceylan et al., 2020]. The Shapley value offers a more nuanced, quantitative version of the latter approach, by assigning the relevant assertions and axioms scores based upon their level of responsibility or importance in obtaining the considered query answer (or entailment).

For our study of Shapley value computation, we will work with description logic (DL) knowledge bases (KB), consisting of an ABox (dataset) and TBox (ontology). We introduce some natural ways of defining the Shapley value computation (SVC) problem in the DL setting, by varying what is to be explained (entailment of a TBox axiom, ABox assertion, or query answer), which parts of the KB are assigned values, and how the complexity is measured. To begin our study, we establish the #P-hardness of the Shapley value computation of a simple graph reachability query, which we then employ to show #P-hardness of several variants of the SVC problem, even for inexpressive DLs and atomic queries. In light of these initial negative results, we embark on a nonuniform complexity analysis, whose aim is to classify the data complexity of the Shapley value computation problems SVCQ associated with each ontology-mediated query (OMQ) Q = (T , q). By transferring recent results from the database setting, we establish a FP/#P-hard dichotomy result of Shapley value computation problem SVCQ for OMQs Q = (T , q) where the TBox T is formulated in the Horn DL ELHI⊥ and q is a constant-free connected homomorphism-closed query. Our final and most technically challenging result shows that the #P-hardness part of the dichotomy can be strengthened to cover OMQs based upon a wider range of queries q. Specifically, we show that for any OMQ Q = (T , q) based upon a ELHI⊥ TBox and a UCQ q (which may be disconnected and/or contain constants), non-FO-rewritability of Q implies #P-hardness of SVCQ. Due to the tight connections holding between SVC and probabilistic query evaluation, the proof of this result can be further used to obtain a FP/#P-hard dichotomy for probabilistic ontology-mediated queries from (ELHI⊥, UCQ), substantially generalizing existing results.

2 Preliminaries

We very briefly recall here some key notions and terminology, referring readers to the full paper for more details.

Databases andQueries AdatabaseD is a finite set of facts P(⃗a), with P a k-ary relation symbol and ⃗a a k-ary tuple of constants. Results are formulated for Boolean queries, which evaluate to true or false in a given database (or first-order interpretation), with D |= q indicating q is true in D. We consider well-known query classes like conjunctive queries (CQs) and unions of conjunctive queries (UCQs), given by (disjunctions of) existentially quantified conjunctions of relational atoms. We also consider hom-closed queries, i.e. q such that D |= q implies D′ |= q for every D′ that maps homomorphically into D, as well as connected queries.

Knowledge Bases We assume that readers are familiar with the basics of description logics (DLs) [Baader et al., 2017]. A DL knowledge base (KB) K = (A, T ) comprises an ABox (dataset) A and a TBox (ontology) T , which are built from concept names (unary relations) and role names (binary relations) and individual constants. An ABox is a database whose facts take the form of concept assertions A(c) and role assertions r(c, d). A TBox is a finite set of axioms, whose form is dictated by the DL in question. We use L TBox to refer to a TBox formulated in the DL L. Of particular interest to the present paper are the well-known lightweight DLs EL and DL-Litecore and their common extension, the Horn DL ELHI⊥, see e.g. [Bienvenu and Ortiz, 2015]. The semantics of DL KBs is given in terms of first-order logic interpretations, with each satisfiable KB giving rise to a set of models.

Ontology-Mediated Query Answering We say a Boolean query q is entailed from a DL KB K if I |= q for every model I of K. We may alternatively group T and q into an ontology-mediated query (OMQ) Q = (T , q), which is posed to the ABox A, in which case we will write A |= Q to mean (A, T ) |= q. We will use the notation (L, Q) to designate the class of all OMQs (T , q) such that T is formulated in the DL L and q is a query from the class of queries Q.

First-order (FO) rewriting is a prominent OMQA technique which rewrites the input OMQ into another query that can be directly evaluated by a database system. Formally, a Boolean FO-query q∗ is an FO-rewriting of Boolean OMQ Q = (T , q) if for every ABox A: A |= (T , q) iff A |= q∗ . If we modify the definition to only quantify over ABoxes that are satisfiable w.r.t. T , we speak instead of a rewriting w.r.t. consistent ABoxes. If an OMQ Q possesses an FO-rewriting, we say that Q is FO-rewritable, else it is called non-FO-rewritable.

3 Shapley Value

We briefly recall the definition of Shapley value in games and how it has been employed in the database setting, before illustrating its application in the ontology setting.

3.1 Shapley Value in Cooperative Games

The Shapley value [Shapley, 1953] was introduced as a means to fairly distribute wealth amongst players in a a cooperative game, based upon their respective contributions. A cooperative game consists of a finite set of players P and a wealth function v : ℘(P) → Q that assigns a value to each coalition (i.e., set) of players, with v(∅) = 0. Picture a scenario where the players arrive one by one in a random order, and each one earns what she added to the current coalition's wealth on arrival. The Shapley value of a player p ∈ P is defined as her expected earnings in this scenario, which can be expressed as:

where S(P) denotes the set of permutations of P and σ<p (resp. σ⩽p) the set of players that appear before p (resp. before or at p) in the permutation σ. Intuitively, we take the average marginal contribution v(σ⩽p) - v(σ<p) of p, across all possible orderings σ of the players.

3.2 Shapley Value for Database Queries

There has been significant interest lately in the problem of computing the Shapley value of database facts as a means of quantifying their contributions to a query answer. The formal setting is as follows: the database D is partitioned into endogenous and exogenous facts, D = Dn ⊎ Dx, the players of the cooperative game are the endogenous facts Dn, and the wealth function of a given Boolean query q is defined, for every subset B ⊆ Dn of endogenous facts, as vq(B) = vB -vx where vB = 1 (resp. vx = 1) if Dx∪B |= q (resp. if Dx |= q), and 0 otherwise. We use SVCq to denote the problem of computing the Shapley value Sh(Dn, vq, α) for the input partitioned database Dn ⊎ Dx and fact α ∈ Dn.

In [Livshits et al., 2021], a FP/#P-hard dichotomy was established for the class of self-join-free CQs (i.e. not having two atoms with the same relation name), showing that for every such query q, SVCq is either tractable (in FP) or #Phard. Interestingly, the dichotomy coincides with the FP/#Phard dichotomy previously established for probabilistic query evaluation (PQE) [Dalvi and Suciu, 2004]. We recall that the problem PQEq is to compute, given a tuple-independent probabilistic database D = (S, π) (consisting of a database S and probability assignment π : S → (0, 1]), the probability of Boolean query q being true, where each assertion

α ∈ S has independent probability π(α) of being present in the database. The PQE dichotomy extends to the more general class of UCQs [Dalvi and Suciu, 2012], where the queries for which PQE is tractable are known as safe UCQs. However, it is an open problem whether UCQs (or even CQs with self-joins) also enjoy a dichotomy for SVC.

Some recent results have helped clarify the relation between the two dichotomies. First, [Deutch et al., 2022] showed how to reduce SVC to PQE. More recently, it has been shown that SVC and SPPQE (a restriction of PQE to probabilistic databases where π(α) ∈ {p, 1} for a single p ∈ (0, 1)) are polynomial-time inter-reducible for many fragments of hom-closed queries [Bienvenu et al., 2024b], in particular for connected queries without constants. This yielded a much broader dichotomy result for the class of graph databases (i.e. having only unary and binary relations):

Theorem 1. [Bienvenu et al., 2024b, Corollaries 4.1 and 4.2] For every connected hom-closed Boolean query q, SPPQEq ≡P SVCq; further, on graph databases, SVCq is in FP if q is equivalent to a safe UCQ and #P-hard otherwise.

3.3 Shapley Value in the Ontology Setting

We present a running example which illustrates the use of the Shapley value in the ontology setting.

Example 2. Consider the ELHI⊥ KB defined in Figure 1, where the ABox (bottom half) contains information on some ingredients and recipes, and the TBox (top half) defines more complex notions such as a 'land-sea recipe'. For instance, ∃HasIngr.FishBased ⊑ FishBased intuitively translates as 'anything that has a fish-based ingredient is fish-based'.

A user of this KB might obtain poulardeNantua as an answer to the query LandSea(x), and wonder which ingredients are the most responsible for this fact. She can thus set everything but the role assertions (which specify ingredients) as exogenous and compute the Shapley values for the Boolean query LandSea(poulardeNantua).

We can compute the values via Eq. (1). There are 4! = 24 possible permutations over the 4 endogenous role assertions {e1, e2, e3, e4}. 14 out of 24 permutations are s.t. v(σ⩽e1 ) - v(σ<e1 ) = 1, and similarly 6 for e2, 2 for e3, and 2 for e4, making the respective Shapley values: 14/24, 6/24, 2/24 and 2/24.

As expected, e1 has the highest responsibility because it is necessary to satisfy the query, then comes e2 that only needs to be combined with e1 and finally e3 and e4 that must be used together in combination with e1.

As we shall see in Section 4, there are several different Shapley value computation tasks that can be considered in the ontology setting. Indeed, we may vary the reasoning task (e.g. query answering or axiom entailment), which parts of the knowledge base are assigned Shapley values (only assertions, only axioms, or both?), how the complexity is measured (is the query fixed or part of the input?), and the languages used to formulate the TBox and the queries.

4 Complexity Results for Ontology Setting

In this section, we briefly present the results of our complexity analysis of different Shapley value computation tasks.

FishBased ⊓MeatBased ⊑ LandSea Fish ⊑ FishBased ∃HasIngr.FishBased ⊑ FishBased Seafood ⊑ FishBased ∃HasIngr.MeatBased ⊑MeatBased Crustacean ⊑ SeaFood HasSauce ⊑ HasIngr Meat ⊑ MeatBased

4.1 Initial Intractability Results

A first application of the Shapley value to ontologies is to focus solely on the TBox and determine which axioms are most responsible for a given TBox entailment, e.g. to find out why crustaceans count as fish-based. Unfortunately, we can show #P-hardness already for the simplest possible DL Lmin containing only concept name inclusions. The proof relies upon first establishing #P-hardness of a Shapley value computation task involving reachability in directed graphs, then using axiom entailment to encode reachability.

Proposition 3. For every TBox T and S ⊆ T and pair of concept names A,B, define vA⊑B(S) := 1 if S |= A ⊑ B, and 0 otherwise. The problem of computing, given a Lmin TBox T , concept names A,B, and an axioms µ ∈ T , the Shapley value of µ in the game (T , vA⊑B) is #P-hard.

We next consider how to use the Shapley value to explain query entailment w.r.t. a DL KB. In our example, a user may ask why there is a fish-based recipe in the KB of Figure 1 if there is no Fish assertion. She could therefore compute the Shapley values for the CQ ∃x.FishBased(x) and discover that the crayfish is considered fish-based because of the assertion Crustacean(crayfish) and the axioms Crustacean ⊑ SeaFood ⊑ FishBased. The input will now be a partitioned KB K = (An ⊎ Ax, Tn ⊎ Tx) and the task is to compute the Shapley value of the statements in An ∪ Tn, in order to quantify their responsibility in K entailing q. Concretely, for any Boolean query q we consider the cooperative game with players An ∪ Tn and vq(S) := vS - vx where vS = 1 (resp. vx = 1) if (Ax ∪ (S ∩An), Tx ∪ (S ∩ Tn)) |= q (resp. if (Ax, Tx) |= q), and 0 otherwise.

Proposition 4. The problem of computing Shapley values for Boolean CQs over partitioned KBs on Lmin is #P-hard. Hardness holds even for queries given as ABox assertions.

Propositions 3 and 4 show that computing Shapley values of axioms is inevitably intractable, as reasoning on concept and role inclusions naturally involves reachability. One idea to sidestep this issue would be to treat the whole TBox as exogenous. Conceptually, this corresponds to treating TBox axioms as given or obvious, thereby focusing on explanations in terms of the ABox assertions. In our running example of Figure 1, the user may wonder what ingredients make the Poularde Nantua recipe fish-based, leading her to compute Shapley values for the CQ FishBased(poulardeNantua), setting everything but the HasIngr-roles as exogenous.

In terms of complexity, the problem will once again be #Phard due to reachability, which this time is expressed within the data itself. The source of difficulty are axioms such as ∃HasIngr.FishBased ⊑ FishBased, which can be found in any DL at least as expressive as EL.

Proposition 5. Let q be a CQ of the form A(c), for A ∈ NC and c ∈ NI. Then the problem of computing Shapley values for q over partitioned KBs on EL is #P-hard, even if we assume that the TBox only contains exogenous axioms.

4.2 ADichotomy for OMQs in ELHI⊥

The results of Section 4.1 show that allowing TBoxes to be part of the input makes the Shapley value computation problems #P-hard. This suggests the interest of analyzing the complexity of Shapley value computation at the level of individual ontology-mediated queries Q = (T , q), only taking data as input. Such a non-uniform approach to complexity analysis has previously been undertaken for several OMQA settings, and in particular in the context of probabilistic OMQA [Jung and Lutz, 2012]. Moreover, this perspective aligns nicely with the formulation of Shapley value computation for database queries, enabling transfer of results.

In order to be able to apply Theorem 1 in a 'black-box' fashion, we need to identify a class of OMQs that is homclosed and connected. To this end, we prove the following lemma, which shows that the addition of an ELHI⊥ ontology preserves the connectedness of hom-closed queries.

Lemma 6. Let q be a connected C-hom-closed 1 query and T an ELHI⊥ ontology. Then the OMQ Q := (T , q) is a connected C-hom-closed query.

Lemma 6 allows us to exploit the equivalence of SVC with probabilistic database evaluation from [Bienvenu et al., 2024b] (recalled in Theorem 1) to obtain a dichotomy for OMQs whose base query is constant-free and connected.

Theorem 7. For every connected (constant-free) hom-closed query q and ELHI⊥ ontology T , we have SVC(T ,q) ≡P SPPQE(T ,q). Further, the problem is in FP if the OMQ (T , q) can be rewritten into a safe UCQ and #P-hard otherwise.

It is decidable whether or not a given UCQ is safe [Dalvi and Suciu, 2012, implicit]. It therefore follows that the dichotomy given by Theorem 7 is effective whenever first-order rewritability is decidable for the considered class of OMQs, and that a first-order rewriting can always be effectively computed when there exists one. This is in particular true for (ELHI⊥,CQ) [Bienvenu et al., 2016, Theorem 5].

Furthermore, [Jung and Lutz, 2012, Theorem 5] gives a syntactic characterisation of which constant-free connected OMQs in (DL-Litecore,CQ) are equivalent to safe UCQs. By Theorem 7, it also characterizes constant-free connected OMQs Q ∈ (DL-Litecore, CQ) that are s.t. SVCQ ∈ FP.

1 To accommodate queries with constants (Theorems 8 and 9), we must consider here C-hom-closed queries, defined using Chomomorphisms, which fix the interpretation of the constants in C.

4.3 Strengthening the #P-Hardness Result

The dichotomy of Theorem 7 is limited in two respects:

• The result only covers connected constant-free queries.
• When an OMQ is seen as an abstract query, the distinction between consistent and inconsistent ABoxes is lost. However, one might be interested in explaining answers to a query only over consistent ABoxes.

When considering OMQs in (ELHI⊥,UCQ), both of these points can be improved upon by carefully exploiting the properties of OMQs that are non-FO-rewritable.

Theorem 8. Let q be a UCQ and T an ELHI⊥ ontology. If the OMQ Q := (T , q) is non-FO-rewritable w.r.t. consistent ABoxes, then SVCQ and PQEQ(1/2; 1)2 on consistent ABoxes are both #P-hard.

As a consequence of Theorem 8, we obtain the following dichotomy for the probabilistic evaluation of OMQs, which extends [Jung and Lutz, 2012, Theorem 7] by generalizing from a subset of (ELI, CQ) to (ELHI⊥, UCQ).

Theorem 9. Let Q be a (ELHI⊥,UCQ) OMQ. Then PQEQ(1/2; 1), SPPQEQ and PQEQ are all in FP if Q is FOrewritable into a safe UCQ, and #P-hard otherwise. Further, this dichotomy is effective if Q ∈ (ELHI⊥, CQ).

5 Conclusion &Discussion

This paper summarizes the results presented in [Bienvenu et al., 2024a] on using Shapley values to provide quantitative explanations in the setting of ontology-mediated query answering. By exploiting recent results on SVC from the database setting, we obtained complexity dichotomies for OMQs whose TBoxes are formulated in the well-known Horn DL ELHI⊥. In particular, Theorem 7 identifies classes of OMQs for which the Shapley value can be computed in FP, while Theorem 8 provides a general #P-hardness result for non-FO-rewritable OMQs. Using the same techniques, and leveraging known connections between SVC and probabilistic query evaluation, we were further able to obtain a general dichotomy result for probabilistic OMQA (Theorem 9).

The dichotomy result for probabilistic OMQA is stronger than the one for SVC, which is to be expected as existing results on SVC in the pure database setting do not cover UCQs that are disconnected or with constants. It is an important open question whether there is a dichotomy for SVCq for all Boolean UCQs q. Note that any progress on this question can be immediately transferred to the OMQA setting.

An interesting but challenging direction for future work is to study SVC for ontologies formulated using existential rules. We expect that the extension of our results to such ontologies will be non-trivial, due to the presence of higher-arity predicates and the lack of forest-shaped models. Indeed, the dichotomy for SPPQE that we exploited to obtain Theorem 7 is currently only known for arity 2 relations, and the proof of Theorem 8 relies upon the existence of a unique path between 'anonymous' elements, ensured by the forest-shaped structure of canonical models of Horn DL ontologies.

2 PQEQ(1/2; 1) is obtained by restricting PQE (or SPPQE) by only allowing 1 and 12 as probability values.

Acknowledgements

This work was partially supported by ANR AI Chair INTENDED (ANR-19-CHIA-0014) and ANR project CQFD (ANR-18-CE23-0003).