Querying Neural Graph Database

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


PhD Thesis Defence


Title: "Querying Neural Graph Database"

By

Mr. Zihao WANG


Abstract:

Neural Graph Databases (NGDBs) augment classic graph databases with neural 
representations that embed features and relations. This integration also 
introduces new and complex challenges in handling logical queries. The 
logical calculus required to answer queries is not readily found in 
continuous spaces, making querying such NGDBs a highly intricate and 
non-trivial task. An important example of a neural graph database is a 
knowledge graph with relational and entity representations, which is our key 
research object.

The first part of this thesis discusses learning approaches for tree-formed 
queries. For such queries, the logical queries are solved by set operators 
over geometric embedding spaces of a fixed dimension, where only constant 
data complexity is required. We introduce a large-scale query-answering 
framework, demonstrating the challenge of generalizing such approaches in the 
combinatorial spaces of logical queries due to the conflict between rigorous 
logical reasoning and geometric embeddings. To overcome this, we first 
understand the truth value matrix between queries and all entities from a 
matrix-decomposition perspective. We then show that fuzzy logical t-norm 
operations can be integrated into the embeddings under specific conditions. 
This leads to the development of a new metric space inspired by unbalanced 
optimal transport for more combinatorially generalizable query answering and 
its computation with convolution operations.

In the second part of the thesis, we take one step back from the Tree Form 
(TF) queries and turn to Existential First Order (EFO) queries. We present 
syntactical and complexity gaps between the TF and EFO queries, which 
motivate further research in learning methods beyond tree-formed queries. 
With an abstract interface of link predictors, the query-answering process of 
EFO queries can be regarded as an optimization process but requires at least 
linear data complexity. We then propose a learning-to-optimization framework 
to answer such queries. Compared to direct global optimization, we introduce 
four types of one-hop inference of a single predicate whose results are 
combined by a graph neural network for a global solution. Notably, we derive 
closed- form formulations of the one-hop inferences for six widely used KG 
embeddings, further facilitating the inference process.


Date:                   Friday, 7 February 2025

Time:                   10:00am - 12:00noon

Venue:                  Room 4472
                        Lifts 25/26

Chairman:               Dr. Yiwen WANG (ECE)

Committee Members:      Dr. Yangqiu SONG (Supervisor)
                        Dr. Wei WANG
                        Prof. Xiaofang ZHOU
                        Dr. Dong XIA (MATH)
                        Prof. Sinno Jialin PAN (CUHK)