Graph Convolutional Networks For Node Classification Tasks On Heterophilic Graphs

As a data structure,graphs widely exist in the data organization forms in real life,such as social graphs,molecular structure graphs,paper reference graphs,computer networks,knowledge graphs,etc.Different from Euclidean Data such as image,voice and text,graph-structured data is a kind of Non-Euclidean Data.How to model neural networks on graph-structured data to extract information for machine learning tasks is a research hotspot in recent years.Traditional graph convolutional networks have made important progress in machine learning of graph-structured data.The model design of graph convolutional networks is based on the homophily assumption,that is,the connected nodes in the graph have a high probability of belonging to the same category or having similar features.Traditional graph convolutional networks adopt the message passing mechanism,that is,the connected nodes propagate features as information to each other,which makes the features of connected nodes tend to be similar and easier to be divided into the same category.This design pattern makes graph convolution networks achieve very good results in learning tasks on homophilic graphs,especially node classification tasks.However,there are many heterophilic graphs in the real world,that is,the connected nodes are more likely to belong to different categories.The learning task of traditional graph convolutional networks on heterophilic graphs,especially the node classification task,is not ideal.How to design graph neural networks to achieve good performance on both homophilic graphs and heterophilic graphs is a problem that is still being explored.According to the different ways of using graph structure information,graph convolutional networks can be divided into spatial graph convolutional networks and spectral graph convolutional networks.In view of the poor performance of graph convolution networks on heterophilic graphs,it can also be analyzed from the perspective of spatial domain and spectral domain respectively.Therefore,both spatial graph convolutional networks and spectral graph convolutional networks are currently trying to solve this problem.In the related work of spatial neural networks,an important idea is to design a more reasonable message passing mechanism,especially to propagate signed information.However,the existing work does not explicitly distinguish the impact of the homophily and heterophily degree between node pairs on the classification results,but only uses an implicit way.How to explicitly model the homophily and heterophily degree between node pairs and use them to guide the propagation of messages is a problem worth studying.From the spectral domain perspective,traditional graph convolutional networks actually act as low-pass filters,filtering out high-pass signals and retaining low-pass signals.High-pass signal is more important for heterophilic graphs,so the work related to spectral graph convolutional networks mainly attempts to design a learnable graph filter,so that it can adaptively adjust the graph filter according to the graph structure data.However,the existing work mainly focuses on designing only one learnable filter in the graph convolutional networks.In the field of anomaly detection,there is existing work that uses two filters to learn low-frequency and high-frequency signals respectively.Whether multiple filters can be designed to play different roles in node classification tasks is also a problem worth studying.This thesis focuses on graph convolutional networks for node classification tasks on heterophilic graph,and two new graph convolutional networks oriented toward node classification tasks are designed from the perspective of spatial domain and spectral domain respectively.The main contributions are as follows:·Graph Convolutional Networks Guided by Explicitly-Estimated Homophily and Heterophily Degree This model designs and uses an improved message passing mechanism,which uses the estimated homophily and heterophily degree of node-pair to adaptively guide the passing of message.This mechanism can make the representation learned by nodes belonging to different categories in homophilic and heterophilic graphs easier to be distinguished.At the same time,in order to estimate the homophily and heterophily degree accurately,the model uses Deepwalk to extract the graph structure information to pre-train the estimator,and combines the estimator pre-trained by the original node attribute information to estimate.The validity of the model was demonstrated by comparative experiments and ablation experiments.·Graph Convolution Networks with Joint Multiple Filters This model is based on the learnable polynomial filters for node classification tasks,which uses multiple graph filters to filter node features respectively,and adds the results of multiple graph filters through attention mechanism.The validity of the model was demonstrated by experiments.Meanwhile,the frequency response function and the comparison of the graph signals before and after filtering are used to explain how the model uses the graph structure information in node classification tasks,which shows that the model has good interpretability.·Comparison of advantages and disadvantages between spatial and spectral models.By comparing the above two models,as well as the representative spatial and spectral comparison models,from the four perspectives of classification effectiveness,interpretability,computational complexity and time cost,model complexity and model parameter quantity,the advantages and disadvantages of spatial and spectral graph neural networks are comprehensively compared.