Performance Prediction for Graph Queries
Mohammad Hossein Namaki, Keyvan Sasani, Yinghui Wu, Assefaw H. Gebremedhin
Washington State University{mnamaki, ksasani, yinghui, assefaw}@eecs.wsu.edu

ABSTRACT
Query performance prediction has shown benefits toquery optimization and resource allocation for relational
databases. Emerging applications are leading to search scenarios where workloads with heterogeneous, structure-lessanalytical queries are processed over large-scale graph andnetwork data. This calls for effective models to predict theperformance of graph analytical queries, which are often
more involved than their relational counterparts.
In this paper, we study and evaluate predictive techniques
for graph query performance prediction. We make several
contributions. (1) We propose a general learning frameworkthat makes use of practical and computationally efficient
statistics from query scenarios and employs regression models. (2) We instantiate the framework with two routinely
issued query classes, namely, reachability and graph pattern matching, that exhibit different query complexity. We
develop modeling and learning algorithms for both queryclasses. (3) We show that our prediction models readily apply to resource-bounded querying, by providing a learningbased workload optimization strategy. Given a query workload and a time bound, the models select queries to beprocessed with a maximized query profit and a total costwithin the bound. Using real-world graphs, we experimentally demonstrate the efficacy of our framework in terms ofaccuracy and the effectiveness of workload optimization.

1.

INTRODUCTION

Graph queries have found prevalent use in knowledge extraction, traffic analytics, Web mining, social network analysis, and social media marketing. Common graph queries
include (a) graph traversal, e.g., reachability queries, and(b) pattern matching via subgraph isomorphism or simulation. Emerging applications require efficient workload processing with bounded resources [8]. Meanwhile, on realworld graphs that easily have billions of nodes and edges,
graph queries are costly, even for reachability (linear-time),
let alone subgraph isomorphism (NP-complete).
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others thanACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.

NDA’17 May 19, 2017, Chicago, IL, USA
c 2017 ACM. ISBN 978-1-4503-4990-1/17/05. . . $15.00
DOI: http://dx.doi.org/10.1145/3068943.3068947

Artist...

Jennifer Lopez Jennifer Lealand

Band
Query Q(A rtist)(A rtist)

J.Lo

Graph G
Tim & Bob

Canela Cox(A rtist)(Band)

a matchFigure 1: Approximate subgraph querying [19]Database systems can greatly benefit from query performance prediction (QPP) for effective resource management
and online query optimization. Given a workload W, adatabase D, and performance metrics M (e.g., response
time, memory), the QPP problem is to predict M for eachquery instance in W over D. Various modeling and learningtechniques for such predictions have been developed for relational queries [2,6,9–11]. These approaches, by employing
statistics from relational algebra, relational data, and (logical and physical) query plans [2, 12], have been found to bequite accurate for relational queries.
In contrast, QPP is particularly challenging for graphanalytical workloads, for several reasons. First, graphqueries, unlike their relational counterparts, can be “structureless” [29], i.e., not well supported by rigid algebra andsyntax. It is often hard to exploit algebra and operator-levelfeatures (e.g., number of “join”) [2,12] for graph queries (e.g.,reachability queries). Second, graph data is often noisy andheterogeneous. Features from data graph alone may not be
reliable for QPP tasks. Third, while a common practice for
QPP is to explore (logical and physical) query plans that are
generated following a principled manner [2], this is inapplicable for approximate graph queries.
Example 1: Consider a query posed on a knowledge graphDBpedia that finds the artists who work with “J.Lo” in aBand [19]. This query can be represented by a graph pattern
Q that carries (ambiguous) keywords, with a corresponding
approximate match as illustrated in Fig. 1. Each patternnode in Q may have a large number of candidate matches.
The quality of the answer is usually determined only at
run-time via similarity functions [29]. For example, “Canela
Cox” is a best answer when “Jennifer Lopez” is matched tothe ambiguous keyword “J.Lo” in the query. Conventional
QPP that exploits relational algebra may not be applicablefor graph pattern Q, as the syntax and declarative operators
are hard to be derived from the “structureless” Q. Moreover,deriving statistics from the graph data alone is already expensive, due to the sheer size of data, and the fact that theunderlying graph may change from time to time.
2

In this paper, we present effective QPP methods forgraph analytical workloads. We develop a practical learning
paradigm that only makes use of computationally efficientquery-oriented features and statistics from executed graphqueries, without imposing any assumptions on graph data,
query syntax and algebra. Our goal is to build a prediction
framework for routinely issued, structureless graph queries.
Contributions. We make the following contribution.
(1) We propose a general learning framework to predict thequery performance of graph analytical queries. The learning
framework makes use of (a) three pragmatic classes of queryoriented features—called query-, sketch- and algorithmfeatures—that characterize query constraints, statistics ofdata to be accessed, and query evaluation behavior, respectively; and (b) well established regression models.
(2) Using the framework, we study two classes of frequently
occurring graph queries and develop models and learningalgorithms for each query class.
(3) We apply the query performance prediction to resourcebounded querying, and develop learning-based workload optimization strategies. The strategy aims to maximize thetotal profit of executed queries within a time bound, by selecting queries based on their predicted performance.
(4) Using real-world datasets, we experimentally verify theeffectiveness of the query prediction and workload optimization. We find the following. (a) Our models can accurately predict the performance of graph queries utilizing
conventional regression models and a handful of simple features. The best predictor attains an average accuracy of 0.93
and 0.96 over the knowledge graphs DBpedia and Freebase,respectively. (b) Our workload optimization strategy improves the effectiveness (measured by total profit of processed queries) of graph engines under bounded resource.
On average, it achieves 92.78% of the effectiveness of an
optimizer that knows the actual run-time of queries. Thesesuggest useful QPP tools for effective online graph analytics.
The rest of the paper is organized as follows. In Section
2, we briefly introduce the graph query classes we consider
as well as the algorithms used in our learning models as a
black box. In Section 3, we describe the models that we havedeveloped for prediction. In Section 4, we address workload
optimization problem. In Section 5, we present experimental
results. We describe related work in Section 6, and conclude
in Section 7.

2.

GRAPH QUERY PERFORMANCE PREDICTION

2.1

Graph queries

Data graphs. We consider a labeled and directed datagraph G=(V, E, L), with node set V and edge set E. Eachnode v ∈ V (edge e ∈ E) has a label L(v) (L(e)) thatspecifies node (edge) information, and each edge represents
a relationship between two nodes. In practice, L may specify
attributes, entity types, and relation names [16].
Graph queries. We consider two familiar query classes.
Graph pattern queries. Graph pattern matching has been
widely applied in areas such as social marketing, cyber security and knowledge extraction. A graph pattern Q is agraph (VQ , EQ , LQ ). Each pattern node u ∈ VQ has a label
LQ (u) that describes the entities to be searched for (e.g.,

type, attribute values), and an edge e ∈ EQ between twoquery nodes specifies the relationship posed on the two entities. A match of Q in G, denoted as Q(G), is a subgraphof G that satisfies certain matching semantics. Given Q, G
and a function f (·) that quantifies the quality of the match
Q(G) to Q, a top-k graph pattern query Q(G, k, f ) finds kbest matches ranked by their quality as determined by f (·).
We consider two specifications for graph pattern queries(see Section 3.2) from approximate graph analytics:◦ Subgraph query [29], which specifies a match Q(G) as a
subgraph induced by an isomorphism between Q and
Q(G); and◦ Simulation query [17], which induces subgraphs Q(G)with entities and relations that satisfy a (dual)simulation relation between Q and Q(G).
For both query classes, the quality of Q(G) can be computed by aggregating (e.g., summing up) a similarity score
between each node (resp. edge) in Q and its counterpart(s)in Q(G) by f (·) [29]. A subgraph query Q and its top match
is illustrated in Fig. 1.
Reachability queries. Reachability queries are routinely used
for traffic analysis, social analysis and Web mining. We
consider a generalized reachability query Q(G, s, t, d), where
G is a graph, s is the source label, t is the target label, and d
is a number. The query asks: “Does there exist a source nodewith label s and a target node with label t that are connectedby a path of length bounded by d in G?” When d=∞, ands and t each has a unique match, Q(G, s, t, d) reduces toconventional single-source single-target reachability test.
Graph pattern queries and reachability queries are representative graph analytical queries. They do not haverigid query structures and syntax. Moreover, the query
performance are determined at run-time, typically via afixed-point computation. Conventional QPP that exploit
operator- and plan-level statistics is not applicable for these
queries.
In the next subsection, we describe query performance
prediction for graph analytics. We address the query evaluation algorithms in Section 3, which are treated as “blackbox” by our learning framework.

2.2

Query performance prediction

Our goal here is to formulate QPP for graph analytical workloads. We consider (1) a mixed workload
W={Q1 , . . . , Qn } over a set of query classes Q, where eachquery Qi is a query instance from a query class in Q; and(2) response time t as the performance metric to be predicted. The problem of graph query performance prediction, denoted as GQPP, is to learn a prediction model P topredict the response time of each query instance in W withmaximum accuracy measured by a specific metric.
Metric. A metric must measure how well the run-time of
future queries are likely to be predicted. We seek to minimize the error depending on the type of the queries andthe scale of their run-time. Therefore, we use R-Squared,
a widely used evaluation metric [12] to evaluate our models. Given n graph queries, R-Squared (denoted as R2 ) is
computed as follows:Pn(yi − yˆi )22
R (y, ŷ) = 1 − Pi=1n2i=1 (yi − ȳ)
where y, ŷ and ȳ are the actual values, predicted values,
and the mean of actual values, respectively. The larger the(a) Query features encode the topological constraints (e.g.,query size, degree, cyclic) and semantic constraints (e.g.,label, transformation functions [29]) from query terms.

Figure 2: Learning framework for GQPP
2

R value is (up to 1), the more accurate the model is.
To empirically verify the robustness of our models, we
also consider two other statistical metrics besides R2 : normalized root mean square error (NRMSE) and mean absolute
error (MAE). NRMSE normalizes the standard deviation of
the differences between predicted values and actual values(RMSE) normalized with standard
P deviation of actual values [27]. MAE, defined as n1 n
i=1 |ŷ − y|, is an absolutecomparison of predictions and eventual outcomes [10].
GQPP as regression. We approach GQPP as a regression
problem. We use the following construction.
◦ Input: A data graph G, a query Q, a feature set F◦ Output: a prediction model P that maximize R2
The problem is to learn, using regression, a function
f (x) = y that maps a feature vector x (that encodes thefeatures in F) to a continuous value y corresponding to theexact response time of the query. The goal is to minimize|ŷ − y|. That is, the closer ŷ is to y, the closer R2 is to 1.

3.

PREDICTION FRAMEWORKWe next introduce our GQPP framework. We start withan overview of the framwork (Section 3.1). We then instantiate the general framework to graph pattern queries(Section 3.2) and reachability queries (Section 3.3).

3.1

Overview

The general GQPP framework is illustrated in Fig. 2.
Following statistical learning, it derives a prediction model
based on training sets (i.e., offline learning), and then predicts query performance for unknown “test” data points
based on the derived model (i.e., online prediction). Our
goal is then to adapt the framework to optimize the (mixed)
graph analytical workload within a bounded resource.
Learning phase. This stage consists of the following. (1)The framework generates training workload WT (to be discussed). To this end, it generates queries, evaluates thequeries over the data graph G (stored and managed by graphdatabase) by invoking standard query evaluation algorithms,
and collects the performance metrics and features for eachquery to construct WT . (2) The predictive model is thenderived by solving the regression problem (Section 2.2).
Features. As remarked earlier, graph analytical queries, unlike their relational counterparts, cannot be easily characterized by features from operators, algebra and apriori queryplans. Features from data alone may also be unreliable. We
hence consider three classes of query-oriented features. The
features are called Query, Sketch, and Algorithm features,
since they characterize statistics from query instances, accessed data, and search behavior, respectively.

(b) Sketch features. The idea is to exploit statistics that estimate the specificity and ambiguity of a query by “sketching”
the data that will be accessed by the queries. These features
may include the size of candidates (the nodes having thesame or similar labels to some pattern query nodes), degreeof sampled candidates, and statistics of sampled neighborhood of the candidates. By paying an affordable amount oftime, these features significantly contribute to the prediction
accuracy of graph queries (as verified in Section 5).
(c) Algorithm features refer to the features that characterize
the performance of graph querying algorithms. For example, top-k graph search typically decomposes a query to subqueries, and assembles the complete results by aggregating
partial matches as multi-way joins [28]. We found that features such as the number of decompositions and “joinable”
candidates are very informative and critical to predict thecost of top-k search (see Section 3.2).
These features can be computed efficiently. Indeed, they
can be extracted by fast linear scans and sampling overqueries and data graphs, and are well supported by established database indexing techniques [28].
Training workload. Given a query class Q, data graph G anda standard evaluation algorithm A, the training workload
WT is a set of pairs (Qi .F, ti ), where (1) Qi is a queryinstance from Q, F is a set of features, and Qi .F refers toa feature representation of a query, and (2) ti is the actual
response time by evaluating Qi with algorithm A. Each pairis instantiated as a single data instance. Progressively, thedata instances are appended to the training workload.
Predictive models. We evaluate a number of methods.
Linear regression. A simple start is linear regression, where
the relationships of independent variables, i.e., the features
Qi .F, and the dependent variable, i.e., the response time ti
of Qi , are modeled using linear predictor functions. The goal
is to find the coefficients ak in the equation t = a1 (Q.F1 ) +a2 (Q.F2 ) + ... + an (Q.Fn ) +  where  is a noise term [9].
Regression trees. Linear regression may fail to accurately
model dependencies that are beyond linear. We consider
regression tree, a more complex model similar to a decision
tree, except that it predicts continuous values instead of
discrete classes.
Random forest. Significant improvements in predictors’ accuracy have resulted from growing an ensemble of trees by
asking them to vote for the predicted value [4]. Ensemble methods allow us to combine diverse weak regression
trees by taking different samples of the original data set
and then combining their outputs [22]. A random forest isa meta-estimator that fits some regression trees on various
subsamples of the dataset and use averaging to improve thepredictive accuracy and control over-fitting [20].
KNN. An alternative method is k-nearest neighbors (kNN)
regression [1]. kNN predicts based on the k closest neighborsof an instance, determined by a predefined distance function.
We consider Euclidean distance over the feature space.
SVM. We also consider SVM (Support Vector Machines)
with nu-SVR kernel for regression [23] (SVM). SVM maps

Query 1

J.Lo

Table 1: Top features for subgraph queries

Query 2Artist Band
ArtistJennifer
Lopez(Fetch)Canela Tim &
Cox
Bob

...

rankedpartialanswers

top-1
Join

... ...

SortedAccessBand

Canela Tim &Bob
Cox

Jennifer
Lopez

Canela Tim &Cox
Bob

Figure 3: Illustration of top-k querying [19]the features to a higher dimensional space to make it possible
to perform the linear separation and perform the regression
in that space.
Correlation analysis. Exploratory data analysis (EDA) is
an important step in data mining to understand the natureof the data. Leveraging summarization and visualization
techniques, it seeks to identify critical features of a dataset
and to eliminate outliers and anomalies [25]. We use EDA
to compare the statistical characteristics of data sets (seeTable 4), identify the relative importance of the features(see Tables 1, 2, and 3), and visually analyze the accuracyof predictors (Fig. 5(a)).
Online prediction. The prediction model is applied to
predict the performance of newly arrived queries. Upon
receiving a query workflow, the framework (1) collects thequeries and computes the query features, and (2) predicts
the query performance metrics. The predicted results canthen be readily applied for resource allocation and workload
optimization (see Section 4).
We next present the learning-based GQPP for specificgraph analytical query classes. The major specification weneed to make is to identify proper features.

3.2

GQPP for pattern queries

We consider two representative classes of graph pattern
queries as follows.
Top-k Subgraph queries [28]. A top-k subgraph query
Q(G, k, f ) defines a match using subgraph isomorphism,
while f is derived by a set of functions drawn from a library (e.g., acronym, synonym, abbreviations), where eachfunction maps nodes and edges (as ambiguous keywords) in
Q to their counterparts in G.
Algorithm. A common practice to evaluate Q(G, k, f ) is tofollow the Threshold Algorithm [7] that aggregates top-ktuples in relational tables. Such an algorithm does the following (illustrated in Fig 3).
(1) Decomposes Q to n small fragments (subqueries, e.g.,stars, twigs) where partial answers can be efficiently evaluated. For each fragment, a sorted list is assigned.
(2) Iteratively generates and fetches partial matches foreach fragment, and assembles the partial matches tocomplete ones whenever possible in a n-way join, following
a sorted access to the lists in (1), until k complete answers are found or no new partial matches can be generated.

Featurepartial matches candidate
joinable nodes
pivots contributed in match(es)node in fragments
pivot candidates
pivot degree avg.
# of query nodes# of query relationships# of fragments

Type
A
A
A
A
S
S
Q
Q
A

Rel.imp.(%)
69.43
15.24
8.45
5.45
1.01
0.22
0.09
0.07
0.03

Two optimizations are typically applied in step (2). (a) A“pivot” pattern node (e.g., center of a star) is selected andassigned to each fragment of Q, so partial answers can becomputed more efficiently. In accordance, a priority queue
P is maintained for the pivot nodes, which bookkeeps theircandidates with non-increasing order (determined by function f ). (b) An estimated upper bound of the quality of the“unseen” answers and a lower bound of the quality of the“seen” complete matches are maintained and compared toguarantee early termination.
Example 2: The algorithm finds top-1 answer for the query
Q shown in Fig 1 as follows (illustrated in Fig 3). It firstdecomposes Q to two stars (Q1 and Q2 ). It then fetches
partial answers for each star query in a sorted manner, andjoins the partial answers whenever possible, until it finds acomplete match and termination criteria is met.
2
We use the algorithm in [28] as a “yardstick” for TA-style
top-k subgraph search.
Features. We consider the following features.
(1) Query features (Q): indicates the query size, determinedby the number of pattern nodes and edges. Intuitively, it
usually takes more time to process larger queries.
(2) Sketch features (S): includes the number of candidates
for pivot nodes. The more candidates pivot nodes have, themore expensive the join operations are.
(3) Algorithm features (A): Abusing the algorithm structure,
we extract the features that are related to query decomposition behavior, such as number of decomposed sub-queries,
number of nodes in each sub-query, and number of pivot
nodes that are in a non-empty partial match, among others.
The candidate size of pivot nodes can be efficiently estimated by using neighborhood indexing [28]. We also countthe number of “joinable nodes” from the decomposition, i.e.,
the number of pattern nodes shared by two sub-queries. The
intuition is that the more joinable nodes there are, the more
expensive it is to find a complete match due to the equi-join
nature of the algorithm.
Observation. We report in Table 1 the most important features, ranked by their relative importance (determined bycorrelation and EDA component). In a decision tree, theimportance of a feature F i (mean decrease impurity) [15]is the total amount of impurity reduction by adding F i to
the tree, where impurity can be computed utilizing variancereduction [5]. In a forest model, the relative importance isaveraged over all the trees for each feature [20].
We find that Algorithm and Sketch features play important role in predicting the performance of top-k subgraphqueries. Query features, on the other hand, is less important. Indeed, the performance of top-k subgraph queries

Table 2: Top features for Dual-simulation queries

Table 3: Top features for reachability queries

Featuresum of out-deg. in candidates
candidates of nodes
sum of in-deg. in candidates# query edges# query nodes

Featurehop bound dsum out-deg. of src. cand.
sum in-deg. of src. cand.
candidates of src.
sum in-deg. of dest. cand.
candidate of dest.
sum out-deg. of dest. cand.

Type
S
S
S
Q&A
Q

Rel. imp. (%)
44.71
30.68
24.18
0.22
0.20

may highly depend on the algorithm behavior (decomposition, n-way joins in the TA-style computation), which can be
more critical than the number of joins (a plan-level feature)
in a graph pattern [12].
Dual-simulation [17]. A dual-simulation query Q(G, k, f )relaxes the subgraph isomorphism from 1-1 bijective mapping to matching relations. Given Q(VQ , EQ , LQ ) and graph
G(V, E, L), a match relation R ⊆ VQ ×V satisfies the following: (1) for any node u ∈ VQ , there is a match v ∈ V suchthat (u, v) ∈ R, and LQ (u)=L(v); (2) for any (u, v) ∈ R,
and any child (resp. parent) of u (denoted as u0 ) in Q, there
is a child (resp. parent) of v (denoted as v 0 ) in G, such that(u0 , v 0 ) ∈ R. That is, it preserves both parent and childrelationships between a node u and its matches v.
As dual-simulation only considers label equality, f is a label equality function. It is known that there exists a unique,maximum matching relation R for dual-simulation [17].
Hence k=1 in Q(G, k, f ), and Q(G, k, f ) refers to the largest
subgraph of G induced by the matches.
Algorithm. A standard algorithm for dual-simulation queries
Q(G, 1, f ) starts by initializing, for each node u in Q, acandidate set C(u) with the nodes having the same label.
It then iteratively performs two join operations between thechildren of candidate sets C(u) (resp. parents of C(v)) andC(v) (resp. C(u)) for each edge (u, v) ∈ EQ , and removes
the candidates that cannot satisfy the constraints of dualsimulation by definition. This is repeated until a fixed pointis reached (no candidate can be removed).
Features. Again, it is nontrivial to predict the performanceof dual-simulation as a fixed-point computation. Luckily,
most of the graph pattern queries are not large (e.g., withdiameters up to 2 [3]), and a proper “sketching” of the candidates may suggest accurate estimation. We consider thefollowing features shown in Table 2 for dual-simulation, using the algorithm in [17] as yardstick algorithm.
(1) Query features: same as subgraph queries, we use number of nodes and edges of a query as query features.
(2) Sketch features: includes the size of candidates |C(u)|for each pattern node u in a query Q and statistics of theirdegree information. Intuitively, more candidates indicate
more expensive “joins” in the fixed-point computation. As
dual-simulation preserves both parent and child relationshipof each pattern node, we extract aggregations of both indegrees and out-degrees of their candidates.
(3) Algorithm features: we consider the number of patternedges as an algorithm feature as well, due to the nature of
the fixed-point computation: it always follows query edges
to perform join operations.
Observation. Unlike top-k subgraph queries, we find that
Sketch features dominate the prediction of the efficiency ofthe computation for dual-simulation queries (as illustrated
in Table 2). Candidate size and degree are critical for predicting dual-simulation query performance. Query size, on
the other hand, is less important.

3.3

Type
Q
S
S
S
S
S
S

Rel. imp. (%)
57.37
33.09
4.36
2.12
1.30
0.93
0.81

GQPP for reachability queries

We next investigate reachability queries. We use a suitably modified Breadth-First Search algorithm to evaluate
reachability queries Q(G, s, t, d). The algorithm finds thecandidate sets for source and target labels, and performs
reachability tests between the candidate sets of s and t.
Features. We use the following features (illustrated in Table 3) for reachability queries.
(1) Query features: includes the hop bound d. Intuitively,
the larger d is, the more expensive the traversal algorithmis, due to the larger set of nodes to be visited.
(2) Sketch features: include both candidate size for source
and target labels, and statistics of their degrees.
(3) Algorithm features: As the behavior of regular breadth
first search is not distinguishable for different reachability
query instances, we do not consider algorithm features.
Observation. For reachability queries, Query feature d andSketch features on degrees of source and target candidates
are the most important features. Indeed, the more candidates and more neighbors they have, and the more hops aquery needs to visit, the more expensive the query is.
These observations are further verified in our experimental
study for graph pattern queries (see Table 6, Section 5).

4.

WORKLOAD OPTIMIZATION

Once the prediction models are derived, they can be readily applied for workload optimization. As an application, we
introduce a query selection strategy for resource bounded
computation based on our GQPP framework. To this end,
we formalize a workload optimization problem in the context
of resource-bounded querying [8].
Workload optimization. Consider a mixed query workload W={Q1 , . . . , Qn } over a set of query classes Q, where
each query Qi is an instance of a query class in Q, andis associated with a profit pi . Given a graph G, workload
W and a time bound T , the problem is to find a set of
queries W’ such that (a) the total time cost forP evaluating
W’ is bounded by T , and (b) the total profit Qi ∈W 0 pi ismaximized. In practice, the profit may refer to e.g., query
importance, priority or QoS profit [21].
Given the GQPP predictor, we present an optimization
strategy as follows. (1) Upon receiving W, it invokes thepredictor to estimate the time cost ti for each query Qi . (2)It then selects a set of queries W 0 ⊆ W by solving the knapsack problem via the following construction. It takes eachquery Qi as an item, the predicted run-time ti (resp. profitpi ) of Qi as item weights (resp. profit), and the time boundT as the size of a knapsack. This construction reduces the
problem to knapsack problem. It then invokes an approximation algorithm [24] that finds W’ with approximation
ratio (1 − ) for error bound  ∈ (0, 1), and in O(|W|2 ) time.

5.

EXPERIMENTS

Using two real-world knowledge graphs, we conduct threesets of experiments to evaluate the following: (1) Performance of different machine-learning predictors for GQPP;(2) Impact of the factors (e.g., size of training data) on theaccuracy of the predictors; and (3) Effectiveness of query
workload management, using a case study.
Experimental Setting. We used the following setting.
Datasets. The two real-world knowledge graphs we use forour experiments are Freebase and DBpedia. Freebase is a collaboratively created large knowledge base, containing 40.3M
entities (e.g., people, companies, cities), 180M relationships,
and 20K node and edge labels, extracted from several publicknowledge bases including Wikipedia. DBpedia consists of
4.86M labeled entities (where each label is one of the 1K
labels such as “Place”, “Person”, “Building”) and 15M edges.
Workload. We develop two query generators, one forgraph pattern queries (including subgraph queries and dualsimulation queries) and the other for reachability queries.
These queries are used to construct the training and test
sets over the two real-world knowledge graphs.
Graph pattern queries. To generate graph pattern queries
Q(k, f, G), we use the DBPSP benchmark [18], a DBpedia
query benchmark. To achieve this, we first generate a setof query templates. Each template has a topology sampledfrom a graph category1 as unlabeled graph. It is then assigned with a type sampled from the top 20% most frequenttypes in the ontologies of DBPedia and Freebase. We create
20 templates to cover common entity types and generate
a total of 1K queries by instantiating the templates. The
generated queries were used for both subgraph queires anddual-simulation queries. We draw the matching function ffrom a library of similarity functions as in [29]. We then set
an integer k drawn from [10, 100].
Reachability queries. For reachability queries Q(s, t, d, G),
we set d ∈ [1, 4], and randomly select a pair of labels, fromthe top 20% most frequent labels in G. We sampled 4K
queries, 1K for each d.
We execute each of these queries 5 times and record theaverage execution time in milliseconds (ms) for each query.
Table 4 shows the average, minimum, and maximum runningtimes of the query classes for our datasets. As the tableshows, we have a mix of long and short running queries.
Algorithms. We implemented the following, all in Java.
(1) Standard query evaluation algorithms (Sec. 3), including: (a) STAR, the algorithm of [28] for top-k subgraphqueries, (b) dual-simulation [17], for dual-sim queries, and(c) a variant of Breath-First Search, for reachability queries.
(2) Query workload optimization algorithms, including (a)our workload optimization algorithm Opt RF, (b) Opt Rnd,a baseline algorithm that randomly selects a next query to
be executed in the workload, until the total response timereaches the time bound T , and (c) Opt True, a counterpartof Opt RF that uses the actual query response times to approximate the best solution.
Predictive models. We implemented all the methods (linear regression LR, regression tree RT, random forest RF,
k-nearest neighbors kNN [1] and SVM [23]) with scikit-learn
library [20], using their default settings.
1

graphclasses.org

Table 5: Accuracy of RF: alternative metrics
DatasetDBPedia

Freebase

Type
Reachability
Dual-Sim.
Top-k
Reachability
Dual-Sim.
Top-k

MAE (seconds)
0.163
0.800
0.271
0.177
0.111
0.130

NRMSE (%)
14.02
14.98
6.43
23.21
1.25
4.20

Metrics. We use three metrics as remarked in Section 2.2:
R-Squared, NRMSE, and MAE.
Test platform. We ran all of our experiments on a Linuxmachine powered by an Intel 2.30 GHz CPU with 64 GB
of memory. Each test is repeated 5 times and the averaged
results are reported.
Result overview. We summarize our findings below.
(1) Using the three classes of features and conventional regression models, the performance of analytical graph queries
can be predicted quite accurately (Exp-1).
(2) The predictors achieve high accuracy without using toolarge training query sets and very complex models (Exp-2).
(3) Our case study verifies the effectiveness of our approachfor the variety of query workload managements including
the single query class, the mixture of the queries, and profits
assignments (Exp-3).
We next introduce our findings in details.
Exp-1: Performance of predictive models. We firstevaluate the accuracy of predictive models LR, RT, and RF,
as well as kNN and SVM.
R-Squared Accuracy. To estimate the accuracy of the predictors, we randomly select 20% for validation and the remaining to train the predictor. We iterate the process for 5
times and the average results are reported.
We report the accuracy of LR, RT, and RF for the threequery classes, in Fig 4(a), Fig 4(b), and Fig 4(c), respectively. In all the cases, RF outperforms the alternatives. It
reaches an accuracy range between 0.86 and 0.99 (resp. 0.98
and 0.97) for dual-simulation (resp. subgraph queries) in
DBpedia and Freebase respectively. For reachability queries,
it achieves 0.90 accuracy over Freebase and 0.95 accuracy for
DBpedia. The higher accuracy of RF is due to its inherent
ensemble methods that lead to the generality and robustnessof the learned predictors [4]. The relatively lower accuracy of
LR is due to the non-linearity of the independent variables(i.e., feature values) with respect to the response variable(i.e., performance metric).
Further, we find the average accuracy of kNN (k = 2 from[2−4]) and SVM to be even lower: 0.72 and 0.48 respectively.
We thus omitted the results of kNN and SVM.
Alternative metrics. We report the average accuracy measured by the two alternative metrics MAE and NRMSE over
Freebase and DBpedia in Table 5. We find the following. (1)In all cases, MAE is less than 0.8 seconds, which indicates aquite accurate prediction, especially for our query workloadwith a large variance of response time (as verified in Exp-3).
Note that the accuracy of two different query types are notcomparable using MAE, as it is scale-dependent. (2) NRMSE
is in general small, especially for dual-simulation and top-kquerying. These verify that the prediction models are quite
robust to different metrics.

Table 4: Minimum, average, and maximum response time of the query samples
Min (ms)
5
1

Reacahbility
Avg (ms) Max (ms)592
12,553
655
6,308
1

LR
RT
RF

0.9
R-Squared

R-Squared

0.8

Dual-sim
Avg (ms)
16,82837,5530.7
0.6

Max (ms)
60,01560,046Subgraph queries
Min (ms) Avg (ms) Max (ms)
122
6,754
63,582284
5,816
51,138

1
LR
RT
RF

0.9
R-Squared

1
0.9

Min (ms)
8
19

0.8
0.7

100
LR
RT
RF

Quality (percentage)

DatasetDBPedia
Freebase

0.8
0.7

0.5
0.4
0.3
DBPedia80
70
60

RandomPred_RF

50
40

0.6

0.6

30

0.5

0.5

20
(1,1)

Freebase

DBPedia(a) Reachabilities Accuracy

90

Freebase(b) Dual-Sim. Accuracy

DBPedia

Freebase(c) Top-k Accuracy(10,10) (100,100) (1K,1K) (10K,10K)
Profit distribution: N(µ,σ)(d) Varying N(µ,σ)

Figure 4: Performance evaluation
1

60

0.9

50

0.8
R-Squared

Actual (seconds)

70

40
30

Table 6: Impact of feature type: Top-k (DBpedia)

0.7
0.6

Dual-Simulation
Top-k
Reachability

20

0.5

10

0.4

0
0

10

20

30

40

50

Predicted (seconds)

60

96

272

448

624

800

(a) Actual vs. Prediction(b) Training Size
Figure 5: Accuracy of predictions
Actual vs. predicted. The comparison between predicted
and actual execution times using RF for top-k querying over
DBpedia is shown in Fig 5(a) for 1K queries.
We also find that the training of RF is quite efficientand feasible over large workload. It takes less than 1 second to train RF models over a training workload of 800
queries. Using well-supported graph neighborhood and label indices [29], it takes on average 15.3 seconds to predictthe performance of a workload of 433 queries, with total
response time of 15 minutes.
Exp-2: Impact of factors. We next evaluate the impact
of model factors on the accuracy of the best model RF.
Varying # of training queries. Fixing the size of test set at200, we varied the number of training queries from 96 to
800, as shown in Fig 5 over DBpedia. The results tell us
the following. (1) As expected, for all the query classes,
RF gains a better accuracy over larger amount of training
queries. (2) Not many training queries are needed to achievea reasonable accuracy. For example, for the top-k querying,
the accuracy is already above 0.90 after 448 queries. The
results over Freebase (not shown) is consistent. In particular,
R2 is more than 0.85 for reachability after 272 queries and0.88 after 448 queries for top-k querying.
Feature types. To further investigate the importance of thethree type of features ((Q)uery, (S)ketch and (A)lgorithm),
we trained seven predictors, one for a combination of thefeature type for top-k queries over DBpedia. Table 6 summarizes the results. The results show the following. (1)Corresponding to the relative importance of the features inTable 1, for top-k, the query-only (resps. sketch) features
perform poorly and the addition of those two does not add
much to the accuracy of the results. (2) Algorithm-only fea-

Feature types
Q
S
A
Q+S
Q+A
S+A
Q+S+A

R-Squared
0.268
0.329
0.925
0.375
0.942
0.930
0.985

tures perform reasonably—they raise the accuracy to 0.925.
(3) The best accuracy (0.985) is obtained by combining all
three categories of features.
Varying # of trees. We evaluated the impact of the numberof estimators in RF, by varying the number of trees in RFfrom 1 to 100. As expected, by increasing the number of
estimators until a saturated point, we observed better accuracy. In our experiments, no better performance is observed
after 10 trees. Therefore, we fix the number of estimators
to 10 for all of other experiments.
Exp-3: Query workload optimization. We next conduct case studies to test the effectiveness of GQPP for query
workload optimization.P To this end, we quantify the effecpi

tiveness of Opt RF as P Q0i ∈W0 p0 , where W (resp. W’) refers
Q ∈W
i

i

to the selected queries of Opt RF (resp. Opt True). It measures the ratio of the total profits gained by Opt RF to thetotal profits obtained by Opt True, under time bound T .
The effectiveness of Opt Rnd is similarly defined.
We simulate workloads as follows. (1) We generate a workload of 6K queries, using a distribution 16%, 16%, and 68%
for top-k subgraph, dual-sim and reachability queries, respectively. (2) We use absolute values of normal distribution |N (µ, σ)| with (µ, σ) = (1, 1) to generate profit of thequeries. (3) The weighted queries are sent to each optimizer in batch. Given a bounded time, the optimizer selects
queries to be executed.
Effectiveness of Opt RF. We report the effectiveness of
Opt RF for the three reachability, dual-simulation, and topk querying in Table 7, where the time bound is set to 15 and30 minutes, respectively.
We observed the following. (1) In all experiments, thebaseline algorithm Opt Rnd fails to reach an effectivenesscomparable to Opt RF. (2) In average, Opt RF outperforms
Opt Rnd by 5.1 for dual-simulation, by 2.75 for top-k query-Table 7: Effectiveness of Opt RF and Opt Rnd
DatasetType
Reachability

DBPedia

Dual-sim.
Top-k
Reachability

Freebase

Dual-sim
Top-k

T (min)
15
30
15
30
15
30
15
30
15
30
15
30

Opt Rnd (%)
31.18
43.72
19.61
28.95
23.32
35.46
39.17
53.89
7.57
13.24
33.75
46.65

Opt RF (%)
91.25
95.76
84.33
89.32
97.98
98.48
92.91
95.49
89.72
91.03
93.37
93.79

ing, and by 2.23 for reachabilty. (3) Over both boundedtimes, Opt RF only lost 4.09%, 6.14%, and 11.4% of the
Opt True profits for top-k querying, reachabilities, and dualsimulation respectively.
The source of Opt RF error in compared with Opt True is
two-fold: (1) inference time of GQPP, and (2) the accuracyof prediction time. In the first sets of experiments, we haveshown the inference time is negligible and the accuracy of
prediction is high. Note that since knapsack problem is NPComplete [24], both Opt True and Opt RF, using nearly thesame amount of time, find an approximate solution.
Distribution of profits. We also evaluated the impact of
profit distribution by varying µ and σ. Fixing the timebound to 15 minutes and a uniform mixture of query types,
we varied N (µ, σ) from (1, 1) to (10K, 10K). Fig 4(d) tells usthat Opt RF remains to be effective, and is insensitive to thechange of profits distribution. This verifies the robustnessof the optimization strategy in terms of profit distribution.
Mixed query workload. We also evaluated the effectivenessof Opt RF in the mixed workload. Fixing the time boundto 15 minutes, we created three sets of query workload over
DBpedia, where each set is dominated by one query class.
We report the effectiveness below.
Distribution
Opt Rnd (%) Opt RF (%)(70%,15%,15%)
23.93
95.60
(15%,70%,15%)
16.07
92.66
(15%,15%,70%)
23.12
95.59
As shown in the table, (1) The effectiveness of Opt RF remains to be insensitive to the distribution of query classes;(2) When dual-simulation are dominant, we observe aslightly lower quality that is related to its lower predictor’saccuracy. Moreover, we observe that dual-simulation takes
more time than other query classes on average. Hence theimpact of QPP predictor to the workload optimization becomes larger when it makes “mistakes”.

6.

RELATED WORK

Query performance prediction has been studied to estimate resource cost and effectiveness of query workloads [13].
We discuss some of this work below.
Relational queries. Learning techniques for QPP havebeen applied in relational databases for SQL workloads. The
goal is to predict the response time and resource consumption of SQL queries leveraging: (1) calibrated cost models
by analyzing a set of queries in offline, and adaptively refining the model units [26]; and (2) statistical machine-learning
predictors constructed from several categories of features including plan-level [14], operator-level (e.g., response time ofoperators in a parser tree), or both features [2]. The framework in [14] focused on learning to estimate CPU time andI/O costs of SQL query plans. In [9], a variation of Principal
Components Analysis (PCA) used to predict the responsetime and other run-time characteristics of database requests.
In [2], the authors advocated the use of support vector machines (SVM) as the specific machine-learning model. They
further proposed a different approach by first building individual predictive models for each physical operator and then
combining their predictions.
XML and SPARQL queries. QPP has been studied
for querying semi-structured data, such as XML [30] andSPARQL [12]. Features are collected from XML parser trees,
query plans, and topological of XML queries (e.g., numberof paths) to predict the response time of XML queries withregression models. Similarly, regression and Support Vector
Machine are used to predict the performance of SPARQL
queries, where the features are collected from SPARQL algebra and pattern [12]. In contrast to XML and SPARQL
queries, graph analytical queries are not well supported byalgebra and apriori query plans. These methods are notapplicable to approximate graph querying scenarios.
Our work differs from previous work in several ways. (1)We study QPP for graph analytical queries, without assuming the existence of rigid syntax; (2) We exploit computationally efficient features that are collected by query input, run-time sketches and algorithms, which do not assume
apriori query plans. Our experimental results over (mixed)
graph analytical workloads verified the effectiveness of predictors, and suggests feasible QPP tools for online analytics.

7.

CONCLUSION

We have presented a learning framework to predict response times of graph queries. We introduced learning methods for both graph pattern queries, defined by subgraphisomorphism and dual-simulation, and reachability queries.
We show that by exploiting computationally efficient features from queries, sketches of the data to be accessed,
and algorithm performance, the response times can be accurately predicted using regression models. We also introduced
a workload optimization strategy for selecting the queries
to be executed under bounded resources while maximizing
profit. Our experimental study over real-world knowledge
bases verifies the effectiveness of the learned predictors aswell as the workload optimization strategy.
The study of QPP for complex graph analytical queries
is in its infancy. We are testing our learning framework formore query classes that support graph mining and learning
operators and algorithms. We plan to exploit features fromquery logs and user-feedback, for more performance metrics,
including relevance, accuracy and the quality of the answers.
Another interesting topic is to develop online machine learning techniques to support ad-hoc, self-tuning prediction overevolving query workload.

8.

ACKNOWLEDGMENTS

Namaki and Wu are supported in part by NSF IIS1633629 and Google Faculty Research Award. Sasani andGebremedhin are supported in part by NSF CAREER award
IIS-1553528.

9.

REFERENCES[1] D. W. Aha, D. Kibler, and M. K. Albert.
Instance-based learning algorithms. Machine learning,
pages 37–66, 1991.
[2] M. Akdere, U. Çetintemel, M. Riondato, E. Upfal, andS. B. Zdonik. Learning-based query performancemodeling and prediction. In ICDE, 2012.
[3] M. Arias, J. D. Fernndez, M. A. Martnez-Prieto, andP. de la Fuente. An empirical study of real-world
sparql queries. 2011.
[4] L. Breiman. Random forests. Machine learning, pages
5–32, 2001.
[5] L. Breiman, J. Friedman, C. J. Stone, and R. A.
Olshen. Classification and regression trees. 1984.
[6] J. Duggan, U. Cetintemel, O. Papaemmanouil, and
E. Upfal. Performance prediction for concurrent
database workloads. In SIGMOD, 2011.
[7] R. Fagin, A. Lotem, and M. Naor. Optimal
aggregation algorithms for middleware. Journal ofcomputer and system sciences, 66(4):614–656, 2003.
[8] W. Fan, X. Wang, and Y. Wu. Querying big graphs
within bounded resources. In SIGMOD, 2014.
[9] A. Ganapathi, H. Kuno, U. Dayal, J. L. Wiener,
A. Fox, M. Jordan, and D. Patterson. Predicting
multiple metrics for queries: Better decisions enabled
by machine learning. In ICDM, 2009.
[10] Q. Guo, R. W. White, S. T. Dumais, J. Wang, and
B. Anderson. Predicting query performance using
query, result, and user interaction features. In
Adaptivity, Personalization and Fusion of
Heterogeneous Information, 2010.
[11] C. Gupta, A. Mehta, and U. Dayal. Pqr: Predicting
query execution times for autonomous workload
management. In Autonomic Computing, 2008.
ICAC’08. International Conference on, 2008.
[12] R. Hasan and F. Gandon. A machine learning
approach to sparql query performance prediction. In
WI-IAT, 2014.
[13] C. Hauff, D. Kelly, and L. Azzopardi. A comparison ofuser and system query performance predictions. In
CIKM, 2010.
[14] J. Li, A. C. König, V. Narasayya, and S. Chaudhuri.
Robust estimation of resource consumption for sql
queries using statistical techniques. Proc. VLDB
Endow., pages 1555–1566, 2012.
[15] G. Louppe, L. Wehenkel, A. Sutera, and P. Geurts.
Understanding variable importances in forests ofrandomized trees. In NIPS, pages 431–439, 2013.
[16] J. Lu, C. Lin, W. Wang, C. Li, and H. Wang. String
similarity measures and joins with synonyms. In
SIGMOD, 2013.
[17] S. Ma, Y. Cao, W. Fan, J. Huai, and T. Wo.
Capturing topology in graph pattern matching.
VLDB, pages 310–321, 2011.
[18] M. Morsey, J. Lehmann, S. Auer, and A.-C.
Ngonga Ngomo. DBpedia SPARQL Benchmark –Performance Assessment with Real Queries on RealData, pages 454–469. 2011.
[19] M. H. Namaki, R. R. Chowdhury, M. R. Islam, J. R.
Doppa, and Y. Wu. Learning to speed up query
planning in graph databases. In ICAPS, 2017.

[20] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel,
B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer,
R. Weiss, V. Dubourg, J. Vanderplas, A. Passos,
D. Cournapeau, M. Brucher, M. Perrot, and
E. Duchesnay. Scikit-learn: Machine learning in
Python. JMLR, pages 2825–2830, 2011.
[21] H. Qu and A. Labrinidis. Preference-aware query andupdate scheduling in web-databases. In ICDE, pages
356–365, 2007.
[22] G. Seni and J. F. Elder. Ensemble methods in data
mining: improving accuracy through combining
predictions. Synthesis Lectures on Data Mining andKnowledge Discovery, pages 1–126, 2010.
[23] S. K. Shevade, S. S. Keerthi, C. Bhattacharyya, andK. R. K. Murthy. Improvements to the smo algorithm
for svm regression. TNNLS, pages 1188–1193, 2000.
[24] V. V. Vazirani. Approximation algorithms. Springer
Science & Business Media, 2013.
[25] P. F. Velleman and D. C. Hoaglin. Applications,basics, and computing of exploratory data analysis.
1981.
[26] W. Wu, Y. Chi, S. Zhu, J. Tatemura, H. Hacigümüs,
and J. F. Naughton. Predicting query execution time:
Are optimizer cost models really unusable? In ICDE,
pages 1081–1092, 2013.
[27] K. Yang, J. Li, and C. Wang. Missing values
estimation in microarray data with partial leastsquares regression. In ICCS, pages 662–669, 2006.
[28] S. Yang, F. Han, Y. Wu, and X. Yan. Fast top-k
search in knowledge graphs. 2016.
[29] S. Yang, Y. Wu, H. Sun, and X. Yan. Schemaless andstructureless graph querying. VLDB, 2014.
[30] N. Zhang, P. J. Haas, V. Josifovski, G. M. Lohman,
and C. Zhang. Statistical learning techniques forcosting xml queries. In VLDB, pages 289–300, 2005.