Technion, Haifa<EMAIL_ADDRESS>Technion, Haifa,
<EMAIL_ADDRESS>Majd Khalil and Benny
Kimelfeld John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23 theoremTheorem[section] lemmaLemma[section]
observationObservation[section] claim[theorem]Claim <ccs2012> <concept>
<concept_id>10003752.10010070.10010111.10003623</concept_id>
<concept_desc>Theory of computation Data provenance</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Data provenance

# The Complexity of the Shapley Value for Regular Path Queries

Majd Khalil  Benny Kimelfeld

###### Abstract

A path query extracts from a labeled graph vertex tuples based on the words
that are formed from the paths that connect the vertices. We study the
computational complexity of measuring the contribution of edges and vertices
to an answer of a path query. We focus on conjunctive regular path queries. To
measure this contribution, we adopt the traditional Shapley value from
cooperative game theory. This value has been recently proposed and studied in
the context of relational database queries, and has uses in a plethora of
other domains, including importance measurement of feature values for machine-
learning classifiers.

We first study edge contribution and show that the exact Shapley value is
almost always hard to compute. Specifically, it is #P-hard to calculate the
contribution of an edge whenever at least one (non-redundant) conjunct allows
for a word of length three or more. In the case of regular path queries (i.e.,
no conjunction), the problem is tractable if the query has only words of
length at most two; hence, this property fully characterizes the tractability
of the problem. On the other hand, if we allow for an approximation error,
then it is straightforward to obtain an efficient scheme (FPRAS) for an
additive approximation. Yet, a multiplicative approximation is harder to
obtain. We establish that in the case of conjunctive regular path queries, a
multiplicative approximation of the Shapley value of an edge can be computed
in polynomial time if and only if all query atoms are finite languages
(assuming non-redundancy and conventional complexity limitations). We also
study the analogous situation where we wish to determine the contribution of a
vertex, rather than an edge, and establish results of a similar nature.

###### keywords:

Path queries Regular path queries Graph databases Responsibility Shapley value

##  1 Introduction

Graph databases arise in common applications where the underlying data is a
network of entities, and especially when connectivity and path structures are
of importance. Such usage spans many fields, including the Semantic Web
[DBLP:conf/pods/ArenasP11], social networks [DBLP:conf/icdt/Fan12], biological
networks [DBLP:journals/biodatamining/LysenkoRSMRA16, yoon2017use], data
provenance [DBLP:conf/edbt/AnandBL10], fraud detection [sadowski2014fraud],
recommendation engines [DBLP:conf/IEEEwisa/YiLFS17], and many more. In their
simplest form, graph databases are finite, directed, edge-labeled graphs.
Vertices represent entities, and edges of different labels are relationships
of different types thereof. The connected nature of graph databases raises the
need for tools that allow inspecting and analyzing the structure and patterns
present in the data; this is typically realized in the form of queries that
enable users to specify the structure of paths of interest.

A canonical example of a graph query is the Regular Path Query (RPQ)
[DBLP:conf/sigmod/CruzMW87, DBLP:conf/pods/CalvaneseGLV99,
DBLP:conf/pods/ConsensM90, DBLP:conf/pods/Yannakakis90]. RPQs allow the
specification of paths using regular expressions over the edge labels. When
evaluated on a graph, the answers are source-target pairs of vertices that are
connected by a path that conforms to the query’s regular expression. This
allows users to inspect complex connections in graphs by enabling them to form
queries that match arbitrarily long paths. An important generalization of RPQs
are the _Conjunctive Regular Path Queries_ (CRPQs) that extend regular path
queries by allowing a conjunction of atoms where each atom is an RPQ that
should hold between two specified variables [DBLP:conf/pods/ConsensM90,
DBLP:conf/sigmod/CruzMW87].

Being simple and expressive, such queries are an integral part of popular
graph query languages for graphs, such as GraphLog, Cypher, XPath, and SPARQL.
Therefore, they motivate and give rise to much research effort, including the
study of some natural computational problems and variations thereof
[DBLP:conf/pods/FlorescuLS98, DBLP:journals/siamcomp/MendelzonW95,
DBLP:conf/icdt/MartensT18, DBLP:journals/tods/MartensT19]: What is the
complexity of deciding whether an RPQ $r$ matches a path from $s$ to $t$ in
$G$ (what we refer to as _Boolean query evaluation_)? Can we efficiently count
and enumerate these paths? Is a given CRPQ contained in another given CRPQ?
Importantly, the combined complexity of Boolean query evaluation is in Ptime
for RPQs, while for CRPQs it is $\mathrm{NP}$-complete
[barcelo2012expressive]. Data complexity, however, is NLogspace-complete for
both [DBLP:conf/pods/Baeza13]. The containment problem for RPQs is Pspace-
complete, and for CRPQs, it is Expspace-hard [DBLP:conf/pods/FlorescuLS98,
DBLP:conf/kr/CalvaneseGLV00].

In this paper, we focus on the problem of _quantifying the responsibility and
contribution_ of different components in the graph, namely edges and vertices,
to an answer of the CRPQ (and RPQ in particular). This problem has been
studied in the context of queries on relational databases, and our motivation
here is the same as in the relational context: we wish to provide the database
user with an explanation of _why_ (or what in the database led to that) we got
a specific answer; when many combinations of data items can lead to an answer,
and the lineage is too large or complex, we wish to quantify the contribution
of individual items in order to distinguish between the more and the less
important to the answer [DBLP:journals/corr/abs-2112-08874].

In the relational model, several definitions and frameworks have been proposed
for measuring the contribution of a tuple. For example, Meliou et al.
[DBLP:journals/pvldb/MeliouGMS11] defined the responsibility of a fact $f$ as,
roughly, the inverse of the minimal number of facts needed to be removed to
make $f$ counterfactual (i.e., the query answer is determined by the existence
of $f$); this measure is an adaptation of earlier notions of formal causality
by Halpern and Pearl [DBLP:conf/uai/HalpernP01]. _Causal effect_ is another
alternative measure proposed by Salimi et al. [DBLP:conf/tapp/SalimiBSB16]: if
the database is probabilistic and each fact has independently the probability
$1/2$ of existence, how does the probability of the answer change if we assume
the existence or absence of $f$? Lastly, and most relevant to our work, recent
work has studied the adoption of the _Shapley value_ —a solution concept from
game theory [DBLP:journals/sigmod/LivshitsBKS21, DBLP:conf/pods/ReshefKL20,
DBLP:conf/icdt/LivshitsK21, DBLP:journals/corr/abs-2112-08874].

The Shapley value is a formula for wealth distribution in a cooperative game
[shapley:book1952]. In databases, the conceptual application is
straightforward: facts are the players who play the game of answering the
Boolean (or numerical) query; hence, the wealth function is the result of the
query [DBLP:journals/sigmod/LivshitsBKS21]. The Shapley value has a plethora
of applications, including profit sharing between ISPs
[DBLP:journals/ton/MaCLMR10], influence measurement in social network analysis
[DBLP:journals/tase/NarayanamN11], determining the most important genes for
specific body functions [moretti2007class], and identifying key players in
terrorist networks [DBLP:journals/snam/CampenHHL18], to name a few. Closer to
databases is a recent application to model checking for measuring the
influence of formula components [mascle2021responsibility]. As another
example, in machine learning, the SHAP score [NIPS2017_7062] has been used for
measuring the contribution of each feature to the prediction, and it is
essentially the Shapley value with the features as players. This value was
also used for quantifying the responsibility that every fact has on the
_inconsistency_ of a knowledge base [DBLP:journals/ai/HunterK10,
DBLP:conf/ijcai/YunVCB18] and a database [DBLP:conf/icdt/LivshitsK21]. Yet,
what limits the applicability of the Shapley value is the high computational
complexity—the execution cost might grow exponentially with the number of
players. Hence, past research has been investigating islands of tractability
and approximation guarantees.

##### Contribution

We study the complexity of computing the Shapley value of edges and vertices
in the domain of graph databases, where the queries are CRPQs. In the
remainder of this section and throughout the paper, we focus on edges (and
discuss vertices in Section 6). As in previous work
[DBLP:journals/pvldb/MeliouGMS11, DBLP:conf/icdt/LivshitsK21], we view the
graph as consisting of two types of edges: _endogenous_ edges and _exogenous_
edges. The endogenous edges are the ones that we consider for reasoning about
the contribution, and they are the players of the game. The exogenous edges
serve as external knowledge: they are static items that we take for granted
(as outside, unconcerned factors, deemed not to be possible causes), and do
not participate in the counterfactual game. The classification into
endogenous/exogenous items is application-dependent, and may even be chosen by
the user at query time.

An instance of our problem involves a query $q$ (e.g., an RPQ or a CRPQ), an
input graph $G$, an answer tuple $\vec{t}$ of vertices of $G$, and an edge $e$
of which contribution to $t$ we seek to measure. As previously done in the
context of contribution measures, we adopt the yardstick of _data complexity_
[DBLP:conf/stoc/Vardi82] where we consider the query $q$ as fixed. More
precisely, each fixed query $q$ is associated with a distinct computational
problem that takes as input $G$, $\vec{t}$ and $e$.

We first show that the exact computation of the Shapley value is almost always
hard. Specifically, it is sufficient for the CRPQ to have a non-redundant atom
(i.e., a conjunct associated with a regular language) with a word of length
three or more for the computation to be #P-hard
($\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$-complete). In addition, for RPQs
(i.e., single-atom CRPQs), we complete this hardness condition to a full
dichotomy by showing that the Shapley value can be computed in polynomial time
if the language contains only words of length at most two.

Next, we study the complexity of approximation. In our context, we adopt a
standard yardstick of tractable approximation, namely FPRAS (Fully Polynomial-
Time Approximation Scheme). An approximation of the Shapley value of an edge
to a CRPQ can be computed via a straightforward Monte-Carlo (average-over-
samples) estimation of the expectation that Shapley defines. This estimation
guarantees an additive (or absolute) approximation. However, we are also
interested in a multiplicative (or relative) approximation.

We establish a dichotomy that classifies CRPQs into a class where there is a
multiplicative FPRAS and the complementing class where there cannot be any
such FPRAS under conventional complexity assumptions. Specifically, if the
CRPQ contains an atom (non-redundant atom) with an infinite regular language,
then (any) multiplicative approximation is intractable since it is already
$\mathrm{NP}$-complete to determine whether the Shapley value is nonzero. In
every other case (assuming no redundant atoms), an additive FPRAS can also be
used to obtain a multiplicative FPRAS, due to the _gap property_ , previously
established in the relational model [DBLP:conf/icdt/LivshitsK21,
DBLP:conf/pods/ReshefKL20]: if the Shapley value is nonzero, it is at least
the reciprocal of a polynomial. Note that this is contrasting the situation
with relational conjunctive queries, where there is always a multiplicative
FPRAS [DBLP:journals/sigmod/LivshitsBKS21].

For the case of vertices, we show that the situation is very similar to what
we have for edges. It is generally hard to compute exact values; it is
sufficient for the CRPQ to have a non-redundant atom that contains a word of
length four or more for the computation to be hard, while for RPQs we identify
that the tractable family of queries is also tractable for vertices (yet, for
vertices we do not complete a full classification). For approximation, we
establish the same dichotomy as for edges.

##### Paper organization.

The rest of the paper is organized as follows. We introduce some basic
terminology in Section 2. In Section 3, we formally define how the Shapley
value is applied in our setting for edges in graph databases. In Section 4, we
study the complexity of computing exact Shapley values for CRPQs, and we study
approximations in Section LABEL:sec:approx. We present the complexity results
for the case when measuring contribution of vertices instead of edges in
Section 6 and outline the changes that should be made to the proofs. We
conclude and discuss directions for future work in Section 7. For lack of
space, some of the proofs are omitted or sketched in the body of the paper,
and given fully in the Appendix.

##  2 Preliminaries

We begin by setting some terminology and notation that we use throughout the
paper.

###  2.1 Graphs and Path Queries

We use $\Sigma$ to denote a finite alphabet (i.e., a finite set of symbols)
that is used for labeling edges of graphs. A _word_ is a finite sequence of
symbols from $\Sigma$. As usual, $\mathord{\Sigma^{*}}$ denotes the set of all
words. A _language_ $L$ is a (finite or infinite) subset of
$\mathord{\Sigma^{*}}$. By a slight abuse of notation, we may identify a
language $L$ with a representation of $L$ such as a regular expression or a
finite-state automaton.

A _regular expression_ is defined as follows: $\emptyset$, $\epsilon$, and
$\sigma\in\Sigma$ are regular expressions denoting the empty language, empty
word and symbol $\sigma$, respectively; in addition, if $r$ and $s$ are
regular expressions, then $(r\mid s)$ and $(r\cdot s)$ and $(r^{*})$ are also
regular expressions, denoting union, concatenation and Kleene star,
respectively. We sometimes omit parentheses and dots when there is no risk of
ambiguity (so we may write $rs$ instead of $(r\cdot s)$, for instance). The
language $L(r)$ that $r$ accepts (recognizes) is defined as usual. We allow
the use of a special regular expression $\mathord{\Sigma^{*}}$ that accepts
every word. A _deterministic finite automaton_ (DFA) $A$ is a tuple
$(Q,\Sigma,\delta,q_{0},F)$, where $Q$ is a finite set of states, $\Sigma$ is
a finite alphabet, $\delta\colon Q\times\Sigma\to Q$ is the transition
function, $q_{0}$ is the initial state, $F$ is the set of accepting states. By
$\delta^{*}(w)$ we denote the state that the automaton reaches after reading
$w$, starting from the initial state. The automaton _accepts_ a word $w$ if
$\delta^{*}(w)\in F$. We again use $L(A)$ to denote the language that $A$
recognizes. (Recall that the classes of regular expressions and DFAs coincide
in their expressive power.)

By a _graph_ we mean an edge-labeled directed graph $G=(V,E)$ where $V$ is the
finite set of nodes and $E\subseteq V\times\Sigma\times V$ is the set of
edges. We will consistently denote by $n$ and $m$ the number of nodes and
edges, respectively; that is, $n=\lvert V\rvert$ and $m=\lvert E\rvert$. A
path $p$ from node $u$ to node $v$ in $G$ is a sequence
$p=(v_{0},a_{1},v_{1})(v_{1},a_{2},v_{2})\ldots(v_{k-1},a_{k},v_{k})$ of edges
in $G$ such that $u=v_{0}$ and $v=v_{k}$. By $|p|$ we denote the length $k$ of
$p$, and by $\mathrm{lbl}(p)$ we denote the word $a_{1}\cdots a_{k}$. If
$G=(V,E)$ is a graph and $E^{\prime}\subseteq E$ is a set of edges, then we
denote by $G[E^{\prime}]$ the subgraph $G^{\prime}=(V,E^{\prime})$ of $G$. In
other words, $G[E^{\prime}]$ is obtained from $G$ by removing every edge in
$E\setminus E^{\prime}$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$aaaabbbbc Figure 1: The graph of the
running example. In the text, we denote the edge $(v_{i},v_{j})$ as $e_{ij}$.

A _path query_ is a query of the form $q\coloneqq(x,L,y)$ where $L$ is a
language. When evaluated on a graph $G$ it returns the set $q(G)$ of all pairs
$(s,t)$ for variables $(x,y)$, such that $s$ and $t$ are nodes in graph $G$
and there exists a path $p$ from $s$ to $t$ with $\mathrm{lbl}(p)\in L$. For
convenience, we may view $q$ as a function that also takes as input a pair of
nodes, such that $q(G,s,t)=1$ if $(G,s,t)$ is a “yes” instance and
$q(G,s,t)=0$ otherwise. We define similarly the special case of the queries,
which we call _regular path queries_ (RPQs), where $L$ is a regular language
that is defined via a regular expression $r$ or an automaton $A$. We sometimes
use the shorthand $L$ for the query $(x,L,y)$, or $r$ in the case of a regular
expression.

######  Example 2.1.

Figure 1 depicts the graph $G$ of our running examples with labels in
$\Sigma=\\{a,b,c\\}$. We show a few examples of path queries on the graph $G$.

  * •

$q_{1}=\mathord{\Sigma^{*}}$. This query tests whether there is a path from
$s$ to $t$ in $G$. For example, we have that $q_{1}(G,v_{1},v_{2})=1$, and
$q_{1}(G,v_{1},v_{6})=1$, as there are paths from $v_{1}$ to both $v_{2}$ and
$v_{6}$. But $q_{1}(G,v_{3},v_{1})=0$, as there is no path from $v_{3}$ to
$v_{1}$.

  * •

$q_{2}=\\{abc\\}$. This query tests whether there is a path from $s$ to $t$ in
$G$ that matches the word $abc$. For example, we have that
$q_{2}(G,v_{1},v_{6})=1$, as there is a path $v_{1}\rightarrow
v_{3}\rightarrow v_{5}\rightarrow v_{6}$ that matches $abc$. But we have that
$q_{2}(G,v_{3},v_{5})=0$, as the only path from $v_{3}$ to $v_{5}$ consists of
a single edge labeled $b$.

  * •

$q_{3}=ab^{*}$. This query tests whether there is a path from $s$ to $t$ in
$G$ that matches regular expression $ab^{*}$. For example, we have that
$q_{3}(G,v_{1},v_{6})=1$, as there are paths: $v_{1}\rightarrow
v_{2}\rightarrow v_{4}\rightarrow v_{6}$, or alternatively, $v_{1}\rightarrow
v_{2}\rightarrow v_{6}$, that match $ab^{*}$. But we have that
$q_{2}(G,v_{3},v_{5})=0$, as the only path from $v_{3}$ to $v_{5}$ consists of
a single edge with label $b$, which does not match the regular expression.

Note that $q_{1}$ and $q_{3}$ are RPQs with infinite languages, whereas
$q_{2}$ is defined simply as a finite (singleton) language. ∎

####  2.1.1 Conjunctive Regular Path Queries

A _conjunctive regular path query_ , CRPQ for short, is a query with $k$
variables $x_{1},\ldots,x_{k}$ that is a conjunction of atomic regular path
queries between pairs of nodes that can be assigned to $x_{1},\ldots,x_{k}$. A
general CRPQ $q$ is in the form:

$q[x_{1},\ldots,x_{k}]=\bigwedge_{i=1}^{m}(y_{i},r_{i},z_{i})$ (1)

Where $y_{i}$ and $z_{i}$ are variables from $\\{x_{1},\ldots,x_{k}\\}$ and
$r_{i}$ is a regular expression. The RPQ $(y_{i},r_{i},z_{i})$ is also
referred to as the atom $i$ of $q$ and is denoted by $q_{i}$. As before, when
evaluated on a graph $G$, we denote by $q(G)$ all of the assignments
$(u_{1},\ldots,u_{k})$ for $(x_{1},\ldots,x_{k})$, such that all atomic RPQs
are true. We might also denote the assignment $(u_{1},\ldots,u_{k})$ as a
function
$\mu:\mathord{\\{x_{1},\dots,x_{k}\\}}\rightarrow\mathord{\\{u_{1},\dots,u_{k}\\}}$
such that $\mu(x_{i})=u_{i}$ for $i=1,\dots,k$. We use a numeric notation
similarly to RPQs, that is, for a particular assignment $u_{1},\ldots,u_{k}$
we have $q[u_{1},\ldots,u_{k}](G)=1$ if it is a “yes” instance and
$q[u_{1},\ldots,u_{k}](G)=0$ otherwise.

######  Example 2.2.

Let us look at the query
$q[x_{1},x_{2},x_{3}]=(x_{1},a^{*},x_{2})\wedge(x_{2},b^{*},x_{3})$. When
evaluated on a graph, this query returns triplets $(u_{1},u_{2},u_{3})$ such
that there is a path from $u_{1}$ to $u_{2}$ that matches $a^{*}$ and there is
a path from $u_{2}$ to $u_{3}$ that matches $b^{*}$. In our example graph
(Figure 1), we have that $q[v_{1},v_{2},v_{6}](G)=1$, as there is a path
$v_{1}\rightarrow v_{2}$ that matches $a^{*}$, and a path $v_{2}\rightarrow
v_{4}\rightarrow v_{6}$ that matches $b^{*}$. Yet,
$q[v_{1},v_{3},v_{6}](G)=0$, as the only path from $v_{3}$ to $v_{6}$ has
label $bc$, which does not match $b^{*}$. ∎

We say that an atom is _redundant_ if removing it from $q$ does not change the
answers of $q$ on all graphs. Formally, we denote by $q^{\setminus j}$ the
query after removing atom $j$.

$q^{\setminus j}[x_{1},\ldots,x_{k}]=\bigwedge_{i=1;i\neq
j}^{m}(y_{i},r_{i},z_{i})$

Then the atom $j$ is _redundant_ if $q\equiv q^{\setminus j}$, that is,
$q(G)=q^{\setminus j}(G)$ for all graphs $G$.

######  Example 2.3.

Let us look at
$q[x_{1},x_{2},x_{3}]=(x_{1},a,x_{2})\wedge(x_{2},b,x_{3})\wedge(x_{1},a^{*}b^{*},x_{3})$.
In this query, the third atom is redundant according to our definition, as
removing it does not change the result set on any graph. Intuitively, if the
first two queries return true then so does the third, and so, the third atom
does not add any restriction to the conjunction. ∎

We will later refer to the following obvious (and standard) observation. Let
$q$ be a CRPQ. If the atom $i$ is non-redundant, then there exists a graph $G$
and assignment $\mu$ to $(x_{1},\dots,x_{k})$ such that
$q_{j}(G,\mu(y_{j}),\mu(z_{j}))=1$ for $j\neq i$ and
$q_{i}(G,\mu(y_{i}),\mu(z_{i}))=0$.

######  Proof 2.4.

By definition, if atom $i$ is non-redundant, it means that there exists a
graph $G_{i}$ such that $q(G_{i})\neq q^{\setminus i}(G_{i})$. And since every
answer tuple $t\in q(G_{i})$ is also also an answer tuple for $q^{\setminus
i}(G_{i})$, this means that there exists an answer tuple
$t^{\prime}=(v_{1},\ldots,v_{k})\in q^{\setminus i}(G_{i})$ such that
$t^{\prime}\notin q(G_{i})$. In other words, for assignment
$(v_{1},\ldots,v_{k})$, there are matching paths for each $q_{j}$ for $j\neq
i$ $(q_{j}(G_{i},s_{j},t_{j})=1)$ and no matching path for $q_{i}$
$(q_{i}(G_{i},s_{i},t_{i})=0)$.

In the sequel, we say that $q$ is _without redundancy_ if every atom of $q$ is
non-redundant. Note that every CRPQ $q$ can be made one without redundancy
(while preserving equivalence) by repeatedly removing redundant atoms.

###  2.2 The Shapley Value

Let $A$ be a finite set of players. A cooperative game is a function $v\colon
P(A)\to\mathbb{R}$ such that $v(\emptyset)=0$. The value $v(S)$ represents a
value, such as wealth, jointly obtained by $S$ when the players of $S$
cooperate. The Shapley value for the player $a$ is defined to be:

$\mathrm{Shapley}(A,v,a)=\frac{1}{\lvert
A\rvert!}\sum_{\sigma\in\Pi_{A}}(v(\sigma_{a}\cup\\{a\\})-v(\sigma_{a}))$ (2)

Here, $\Pi_{A}$ is the set of all possible permutations over the players in
$A$, and for each permutation $\sigma$ we denote by $\sigma_{a}$ the set of
players that appear before $a$ in the permutation. Alternatively, the Shapley
value can be written as follows.

$\mathrm{Shapley}(A,v,a)=\sum_{B\subseteq A\setminus\\{a\\}}\frac{\lvert
B\rvert!(\lvert A\rvert-\lvert B\rvert-1)!}{\lvert
A\rvert!}(v(B\cup\\{a\\})-v(B))$

Intuitively, the Shapley value of a player $a$ is the expected contribution of
$a$ to the value $v(B)$ where $B$ is a set of players chosen by randomly (and
uniformly) selecting players one by one without replacement. The Shapley value
is known to be unique up to some rationality axioms that we omit here (c.f.
[shapley:book1952]).

##  3 The Shapley Value of Edges

Throughout the paper, we focus on the Shapley value of edges of the input
graph $G$. Later, in Section 6, we also discuss the extension of our results
to the Shapley value of vertices.

Given a CRPQ $q$, our goal is to quantify the contribution of edges in the
input graph $G$ to an answer $\vec{u}$ for $q$. We adopt the convention that,
for the sake of measuring contribution, the database is viewed as consisting
of two types of data items—we reason about the contribution of the
_endogenous_ items while we take for granted the existence of the _exogenous_
items (that serve as out-of-game background) [DBLP:conf/tapp/SalimiBSB16,
DBLP:journals/sigmod/LivshitsBKS21, DBLP:journals/pvldb/MeliouGMS11]. Hence,
in our setup, we view the graph as consisting of two types of edges:
_endogenous edges_ and _exogenous edges_. Notationally, for a graph $G=(V,E)$
we denote by $E_{\mathsf{n}}$ and $E_{\mathsf{x}}$ the sets of endogenous and
exogenous edges, respectively, and we assume that $E$ is the disjoint union of
$E_{\mathsf{n}}$ and $E_{\mathsf{x}}$.

Our goal is to quantify the contribution of an edge $e\in E_{\mathsf{n}}$ to
an answer $\vec{u}=(u_{1},\ldots u_{k})$ of the query $q$, that is, to the
fact that $q[\vec{u}](G)=1$. To this end, we view the situation as a
cooperative game where the players are the endogenous edges. The Shapley value
of an edge $e\in E_{\mathsf{n}}$ in this setting will be denoted by
$\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)$.

$\mathrm{Shapley}\langle
q\rangle(G,\vec{u},e)\mathrel{\overset{\mathrm{def}}{\leavevmode\resizebox{0.0pt}{0.0pt}{=}}}\mathrm{Shapley}(E_{\mathsf{n}},v_{pq},e)$

where the function $\mathrm{Shapley}$ is as defined in Equation (2) and
$v_{pq}$ is the numerical function that takes as input a subset of the
endogenous edges and is defined as follows:

$v_{pq}(B)\mathrel{\overset{\mathrm{def}}{\leavevmode\resizebox{0.0pt}{0.0pt}{=}}}q[\vec{u}](G[B\cup
E_{\mathsf{x}}])-q[\vec{u}](G[E_{\mathsf{x}}])$

In particular, $v_{pq}(\emptyset)=0$. Put differently, we have the following.

$\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)=\\\ \sum_{B\subseteq
E_{\mathsf{n}}\setminus\\{e\\}}\frac{\lvert B\rvert!(\lvert
E_{\mathsf{n}}\rvert-\lvert B\rvert-1)!}{\lvert
E_{\mathsf{n}}\rvert!}\Big{(}q[\vec{u}](G[B\cup
E_{\mathsf{x}}\cup\\{e\\}])-q[\vec{u}](G[B\cup E_{\mathsf{x}}])\Big{)}$

For a CRPQ $q$, the computational problem $\mathsf{CRPQShapley}\langle
q\rangle$ is that of computing the Shapley value of a given edge:

Problem $\mathsf{CRPQShapley}\langle q\rangle$
---
Input: |  Graph $G$, node vector $\vec{u}=(u_{1},\ldots,u_{k})$, endogenous edge $e$
Goal: |  Compute $\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)$

When $q$ has only one atom, and is in fact an RPQ $(x,r,y)$ with $r$ being a
regular expression, we may replace $q$ with $r$ in the notation and write
$\mathrm{Shapley}\langle r\rangle(G,s,t,e)$ and $\mathsf{RPQShapley}\langle
r\rangle$ with the meaning of $\mathrm{Shapley}\langle q\rangle(G,s,t,e)$ and
$\mathsf{RPQShapley}\langle q\rangle$, respectively.

Here we show some examples for the computation of the Shapley values of edges
for different inputs.

######  Example 3.1.

We refer to the graph $G$ of Figure 1. By default, all edges are endogenous
unless stated otherwise. (Note that we denote by $e_{ij}$ the edge
$(v_{i},v_{j})$.)

  * •

$\mathrm{Shapley}\langle abc\rangle(G,v_{1},v_{6},e)$. Any edge that is not on
the only path that matches $abc$, namely $p\colon v_{1}\rightarrow
v_{3}\rightarrow v_{5}\rightarrow v_{6}$, will have the Shapley value of zero.
This is true since adding such an edge to $G[B\cup E_{\mathsf{x}}]$, where
$B\subseteq E_{\mathsf{n}}$, will not change the result of the path query. For
edges on the path $p$, the computations are similar to each other and they all
have the have same Shapley value. For one of them to change the query result,
it needs to appear after both other edges in the permutation of
$E_{\mathsf{n}}$. This happens in $\frac{9!}{3}$ of the overall $9!$
permutations. So we have:

$\mathrm{Shapley}\langle
abc\rangle(G,v_{1},v_{6},e_{13})=\mathrm{Shapley}\langle
abc\rangle(G,v_{1},v_{6},e_{35})=\mathrm{Shapley}\langle
abc\rangle(G,v_{1},v_{6},e_{56})=\frac{1}{3}\,.$

If we assume that $e_{13}$ is exogenous, then the other two edges will _split_
the contribution evenly. Then we get:

$\mathrm{Shapley}\langle
abc\rangle(G,v_{1},v_{6},e_{35})=\mathrm{Shapley}\langle
abc\rangle(G,v_{1},\allowbreak v_{6},e_{56})=\frac{1}{2}\,.$

  * •

$\mathrm{Shapley}\langle ab^{*}\rangle(G,v_{1},v_{6},e)$. This is a more
complicated computation, since there are two paths that match the regular
expression $ab^{*}$ (as we have seen in Example 2.1). Again, any edge that is
not on any of these paths will have a Shapley value of zero. But now, the
contributions of the remaining edges is not equal since, for instance,
$e_{12}$ is on both paths so we expect it to have higher contribution than the
others. For the edge $e_{26}$ to change the query result, it needs to appear
after edge $e_{12}$ but before at least one of $e_{24}$ and $e_{46}$.
Permutations where this happens are either permutations where $e_{26}$ appears
after $e_{12}$ and one of $e_{24}$ and $e_{46}$ but before the other one, and
there are $2\cdot\sum_{i=0}^{5}(i+2)!\binom{5}{i}(8-i-2)!=\frac{2}{12}\cdot
9!$ such permutations. Or permutations where $e_{26}$ appears after $e_{12}$
but before both $e_{24}$ and $e_{46}$, and there are
$\sum_{i=0}^{5}(i+1)!\binom{5}{i}(8-i-1)!=\frac{1}{12}\cdot 9!$ such
permutations. There are an overall of $9!$ possible permutations, so,

$\mathrm{Shapley}\langle ab^{*}\rangle(G,v_{1},v_{6},e_{26})=\frac{1}{4}\,.$

For the two edges $e_{24}$ and $e_{46}$, the computations are similar to each
other. For one of them to change the query, it needs to appear after $e_{12}$
and the other one, but before $e_{26}$. Similar to before, there are
$\sum_{i=0}^{5}(i+2)!\binom{5}{i}(8-i-2)!=\frac{1}{12}\cdot 9!$ permutations
where this happens, so,

$\mathrm{Shapley}\langle
ab^{*}\rangle(G,v_{1},v_{6},e_{24})=\mathrm{Shapley}\langle
ab^{*}\rangle(G,v_{1},v_{6},e_{46})=\frac{1}{12}\,.$

For the last edge $e_{12}$, it needs to appear after $e_{26}$ or after both
$e_{24}$, $e_{46}$. Permutations where this happens are either permutations
where $e_{12}$ appears after both $e_{24}$ and $e_{46}$ but before $e_{26}$,
after both $e_{26}$ and $e_{24}$ but before $e_{46}$, after both $e_{26}$ and
$e_{46}$ but before $e_{24}$, and there are
$3\cdot\sum_{i=0}^{5}(i+2)!\binom{5}{i}(8-i-2)!=\frac{3}{12}\cdot 9!$ such
permutations. Or permutations where $e_{12}$ appears after all three of
$e_{26},e_{24},e_{46}$, and there are
$\sum_{i=0}^{5}(i+3)!\binom{5}{i}(8-i-3)!=\frac{3}{12}\cdot 9!$ such
permutations. Or permutations where $e_{12}$ appears after $e_{26}$ but before
both $e_{24}$ and $e_{46}$, and there are
$\sum_{i=0}^{5}(i+1)!\binom{5}{i}(8-i-1)!=\frac{1}{12}\cdot 9!$ such
permutations. So overall we get that,

$\mathrm{Shapley}\langle ab^{*}\rangle(G,v_{1},v_{6},e_{12})=\frac{7}{12}\,.$

Note that that $\sum_{e\in E_{\mathsf{n}}}{\mathrm{Shapley}\langle
ab^{*}\rangle(G,v_{1},v_{6},e)}=1$, which is expected since the sum of the
Shapley values of all players is always equal to the value of the game for the
whole set of players [shapley:book1952].∎

##  4 Complexity of Exact Computation

In this section, we study the complexity of $\mathsf{CRPQShapley}\langle
q\rangle$, where the goal is to compute the exact Shapley value of an edge.
Note that the query $q$ is fixed in the analysis, and hence, every $q$ defines
a separate computational problem $\mathsf{CRPQShapley}\langle q\rangle$.

###  4.1 Results

Our main results for this section are the following theorems, showing that the
$\mathsf{CRPQShapley}\langle q\rangle$ is computationally intractable for
almost _every_ CRPQ $q$, except for limited cases.

######  Theorem 4.1 (Hardness).

Let $q$ be a CRPQ. If $q$ has a non-redundant atom $i$ with a language that
contains a word of length three or more, then $\mathsf{CRPQShapley}\langle
q\rangle$ is $\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$-complete.

Recall that $\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$ is the class of functions
computable in polynomial time with an oracle to a problem in $\mathrm{\\#P}$
(e.g., counting the number of satisfying assignments of a propositional
formula). This class is considered intractable, and above the polynomial
hierarchy (Toda’s theorem [DBLP:journals/siamcomp/Toda91]).

The question of whether the condition of Theorem 4.1 is necessary for hardness
remains open. Yet, we can show that it is, indeed, necessary, in the case of a
single atom (RPQ):

[Tractability] Let $q$ be an RPQ with the regular expression $r$. If every
word in $L(r)$ is of length at most two, then $\mathsf{RPQShapley}\langle
q\rangle$ is solvable in polynomial time.

######  Proof 4.2 (Proof of Theorem 4.1).

As mentioned before, the problem of computing Shapley values in our setting
reduces to computing $\lvert\mathcal{M}(G,s,t,L,k)\rvert$. We will now show
that $\lvert\mathcal{M}(G,s,t,L,k)\rvert$ can be computed in polynomial time
in this case. First, let us observe that we can compute
$\lvert\mathcal{M}(G,s,t,L,k)\rvert$ by computing the complement set
$\lvert\overline{\mathcal{M}(G,s,t,L,k)}\rvert$ which is defined similarly but
for subsets where there is no path, and subtracting from the overall number of
subsets of size $k$ of endogenous edges:

$\lvert\mathcal{M}(G,s,t,L,k)\rvert=\binom{m_{n}}{k}-\lvert\overline{\mathcal{M}(G,s,t,L,k)}\rvert$

So it suffices to show how to compute
$\lvert\overline{\mathcal{M}(G,s,t,L,k)}\rvert$.

Let $L=\\{w_{0},\ldots,w_{l}\\}$. For a subset of endogenous edges to be in
$\overline{\mathcal{M}(G,s,t,L,k)}$, it should not connect, with
$E_{\mathsf{x}}$, any path from $s$ to $t$ matching $w\in L$, i.e., matching
one of $w_{0},\ldots,w_{l}$. In other words, it should not connect any path of
size 2 matching some $\lvert w_{i}\rvert=2$, or any path of size 1 matching
some $\lvert w_{i}\rvert=1$.

This divides endogenous edges of the graph into 4 categories:

  * •

$\mathsf{Permitted}$. Edges which are not part of any such path.

  * •

$\mathsf{OnPath2E}$. Edges which are on a path of size 2 matching some
$w_{i}$, where both edges are endogenous.

  * •

$\mathsf{OnPath2X}$. Edges which are on a path of size 2 matching some
$w_{i}$, where one of the edges is exogenous.

  * •

$\mathsf{OnPath1}$. Edges which are on a path of size 1 matching some $w_{i}$.

These are disjoint paths, as we assume that there are no parallel edges, and
edges on a path of size 1 can not also be on paths of size 2 and vice versa.

Each subset of size $k$ in $\overline{\mathcal{M}(G,s,t,L,k)}$ has no edges
from $\mathsf{OnPath1}$ as such edges make a path, and no edges from
$\mathsf{OnPath2X}$ as such edges connect a path along with $E_{\mathsf{x}}$,
$i$ edges from $\mathsf{Permitted}$, and $k-i$ edges from $\mathsf{OnPath2}$
such that no whole path is added, meaning a maximum of one edge is added from
each path of size 2. For each $i$, this translates to
$\binom{\lvert\mathsf{Permitted}\rvert}{i}$ options for edges from
$\mathsf{Permitted}$, and
$2{\binom{\frac{\lvert\mathsf{OnPath2}\rvert}{2}}{k-i}}$ options for edges
from $\mathsf{OnPath2}$; choosing $k-i$ paths from
$\frac{\lvert\mathsf{OnPath2}\rvert}{2}$ paths, and for each path there are 2
possibilities for edges. All in all we get that:

$\lvert\overline{\mathcal{M}(G,s,t,L,k)}\rvert=\sum_{i=0}^{k}2{\binom{\lvert\mathsf{Permitted}\rvert}{i}}{\binom{\frac{\lvert\mathsf{OnPath2}\rvert}{2}}{k-i}}$

Which can be computed in polynomial time.

Hence, we get a full classification for RPQs:

######  Corollary 4.3.

Let $q$ be an RPQ with the regular expression $r$. Assuming
$\mathrm{P}\neq\mathrm{NP}$, the following are equivalent:

  1. 1.

$\mathsf{CRPQShapley}\langle q\rangle$ is solvable in polynomial time.

  2. 2.

Every word in $L(r)$ is of length at most two.

Next, in Section 4.2 we prove Theorem 4.1, and in Section
LABEL:sec:exact_tract we prove Theorem 4.1.

###  4.2 Proof of Hardness

Membership in $\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$ is straightforward from
the definition of the Shapley value in Equation (2). Indeed,
$\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)$ can be computed using an
oracle to the problem of counting the number of permutations over the edge set
such that $e$ changes the query from zero (false) to one (true). For the
$\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$-hardness, we prove it in a sequence of
reductions. We begin with hardness for the special case where the language
consists of a single three-letter word. For that, we will use a result by
Livshits et al. [DBLP:journals/sigmod/LivshitsBKS21] on the computation of
Shapley values for facts in relational databases. We use that to prove
hardness for the general case of a regular language (or any language) with one
or more words of length at least three, even when restricted to simple graphs.

We first recall the result of Livshits et al.
[DBLP:journals/sigmod/LivshitsBKS21]. They considered relational databases $D$
where some of the facts are endogenous and the rest exogenous. As in our
notation, the corresponding subsets of $D$ are denoted by $D_{\mathsf{n}}$ and
$D_{\mathsf{x}}$, respectively. For a Boolean query $q$ that maps every
database into $\mathord{\\{0,1\\}}$, they defined the Shapley value of a fact
similarly to the way we define the Shapley value of an edge: the endogenous
facts are the players and the query is the wealth function:

$\mathrm{Shapley}\langle
q\rangle(D,f)=\mathrm{Shapley}(D_{\mathsf{n}},v_{db},f)$

where $v_{db}(E)=q(E\cup D_{\mathsf{x}})-q(D_{\mathsf{x}})$. They established
a complete classification of the class of conjunctive queries without self-
joins into tractable and intractable queries for the computation of the
Shapley value. What is relevant to us is that the following conjunctive query
is $\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$-hard:

$Q_{\mathsf{RST}}()\colon\,\exists{x,y}[R(x)\land S(x,y)\land T(y)]$

In addition, we define a special kind of graphs that will help us in some of
the proofs. A graph $G=(V,E)$ is called a _leveled graph_ if there exists a
split of vertices into levels $V_{0},\ldots,V_{k}$, such that:

  1. 1.

The set of vertices $V$ is the disjoint union of $V_{0},\ldots,V_{k}$.

  2. 2.

Edges are only between vertices in consecutive levels.

lightgray R
---
a
b
c
lightgray S
---
a | c
a | d
b | c
d | c

Transitions $(1),(2),(4),(5)$, follow from definitions. We need to prove
transition $(3)$; if adding $a$ to $S\cup E_{\mathsf{x}}$ connects a path from
$s$ to $t$ in $G$, then, adding $a_{k}$ to $S^{\prime}\cup
E_{\mathsf{x}}^{\prime}$ connects a path from $s^{\prime}$ to $t^{\prime}$ in
$G^{\prime}$ that matches $r$, where $S^{\prime}$ is the subset containing all
edges $e_{i}$ for each edge $e\in S$ and edges $a_{i}$ for $i\neq k$.

First, we will need to prove that there is no path from $s^{\prime}$ to
$t^{\prime}$ in $G^{\prime}$ using only $S^{\prime}\cup
E_{\mathsf{x}}^{\prime}$ matching $r$. Let us assume that there is, then this
path contains a sub-path from $s$ to $t$ of edges $e_{i}$, for each such edge
$e_{i}$, $e\in S$ by the way of reduction, so we get that there is a path from
$s$ to $t$ in $G$ using $S\cup E_{\mathsf{x}}$ by contradiction to that $a$ is
needed to connect such path. Now we will prove that adding $a_{k}$ connects a
path from $s^{\prime}$ to $t^{\prime}$ matching $r$. We know that adding $a$
to $S\cup E_{\mathsf{x}}$ connects a path from $s$ to $t$ in $G$ so from that
we get that adding $a_{k}$ to $S^{\prime}\cup E_{\mathsf{x}}^{\prime}$
connects a path from $s$ to $t$ in $G^{\prime}$ that is the same path as in
$G$ but each edge is split into $c$ edges, the overall path from $s^{\prime}$
to $t^{\prime}$ will be composed the only path from $s^{\prime}$ to $s$ and
then the path we mentioned from $s$ to $t$ and finally the path from $t$ to
$t^{\prime}$. We will now show that this path matches $r$ by simulating a run
of the DFA for $r$ and showing that it ends in an accepting state.

Starting from the initial state $v_{0}$, the path from $s^{\prime}$ to $s$
would transition the automaton into state $v_{i}$, as this path was
constructed according to the transitions of the automaton. Then, each pass
through a collection of edges $e_{k}$ that match an edge $e$ in the original
graph keeps the automaton in the same state, this is because going through
their labels creates a cycle. Since the path from $s$ to $t$ goes through a
finite number of such transitions, we get that simulating the path until $t$
keeps the automaton in state $v_{i}$. Finally, simulating the last part is
similar to the first part, and it would transition the automaton into state
$v_{k}$ which is an accepting state. This means that adding $e_{k}$ connects a
path from $s^{\prime}$ to $t^{\prime}$ matching $r$.

$\Longleftarrow:$

$\mathrm{Shapley}\langle
r\rangle(G^{\prime},s^{\prime},t^{\prime},a_{k})>0\underset{(1)}{\Longrightarrow}\exists
S^{\prime}\subset E_{\mathsf{n}}^{\prime}:q_{r}(G^{\prime}[S^{\prime}\cup
E_{\mathsf{x}}^{\prime}\cup\\{a_{k}\\}],s^{\prime},t^{\prime})-q_{r}(G^{\prime}[S^{\prime}\cup
E_{\mathsf{x}}^{\prime}],s^{\prime},t^{\prime})>0\underset{(2)}{\Longrightarrow}$
Adding $a_{k}$ to $S^{\prime}\cup E_{\mathsf{x}}^{\prime}$ connects a path
from $s^{\prime}$ to $t^{\prime}$ in $G^{\prime}$ that matches $r$
$\underset{(3)}{\Longrightarrow}$ Adding $a$ to $S\cup E_{\mathsf{x}}$
connects a path from $s$ to $t$ in $G$, where $S$ is the subset containing all
edges $e\in E$ s.t. $\forall i\in\\{1,\ldots,c\\}:e_{i}\in S^{\prime}$
$\underset{(4)}{\Longrightarrow}\exists S\subset
E_{\mathsf{n}}:q_{\mathord{\Sigma^{*}}}(G(S\cup
E_{\mathsf{x}}\cup\\{a\\}),s,t)-q_{\mathord{\Sigma^{*}}}(G(S\cup
E_{\mathsf{x}}),s,t)>0\underset{(5)}{\Longrightarrow}\mathrm{Shapley}\langle\mathord{\Sigma^{*}}\rangle(G,s,t,a)>0$.

Again, transitions $(1),(2),(4),(5)$, follow from definitions. We need to
prove transition $(3)$; if adding $a_{k}$ to $S^{\prime}\cup
E_{\mathsf{x}}^{\prime}$ connects a path from $s^{\prime}$ to $t^{\prime}$ in
$G^{\prime}$ that matches $r$, then, adding $a$ to $S\cup E_{\mathsf{x}}$
connects a path from $s$ to $t$ in $G$, where $S$ is the subset containing all
edges $e\in E$ s.t. $\forall i\in\\{1,...,c\\}:e_{i}\in S^{\prime}$.

First, we will need to prove that there is no path from $s$ to $t$ in $G$
using only $S\cup E_{\mathsf{x}}$. Let us assume that there is, then as shown
before there is a path from $s^{\prime}$ to $t^{\prime}$ in $G^{\prime}$ using
only $S^{\prime}\cup E_{\mathsf{x}}^{\prime}$ that matches $r$, by
contradiction to that $a_{k}$ is needed to connect such path. Now we will
prove that adding $a$ connects a path from $s$ to $t$. We know that adding
$a_{k}$ to $S^{\prime}\cup E_{\mathsf{x}}^{\prime}$ connects a path from
$s^{\prime}$ to $t^{\prime}$ in $G^{\prime}$ that matches $r$, specifically,
it connects a sub-path from $s$ to $t$. We can see that if such sub-path
passes through some $e^{\prime}_{k}$, it passes through all $e^{\prime}_{i}$
so all $e^{\prime}_{i}\in S^{\prime}$, and consequently $e^{\prime}\in S$.
This means that adding $a$ to $S\cup E_{\mathsf{x}}$ connects a path from $s$
to $t$.

It is straight-forward to show that the problem is in $\mathrm{NP}$ for a
start, as any subset of endogenous edges that adding $e$ to it connects a
matching path serves as a witness and can be verified in polynomial time. We
will prove $\mathrm{NP}$-hardness by showing a reduction from the problem of
determining whether
$\mathrm{Shapley}\langle\mathord{\Sigma^{*}}\rangle(G,s,t,e)>0$ which we
showed to be $\mathrm{NP}$-complete. Given an input instance $(G,s,t,a)$, we
will show how to construct an instance
$(G^{\prime},s^{\prime},t^{\prime},a_{k})$ for our problem such that:

$\mathrm{Shapley}\langle\mathord{\Sigma^{*}}\rangle(G,s,t,a)>0\iff\mathrm{Shapley}\langle
r\rangle(G^{\prime},s^{\prime},t^{\prime},a_{k})>0$

Since $L(r)$ is infinite, we know that its corresponding DFA graph that we
will denote by $G_{DFA}$ has at least one cycle. We find a path from an
initial state to an accepting state that passes through a node $v_{i}$ that is
part of a cycle. We will denote the path by:
$l:v_{0}\rightarrow\ldots\rightarrow v_{i}\rightarrow\ldots\rightarrow v_{k}$.

We assumed the node $v_{i}$ is part of a cycle, we denote the labels which are
along the cycle starting from $v_{i}$ by
$w_{cycle}=\sigma_{0}\dots\sigma_{c}$. The graph $G^{\prime}$ will be
constructed so that it any path in it from $s^{\prime}$ to $t^{\prime}$
matches $r$ in the following way, containing 3 sub-graphs:

  * •

The path $s^{\prime}=v_{0}\rightarrow\ldots\rightarrow v_{i}^{in}=s$, with the
same labels as in the DFA, the edge $(v_{i-1},v_{i}^{in})$ will have the label
of $(v_{i-1},v_{i})$. (_exogenous_).

  * •

A copy of the graph $G$ where each edge $e$ is split into $c$ edges with
labels matching $w_{cycle}$ which we will denote by $e_{1}...e_{c}$. The node
$s=v_{i}^{in}$ will serve as the source $s$ in the original graph, and the
node $t=v_{i}^{out}$ will serve as the target $t$ in the original graph.
(_endogenous/exogenous according to original edge_).

  * •

The path $t=v_{i}^{out}\rightarrow\ldots\rightarrow v_{k}$, with the same
labels as in the DFA, the edge $(v_{i}^{out},v_{i+1})$ will have the label of
$(v_{i},v_{i+1})$. (_exogenous_).

We complete the proof by showing that that for each $a\in E$ and $a_{k}\in
E^{\prime}$ that is any edge that sits on the path that replaced the edge $a$
in $G^{\prime}$ it holds that
$\mathrm{Shapley}\langle\mathord{\Sigma^{*}}\rangle(G,s,t,a)>0$ if and only if
$\mathrm{Shapley}\langle r\rangle(G^{\prime},s^{\prime},t^{\prime},a_{k})>0$.

Finally, we extend Lemma LABEL:lemma:hardness_approx from RPQs to CRPQs. Let
$q$ be a CRPQ without redundancy. If $L(r_{i})$ is infinite for some atom $i$
of $q$, then determining whether $\mathrm{Shapley}\langle
q\rangle(G,\vec{u},e)>0$ is $\mathrm{NP}$-complete.

The proof here is very similar to the proof we had for Theorem 4.1, and is
provided in the Appendix for completeness.

######  Proof 5.7.

It is straightforward to show that the problem is in $\mathrm{NP}$. For
hardness, we know that there exists an atom $i$ of $q$ such that it is non-
redundant and $L(r_{i})$ is infinite. We will show a reduction from the
problem of deciding whether $\mathrm{Shapley}\langle r_{i}\rangle(G,s,t,e)>0$
which we showed to be $\mathrm{NP}$-hard and that proves the lemma.

Given an input graph $G$, source node $s$, target node $t$ and edge $a$, the
reduction would work the same way as in the proof of Theorem 4.1 and we
construct a $G^{*}$ that is a union of the graph $G_{i}$ that we get from that
atom $i$ is non-redundant along with an assignment $\vec{v}$ (Observation
2.3), and the original graph $G$. The same claims hold as in the previous
proof and we get:

$\mathrm{Shapley}\langle r_{i}\rangle(G,s,t,a)=\mathrm{Shapley}\langle
q\rangle(G^{*},\vec{v},a)$

That concludes the proof of the reduction as given a solution for the problem
of determining whether $\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)>0$ we
can solve the problem of determining whether $\mathrm{Shapley}\langle
r_{i}\rangle(G,s,t,e)>0$ in polynomial time.

##### Open Problem: Directed Acyclic Graphs

It is worth noting that the proof as shown in this section, does not work when
the graph is acyclic as it relies on Lemma LABEL:lemma:simplepath as a basis.
Which states that the decision problem that takes as input, a graph $G$,
source node $s$, target node $t$, and edge $e$, and decides whether $e$ lies
on a simple path from $s$ to $t$ in graph $G$, is $\mathrm{NP}$-complete.
While this is true in the case of a general graph $G$, it is not when the
graph is acyclic, where the problem can be solved in polynomial time. This
leaves the problem of whether there is a different dichotomy when restricted
to DAGs open. However, for exact computation there is no change even when
restricted to DAGs as the proofs work as is.

###  5.3 Proof of Tractability

We will now show that for any query that the condition for hardness does not
hold, a multiplicative FPRAS exists. We will start by showing that in this
case, the gap property holds: if the Shapley value is nonzero, then it must be
at least the reciprocal of a polynomial.

######  Lemma 5.8.

Let $q$ be a fixed CRPQ without redundancy. If $L(r_{i})$ is finite for every
atom $i$ of $q$, then $\mathrm{Shapley}\langle q\rangle(G,\vec{u}$, e) is
either zero or at least $1/p(\lvert E\rvert)$.

######  Proof 5.9.

If there is no subset $S$ of $E_{\mathsf{n}}$ such that adding $e$ to it along
with $E_{\mathsf{x}}$ changes the value of query $q$ from false to true, then
$\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)=0$. Otherwise, let $S$ be a
minimal such set, it holds that $\lvert S\rvert\leq k_{1}+\ldots+k_{m}=k$,
where $k_{i}$ is the length of the longest word in $L(r_{i})$; the language
for the $i$-th atom in $q$, as at worst case, the paths match the longest word
for each RPQ. And since each $L(r_{i})$ is finite, each $k_{i}$ is a finite
constant. Thus, $k$ also is a finite constant.

The probability to choose a permutation $\sigma$, such that $\sigma_{e}$ is
exactly $S\setminus\\{e\\}$ is (|S|-1)!(mn-|S|)!mn! ≥(mn-k)!mn! . Hence, we
have

$\displaystyle\mathrm{Shapley}\langle
q\rangle(G,\vec{u},e)\geq\frac{(m_{n}-k))!}{m_{n}!}\frac{1}{(m_{n}-k+1)\cdot\ldots\cdot
m_{n}}=\frac{1}{p(\lvert E\rvert)}$

since $\lvert E\rvert=m_{n}+m_{e}$.

######  Lemma 5.10.

Let $q$ be a CRPQ without redundancy. If $L(r_{i})$ is finite for every atom
$i$ of $q$, then $\mathsf{CRPQShapley}\langle q\rangle$ has both an additive
and a multiplicative FPRAS.

######  Proof 5.11.

Using the Chernoff-Hoeffding bound, we can get an additive FPRAS of the value
$\mathrm{Shapley}\langle q\rangle(G,\vec{u},e)$, by simply taking the ratio of
successes over $O(\log(1/\delta)/\epsilon^{2})$ trials of the following
experiment:

  * •

Select a random permutation $(e_{1},...,e_{m})$ over the set of endogenous
edges $E_{\mathsf{n}}$.

  * •

Suppose that $e=e_{i}$, and let $E_{i-1}=\\{e_{1},...,e_{i-1}\\}$. If
$q[\vec{u}](G[E_{i-1}\cup E_{\mathsf{x}}\cup\\{e\\}])=1$ and
$q[\vec{u}](G[E_{i-1}\cup E_{\mathsf{x}}])=0$, then report “success,”
otherwise, report “failure.”

Now from Lemma 5.8 (that the gap property holds), we can easily get that an
additive FPRAS also serves as a multiplicative one.

######  Proof 5.12 (Proof of Theorem LABEL:thm:approx).

Lemma 4.2 shows the hardness side, as it implies that under conventional
complexity assumptions, there is no polynomial-time multiplicative
approximation when there is an atom with an infinite language (as it would
allow to determine whether the Shapley value is nonzero). Lemma 5.10 shows an
FPRAS for the tractable case where all atom have finite languages.

##  6 Shapley Value of Vertices

In this section, we discuss the differences between the computation complexity
of the Shapley value for edges and the Shapley values for vertices in the
graph. Similarly to the case for edges, given a conjunctive regular path query
$q$, our goal is to quantify the contribution of vertices in the input graph
$G$ to an answer of the path query. The graph consists of two types of
vertices— _endogenous vertices_ , and _exogenous vertices_.

Notationally, for a graph $G=(V,E)$ we denote by $V_{\mathsf{n}}$ and
$V_{\mathsf{x}}$ the sets of endogenous and exogenous vertices, respectively,
and we assume that $V$ is the disjoint union of $V_{\mathsf{n}}$ and
$V_{\mathsf{x}}$. We denote by $\mathrm{Shapley}\langle q\rangle(G,\vec{u},v)$
the Shapley value of a vertex $v\in V_{\mathsf{n}}$.

$\mathrm{Shapley}\langle
q\rangle(G,\vec{u},v)\mathrel{\overset{\mathrm{def}}{\leavevmode\resizebox{0.0pt}{0.0pt}{=}}}\mathrm{Shapley}(V_{\mathsf{n}},v_{pq}^{\mathsf{v}},v)$

Where $v_{pq}^{\mathsf{v}}$ is defined as follows:

$v_{pq}^{\mathsf{v}}(B)\mathrel{\overset{\mathrm{def}}{\leavevmode\resizebox{0.0pt}{0.0pt}{=}}}q[\vec{u}](G[B\cup
V_{\mathsf{x}}])-q[\vec{u}](G[V_{\mathsf{x}}])$

We denote by $\mathsf{CRPQShapley}^{\mathsf{v}}\langle q\rangle$ and
$\mathsf{RPQShapley}^{\mathsf{v}}\langle r\rangle$, The corresponding
computational problems to those defined earlier for the Shapley values of
edges. We now state the results we have with some notes on the changes that
should be made in the proofs.

###  6.1 Complexity of Exact Computation

The hardness part is almost the same as the case of edges. We begin with
hardness for the special case where the regular language (or any language)
consists of a single four-letter word instead of three. For that, we use the
same result by Livshits et al. [DBLP:journals/sigmod/LivshitsBKS21] on the
computation of Shapley values for facts in relational databases. From this we
continue the same series of reductions as done for edges to get the hardness
for a general CRPQ. The tractable part is also tractable when looking at
vertices. So we have the following:

######  Theorem 6.1.

The following hold for a CRPQ $q$.

  1. 1.

If $q$ has a non-redundant atom $i$ with a language that contains a word of
length four or more, then $\mathsf{CRPQShapley}\langle q\rangle$ is
$\mathord{\mathrm{FP}^{\mathrm{\\#P}}}$-complete.

  2. 2.

If $q$ has only one atom with regular expression $r$. If every word in $L(r)$
is of length at most two, then $\mathsf{CRPQShapley}^{\mathsf{v}}\langle
q\rangle$ is solvable in polynomial time.

Note that in the case of vertices, we leave a gap in the classification of
RPQs. Theorem 6.1 states that if there exists a word of length four or more,
then the problem is hard, and if all words are of length at most two, then the
problem is solvable in polynomial time. The case where there are words of
length three but not longer remains an open problem (as opposed to the case of
edges where we had a full dichotomy on RPQs due to Corollary 4.3).

###  6.2 Complexity of Approximation

For approximation, we get the exact same dichotomy on CRPQs. We know from
before that also the decision problem that decides whether a vertex $v$ lies
on a simple path from $s$ to $t$ in graph $G$, is $\mathrm{NP}$-complete. From
that we get that the problem of determining whether
$\mathrm{Shapley}\langle\mathord{\Sigma^{*}}\rangle(G,s,t,v)>0$ is also
$\mathrm{NP}$-complete. From that we continue with a series of reductions that
is almost identical to what we have for the case of edges.

######  Theorem 6.2.

Let $q$ be a CRPQ without redundancy. If $L(r_{i})$ is finite for every atom
$i$ of $q$ , then $\mathsf{CRPQShapley}^{\mathsf{v}}\langle q\rangle$ has a
multiplicative FPRAS. Otherwise, $\mathsf{CRPQShapley}^{\mathsf{v}}\langle
q\rangle$ has no multiplicative approximation (of any ratio) or else
$\mbox{NP}\subseteq\mbox{BPP}$.

In conclusion, we establish that the complexity for both exact computation and
approximation of the Shapley value of vertices is very similar to the case of
edges. It is generally hard to compute exact values; it is sufficient for the
CRPQ to have an atom that is non-redundant and contains a word of length four
or more for the computation to be hard, while for RPQs we identify that the
tractable family of queries for edges is also tractable for vertices. For
approximation, we show that we have an identical dichotomy for when queries
admit a multiplicative FPRAS.

##  7 Concluding Remarks

This work continues the research line of responsibility and contribution in
databases. We presented the graph-database perspective where the queries are
(conjunctive) regular path queries, and the responsibility measure is the
Shapley value. We investigated the data complexity of the Shapley value of
edges in the graph. For the exact computation, we showed that it is generally
hard, while we also show a specific family of CRPQs where the computation can
be done in polynomial time. While this is not a full dichotomy on CRPQs, the
tractable case we showed basically defines a dichotomy on the class of RPQs.
It remains an open problem whether the condition we have for hardness defines
a full dichotomy on CRPQs. We have also studied approximation of the Shapley
values in the form of an FPRAS. An additive FPRAS is easy to achieve using
Monte-Carlo sampling, while a multiplicative approximation is harder. We
showed a family of CRPQs where the gap property holds, and hence, an additive
FPRAS can be transformed into a multiplicative one. These are the CRPQs where
every atom has a finite language. For the other CRPQs, we showed that it is
hard to obtain any multiplicative approximation. Thus, we achieved a dichotomy
on CRPQs for the case of approximation (assuming no redundant atoms).

Several problems remain open. We still do not have a full dichotomy for exact
computation of Shapley values. In addition, the proof of the hardness of
approximation in Section LABEL:sec:approx_hard is not valid when the graph in
hand is acyclic; this raises the question of whether there are better
opportunities of efficient approximations when the problem is restricted to
acyclic graphs. Another direction is investigating richer path languages, for
example, allowing existentially quantified variables in the query, or negated
atoms.

## References

  * [1] Manish Kumar Anand, Shawn Bowers, and Bertram Ludäscher.  Techniques for efficiently querying scientific workflow provenance graphs.  In Ioana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Léger, Felix Naumann, Anastasia Ailamaki, and Fatma Özcan, editors, EDBT 2010, 13th International Conference on Extending Database Technology, Lausanne, Switzerland, March 22-26, 2010, Proceedings, volume 426 of ACM International Conference Proceeding Series, pages 287–298, None, 2010. ACM.  URL: https://doi.org/10.1145/1739041.1739078, doi:10.1145/1739041.1739078.
  * [2] Marcelo Arenas and Jorge Pérez.  Querying semantic web data with SPARQL.  In Maurizio Lenzerini and Thomas Schwentick, editors, Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12-16, 2011, Athens, Greece, pages 305–316, None, 2011. ACM.  URL: https://doi.org/10.1145/1989284.1989312, doi:10.1145/1989284.1989312.
  * [3] Pablo Barceló Baeza.  Querying graph databases.  In Richard Hull and Wenfei Fan, editors, Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 175–188, None, 2013\. ACM.  URL: https://doi.org/10.1145/2463664.2465216, doi:10.1145/2463664.2465216.
  * [4] Pablo Barceló, Leonid Libkin, Anthony W Lin, and Peter T Wood.  Expressive languages for path queries over graph-structured data.  ACM Transactions on Database Systems (TODS), 37(4):1–46, 2012.
  * [5] Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi.  Rewriting of regular expressions and regular path queries.  In Victor Vianu and Christos H. Papadimitriou, editors, Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia, Pennsylvania, USA, pages 194–204, None, 1999. ACM Press.  URL: https://doi.org/10.1145/303976.303996, doi:10.1145/303976.303996.
  * [6] Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi.  Containment of conjunctive regular path queries with inverse.  In Anthony G. Cohn, Fausto Giunchiglia, and Bart Selman, editors, KR 2000, Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference, Breckenridge, Colorado, USA, April 11-15, 2000, pages 176–185, None, 2000. Morgan Kaufmann.
  * [7] Mariano P. Consens and Alberto O. Mendelzon.  Graphlog: a visual formalism for real life recursion.  In Daniel J. Rosenkrantz and Yehoshua Sagiv, editors, Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee, USA, pages 404–416, None, 1990. ACM Press.  URL: https://doi.org/10.1145/298514.298591, doi:10.1145/298514.298591.
  * [8] Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood.  A graphical query language supporting recursion.  In Umeshwar Dayal and Irving L. Traiger, editors, Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, CA, USA, May 27-29, 1987, pages 323–330, None, 1987. ACM Press.  URL: https://doi.org/10.1145/38713.38749, doi:10.1145/38713.38749.
  * [9] Daniel Deutch, Nave Frost, Benny Kimelfeld, and Mikaël Monet.  Computing the shapley value of facts in query answering.  CoRR, abs/2112.08874, 2021.
  * [10] Wenfei Fan.  Graph pattern matching revised for social network analysis.  In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT ’12, Berlin, Germany, March 26-29, 2012, pages 8–21, None, 2012. ACM.  URL: https://doi.org/10.1145/2274576.2274578, doi:10.1145/2274576.2274578.
  * [11] Daniela Florescu, Alon Y. Levy, and Dan Suciu.  Query containment for conjunctive queries with regular expressions.  In Alberto O. Mendelzon and Jan Paredaens, editors, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA, pages 139–148, None, 1998. ACM Press.  URL: https://doi.org/10.1145/275487.275503, doi:10.1145/275487.275503.
  * [12] Steven Fortune, John E. Hopcroft, and James Wyllie.  The directed subgraph homeomorphism problem.  Theor. Comput. Sci., 10:111–121, 1980.  URL: https://doi.org/10.1016/0304-3975(80)90009-2, doi:10.1016/0304-3975(80)90009-2.
  * [13] Joseph Y. Halpern and Judea Pearl.  Causes and explanations: A structural-model approach: Part 1: Causes.  In UAI, pages 194–202, None, 2001. None.
  * [14] Anthony Hunter and Sébastien Konieczny.  On the measure of conflicts: Shapley inconsistency values.  Artif. Intell., 174(14):1007–1026, 2010.
  * [15] Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag.  Query games in databases.  SIGMOD Rec., 50(1):78–85, 2021.
  * [16] Ester Livshits and Benny Kimelfeld.  The shapley value of inconsistency measures for functional dependencies.  In Ke Yi and Zhewei Wei, editors, 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, volume 186 of LIPIcs, pages 15:1–15:19, None, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.  URL: https://doi.org/10.4230/LIPIcs.ICDT.2021.15, doi:10.4230/LIPIcs.ICDT.2021.15.
  * [17] Scott M Lundberg and Su-In Lee.  A unified approach to interpreting model predictions.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4765–4774. Curran Associates, Inc., None, 2017\.  URL: http://papers.nips.cc/paper/7062-a-unified-approach-to-interpreting-model-predictions.pdf.
  * [18] Artem Lysenko, Irina A. Roznovat, Mansoor Saqi, Alexander Mazein, Christopher J. Rawlings, and Charles Auffray.  Representing and querying disease networks using graph databases.  BioData Min., 9:23, 2016.  URL: https://doi.org/10.1186/s13040-016-0102-8, doi:10.1186/s13040-016-0102-8.
  * [19] Richard T. B. Ma, Dah-Ming Chiu, John Chi-Shing Lui, Vishal Misra, and Dan Rubenstein.  Internet economics: The use of shapley value for ISP settlement.  IEEE/ACM Trans. Netw., 18(3):775–787, 2010.  URL: https://doi.org/10.1109/TNET.2010.2049205, doi:10.1109/TNET.2010.2049205.
  * [20] Wim Martens and Tina Trautner.  Evaluation and enumeration problems for regular path queries.  In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, pages 19:1–19:21, None, 2018. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.  URL: https://doi.org/10.4230/LIPIcs.ICDT.2018.19, doi:10.4230/LIPIcs.ICDT.2018.19.
  * [21] Wim Martens and Tina Trautner.  Dichotomies for evaluating simple regular path queries.  ACM Trans. Database Syst., 44(4):16:1–16:46, 2019.  URL: https://doi.org/10.1145/3331446, doi:10.1145/3331446.
  * [22] Corto Mascle, Christel Baier, Florian Funkev, Simon Jantsch, and Stefan Kiefer.  Responsibility and verification: Importance value in temporal logics.  In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–14. IEEE, 2021.
  * [23] Alexandra Meliou, Wolfgang Gatterbauer, Katherine F. Moore, and Dan Suciu.  The complexity of causality and responsibility for query answers and non-answers.  Proc. VLDB Endow., 4(1):34–45, 2010.
  * [24] Alberto O. Mendelzon and Peter T. Wood.  Finding regular simple paths in graph databases.  SIAM J. Comput., 24(6):1235–1258, 1995.  URL: https://doi.org/10.1137/S009753979122370X, doi:10.1137/S009753979122370X.
  * [25] Stefano Moretti, Fioravante Patrone, and Stefano Bonassi.  The class of microarray games and the relevance index for genes.  Top, 15(2):256–280, 2007.
  * [26] Ramasuri Narayanam and Yadati Narahari.  A shapley value-based approach to discover influential nodes in social networks.  IEEE Trans Autom. Sci. Eng., 8(1):130–147, 2011.  URL: https://doi.org/10.1109/TASE.2010.2052042, doi:10.1109/TASE.2010.2052042.
  * [27] Alon Reshef, Benny Kimelfeld, and Ester Livshits.  The impact of negation on the complexity of the shapley value in conjunctive queries.  In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 285–297, None, 2020. ACM.  URL: https://doi.org/10.1145/3375395.3387664, doi:10.1145/3375395.3387664.
  * [28] Gorka Sadowski and Philip Rathle.  Fraud detection: Discovering connections with graph databases.  White Paper-Neo Technology-Graphs are Everywhere, 13, 2014.
  * [29] Babak Salimi, Leopoldo E. Bertossi, Dan Suciu, and Guy Van den Broeck.  Quantifying causal effects on query answering in databases.  In TaPP, None, 2016. USENIX Association.
  * [30] Lloyd S Shapley.  A value for n-person games.  In Harold W. Kuhn and Albert W. Tucker, editors, Contributions to the Theory of Games II, pages 307–317. Princeton University Press, Princeton, 1953.
  * [31] Seinosuke Toda.  PP is as hard as the polynomial-time hierarchy.  SIAM J. Comput., 20(5):865–877, 1991.
  * [32] Tjeerd van Campen, Herbert Hamers, Bart Husslage, and Roy Lindelauf.  A new approximation method for the shapley value applied to the WTC 9/11 terrorist attack.  Soc. Netw. Anal. Min., 8(1):3:1–3:12, 2018.  URL: https://doi.org/10.1007/s13278-017-0480-z, doi:10.1007/s13278-017-0480-z.
  * [33] Moshe Y. Vardi.  The complexity of relational query languages (extended abstract).  In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 137–146, None, 1982. ACM.  URL: https://doi.org/10.1145/800070.802186, doi:10.1145/800070.802186.
  * [34] Mihalis Yannakakis.  Graph-theoretic methods in database theory.  In Daniel J. Rosenkrantz and Yehoshua Sagiv, editors, Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee, USA, pages 230–242, None, 1990. ACM Press.  URL: https://doi.org/10.1145/298514.298576, doi:10.1145/298514.298576.
  * [35] Ningning Yi, Chunfang Li, Xin Feng, and Minyong Shi.  Design and implementation of movie recommender system based on graph database.  In 14th Web Information Systems and Applications Conference, WISA 2017, Liuzhou, Guangxi Province, China, November 11-12, 2017, pages 132–135, None, 2017. IEEE.  URL: https://doi.org/10.1109/WISA.2017.34, doi:10.1109/WISA.2017.34.
  * [36] Byoung-Ha Yoon, Seon-Kyu Kim, and Seon-Young Kim.  Use of graph database for the integration of heterogeneous biological data.  Genomics & informatics, 15(1):19, 2017.
  * [37] Bruno Yun, Srdjan Vesic, Madalina Croitoru, and Pierre Bisquert.  Inconsistency measures for repair semantics in OBDA.  In IJCAI, pages 1977–1983. ijcai.org, 2018.