Graph Neural Network leveraging Higher-order Class Label Connectivity for Heterophilous Graphs
2026-06-05 • Machine Learning
Machine LearningArtificial Intelligence
AI summaryⓘ
The authors studied how graph neural networks (GNNs) can better classify nodes in graphs where connected nodes often have different labels, called heterophilous graphs. They found that existing GNNs struggle with this because they don't consider complex patterns of label connections. To fix this, they created a new method called Label Context Classifier (LCC) that uses special patterns of node visits, called walks, to understand these connections better in directed graphs. Their experiments showed that combining LCC with existing GNNs improves classification performance on challenging heterophilous graphs.
Graph Neural Networks (GNNs)Node ClassificationHomophilyHeterophilyDirected GraphsLabel Context Classifier (LCC)Graph Convolutional NetworksHigher-order ConnectivityGraph Walks
Authors
Takuto Takahashi, Itsuki Nakayama, Takahiro Mitani, Ryosuke Kikuchi, Yuya Sasaki, Makoto Onizuka
Abstract
Node classification in graph neural networks (GNNs) has been widely applied in various fields of graph analysis. GNNs achieve high-accuracy node classification in homophilous graphs, where nodes with the same class label tend to be connected. However, their performance remains limited in heterophilous graphs, where nodes with different class labels are more likely to be connected. In particular, current GNNs derived from graph convolutional networks cannot capture higher-order class label connectivity, which is frequently observed in real-world heterophilous graphs. To address this issue, we propose a novel classifier, Label Context Classifier (LCC), designed to capture higher-order class label connectivity in directed graphs. LCC estimates the class label of a target node by leveraging label context embeddings that are generated through four distinct types of walks. In addition, our approach allows the integration of LCC and any GNN by adaptively learning their importance. Experimental results demonstrate that GNNs integrated with LCC outperform SOTA methods and the label context embeddings improve the node classification performance in heterophilous directed graphs.