Research On Graph Classification Methods Based On Graph Substructures

Graph data is one of the most dominant components of the Big Data.Unlike structured data,graph data is naturally unstructured,non-euclidean,and of variable size.This makes it difficult to apply traditional neural network methods for structured data to graph data directly,so the research of neural networks applicable to graphs has become an important research direction in the information field in recent years.Among them,graph classification,as the most fundamental graph neural network research topic,has received extensive attention.One part of related research designs graph kernel functions for denoising and cropping elements in graphs manually,and then completes graph classification by statistical,template matching or neural network methods;another part constructs a differential graph convolutional model GCN,which is combined with graph pooling techniques to refine the graph representation and realize graph classification.Although the above studies show feasibility and application value,there are still some problems that need to be solved.For example,the design of most graph kernel functions requires a large amount of expert experiences,and leads to the destruction of the original graph topology because it will limit the scale of graph substructure extraction.The special substructure and process randomness of some graph kernel extractions make it difficult to adapt to structured neural networks.Graph convolution networks focus on the graph nodes’ own and first-order neighboring substructures,while ignoring important information in higher-order neighbors.And the node feature generalization problem of deep graph convolution degrades the overall model performance.Starting from the above problems and different graph substructures,this thesis studies the graph neural network classification models based on graph rooted subtrees and graph multi-level cluster structures,and proposes corresponding solutions.The main work is as follows:(1)This thesis proposes a graph classification model,RSRNN,based on rooted subtree extraction and Tree-LSTM.It achieves rooted subtree extraction by selecting candidate nodes and expanding rooted subtrees,and learns TreeLSTM on rooted subtrees to obtain graph representations.The rooted subtree design is simple and preserves the topology of graphs;to make this model fit better to arbitrary rooted subtree structures and to generalize to more general graphs,the Tree-LSTM is improved to contain a branching attention mechanism in this thesis.(2)This thesis proposes a multi-level cluster structure-based graph convolutional network and adaptive attention pooling model,MCSPool.By deeply studying and discussing the limitations of graph convolutional networks,this thesis starts from the perspective of graph multi-level cluster structure and proposes a cluster convolutional layer,which alleviates the node feature generalization caused by deepening GCN;summarizes the existing graph pooling layer in the form of multi-level cluster and proposes a recursion-based adaptive attention pooling layer to make learning parameter process automated and fine-grained.In summary,graph classification methods based on graph substructure proposed in this thesis have theoretical research significance.The experiments’results show that each model improves the average classification accuracy on open datasets,which is competitive and has practical value compared with other baseline models.