Uncertainty for Active Learning on Graphs
This work addresses the under-explored applicability of Uncertainty Sampling in graph-based machine learning, providing insights for developing principled uncertainty estimation methods in this domain.
The paper tackled the problem of applying Uncertainty Sampling to node classification on graphs, finding a significant performance gap compared to other Active Learning strategies, and developed ground-truth Bayesian uncertainty estimates that consistently outperformed other estimators on real datasets.
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.