Harnessing Graph Changes in Complex Graph Queries

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Harnessing Graph Changes in Complex Graph Queries"

By

Mr. Xun JIAN


Abstract

In many real-world applications, the underlying data can be modeled as graphs. 
Querying graph data involves four main building blocks: the query semantics, 
the query parameters, the underlying graph data, and the output. When handling 
graph queries, changes can be made on the input parameters, the input graph, or 
the output. For example, modern graphs are dynamically changing, and bring 
challenges to the efficiency of querying algorithms. Also, query rewriting 
techniques are developed to modify query parameters, so that the output matches 
the user’s intent.

In this thesis, we study how to handle and utilize such changes in order to 
improve the efficiency and effectiveness of three complex graph queries. 
Specifically, we first study the problem of community search on dynamic 
heterogeneous information networks (HINs), where the input graph is dynamically 
changing, and an efficient algorithm should be able to quickly update the 
output after the graph changes. Then we consider the problem of SPARQL query 
rewriting, in which one is allowed to modify the input SPARQL query, which is a 
kind of query parameters, so that the actual output is close to the user's 
intention. Finally, we study the problem of publishing graphs under node 
differential privacy, where one should randomly modify the output graph, so the 
information of any single node cannot be inferred from the output graph with 
high confidence.


Date:			Wednesday, 24 February 2021

Time:			9:00am - 11:00am

Zoom Meeting:
https://hkust.zoom.us/j/98507326327?pwd=ZGhtMC9ITnFRZFprT2l2MzNDRzBKZz09

Chairperson:		Prof. Daniel PALOMAR (ECE)

Committee Members:	Prof. Lei CHEN (Supervisor)
 			Prof. Qiong LUO
 			Prof. Ke YI
 			Prof. Can YANG (MATH)
 			Prof. Jian PEI (Simon Fraser University)


**** ALL are Welcome ****