Posterior Label Smoothing for Node Classification

Authors: Jaeseung Heo, MoonJeong Park, Dongwoo Kim
Primary area: learning on graphs and other geometries & topologies
Keywords: node classification, label smoothing

Abstract:
Soft labels can improve the generalization of a neural network classifier in many domains, such as image classification. Despite its success, the current literature has overlooked the efficiency of label smoothing in node classification with graph-structured data. In this work, we propose a simple yet effective label smoothing for the transductive node classification task. We design the soft label to encapsulate the local context of the target node through the neighborhood label distribution. We apply the smoothing method for seven baseline models to show its effectiveness. The label smoothing methods improve the classification accuracy in 10 node classification datasets in most cases. In the following analysis, we find that incorporating global label statistics in posterior computation is the key to the success of label smoothing. Further investigation reveals that the soft labels mitigate overfitting during training, leading to better generalization performance. Our code is available at https://anonymous.4open.science/r/PosteL.

Decision: reject
Reviewer scores: 3, 5, 8, 6

Reviews and discussion:
<thread>
creation date:
1729581347984

thread_type:
official_review

<thread_object>
creator: reviewer_uap1

<content>
summary:
The paper proposes a label-smoothing method called PosteL for the transductive node classification task. This method generates soft labels by integrating local neighborhood information and global label statistics, enhancing generalization and reducing overfitting. Specifically, it computes the posterior distribution of node labels by estimating conditional distributions through neighbour nodes and prior distributions through all labeled nodes, and then interpolates the posterior distribution with the ground truth label to obtain a soft label.Experiments on 10 node classification datasets with 7 baseline models demonstrate its effectiveness.

strengths:
1. This paper introduces a simple yet effective label smoothing method for transductive node classification.

2. This paper investigates the performance of the proposed label smoothing method on different datasets and models, and analyzes the key factors for its success.

3. The authors present their ideas in a well-structured manner, making it easy for readers to follow the flow of the research. The figures in the paper are presented clearly and effectively support the text.

weaknesses:
1. After claiming the effective handling of heterophilic graphs as a highlight, the description of the proposed method fails to emphasize its treatment of heterophilic graphs. For instance, it is not clear why the proposed method is suitable for handling heterophilic graphs and where the efficiency of this treatment is manifested.

2. The motivation for proposing the method and the effects achieved by the method itself seem to be contradictory. In Section 1, the authors state "...their performance on heterophilic graphs, where nodes tend to connect with others that are dissimilar or belong to different classes, still remains questionable." However, the proposed method estimates the posterior of one node based on label frequency of its neighbours, which leads to its prediction similar to the classes of its neighbours. In addition, the estimation of the prior mitigates the problem of class imbalance but does not address the stated problem of heterogeneity.

3. The idea in the method section of the article is similar to that of a naive Bayes approach, but some assumptions of conditional independence need to be clearly stated in Section 3.

4. In the case where the neighbors are not labeled and the neighbors of the neighbors are also not labeled, an iterative process of generating pseudo-labels needs to be reflected in this algorithm part.

questions:
1. Please explain how the method proposed in the article addresses the stated problem of heterogeneity.

2. In the setting of this paper,  the connectivity between all nodes, including the test nodes, is assumed to be observed. Is this assumption a bit too strong? Please give some explanations.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730097368934

thread_type:
official_review

<thread_object>
creator: reviewer_vwwq

<content>
summary:
The manuscript proposes PosteL, a label smoothing method utilizing posterior distribution for node classification in graph-structured data. It is basically a preprocessing method for GNNs, generating soft labels based on neighborhood context and global label statistics before the training phase.

strengths:
1. The manuscript is well-structured and easy to comprehend. For example, Fig. 1 is clear and intuitive.
2. The method is simple yet effective. PosteL can be combined seamlessly with existing methods.
3. The manuscript presents a wealth of experimental results that highlight the potential of PosteL for performance enhancement.

weaknesses:
The significant drawback I perceive in this manuscript is that while it explores the usefulness of smoothing in the graph domain, the underlying principles that contribute to its effectiveness are not sufficiently clarified. Providing a theoretical analysis of its effectiveness would significantly strengthen the authors' claims.

questions:
1. According to Section 2.2, PosteL differs from existing works focused on smoothing in the graph domain in terms of assumptions. However, is there any analysis that demonstrates how these assumptions influence performance improvement? Are there specific examples that support the manuscript's assumptions? Providing this would be crucial for substantiating the novelty of the work.
2. According to the appendix, the datasets are all structured data. Can PosteL be applied to a broader range of research in the graph domain?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730453072142

thread_type:
official_review

<thread_object>
creator: reviewer_5wqb

<content>
summary:
This paper proposes a posterior label smoothing method (PosteL) that enhances node classification accuracy by incorporating both local neighborhood information and global label statistics. The approach demonstrates performance improvements on both homogeneous and heterogeneous graphs. Experimental results show that this method prevents overfitting and exhibits generalization capabilities across multiple datasets and baseline models.

strengths:
1. This paper introduces a new idea in label smoothing by using posterior distribution calculations for label smoothing. Unlike traditional uniform noise smoothing methods, the authors propose combining local neighborhood information with global label distribution, allowing labels to reflect the local graph structure of nodes.
2. The method was tested on both standard homogeneous graphs and heterogeneous graphs, highlighting its general applicability. Experiments show that PosteL label smoothing can prevents overfitting and enhances model generalization without increasing model complexity.

weaknesses:
1. While the posterior label smoothing method achieves notable improvements on graph-structured data, it relies on the neighborhood label distribution of nodes, which may lead to unstable posterior distributions in sparse graphs or scenarios with very few labels, resulting in reduced label quality. Although the authors propose a strategy of re-estimating the posterior with pseudo labels, limitations remain, especially on heterogeneous graphs with sparse labels.
2. Although the paper mentions that the computational complexity is linearly related to the number of edges and categories, it lacks sufficient discussion on efficient computation and optimization for large-scale graph structures, especially heterogeneous graphs. In real-world applications, such as large-scale social networks or e-commerce recommendation systems, this method may encounter efficiency bottlenecks.
3. Although the paper compares various existing label smoothing methods, it lacks adequate comparison with the latest graph classification models, particularly on large-scale heterogeneous graphs. This limitation suggests that PosteL’s effectiveness on more complex or dynamic graph tasks may require further validation.

questions:
1 The author should clarify how different neighborhood configurations impact performance in heterophilic vs. homophilic settings.
2 How does the method perform with highly sparse labels, particularly below 10% labeled data? Are there specific mitigations for sparsity?
3  The aushor should provide details on the computational cost of PosteL relative to other smoothing methods, especially in terms of training duration across datasets?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730698213226

thread_type:
official_review

<thread_object>
creator: reviewer_cvti

<content>
summary:
The paper introduces a method called Posterior Label Smoothing (PosteL) designed to improve node classification tasks in graph-structured data. By integrating both local neighborhood information and global label statistics, PosteL generates soft labels that enhance the generalization capabilities of models and mitigate overfitting. The method is applied to various datasets and models, showing that it consistently outperforms traditional label smoothing and other baseline methods.

strengths:
1. The paper is well-written and the content is presented clearly, making it easy to follow.

2. The experiments are comprehensive and include a variety of different settings.

3. The proposed method is probabilistically driven, offering a more rational approach compared to existing heuristics.

weaknesses:
1. The contribution of this paper is somewhat incremental - the idea of using neighborhood information to perform label smoothing has already been extensively studied [1, 2]. 

2. "Under the assumption that the neighborhood labels are conditionally independent given the label of the node to be relabeled...", I fail to comprehend this statement, hope authors can further explain this. But in any case, I think the assumption of two adjacent nodes are conditioally independent is too strong. 

3. While the proposed method shows superior emprical performance, this paper fail to provide an in-depth explaination on why label-smoothing performs so well in graph-structured data - does it stems from the same reason as i.i.d. data? What makes the proposed method superior than other label smoothing methods on graph?

4. The improvements over the most competitive baselines are marginal - for most cases the differences are within the standard deviation.

[1] Adaptive Label Smoothing To Regularize Large-Scale Graph Training, Zhou et al., 2021.

[2] Structure-Aware Label Smoothing for Graph Neural Networks, Wang et al., 2021.

questions:
please refer to the weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1732180514947

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
Thanks to all the reviewers for their dedicated efforts during the rebuttal phase. We have carefully considered all of the comments, and we have revised our manuscript to incorporate the reviewers' feedback.

### **In-depth analysis of the underlying assumptions of PosteL**
In the first response, we aim to provide an in-depth explanation of the underlying assumption of PosteL. We have included this analysis in Appendix A of the revised version.

Our posterior distribution, $P(Y_i=k|\\{Y_j = y_j|j\in\mathcal{N}(i)\\})$, is based on the assumption that nodes with similar neighborhood label distributions should exhibit similar characteristics. Recently, [1] introduced neighborhood context similarity, $\mathcal{S}(\mathcal{G})$, defined as:

\begin{equation}
\mathcal{S}(\mathcal{G})=\sum_{k=1}^{K}\sum_{u,v\in\mathcal{V_k}}\cos(d(u),d(v)),
\end{equation}

where $K$ is the number of classes, $\mathcal{V}_k$ is the set of nodes with label $k$, $d(u)$ is the neighborhood label distribution, and $\cos(\cdot)$ is the cosine similarity. (We omit some terms for simplicity.) $\mathcal{S}(\mathcal{G})$ represents the degree to which the neighborhood distributions between nodes with the same label are similar. This metric is closely related to our assumption: if $\mathcal{S}(\mathcal{G})$ is large, our assumption holds. The table below, from [1], presents the edge homophily ratio $\mathcal{H}(\mathcal{G})$ and neighborhood context similarity $\mathcal{S}(\mathcal{G})$ for each dataset.

||Cora|CiteSeer|Pubmed|Computers|Photo|Chameleon|Actor|Squirrel|Texas|Cornell|
|-|-|-|-|-|-|-|-|-|-|-|
|$\mathcal{H}(\mathcal{G})$|0.81|0.74|0.80|0.78|0.83|0.23|0.22|0.22|0.11|0.30|
|$\mathcal{S}(\mathcal{G})$|0.89|0.81|0.87|0.90|0.91|0.67|0.68|0.73|0.79|0.40|

This table shows that our assumption generally holds across both homophilic and heterophilic graphs. We conjecture that this generality of the assumption contributes to PosteL's strong performance on both homophilic and heterophilic datasets.

### **The comparison between PosteL and the other smoothing methods**

In the second response, we provide differences between PosteL and other label smoothing methods from a different perspective, especially on heterophilic graphs. We have included this analysis in Appendix C of the revised version.

**1. The effect of utilizing global statistics**  
PosteL leverages global statistics, specifically $\hat{P}(Y_j=m|Y_i=n, (i,j)\in\mathcal{E})$ and $\hat{P}(Y_i=m)$, to generate soft labels. In contrast, SALS [2] only utilizes information from 1-hop neighbors. The use of global statistics in ALS [3] is questionable due to the presence of learnable component in their soft label. We provide an example of the soft labels on a binary node classification task with a bipartite graph at this [**(anonymized link)**](https://ibb.co/gVD9rBs). The toy example highlights the key differences between existing methods and ours, which will be elaborated further below.

**1-1. Conditional probability $\hat{P}(Y_j=m|Y_i=n)$ and its impact**  
$\hat{P}(Y_j=m|Y_i=n, (i,j)\in\mathcal{E})$ is the conditional probability of a label given the neighborhood label. We analyze the effect of the conditional distribution in balanced binary classification. Let us define node-wise individual homophily $p_i$ and class homophily $c_k$ as:

\begin{equation}
p_i:=\frac{|\\{(i,j)|(i,j)\in\mathcal{E},y_i=y_j\\}|}{|\\{(i,j)|(i,j)\in\mathcal{E}\\}|},
\end{equation}

\begin{equation}
c_k:=\frac{|\\{(i,j)|(i,j)\in\mathcal{E},y_i=k,y_j=k\\}|}{|\\{(i,j)|(i,j)\in\mathcal{E},y_i=k\\}|}=\hat{P}(Y_j=k|Y_i=k, (i,j)\in\mathcal{E}).
\end{equation}

With PosteL, the probability that the posterior label is the same as the ground truth label is given by:

\begin{equation}
P(Y_i=y_i|\\{Y_j = y_j|j\in\mathcal{N}(i)\\})  = \frac{c_{y_i}^{|\mathcal{N}(i)|p_i}(1-c_{y_i})^{|\mathcal{N}(i)|(1-p_i)}}{c_{y_i}^{|\mathcal{N}(i)|p_i}(1-c_{y_i})^{|\mathcal{N}(i)|(1-p_i)}+c_{y_i'}^{|\mathcal{N}(i)|(1-p_i)}(1-c_{y_i'})^{|\mathcal{N}(i)|p_i}},
\end{equation}

where $y_i$ is the ground truth label of node $i$ and $y_i'$ is the other label. 

With homophilic graphs where $c_y>(1-c_y), c_{y'}>(1-c_{y'})$ and $p_i > (1-p_i)$ generally, the posterior distribution of the ground truth label is higher than the negative label. With heterophilic graphs, where $c_y<(1-c_y), c_{y'}<(1-c_{y'})$ and $p_i < (1-p_i)$ generally, the posterior distribution of the ground truth is also higher than the negative label.

A simple analysis shows that PosteL assigns a high probability to the ground truth label regardless of whether the graph is homophilic or heterophilic. The presence of the global label statistics $\hat{P}(Y_j=m|Y_i=n, (i,j)\in\mathcal{E})$ plays an important role in these cases, as they provide information about the overall homophilicity of the graph.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a label smoothing method for transductive node classification, which incorporates local context through neighborhood label distribution. However, the reviewers provided negative feedback, raising several concerns, including: (1) the assumption that neighborhood labels are conditionally independent given the node's label is unclear; (2) the improvements over competitive baselines are viewed as marginal; and (3) the method faces limitations in handling heterogeneous graphs with sparse labels. Based on these considerations, the paper is not recommended for acceptance at this time.