Towards Subgraph Isomorphisms with Representation Learning

PhD Thesis Proposal Defence


Title: "Towards Subgraph Isomorphisms with Representation Learning"

by

Mr. Xin LIU


Abstract:

Graphs are one of the general data structures to model the world, with subgraph 
matching being a fundamental and critical problem. In graph theory, subgraph 
matching is equivalent to identifying subgraph isomorphisms between two graphs. 
The decision problem of determining the existence of a subgraph isomorphism for 
a given graph pair is known to be NP-complete, as is the counting problem of 
establishing the total number of subgraph isomorphisms. A more challenging 
matching task involves locating all subgraphs and their corresponding mappings. 
Numerous enumeration and approximation algorithms have been developed for 
subgraph isomorphisms, but their generality and scalability remain constrained 
by computational complexity or memory usage. To overcome these issues, we 
explore various graph representation techniques. We highlight the constraints 
of current graph kernels for subgraph isomorphism counting and suggest 
modifications to enhance performance. To improve the generalization 
capabilities of representations, we introduce a deep learning framework that 
augments various neural representation learning architectures to simulate 
searching and pruning for subgraph isomorphism counting and matching. We show 
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 awareness of the global graph 
structure and strengthens the transfer capability through pretraining on 
synthetic data. We also conduct a theoretical analysis of the shortcomings of 
existing message-passing graph neural networks when dealing with heterogeneous 
multi-graphs. By examining the connection between the edge-to-vertex transform 
and the duality of isomorphisms in heterogeneous multi-graphs, we propose an 
advanced dual message-passing mechanism for learning edge representations, 
which leads to comprehensive graph representations. We also demonstrate that a 
simple dummy node connecting all existing vertices can preserve the graph 
information without loss during transformation and learning. Experimental 
results indicate that our proposed neural framework and algorithms offer a 
promising alternative for subgraph isomorphism problems, particularly in 
large-scale graphs and patterns.


Date:			Thursday, 13 April 2023

Time:                  	9:00am - 11:00am

Venue:			Room 5501
  			lifts 25/26

Committee Members:	Dr. Yangqiu Song (Supervisor)
 			Dr. Dan Xu (Chairperson)
 			Prof. Raymond Wong
 			Prof. Dit-Yan Yeung


**** ALL are Welcome ****