# Relaxing Relationship Queries on Graph Data

Shuxin Li<EMAIL_ADDRESS>Gong Cheng<EMAIL_ADDRESS>Chengkai Li
<EMAIL_ADDRESS>National Key Laboratory for Novel Software Technology, Nanjing
University, Nanjing 210023, China  Department of Computer Science and
Engineering, University of Texas at Arlington, Arlington, Texas, United States

###### Abstract

In many domains we have witnessed the need to search a large entity-relation
graph for direct and indirect relationships between a set of entities
specified in a query. A search result, called a semantic association (SA), is
typically a compact (e.g., diameter-constrained) connected subgraph containing
all the query entities. For this problem of SA search, efficient algorithms
exist but will return empty results if some query entities are distant in the
graph. To reduce the occurrence of failing query and provide alternative
results, we study the problem of query relaxation in the context of SA search.
Simply relaxing the compactness constraint will sacrifice the compactness of
an SA, and more importantly, may lead to performance issues and be
impracticable. Instead, we focus on removing the smallest number of entities
from the original failing query, to form a maximum successful sub-query which
minimizes the loss of result quality caused by relaxation. We prove that
verifying the success of a sub-query turns into finding an entity (called a
certificate) that satisfies a distance-based condition about the query
entities. To efficiently find a certificate of the success of a maximum sub-
query, we propose a best-first search algorithm that leverages distance-based
estimation to effectively prune the search space. We further improve its
performance by adding two fine-grained heuristics: one based on degree and the
other based on distance. Extensive experiments over popular RDF datasets
demonstrate the efficiency of our algorithm, which is more scalable than
baselines.

###### keywords:

semantic association search, complex relationship, query relaxation, graph
data

††journal: JoWS

##  1 Introduction

Graph data (e.g., RDF data) representing binary relations between entities is
becoming the back end of increasingly many applications. Graphs are
particularly suitable for answering _relationship queries_. As a simple
example, with the academic graph in Fig. 1, answering a query like _how is Dan
related to ISWC 2019_ could be to conveniently look up arcs that connect two
particular vertices representing the two entities mentioned in the query: Dan
and ISWC2019, which are called _query entities_. In the literature, a
relationship between two or more query entities is commonly referred to as a
_semantic association_ (SA). For two query entities, an SA is usually a path
or a path-like subgraph that connects them [1, 2, 3, 4, 5, 6, 7, 8, 9]. More
generally, for a set of two or more query entities, an SA is a compact
subgraph that connects all the query entities [10, 11, 12, 13, 14, 15]. For
example, the SA shown on the right-hand side of Fig. 2, which is a subgraph of
the academic graph in Fig. 1, is an answer to _how are Alice, Bob, and Dan
connected_. It shows that Alice and Bob have papers accepted at a conference
which Dan is a PC member of.

Figure 1: An example of entity-relation graph, where the five bold arcs induce
a connected subgraph representing a relationship between three entities in a
relationship query: Alice, Bob, and Dan. The subgraph is referred to as an SA
which is a result of that query. Figure 2: An example of query relaxation for
SA search on the entity-relation graph in Fig. 1.

Application of SA Search. Searching a graph for SAs that connect a set of
query entities, called _SA search_ for short, is a well-established research
problem and has found application in many domains. For example, given a graph
about the national security domain including organizations, countries, people,
terrorists, terrorist acts, etc., it is useful to detect notable SAs that
connect a group of suspect airline passengers in a given flight [16]. In a
social network, e.g., a co-authorship network of scientists, SAs can clearly
depict the key relationships between a group of scientists, without the
disturbance of many remote and uncorrelated scientists [15, 10]. SA search is
also helpful in biomedical research [17], and is an underlying technique for
keyword search on graphs [18, 19, 20, 21, 22, 23, 24, 25].

Limitations of Existing Solutions. SA search may _fail and yield empty
results_ , which can disappoint users of an SA search system. It happens when
some query entities are disconnected in the graph and hence there are no
connected subgraphs containing all the query entities. More generally, it also
happens when some query entities are connected but are far away from each
other in the graph, so that existing solutions that aim at structurally
compact SAs may fail to produce any results. Such solutions adopt various
kinds of _compactness constraints_ on allowable SAs, mainly in order to bound
the search space and achieve satisfactory performance. They place an upper
bound on the length of a path-structured SA [2, 4, 8], on the number of
vertices in an SA [10, 7, 13, 15], or on the radius or diameter of an SA [11,
12, 24]. For example, in Fig. 1, if the diameter of an SA is bounded by 4, no
SAs in the graph can connect all of Alice, Bob, Dan, and Gary, because the
distance between Alice and Gary is 5 which exceeds the bound, even though
Alice, Bob, and Dan are sufficiently close to each other.

Bounding is necessary and desired for practical applications where top-ranked
SAs are requested. Computing the top-ranked SA in an unbounded space is
usually formulated as a Steiner tree problem [14], and is NP-hard. The
performance of existing solutions is acceptable only when the search space is
bounded and the bound is set to very small values [26], because the number of
candidate SAs is exponential to the size of an allowable SA. On the other
hand, solutions with compactness constraints are believed cost-effective
because the relationship represented by a large SA, which would be disregarded
by those solutions, is usually not meaningful or interesting to users [24], as
demonstrated by our recent user study [12].

In spite of the necessity and benefits of adopting compactness constraint,
_query failure would occur more often_ , which has not been addressed in
previous research.

Research Goal. Subject to a predetermined compactness constraint which is
practically needed for SA search, our goal in this article is to reduce the
occurrence of failing query and improve the usability of an SA search system,
Consequently, a better trade-off will be established between the performance
of search and the quality of search results. To this end, we will study _query
relaxation_ techniques for SA search that can provide alternative search
results instead of empty results.

Methods and Challenges. One straightforward approach is to _relax the
compactness constraint_ (e.g., lifting the upper bound of diameter to 5 in the
above example), which can produce an SA for the above query. Despite the
sacrifice of compactness, this approach may not fundamentally solve the
problem. Recall that compactness constraint is introduced mainly in order to
bound the search space. It cannot be arbitrarily relaxed as needed but has to
be maintained at a small value in order to achieve acceptable performance of
search. Our experiment results in Section 5.3 will show that: considerably
many queries still fail even though the compactness constraint has been lifted
to the largest value to which existing search algorithms can scale.

Another approach, which we will explore in this article, is to find SAs that
connect not all but part of the query entities, i.e., to _relax the query
entities_. As illustrated in Fig. 2, without lifting the upper bound of
diameter, an SA of diameter 4 that connects Alice, Bob, and Dan (but not Gary)
can be found as a search result and returned to the user. This kind of query
relaxation technique has been familiar to ordinary users. For example, as a
comparable application, Google Search retrieves documents that do not contain
all the query keywords, and it explicitly indicates the missing keywords for
each document in the search results pages. Following this paradigm, research
challenges in the context of SA search include:

  1. 1.

how to optimize the quality of relaxed search results (i.e., SAs) in terms of
result completeness, and

  2. 2.

how to efficiently perform the optimization.

Research Contributions. Relaxation techniques have been considered for
relational queries [27], graph queries [28], XML search [29], and entity
search [30]. However, query relaxation for SA search is a new research
problem. The task here is to remove some entities from a failing relationship
query such that the remaining sub-query could be successful, i.e., an SA
subject to the compactness constraint can be found as a result of the sub-
query. To optimize the quality of relaxed SAs and meet the first challenge, we
aim to minimize the loss of search result completeness by _removing the
smallest number of query entities_ , so that the largest proportion of query
entities can be connected by relaxed SAs. This problem is non-trivial in
consideration of the magnitude of graph data and the allowable response time
of a search system. To develop an efficient solution and meet the second
challenge, our technical contributions are summarized as follows.

  * 1.

We prove that: the success of a relationship query can be indirectly but more
efficiently verified by finding an entity (called a certificate) that
satisfies a distance-based condition about the query entities. Following that,
we devise a polynomial-time algorithm for query relaxation called CertQR,
which is more scalable than an intuitive exponential-time solution adapted
from a state-of-the-art algorithm for SA search [11].

  * 2.

We then devise a best-first search algorithm called CertQR+, which leverages
distance-based estimation to effectively prune the search space of CertQR.
Furthermore, to guide CertQR+ to find an optimum solution earlier, we
introduce two fine-grained heuristics: one based on degree and the other based
on distance. The combination of these techniques achieves considerable
performance improvement.

The remainder of this article is organized as follows. Section 2 formulates
the problem. Section 3 and Section 4 present CertQR and CertQR+, respectively.
Section 5 reports experiments. Section 6 discusses related work. Section 7
concludes the article with future work.

##  2 Problem

###  2.1 Preliminaries

The terminology defined here is compatible with that used in our previous work
[11, 12]. Entities and their binary relations form a graph.

######  Definition 1 (entity-relation graph)

An entity-relation graph is a finite directed labeled graph denoted by
$G=\langle E_{G},A_{G},\mathbb{R},\mathtt{lbl}_{G}\rangle$ where

  * 1.

$E_{G}$ is a finite set of entities as vertices,

  * 2.

$A_{G}$ is a finite set of arcs, each arc $a\in A_{G}$ directed from its tail
vertex $\mathtt{tl}(a)\in E_{G}$ to its head vertex $\mathtt{hd}(a)\in E_{G}$,
and

  * 3.

$\mathtt{lbl}_{G}:A_{G}\mapsto\mathbb{R}$ is a function that labels each arc
$a\in A_{G}$ with a binary relation $\mathtt{lbl}_{G}(a)\in\mathbb{R}$.

Figure 1 shows an entity-relation graph, which will be used as a running
example in this article. RDF graph is a kind of entity-relation graph.
Following [11, 12], we focus on the relations between instance-level entities
and hence we ignore rdf:type and literals.

Although $G$ is directed, it is often treated as an undirected graph in SA
search. For example, when referring to a path in $G$, we do not require its
arcs to all go the same direction. When referring to a tree in $G$, we do not
require its arcs to all go towards or all go away from a particular vertex.

A user may intend to search an entity-relation graph for relationships between
a particular set of entities.

######  Definition 2 (relationship query)

A relationship query, or a query for short, consists of $n$ entities ($n\geq
2$) in $G$ denoted by $Q=\\{qe_{1},\ldots,qe_{n}\\}$, where
$qe_{1},\ldots,qe_{n}\in E_{G}$ are called query entities.

For example, $\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ is a
relationship query submitted to the entity-relation graph in Fig. 1.

An SA as a result of a relationship query is a minimal subgraph connecting all
the query entities. It is actually a Steiner tree that spans all the query
entities. We follow [11, 12] to put an upper bound on the diameter of an
allowable SA as a compactness constraint. Before giving the formal definition
of SA, we review some graph terminology.

######  Definition 3 (graph terminology)

The length of a path is the number of arcs it uses. The distance between two
vertices, denoted by $\mathtt{dist}(\cdot,\cdot)$, is the length of a shortest
path between them, or $+\infty$ if no such path exists. The diameter of a
graph $G=\langle E_{G},A_{G},\mathbb{R},\mathtt{lbl}_{G}\rangle$, denoted by
$\mathtt{diam}(G)$, is the largest distance between pairs of vertices:

$\mathtt{diam}(G)=\max_{e_{i},e_{j}\in E_{G}}{\mathtt{dist}(e_{i},e_{j})}\,.$
(1)

The eccentricity of a vertex is the largest distance between this vertex and
other vertices in the graph. The radius of a graph, denoted by
$\mathtt{rad}(\cdot)$, is the minimum eccentricity in the graph:

$\mathtt{rad}(G)=\min_{e_{i}\in E_{G}}{\max_{e_{j}\in
E_{G}}{\mathtt{dist}(e_{i},e_{j})}}\,.$ (2)

A central vertex is a vertex of minimum eccentricity. The neighbors of a
vertex $e$, denoted by $\mathtt{N}(e)$, are the vertices that are adjacent
from/to it:

$\mathtt{N}(e)=\\{e^{\prime}\in E_{G}:\exists a\in
A_{G},\\{\mathtt{tl}(a),\mathtt{hd}(a)\\}=\\{e,e^{\prime}\\}\\}\,.$ (3)

Now we formally define SA.

######  Definition 4 (semantic association)

A result of a relationship query $Q$ is called a semantic association (SA),
denoted by $x=\langle E_{x},A_{x}\rangle$, which is a subgraph of $G$ with
vertices $E_{x}\subseteq E_{G}$ and arcs $A_{x}\subseteq A_{G}$ satisfying

  * 1.

$x$ contains all the query entities in $Q$, i.e., $Q\subseteq E_{x}$,

  * 2.

$x$ is connected,

  * 3.

$x$ is minimal, i.e., none of its proper subgraphs satisfy the above two
conditions, and

  * 4.

$\mathtt{diam}(x)\leq D$, where $D$ is a diameter constraint.

From the minimality of $x$, we infer that $x$ is a (Steiner) tree where all
the leaf vertices are query entities. For example, given $D=4$, the tree shown
in Fig. 2 is an SA of diameter 4 for the query
$\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$.

###  2.2 Problem Statement

SA search is to search an entity-relation graph for SAs that are results of an
input relationship query. Depending on whether SA search yields empty results,
we classify relationship queries into two types.

######  Definition 5 (successful query and failing query)

A relationship query $Q$ is successful if at least one SA can be found in $G$
under the predefined diameter constraint. Otherwise, $Q$ is called a failing
query.

For example, the relationship query
$\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ submitted to the entity-
relation graph in Fig. 1 is a successful query under $D\geq 4$ because the
subgraph shown in Fig. 2 is an SA of diameter 4 for this query. The query
$\\{\texttt{Alice},\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$ is a failing
query when $D\leq 4$.

######  Definition 6 (sub-query)

For two relationship queries $Q$ and $Q^{\prime}$ satisfying
$Q^{\prime}\subseteq Q$, $Q^{\prime}$ is called a sub-query of $Q$.

Let $\mathtt{subs}(Q)$ be the set of all the sub-queries of $Q$. For example,
the query $\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ has four sub-
queries: $\\{\texttt{Alice},\texttt{Bob}\\}$,
$\\{\texttt{Alice},\texttt{Dan}\\}$, $\\{\texttt{Bob},\texttt{Dan}\\}$, and
itself. Recall that a relationship query contains at least two entities.

In case a relationship query fails, we aim to relax it by finding a sub-query
such that it is successful and it undergoes the smallest change from the
original query. We measure the change by the number of removed query entities.

######  Definition 7 (query relaxation for SA search)

Given a relationship query $Q$ submitted to an entity-relation graph $G$ under
a diameter constraint $D$, the problem of query relaxation is to find a sub-
query of $Q$, denoted by $Q_{max}$, such that $Q_{max}$ is successful and
contains the largest number of query entities in $Q$:

$Q_{max}=\operatorname*{arg\,max}_{Q^{\prime}\in\mathtt{subs}(Q)\text{ and
}Q^{\prime}\text{ is successful}}{|Q^{\prime}|}\,.$

We define $Q_{max}=\emptyset$ if none of the sub-queries of $Q$ are
successful. We will have $Q_{max}=Q$ if $Q$ itself is successful.

For example, under $D\geq 4$ on the entity-relation graph $G$ in Fig. 1, the
relationship query $Q=\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ is
successful, and hence $Q_{max}=Q$. However, the query
$Q=\\{\texttt{Alice},\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$ fails, and we
have $Q_{max}=\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ or
$\\{\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$. Maximum successful sub-
queries may not be unique.

The output of our problem is a relaxed query rather than the results of the
said query. This separation of query relaxation and SA search decouples our
work from downstream tasks, and hence maximizes our research’s applicability
in the real world. For example, some downstream approach searches for all
possible SAs and mines their frequent patterns [11], whereas other approaches
can perform search algorithms that are tailored to directly find top-ranked
SAs according to various ranking criteria [12]. All these downstream solutions
can use our approach to preprocess an input relationship query to avoid query
failure. By contrast, if we focus on directly returning the results of a
relaxed query, we will have to choose a specific downstream task (e.g., a
specific ranking function) and design a hybrid approach that combines query
relaxation and SA search, which may be more efficient than two separate steps.
However, its applicability would be limited. We will explore this direction in
future work.

###  2.3 Discussion on Intuitive Solutions

We are among the first to study query relaxation for SA search. Before
introducing our algorithms, we discuss the shortcomings of two intuitive
solutions. The discussion could help explain the difficulty of the problem.

The first intuitive solution is to exhaustively check all possible sub-queries
in non-increasing order of the number of query entities they contain, and
either return the first sub-query that is successful or return $\emptyset$ if
none of the sub-queries are successful. To check a sub-query, we could perform
an existing algorithm for SA search, e.g., [11]. Immediately when the search
algorithm finds the first result, we know that the sub-query is successful.
Otherwise, if the algorithm ends without outputting any result, the sub-query
fails. One shortcoming of this solution is its _exponential running time_. The
time of performing SA search to check a sub-query is exponential to the
diameter constraint [11], and the number of sub-queries to be checked is
exponential to the number of entities in the original query. We will optimize
this solution and use it as a baseline in our experiments. However, more
scalable solutions are our focus in this article.

The second intuitive solution is to calculate the distance between every pair
of query entities. The idea is: in a successful sub-query, the distance
between every pair of query entities is not larger than the diameter
constraint. However, this is _only necessary but not sufficient_ for the
success of a sub-query. The issue is related to the minimality of an SA which
is required to be a tree, in order to follow common practice in the research
of SA search and be compatible with existing search algorithms and ranking
criteria, e.g., [11, 12, 14]. For a counterexample, consider a small entity-
relation graph that is a triangle, where all the three entities form a
relationship query. Although the distance between every pair of query entities
is 1, the query still fails under $D=1$, because all the spanning trees of the
graph have a diameter of 2, thereby violating the diameter constraint.

##  3 CertQR: Certificate-based Algorithm

We outline our idea as follows. The success of a relationship query can be
indirectly but more efficiently verified by finding an entity (called a
certificate) that satisfies a distance-based condition about the query
entities. A maximum sub-query that a particular entity is a certificate of the
success of can be found in polynomial time. Clearly there are at most linearly
many candidate certificates to consider. Therefore, our proposed algorithm for
query relaxation, called CertQR, runs in polynomial time.

We will introduce the notion of certificate in Section 3.1, and present the
CertQR algorithm in Section 3.2.

###  3.1 Certificate of Successful Sub-query

We will informally illustrate our idea, and then formalize the notion of
certificate. We use $\mathtt{dist}$ to specifically denote the distance
between two entities in $G$.

####  3.1.1 Basic Idea

Under a diameter constraint $D$, a relationship query $Q$ submitted to an
entity-relation graph $G$ is successful _only if_ there is an entity $c\in
E_{G}$ that is at most $\left\lceil{\frac{D}{2}}\right\rceil$ hops away from
every query entity in $Q$. The existence of $c$ is a necessary condition for
the success of $Q$, which we will prove later. For example, under $D=4$, the
query $\\{\texttt{Alice},\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$ submitted
to $G$ in Fig. 1 is not successful, because no such entity $c$ exists. Its
sub-query $\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ is successful, and
we have $c=\texttt{ISWC2019}$ because

$\begin{split}\mathtt{dist}(\texttt{ISWC2019},\texttt{Alice})&=2\leq\left\lceil{\frac{D}{2}}\right\rceil\,,\\\
\mathtt{dist}(\texttt{ISWC2019},\texttt{Bob})&=2\leq\left\lceil{\frac{D}{2}}\right\rceil\,,\\\
\mathtt{dist}(\texttt{ISWC2019},\texttt{Dan})&=1\leq\left\lceil{\frac{D}{2}}\right\rceil\,.\end{split}$
(4)

When $D$ is even, the existence of $c$ is also a sufficient condition for the
success of $Q$, which we will prove later. However, it is not a sufficient
condition when $D$ is odd. For example, when $D=3$, the query
$\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ is not successful even though
the inequalities in Eq. (4) hold. The issue is due to query entities that are
exactly $\left\lceil{\frac{D}{2}}\right\rceil$ hops away from $c$, which are
referred to as _critical query entities_ , e.g., Alice and Bob in the above
example which satisfy

$\begin{split}\mathtt{dist}(\texttt{Alice},\texttt{Bob})&=\mathtt{dist}(\texttt{Alice},\texttt{ISWC2019})\\\
&\quad+\mathtt{dist}(\texttt{ISWC2019},\texttt{Bob})\\\
&=\left\lceil{\frac{D}{2}}\right\rceil+\left\lceil{\frac{D}{2}}\right\rceil>D\,,\\\
\end{split}$ (5)

so the diameter constraint is violated. To establish a sufficient condition
when $D$ is odd, we observe that: if $c$ has a neighbor $c^{\prime}\in E_{G}$
such that it is $(\left\lceil{\frac{D}{2}}\right\rceil-1)$ hops away from
_every_ critical query entity, the distance between every pair of critical
query entities will not be larger than
$2(\left\lceil{\frac{D}{2}}\right\rceil-1)=D-1$, thereby complying with the
diameter constraint. Using the existence of $c^{\prime}$ as an additional
condition, when $D=3$ in the above example, $c=\texttt{ISWC2019}$ will not
mistakenly imply the success of the query
$\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$ because none of the neighbors
of $c$ qualify for $c^{\prime}$. In the meantime, $c=\texttt{ISWC2019}$
correctly implies the success of the query
$\\{\texttt{Dan},\texttt{Erin},\texttt{Frank}\\}$ with
$c^{\prime}=\texttt{Paper02}$. The existence of $\langle c,c^{\prime}\rangle$
is a sufficient and necessary condition for the success of $Q$ when $D$ is
odd, which we will prove later.

To sum up, the existence of such an entity $c$ (when $D$ is even) or a pair of
entities $\langle c,c^{\prime}\rangle$ (when $D$ is odd) is a necessary and
sufficient condition for the success of $Q$. We call $c$ or $\langle
c,c^{\prime}\rangle$ a _certificate_ of the success of $Q$.

####  3.1.2 Formal Definition

Theorem 1 formalizes the above idea. A constructive proof is presented.

######  Theorem 1 (certificate)

A relationship query $Q$ submitted to an entity-relation graph $G$ under a
diameter constraint $D$ is successful if and only if $\exists c\in E_{G}$ such
that

  1. 1.

$\forall qe\in Q$,
$\mathtt{dist}(qe,c)\leq\left\lceil{\frac{D}{2}}\right\rceil$, and

  2. 2.

if $D$ is odd and $\exists qe\in Q$ such that
$\mathtt{dist}(qe,c)=\left\lceil{\frac{D}{2}}\right\rceil$, then $c$ has a
neighbor $c^{\prime}\in\mathtt{N}(c)$ such that $\forall qe\in Q$ that
satisfies $\mathtt{dist}(qe,c)=\left\lceil{\frac{D}{2}}\right\rceil$,
$\mathtt{dist}(qe,c^{\prime})=\left\lceil{\frac{D}{2}}\right\rceil-1$.

Such an entity $c$ (when $D$ is even) or a pair of entities $\langle
c,c^{\prime}\rangle$ (when $D$ is odd) is called a _certificate_ of the
success of $Q$. For convenience, whenever $D$ is even or odd, we consistently
refer to $c$ as a certificate. Given a certificate $c$, $qe\in Q$ that
satisfies $\mathtt{dist}(qe,c)=\left\lceil{\frac{D}{2}}\right\rceil$ is called
a _critical query entity_.

Proof. We present a constructive proof. Recall that the distance between two
entities in $G$ is denoted by $\mathtt{dist}$. We denote their distance in an
SA $x$ by $\mathtt{dist}_{x}$.

Proof of Necessity. Let $c$ be a central vertex of an SA $x=\langle
E_{x},A_{x}\rangle$ that is a result of $Q$. We will show that $c$ satisfies
the two conditions in the theorem.

For the first condition, recall that $x$ is a tree, which satisfies
$\mathtt{rad}(x)=\left\lceil{\frac{\mathtt{diam}(x)}{2}}\right\rceil\leq\left\lceil{\frac{D}{2}}\right\rceil$.
Accordingly, $\forall qe\in Q\subseteq E_{x}$,
$\mathtt{dist}_{x}(qe,c)\leq\left\lceil{\frac{D}{2}}\right\rceil$. Immediately
we have
$\mathtt{dist}(qe,c)\leq\left\lceil{\frac{D}{2}}\right\rceil$ because $x$ is a
subgraph of $G$.

For the second condition, as $x$ is a tree, let $p_{qe}$ be the unique (and
hence shortest) path between $c$ and a critical query entity $qe$ in $x$. The
length of $p_{qe}$ is exactly $\left\lceil{\frac{D}{2}}\right\rceil$; it is
not larger than $\left\lceil{\frac{D}{2}}\right\rceil$ because
$\mathtt{dist}_{x}(qe,c)\leq\left\lceil{\frac{D}{2}}\right\rceil$; it is not
smaller than $\left\lceil{\frac{D}{2}}\right\rceil$ because
$\mathtt{dist}(qe,c)=\left\lceil{\frac{D}{2}}\right\rceil$. Therefore,
$p_{qe}$ is a shortest path in $G$. Let $c^{\prime}$ be $c$’s neighbor in
$p_{qe}$. We will show that $c^{\prime}$ satisfies the second condition. If
$qe$ is the only critical query entity, the second condition will be trivially
satisfied. Otherwise, for any critical query entity $qe^{\prime}$ in $x$ other
than $qe$, the unique and shortest path between $c$ and $qe^{\prime}$ in $x$
(which is also a shortest path in $G$) also passes through $c^{\prime}$
because otherwise, we would have
$\mathtt{dist}_{x}(qe,qe^{\prime})=\left\lceil{\frac{D}{2}}\right\rceil+\left\lceil{\frac{D}{2}}\right\rceil>D$
when $D$ is odd, violating the diameter constraint. Therefore,
$\mathtt{dist}(qe^{\prime},c^{\prime})=\left\lceil{\frac{D}{2}}\right\rceil-1$.

Proof of Sufficiency. When $D$ is even, for each query entity $qe\in Q$, we
choose a shortest path between $qe$ and $c$ in $G$. All of these paths are
merged into a connected subgraph $x$, which clearly satisfies
$\mathtt{diam}(x)\leq D$. In particular, if the shortest paths between two
vertices are not unique, we consistently choose a particular one of them in a
deterministic way to avoid cycles. It can be determined with the help of a
fixed order of the arcs in $A_{G}$, e.g., in alphabetical order of their IDs.
However, the specific order is not important. This ensures that $x$ is a tree
and hence is minimal. Therefore, $x$ is an SA and $Q$ is successful.

When $D$ is odd, we construct a minimal connected subgraph $x$ in a similar
way. In particular, when $qe\in Q$ is a critical query entity, we firstly
choose a shortest path between $qe$ and $c^{\prime}$ in $G$, and then merge
that path with the arc between $c^{\prime}$ and $c$ to form a shortest path
between $qe$ and $c$. This ensures that $\mathtt{diam}(x)\leq D$. Therefore,
$x$ is an SA and $Q$ is successful.

Certificates may not be unique. In Fig. 1, under $D=4$, the relationship query
$\\{\texttt{Alice},\texttt{Dan}\\}$ is successful. Both Paper01 and ISWC2019
are certificates of its success.

0: An entity-relation graph $G$, a diameter constraint $D$, and a relationship
query $Q$.

0: $Q_{max}$ — a maximum successful sub-query of $Q$.

1: $qu\leftarrow$ empty queue

2: $visited\leftarrow\emptyset$

3: for all $qe\in Q$ do

4: $qu$.Enqueue($\langle qe,qe\rangle$)

5: $visited\leftarrow visited\cup\\{qe\\}$

6: end for

7: $Q_{max}\leftarrow\emptyset$

8: while $qu$ is not empty do

9: $\langle e,sqe\rangle\leftarrow qu$.Dequeue()

10: $Q_{e}\leftarrow$ OptWithCert($G$, $D$, $Q$, $e$, $Q_{max}$)

11: if $|Q_{e}|>|Q_{max}|$ then

12: $Q_{max}\leftarrow Q_{e}$

13: end if

14: if $\mathtt{dist}(e,sqe)<\left\lceil{\frac{D}{2}}\right\rceil$ then

15: for all $e^{\prime}\in\mathtt{N}(e)$ do

16: if $e^{\prime}\notin visited$ then

17: $qu$.Enqueue($\langle e^{\prime},sqe\rangle$)

18: $visited\leftarrow visited\cup\\{e^{\prime}\\}$

19: end if

20: end for

21: end if

22: end while

23: return $Q_{max}$

Figure 3: CertQR: a certificate-based algorithm for query relaxation.

###  3.2 Certificate-based Algorithm

Based on the notion of certificate, we propose an algorithm for query
relaxation.

0: An entity-relation graph $G$, a diameter constraint $D$, a relationship
query $Q$, an entity $c\in E_{G}$, and a known successful sub-query
$Q_{known}$ (or $\emptyset$ if not known).

0: $Q_{c}$ — a maximum sub-query of $Q$ that $c$ is a certificate of the
success of. The algorithm outputs $\emptyset$ when: $c$ is not a certificate
of the success of any sub-query, or no such sub-query is larger than
$Q_{known}$.

1: $Q^{1}\leftarrow\\{qe\in
Q:\mathtt{dist}(qe,c)\leq\left\lceil{\frac{D}{2}}\right\rceil\\}$

2: $Q^{2}\leftarrow\\{qe\in
Q:\mathtt{dist}(qe,c)=\left\lceil{\frac{D}{2}}\right\rceil\\}$

3: if $|Q^{1}|>|Q_{known}|$ then

4: if $D$ is even or $|Q^{2}|\leq 1$ then

5: $Q_{c}\leftarrow Q^{1}$

6: else

7: for all $c^{\prime}\in\mathtt{N}(c)$ do

8: $R_{c^{\prime}}\leftarrow\\{qe\in
Q^{2}:\mathtt{dist}(qe,c^{\prime})=\left\lceil{\frac{D}{2}}\right\rceil-1\\}$

9: end for

10:
$Q_{c}\leftarrow(\operatorname*{arg\,max}_{R_{c^{\prime}}}{|R_{c^{\prime}}|})\cup(Q^{1}\setminus
Q^{2})$

11: end if

12: if $|Q_{c}|>1$ then

13: return $Q_{c}$

14: else

15: return $\emptyset$

16: end if

17: else

18: return $\emptyset$

19: end if

Figure 4: The OptWithCert algorithm.

####  3.2.1 Algorithm Design

The problem of query relaxation formulated in Definition 7 is to find a
maximum successful sub-query of $Q$, denoted by $Q_{max}$. Following Theorem
1, it turns into finding a maximum sub-query whose success has a certificate.
Such a certificate, if it exists, is at most
$\left\lceil{\frac{D}{2}}\right\rceil$ hops away from every query entity in
$Q_{max}$. Therefore, we can exhaustively search all the entities that are at
most $\left\lceil{\frac{D}{2}}\right\rceil$ hops away from each query entity
in $Q$. Each of these entities may be a certificate of the success of one or
more sub-queries of $Q$. A maximum one of these sub-queries will be $Q_{max}$.

The algorithm, called CertQR, is presented in Fig. 3. Breadth-first search
simultaneously starts from each query entity $qe\in Q$ (lines 3–6). The
frontier is stored in a queue denoted by $qu$, where each element is an
ordered pair of entities $\langle e,sqe\rangle$, consisting of an entity $e\in
E_{G}$ to process, and a query entity $sqe\in Q$ starting from which $e$ is
visited for the first time (i.e., $sqe$ is the closest query entity to $e$).
Visited entities are stored in a set denoted by $visited$. Iteratively, for
each entity $e$ to process (line 9), the OptWithCert algorithm in Fig. 4 finds
$Q_{e}$, which is a maximum sub-query that $e$ is a certificate of the success
of (line 10). If $Q_{e}$ is larger than the current $Q_{max}$, a substitution
will be made to update $Q_{max}$ (lines 11–13). If $e$ is less than
$\left\lceil{\frac{D}{2}}\right\rceil$ hops away from $sqe$, search will
continue and expand the neighbors of $e$, i.e., $\mathtt{N}(e)$ (lines 14–21).
Finally, $Q_{max}$ is returned, which is either a maximum successful sub-query
of $Q$ if it exists, or $\emptyset$ (line 23).

OptWithCert in Fig. 4 finds $Q_{c}$ — a maximum sub-query that a particular
entity $c$ is a certificate of the success of. It returns $\emptyset$ if $c$
is not a certificate of the success of any sub-query. Let $Q^{1}$ and $Q^{2}$
be the sets of query entities that are at most and are exactly
$\left\lceil{\frac{D}{2}}\right\rceil$ hops away from $c$, respectively (lines
1–2). According to Theorem 1, $Q^{1}$ is exactly $Q_{c}$ when $D$ is even
(lines 4–5). When $D$ is odd, we need to consider critical query entities,
i.e., $Q^{2}$ (lines 6–11). Specifically, for each neighbor of $c$ denoted by
$c^{\prime}\in\mathtt{N}(c)$, let $R_{c^{\prime}}$ be the subset of critical
query entities that are $(\left\lceil{\frac{D}{2}}\right\rceil-1)$ hops away
from $c^{\prime}$ (lines 7–9). These critical query entities (i.e.,
$R_{c^{\prime}}$) and all the non-critical query entities (i.e.,
$Q^{1}\setminus Q^{2}$) together form a maximum sub-query that $\langle
c,c^{\prime}\rangle$ is a certificate of the success of. $Q_{c}$ is a maximum
one of these sub-queries over all $c^{\prime}\in\mathtt{N}(c)$ (line 10).

Two additional improvements are made in OptWithCert. First, even if $D$ is
odd, it will be unnecessary to look for $c^{\prime}$ and we will have
$Q_{c}=Q^{1}$ if $|Q^{2}|\leq 1$ (lines 4–5), because either there is no
critical query entity (i.e., $|Q^{2}|=0$) or there is only one critical query
entity (i.e., $|Q^{2}|=1$) so that there certainly exists
$c^{\prime}\in\mathtt{N}(c)$ that satisfies $R_{c^{\prime}}=Q^{2}$. Second,
because a maximum successful sub-query found by the algorithm is bounded by
$Q^{1}$, the algorithm will be terminated early if $Q^{1}$ is not larger than
$Q_{known}$, which is a known successful sub-query (line 3). In the CertQR
algorithm (line 10), the current maximum successful sub-query is assigned to
$Q_{known}$ when invoking OptWithCert.

####  3.2.2 Algorithm Analysis

The correctness of the CertQR algorithm is straightforward following Theorem
1.

The running time of CertQR mainly consists of:

  * 1.

$O(|E_{G}|+|A_{G}|)$ for breadth-first search, and

  * 2.

the time for $O(|E_{G}|)$ times of invoking OptWithCert.

The running time of OptWithCert is dominated by distance calculation
($\mathtt{dist}$). Let $d$ be the running time for one $\mathtt{dist}$ call.
Altogether, the $O(|E_{G}|)$ times of invoking OptWithCert use
$O(|E_{G}|\cdot|Q|d)$ time when $D$ is even (lines 1–2), and need additional
$O(|A_{G}|\cdot|Q|d)$ time when $D$ is odd (lines 7–10).

Overall, the running time of CertQR is bounded by
$O((|E_{G}|+|A_{G}|)\cdot|Q|d)$, which is polynomial. It is more scalable than
the intuitive exponential-time solution discussed in Section 2.3.

Calculation of Distance. The running time of CertQR is proportional to $d$.
When $G$ is large, online calculating $\mathtt{dist}$ is time-consuming
(though still in polynomial time), and materializing offline calculated
distances between all pairs of entities is space-consuming. To achieve a
trade-off between time and space, we implement an off-the-shelf _distance
oracle_ [31]. This data structure, based on certain precomputed and
materialized information, allows reasonably fast distance calculation, though
not as fast as directly looking up materialized distances. Therefore, $d$ can
be practically regarded as a constant. The size of a distance oracle is
considerably smaller than the size of materializing distances between all
pairs of entities. The reader is referred to [31] for a detailed
implementation, and to [32] for a survey of related techniques.

For the completeness of this article, we briefly describe our implementation
of distance oracle according to [31]. For each vertex, its distances to a
small set of landmark vertices are precomputed and materialized. For any two
vertices, they have at least one common landmark vertex that is on a shortest
path between them. Therefore, the distance between two vertices can be quickly
calculated based on their materialized distances to their common landmark
vertices. Minimizing the number of landmark vertices and materialized
distances is the focus of [31], which we will not detail here.

####  3.2.3 Running Example

Under $D=4$, for the relationship query $\\{\texttt{Alice},\texttt{Bob},\\\
\texttt{Dan},\texttt{Gary}\\}$ submitted to $G$ in Fig. 1, every entity in the
graph is at most 2 hops away from some query entity. So all the 11 entities
are visited in search and processed by OptWithCert. As a result, ISWC2019 is a
certificate of the success of
$\\{\texttt{Alice},\texttt{Bob},\texttt{Dan}\\}$, and Paper02 is a certificate
of the success of $\\{\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$. The two
sub-queries are equally large. Either of them will be returned as $Q_{max}$.

##  4 CertQR+: Improved Algorithm

CertQR exhaustively considers all the entities that are at most
$\left\lceil{\frac{D}{2}}\right\rceil$ hops away from each query entity as
candidate certificates. To improve the performance, we propose to consider
fewer entities but ensure that unvisited entities cannot be a certificate of
the success of a sub-query that is larger than the one to return. To achieve
it, we devise a _best-first search_ algorithm called CertQR+.

We will present the CertQR+ algorithm in Section 4.1, and introduce two fine-
grained heuristics to further improve the performance in Section 4.2.

0: An entity-relation graph $G$, a diameter constraint $D$, and a relationship
query $Q$.

0: $Q_{max}$ — a maximum successful sub-query of $Q$.

1: $pq\leftarrow$ empty priority queue

2: for all $qe\in Q$ do

3: $pr\leftarrow\mathtt{priority}(qe|qe)$

4: $pq$.InsertWithPriority($\langle qe,qe,pr\rangle$)

5: $visited_{qe}\leftarrow\\{qe\\}$

6: end for

7: $Q_{max}\leftarrow\emptyset$

8: $checked\leftarrow\emptyset$

9: while $pq$ is not empty do

10: $\langle e,sqe,pr\rangle\leftarrow pq$.PullHighestPriorityElement()

11: if $\left\lfloor{pr}\right\rfloor\leq|Q_{max}|$ or
$\left\lfloor{pr}\right\rfloor\leq 1$ then

12: break the while loop

13: else

14: if $e\notin checked$ then

15: $Q_{e}\leftarrow$ OptWithCert($G$, $D$, $Q$, $e$, $Q_{max}$)

16: $checked\leftarrow checked\cup\\{e\\}$

17: if $|Q_{e}|>|Q_{max}|$ then

18: $Q_{max}\leftarrow Q_{e}$

19: end if

20: end if

21: if $\mathtt{dist}(e,sqe)<\left\lceil{\frac{D}{2}}\right\rceil$ and
$\left\lfloor{pr}\right\rfloor>|Q_{max}|$ then

22: for all $e^{\prime}\in\mathtt{N}(e)$ do

23: if $e^{\prime}\notin visited_{sqe}$ and
$\mathtt{dist}(e^{\prime},sqe)=\mathtt{dist}(e,sqe)+1$ then

24: $pr^{\prime}\leftarrow\mathtt{priority}(e^{\prime}|sqe)$

25: $pq$.InsertWithPriority($\langle e^{\prime},sqe,pr^{\prime}\rangle$)

26: $visited_{sqe}\leftarrow visited_{sqe}\cup\\{e^{\prime}\\}$

27: end if

28: end for

29: end if

30: end if

31: end while

32: return $Q_{max}$

Figure 5: CertQR+: an improved version of CertQR.

###  4.1 Improved Algorithm

Our improved algorithm performs best-first search.

####  4.1.1 Algorithm Design

The new algorithm, called CertQR+, is presented in Fig. 5. Similar to CertQR,
search simultaneously starts from each query entity. However, different from
CertQR which visits each entity in $G$ at most once, CertQR+ runs $|Q|$
_independent searches_. Each search is only focused on sub-queries that
contain the start query entity of that search. An entity in the graph may be
visited up to $|Q|$ times in $|Q|$ searches. This seems slower than CertQR,
but we will show that these independent searches can be terminated early.

Specifically, each search starts from a distinct query entity $qe\in Q$ (lines
2–6). The frontier, which is shared by all the $|Q|$ searches, is stored in a
priority queue denoted by $pq$, where each element is an ordered entity-
entity-priority triple $\langle e,sqe,pr\rangle$, consisting of an entity
$e\in E_{G}$ to process, a query entity $sqe\in Q$ starting from which $e$ is
visited (i.e., $sqe$ identifies a search), and a priority for $e$ denoted by
$pr$. Entities visited in a search starting from $qe$ are stored in a set
denoted by $visited_{qe}$.

Different from CertQR which uses a first-in-first-out queue and performs
breadth-first search, CertQR+ uses a priority queue $pq$ and performs best-
first search. In each iteration, it pulls out a triple $\langle
e,sqe,pr\rangle$ that has the highest priority $pr$ (line 10). We define $pr$
to be: an _estimate_ of the number of query entities in a maximum possible
sub-query which _$e$ or its descendant in the search starting from $sqe$_ can
be a certificate of the success of. If the highest priority in $pq$ is not
larger than $|Q_{max}|$ or 1 where $Q_{max}$ denotes the current maximum
successful sub-query, the algorithm can be terminated and $Q_{max}$ will be
returned (lines 11-12). We will later elaborate the computation of priority.

Although $e$ may be visited in different independent searches, it will be
processed by OptWithCert at most once (lines 14–16). Entities that have been
processed by OptWithCert are stored in a set denoted by $checked$, which is
shared by all the $|Q|$ searches. If OptWithCert finds a larger successful
sub-query, $Q_{max}$ will be updated (lines 17–19).

The search starting from $sqe$ will expand the neighbors of $e$ if: $e$ is
less than $\left\lceil{\frac{D}{2}}\right\rceil$ hops away from $sqe$, and
$pr$ is larger than $Q_{max}$ (lines 21–29). A neighbor
$e^{\prime}\in\mathtt{N}(e)$ will be expanded only if
$\mathtt{dist}(e^{\prime},sqe)=\mathtt{dist}(e,sqe)+1$ (line 23), i.e.,
$e^{\prime}$ is reached via a shortest path from $sqe$. This additional
requirement is not necessary but may reduce the search space, which we will
discuss later.

Finally, $Q_{max}$ is returned, which is either a maximum successful sub-query
of $Q$ if it exists, or $\emptyset$ (line 32).

Computation of Priority. The priority for an entity $e$, i.e., $pr$, is
computed by a function $\mathtt{priority}(e|sqe)$ which depends on $sqe$:

$\mathtt{priority}(e|sqe)=|\mathtt{est}(e|sqe)|\,,$ (6)

where $\mathtt{est}(e|sqe)$ is an estimated set of query entities in a maximum
possible sub-query which $e$ or its descendant in the search starting from
$sqe$ can be a certificate of the success of. Our estimation uses distances
between entities:

$\begin{split}\mathtt{est}(e|sqe)=\\{sqe\\}\cup\\{&qe\in(Q\setminus\\{sqe\\}):\\\
&\mathtt{dist}(e,sqe)+\mathtt{dist}(e,qe)\leq D\\}\,.\end{split}$ (7)

We will prove that it guarantees the optimality of $Q_{max}$ when the
algorithm is terminated.

In Section 4.2, we will consider more effective implementation of
$\mathtt{priority}(e|sqe)$ based on fine-grained heuristics.

####  4.1.2 Algorithm Analysis

Theorem 2 proves the correctness of CertQR+.

###### Theorem 2

CertQR+ returns a maximum successful sub-query if it exists.

The key idea of our proof is to show the existence of a path between some
query entity in an optimum solution and a certificate of its success such
that: for every entity in the path, its priority is not smaller than the
number of query entities in that optimum solution. Consequently, as search
starts from each query entity, it is impossible that the algorithm produces a
sub-optimum solution without visiting that certificate via the path.

Proof. We prove by contradiction.

Assume CertQR+ returns a sub-optimum solution $Q_{max}$ which is smaller than
an optimum solution denoted by $Q_{opt}$. Let $c\in E_{G}$ be a certificate of
the success of $Q_{opt}$. Before CertQR+ is terminated, $c$ has never been
processed by OptWithCert because otherwise, $Q_{opt}$ instead of $Q_{max}$
would be returned. However, we can prove the existence of a particular path
between $c$ and some query entity $sqe\in Q_{opt}$, called a _key path_ , such
that: for every entity $e$ in this path,
$\mathtt{priority}(e|sqe)\geq|Q_{opt}|>|Q_{max}|$ holds. With this key path,
the algorithm is impossible to return $Q_{max}$ without visiting $c$ via this
path and finding $Q_{opt}$ by OptWithCert, leading to a contradiction.

To show the existence of such a key path, consider an SA $x$ constructed
according to the proof of sufficiency of Theorem 1, which consists of shortest
paths between $c$ and each query entity in $Q_{opt}$. Now we prove that: (i)
at least one of these shortest paths is not longer than
$\left\lfloor{\frac{D}{2}}\right\rfloor$, and (ii) this shortest path is a key
path.

(i) When $D$ is even, all of those shortest paths are not longer than
$\left\lceil{\frac{D}{2}}\right\rceil=\left\lfloor{\frac{D}{2}}\right\rfloor$.
When $D$ is odd, assume on the contrary that all of them are longer than
$\left\lfloor{\frac{D}{2}}\right\rfloor$. According to Theorem 1, all the
query entities are critical query entities, and hence all of those shortest
paths pass through $c^{\prime}$ which is a neighbor of $c$. That contradicts
the minimality of $x$ in Definition 4 because the vertex $c$ and the arc
between $c$ and $c^{\prime}$ can be removed from $x$ to obtain a proper
subgraph of $x$ that is a well-defined SA.

(ii) Let $p$ be a path not longer than
$\left\lfloor{\frac{D}{2}}\right\rfloor$ proved in (i), which connects $sqe\in
Q_{opt}$ and $c$. For every entity $e$ in $p$ and every query entity
$sqe^{\prime}\in(Q_{opt}\setminus\\{sqe\\})$,
$\mathtt{dist}(e,sqe)+\mathtt{dist}(e,sqe^{\prime})$ is not larger than the
sum of the length of $p$ and the length of a shortest path between $c$ and
$sqe^{\prime}$, which in turn is not larger than
$\left\lfloor{\frac{D}{2}}\right\rfloor+\left\lceil{\frac{D}{2}}\right\rceil=D$.
Therefore, $sqe^{\prime}\in\mathtt{est}(e|sqe)$ and we have
$\mathtt{priority}(e|sqe)=|\mathtt{est}(e|sqe)|\geq|Q_{opt}|$, so $p$ is a key
path.

In order to find an optimum solution, it would be sufficient to visit a key
path which is a shortest path. It explains why CertQR+ only searches along
shortest paths (line 23).

The running time of CertQR+ mainly consists of:

  * 1.

$O(|Q|\cdot(|E_{G}|+|A_{G}|))$ for $|Q|$ searches,

  * 2.

$O((|E_{G}|+|A_{G}|)\cdot|Q|d)$ for $O(|E_{G}|)$ times of invoking
OptWithCert, being the same as that in CertQR,

  * 3.

$O(|Q|^{2}d\cdot|E_{G}|)$ for $O(|Q|\cdot|E_{G}|)$ times of priority
computation, and

  * 4.

$O(|Q|\cdot|E_{G}|\log(|Q|\cdot|E_{G}|))$ for $O(|Q|\cdot|E_{G}|)$ pairs of
insert-pull operations using a Fibonacci heap for priority queue.

The overall worst-case running time of CertQR+ can be longer than that of
CertQR. However, CertQR+ could be faster in practice mainly because searches
in CertQR+ can be terminated early.

####  4.1.3 Running Example

Under $D=4$, for the relationship query $Q=\\{\texttt{Alice},\\\
\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$ submitted to $G$ in Fig. 1,
CertQR+ initially inserts four triples into $pq$:

$\begin{split}t_{1}&=\langle\texttt{Alice},\texttt{Alice},3\rangle\,,\\\
t_{2}&=\langle\texttt{Bob},\texttt{Bob},4\rangle\,,\\\
t_{3}&=\langle\texttt{Dan},\texttt{Dan},4\rangle\,,\\\
t_{4}&=\langle\texttt{Gary},\texttt{Gary},3\rangle\,.\end{split}$

In $pq$, $t_{2}$ (or $t_{3}$) has the highest priority and is pulled out
first. However, OptWithCert finds that Bob is not a certificate of the success
of any sub-query. Bob’s neighbors are expanded, and a new triple is inserted
into $pq$:

$t_{5}=\langle\texttt{Paper02},\texttt{Bob},4\rangle\,.$

$t_{5}$ (or $t_{3}$) is pulled out of $pq$. OptWithCert finds that Paper02 is
a certificate of the success of
$\\{\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$, which is assigned to
$Q_{max}$. Paper02’s neighbors are then expanded, and three new triples are
inserted into $pq$:

$\begin{split}t_{6}&=\langle\texttt{ISWC2019},\texttt{Bob},3\rangle\,,\\\
t_{7}&=\langle\texttt{Erin},\texttt{Bob},1\rangle\,,\\\
t_{8}&=\langle\texttt{Frank},\texttt{Bob},2\rangle\,.\end{split}$

$t_{3}$ is pulled out of $pq$. OptWithCert finds that Dan is not a certificate
of the success of any sub-query. Dan’s neighbors are expanded, and a new
triple is inserted into $pq$:

$t_{9}=\langle\texttt{ISWC2019},\texttt{Dan},4\rangle\,.\\\ $

Note that ISWC2019 has been visited twice in two different searches: one
starting from Bob (i.e. $t_{6}$) and the other from Dan (i.e., $t_{9}$).

$t_{9}$ is pulled out of $pq$. OptWithCert finds that ISWC2019 is not a
certificate of the success of any sub-query that is larger than the current
$Q_{max}=\\{\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$. ISWC2019’s neighbors
are expanded, and three new triples are inserted into $pq$:

$\begin{split}t_{10}&=\langle\texttt{Paper01},\texttt{Dan},2\rangle\,,\\\
t_{11}&=\langle\texttt{Paper02},\texttt{Dan},3\rangle\,,\\\
t_{12}&=\langle\texttt{Paper03},\texttt{Dan},1\rangle\,.\end{split}$

Now the highest priority in $pq$ is 3, which is not larger than $|Q_{max}|=3$.
The algorithm is terminated and returns
$Q_{max}=\\{\texttt{Bob},\texttt{Dan},\texttt{Gary}\\}$.

For this example, CertQR+ is faster than CertQR. First, in CertQR, 11 entities
are processed by OptWithCert, whereas only 4 entities are processed by
OptWithCert in CertQR+. Second, Carol is visited in CertQR but not in CertQR+.
CertQR+ effectively prunes the search space of CertQR.

###  4.2 Fine-Grained Heuristics

We introduce two fine-grained heuristics that may guide CertQR+ to find an
optimum solution earlier. In Eq. (6), $\mathtt{priority}(e|sqe)$ is an
integer. We will heuristically define its fractional part. That will not
affect the correctness of CertQR+, which only relies on the integer part of
priority (lines 11 and 21). On the other hand, ties in the priority queue
(according to the integer part) will be broken not arbitrarily but
heuristically (according to the fractional part). This fine-grained ordering
may allow CertQR+ to be terminated earlier.

####  4.2.1 Degree-enhanced Priority

This heuristic considers the _degree_ of $e$, namely the number of arcs in $G$
that are incident from/to $e$, denoted by $\mathtt{deg}(e)$:

$\mathtt{deg}(e)=|\\{a\in A_{G}:\mathtt{tl}(a)=e\text{ or
}\mathtt{hd}(a)=e\\}|\,.$ (8)

The idea is: when multiple entities have the same value of $|\mathtt{est}|$,
we will give priority to the one having the smallest degree, because expanding
the neighbors of an entity having a large degree and computing their
priorities is time-consuming (lines 22–28). Therefore, we define a variant of
$\mathtt{priority}$ as follows:

$\mathtt{priority}_{\text{dg}}(e|sqe)=|\mathtt{est}(e|sqe)|+\frac{1}{2+\mathtt{deg}(e)}\,,$
(9)

where the fractional part depends on $\mathtt{deg}$.

####  4.2.2 Distance-enhanced Priority

This heuristic considers the distance between $e$ and possible certificates of
the success of $\mathtt{est}(e|sqe)$. According to Theorem 1, the distance
between such a certificate (if it exists) and each query entity
$qe\in\mathtt{est}(e|sqe)$ is not longer than
$\left\lceil{\frac{D}{2}}\right\rceil$. Therefore, the number of hops from $e$
to a possible certificate is bounded below by:

$\mathtt{hp}(e|sqe)=\max_{qe\in\mathtt{est}(e|sqe)}{\max{\\{0,\mathtt{dist}(e,qe)-\left\lceil{\frac{D}{2}}\right\rceil\\}}}\,.$
(10)

The idea is: when multiple entities have the same value of $|\mathtt{est}|$,
we will give priority to the closest one to a possible certificate, which may
lead to a better solution earlier. Therefore, we define a variant of
$\mathtt{priority}$ as follows:

$\mathtt{priority}_{\text{ds}}(e|sqe)=|\mathtt{est}(e|sqe)|+\frac{1}{2^{1+\mathtt{hp}(e|sqe)}}\,,$
(11)

where the fractional part depends on $\mathtt{hp}$.

####  4.2.3 Combined Priority

The above two heuristics can be combined as follows:

$\mathtt{priority}_{\text{dgs}}(e|sqe)=|\mathtt{est}(e|sqe)|+\frac{1}{(2+\mathtt{deg}(e))^{1+\mathtt{hp}(e|sqe)}}\,.$
(12)

##  5 Experiments

Our code and resources for experiments are available111https://github.com/nju-
websoft/CertQR.

At the beginning of the article, we mentioned two methods for query
relaxation: relaxing the compactness constraint and relaxing the query
entities. In the first experiment, we compared the quality of their output, to
show the better practicability of the latter method. In the second experiment,
we tested the running time of our proposed algorithms compared with baselines,
to demonstrate their efficiency. All the experiments were performed on an
Intel Xeon E7-4820 (2.00 GHz) with 128GB memory for Java.

###  5.1 Datasets

Three popular RDF datasets were used in our experiments: DBpedia, LinkedMDB,
and Mondial. They covered the datasets used in previous efforts to evaluate SA
search [12] as well as keyword search on graphs [26].

DBpedia is a large encyclopedic RDF dataset derived from Wikipedia, describing
people, places, creative works, organizations, species, etc. Using its 2015-10
version222https://wiki.dbpedia.org/Downloads2015-10, we obtained an entity-
relation graph by importing relations between entities from two dump files:
_Mappingbased Objects_ and _Person data_.

LinkedMDB is a large RDF dataset describing movies and related concepts, e.g.,
actors, directors. We obtained an entity-relation graph by importing relations
between entities from its latest dump
file333http://www.cs.toronto.edu/~oktie/linkedmdb/linkedmdb-latest-dump.zip.

Mondial is a small geographical database. We obtained an entity-relation graph
by importing relations between entities from its RDF graph
version444http://www.dbis.informatik.uni-goettingen.de/Mondial/Mondial-
RDF/mondial.rdf.

Table 1: Size of Entity-Relation Graphs Dataset | Number of vertices | Number of arcs
---|---|---
DBpedia | 5,356,286 | 17,494,749
LinkedMDB | 1,326,784 | 2,132,796
Mondial | 8,478 | 34,868

Note that rdf:type and literals were not included in the entity-relation
graphs because our focus was on the relations between instance-level entities.
Table 1 presents the size of each graph.

###  5.2 Queries

For each entity-relation graph, we constructed two types of queries having
complementary characteristics.

A simulated query consisted of related entities, which were likely to be
pairwise close in a graph. We adopted the process described in [12] to
construct such queries that well simulated real users’ information needs.

(a) DBpedia (simulated queries)

(b) LinkedMDB (simulated queries)

(c) Mondial (simulated queries)

Figure 6: Distribution of result quality after query relaxation. The area of a
bubble represents the number of queries having a particular value of $\langle
D_{min},N_{min}\rangle$ represented by the center of the bubble.

Specifically, for DBpedia, we identified 250 entities that were mentioned in
the training set of the QALD-5 evaluation
campaign555https://qald.sebastianwalter.org/index.php?q=5, called _seed
entities_. For each seed entity (e.g., Michael Jordan), we submitted its name
as a keyword query to the Google search engine, which might trigger Google’s
Knowledge Graph to return a set of entities that “people also search for”
(e.g., Kobe Bryant). We identified their corresponding entities in DBpedia, if
they existed, called _related entities_. For 92 seed entities, at least five
related entities could be found. For each of those seed entities and each
number of query entities $n$ in the range of 2–6, we generated a simulated
query consisting of the seed entity and $n-1$ entities randomly selected from
its related entities.

For LinkedMDB and Mondial, the processes were similar. For LinkedMDB, seed
entities were 39 top rated movies in IMDb. Related entities were movies that
“people who liked (a seed entity) also liked” recommended by IMDb. For
Mondial, seed entities were 57 entities mentioned in the keyword queries used
in a previous evaluation effort666https://doi.org/10.18130/V3/KEVCF8. Related
entities were obtained in the same way we did for DBpedia.

There were $(92+39+57)\cdot 5=940$ simulated queries.

A random query consisted of random entities, which were not likely to be
pairwise close in a graph. Complementary to simulated queries, random queries
were more likely to fail and need to be relaxed. For each entity-relation
graph and each number of query entities $n$ in the range of 2–6, we
constructed 100 random queries, each consisting of $n$ randomly selected
entities. There were $100\cdot 5\cdot 3=1500$ random queries.

###  5.3 Experiment on Quality

In Section 1, we mentioned two methods for query relaxation. One
straightforward approach was to relax the compactness constraint. The other,
as the focus of this article, was to relax the query entities. In this
experiment, we compared the quality of their output to analyze their
practicability. Therefore, we only used simulated queries for this experiment.

####  5.3.1 Experiment Design

We measured quality from two perspectives: compactness and completeness.

Compactness. For each query, we found the minimum diameter constraint under
which the query was successful, denoted by $D_{min}$. It characterized the
_compactness of search results after relaxing the diameter constraint_. It
also indicated the practicability of this approach, which would be
impracticable if $D_{min}$ were large so that existing algorithms for SA
search could not scale well.

Completeness. On the other hand, for each query under $D=4$ which was a
typical setting used in the literature [11, 12], we computed the smallest
number of query entities to remove in order to obtain a successful sub-query
if it existed, denoted by $N_{min}$; otherwise, we defined $N_{min}=\infty$.
It characterized the _completeness of search results after relaxing the query
entities_ , in terms of the number of missing query entities.

####  5.3.2 Experiment Results and Analysis

Figure 6 presents the distribution of $D_{min}$ and $N_{min}$. The area of a
bubble represents the number of queries having a particular value of $\langle
D_{min},N_{min}\rangle$ represented by the center of the bubble.

Among all the simulated queries, 87% on DBpedia (Fig. 6a), 89% on LinkedMDB
(Fig. 6b), and 99% on Mondial (Fig. 6c) were successful under $D=4$. Query
relaxation was needed not for them but for the rest of queries that failed,
whose proportions were still considerable on large entity-relation graphs like
DBpedia and LinkedMDB.

For 82% of the failing queries on DBpedia and 100% of the failing queries on
LinkedMDB and Mondial, removing only one query entity by our approach could
result in a successful sub-query ($N_{min}=1$). The loss of result
completeness, i.e., the number of missing query entities, was managed at the
lowest level.

By contrast, if we chose the alternative approach of relaxing the compactness
constraint, by lifting the diameter constraint (i.e., $D$) from 4 to 5, only
55% of the failing queries on DBpedia, 23% on LinkedMDB, and 100% on Mondial
could turn into successful queries. In fact, even $D_{min}\geq 10$ was
frequently observed when some queries entities were distantly connected or
even disconnected in an entity-relation graph. Therefore, the downside of this
alternative approach included: (a) the loss of result compactness, (b) the
incapability to handle disconnected query entities, and more importantly, (c)
the performance issue considering that existing techniques for SA search could
not scale to large graphs unless $D$ was very small [11, 26]. For example, the
search algorithm in [11] could only scale up to $D=4$ on DBpedia.

To conclude, _relaxing the compactness constraint could not fundamentally
solve the problem of query failure. Relaxing the query entities was a more
practicable approach, which preserved result compactness and minimized result
incompleteness._

Figure 7: A snippet of DBpedia. Under $D=4$, the query $\\{\texttt{Vitruvian Man},~{}\texttt{Mona Lisa},~{}\texttt{Venus de Milo},~{}\texttt{The Scream}\\}$ is relaxed to $\\{\texttt{Vitruvian Man},~{}\texttt{Mona Lisa},~{}\texttt{Venus de Milo}\\}$, which yields an SA comprising the four bold arcs. Table 2: Proportion of Timeout Runs on BSL Dataset | Query | $n=2$ | $n=3$ | $n=4$ | $n=5$ | $n=6$
---|---|---|---|---|---|---
DBpedia | Simulated | 2.17% | 3.80% | 4.89% | 10.87% | 19.29%
| Random | 0 | 0 | 2.50% | 12.50% | 12.00%
LinkedMDB | Simulated | 0 | 0 | 0.64% | 3.85% | 10.90%
| Random | 0 | 0 | 0 | 0 | 0
Mondial | Simulated | 0 | 6.14% | 13.60% | 36.84% | 40.79%
| Random | 0 | 0 | 2.50% | 14.75% | 20.50%
Table 3: Proportion of Timeout Runs on BSL+ Dataset | Query | $n=2$ | $n=3$ | $n=4$ | $n=5$ | $n=6$
---|---|---|---|---|---|---
DBpedia | Simulated | 0.54% | 0.54% | 3.80% | 9.78% | 16.30%
| Random | 0 | 0 | 2.25% | 7.25% | 12.00%
LinkedMDB | Simulated | 0 | 0 | 7.69% | 12.18% | 15.38%
| Random | 0 | 0 | 0 | 0 | 0
Mondial | Simulated | 0 | 5.26% | 9.65% | 28.51% | 32.02%
| Random | 0 | 0 | 1.25% | 13.50% | 10.50%

Case Study. One simulated query for DBpedia in our experiments was about four
artworks: Vitruvian Man, Mona Lisa, Venus de Milo, and The Scream. As
illustrated in Fig. 7, the query failed under $D=4$ because The Scream was far
away from the other three query entities in the graph. Its maximum successful
sub-query was obtained by removing The Scream, resulting in the following SA:
Leonardo da Vinci is the author of both Vitruvian Man and Mona Lisa; the
latter is located in the Louvre which also hosts Venus de Milo. Alternatively,
the original query would be successful when $D$ was increased to 6, to which
the algorithm for SA search in [11] could not scale. Besides, a resulting
large-sized SA would be diffuse, containing almost all the entities and
relations in Fig. 7.

###  5.4 Experiment on Efficiency

We tested the running time of our proposed algorithms. Both simulated and
random queries were used for this experiment.

####  5.4.1 Participating Algorithms

We compared 7 algorithms. We did not find any methods in the literature that
could be directly used to solve our problem, so we adapted and improved a
state-of-the-art algorithm for SA search as a baseline.

BSL was a baseline approach that checked all possible sub-queries in non-
increasing order of the number of query entities they contained, and returned
the first successful one. To check a sub-query, BSL performed a state-of-the-
art path-merging and path-pruning based algorithm for SA search [11], which
would be terminated early after finding the first SA (thereby indicating
success). It was the first intuitive solution discussed in Section 2.3.

BSL+ was a variant of BSL we developed in order to improve the performance.
Considering that BSL repeatedly ran the search algorithm [11] on the same set
of query entities, we disabled path pruning but cached all the unpruned paths
found in its first run, so that they could be reused in the subsequent runs.

CertQR denoted our certificate-based algorithm presented in Section 3.

CertQR+ denoted our improved algorithm presented in Section 4, not using any
heuristics introduced in Section 4.2.

dg, ds, and dgs denoted our improved algorithm presented in Section 4 using
the heuristics defined by Eq. (9), Eq. (11), and Eq. (12), respectively.

For all the algorithms, entity-relation graphs were stored in memory using the
JGraphT library777https://jgrapht.org/. We used Boolean arrays to record
visited entities and those having been processed by OptWithCert, so that set
membership could be checked in constant time. The priority queue in CertQR+
was implemented with a heap. BSL and our proposed algorithms used distance
oracles, which affordably occupied 9.2GB, 7.2GB, and 0.4GB memory for DBpedia,
LinkedMDB, and Mondial, respectively.

####  5.4.2 Experiment Design

For each query, we ran each algorithm under each diameter constraint (i.e.,
$D$) in the range of 3–6. To obtain more reliable results, we ran each
algorithm three times and took the median running time.

We set a timeout of 1,000 seconds. Any single run of an algorithm would be
terminated when reaching timeout. In that case, the running time was defined
to be the timeout value. Therefore, the longest running time reported in the
following was bounded by 1,000 seconds.

(a) DBpedia (simulated queries)

(b) LinkedMDB (simulated queries)

(c) Mondial (simulated queries)

(d) DBpedia (random queries)

(e) LinkedMDB (random queries)

(f) Mondial (random queries)

Figure 8: Time per run, broken down by number of query entities (i.e., $n$).

(a) DBpedia (simulated queries)

(b) LinkedMDB (simulated queries)

(c) Mondial (simulated queries)

(d) DBpedia (random queries)

(e) LinkedMDB (random queries)

(f) Mondial (random queries)

Figure 9: Time per run, broken down by diameter constraint (i.e., $D$).

####  5.4.3 Experiment Results and Analysis: CertQR(+) versus BSL(+)

Table 2 and Table 3 show the proportions of runs where BSL and BSL+ reached
timeout, respectively. Timeout was more often when the number of query
entities (i.e., $n$) increased, and became notable from $n=4$, suggesting the
difficulty of the problem and the unscalability of this intuitive solution. By
comparison, our proposed CertQR and CertQR+ never reached timeout in the
experiment, showing their scalability.

The running time of BSL, BSL+, CertQR, and CertQR+ are shown in Fig. 8 and
Fig. 9 on a logarithmic scale, with lines representing standard deviations. In
Fig. 8 where the results were broken down by number of query entities (i.e.,
$n$), although the improved BSL+ slightly outperformed BSL, both of them were
notably slower than CertQR on DBpedia (Fig. 8a and Fig. 8d) and Mondial (Fig.
8c and Fig. 8f). The differences were larger than an order of magnitude in
most cases, and became larger when $n$ increased, which _demonstrated the
effectiveness of using certificates and showed the higher efficiency of
CertQR_.

CertQR+ consistently outperformed CertQR. Their differences on large graphs,
i.e., DBpedia (Fig. 8a and Fig. 8d) and LinkedMDB (Fig. 8b and Fig. 8e), were
about an order of magnitude, which _demonstrated the effectiveness of our
distance-based estimation for best-first search_. In particular, CertQR+ used
less than 1 second under most settings, and used 2 seconds only on occasion
(in Fig. 8d). Its performance was sufficient for practical use.

One exception was on random queries on LinkedMDB (Fig. 8e), where BSL and BSL+
outperformed CertQR though still were second to CertQR+. The fairly good
performance of BSL and BSL+ was mainly attributed to the sparseness of
LinkedMDB. According to Table 1, the arc-vertex ratio of LinkedMDB was much
lower than that of DBpedia and Mondial. Recall that BSL and BSL+ used a path-
merging based algorithm to search for an SA. For a random query which usually
consisted of distantly connected entities, paths starting from them rarely met
when the graph was sparse, so fewer merging operations were performed.

Table 4: Performance Improvement on CertQR+ Dataset | Query | dg | ds | dgs
---|---|---|---|---
DBpedia | Simulated | 19.55% | 13.52% | 23.43%
| Random | 15.41% | 6.07% | 18.99%
LinkedMDB | Simulated | 26.97% | 15.12% | 31.20%
| Random | 17.94% | 9.72% | 17.96%
Mondial | Simulated | -4.08% | -1.74% | -0.82%
| Random | 1.93% | 1.04% | 5.23%

In Fig. 9 where the results were broken down by diameter constraint (i.e.,
$D$), CertQR+ was also generally the fastest. We would like to clarify two
phenomena that might confuse. First, the performance of BSL and BSL+
fluctuated, because they ran slower when $D$ was odd. In that case, merging a
set of paths of length $\left\lceil{\frac{D}{2}}\right\rceil$ could form an SA
of diameter $D+1$ and violate the diameter constraint, so the algorithm had to
continue with other merging options. Second, for simulated queries (Fig. 9a,
Fig. 9b, and Fig. 9c) which were successful in most cases, CertQR+ generally
used less time when $D$ increased, because the number of certificates also
increased. It became easier for best-first search to find a certificate,
whereas the search space of other algorithms grew, which _showed the
scalability of CertQR+ from another perspective_.

####  5.4.4 Experiment Results and Analysis: dg, ds, and dgs

Table 4 shows the performance improvement by adding the three heuristics to
CertQR+. In most cases, both dg and ds considerably improved the performance.
Their combination (i.e., dgs) produced the best results. The results suggested
that _the two fine-grained heuristics were both effective, and their effects
were complementary._ However, adding heuristics caused negative effects on
Mondial, where most simulated queries were successful when $D$ was small
according to Fig. 6c. Because the graph was small and dense, there were many
certificates which could be quickly found by CertQR+ without using any
heuristics. Only in that case, adding heuristics did not help much, but their
computation took additional time.

##  6 Related Work

SA search has attracted vast research attention from the Semantic Web and
database communities [6, 7, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 8, 9].
Whereas existing efforts are focused on search algorithms and ranking
criteria, _we present the first study on query relaxation_ , which is useful
when the compactness of allowable SAs is constrained [2, 4, 10, 7, 13, 15, 11,
12, 8]. This new research problem and the techniques we use are fundamentally
different from those considered in the literature. In particular, to verify
the success of a relationship query, _we search for a certificate entity
instead of expensively searching for an SA_. We mainly exploit distances
between entities to prune the search space and improve the performance.
Distance is also used in related research [11, 20, 21, 22, 25]. By comparison,
our theoretical contributions are distinguished by: _a distance-based
certificate based on which the success of a query can be more efficiently
verified (i.e., Theorem 1)_, and _a distance-based estimation which guarantees
the optimality of best-first search (i.e., Theorem 2)_.

Query relaxation for other related tasks have been formulated in completely
different ways. In entity search, a query consists of a set of property values
describing entity targets. Query relaxation allows an answer to have property
values that are not exactly the same as but similar to those specified in the
query [30]. For a path query formulated using regular expressions
characterizing path targets, it can be relaxed to less specific expressions
based on inference rules [33]. More general graph queries (e.g., SPARQL
queries for RDF) can be relaxed by substituting constants with variables, and
by removing its constituents (e.g., triple patterns) or making them optional
[28, 34]. Clearly, these ad hoc solutions could not be directly applied to the
problem we consider. A relationship query consists of a set of entities, which
is different from the above queries.

##  7 Conclusion and Future Work

The ability to relax a failing relationship query and provide alternative
results improves the usability of an SA search system. We show that simply
relaxing the compactness constraint is impracticable, and we turn to minimally
relaxing the query entities. Our proposed certificate-based best-first search
algorithm is more scalable than baselines, and its performance could meet the
demands of practical use. We believe its application is not restricted to SA
search. For example, our proposed algorithm can be straightforwardly extended
to relax keyword queries on graphs where each query keyword can be mapped to
multiple query entities. This will be our future work.

Our solution has the following limitations. First, our algorithm depends on
fast distance calculation. In this work we implement a distance oracle to
achieve a trade-off between time and space. However, it requires rebuild when
an entity-relation graph evolves. Besides, resource-limited machines may not
store it in memory, which could notably influence the performance. We will
seek better substitute techniques in future work. Second, although our
algorithm has minimized result incompleteness by finding a maximum successful
sub-query, a user may still be unsatisfied with relaxed results due to missing
query entities. One potentially better solution is to perform replacement
rather than removal, e.g., to replace some query entities with other similar
entities. It would be interesting to conduct a user study to compare different
kinds of solutions. Third, we separate query relaxation from SA search in
order to generalize our solution to a wider range of application. However, it
may be more efficient to have a hybrid algorithm that directly outputs relaxed
top-ranked SAs. We will explore this direction based on some common ranking
criteria.

## Acknowledgment

This work was supported in part by the NSFC under Grant 61772264, and in part
by the Six Talent Peaks Program of Jiangsu Province under Grant RJFW-011.

## References

  * [1] K. Anyanwu, A. P. Sheth, $\rho$-queries: enabling querying for semantic associations on the semantic web, in: Proceedings of the Twelfth International World Wide Web Conference, WWW 2003, Budapest, Hungary, May 20-24, 2003, 2003, pp. 690–699.  doi:10.1145/775152.775249.
URL http://doi.acm.org/10.1145/775152.775249

  * [2] G. Cheng, Y. Zhang, Y. Qu, Explass: Exploring associations between entities via top-k ontological patterns and facets, in: The Semantic Web - ISWC 2014 - 13th International Semantic Web Conference, Riva del Garda, Italy, October 19-23, 2014. Proceedings, Part II, 2014, pp. 422–437.  doi:10.1007/978-3-319-11915-1_27.
URL https://doi.org/10.1007/978-3-319-11915-1_27

  * [3] C. Halaschek-Wiener, B. Aleman-Meza, I. B. Arpinar, A. P. Sheth, Discovering and ranking semantic associations over a large RDF metabase, in: (e)Proceedings of the Thirtieth International Conference on Very Large Data Bases, Toronto, Canada, August 31 - September 3 2004, 2004, pp. 1317–1320.
URL http://www.vldb.org/conf/2004/DEMP17.PDF

  * [4] M. Janik, K. Kochut, BRAHMS: A workbench RDF store and high performance memory system for semantic association discovery, in: The Semantic Web - ISWC 2005, 4th International Semantic Web Conference, ISWC 2005, Galway, Ireland, November 6-10, 2005, Proceedings, 2005, pp. 431–445.  doi:10.1007/11574620_32.
URL https://doi.org/10.1007/11574620_32

  * [5] M. Zhou, Y. Pan, Y. Wu, Efficient association discovery with keyword-based constraints on large graph data, in: Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom, October 24-28, 2011, 2011, pp. 2441–2444.  doi:10.1145/2063576.2063987.
URL http://doi.acm.org/10.1145/2063576.2063987

  * [6] K. Anyanwu, A. Maduko, A. P. Sheth, Semrank: ranking complex relationship search results on the semantic web, in: Proceedings of the 14th international conference on World Wide Web, WWW 2005, Chiba, Japan, May 10-14, 2005, 2005, pp. 117–127.  doi:10.1145/1060745.1060766.
URL http://doi.acm.org/10.1145/1060745.1060766

  * [7] L. Fang, A. D. Sarma, C. Yu, P. Bohannon, REX: explaining relationships between entity pairs, PVLDB 5 (3) (2011) 241–252.  doi:10.14778/2078331.2078339.
URL http://www.vldb.org/pvldb/vol5/p241_lujunfang_vldb2012.pdf

  * [8] G. Pirrò, Explaining and suggesting relatedness in knowledge graphs, in: The Semantic Web - ISWC 2015 - 14th International Semantic Web Conference, Bethlehem, PA, USA, October 11-15, 2015, Proceedings, Part I, 2015, pp. 622–639.  doi:10.1007/978-3-319-25007-6_36.
URL https://doi.org/10.1007/978-3-319-25007-6_36

  * [9] J. Lehmann, J. Schüppel, S. Auer, Discovering unknown connections - the dbpedia relationship finder, in: The Social Semantic Web 2007, Proceedings of the 1st Conference on Social Semantic Web (CSSW), September 26-28, 2007, Leipzig, Germany., 2007, pp. 99–110.
URL http://subs.emis.de/LNI/Proceedings/Proceedings113/article1855.html

  * [10] C. Chen, G. Wang, H. Liu, J. Xin, Y. Yuan, SISP: a new framework for searching the informative subgraph based on PSO, in: Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom, October 24-28, 2011, 2011, pp. 453–462.  doi:10.1145/2063576.2063645.
URL http://doi.acm.org/10.1145/2063576.2063645

  * [11] G. Cheng, D. Liu, Y. Qu, Efficient algorithms for association finding and frequent association pattern mining, in: The Semantic Web - ISWC 2016 - 15th International Semantic Web Conference, Kobe, Japan, October 17-21, 2016, Proceedings, Part I, 2016, pp. 119–134.  doi:10.1007/978-3-319-46523-4_8.
URL https://doi.org/10.1007/978-3-319-46523-4_8

  * [12] G. Cheng, F. Shao, Y. Qu, An empirical evaluation of techniques for ranking semantic associations, IEEE Trans. Knowl. Data Eng. 29 (11) (2017) 2388–2401.  doi:10.1109/TKDE.2017.2735970.
URL https://doi.org/10.1109/TKDE.2017.2735970

  * [13] G. Kasneci, S. Elbassuoni, G. Weikum, MING: mining informative entity relationship subgraphs, in: Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM 2009, Hong Kong, China, November 2-6, 2009, 2009, pp. 1653–1656.  doi:10.1145/1645953.1646196.
URL http://doi.acm.org/10.1145/1645953.1646196

  * [14] G. Kasneci, M. Ramanath, M. Sozio, F. M. Suchanek, G. Weikum, STAR: steiner-tree approximation in relationship graphs, in: Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China, 2009, pp. 868–879.  doi:10.1109/ICDE.2009.64.
URL https://doi.org/10.1109/ICDE.2009.64

  * [15] H. Tong, C. Faloutsos, Center-piece subgraphs: problem definition and fast solutions, in: Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA, August 20-23, 2006, 2006, pp. 404–413.  doi:10.1145/1150402.1150448.
URL http://doi.acm.org/10.1145/1150402.1150448

  * [16] A. P. Sheth, B. Aleman-Meza, I. B. Arpinar, C. Bertram, Y. S. Warke, C. Ramakrishnan, C. Halaschek, K. Anyanwu, D. Avant, F. S. Arpinar, K. Kochut, Semantic association identification and knowledge discovery for national security applications, J. Database Manag. 16 (1) (2005) 33–53.  doi:10.4018/jdm.2005010103.
URL https://doi.org/10.4018/jdm.2005010103

  * [17] Y. Makita, N. Kobayashi, Y. Yoshida, K. Doi, Y. Mochizuki, K. Nishikata, A. Matsushima, S. Takahashi, M. Ishii, T. Takatsuki, R. Bhatia, Z. Khadbaatar, H. Watabe, H. Masuya, T. Toyoda, Posmed: ranking genes and bioresources based on semantic web association study, Nucleic Acids Research 41 (Webserver-Issue) (2013) 109–114.  doi:10.1093/nar/gkt474.
URL https://doi.org/10.1093/nar/gkt474

  * [18] G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, S. Sudarshan, Keyword searching and browsing in databases using BANKS, in: Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26 \- March 1, 2002, 2002, pp. 431–440.  doi:10.1109/ICDE.2002.994756.
URL https://doi.org/10.1109/ICDE.2002.994756

  * [19] B. Ding, J. X. Yu, S. Wang, L. Qin, X. Zhang, X. Lin, Finding top-k min-cost connected trees in databases, in: Proceedings of the 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey, April 15-20, 2007, 2007, pp. 836–845.  doi:10.1109/ICDE.2007.367929.
URL https://doi.org/10.1109/ICDE.2007.367929

  * [20] H. He, H. Wang, J. Yang, P. S. Yu, BLINKS: ranked keyword searches on graphs, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, Beijing, China, June 12-14, 2007, 2007, pp. 305–316.  doi:10.1145/1247480.1247516.
URL http://doi.acm.org/10.1145/1247480.1247516

  * [21] V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, H. Karambelkar, Bidirectional expansion for keyword search on graph databases, in: Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005, 2005, pp. 505–516.
URL
http://www.vldb.org/archives/website/2005/program/paper/wed/p505-kacholia.pdf

  * [22] M. Kargar, A. An, Keyword search in graphs: Finding r-cliques, PVLDB 4 (10) (2011) 681–692.  doi:10.14778/2021017.2021025.
URL http://www.vldb.org/pvldb/vol4/p681-kargar.pdf

  * [23] W. Le, F. Li, A. Kementsietsidis, S. Duan, Scalable keyword search on large RDF data, IEEE Trans. Knowl. Data Eng. 26 (11) (2014) 2774–2788.  doi:10.1109/TKDE.2014.2302294.
URL https://doi.org/10.1109/TKDE.2014.2302294

  * [24] G. Li, B. C. Ooi, J. Feng, J. Wang, L. Zhou, EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, 2008, pp. 903–914.  doi:10.1145/1376616.1376706.
URL http://doi.acm.org/10.1145/1376616.1376706

  * [25] R. Li, L. Qin, J. X. Yu, R. Mao, Efficient and progressive group steiner tree search, in: Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, 2016, pp. 91–106.  doi:10.1145/2882903.2915217.
URL http://doi.acm.org/10.1145/2882903.2915217

  * [26] J. Coffman, A. C. Weaver, An empirical performance evaluation of relational keyword search techniques, IEEE Trans. Knowl. Data Eng. 26 (1) (2014) 30–42.  doi:10.1109/TKDE.2012.228.
URL https://doi.org/10.1109/TKDE.2012.228

  * [27] N. Koudas, C. Li, A. K. H. Tung, R. Vernica, Relaxing join and selection queries, in: Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, 2006, 2006, pp. 199–210.
URL http://dl.acm.org/citation.cfm?id=1164146

  * [28] S. Elbassuoni, M. Ramanath, G. Weikum, Query relaxation for entity-relationship search, in: The Semanic Web: Research and Applications - 8th Extended Semantic Web Conference, ESWC 2011, Heraklion, Crete, Greece, May 29 - June 2, 2011, Proceedings, Part II, 2011, pp. 62–76.  doi:10.1007/978-3-642-21064-8_5.
URL https://doi.org/10.1007/978-3-642-21064-8_5

  * [29] G. Koloniari, E. Pitoura, Distributed structural relaxation of xpath queries, in: Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China, 2009, pp. 529–540.  doi:10.1109/ICDE.2009.110.
URL https://doi.org/10.1109/ICDE.2009.110

  * [30] A. Hogan, M. Mellotte, G. Powell, D. Stampouli, Towards fuzzy query-relaxation for RDF, in: The Semantic Web: Research and Applications \- 9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 27-31, 2012. Proceedings, 2012, pp. 687–702.  doi:10.1007/978-3-642-30284-8_53.
URL https://doi.org/10.1007/978-3-642-30284-8_53

  * [31] T. Akiba, Y. Iwata, Y. Yoshida, Fast exact shortest-path distance queries on large networks by pruned landmark labeling, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2013, New York, NY, USA, June 22-27, 2013, 2013, pp. 349–360.  doi:10.1145/2463676.2465315.
URL http://doi.acm.org/10.1145/2463676.2465315

  * [32] C. Sommer, Shortest-path queries in static networks, ACM Comput. Surv. 46 (4) (2014) 45:1–45:31.  doi:10.1145/2530531.
URL http://doi.acm.org/10.1145/2530531

  * [33] A. Poulovassilis, P. Selmer, P. T. Wood, Approximation and relaxation of semantic web path queries, J. Web Sem. 40 (2016) 1–21.  doi:10.1016/j.websem.2016.08.001.
URL https://doi.org/10.1016/j.websem.2016.08.001

  * [34] G. Fokou, S. Jean, A. Hadjali, M. Baron, Cooperative techniques for SPARQL query relaxation in RDF databases, in: The Semantic Web. Latest Advances and New Domains - 12th European Semantic Web Conference, ESWC 2015, Portoroz, Slovenia, May 31 - June 4, 2015. Proceedings, 2015, pp. 237–252.  doi:10.1007/978-3-319-18818-8_15.
URL https://doi.org/10.1007/978-3-319-18818-8_15