Expressive Power ofMessage Passing in Graph Neural Networks

Abstract

Graph neural networks (GNNs) have become essential tools for graph representation learning, with models likeGraphConvolutionalNetworks (GCNs),Graph- SAGE, and Graph Attention Networks (GATs). It has achieved notable success in various applications. HSGATv2, a recent advancement, enhances attentionmechanisms for nodes with the same class label. However, traditional GNN weight assignment methods, which often depend on node degrees or pair-wise representations, are less effective in heterophilic networks in which the labels or properties of connected nodes differ. It has been shownthat most existing models are primarily prone to homophilic graphs and lack generalization to heterophilic settings, and multi-layer perceptrons and other models that neglect the graph structure sometimes exceed these models in terms of performance. This dissertation explores the effectiveness of GNNs in node classification tasks within heterophilic or lowhomophily environments, where many common GNNs fail to perform well. So, in this dissertation, we try to address it and introduce a representation learning methodology that is comparatively suitable for both homophilic and heterophilic graphs. By thoroughly examining local structure and heterophily distributions, our approach effectively manages networks with diverse homophily ratios. Additionally, we propose a regularized optimization function to enhance model adaptability to any graphstructure. Our evaluationsonvariousnodeclassification datasets demonstrate that the proposed method is competitive to the standard baseline models, and promisingly generalizable.