Posterior Label Smoothing for Node Classification

We sincerely appreciate your effort in the review process and your constructive feedback to improve our paper. We particularly recognize the issue of lacking related work. We have conducted additional experiments and strengthened the related work section. Detailed responses to your questions are provided below.

W1 & W3: Related work that combine label-smoothing with GNNs

We have addressed this question in the general response. Please refer to general response 1. In short, we confirm that our method outperforms two recently proposed methods [1,2].

W2: Lack of theoretical motivation or analysis

We agree that we lack theoretical analysis for our method, and providing it would enhance the soundness and contribution of our work. In this response, we try to make a connection between our method and a previous theoretical analysis on label smoothing. In [3], the authors identify that uniform label smoothing can help generalization when the training label is noisy. In this sense, our method can also be seen as a mitigation of the noisy label. In traditional classification tasks where the relation between data points are unclear, it would be difficult to develop a meaningful smoothing. Whereas, in node classification tasks, we know that connected nodes are related to each other and therefore develop more informative smoothing method as we have done. More rigorous analysis in this theoretical direction would be a promising future work.

On the other hand, as Reviewer yTqG mentioned, our main contribution lies in the strong empirical results and diverse analyses we present. We believe that these contributions also offer positive contribution to the community.

W4: Explaining how the current application differs from or builds upon previous uses of iterative-pseudo labeling

The main difference between existing iterative pseudo labeling methods and ours lies in the use of the pseudo labels. As [4] noted, traditional methods “essentially adopt the semi-supervised strategy”, while we adopt the supervised settings. In more detail, once the pseudo labels are generated, traditional methods incorporate them into training set to retrain the model [4, 5], whereas we use the pseudo label to update the neigborhood and conditional statistics used for smoothing.

[1] Wang, Yiwei, et al. "Structure-aware label smoothing for graph neural networks." arXiv preprint (2021).
[2] Zhou, Kaixiong, et al. "Adaptive label smoothing to regularize large-scale graph training." SDM 2023.
[3] Chen, Blair, et al. "An investigation of how label smoothing affects generalization." arXiv preprint (2020).
[4] Cascante-Bonilla, Paola, et al. "Curriculum labeling: Revisiting pseudo-labeling for semi-supervised learning." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 8. 2021.
[5] Xu, Qiantong, et al. "Iterative pseudo-labeling for speech recognition." Interspeech 2020.

We sincerely appreciate your effort in the review process and recognition of the strengths of our work. We have carefully considered all of your comments, and detailed responses to your questions are provided below. We hope this helps address any concerns you may have.

W1: Sensitivity analysis of the hyperparameters $\alpha$ and $\beta$

We have addressed this question in the general response. Please refer to general response 2. In short, we confirm that our method is insensitive to $\alpha$ and $\beta$.

W2: Comprehensive comparison with related work

We have addressed this question in the general response. Please refer to general response 1. In short, we confirm that our method outperforms two recently proposed methods.

Q1: Are there examples to support the assumption that the neighborhood labels are conditionally independent given the label of the node?

Unfortunately, we couldn't find any empirical evidence on our claim about the independency. Having said that, this kind of assumption is widely adopted in machine learning in general to make the model simple and tractable. One example is the i.i.d. assumption between data points, which is widely accepted even though it doesn't make sense in reality. In the context of graph learning, [1,2,3] assume that L-hop ego graph of a target node is i.i.d., which is similar to our assumption.

Q2: Why are the node features not considered in the relabeling process?

KD can be seen as a relabeling process that considers the node features, since teacher models generate soft labels using the node features as input. Our experimental results show that PosteL, which focuses on utilizing label information rather than node features, outperforms KD. Incorporating both node features and labels into the relabeling process would be an interesting idea, but it may hurt our core contribution 'simple but effective'. Having said that this could be an interesting research direction for future work.

Q3: How does the performance on sparse label compare to other preprocessing methods?

We conduct additional experiments to evaluate the performance of label smoothing baselines on sparse labels. PosteL shows the best performance, achieving the highest results in 22 out of 24 cases. Label smoothing with uniform noise (LS) is less affected by sparse labels since it does not rely on labeled neighborhoods, performing slightly better than when using GT labels. In contrast, SALS [4] and ALS [5] are significantly affected by sparse labels because they depend on labeled neighborhoods.

Q3: The reasons behind the effectiveness of PosteL with sparse labels. are lacking explanation.

The reason for our concern regarding PosteL in sparse label settings is that PosteL's advantage comes from utilizing information from labeled neighborhoods. However, in sparse label settings, there are fewer labeled neighborhoods. We believe the pseudo labeling process mitigates this concern, allowing PosteL to work effectively in sparse label settings.

SALS and ALS face the same issue as PosteL, but they do not propose a method to mitigate it. Consequently, we observe that SALS and ALS often perform worse than when using GT labels.

[1] Verma, Saurabh, and Zhi-Li Zhang. "Stability and generalization of graph convolutional neural networks." KDD 2019.
[2] Garg, Vikas, Stefanie Jegelka, and Tommi Jaakkola. "Generalization and representational limits of graph neural networks." ICML 2020.
[3] Wu, Qitian, et al. "Handling distribution shifts on graphs: An invariance perspective." arXiv preprint 2022.
[4] Wang, Yiwei, et al. "Structure-aware label smoothing for graph neural networks." arXiv preprint arXiv:2112.00499 (2021).
[5] Zhou, Kaixiong, et al. "Adaptive label smoothing to regularize large-scale graph training." SDM 2023.

We sincerely appreciate your effort in the review process and your constructive feedback. We have carefully reviewed our paper based on your comments, and detailed responses to your questions are provided below. Finally, thank you for highlighting the editorial issues regarding the duplicated reference and inconsistent notation. We will address these issues in a future revision.

W1: Comparison with time/resource consumption

We estimated training time of PosteL and the other baselines and presented in the following table. With IPL, PosteL requires more training time, being 1.3 times slower than ALS [1] and 5.7 times slower than using GT labels. If this computational overhead is too heavy, we can use PosteL without IPL or IPL with one iteration as an alternative. PosteL without IPL is 2 times faster than KD and ALS, and PosteL with IPL with one iteration is also faster than KD and ALS while not sacrificing the accuracy. We reported the accuracy of each variation in Table 3 of our paper. Additionally, we measured the memory consumption of PosteL on the Cora dataset. PosteL requires only 0.87MB of additional memory to process labels.

W2: The reliance on global label statistics might introduce bias in cases where the dataset has inherent class imbalance or label noise.

• [Class imbalance] We believe that the class imbalance would not be a problem if the training and test sets follow the same underlying distribution. In fact, some datasets we used have class imbalance property, such as Computers and Texas, where our method improves the accuracy. In the table below, we provide the proportion of nodes for each class across different datasets.

• [Noisy label] To check the robustness of our method under noisy label, we conducted additional experiments, where 30% of the training data labels were randomly flipped to different labels. The table below shows the results on noisy labels. We observed that PosteL still outperforms GT on noisy labels.

W4: Experimental results comparing with recent methods

We have addressed this question in the general response. Please refer to general response 1. In short, we confirm that our method outperforms two recently proposed methods [1,2].

W6 & Q3: Sensitivity analysis of the hyperparameters $\alpha$ and $\beta$

We have addressed this question in the general response. Please refer to general response 2. In short, we confirm that our method is insensitive to $\alpha$ and $\beta$.

Q1: Details on the implementation of the IPL process

Details on the implementation of the iterative pseudo labeling are provided below.

1. Generate soft labels for the training nodes by applying Equation 1 to the GT labels of the training nodes.
2. Train the GNN using the soft labels of training nodes obtained from Step 1.
3. Using the trained GNN from Step 2, obtain pseudo labels for the validation and test nodes.
4. Using the GT labels of the training nodes and the pseudo-labels of the validation and test nodes, generate new soft labels for the training nodes by applying Equation 1.
5. Train a new GNN using the soft labels of the training nodes obtained from Step 4.
6. Repeat Steps 4 and 5 until the validation loss does not decrease.

Q2: In the IPL process, the validation and test sets are introduced to training. Whether the model will be overfitting to validation and test sets?

We apologize for confusion. As described in the answer to the previous question, the model is not trained to fit the pseudo labels of validation and test nodes directly. Instead, pseudo labels are used to calculate statistical values that update the soft labels of training nodes.

Q4: Not all the validation and test losses with the soft labels converge to lower losses than those with the ground truth labels.

Indeed, this is an interesting observation. We found that even when the validaiton loss with the soft labels is greater than that of the GT labels, the accuracy of the PosteL is better than the model trained on GT labels. Due to the characteristics of the cross entropy loss, two different prediction results with the same label after argmax can have very different level of losses, e.g., for binary prediction, $\arg\max([0,1])=\arg\max([0.4,0.6])=1$. This can be understood as an overfitting mitigation, but we believe it is not 'overly' mitigated since the PosteL is still effective in terms of the accuracy. Similar observation is noted in previous work as well [3].

Q5: Loss curve of other soft label based methods

In Figure 2 of attached PDF file in the general response, we plot learning curves of different models with their best hyperparameter configurations. PosteL shows the smallest gap between training and testing losses compared to other methods, showing strong empirical evidence on overfitting alleviation. Furthermore, the validation and test losses of our methods still remains at the similar level while those of other methods are keep increasing when the training is longer.

[1] Zhou, Kaixiong, et al. "Adaptive label smoothing to regularize large-scale graph training." SDM 2023.
[2] Wang, Yiwei, et al. "Structure-aware label smoothing for graph neural networks." arXiv preprint (2021).
[3] Müller, Rafael, Simon Kornblith, and Geoffrey E. Hinton. "When does label smoothing help?." NeurIPS 2019.

Thank you for your dedicated effort in the review process. We appreciate the constructive feedback and your recognition of the strengths of our work. We have carefully considered all the points you mentioned and provided detailed responses to each question below. Additionally, we will address the editorial issues you mentioned in the revised version.

W1 & Q1: Related work on label smoothing for node classification

We have addressed this question in the general response. Please refer to general response 1. In short, we confirm that our method outperforms two recently proposed methods.

W2: Theoretical contribution

We agree that we lack theoretical analysis for our method, and providing it would enhance the soundness and contribution of our work. [1] shows the effect of label smoothing with uniform noise on the view of generalization, which can be a potential direction for future works.

W3 & W4: Experimental details and the meaning of experiments with varying proportion of training set.

We first sorry for the use of a jargon. In this work, we tackle a node classification problem in a transductive setting. In transductive node classification, a graph and the labels of some nodes are given as a training set, and we predict the labels of the remaining nodes as a test set. Hence, in training time, we can observe the entire connectivity between all nodes including a test set. A small portion of training set can be used as a validation set.

Table 4 in our paper shows the changes in prediction performance when the proportion of labeled nodes increases. Intuitively, our method may not work well when the number of nodes with known label is small, but through the experiments, we found that our method works surprisingly well with the limited amount of training labels. Although it needs to be investigated more thoroughly, we conjecture that the estimation of the global label statistics could help to compensate the influence of sparse neighbors.

Q2: It is a bit concerning that according to Figures 2, 6, and 7, the baselines appear to have a chance if the right regularization and/or optimal early stopping is applied. Also, the weight decay grid search is very limited; is there any reason for that? Moreover, do you have a justification as to why we should not take the early stopping as a hyperparameter as opposed to the current setup that is fixed for each variation?

In Figure 2 of the attached PDF file in the general response, we plot the learning curves of different models with their best hyperparameter configurations within our grid search space. PosteL shows the smallest gap between training and testing losses compared to other methods, showing strong empirical evidence on overfitting alleviation. Furthermore, the validation and test losses of our methods still remains at the similar level while those of other methods are keep increasing when the training is longer.

The grid search spaces are originally proposed in the BernNet paper [2]. We follow the same procedure for a fair comparison. The early stopping strategy is also adopted from the BernNet. Our empirical observation with Figure 2 in the general response also suggest that 200 epochs are sufficient to check potential improvement in training.

Q3: Table 1: some explanation as to why certain models, such as GPR-GNN or BernNet, appear to not be benefiting from label smoothing

We respectfully disagree that our method does not benefit from label smoothing for certain models. For GPR-GNN and BernNet, our method improves performance in 19 out of 20 cases, with 8 cases showing significant improvement over a 95% confidence interval. The relatively smaller improvements for heterophilic graphs compared to other backbone GNNs might be because GPR-GNN and BernNet are already known to process heterophilic graphs well, thus leaving less room for additional gains.

Q4: line 117: it is mentioned that the condition is unnecessary based on empirical results. Could you please refer to the experiment in which this is being observed?

Sorry for the confusion. The empirical results are observed while we conducted experiments but never shown in the submitted manuscript. For the information, we provide the hyperparameter sensitivity analysis in the general response by varying the values of $\alpha$ and $\beta$.

In Figure 1 of the attached PDF file in the general response, the blue line represents the performance with varying $\alpha$, while the green line shows the performance with varying $\beta$. The red dotted line indicates the performance with the GT labels. We found that the model performance is quite robust to the choice of hyperparameter except for extreme cases.

Q5: line 109: is this still true in the case of the IPL? In the IPL, the empirical distributions seem to be updated according to the pseudo-labels on the validation/test, correct?

Correct. We keep the original empirical distributions the same to make the IPL simple. We conducted experiments with the updated empirical distributions but could not find a significant gain in results.

Q6: Figures 2, 6, and 7: are they based on one split? Perhaps it would be useful to look at the mean and variance across all splits, similar to the reporting in Table 1.

Yes, Figures 2, 6, and 7 are based on a single split. Figure 2 in the general response shows the loss curve averaged over 10 splits on the Squirrel dataset. We will update these figures in future revision.

[1] Chen, Blair, et al. "An investigation of how label smoothing affects generalization." arXiv preprint (2020).
[2] He, Mingguo, Zhewei Wei, and Hongteng Xu. "Bernnet: Learning arbitrary graph spectral filters via bernstein approximation." NeurIPS 2021.

I thank the authors for their diligence in addressing the concerns and questions. Q4, Q5, and Q6 are addressed, and I have no further inquiry.

Regarding Q1, the explanation provided is the type of information expected to be included in the paper. For the final revision of the paper, it is highly recommended that similarities be included and that the existence of [1] be acknowledged. Likewise, it is important to highlight the key differences between each step in as much detail as possible. ALS's label propagation is similar to posterior label smoothing in this work, with the key difference being that the prior in the former is the hard labels while in the latter is the global statistics, which appears to be one of the elements that accommodate both homophilic and heterophilic graphs. A similar comparison is expected for the "label refinement" and "smooth pacing" steps from ALS. It would be great if the authors also provided such an explanation in their answer to this inquiry, which could further assist reviewers in their final opinion.

Also, in Table 1 of the attached PDF, it would be great to highlight which datasets are homophilic and heterophilic.

Concerning the response to W3 & W4, while the current experiment conducted under section 4.3 is a valid experiment, it addresses the question of the efficiency of the model in learning. The title of the section, however, sets the expectation for the reader to see the performance of the model against different label sparsity ratios.

Here are some possibilities:

• a) varying node label sparsity across the graph but with a fixed training set size.
• b) varying node label sparsity across train and test sets. (so the sparsity is different per each set)
• c) fixed label sparsity across the graph, but varying training set size while test set size is fixed.

The authors provide results for "case c", while "case a" seems to assess the robustness of the method against different sparsities because it addresses sparsity more directly, while "case c" includes the confounding effect of both train size and label sparsity.

My recommendation is to rephrase the current section title, and if authors intend to report robustness against sparsity, "case a" is a better option. If they decide not to include such an experiment in their work, it is then suggested to make necessary clarifications in the title and body of the section corresponding to this experiment, and they may mention this as a future work.

Concerning Q2, First, a follow-up question: Loss curves for GT in Figure 2 from the paper and Figure 2 from the attached PDF do not match, e.g., GT labels in 1000 epochs get minimized up to ~0.4 loss, while in the new attached PDF for the same number of epochs, it gets minimized up to ~0.8. Similarly, for the PosteL, e.g., the difference between validation and test is more pronounced based on Figure 2 of the paper than the figure in the attachment.

I was expecting them to be the same. Why are they different?

Second, I rephrase my question as I feel the main point is still not fully addressed: According to the original Figure 2 from the paper, early stopping at epoch ~50 provides a similar performance to Postel labels.

That holds true for all datasets in Figure 6 and for some datasets in Figure 7. So, the question is, given that we can obtain comparable performance only by performing different early stopping for GT vs PosteL, why not do that?

Concerning Q3, my concern is addressed. However, I just want to clarify that my question was meant to be, "Why does GPR-GNN or BernNet appear to not benefit from label smoothing as much." It would be useful to add the explanation that the authors provided in their response to the paper as well.

A minor final point regarding Tables 1 and 5 of the paper: it is not self-evident which datasets are homophilic and which are heterophilic. This can be communicated more directly.

[1] Zhou, Kaixiong, et al. "Adaptive label smoothing to regularize large-scale graph training." SDM 2023.