Uncertainty Sampling is an Active Learning strategy that aims to improve the data efficiency of machine learning models by iteratively acquiring labels of data points with the highest uncertainty. While it has proven effective for independent data its applicability to graphs remains under-explored. We propose the first extensive study of Uncertainty Sampling for node classification: (1) We benchmark Uncertainty Sampling beyond predictive uncertainty and highlight a significant performance gap to other Active Learning strategies. (2) We develop ground-truth Bayesian uncertainty estimates in terms of the data generating process and prove their effectiveness in guiding Uncertainty Sampling toward optimal queries. We confirm our results on synthetic data and design an approximate approach that consistently outperforms other uncertainty estimators on real datasets. (3) Based on this analysis, we relate pitfalls in modeling uncertainty to existing methods. Our analysis enables and informs the development of principled uncertainty estimation on graphs.

基于节点分类的不确定性采样是主动学习策略，通过迭代地获取具有最高不确定性的数据点的标签，以提高机器学习模型的数据效率。本文首次对节点分类的不确定性采样进行了全面研究，我们超越了预测不确定性来评估不确定性采样，揭示了与其他主动学习策略之间的显著性能差距，并开发了基于数据生成过程的地面真实贝叶斯不确定性估计，证明了其在引导最佳查询中的有效性。在合成数据上验证了我们的结果，并设计了一种近似方法，不断优于其他真实数据集上的不确定性估计。基于此分析，我们将不确定性建模中的问题与现有方法联系起来，我们的分析有助于并引导了基于图的原则性不确定性估计的发展。

图上主动学习中的不确定性