Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation
This addresses the challenge of semi-supervised node classification on heterophilous graphs for graph learning researchers, offering a competitive and efficient alternative to GNNs.
The paper tackled the problem of label propagation falling short on graphs with low homophily by designing a combination of a base predictor with a label propagation algorithm that uses a class compatibility matrix, achieving leading performance on benchmarks with various homophily levels and reducing parameters and execution time by orders of magnitude.
Graph Neural Networks (GNNs) have been predominant for graph learning tasks; however, recent studies showed that a well-known graph algorithm, Label Propagation (LP), combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. To overcome this, we carefully design a combination of a base predictor with LP algorithm that enjoys a closed-form solution as well as convergence guarantees. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities. On a wide variety of benchmarks, we show that our approach achieves the leading performance on graphs with various levels of homophily. Meanwhile, it has orders of magnitude fewer parameters and requires less execution time. Empirical evaluations demonstrate that simple adaptations of LP can be competitive in semi-supervised node classification in both homophily and heterophily regimes.