Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - GRACE (Resource Bounded Graph Query Answering)

Teaser

Graphs are a ubiquitous model to represent objects and their relations, such as social networks, transportation networks, telecommunication networks, the World Wide Web, biological networks, transportation systems, epidemic networks, chemical networks, knowledge bases, and...

Summary

Graphs are a ubiquitous model to represent objects and their relations, such as social networks, transportation networks, telecommunication networks, the World Wide Web, biological networks, transportation systems, epidemic networks, chemical networks, knowledge bases, and hidden terrorist networks . The need for querying big graphs is evident in social media marketing, knowledge discovery, route planning, mobile network analysis, computer vision, the study of adolescent drug use, and intelligence analysis for identifying terrorist organizations, among other things.

Querying big graphs has introduced a number of challenges, from fundamental problems to practical techniques. It demands a departure from the traditional query evaluation paradigm. Vital to any systems for querying big graphs are a number of technical questions. What graph patterns should we support to query big graphs? How can we identify associations of entities in real-life graphs? What queries are BD-tractable, i.e., “tractable” on big graphs? What queries are parallel scalable, i.e., guarantee to reduce running time when more resources (processors) are used? How can we make queries BD-tractable? What parallel model should we use to query big graphs? When exact query answers are beyond reach in big graphs under constrained resources, can we compute approximate answers with accuracy guarantees? Is it possible to support all these techniques in a query system? What emerging applications can the system help? Can we extend the techniques to big relations, beyond graph queries?

In response to the challenges, this project aims to extend the conventional query paradigm, establish methodological and algorithmic foundations, and provide effective resource-constrained techniques for efficiently querying big real-life graphs and relations.

Work performed

The ERC project has been fruitful in the past 30 months. We have (1) made encouraging progress
on all of its 6 work packages (WPs), (2) published 26 papers in international database conferences and
journals, all refereed, including 7 invited papers; (3) received three awards: (a) the Best Paper Award
for SIGMOD 2017, the premier international database systems conference; (b) the Best Demo Award
for VLDB 2017, the leading international all-round database conference; and (c) 2017 ACM SIGMOD
Research Highlight Award; and (4) developed two functional prototype systems as proof of concept; both
systems have been evaluated in industry and have proven effective.


We have made progress on each and every of its six work packages (WPs), summarized as follows
please see detailed report).

1. WP1: (1) a language for graph pattern queries that supports first-order logic and counting quantifiers [21],
(2) an extension of association rules from relations to graphs [20], (3) dependency languages for specifying
the semantics of graph-structured data, extending classical functional dependencies and keys from relations
for graphs [11, 17, 22]; and (4) an extension of graph functional dependencies [22] by supporting built-in
comparison predicates and linear arithmetic expressions [16], to catch numeric inconsistencies in graph-structured data.

2. WP2: (1) a theory of bounded evaluation for achieving BD-tractability [1, 3, 4]; (2) two characterizations
of the effectiveness of incremental graph computations [14], to make big graphs small, (3) several
parallel scalable algorithms for big graph analytics [11, 20, 21, 22, 16]; (4) axiom systems and complexity
bounds for analyzing graph dependencies [16, 17]; and (5) parallel algorithms for discovering and
reasoning about graph functional dependencies [13, 15], for optimizing graph queries, among others.

3. WP3: (1) an effective syntax of relational algebra as a principled approach toward bounded evaluability [1],
(2) techniques for bounded query evaluation using views, for both big relations [3, 4] and
graphs [19], and (3) a new programming model for parallel graph computations [10, 23, 25], and (4) a
new parallel model for querying big graphs [18], which subsumes the state-of-the-art synchronous (e.g.,
BSP) and asynchronous parallel models (e.g., ASP) as special cases.

4. WP4: a new data-driven approximation schema for querying big relations with bounded resources, the
first one that guarantees a deterministic accuracy bound for unpredictable SQL queries [2].

5. WP5: (1) GRAPE, a functional prototype system for querying graphs [24] based on the programming
model and parallel model of WP3; and applications of querying big graphs in (2) social media marketing [20, 21],
(3) knowledge base enrichment [11], (4) inconsistency and spam detection [16, 22], and
(5) virtual network mapping [5].


6. WP6: (1) BEAS, a functional prototype system for querying big relations [6, 7] based on the bounded
evaluation theory of WP2, and (2) techniques for improving the quality of big relations [8, 26].

The project has generated 26 publications so far, among which 20 are in top-ranked journals or major
international database conferences, 7 are invited papers, and 3 received awards, the premier international
database systems conference.

We list the publications below, all refereed

• Thirteen journal publications [2, 4, 5, 7, 8, 9, 10, 11, 12, 19, 20, 23, 26], including 2 in TODS [4, 8], 2 in
TKDE [19, 26], and 3 in PVLDB [2, 11, 20]. Among these 7 are invited papers [4, 5, 7, 9, 10, 12, 19].

• Thirteen papers in the proceedings of major international database theory and system conferences,
including 9 papers in SIGMOD [1, 6, 13, 14, 16, 18, 21, 22, 25] (8 research papers and 1 demo), 2 in
PODS [3, 17], 1 in ICDE [15], and 1 VLDB demo [24].

• In particular, the output from the project has received three awards: the Best Paper Award for SIG-
MOD 2017, the premier international database systems co

Final results

We have proposed a new parallel model for graph computations [25]. It allows one to plug in existing sequential graph algorithms and automatically parallelizes the computation, without recasting the algorithms into a new model. This makes parallel graph computations accessible to a large group of users. Moreover, it guarantees convergence at correct answers as long as the sequential algorithms plugged in are correct. The work received the Best Paper Award for SIGMOD 2017, the premier international database systems conference.

As a proof of concept, we have developed GRAPE, a parallel GRAPh Engine for graph computations, based on our programming and parallel models developed in [25]. A preliminary implementation of GRAPE was demonstrated at VLDB 2017 [24], a leading all-round international database conference, and received the Best Demo Award, given by a committee consisting of mostly industry people.

The work was selected to receive 2017 ACM SIGMOD Research Highlight Award.

In addition, BEAS [6], another our prototype system we have developed for querying big relations, has been deployed and evaluated at Huawei Technologies, the largest telecommunications equipment and services provider in the world. It has been verified that our bounded evaluation techniques improve the performance of Huaweis query engines by orders of magnitude. As a consequence, Huawei has invested in a joint research lab at Edinburgh, at the level exceeding 1M euro per annum. This is the first research lab funded by Huawei that is dedicated to open research. See
https://www.ed.ac.uk/news/2017/huawei-deal-to-advance-expertise-in-data-science

Website & more info

More info: http://homepages.inf.ed.ac.uk/wenfei/GRACE.html.