Posterior Label Smoothing for Node Classification

Q2: 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.

This problem setup is known as the transductive setting. In a transductive setting, the labels of training nodes and all connectivity information, including that of test nodes, are provided. The objective of this setting is to predict the labels of test nodes using their connectivity information. This is a common setting in node classification papers [1, 2, 3]. A typical example is the citation graph, where the objective is to predict the category of a paper using the information from adjacent (cited) papers.

[1] Kipf, Thomas N., and Max Welling. "Semi-supervised classification with graph convolutional networks." ICLR 2017.
[2] Veličković, Petar, et al. "Graph attention networks." ICLR 2018.
[3] Chien, Eli, et al. "Adaptive universal generalized pagerank graph neural network." ICLR 2021.

We sincerely appreciate the dedicated effort in evaluating our work and providing constructive feedback. We recognize that the explanation for why our method works on heterophilic graphs was insufficient, and we believe the response will help clarify this. A detailed explanation is provided below, and if any parts remain unclear or if further questions arise, we would be happy to address them.

W1: 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.

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

We provide an in-depth analysis of the underlying assumptions of PosteL and a case study comparing smoothing methods and PosteL in the general response at the top of the page. Please refer to the general response for details.

Firstly, PosteL assumes that nodes with similar neighborhood label distributions should exhibit similar characteristics. As shown in the general response, this assumption holds for both homophilic and heterophilic graphs. We conjecture that this generality of the assumption contributes to PosteL's strong performance across both types of datasets.

Next, PosteL assigns a high probability to the ground truth label for both homophilic and heterophilic graphs. This is in evident difference to SALS, which is dominated by negative labels on heterophilic graphs.

Comparing PosteL to ALS is non-trivial due to the trainable component in ALS. However, we found that ALS fails to distinguish nodes with different labels when individual node homophily is zero. We also show that PosteL can distinguish the failure cases of ALS.

This difference comes from the use of global statistics, $\hat{P}(Y_j=m|Y_i=n, (i,j) \in \mathcal{E})$, so we conjecture that it is another main factor behind PosteL's superior performance. This aligns with the results in Table 2 of our paper, which show that replacing global statistics with local statistics decreases performance.

W2: 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.

As analyzed in the general response and the attached example, the PosteL label differs from the labels of neighboring nodes on heterophilic graphs. Figure 1 in the paper also illustrates this, where the soft label assigns a high probability to the green label, despite neighboring nodes being labeled red and blue. For these reasons, we respectfully disagree with this comment.

W3: 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.

Our method is based on the assumption that neighborhood labels are conditionally independent, given the label of the node to be relabeled. The approximation described in lines 153–156 stems from this assumption. We have clarified this point in the revised version (lines 151–153).

W4: 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.

When there is no labeled neighborhood, the likelihood cannot be calculated. In such cases, we use the ground truth label instead of the posterior distribution. We have clarified this exception in the revised version of our paper, specifically in Algorithm 1 and Algorithm 2. To minimize the occurrence of such cases, we propose iterative pseudo labeling. This method assigns pseudo labels using the trained GNN, ensuring that every node has either a label or a pseudo label. As a result, exception cases arise only for nodes with no neighbors. For a detailed explanation, please refer to Algorithms 2 and 3 in Appendix B. Additionally, the absence of labels in neighbors of neighbors does not pose an issue for our method, as it does not rely on the labels of two-hop neighbors.

We sincerely appreciate the response. We believe the provided feedback is very important and it will be thoroughly addressed in this response. It would be greatly appreciated if this could be reviewed with kind consideration. We have included this analysis in Appendix A of the revised version.

Theoretical analysis of the characteristics of PosteL with heterophilic graphs

In addition to the detailed analysis provided in the general response (at the top of the page), we provide additional two lemmas showing the characteristics of PosteL with heterophilic graphs.

For simplicity, we focus on a binary classification problem with two classes: 0 and 1. To establish the lemma, we define the individual node homophily $p_i$ and class homophily $c_k$ as follows:

$

p_i:=\frac{|\{(i,j)|(i,j)\in\mathcal{E},y_i=y_j\}|}{|\{(i,j)|(i,j)\in\mathcal{E}\}|}, 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\}|}.

$

Then the posterior label of the node being labeled to 0 is:

$

P(Y_i=0|\{Y_j = y_j|j\in\mathcal{N}(i)\}) = \frac{c_0^{|\mathcal{N}(i)|p_i}(1-c_0)^{|\mathcal{N}(i)|(1-p_i)}}{c_0^{|\mathcal{N}(i)|p_i}(1-c_0)^{|\mathcal{N}(i)|(1-p_i)}+c_1^{|\mathcal{N}(i)|(1-p_i)}(1-c_1)^{|\mathcal{N}(i)|p_i}}.

$

Lemma 1. In a heterophilic graph with $c_0, c_1 < 0.5$, if two nodes have the same degree $d$, and node $i$ is connected to more nodes labeled 1 than node $j$, then PosteL assigns a higher probability of node $i$ being labeled 0 compared to node $j$.

Since the number of adjacent nodes with a different label is larger for node $i$, we have $p_i<p_j$. The lemma can be expressed as follows:

$

\frac{c_0^{dp_i}(1-c_0)^{d(1-p_i)}}{c_0^{dp_i}(1-c_0)^{d(1-p_i)}+c_1^{d(1-p_i)}(1-c_1)^{dp_i}}>\frac{c_0^{dp_j}(1-c_0)^{d(1-p_j)}}{c_0^{dp_j}(1-c_0)^{d(1-p_j)}+c_1^{d(1-p_j)}(1-c_1)^{dp_j}}.

$

Expanding the inequality:

$

c_0^{d(p_i+p_j)}(1-c_0)^{d(2-p_i-p_j)}+c_0^{dp_i}(1-c_0)^{d(1-p_i)}c_1^{d(1-p_j)}(1-c_1)^{dp_j} >\ c_0^{d(p_i+p_j)}(1-c_0)^{d(2-p_i-p_j)}+c_0^{dp_j}(1-c_0)^{d(1-p_j)}c_1^{d(1-p_i)}(1-c_1)^{dp_i}.

$

Subtracting $c_0^{d(p_i + p_j)}(1 - c_0)^{d(2 - p_i - p_j)}$ from both sides:

$

c_0^{dp_i}(1-c_0)^{d(1-p_i)}c_1^{d(1-p_j)}(1-c_1)^{dp_j}>c_0^{dp_j}(1-c_0)^{d(1-p_j)}c_1^{d(1-p_i)}(1-c_1)^{dp_i}.

$

$

((1-c_0)(1-c_1))^{d(p_j-p_i)}>(c_0c_1)^{d(p_j-p_i)}.

$

Since $c_0<1-c_0$ and $c_1<1-c_1$ imply that $(1 - c_0)(1 - c_1)>c_0c_1$, and given $(1 - c_0)(1 - c_1)>c_0c_1$ and $p_j-p_i> 0$, the inequality holds.

Lemma 2. In a heterophilic graph with $c_0, c_1 < 0.5$, if two nodes are connected only to nodes labeled 1, and their respective degrees are $n$ and $m$ ($n > m$), then PosteL assigns a higher probability of being labeled 0 to the node with the higher degree.

When nodes are connected only to nodes labeled 1, PosteL assigns the posterior probability of the node being labeled 0 as follows:

$

P(Y_i=0|\\{Y_j = 1|j\in\mathcal{N}(i)\\})=  \frac{(1-c_0)^{\text{deg}(i)}}{(1-c_0)^{\text{deg}(i)}+c_1^{\text{deg}(i)}},

$

where $\text{deg}(i)$ represents the degree of node $i$. The lemma can be expressed as follows:

$

\frac{(1-c_0)^n}{(1-c_0)^n+c_1^n} > \frac{(1-c_0)^m}{(1-c_0)^m+c_1^m}.

$

Expanding the inequality:

$

((1-c_0)^m+c_1^m)(1-c_0)^n > ((1-c_0)^n+c_1^n)(1-c_0)^m.

$

$

(1-c_0)^n(1-c_0)^m+c_1^m(1-c_0)^n > (1-c_0)^n(1-c_0)^m+c_1^n(1-c_0)^m.

$

$

c_1^m(1-c_0)^n > c_1^n(1-c_0)^m.

$

$

(1-c_0)^{n-m} > c_1^{n-m}.

$

Since $c_0,c_1<0.5$, it follows that $1-c_0>c_1$. Thus, the inequality holds.

As a corollary we can show the following two properties.

1. If two nodes have the same degree, the node connected to more nodes labeled 1 should have a higher probability of being labeled 0.
2. If two nodes are connected only to nodes labeled 1, the node with the higher degree should have a higher probability of being labeled 0.

Although these lemmas and corollary may not reflect the real-world scenario, analyzing properties of a model is an important step towards understanding its performance.

The comparison between PosteL and the other smoothing methods

(This section is copied from the general response in case, it is missed. The analysis is not just showing the assumptions and empirical results but contains key characteristics of PosteL to compare with the existing methods.)

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 [1] only utilizes information from 1-hop neighbors. The use of global statistics in ALS [2] 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). 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. With PosteL, the probability that the posterior label is the same as the ground truth label is given by:

$

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}},

$

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.

SALS [1]
SALS interpolates the ground truth label with the neighborhood labels to generate a soft label. Hence, when the graph is heterophilic, the soft label is likely to be dominated by the negative labels. The figure in the anonymized link shows the example of SALS, where the soft label is dominated by the negative label.

ALS [2]
The label smoothing of ALS consists of three processes: 1) ALS aggregates the neighborhood labels using the formula $\frac{1}{|\mathcal{N}(i)|}\sum_{j\in\mathcal{N}(i)}\mathbf{e}_j$, 2) the aggregated labels are interpolated with the ground truth label, and 3) the interpolated labels are transformed via a linear transform parameterized by learnable weight matrix $\mathbf{W}$ followed by softmax. (Note that our analysis is based on the published version of ALS [2] and not arxiv version - the methods are slightly different between these two versions.)

Analyzing the deterministic behavior of ALS [2], as done previously for PosteL and SALS, is non-trivial due to the presence of a learnable component. However, there are explicit cases where ALS fails to distinguish nodes with different labels. When $p_i=0$, ALS generates a soft label as $\text{softmax}([1,1]\mathbf{W})$, regardless of the value of $y_i$. In such cases, ALS adds the same noise regardless of the characteristics of nodes, which is identical to uniform smoothing. The attached figure illustrates a example of ALS, where it assigns the same label to all nodes.

Discussion
Based on these differences, we argue that PosteL is significantly distinguished from other smoothing methods. This difference comes from the use of global statistics, $\hat{P}(Y_j=m|Y_i=n, (i,j) \in \mathcal{E})$, so we conjecture that it is the main factor behind PosteL's superior performance. This aligns with the results in Table 2 of our paper, which show that replacing global statistics with local statistics decreases performance.

[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.

We sincerely appreciate the dedicated effort in the review process and the recognition of the strengths of our work. We are also grateful for the constructive feedback. We acknowledge the insufficient explanation of PosteL's effectiveness and have addressed this through our response. If any parts remain unclear or if further questions arise, we would be happy to address them.

W1: 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.

We provide an in-depth analysis of the underlying assumptions of PosteL and a case study comparing smoothing methods and PosteL in the general response at the top of the page. Please refer to the general response for details.

Firstly, PosteL assumes that nodes with similar neighborhood label distributions should exhibit similar characteristics. As shown in the general response, this assumption holds for both homophilic and heterophilic graphs. We conjecture that this generality of the assumption contributes to PosteL's strong performance across both types of datasets.

Next, PosteL assigns a high probability to the ground truth label for both homophilic and heterophilic graphs. This is in evident difference to SALS, which is dominated by negative labels on heterophilic graphs.

Comparing PosteL to ALS is non-trivial due to the trainable component in ALS. However, we found that ALS fails to distinguish nodes with different labels when individual node homophily is zero. We also show that PosteL can distinguish the failure cases of ALS.

This difference comes from the use of global statistics, $\hat{P}(Y_j=m|Y_i=n, (i,j) \in \mathcal{E})$, so we conjecture that it is another main factor behind PosteL's superior performance. This aligns with the results in Table 2 of our paper, which show that replacing global statistics with local statistics decreases performance.

Q1: 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.

We address this question in the general response. Please refer to the section In-depth analysis of the underlying assumptions of PosteL in the general response.

Q2: According to the appendix, the datasets are all structured data. Can PosteL be applied to a broader range of research in the graph domain?

The only requirements for applying PosteL are the node labels and adjacency information, which are typically provided in node classification tasks. Therefore, PosteL can be applied to a wider range of node classification researchs in the graph domain.

W3: 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.

We validate the effectiveness of PosteL on the latest graph classification model, OrderedGNN [2]. PosteL achieves the best performance on nine out of ten datasets and significantly outperforms on the CiteSeer and Squirrel datasets. We have included this analysis in Table 1 of the revised version.

We validate PosteL's performance on the large-scale ogbn-products dataset [1] on GCN. While the performance improvement is not statistically significant, PosteL achieves the best performance compared to other smoothing methods. We have included this experiment in Appendix G of the revised version.

Q1: The author should clarify how different neighborhood configurations impact performance in heterophilic vs. homophilic settings.

We provide an in-depth analysis of the underlying assumptions of PosteL and a case study comparing smoothing methods and PosteL in the general response at the top of the page. Please refer to the general response for details.

SALS demonstrates different neighborhood configurations could significantly impact performance. In homophilic graphs, the soft labels from SALS are dominated by positive labels. However, in heterophilic graphs, the soft labels from SALS are dominated by negative labels.

Table 1 of our paper shows the differing effects of SALS on homophilic and heterophilic graphs. On homophilic graphs, SALS consistently performs better than the ground truth label. However, SALS shows a significant decrease in performance on the Texas dataset, which is the most heterophilic dataset in our experiments.

In contrast, PosteL is not significantly affected by whether the graph is homophilic or heterophilic, as it consistently assigns a high probability to the ground truth label for both types of graphs.

In addition, PosteL has the underlying assumption that nodes with similar neighborhood label distributions should exhibit similar characteristics. As shown in the general response, this assumption holds for both homophilic and heterophilic graphs. We conjecture that this generality of the assumption contributes to PosteL's strong performance across both types of datasets.

Q3: The author should provide details on the computational cost of PosteL relative to other smoothing methods, especially in terms of training duration across datasets?

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 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. We have included this experiment in Appendix F of the revised version.

[1] Hu, Weihua, et al. "Open graph benchmark: Datasets for machine learning on graphs." NeurIPS 2020.
[2] Song, Yunchong, et al. "Ordered gnn: Ordering message passing to deal with heterophily and over-smoothing." ICLR 2023.

We sincerely appreciate the extensive effort in evaluating our paper and providing constructive feedback. We have carefully considered all comments and incorporated additional experiments in the revised version. If any parts remain unclear or if further questions arise, we would be happy to address them.

Before addressing the feedback, we would like to clarify the distinction between the terms heterophilic and heterogeneous. Since our paper focuses on heterophilic graphs, we assume that the use of "heterogeneous" in the feedback refers to "heterophilic." If this assumption is incorrect, please let us know, and we will adjust our response accordingly.

W1: 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.

Q2: How does the method perform with highly sparse labels, particularly below 10% labeled data? Are there specific mitigations for sparsity?

We evaluate the performance of PosteL with extremely sparse labels. For all datasets, we randomly select 10 nodes per class as training nodes, resulting in $10K$ training nodes. In the PubMed dataset, only 0.15% of nodes are used as training nodes. PosteL outperforms the baselines even in this extremely sparse setting, particularly on heterophilic datasets, demonstrating that the pseudo labeling strategy effectively mitigates the issue of sparsity. We have included this experiment in Appendix G of the revised version.

W2: 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.

We measured the runtime of processing soft labels (Algorithm 1) on the ogbn-products dataset [1], which contains 2,449,029 nodes and 61,859,140 edges, to validate the computational complexity on a large-scale graph. Using our method, generating soft labels takes 52.57 seconds. Given that training for one epoch requires 19.11 seconds, this is not a significant overhead. These results demonstrate that PosteL can efficiently generate soft labels, even on large-scale graph structures. We have included this analysis in Appendix G of the revised version.

We sincerely appreciate the effort in evaluating our paper and providing constructive feedback. We acknowledge that the explanation of our method's advantage in node classification was insufficient, and we believe that we have addressed this issue in our response. If any aspects remain unclear or if there are additional questions, we would be happy to address them.

W1: The contribution of this paper is somewhat incremental - the idea of using neighborhood information to perform label smoothing has already been extensively studied.

W3: 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?

We provide an in-depth analysis of the underlying assumptions of PosteL and a case study comparing smoothing methods and PosteL in the general response at the top of the page. Please refer to the general response for details.

Firstly, PosteL is significantly distinct from other smoothing methods. We shows that PosteL assigns a high probability to the ground truth label for both homophilic and heterophilic graphs. This is in evident difference to SALS, which is dominated by negative labels on heterophilic graphs.

Comparing PosteL to ALS is non-trivial due to the trainable component in ALS. However, we found that ALS fails to distinguish nodes with different labels when individual node homophily is zero. We also show that PosteL can distinguish the cases.

Based on these differences, we argue that PosteL is significantly distinguished from other smoothing methods. This difference comes from the use of global statistics, $\hat{P}(Y_j=m|Y_i=n, (i,j) \in \mathcal{E})$, so we conjecture that it is the main factor behind PosteL's superior performance. This aligns with the results in Table 2 of our paper, which show that replacing global statistics with local statistics decreases performance.

Next, PosteL assumes that nodes with similar neighborhood label distributions should exhibit similar characteristics. As shown in the general response, this assumption holds for both homophilic and heterophilic graphs. We conjecture that this generality of the assumption contributes to PosteL's strong performance across both types of datasets.

W2: "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.

The statement is used to derive the factorization of the joint distribution in lines 153-156 as follows $P(\\{Y_j = y_j|j\in\mathcal{N}(i)\\}|Y_i=k) \approx \prod_{j \in \mathcal{N}(i)} {P}(Y_j=y_j | Y_i = k, (i,j)\in\mathcal{E})$. We have clarified this assumption in revised version (line 151-153). This assumption might be stong, however 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 are widely accepted even though it is unclear whether it holds in many cases. 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.

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

Compared to ALS, which achieves the second-best performance, PosteL outperforms it beyond the 95% confidence interval in 13 out of 70 settings. Therefore, we argue that PosteL is significantly better than even the most competitive baselines.

[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.

Whenever you have a chance, we’d appreciate your feedback on our rebuttal - thank you.

SALS [2]
SALS interpolates the ground truth label with the neigbhorhood labels to generate a soft label. Hence, when the graph is heterophilic, the soft label is likely to be dominated by the negative labels. The figure in the anonymized link shows the example of SALS, where the soft label is dominated by the negative label.

ALS [3]
The label smoothing of ALS consist of three processes: 1) ALS aggregates the neighborhood labels using the formula $\frac{1}{|\mathcal{N}(i)|}\sum_{j\in\mathcal{N}(i)}\mathbf{e}_j$, 2) the aggregated labels are interpolated with the ground truth label, and 3) the interpolated labels are transformed via a linear transform parameterized by learnable weight matrix $\mathbf{W}$ followed by softmax. (Note that our analysis is based on the published version of ALS [3] and not arxiv version - the methods are slightly different between these two versions.)

Analyzing the deterministic behavior of ALS [3], as done previously for PosteL and SALS, is non-trivial due to the presence of a learnable component. However, there are explicit cases where ALS fails to distinguish nodes with different labels. When $p_i=0$, ALS generates a soft label as $\text{softmax}([1,1]\mathbf{W})$, regardless of the value of $y_i$. In such cases, ALS adds the same noise regardless of the characteristics of nodes, which is identical to uniform smoothing. The attached figure illustrates a example of ALS, where it assigns the same label to all nodes.

Discussion
Based on these differences, we argue that PosteL is significantly distinguished from other smoothing methods. This difference comes from the use of global statistics, $\hat{P}(Y_j=m|Y_i=n, (i,j) \in \mathcal{E})$, so we conjecture that it is the main factor behind PosteL's superior performance. This aligns with the results in Table 2 of our paper, which show that replacing global statistics with local statistics decreases performance.

1-2. Global label distribution $\hat{P}(Y_i=m)$ and imbalanced datasets
Next, $\hat{P}(Y_i=m) := \frac{\lvert \set{ u \mid y_u = m } \rvert}{\lvert \mathcal{V} \rvert}$, represents the proportion of label $m$ across all nodes. This term is multiplied by the conditional probability, so when a label has a low proportion, PosteL assigns a lower probability to it. Reflecting the label distribution across the entire graph can be advantageous for graphs with imbalanced labels. For example, PosteL demonstrates consistent performance improvement on the imbalanced Computers dataset, where the label proportions are shown in the following table.

1-3. Further analysis on global statistics
Additionally, We demonstrate in subsection [Influence of neighborhood label distribution] in Section 4.2 that global label statistics contain sufficient information for distinguishing labels. Furthermore, we show in Table 2 that relying solely on local information negatively impacts performance. Therefore, we argue that the use of global statistics is the reason for PosteL's superior performance.

2. The advantage of utilizing pseudo labeling strategy
Another distinction is the pseudo labeling strategy. SALS and ALS cannot work on sparse graphs, as there will be no labeled neighborhoods. Our pseudo labeling strategy enables smoothing even on sparse graphs by assigning pseudo label to unlabeled nodes. To the best of our knowledge, PosteL is the first label smoothing approach in node classification to address sparse label scenarios.

[1] Xiao, Teng, et al. "Simple and asymmetric graph contrastive learning without augmentations." NeurIPS 2024.
[2] Wang, Yiwei, et al. "Structure-aware label smoothing for graph neural networks." arXiv preprint 2021.
[3] Zhou, Kaixiong, et al. "Adaptive label smoothing to regularize large-scale graph training." Proceedings of the 2023 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2023.

Theoretical analysis of the characteristics of PosteL with heterophilic graphs

We provide additional two lemmas showing the characteristics of PosteL with heterophilic graphs.

For simplicity, we focus on a binary classification problem with two classes: 0 and 1. The posterior label of the node being labeled to 0 is:

$

P(Y_i=0|\{Y_j = y_j|j\in\mathcal{N}(i)\}) = \frac{c_0^{|\mathcal{N}(i)|p_i}(1-c_0)^{|\mathcal{N}(i)|(1-p_i)}}{c_0^{|\mathcal{N}(i)|p_i}(1-c_0)^{|\mathcal{N}(i)|(1-p_i)}+c_1^{|\mathcal{N}(i)|(1-p_i)}(1-c_1)^{|\mathcal{N}(i)|p_i}}.

$

Lemma 1. In a heterophilic graph with $c_0, c_1 < 0.5$, if two nodes have the same degree $d$, and node $i$ is connected to more nodes labeled 1 than node $j$, then PosteL assigns a higher probability of node $i$ being labeled 0 compared to node $j$.

Since the number of adjacent nodes with a different label is larger for node $i$, we have $p_i<p_j$. The lemma can be expressed as follows:

$

\frac{c_0^{dp_i}(1-c_0)^{d(1-p_i)}}{c_0^{dp_i}(1-c_0)^{d(1-p_i)}+c_1^{d(1-p_i)}(1-c_1)^{dp_i}}>\frac{c_0^{dp_j}(1-c_0)^{d(1-p_j)}}{c_0^{dp_j}(1-c_0)^{d(1-p_j)}+c_1^{d(1-p_j)}(1-c_1)^{dp_j}}.

$

Expanding the inequality:

$

c_0^{d(p_i+p_j)}(1-c_0)^{d(2-p_i-p_j)}+c_0^{dp_i}(1-c_0)^{d(1-p_i)}c_1^{d(1-p_j)}(1-c_1)^{dp_j} >\ c_0^{d(p_i+p_j)}(1-c_0)^{d(2-p_i-p_j)}+c_0^{dp_j}(1-c_0)^{d(1-p_j)}c_1^{d(1-p_i)}(1-c_1)^{dp_i}.

$

Subtracting $c_0^{d(p_i + p_j)}(1 - c_0)^{d(2 - p_i - p_j)}$ from both sides:

$

c_0^{dp_i}(1-c_0)^{d(1-p_i)}c_1^{d(1-p_j)}(1-c_1)^{dp_j}>c_0^{dp_j}(1-c_0)^{d(1-p_j)}c_1^{d(1-p_i)}(1-c_1)^{dp_i}.

$

$

((1-c_0)(1-c_1))^{d(p_j-p_i)}>(c_0c_1)^{d(p_j-p_i)}.

$

Since $c_0<1-c_0$ and $c_1<1-c_1$ imply that $(1 - c_0)(1 - c_1)>c_0c_1$, and given $(1 - c_0)(1 - c_1)>c_0c_1$ and $p_j-p_i> 0$, the inequality holds.

Lemma 2. In a heterophilic graph with $c_0, c_1 < 0.5$, if two nodes are connected only to nodes labeled 1, and their respective degrees are $n$ and $m$ ($n > m$), then PosteL assigns a higher probability of being labeled 0 to the node with the higher degree.

When nodes are connected only to nodes labeled 1, PosteL assigns the posterior probability of the node being labeled 0 as follows:

$

P(Y_i=0|\\{Y_j = 1|j\in\mathcal{N}(i)\\})=  \frac{(1-c_0)^{\text{deg}(i)}}{(1-c_0)^{\text{deg}(i)}+c_1^{\text{deg}(i)}},

$

where $\text{deg}(i)$ represents the degree of node $i$. The lemma can be expressed as follows:

$

\frac{(1-c_0)^n}{(1-c_0)^n+c_1^n} > \frac{(1-c_0)^m}{(1-c_0)^m+c_1^m}.

$

Expanding the inequality:

$

((1-c_0)^m+c_1^m)(1-c_0)^n > ((1-c_0)^n+c_1^n)(1-c_0)^m.

$

$

(1-c_0)^n(1-c_0)^m+c_1^m(1-c_0)^n > (1-c_0)^n(1-c_0)^m+c_1^n(1-c_0)^m.

$

$

c_1^m(1-c_0)^n > c_1^n(1-c_0)^m.

$

$

(1-c_0)^{n-m} > c_1^{n-m}.

$

Since $c_0,c_1<0.5$, it follows that $1-c_0>c_1$. Thus, the inequality holds.

As a corollary we can show the following two properties.

1. If two nodes have the same degree, the node connected to more nodes labeled 1 should have a higher probability of being labeled 0.
2. If two nodes are connected only to nodes labeled 1, the node with the higher degree should have a higher probability of being labeled 0.

Although these lemmas and corollary may not reflect the real-world scenario, analyzing properties of a model is an important step towards understanding its performance.