Towards Precise Prediction Uncertainty in GNNs: Refining GNNs with Topology-grouping Strategy

[On Comparison with GC]

W2 & W3. We appreciate the reviewer’s insightful observation in drawing parallels between our work and the approach presented in [3]. However, we respectfully disagree with the view that our work, SIMI-MAILBOX, is closely related to [3].

While our method shares the group-wise temperature scaling strategy with [3], there exist clear differences between SIMI-MAILBOX and the proposed method GC in [3], which we believe are worthwhile to clarify.

1. Specialization for GNNs: Alongside with aforementioned papers [1, 2], the grouping mechanism in [3] does not cover the topological properties of the graph data - a distinction crucial for GNN calibration, leading to suboptimal calibration for addressing GNNs. In contrast, our SIMI-MAILBOX is specifically tailored to the unique challenges and structures of GNNs, thereby accomplishing state-of-the-art performance on diverse benchmark datasets against numerous baselines.
2. Different Grouping Mechanism: While both [3] and SIMI-MAILBOX involve grouping instances for calibration, the underlying principles and mechanisms of these groupings are notably distinct. Our method conducts sophisticated categorization based on neighborhood similarity and confidence levels, specifically tailored to the unique properties of GNNs. Owing to this careful binning principles, leveraging KMeans clustering can lead to effective categorization. In contrast, [3] proposes a learning-based grouping function that does not explicitly account for the inherent characteristics of GNNs. Although it yields prominent performance in vision domain, the learning-based grouping function, which is in practice a single linear layer according to the original code (https://github.com/ThyrixYang/group_calibration/blob/master/methods/group_calibration.py), is not sufficient to capture neighborhood affinity, which will be verified in the subsequent experiment.
3. Methodological Distinction: In fact, [3] utilized the holdout set, which is partially sampled from the test set, to train the calibration function. However, our experiments demonstrate SIMI-MAILBOX's effectiveness with no need of the holdout set.

To validate the effectiveness of our method and grouping strategy over [3] empirically, we conducted additional experiments to compare our SIMI-MAILBOX and [3] with the holdout set (specified as GC w/ HO). We adopted two configurations, GC combined with TS [4] and GC with ETS [5], following the combination settings in the original paper. Detailed experimental settings is configured in Appendix B.5 in the revised paper. Note that unlike GC, our SIMI-MAILBOX is trained solely on the validation set, without an access to the holdout data.

According to the Table 1 and 2, our method consistently outperforms all combinations of GC across 15 out of 16 settings, pioneering the effectiveness of proposed grouping strategy over GC, even without an access to the holdout set. For convenience, we attach tables below in Table 12 in the revised paper.

Thus, while there are superficial similarities in using grouping and per-group temperatures for calibration, the specific execution and underlying principles of SIMI-MAILBOX are markedly different from [3], demonstrating predominant calibration performance over GC. Further, the results indicate that the learning-based grouping function in GC does not fully encompass the inherent characteristics of GNNs. We believe these differences are significant and contribute to the distinctiveness and novelty of our work in the domain of GNN calibration.

References

[1] Beyond calibration: estimating the grouping loss of modern neural networks, ICLR 2023.

[2] Multicalibration: Calibration for the (Computationally-Identifiable) Masses, ICML 2018.

[3] Beyond Probability Partitions: Calibrating Neural Networks with Semantic Aware Grouping, NeurIPS 2023.

[4] On Calibration of Modern Neural Networks, ICML 2017.

[5] Mix-n-Match: Ensemble and Compositional Methods for Uncertainty Calibration in Deep Learning, ICML 2020.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[On Comparison with Grouping-based Calibration Methods]

W1. We appreciate the reviewer’s helpful observations and for directing our attention to the work detailed in [1, 2]. We acknowledge the significance of this studies, thereby following the reviewer’s suggestion, we included these studies in the related works section (Section 2) in the revised manuscript.

Nevertheless, our method exhibits fundamental differences from [1, 2] in methodology and application. SIMI-MAILBOX is designed to address the unique calibration challenges posed by the intricate structure of graphs. The methodology and extensive analysis are deeply rooted in the properties of graph data, such as neighborhood affinity, which we do not find a direct parallel in the grouping discussed in [1, 2, 3]. We will discuss further distinctions in one-by-one.

To begin with, our work does share the similar aspect with [1] in terms of viewing the calibration status in a group-wise manner. However, the primary distinctions between our work and [1] lie in:

1. Different Grouping Mechanism: While [1] conducts partitioning leveraging decision tree, our method performs sophisticated categorization based on neighborhood similarity along with confidence levels. The referred work [1] is not designed to capture neighborhood affinity, which is a pivotal component in GNN calibration domain. Furthermore, it does not offer the principles for effective categorization, whereas we present the categorization criteria based on the novel observation of the correlation between neighborhood affinity and miscalibration level.
2. Methodological Divergence: While [1] introduces a universal approach to calibration loss applicable across different domains, SIMI-MAILBOX employs a novel strategy of post-hoc group-specific temperature adjustments that are uniquely suited to the diverging neighborhood affinity in graph data. The grouping scheme in [1] is utilized to quantify the grouping loss, rather than developing a new calibration method using the grouping algorithm.

Meanwhile, our approach partially aligns with [2] in its objective to address miscalibration among varying subgroups. Nevertheless, there are key differentiators that set our work apart from [2]:

1. Unspecified Grouping Mechanism: While both our method and the approach in [2] emphasize subgroup calibration, SIMI-MAILBOX employs a different grouping mechanism. Our method clusters nodes by assessing similarity in neighborhood predictions and confidence levels within the graph. In contrast, [2] proposes a more generalized framework for multicalibration, but without the specific focus on how the ideal subgraphs should be generated.
2. Essential Principle of Group-wise Calibration: The core principle of group-wise calibration is to categorize instances based on similar degrees of miscalibration. However, as mentioned in the above, [2] lacks the particular emphasis on this characteristic. Since per-group temperature is uniformly assigned to nodes within the designated group, organizing nodes with diverging levels of miscalibration leads to suboptimal calibration results. In contrast, our method presents straightforward criteria, i.e., neighborhood similarity along with confidence level, stemmed from our novel observation of the intimate correlation between nodes sharing similar neighborhood affinity and confidence.

[Sensitivity Analysis]

Q1-1. (On Hyperparameter Robustness) In response to the the reviewer’s helpful suggestion, we conducted extensive hyperparameter sensitivity analysis for GCN and GAT across all benchmark datasets. The whole results are depicted in Figure 4 in the revised manuscript. We compare the ECE results of the strongest baseline GATS [2] (specified as dark brown) and ours across varying values of a scaling factor $\lambda$ (specified as green) and the number of bins $N$ (specified as pink) within the range of [5, 10, 15, 20, 25, 30].

As demonstrated in Figure 4, SIMI-MAILBOX consistently outperforms the baseline across all hyperparameter configurations throughout diverse settings, with the number of bins $N$ demonstrating particularly stable performance trends. This robustness is attributed to our method's design, which accounts for the correlation between neighborhood similarity and the degree of miscalibration.

Q1-2. (Robustness on Scaling Functions) Regarding the reviewer’s concern with scaling $\hat p_i$ and $\bar{\mathcal M}_{simi}(i)$, the choice of scaling is rooted in the intuition of potential disparity in distributions of neighborhood similarity and confidence. For instance, while neighborhood similarity can be evenly distributed between 0 and 1, confidence in a high-accuracy dataset might be concentrated at higher values. In this situation, min-max scaling is an effective technique for normalizing data, especially when the values are concentrated in a specific range. However, to further enhance the robustness with respect to the design choice of scaling, we conducted additional experiment on our method with standard scaling (standard normalization) for constructing a feature vector, illustrated in tables below.

According to Table 1 and 2, SIMI-MAILBOX equipped with standard scaling consistently outperforms the strongest baseline in 15 of the 16 settings. Moreover, the performance gap between our method with standard scaling and the original SIMI-MAILBOX is marginal, suggesting that SIMI-MAILBOX is resilient to different choices of scaling method as well. For convenience, we attach tables below in Table 6 in the revised manuscript.

References

[1] Be confident! towards trustworthy graph neural networks via confidence calibration, NeurIPS 2021.

[2] What makes graph neural networks miscalibrated?, NeurIPS 2022.

[On Unfriendly Part]

W2. Thank you for your valuable feedback regarding the presentation of Figures 1 and 3 in our manuscript. We understand your concern about these figures appearing similar in format, which might lead to confusion. To mitigate this, we will consider adjusting the color schemes or formatting to visually differentiate the figures further in the later version of the paper.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[On Algorithmic Point of View on Previous GNN Calibration Methods]

W1. Our work acknowledges the heuristic nature of these conventional approaches and, as the reviewer correctly noted, our empirical results support this assertion. In response to the reviewer’s constructive feedback, we provide the limitation of previous GNN calibration approaches for addressing varying similarity levels in the algorithmic perspective as below.

To begin with, the node-wise temperature $T^{\text{CaGCN}}$ for $l$ layers in CaGCN [1] is defined as below:

where $\sigma^+$ and $\sigma_{\text{ReLU}}$ denote softplus and ReLU operation, while $Z$ and $W$ represent logits from trained GNNs and trainable weights, respectively.

The foundational assumption of CaGCN for leveraging GCN as a temperature function is that confidence for nodes linked to agreeing nodes should elevate, while that for nodes with disagreeing neighbors should decrease. They assert that GCN can make the confidence of adjacent nodes similar by propagating the predictions to neighboring counterparts. However, according to the above formulation, the temperature function does not necessarily yield higher temperatures for nodes with dissimilar neighbors or lower ones for those with similar neighbors, leading to suboptimal calibration results across diverse neighborhood affinity level. Moreover, our findings in Section 4 indicate that this does not hold true, especially for nodes with dissimilar neighbors.

Meanwhile, from the perspective of individual nodes $i$, the temperature function of GATS [2] $T^{\text{GATS}}_i$ is formulated as:

Here, $H$ and $T_0$ signify the number of attention heads and the initial bias term, respectively, with $\omega$ acting as a learnable coefficient to scale the relative confidence $\delta\hat c_i$ against neighborhood. The scaling factor $\gamma$ is introduced to leverage the distance-to-training-nodes property, and $\tau_j$ refers to the original logits $z_j$ transformed by a linear layer, followed by class-wise sorting within individual nodes' logits.

Recall that GATS demonstrated an increment in calibration error with a decrement in representational similarity, thereby introducing attention coefficient $\alpha_{ij}$ to reflect this. While $\alpha_{ij}$ attempts to capture the affinity between nodes, the model's capacity to discern and appropriately adjust for low similarity levels is limited, since the complex integration of various factors may lead to suboptimal temperature adjustments. For instance, the impact of the initial bias term $T_0$ and $\omega\delta\hat c_i$ may obscure the neighborhood similarity associated with nodes, which may not adequately capture the distinct calibration needs of nodes in diverse similarity contexts. Consequently, nodes in low or high similarity contexts might receive suboptimal temperature adjustments.

We sincerely thank the reviewer 3Tgz for the reassessment and improved score of our submission. Your constructive feedback has enhanced our work during the rebuttal. We are glad that our revision and responses have addressed your concerns.

Table 1. ECE results (reported in percentage) for our proposed calibration method with min-max scaling and standard scaling, compared to GATS on GCN. A lower ECE indicates better calibration performance.

Table 2. ECE results (reported in percentage) for our proposed calibration method with min-max scaling and standard scaling, compared to GATS on GAT. A lower ECE indicates better calibration performance.

[On Eq. 1]

W5. We sincerely appreciate the reviewer’s correction. We modified the typo in Eq. (1) in the revised paper.

References

[1] Be confident! towards trustworthy graph neural networks via confidence calibration, NeurIPS 2021.

[2] What makes graph neural networks miscalibrated?, NeurIPS 2022.

[3] Multi-scale Attributed Node Embedding, IMA Journal of Complex Networks 2021.

[4] Geom-GCN: Geometric Graph Convolutional Networks, ICLR 2020.

[5] Fast graph representation learning with PyTorch Geometric, ICLR 2019 (RLGM Workshop).

[6] On Calibration of Modern Neural Networks, ICML 2017.

[On Code Reproduction]

W4 & Q4. We apologize for any confusion caused regarding the accessibility of our code. To clarify, the link to our code repository was provided in the Appendix A.2 of our paper. We understand that this placement may have made it less noticeable. For your convenience, we have included the code as a zip file in the supplementary materials of our submission. However, due to the large memory of pretrained (uncalibrated) GNN model, we have attached the source code of SIMI-MAILBOX and descriptions for running the code, without the trained model. The full contents including pretrained GNN is provided in https://anonymous.4open.science/r/Simi_Mailbox-0816/.

We hope this resolves any difficulties you encountered in accessing our code and aids in your review of our work.

[On Experiments on Heterophilous Graphs]

W3 & Q3. In response to the reviewer’s insightful question, we extended our evaluations to include heterophilous graphs, as detailed in below table. Our benchmark datasets for this experiment included Chameleon, Squirrel, Actor, Texas, Wisconsin, and Cornell [3, 4]. We compared SIMI-MAILBOX against uncalibrated GNNs (UnCal), temperature scaling (TS) [6], and GATS. We adopted 10 different train/validation/test splits provided in the official PyTorch Geometric Library [5]. For each split, we conducted 5 random initialization, resulting in 50 runs in total. We maintained the same seeds to our method and baselines, to ensure fair comparison.

As indicated in Table 1, our method surpasses the baselines in 14 out of 16 settings. Notably, on the Texas dataset, SIMI-MAILBOX achieves ECE reduction of 2.65% and 2.98% for GCN and GAT, respectively, compared to uncalibrated results. Conversely, TS and GATS showed limited effectiveness in reducing calibration error in the Texas; GATS in fact increases ECE beyond the uncalibrated results. While the improvements with heterophilous graphs are less pronounced than those observed with homophilous graphs, SIMI-MAILBOX still effectively mitigates miscalibration than previous calibration methods. This is attributed to our method’s careful categorization on the basis of neighborhood similarity and confidence levels. For convenience, we attach tables below in Table 7 in the revised manuscript.

Table 1. ECE results (reported in percentage) on heterophilous datasets for our proposed calibration method and baselines on GCN, averaged over 50 runs. A lower ECE indicates better calibration performance.

Table 2. ECE results (reported in percentage) on heterophilous datasets for our proposed calibration method and baselines on GAT, averaged over 50 runs. A lower ECE indicates better calibration performance.

[On Limited Contribution]

W2. We thank the reviewer’s constructive comment regarding the nature of our proposed method. While our method shares the post-hoc temperature scaling scheme with previous works like CaGCN [1] and GATS [2], it introduces a novel approach in several key aspects.

To begin with, SIMI-MAILBOX employs group-specific temperatures, regardless of proximity or connectivity. Our method surpasses the node-wise adjustments typical in existing models like CaGCN and GATS, as these models are highly dependent on adjacent counterparts. Specifically, CaGCN derives per-node temperatures by leveraging GCN to propagate the logits of nodes to their corresponding neighbors. GATS yields node-wise temperature by propagating GAT to aggregate the neighbors’ logits and distance to training nodes, utilizing attention coefficient to encode neighborhood similarity. Conversely, our approach distinctively leverages KMeans clustering to categorize nodes, taking into account of both their prediction similarity and confidence levels. This enables a more granular and accurate calibration.

Furthermore, the significant innovation of SIMI-MAILBOX lies in our discovery that nodes with similar degrees of neighborhood affinity and confidence exhibit analogous calibration errors. This characteristic, not explored in prior works [1, 2], guides our unique categorization strategy and contributes to state-of-the-art calibration performance.

Additionally, our method achieves significant calibration time reduction against [1, 2], as depicted in Table 4. This is especially pronounced in comparison with GATS [2], which is verified to require significantly higher time consumption. This is due to the involvement of extensive parameters having distinct roles in calibration. Besides, GATS requires precomputation of the distance to training data for every node via BFS, which is computationally prohibitive when it comes to the large-scale graph data (Note that we did not include the duration of this preprocessing stage in GATS on Table 4). However, our SIMI-MAILBOX can reach markedly faster convergence owing to its straight forward design, without the need for preprocessing.

Thus, while there are some conceptual similarities with existing methods, SIMI-MAILBOX's distinct implementation and the new insight substantiate its novelty and valuable contribution to the field of GNN calibration.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[On Accuracy Preserving Property]

W1 & Q1. Our method's algorithmic structure, which utilizes post-hoc group-specific temperatures, ensures that the relative ordering of predictions remains unchanged.

Let us define $f_g:\mathbb R^K\rightarrow \mathbb R^K$ as a calibration function and $z_i=[z_{i1},z_{i2},...,z_{iK}]^{\mathsf T}$ as a logit vector of node $i$. We denote the group-specific temperature for the group node $i$ belongs to as $t_{g_i}$.

Since the group-wise temperature $t_{g_i}$ is uniformly applied to all elements of $z_i$, the order between elements in the calibrated logit $f_g(z_i)$ remains unchanged when subjected to the softmax operation $\sigma_{\text{sm}}$:

Thus, our SIMI-MAILBOX preserves the classification accuracy of the original GNNs, as the softmax function is order-preserving and the scaling by $t_{g_i}$ does not alter the relative ranking of the logit.

Furthermore, we present the tables below to empirically verify that our method preserves the accuracy of uncalibrated GNNs.

Table 1. Accuracy of uncalibrated GCN and Simi-Mailbox calibrated on GCN.

Table 2. Accuracy of uncalibrated GAT and Simi-Mailbox calibrated on GAT.

Thanks for the authors' detailed response. The pioneering work (CaGCN) [1] in this field (GNN calibration) evaluate their method in the self-training setting. Why you did not follow their experiments?

[1] Be confident! towards trustworthy graph neural networks via confidence calibration. (NeurIPS 2021)

Thank you for your detailed response. I am glad to hear that the experiments have addressed my concerns. As a result, I have raised the score to 6. Additionally, I suggest incorporating these new results into the final version.

[On Self-training Experiment]

In response to the reviewer’s thoughtful suggestion, we expanded our evaluation on self-training scenarios. We integrated our SIMI-MAILBOX into the original CaGCN [1] codebase to maintain consistency. To ensure fair comparisons, we followed the same datasets, split ratio, and evaluation protocols. Owing to the constraints of the rebuttal period, we present performance results averaged over five runs, ensuring the same random seeds across all experimental setups.

Note that, the performance reported in the original paper could be slightly different from our results. This discrepancy arises due to a requirement in our environment for a higher version of PyTorch (version 1.9.0) to accommodate dgl-cuda11.1, as opposed to the PyTorch version 1.8.1 used in CaGCN.

As presented in the following tables, SIMI-MAILBOX demonstrates superior performance over both uncalibrated GNNs and CaGCN across 17 out of 18 settings. This is especially evident in GAT on the Citeseer dataset, where our method achieves a performance increase of 4.18% compared to uncalibrated GAT when L/C=40. These results underscore the efficacy of SIMI-MAILBOX in generating refined pseudo-labels through its sophisticated calibration process. For your convenience, we have attached the tables below in Table 13 and 14 in the revised manuscript.

References

[1] Be confident! towards trustworthy graph neural networks via confidence calibration, NeurIPS 2021.

Table 1. Average node classification accuracy of various label rate (L/C) for our proposed calibration method and baselines on GCN.

Table 2. Average node classification accuracy of various label rate (L/C) for our proposed calibration method and baselines on GAT.