Similarity Search On Supergraph Containment Algorithm Based On Graph Neural Network

With the advent of the information explosion era,human beings are being exposed to an exponentially increasing amount of information.In order to make the best use of it,both the industry and academia attach great importance to the theoretical research and practical applications related to graph structures.Graph structures abstract things and the relationships between them into vertices and edges.It is helpful for people to find valuable information that can benefit human society.Among the many graph-related problems,the problem of graph query processing has always been a hot issue,and supergraph search is a fundamental graph query processing problem.Supergraph search aims to find all data graphs contained in a given query graph by performing supergraph matching based on subgraph isomorphism.Supergraph search is used in a wide range of fields.For example,researchers can determine the known structures of proteins inside an unknown protein by using supergraph search to infer the properties possessed by that protein,and predict how it may interact with other proteins.However,these application scenarios require a rapid search of huge amounts of data.Therefore,the efficiency and scalability of the model are important.This thesis focuses on how to implement the supergraph search efficiently and accurately.More specifically,as this problem is NP-complete,conventional methods are not able to solve the problem efficiently.An ideal solution to the problem is to use machine learning models and achieve approximate solutions.Among the many machine learning algorithms designed for graph structures,graph neural networks are one of the most popular and effective models.Graph neural networks can offer more possibilities for solving the supergraph search problem.This thesis proposes the first learning-based method for similarity search on supergraph containment,named Neural Supergraph similarity Search(NSS).With the help of graph neural networks,NSS can learn the representations for query and data graphs and then efficiently conduct the supergraph search on the representation space.NSS’s complexity is linear to the number of data graphs.The carefully designed Wasserstein discriminator and reconstruction network enable NSS to better capture the interrelation,structural and label information between and within query and data graphs.In order to better evaluate the advancement of NSS,this thesis will compare NSS with other algorithms in terms of both accuracy and efficiency.Experiments demonstrate that NSS is up to 6 orders of magnitude faster than the state-of-the-art exact supergraph search algorithm in terms of query processing and more accurate compared to the other learningbased solutions.In addition,NSS has good robustness to perform supergraph searches on datasets of different sizes or directed graphs.At the same time,the scalability of NSS is excellent,and the model can be applicable to large graphs of millions.