Uncertainty for Active Learning on Graphs

We want to thank the reviewer for their valuable time and feedback to review our manuscript.

The reviewer is correct that the ground-truth uncertainties actually use the ground-truth labels and this technically implies data leakage. However, our argument goes for the existence of such optimal (oracle-like) uncertainty measures and not utilizing them in a practical context.

Our main goal is to study the link between US and AL. Our theoretical result therefore implies that using the optimal epistemic uncertainty (which, again, can not be computed exactly in practice) is an optimal AL strategy. We first supply this with an empirical study on CSBMs under the idealized setting of full access to ground-truth uncertainties. This allows us to study the effects of disentangling uncertainty in an isolated fashion. We do not intend to propose ground-truth uncertainty as an AL strategy on CSBMs. We also want to point out that our theoretical analysis still fully translates to any dataset, albeit that ground-truth uncertainty, while also existing in this context, is not available and needs to be approximated instead. In our revised manuscript, we also accommodate learning the generative process (e.g. using a GNN) into our theory while retaining all optimality guarantees.

We agree with the concern whether the strong performance in an ideal setting (CSBMs) does imply a practically usable AL strategy. Therefore, to further strengthen the claim that our findings translate to real data, we also added an experimental study on real-world graph datasets. Here, we used simple GNN-based approximations to ground-truth uncertainty (see Appendix H for details) and did not facilitate any ground-truth labels (i.e. data leakage) hence being a practical approach to AL. We find that disentangling uncertainty according to our theory already outperforms many SOTA methods and US methods on most datasets (see Figures 6 and 15). We believe that this strongly underlines that our findings also translate well to realistic settings and can inform US strategies towards aligning with AL.

While the ground-truth uncertainty is defined with respect to information that is not available in practice (data generating process, labels of unobserved nodes), we empirically verify that trying to approximate them according to our theoretical framework gives a very strong AL strategy off-the-shelf. We believe that this shows that our theoretical analysis is highly relevant to the field of AL on graphs and can guide the development of novel US methods in a theoretically sound and well-motivated fashion.

We again want to point out that regardless of outperforming other AL strategies on multiple datasets in a realistic setting without data leakage, the core contribution of our work is its theoretical analysis. Understanding if and how UQ relates to AL bridges an important aspect of uncertainty modeling neglected by previous advances in the field of UQ. The efficacy of an approximative application of our insights is just one instance of how our work can impact the development of UQ methods. For example, future work could aim at better modeling the unknown data-generating process, e.g. by considering non-edges. We also make a case for considering AL when evaluating the effectiveness of novel UQ strategies on graphs. Consequentially, we updated our manuscript to highlight the contribution and goal of our paper more distinctly (see Sections 1 and 6).

Final Remarks

We hope that the addition of a practical, novel method together with an experiment on real-world data without data leakage that outperforms SOTA US approaches convinces the reviewer that our analysis poses a significant and valuable, practical contribution and is worth sharing with the scientific community. If so, we kindly ask the reviewer to reconsider their score.

We thank the reviewer for the time and the thorough review. We are delighted that the reviewer agrees with us, that we study the AL problem from an interesting perspective.

Missing methods

Addressing weaknesses a and b: We understand the concerns the reviewer has about the applicability of our results to a practical setting in which neither all labels nor the generative process is available. Our analysis, however, is purely theoretical: We show that ground-truth epistemic uncertainty is an optimal AL strategy. This result about the alignment of uncertainty estimation and AL also holds on real graphs, even though the proposed ground-truth uncertainties can not be computed exactly in practice. Our goal is to formally justify why we should expect US sampling to be an effective strategy in the first place. Furthermore, we can formally prove that disentanglement plays a crucial role in effective US, which again translates to real-world scenarios. Our work therefore provides a sound, theoretical basis on which novel US can be developed and applied to AL for interdependent data, which we believe to be a valuable contribution to the field.

We want to point out that it is not the access to ground-truth data that is central to the effectiveness of epistemic US: Measures of total, aleatoric, and epistemic uncertainty are defined in terms of ground-truth information (see Defintions 1-3) and exhibit very different efficacy to AL.

Nonetheless, we agree that our manuscript benefits from a more practical evaluation as well. To that end, we extended the theoretical framework to also allow a classifier to model the parameters of an underlying process in a learnable fashion, a framework that GNNs for example fit into. Based on this, we apply our theoretical insights to real-world data using GNNs as an approximative approach to our proposed, unknown ground-truth uncertainties. In this evaluation, we do not utilize any information about unavailable labels or the generative process. Nonetheless, this very off-the-shelf application of our findings elevates the uncertainty of a GNN classifier to outperform SOTA methods on multiple datasets. We hope to specifically also address weakness b with this additional empirical study, as we now propose an approximate estimator of epistemic uncertainty that aligns with our theory. We additionally discuss potential approximative errors of this simplistic approach in Appendix H.

Overall, we also adapted the manuscript to address the overall intention of our analysis more clearly: Our goal is not the proposal of a novel AL strategy, but rather to bridge the gap between principled US and AL on graphs. We theoretically prove that disentangled US and AL align in general. We reveal pitfalls in UQ and how to address them with an evaluation in an idealized setting on a CSBM. Lastly, we confirm the applicability to real-world scenarios by evaluating a simple approximative realization of our insights on real graphs and observing strong performance.

Addressing Question a: Estimating the true generative process of graph data is indeed a challenging topic. The aforementioned approach utilizes a simple GNN to address this problem and exhibits already reasonable performance. Nonetheless, we believe that our work can guide US toward the development of more faithful estimators: For example, on CSBMs, we observed non-edges to play a crucial role in successful US. Contemporary GNNs do not explicitly utilize such information which we conjecture to be one interesting direction for future research.

We want to thank the reviewer for their valuable feedback and the invested time to read our manuscript. We are delighted that the reviewer agrees with us that this is beneficial to the scientific community.

Knowledge of model parameters (Adressing Weakness 1 and Q 1&2)

We thank the reviewer for this comment and question as it is a valid point that we need to discuss in our work. We generalized our definitions to incorporate a parametrized classifier that opts to learn the true generative process:

$f_\theta^*(A, X, y_O^{gt}) = \text{argmax}_{c \in [C]^{|U|}} \textcolor{blue}{\int}\text{Pr}[{y_U= c \mid A, X, y_O = y_O^{gt}, \textcolor{blue}{\theta}}] \textcolor{blue}{p(\theta \mid A, X, y_O)d\theta}$

We updated and uploaded a revision of our paper where we highlight changes in blue. The Bayesian classifier averages its prediction over its parameters $\theta$ according to a posterior distribution $p(\theta | \mathbf{X}, \mathbf{A}, \mathbf{y})$. For example, these parameters $\theta$ could be estimates of the parameters of the underlying data-generating process in the CSBM setting or GNN parameters for real data. These changes can be found in Definitions 1-3 and the corresponding proofs. We adapt definitions 2 and 3 accordingly. Importantly, the proposed optimality results still hold, as only the computation of the ground-truth uncertainty is affected by this change.

While we can also try to learn the parameters of the underlying CSBM, this would introduce unwarranted noise into the evaluation. We have further clarified in our manuscript that the analysis on CSBMs opts to isolate the effect of disentangling and correctly modeling uncertainty (and therefore assumes no modeling errors).

In a new paragraph in Section 6, we detail an AL strategy that models the epistemic uncertainty as the difference between total and aleatoric (as in our theoretic result). Here, the total uncertainty originates from a classifier trained solely on labeled data. We then apply the predictions from this classifier as pseudo labels to train a subsequent model on all labeled nodes, with the exception of one (pseudo labels + real label) to model the aleatoric uncertainty for this one node.

Our method outperforms state-of-the-art US strategies on many datasets. All Figures can be seen in the updated version, Section 6 and Appendix H).

This experiment does not rely on explicit knowledge of either the generative process or unavailable labels but uses multiple approximations instead and thus could even be used as an AL strategy in practice. We, therefore, believe to provide even more valuable insights by closing the gap between an idealized synthetic setting and real scenarios. Looking ahead, future work could include improving the GNN approximators based on our other findings, such as modeling non-edges, for example in a transformer-like model.

We hope that with the adaptation of our theoretic results and the new experiments we properly addressed the parameter knowledge concern. If desired by the reviewer, we are open to including an additional experiment in the CSBM setting, conducted without parameter knowledge in the camera-ready version of our work.

We thank the reviewer for this pointer since framing and defining the problem in this more general parametrized way helps to better exemplify the applicability towards real-world scenarios which improves our manuscript substantially.

Adding that we don’t propose a novel method earlier in the text

We believe that the most substantial contribution of our work lies in the analysis of the problem. This groundwork paves the way for the principled development of new UQ strategies and strongly motivates AL as a valuable evaluation benchmark. For example, future studies could explore whether their uniquely disentangled uncertainties, potentially designed for different tasks, are also effective in an AL context.

Therefore, while we now even showcase a straightforward and practical application of our findings, it is our intent to present it as an experimental validation of our theory's applicability to real-world graphs, rather than as the centerpiece of a methods-focused paper. Hence, we further emphasize in our updated manuscript that a new method is not the goal of our work in the introduction and hope that the reviewer agrees with our view.

Final Comments

We updated our manuscript with all the changes highlighted in blue and would be delighted to learn whether the reviewer agrees with us that these changes improve our work significantly. We again want to again thank for the reviewer's valuable feedback that helped us improve the paper and kindly ask them to consider reevaluating their score.

We want to thank the author for their answer. This is indeed a typo in our updated manuscript: instead of being conditioned on $y_O$ the parameters have to be conditioned on $y_{-I}$ when computing aleatoric confidence. We adapted this in our document and decorated the $\theta$ with a hat to highlight that this is a different parameter belief than in Equation 2. We hope this adequately adresses the remark.

The parameter learning from (partially unobserved) labels $y_{-i}$ is indeed problematic in the real world. There, one has to rely on approximations: One idea, besides our framework, would be using one of the newer graph foundation models for aleatoric learning where the model has a lot more data outside the current graph. Another idea would be to only model aleatoric uncertainty in the absence of graph effects, i.e. using a LLM on the text of e.g. CoraML.

What we propose in our real-world experiment is a model that uses the pseudo labels from the learned classifier. That is, we learn $f(A, X, y_O)$ and infer all unseen data $\hat{y}_U$. Then we condition the parameter learning of an auxiliary model (for aleatoric uncertainty) on $p(\hat{\theta} | A, X, y_O, \hat{y}_U)$, i.e. we approximate $y_U$ with $\hat{y}_U$.

In our study on real-world datasets, we in fact use different parameter sets $\theta$ and $\hat{\theta}$ for estimating total and aleatoric confidence (LHS). This fits into the framework, as we assume different parameter beliefs for both uncertainty types $p(\theta | A, X, y_O)$ and $p(\hat{\theta} | A, X, y_O, \hat{y}_U)$.

Our results show that this method (LHS) and the other approximation we use (RHS) work well in practice: We again summarise the AUC scores for US and non-US method, where the best US strategy is highlighted bold and the best overall strategy (ie also non-US) is highlighted with a dagger in this table:

In conclusion, we want to say that the main goal of our paper is to investigate why all SOTA US strategies fail on AL. We find that this is due to wrong modeling choices. With a simple fix, we outperform all SOTA US strategies. We hope that our findings spark even more sophisticated strategies for US on graphs, which we believe to be underdeveloped. In particular, we don’t try to ‘sell’ our method as a novel AL strategy but provide a theoretically sound and empirically well-supported analysis of the relationship of US and AL that we hope to inspire more research in this area. We firmly believe, and hope that the reviewer agrees with us, that this is of value to the scientific community and in our view worth more than ‘just’ proposing a new acquisition strategy.

We want to thank the reviewer for their time and feedback and are delighted that the reviewer agrees with us that it is an interesting and important finding that US AL does not outperform random sampling.

Application to real-world graphs (addressing weaknesses 1 and 2)

We follow the reviewer’s suggestion to provide more evidence for applicability of our results to real-world problems. Nonetheless, the result that US is an optimal strategy for AL still holds, even if the true epistemic uncertainty can not easily be computed in practice. We both theoretically prove and empirically (on CSBMs) this optimality. Hence, we expect a strong, disentangled UQ method to perform well in AL. Our work motivates principled UQ and shows its relationship to AL formally and does not explicitly aim at proposing a novel improved AL strategy. We updated our paper to make this point more clear.

We also acknowledge the concerns regarding transferability to real-world settings. To that end, in our updated manuscript, we now introduce a method to apply our theory to real-world data in Section 6, paragraph “Real-World Data”. We detail a straightforward framework that models the epistemic uncertainty as the difference between total and aleatoric. This strategy is directly derived from our theoretic results and does not introduce any other components or tuning: The total uncertainty originates from a classifier trained solely on labeled data. We then apply the predictions from this classifier as pseudo labels to train a subsequent model on all labeled nodes (pseudo labels + real label) to model the aleatoric uncertainty. Our method outperforms many state-of-the-art US strategies on most datasets (all Figures can be seen in the updated version, Section 6 and Appendix H). We also provide a discussion of potential failure modes of this framework in Appendix H.

This experiment shows that our analysis translates to real-world graphs, where we explicitly do not use any unavailable data or knowledge about the generative process. Additionally, we adapted our theory to a setting where the Bayesian classifier has to learn the parameters of the underlying unknown generative process. GNNs that predict marginal probabilities for each node fit into this framework. Since our optimality guarantees still hold under these relaxed assumptions, we believe the applicability of our findings to be even more clearly relevant to practical scenarios.

We hope that with these results on real data, we can convince the reviewer that the theoretical insights on CSBMs apply to real-world graphs as the newly proposed framework is a simple straightforward implementation thereof. We want to mention that we still believe that, even though we outperform other SOTA AL strategies on multiple datasets, our theoretic analysis is the main contribution, as it bridges the gap between understanding the relationship between US and AL on graphs which has not been discussed in previous literature. As an example of how to incorporate our findings, one could try to explicitly tailor GNNs towards better modeling an assumed generative process, e.g. by considering the non-edges in a transformer-like fashion. Furthermore, as a consequence of our result that US and AL are well aligned, we strongly motivate using AL as a test of quality for newly devised uncertainty estimators (which are currently mostly evaluated on the detection of distribution shifts).

We also revised our manuscript to make the structure and value of our analysis clear: We first theoretically prove the alignment between epistemic US and AL and then proceed to support this with empirical evidence. First, we focus on a simplified CSBM setting and access to all labels. This analysis isolates the effects stemming from proper disentanglement and data modeling. We then proceed to a real-world setting, where we have to rely on various approximations to apply our theoretical insights. We observe our framework to show high efficacy nonetheless. This structure enables us to both propose theoretical soundness of the results we provide as well as high practicability at the same time.

Further changes to the manuscript

Addressing Question 1: As we use multiple dataset splits and model initializations, all curves are already average performances. We added plots for the requested experiments including the standard deviation to the Appendix (Figure 9), such that readers can see the high variance. Further, we added a description of the repeated trial setting to the main text in Section 4.

Addressing Question 2: We adapted the manuscript to give the background about US more concisely and added more explanation of epistemic and aleatoric effects to the background Section 2 at the same time. All additions are made visible with a blue font color in the new PDF version.

A) We are not sure why the reviewer thinks that there is no advantage over US baselines. We will emphasize that the dark green line (RHS) represents our framework in Figure 4 and Figure 15. In these figures, we show that this RHS approximation outperforms all other US strategies on all datasets! For a better quantitative comparison, we provide the area under the curve (AUC) for all of these plots which summarises the average accuracy over acquisitions in this. We highlight the best performing US strategy in bold and the best overall with a dagger.

The only consistently equally well-performing (non-US) strategy is GEEM, which our RHS approach matches. We also point out that our method is a straightforward implementation of the theory our paper provides without tuning any models. Nonetheless, we clearly (qualitatively and quantitatively outperform other US strategies and match the best non-US strategy's performance. Thus, we are confident to conclude that our results show significant merits for practical real-world uncertainty estimation, as evidently shown by the AUC scores.

B) We agree that the variance is extremely high on CSBMs. We point out two potential reasons: First, AL settings can inherently be noisy and since the CSBM graphs are relatively small, differences in acquired nodes (especially when picked almost randomly) may be even more pronounced. This is due to the fact that the CSMBs we study have a relatively low signal-to-noise ratio (SNR), otherwise, the whole task would be very easy to solve with GNNs (achieving near-perfect accuracy after only one acquisition per class). In this SNR regime, however, we observe high variance. Second, we study not one graph but average results over five CSBMs sampled from the same distribution: Again, due to relatively small graph sizes, we observe very different graphs in practice. We chose to average over multiple graphs to avoid “cherry-picking” one CSBM graph, where our ground-truth uncertainty performs well, and instead drew 5 random graphs to give an overall more truthful impression of performance.

However, due to the new real-world graph experiments, where we show that our RHS method outperforms all US strategies, showing the superiority of ours compared to baselines on CSBMs might be obsolete. What still is interesting is the performance of our approach using various uncertainties but we can remove the other figure if the reviewer is unhappy with it.

In conclusion, we want to say that we show that: (1) there is a gap between non-US AL and US AL strategies, and no SOTA method for US seems to work on par with the traditional methods. (2) we further analyze the problem and can prove that US and AL are well aligned and propose a new principled framework for US where the uncertainties are properly disentangled. (3) we show on synthetic and real-world data that we outperform all other US significantly and close the gap to non-US. Thus, we lay principled groundwork for new uncertainty estimators on graphs. In particular, we don’t try to ‘sell’ our method as a novel AL strategy but provide a theoretically sound and empirically well-supported analysis of the relationship of US and AL that we hope to inspire more research in this area. We firmly believe, and hope that the reviewers agree with us, that this is of value to the scientific community and in our view even worth more than proposing a new acquisition strategy.