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.

翻译：图表神经网络(GNNs)在图形学习任务中一直占主导地位;然而,最近的研究表明,众所周知的图表算法Label Propagation(LP)加上浅神经网络可以达到与GNNs相似的性能,在具有高同质的图形中半监督节点分类。在本文中,我们表明,这一方法在低同质的图表上不尽如人意,节点往往与相对类的节点相连。为了克服这一点,我们仔细设计了一个基础预测器与LP算法的组合,该算法享有封闭式的解决方案和趋同保证。我们的算法首先学习了等级兼容性矩阵,然后用按类同性比较加权的LP算法汇总标签预测。在各种基准上,我们显示我们的方法在具有不同水平同质的图表上取得了领先性能。同时,它有数量级的参数,需要更少的执行时间。 经验性评估表明,在同性和异性和异性制度中,简单调整LP的简单调整在半超型节点分类中都具有竞争力。