Theory and Practice: Graph Representation Learning For Subgraph Isomorphisms And Substructure-Augmented Applications

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


PhD Thesis Defence


Title: "Theory and Practice: Graph Representation Learning For Subgraph
Isomorphisms And Substructure-Augmented Applications"

By

Mr. Xin LIU


Abstract:

Graphs are one of the most widely used data structures to model various 
domains, with subgraph matching being a fundamental and critical demand. In 
graph theory, subgraph matching involves identifying subgraph isomorphisms 
between two graphs, whose decision problem of existence and counting is known 
to be NP-complete. A more challenging task is to locate all isomorphic 
subgraphs and their corresponding mappings. Numerous enumeration and 
approximation algorithms have been developed for subgraph isomorphisms, but 
their generality and scalability are limited by computational complexity or 
memory usage. To overcome these issues, we explore different graph 
representation techniques from the perspective of learning. We highlight the 
constraints of current graph kernels for subgraph isomorphism counting and 
suggest modifications to enhance performance. To improve the generalization 
capabilities of graph representations, we introduce a deep learning framework 
that integrates various neural representation learning architectures to 
simulate searching and pruning for subgraph isomorphism counting and matching. 
We demonstrate that graph neural networks consistently outperform sequence 
models, with the sum pooling operation playing a significant role. Moreover, 
we develop an efficient dynamic memory network that improves the perception of 
the global graph structure and strengthens the transfer capability through 
pretraining on synthetic data. Additionally, we successfully apply the ideas 
of neural subgraph matching to anonymous recommendation systems: we extract 
frequent attribute patterns from transition graphs and utilize them to enhance 
the user intent capture, attribute preference estimation, and long-period 
recommendation. We also conduct a theoretical analysis of the shortcomings of 
existing message passing graph neural networks when dealing with heterogeneous 
multigraphs. By examining the connection between the edge-to-vertex transform 
and the duality of isomorphisms in heterogeneous multigraphs, we propose an 
advanced dual message passing mechanism for learning edge representations, 
leading to comprehensive graph representations for subgraph matching and 
unsupervised node classification. We also show that incorporating a simple 
dummy node that connects all existing vertices allows for the preservation of 
graph information without loss during transformation and learning. These 
structures directly boost the performance of subgraph matching and graph 
classification, and the dual graph can further improve the measurement of 
substructure similarity. Extensive experimental results highlight the 
potential of our proposed neural framework and algorithms in addressing 
subgraph isomorphism problems, particularly in large-scale graphs and 
patterns. And applying them to downstream tasks for enhancing the awareness of 
substructures can yield direct performance benefits.


Date:                   Thursday, 29 June 2023

Time:                   4:00pm - 6:00pm

Venue:                  Room 4475
                        lifts 25/26

Chairperson:            Prof. Qing CHEN (MAE)

Committee Members:      Prof. Yangqiu SONG (Supervisor)
                        Prof. Raymond WONG
                        Prof. Dan XU
                        Prof. Can YANG (MATH)
                        Prof. Sinno Jialin PAN (CUHK)