A Survey on Efficient Subgraph Enumeration over Distributed Graphs

PhD Qualifying Examination


Title: "A Survey on Efficient Subgraph Enumeration over Distributed
Graphs"

by

Mr. Xun JIAN


Abstract:

Subgraph enumeration is a fundamental problem in graph theory. Given two 
graphs d and p, subgraph enumeration is to enumerate all subgraphs of the 
data graph d, which are isomorphic to the pattern graph p. It has a wide 
range of applications in sociology, chemistry, telecommunication, 
bioinformatics and networks. For example, a user may be interested in 
searching a special structure in social networks, to identify groups of 
people that may share certain properties. In a router network, finding 
specific structures can help detect nodes that play an important role in 
the communication. Moreover, querying patterns in a knowledge graph is 
essentially enumerating subgraphs with property constraints. Although 
subgraph enumeration has been applied in different areas in practice, the 
problem itself is computationally-hard. The underlying problem, called 
subgraph isomorphism, is known to be NP-complete. Also, the number of 
results of subgraph enumeration can be exponentially large, making the 
computation as well as the storage become even more challenging. The 
survey starts with an introduction to the concept and background of 
subgraph isomorphism and subgraph enumeration. Existing works are then 
described analyzed, based on the computation model and searching strategy. 
Different computation models and optimization strategies are also compared 
in different cases. Finally, it ends up with a discussion about the 
challenges and future research opportunities of subgraph enumeration.


Date:			Tuesday, 26 June 2018

Time:                  	1:00pm - 3:00pm

Venue:                  Room 5560
                         Lifts 27/28

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Dimitris Papadias (Chairperson)
 			Dr. Yangqiu Song
 			Dr. Ke Yi


**** ALL are Welcome ****