\left| \frac{1}{\varepsilon}(\mathcal{N}^* \textbf{e}^*)_2 \partial_Y \tilde{u}^P \right|_{l,\rho',0,\theta'} \leq C  \left| \frac{1}{Y}\int \limits_0^Y \partial_x \left( \mathcal{N}^* \textbf{e}^* \right)_1 d Y' \right|_{l,\rho',0,\theta'} \sup \limits_Y \left| Y \partial_Y \tilde{u}^P \right|_{l,\rho'} \leq \\ C \left| \partial_x \left( \mathcal{N}^* \textbf{e}^* \right)_1 \right|_{l,\rho',0,\theta'} \leq C \int \limits_0^t \frac{|\textbf{e}^*|_{l,\rho(s),0,\theta'}}{\rho(s)-\rho'} d s.
\end{split}
\end{equation}

In the first inequality we used algebra property <ref>, in the second inequality we used the boundedness of $\sup \limits_Y \left| Y \partial_Y \tilde{u}^P \right|_{l,\rho'}$ (both for the regular and for the singular part) and the fact that the average operator is bounded from $L^2$ to $L^2$ (is bounded by the maximal function, so its trivial), and in the last inequality we used proposition <ref>. With a similar argument we have that
\begin{equation}
\left| \frac{1}{\varepsilon}(\mathcal{N}^* \textbf{e}^*)_2 \partial_{YY} \tilde{u}^P \right|_{l-1,\rho',0,\theta'} \leq C \left( 1 + \frac{1}{t^{1/2}} \right) \int \limits_0^t |\textbf{e}^*|_{l,\rho',0,\theta'} ds
\end{equation}

\begin{equation}\label{ultimaquasicontr}
\begin{split}
\left| \frac{1}{\varepsilon}\partial_Y (\mathcal{N}^* \textbf{e}^*)_2 \partial_{Y} \tilde{u}^P \right|_{l-1,\rho',0,\theta'}= \left| \partial_x(\mathcal{N}^* \textbf{e}^*)_1 \partial_{Y} \tilde{u}^P \right|_{l-1,\rho',0,\theta'} \leq \\  C \left( 1 + \frac{1}{t^{1/2}} \right) \int \limits_0^t |\textbf{e}^*|_{l,\rho',0,\theta'} ds
\end{split}.
\end{equation}

[1]
R. Alexandre, Y.-G. Wang, C.-J. Xu, and T. Yang, Well-posedness of
the Prandtl equation in Sobolev spaces, Journal of the American
Mathematical Society, 28 (2015), pp. 745–784.

[2]
Asano, Zero-viscosity limit of the incompressible Navier-Stokes
equations, Mathematical Analysis of Fluid and Plasma Dynamics,
Sūrikaisekikenkyūsho Kōkyūroku 656, Kyoto Univ., Res. Inst. Math. Sci.,
Kyoto,  (1988), pp. 105–128.

[3]
C. Bardos and S. Benachour, Domaine d'analycité des solutions de
l'équation d'Euler dans un ouvert de $\mathbb{R}^{n}$, Ann. Scuola
Norm. Sup. Pisa Cl. Sci. (4), 4 (1977), pp. 647–687.

[4]
C. W. Bardos and E. S. Titi, Mathematics and turbulence: where do we
stand?, Journal of Turbulence, 14 (2013), pp. 42–76.

[5]
G. K. Batchelor, An Introduction to Fluid Dynamics, Cambridge
Mathematical Library, Cambridge University Press, 2000.

[6]
J. Bona and J. Wu, The zero-viscosity limit of the 2D
Navier-Stokes equations, Studies in Applied Mathematics, 109 (2002),
pp. 265–278,
<https://www.scopus.com/inward/record.uri?eid=2-s2.0-0036872955   doi=10.1111

[7]
J. P. Boyd and N. Flyer, Compatibility conditions for time-dependent
partial differential equations and the rate of convergence of Chebyshev and
Fourier spectral methods, Computer Methods in Applied Mechanics and
Engineering, 175 (1999), pp. 281 – 309,

[8]
R. Caflisch and M. Sammartino, Navier-stokes equations on an
exterior circular domain: Construction of the solution and the zero viscosity
limit, Comptes Rendus de l'Academie des Sciences - Series I: Mathematics,
324 (1997), pp. 861–866.

[9]
M. Cannone, M. Lombardo, and M. Sammartino, Well-posedness of
Prandtl equations with non-compatible data, Nonlinearity, 26 (2013),
pp. 3077–, <https://doi.org/10.1088/0951-7715/26/12/3077>.

[10]
M. Cannone, F. Planchon, and M. Schonbek, Strong solutions to the
incompressible Navier Stokes equations in the half space, Communications
in Partial Differential Equations, 25 (2000), pp. 903–924,

[11]
Q. Chen, Z. Qin, and R. Temam, Treatment of incompatible initial and
boundary data for parabolic equations in higher dimension, 2010,

[12]
Q. Chen, Z. Qin, and R. Temam, Numerical resolution near t=0 of
nonlinear evolution equations in the presence of corner singularities in
space dimension 1, Communications in Computational Physics, 9 (2011),
pp. 568–586.

[13]
W. Cheng and X. Wang, Discrete Kato-type theorem on inviscid limit
of navier-stokes flows, Journal of Mathematical Physics, 48 (2007).

[14]
P. Constantin, T. Elgindi, M. Ignatova, and V. Vicol, Remarks on the
inviscid limit for the Navier-Stokes equations for uniformly bounded
velocity fields, SIAM Journal on Mathematical Analysis, 49 (2017),
pp. 1932–1946.

[15]
P. Constantin, I. Kukavica, and V. Vicol, On the inviscid limit of
the Navier-Stokes equations, Proceedings of the American Mathematical
Society, 143 (2015), pp. 3075–3090.

[16]
P. Constantin, M. Lopes Filho, H. Nussenzveig Lopes, and V. Vicol, Vorticity measures and the inviscid limit, Archive for Rational Mechanics
and Analysis, 234 (2019), pp. 575–593.

[17]
P. Constantin and V. Vicol, Remarks on high Reynolds numbers
hydrodynamics and the inviscid limit, Journal of Nonlinear Science, 28
(2018), pp. 711–724.

[18]
H. Dietert and D. Gérard-Varet, Well-posedness of the prandtl
equations without any structural assumption, Annals of PDE, 5 (2019).

[19]
T. Drivas and H. Nguyen, Remarks on the emergence of weak Euler
solutions in the vanishing viscosity limit, Journal of Nonlinear Science, 29
(2019), pp. 709–721.

[20]
M. Fei, T. Tao, and Z. Zhang, On the zero-viscosity limit of the
Navier–Stokes equations in ${R_+^3}$ without analyticity, Journal des
Mathematiques Pures et Appliquees, 112 (2018), pp. 170–229.

[21]
F. Gargano, M. Sammartino, and V. Sciacca, High Reynolds number
Navier–Stokes solutions and boundary layer separation induced by a
rectilinear vortex, Computers and Fluids, 52 (2011), p. 73–91.

[22]
F. Gargano, M. Sammartino, V. Sciacca, and K. W. Cassel, Analysis of
complex singularities in high-Reynolds-number Navier–Stokes
solutions, Journal of Fluid Mechanics, 747 (2014), p. 381–421.

[23]
D. Gérard-Varet and E. Dormy, On the ill-posedness of the
Prandtl equation, Journal of the American Mathematical Society, 23 (2010),
pp. 591–609.

[24]
D. Gérard-Varet and N. Masmoudi, Well-posedness for the
Prandtl system without analyticity or monotonicity, Annales Scientifiques
de l'Ecole Normale Superieure, 48 (2015), pp. 1273–1325.

[25]
D. Gérard-Varet and T. Nguyen, Remarks on the ill-posedness of
the Prandtl equation, Asymptotic Analysis, 77 (2012), pp. 71–88.

[26]
G.-M. Gie, Asymptotic expansion of the Stokes solutions at small
viscosity: The case of non-compatible initial data, Communications in
Mathematical Sciences, 12 (2013), pp. 383–400.

[27]
G.-M. Gie, J. Kelliher, and A. Mazzucato, Boundary layers for the
Navier–Stokes equations linearized around a stationary euler flow,
Journal of Mathematical Fluid Mechanics, 20 (2018), pp. 1–22.

[28]
E. Grenier, On the nonlinear instability of Euler and Prandtl
equations, Communications on Pure and Applied Mathematics, 53 (2000),
pp. 1067–1091.

[29]
Y. Guo and T. Nguyen, A note on Prandtl boundary layers,
Communications on Pure and Applied Mathematics, 64 (2011), pp. 1416–1438.

[30]
M. Hamouda, R. Temam, and L. Zhang, Modeling the LID driven flow:
Theory and computation, International Journal of Numerical Analysis and
Modeling, 14 (2017), pp. 313–341.

[31]
D. Han, A. Mazzucato, D. Niu, and X. Wang, Boundary layer for a
class of nonlinear pipe flow, Journal of Differential Equations, 252 (2012),
pp. 6387–6413.

[32]
T. Kato, Remarks on the zero viscosity limit for nonstationary
Navier-Stokes flows with boundary, In: Seminar on Partial Differential
Equations, in: Math. Sci. Res. Inst. Publ.,  (1984), pp. 85–98.

[33]
J. Kelliher, Vanishing viscosity and the accumulation of vorticity
on the boundary, Commun. Math. Sci., 6 (2008), pp. 869–880.

[34]
J. Kelliher, On the vanishing viscosity limit in a disk,
Mathematische Annalen, 343 (2009), pp. 701–726.

[35]
J. Kelliher, Observations on the vanishing viscosity limit,
Transactions of the American Mathematical Society, 369 (2017),
pp. 2003–2027.

[36]
I. Kukavica, N. Masmoudi, V. Vicol, and T. Wong, On the local
well-posedness of the Prandtl and hydrostatic Euler equations with
multiple monotonicity regions, SIAM Journal on Mathematical Analysis, 46
(2014), pp. 3865–3890.

[37]
I. Kukavica and V. Vicol, On the local existence of analytic
solutions to the Prandtl boundary layer equations, Communications in
Mathematical Sciences, 11 (2013),

[38]
I. Kukavica, V. Vicol, and F. Wang, The inviscid limit for the
navier–stokes equations with data analytic only near the boundary, Archive
for Rational Mechanics and Analysis, 237 (2020), pp. 779–827.

[39]
C. Levermore and M. Oliver, Analyticity of solutions for a
generalized Euler equation, Journal of Differential Equations, 133 (1997),
pp. 321–339.

[40]
W.-X. Li and T. Yang, Well-posedness in Gevrey function spaces for
the Prandtl equations with non-degenerate critical points, Journal of the
European Mathematical Society, 22 (2020), pp. 717–775.

[41]
C.-J. Liu, Y.-G. Wang, and T. Yang, On the ill-posedness of the
Prandtl equations in three-dimensional space, Archive for Rational
Mechanics and Analysis, 220 (2016), pp. 83–108.

[42]
C.-J. Liu, Y.-G. Wang, and T. Yang, A well-posedness theory for the
prandtl equations in three space variables, Advances in Mathematics, 308
(2017), pp. 1074–1126.

[43]
C.-J. Liu and T. Yang, Ill-posedness of the Prandtl equations in
Sobolev spaces around a shear flow with general decay, Journal des
Mathematiques Pures et Appliquees, 108 (2017), pp. 150–162.

[44]
M. Lombardo, M. Cannone, and M. Sammartino, Well-posedness of the
boundary layer equations, SIAM Journal on Mathematical Analysis, 35 (2003),

[45]
M. Lopes Filho, A. Mazzucato, and H. Nussenzveig Lopes, Vanishing
viscosity limit for incompressible flow inside a rotating circle, Physica D:
Nonlinear Phenomena, 237 (2008), pp. 1324–1333.

[46]
M. Lopes Filho, A. Mazzucato, H. Nussenzveig Lopes, and M. Taylor, Vanishing viscosity limits and boundary layers for circularly symmetric 2D
flows, Bulletin of the Brazilian Mathematical Society, 39 (2008),
pp. 471–513.

[47]
Y. Maekawa, On the inviscid limit problem of the vorticity equations
for viscous incompressible flows in the half-plane, Communications on Pure
and Applied Mathematics, 67 (2014), pp. 1045–1128,

[48]
Y. Maekawa and A. Mazzucato, The Inviscid Limit and Boundary Layers
for Navier-Stokes Flows, Springer International Publishing, Cham, 2016,
pp. 1–48.

[49]
P. Maremonti, Stokes and Navier-Stokes problems in the
half-space: Existence and uniqueness of solutions non-converging to a limit
at infinity, Zapiski Nauch. Sem. POMI, 362 (2008), pp. 176–240.

[50]
N. Masmoudi, The Euler limit of the Navier-Stokes equations,
and rotating fluids with boundary, Archive for Rational Mechanics and
Analysis, 142 (1998), pp. 375–394.

[51]
N. Masmoudi and T. Wong, Local-in-time existence and uniqueness of
solutions to the prandtl equations by energy methods, Communications on Pure
and Applied Mathematics, 68 (2015), pp. 1683–1741,
<https://www.scopus.com/inward/record.uri?eid=2-s2.0-84938958766   doi=10.1002

[52]
T. Nguyen and T. Nguyen, The inviscid limit of Navier-Stokes
equations for analytic data on the half-space, Archive for Rational
Mechanics and Analysis, 230 (2018), pp. 1103–1129.

[53]
A. V. Obabko and K. W. Cassel, Navier–Stokes solutions of
unsteady separation induced by a vortex, Journal of Fluid Mechanics, 465
(2002), p. 99–130.

[54]
O. Oleinik and V. Samokhin, Mathematical Models in Boundary Layer
Theory, Applied mathematics and mathematical computation, Chapman & Hall,

[55]
R. Paley and N. Wiener, Fourier Transforms in the Complex Domain,
no. v. 19 in Amer. Math. Soc. Colloquium pub, American Mathematical Society,
1934, <https://books.google.it/books?id=gOSVAwAAQBAJ>.

[56]
M. Sammartino and R. Caflisch, Zero viscosity limit for analytic
solutions of the Navier- Stokes equation on a half-space I. existence
for Euler and Prandtl equations, Communications in Mathematical Physics,
192 (1998), pp. 433–461.

[57]
M. Sammartino and R. Caflisch, Zero viscosity limit for analytic
solutions of the Navier-Stokes equation on a half-space II.
construction of the Navier-Stokes solution, Comm. Math. Phys., 192
(1998), pp. 463–491.

[58]
R. C. Sir Horace Lamb M.A. LL.D. Sc.D. F.R.S., Hydrodynamics,
Cambridge Mathematical Library, Cambridge University Press, 6 ed., 1975.

[59]
R. Temam, Suitable initial conditions, J. Comput. Phys., 218
(2006), pp. 443–450, <https://doi.org/10.1016/j.jcp.2006.03.033>.

[60]
R. Temam and X. Wang, On the behavior of the solutions of the
Navier-Stokes equations at vanishing viscosity, Annali della Scuola
Normale Superiore di Pisa - Classe di Scienze, Ser. 4, 25 (1997),
pp. 807–828.

[61]
S. Ukai, A solution formula for the Stokes equation in ${R}^n$,
Communications on Pure and Applied Mathematics, 40 (1987), pp. 611–621,

[62]
M. van Dyke, Perturbation Methods in Fluid Mechanics, Academic
Press, New York, 1964.

[63]
C. Wang, Y. Wang, and Z. Zhang, Zero-viscosity limit of the
Navier–Stokes equations in the analytic setting, Archive for Rational
Mechanics and Analysis, 224 (2017), pp. 555–595.

[64]
F. Wang, The three-dimensional inviscid limit problem with data
analytic near the boundary, SIAM J. Math. Anal., 52 (2020), pp. 3520–3545.

[65]
X. Wang, A Kato type theorem on zero viscosity limit of
Navier-Stokes flows, Indiana Univ. Math. J., 50 (2001), pp. 223–241.


# Posterior Label Smoothing for Node Classification

Jaeseung Heo
Graduate School of Artificial Intelligence
POSTECH
Republic of Korea
<EMAIL_ADDRESS>
&Moonjeong Park
Graduate School of Artificial Intelligence
POSTECH
Republic of Korea
<EMAIL_ADDRESS>
Dongwoo Kim
Graduate School of Artificial Intelligence
Department of Computer Science & Engineering
POSTECH
Republic of Korea
<EMAIL_ADDRESS>

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

##  1 Introduction

Adding a uniform noise to the ground truth labels has shown remarkable success
in training neural networks for various classification tasks, including image
classification and natural language processing (Szegedy et al., 2016a; Vaswani
et al., 2017; Müller et al., 2019; Zhang et al., 2021). Despite its
simplicity, label smoothing acts as a regularizer for the output distribution
and improves generalization performance (Pereyra et al., 2017). More
sophisticated soft labeling approaches have been proposed based on the
theoretical analysis of label smoothing (Li et al., 2020; Lienen and
Hüllermeier, 2021). However, the usefulness of smoothing has been under-
explored in the graph domain, especially for node classification tasks.

In this work, we propose a _simple yet effective_ smoothing method for
transductive node classification tasks. Inspired by the previous work
suggesting predicting the local context of a node (Hu et al., 2019; Rong et
al., 2020), such as subgraph prediction, helps to learn better
representations, we propose a smoothing method that can potentially reflect
the local context of the target node. To encode the neighborhood information
into the node label, we propose to relabel the node with a posterior
distribution of the label given neighborhood labels.

Under the assumption that the neighborhood labels are conditionally
independent given the label of the node to be relabeled, we factorize the
likelihood into the product of conditional distributions between two adjacent
nodes. To compute the posterior, we estimate the conditionals and prior from a
graph’s global label statistics, making the posterior incorporate the local
structure and global label distributions. Since the posterior obtained in this
way does not preserve the ground truth label, we finally interpolate the
posterior with the ground truth label, resulting in a soft label.

The posterior, however, may pose high variance when there are few numbers of
neighborhood nodes. To mitigate the issue with the sparse labels, we further
propose iterative pseudo labeling to re-estimate the likelihood and prior
based on the pseudo labels. Specifically, we use the pseudo labels of
validation and test sets to update the likelihood and prior, along with the
ground truth labels of the training set.

We apply our smoothing method to seven different baseline neural network
models, including MLP and variants of graph neural networks, and test its
performance on 10 benchmark node classification datasets. Our empirical study
finds that the soft label with iterative pseudo labeling improves the accuracy
in 67 out of 70 cases despite its simplicity. We analyze the cases where the
soft label decreases the accuracy and reveals characteristics of label
distributions with which the soft labeling may not work. Further analysis
shows that using local neighborhood structure and global label statistics is
the key to its success. Through the loss curve analysis, we find that the soft
label prevents over-fitting, leading to a better generalization performance in
classification.

##  2 Related work

In this section, we introduce previous studies related to our method. We begin
by discussing various node classification methods, followed by an exploration
of the application of soft labels in model training.

###  2.1 Node classification

Graph structures are utilized in various ways for node classification tasks.
Some studies propose model frameworks based on the assumption of specific
graph structures. For example, GCN (Kipf and Welling, 2016), GraphSAGE
(Hamilton et al., 2017), and GAT (Veličković et al., 2017) aggregate neighbor
node representations based on the homophilic assumption. To address the class-
imbalance problem, GraphSMOTE (Zhao et al., 2021), ImGAGN (Qu et al., 2021),
and GraphENS (Park et al., 2022) are proposed for homophilic graphs. H2GCN
(Zhu et al., 2020) and U-GCN (Jin et al., 2021) aggregate representations of
multi-hop neighbor nodes to improve performance on heterophilic graphs. Other
studies concentrate on learning graph structure. GPR-GNN (Chien et al., 2020)
and CPGNN (Zhu et al., 2021) learn graph structures to determine which nodes
to aggregate adaptively. LDS (Franceschi et al., 2019), IDGL (Chen et al.,
2020) and DHGR (Bi et al., 2022) take a graph rewiring approach, learning
optimized graph structures to refine the given structure. Besides, research
such as ChebNet (Defferrard et al., 2016), APPNP (Gasteiger et al., 2018), and
BernNet (He et al., 2021) focus on learning appropriate filters from the graph
signals.

###  2.2 Classification with soft labels

Hinton et al. (2015) demonstrate that a small student model trained using soft
labels generated by the predictions of a large teacher model shows better
performance than a model trained using one-hot labels. This approach, known as
knowledge distillation (KD), is widely adopted in computer vision (Liu et al.,
2019), natural language processing (NLP) (Jiao et al., 2020), and
recommendation systems (Tang and Wang, 2018) for compression or performance
improvement. In the graph domain, applying KD has been considered an effective
method to distill graph structure knowledge to student models. TinyGNN (Yan et
al., 2020) highlights that deep GNNs can learn information from further
neighbor nodes than shallow GNNs, and it distills local structure knowledge
from deep GNNs to shallow GNNs. NOSMOG (Tian et al., 2023) improves the
performance of multi-layer perceptrons (MLPs) on graph data by distilling
graph structure information from a GNN teacher model.

On the other hand, simpler alternatives to generate soft labels are
considered. The label smoothing (LS) (Szegedy et al., 2016a) generates soft
labels by adding uniform noise to the labels. The benefits of LS have been
widely explored. Müller et al. (2019) show that LS improves model calibration.
Lukasik et al. (2020) establish a connection between LS and label-correction
techniques, revealing LS can address label noise. LS has been widely adopted
in computer vision (Zhang et al., 2021) and NLP (Vaswani et al., 2017)
studies, but has received little attention in the graph domain.

##  3 Method

Figure 1: Overall illustration of posterior node relabeling. To relabel the
node label, we compute the posterior distribution of the label given
neighborhood labels. Note that the node features are not considered in the
relabeling process.

In this section, we describe our approach for label smoothing for the node
classification problem and provide a new training strategy that iteratively
refines the soft labels via pseudo labels obtained from the training
procedure.

###  3.1 Posterior label smoothing

Consider a transductive node classification with graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\bm{X})$, where $\mathcal{V}$ and
$\mathcal{E}$ denotes the set of nodes and edges respectively, and
$\bm{X}\in\mathbb{R}^{\lvert\mathcal{V}\rvert\times d}$ denotes
$d$-dimensional node feature matrix. For each node $i$ in a training set, we
have a label $y_{i}\in[K]$, where $K$ is the total number of classes. We use
the notation $\bm{e}_{i}\in\\{0,1\\}^{K}$ for one-hot encoding of $y_{i}$,
i.e., ${e}_{ik}=1$ if $y_{i}=k$ and $\sum_{k}{e}_{ik}=1$. In a transductive
setting, we observe the connectivity between all nodes, including the test
nodes, without having true labels of the test nodes.

We propose a simple and effective relabeling method to allocate a new label of
a node based on the label distribution of the neighborhood nodes.
Specifically, we consider the posterior distribution of node labels given
their neighbors. Let $\mathcal{N}(i)$ be a set of neighborhood nodes of node
$i$. If we assume the distribution of node labels depends on the graph
connectivity, then the posterior probability of node $i$’s label, given its
neighborhood labels, is

$P(Y_{i}=k|\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}(i)})=\frac{{P}(\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}(i)}|Y_{i}=k){P}(Y_{i}=k)}{\sum_{\ell=1}^{K}{P}(\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}(i)}|Y_{i}=\ell){P}(Y_{i}=\ell)}\;.$
(1)

The likelihood measures the joint probability of the neighborhood labels given
the label of node $i$. To obtain the likelihood, we approximate the likelihood
through the product of empirical conditional label distribution between
adjacent nodes, i.e.,
$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})$,
where $P(Y_{j}=y_{j}|Y_{i}=k,(i,j)\in\mathcal{E})$ is the conditional of
between adjacent nodes. The conditional between adjacent nodes $i$ and $j$
with label $n$ and $m$, respectively, is estimated by

$\hat{P}(Y_{j}=m|Y_{i}=n,(i,j)\in\mathcal{E})\coloneq\frac{\lvert\\{(u,v)\mid
y_{v}=m,y_{u}=n,(u,v)\in\mathcal{E}\\}\rvert}{\lvert\\{(u,v)\mid
y_{u}=n,(u,v)\in\mathcal{E}\\}\rvert}\;.$ (2)

The prior distribution is also estimated from the empirical observations. We
use the empirical proportion of label as a prior, i.e.,
$\hat{P}(Y_{i}=m)\coloneq{\lvert\\{u\mid
y_{u}=m\\}\rvert}/{\lvert\mathcal{V}\rvert}$. We also explore alternative
designs for the likelihood and compare their performances in Section 4.2.

Note that, in implementation, all empirical distributions are computed only
with the training nodes and their labels. The empirical distribution might be
updated after node relabeling through the posterior computation, but we keep
it the same throughout the relabeling process.

The posterior distribution can be used as a soft label to train the model, but
we add uniform noise $\epsilon$ to the posterior to mitigate the risk of the
posterior becoming overly confident if there are few or no neighbors. In
addition, since the most probable label from the posterior might be different
from the ground truth label, we interpolate the posterior with the ground
truth label. To this end, we obtain the soft label $\hat{\bm{e}}_{i}$ of node
$i$ as

$\hat{\bm{e}}_{i}=(1-\alpha)\tilde{\bm{e}}_{i}+\alpha\bm{e}_{i}\;,$ (3)

where $\tilde{{{e}}}_{ik}\propto
P(Y_{i}=k\mid\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}(i)})+\beta\epsilon$. $\alpha$
and $\beta$ control the importance of interpolation and uniform noise. By
enforcing $\alpha>1/2$, we can keep the most probable label of soft label the
same as the ground truth label, but we find that this condition is not
necessary in empirical experiments. We name our method as PosteL (Posterior
Label smoothing). The detailed algorithm of PosteL is shown in Algorithm 1.

Algorithm 1 PosteL: Posterior label smoothing

The set of training nodes
$\mathcal{V}_{\operatorname{train}}\subset\mathcal{V}$, the number of classes
$K$, one-hot encoding of training node labels
$\\{\bm{e}_{i}\\}_{i\in\mathcal{V}_{\operatorname{train}}}$, and
hyperparameters $\alpha$ and $\beta$.

The set of soft labels
$\\{\hat{\bm{e}}_{i}\\}_{i\in\mathcal{V}_{\operatorname{train}}}$

Estimate prior distribution for $m\in[K]$:
$\hat{P}(Y_{i}=m)=\sum_{u\in\mathcal{V}_{\operatorname{train}}}{e}_{um}/\lvert\mathcal{V}_{\operatorname{train}}\rvert$.

Define the set of training neighbors for each node $u$:
$\mathcal{N}_{\operatorname{train}}(u)=\mathcal{N}(u)\cap\mathcal{V}_{\operatorname{train}}$.

Estimate the empirical conditional for $n,m\in[K]$:
$\hat{P}(Y_{j}=m|Y_{i}=n,(i,j)\in\mathcal{E})\propto\sum_{u:u\in\mathcal{V}_{\operatorname{train}},y_{u}=n}\sum_{v\in\mathcal{N}_{\operatorname{train}}(u)}{e}_{vm}$.

for $i\in\mathcal{V}_{\operatorname{train}}$ do

Approximate likelihood:
$P(\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}_{\operatorname{train}}(i)}|Y_{i}=k)\approx\prod_{j\in\mathcal{N}_{\operatorname{train}}(i)}\hat{P}(Y_{j}=y_{j}|Y_{i}=k,(i,j)\in\mathcal{E})$.

Compute posterior distribution:
$P(Y_{i}=k\mid\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}_{\operatorname{train}}(i)})$
using Equation 1.

Add uniform noise: $\tilde{e}_{ik}\propto
P(Y_{i}=k\mid\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}_{\operatorname{train}}(i)})+\beta\epsilon$.

Obtain soft label:
$\hat{\bm{e}}_{i}=(1-\alpha)\tilde{\bm{e}}_{i}+\alpha\bm{e}_{i}$.

end for

###  3.2 Iterative pseudo labeling

Posterior relabeling is a method used to predict the label of a node based on
the labels of its neighboring nodes. However, in transductive node
classification tasks where train, validation, and test nodes coexist within
the same graph, the presence of unlabeled nodes can hinder the accurate
prediction of posterior labels. For instance, when a node has no labeled
neighbors, the likelihood becomes one, and the posterior only relies on the
prior. Moreover, in cases where labeled neighbors are scarce, noisy labels
among the neighbors can significantly compromise the posterior distribution.
Such challenges are particularly prevalent in sparse graphs. For example,
26.35% of nodes in the Cornell dataset have no neighbors with labels. In such
scenarios, the posterior relabeling can be challenging.

To address these limitations, we propose to update the likelihoods and priors
through the pseudo labels of validation and test nodes. We first train a graph
neural network with the soft labels obtained via Equation 3 and predict the
labels of validation and test nodes to obtain the pseudo labels. We choose the
most probable label as a pseudo label from the prediction. We then update the
likelihood and prior with the pseudo labels, leading to the re-calibration of
the posterior smoothing and soft labels. By repeating training and re-
calibration until the best validation loss of the predictor no longer
decreases, we can maximize the performance of node classification. We assume
that if posterior label smoothing improves classification performance with a
better estimation of likelihood and prior, the pseudo labels obtained from the
predictor can benefit the posterior estimation as long as there are not many
false pseudo labels.

##  4 Experiments

The experimental section is composed of two parts. First, we evaluate the
performance of our method for node classification through various datasets and
models. Second, we provide a comprehensive analysis of our method,
investigating the conditions under which it performs well and the importance
of each design choice.

###  4.1 Node classification

In this section, we assess the enhancements in node classification performance
across a range of datasets and backbone models. Our aim is to validate the
consistent efficacy of our method across datasets and backbone models with
diverse characteristics.

#### Datasets

We assess the performance of our method across 10 node classification
datasets. To examine the effect of our method on diverse types of graphs, we
conduct experiments on both homophilic and heterophilic graphs. Adjacent nodes
in a homophilic graph are likely to have the same label. Adjacent nodes in a
heterophilic graph are likely to have different labels. For the homophilic
datasets, we use five datasets: the citation graphs Cora, CiteSeer, and PubMed
(Sen et al., 2008; Yang et al., 2016), and the Amazon co-purchase graphs
Computers and Photo (McAuley et al., 2015). For the heterophilic datasets, we
use five datasets: the Wikipedia graphs Chameleon and Squirrel (Rozemberczki
et al., 2021), the Actor co-occurrence graph Actor (Tang et al., 2009), and
the webpage graphs Texas and Cornell (Pei et al., 2020). Detailed statistics
of each dataset are illustrated in Appendix A.

Table 1: Classification accuracy on 10 node classification datasets. $\Delta$
represents the performance improvement achieved by PosteL compared to the
backbone model trained with the ground truth label. All results of the
backbone model trained with the ground truth label are sourced from He et al.
(2021).

| Cora | CiteSeer | PubMed | Computers | Photo | Chameleon | Actor | Squirrel | Texas | Cornell
---|---|---|---|---|---|---|---|---|---|---
GCN | 87.14±1.01 | 79.86±0.67 | 86.74±0.27 | 83.32±0.33 | 88.26±0.73 | 59.61±2.21 | 33.23±1.16 | 46.78±0.87 | 77.38±3.28 | 65.90±4.43
+LS | 87.77±0.97 | 81.06±0.59 | 87.73±0.24 | 89.08±0.30 | 94.05±0.26 | 64.81±1.53 | 33.81±0.75 | 49.53±1.10 | 77.87±3.11 | 67.87±3.77
+KD | 87.90±0.90 | 80.97±0.56 | 87.03±0.29 | 88.56±0.36 | 93.64±0.31 | 64.49±1.38 | 33.33±0.78 | 49.38±0.64 | 78.03±2.62 | 63.61±5.57
+PosteL | 88.56±0.90 | 82.10±0.50 | 88.00±0.25 | 89.30±0.23 | 94.08±0.35 | 65.80±1.23 | 35.16±0.43 | 52.76±0.64 | 80.82±2.79 | 80.33±1.80
$\Delta$ | $+1.42({\color[rgb]{1,0,0}\uparrow})$ | $+2.24({\color[rgb]{1,0,0}\uparrow})$ | $+1.26({\color[rgb]{1,0,0}\uparrow})$ | $+5.98({\color[rgb]{1,0,0}\uparrow})$ | $+5.82({\color[rgb]{1,0,0}\uparrow})$ | $+6.19({\color[rgb]{1,0,0}\uparrow})$ | $+1.93({\color[rgb]{1,0,0}\uparrow})$ | $+5.98({\color[rgb]{1,0,0}\uparrow})$ | $+3.44({\color[rgb]{1,0,0}\uparrow})$ | $+14.43({\color[rgb]{1,0,0}\uparrow})$
GAT | 88.03±0.79 | 80.52±0.71 | 87.04±0.24 | 83.32±0.39 | 90.94±0.68 | 63.13±1.93 | 33.93±2.47 | 44.49±0.88 | 80.82±2.13 | 78.21±2.95
+LS | 88.69±0.99 | 81.27±0.86 | 86.33±0.32 | 88.95±0.31 | 94.06±0.39 | 65.16±1.49 | 34.55±1.15 | 45.94±1.60 | 78.69±4.10 | 74.10±4.10
+KD | 87.47±0.94 | 80.79±0.60 | 86.54±0.31 | 88.99±0.46 | 93.76±0.31 | 65.14±1.47 | 35.13±1.36 | 43.86±0.85 | 79.02±2.46 | 73.44±2.46
+PosteL | 89.21±1.08 | 82.13±0.64 | 87.08±0.19 | 89.60±0.29 | 94.31±0.31 | 66.28±1.14 | 35.92±0.72 | 49.38±1.05 | 80.33±2.62 | 80.33±1.81
$\Delta$ | $+1.18({\color[rgb]{1,0,0}\uparrow})$ | $+1.61({\color[rgb]{1,0,0}\uparrow})$ | $+0.04({\color[rgb]{1,0,0}\uparrow})$ | $+6.28({\color[rgb]{1,0,0}\uparrow})$ | $+3.37({\color[rgb]{1,0,0}\uparrow})$ | $+3.15({\color[rgb]{1,0,0}\uparrow})$ | $+1.99({\color[rgb]{1,0,0}\uparrow})$ | $+4.89({\color[rgb]{1,0,0}\uparrow})$ | $-0.49({\color[rgb]{0,0,1}\downarrow})$ | $+2.12({\color[rgb]{1,0,0}\uparrow})$
APPNP | 88.14±0.73 | 80.47±0.74 | 88.12±0.31 | 85.32±0.37 | 88.51±0.31 | 51.84±1.82 | 39.66±0.55 | 34.71±0.57 | 90.98±1.64 | 91.81±1.96
+LS | 89.01±0.64 | 81.58±0.61 | 88.90±0.32 | 87.28±0.27 | 94.34±0.23 | 53.98±1.47 | 39.44±0.78 | 36.81±0.98 | 91.31±1.48 | 89.51±1.81
+KD | 89.16±0.74 | 81.88±0.61 | 88.04±0.39 | 86.28±0.44 | 93.85±0.26 | 52.17±1.23 | 41.43±0.95 | 35.28±1.10 | 90.33±1.64 | 91.48±1.97
+PosteL | 89.62±0.84 | 82.47±0.66 | 89.17±0.26 | 87.46±0.29 | 94.42±0.24 | 53.83±1.66 | 40.18±0.70 | 36.71±0.60 | 92.13±1.48 | 93.44±1.64
$\Delta$ | $+1.48({\color[rgb]{1,0,0}\uparrow})$ | $+2.00({\color[rgb]{1,0,0}\uparrow})$ | $+1.05({\color[rgb]{1,0,0}\uparrow})$ | $+2.14({\color[rgb]{1,0,0}\uparrow})$ | $+5.91({\color[rgb]{1,0,0}\uparrow})$ | $+1.99({\color[rgb]{1,0,0}\uparrow})$ | $+0.52({\color[rgb]{1,0,0}\uparrow})$ | $+2.00({\color[rgb]{1,0,0}\uparrow})$ | $+1.15({\color[rgb]{1,0,0}\uparrow})$ | $+1.63({\color[rgb]{1,0,0}\uparrow})$
MLP | 76.96±0.95 | 76.58±0.88 | 85.94±0.22 | 82.85±0.38 | 84.72±0.34 | 46.85±1.51 | 40.19±0.56 | 31.03±1.18 | 91.45±1.14 | 90.82±1.63
+LS | 77.21±0.97 | 76.82±0.66 | 86.14±0.35 | 83.62±0.88 | 89.46±0.44 | 48.23±1.23 | 39.75±0.63 | 31.10±0.80 | 90.98±1.64 | 90.98±1.31
+KD | 76.32±0.94 | 77.75±0.75 | 85.10±0.29 | 83.89±0.53 | 88.23±0.38 | 47.40±1.75 | 41.32±0.75 | 32.58±0.83 | 89.34±1.97 | 91.80±1.15
+PosteL | 78.39±0.94 | 78.40±0.71 | 86.51±0.33 | 84.20±0.55 | 89.90±0.27 | 48.51±1.66 | 40.15±0.46 | 33.11±0.60 | 92.95±1.31 | 93.61±1.80
$\Delta$ | $+1.43({\color[rgb]{1,0,0}\uparrow})$ | $+1.82({\color[rgb]{1,0,0}\uparrow})$ | $+0.57({\color[rgb]{1,0,0}\uparrow})$ | $+1.35({\color[rgb]{1,0,0}\uparrow})$ | $+5.18({\color[rgb]{1,0,0}\uparrow})$ | $+1.66({\color[rgb]{1,0,0}\uparrow})$ | $-0.04({\color[rgb]{0,0,1}\downarrow})$ | $+2.08({\color[rgb]{1,0,0}\uparrow})$ | $+1.50({\color[rgb]{1,0,0}\uparrow})$ | $+2.79({\color[rgb]{1,0,0}\uparrow})$
ChebNet | 86.67±0.82 | 79.11±0.75 | 87.95±0.28 | 87.54±0.43 | 93.77±0.32 | 59.28±1.25 | 37.61±0.89 | 40.55±0.42 | 86.22±2.45 | 83.93±2.13
+LS | 87.22±0.99 | 79.70±0.63 | 88.48±0.29 | 89.55±0.38 | 94.53±0.37 | 66.41±1.16 | 39.39±0.73 | 42.55±1.11 | 87.21±2.62 | 84.59±2.30
+KD | 87.36±0.95 | 80.80±0.72 | 88.41±0.20 | 89.81±0.30 | 94.76±0.30 | 61.47±1.23 | 40.68±0.50 | 43.88±1.97 | 84.75±3.61 | 83.61±2.30
+PosteL | 88.57±0.92 | 82.48±0.52 | 89.20±0.31 | 89.95±0.40 | 94.87±0.25 | 66.83±0.77 | 39.56±0.51 | 50.87±0.90 | 86.39±2.46 | 88.52±2.63
$\Delta$ | $+1.90({\color[rgb]{1,0,0}\uparrow})$ | $+3.37({\color[rgb]{1,0,0}\uparrow})$ | $+1.25({\color[rgb]{1,0,0}\uparrow})$ | $+2.41({\color[rgb]{1,0,0}\uparrow})$ | $+1.10({\color[rgb]{1,0,0}\uparrow})$ | $+7.55({\color[rgb]{1,0,0}\uparrow})$ | $+1.95({\color[rgb]{1,0,0}\uparrow})$ | $+10.32({\color[rgb]{1,0,0}\uparrow})$ | $+0.17({\color[rgb]{1,0,0}\uparrow})$ | $+4.59({\color[rgb]{1,0,0}\uparrow})$
GPR-GNN | 88.57±0.69 | 80.12±0.83 | 88.46±0.33 | 86.85±0.25 | 93.85±0.28 | 67.28±1.09 | 39.92±0.67 | 50.15±1.92 | 92.95±1.31 | 91.37±1.81
+LS | 88.82±0.99 | 79.78±1.06 | 88.24±0.42 | 88.39±0.48 | 93.97±0.33 | 67.90±1.01 | 39.72±0.70 | 53.39±1.80 | 92.79±1.15 | 90.49±2.46
+KD | 89.33±1.03 | 81.24±0.85 | 89.85±0.56 | 87.88±1.11 | 94.23±0.51 | 66.76±1.31 | 42.00±0.63 | 53.26±1.07 | 94.26±1.48 | 88.52±1.97
+PosteL | 89.20±1.07 | 81.21±0.64 | 90.57±0.31 | 89.84±0.43 | 94.76±0.38 | 68.38±1.12 | 40.08±0.69 | 53.54±0.79 | 93.28±1.31 | 92.46±0.99
$\Delta$ | $+0.63({\color[rgb]{1,0,0}\uparrow})$ | $+1.09({\color[rgb]{1,0,0}\uparrow})$ | $+2.11({\color[rgb]{1,0,0}\uparrow})$ | $+2.99({\color[rgb]{1,0,0}\uparrow})$ | $+0.91({\color[rgb]{1,0,0}\uparrow})$ | $+1.10({\color[rgb]{1,0,0}\uparrow})$ | $+0.16({\color[rgb]{1,0,0}\uparrow})$ | $+3.39({\color[rgb]{1,0,0}\uparrow})$ | $+0.33({\color[rgb]{1,0,0}\uparrow})$ | $+1.09({\color[rgb]{1,0,0}\uparrow})$
BernNet | 88.52±0.95 | 80.09±0.79 | 88.48±0.41 | 87.64±0.44 | 93.63±0.35 | 68.29±1.58 | 41.79±1.01 | 51.35±0.73 | 93.12±0.65 | 92.13±1.64
+LS | 88.80±0.92 | 80.37±1.05 | 87.40±0.27 | 88.32±0.38 | 93.70±0.21 | 69.58±0.94 | 39.60±0.53 | 52.39±0.60 | 91.80±1.80 | 90.49±1.48
+KD | 87.78±0.99 | 81.20±0.86 | 87.59±0.41 | 87.35±0.40 | 93.96±0.40 | 67.75±1.42 | 41.04±0.89 | 51.25±0.83 | 93.61±1.31 | 90.33±2.30
+PosteL | 89.39±0.92 | 82.46±0.67 | 89.07±0.29 | 89.56±0.35 | 94.54±0.36 | 69.65±0.83 | 40.40±0.67 | 53.11±0.87 | 93.93±1.15 | 92.95±1.80
$\Delta$ | $+0.87({\color[rgb]{1,0,0}\uparrow})$ | $+2.37({\color[rgb]{1,0,0}\uparrow})$ | $+0.59({\color[rgb]{1,0,0}\uparrow})$ | $+1.92({\color[rgb]{1,0,0}\uparrow})$ | $+0.91({\color[rgb]{1,0,0}\uparrow})$ | $+1.36({\color[rgb]{1,0,0}\uparrow})$ | $-1.39({\color[rgb]{0,0,1}\downarrow})$ | $+1.76({\color[rgb]{1,0,0}\uparrow})$ | $+0.81({\color[rgb]{1,0,0}\uparrow})$ | $+0.82({\color[rgb]{1,0,0}\uparrow})$

#### Experimental setup and baselines

We evaluate the performance of PosteL across various backbone models, ranging
from MLP, which ignores underlying structure between nodes, to six widely used
graph neural networks: GCN (Kipf and Welling, 2016), GAT (Veličković et al.,
2017), APPNP (Gasteiger et al., 2018), ChebNet (Defferrard et al., 2016), GPR-
GNN (Chien et al., 2020), and BernNet (He et al., 2021). We follow the
experimental setup and backbone implementations of He et al. (2021).
Specifically, we use fixed 10 train, validation, and test splits with ratios
of 60%/20%/20%, respectively, and measure the accuracy at the lowest
validation loss. We report the mean performance and 95% confidence interval.
The model is trained for 1,000 epochs, and we apply early stopping when
validation loss does not decrease during the last 200 epochs. For all models,
the learning rate is validated within $\\{0.001,0.002,0.01,0.05\\}$, and
weight decay within $\\{0,0.0005\\}$. The search spaces of the other model-
dependent hyperparameters are provided in Appendix B. We validate two
hyperparameters for PosteL: posterior label ratio
$\alpha\in\\{0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0\\}$ and uniform noise
ratio $\beta\in\\{0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9\\}$.

We compare our method with two different soft labeling methods, including
label smoothing (LS) (Szegedy et al., 2016b) and knowledge distillation (KD)
(Hinton et al., 2015). For KD, we use an ensemble of average logits from three
independently trained GNNs as a teacher model. The temperature parameter for
KD is set to four following the previous work (Stanton et al., 2021).

#### Results

In Table 1, the classification accuracy and 95% confidence interval for each
of the seven models across the 10 datasets are presented. In most cases,
PosteL outperforms baseline methods across various settings, demonstrating
significant performance enhancements and validating its effectiveness for node
classification. Specifically, our method performs better in 67 cases out of 70
settings against the ground truth labels. Furthermore, among these settings,
39 cases show improvements over the 95% confidence interval. Notably, on the
Cornell dataset with the GCN backbone, our method achieves a substantial
performance enhancement of 14.43%. When compared to the other soft label
methods, PosteL performs better in most cases as well. The knowledge
distillation method shows comparable performance with the GPR-GNN baseline,
but even in this case, there are marginal differences between the two
approaches.

###  4.2 Analysis

In this section, we analyze the main experimental result from various
perspectives, including design choices, ablations, and computational
complexity.

#### Learning curves analysis

Figure 2: Loss curve of GCN trained on PosteL labels and ground truth labels
on the Squirrel dataset.

We investigate the influence of soft labels on the learning dynamics of GNNs
by visualizing the loss function of GCNs with and without soft labels. Figure
2 visualizes the differences between training, validation, and test losses
with and without the PosteL labels on the Squirrel dataset. From the training
loss, we observe that the cross entropy with the PosteL labels converges to a
higher loss than that with the ground truth labels. The curve shows that
predicting soft labels is more difficult than predicting ground truth labels.
On the other hand, the validation and test losses with the soft labels
converge to lower losses than those with the ground truth labels. Especially,
up to 200 epochs, we observe that no overfitting happens with the soft labels.
We conjecture that predicting the correct PosteL label implies the correct
prediction of the local neighborhood structure since the PosteL labels contain
the local neighborhood information of the target node. Hence, the model
trained with PosteL labels could have a better understanding of the graph
structure, potentially leading to a better generalization performance. A
similar context prediction approach has been proposed as a pertaining method
in previous studies (Hu et al., 2019; Rong et al., 2020). We provide the same
curves for all datasets in Figure 8 and Figure 10 in Appendix D. All curves
across all datasets show similar patterns.

#### Influence of neighborhood label distribution

(a) PubMed

(b) Texas

(c) Actor

Figure 3: Empirical conditional distributions between two adjacent nodes. We
omit the adjacent condition $(i,j)\in\mathcal{E}$ from the figures for
simplicity.

Our approach assumes that the distribution of neighborhood labels varies
depending on the label of the target node. If there are no significant
differences between the neighborhood’s label distributions, the posterior
relabeling assigns similar soft labels for all nodes, making our method
similar to the uniform noise method.

Figure 3 shows the neighborhood label distribution for three different
datasets. In the PubMed and Texas datasets, we observe a notable difference in
the conditionals when w.r.t the different labels of a target node. The PubMed
dataset is known to be homophilic, where nodes with the same labels are likely
to be connected, and the conditional distributions match the characteristics
of the homophilic dataset. The Texas dataset, a heterophilic dataset, shows
that some pairs of labels more frequently appear in the graph. For example,
when the target node has the label of 1, their neighborhoods will likely have
the label of 5. On the other hand, the conditionals of the Actor dataset do
not vary much regarding the label of the target node. In such a case, the
prior will likely dominate the posterior. Therefore, the posterior may not
provide useful information about neighborhood nodes, potentially limiting the
effectiveness of our method. This analysis aligns with the results in Table 1,
where the improvement of the Actor dataset is less significant than those of
the PubMed and Texas datasets. The neighborhood label distributions for all
datasets are provided in Figure 11 and Figure 12 in Appendix E.

#### Visualization of node embeddings

Figure 5 presents the t-SNE (Van der Maaten and Hinton, 2008) plots of node
embeddings from the GCN with the Chameleon and Squirrel datasets. The node
color represents the label. For each dataset, the left plot visualizes the
embeddings with the ground truth labels, while the right plot visualizes the
embeddings with PosteL labels. The visualization shows that the embeddings
from the soft labels form tighter clusters compared to those trained with the
ground truth labels. This visualization results coincide with the t-SNE
visualization of the previous work of Müller et al. (2019).

(a) Chameleon

(b) Squirrel

Figure 5: t-SNE plots of the final layer representation of the Chameleon and
Squirrel datasets. For each dataset, the left figure displays the
representations trained on the ground truth labels, while the right figure
displays the representations trained on the PosteL labels.

#### Effect of iterative pseudo labeling

We evaluate the impact of iterative pseudo labeling by analyzing the loss
curve at each iteration. Figure 6 illustrates the loss curves for different
iterations on the Cornell dataset. As the iteration progresses, the validation
and test losses after 1,000 epochs keep decreasing. In this example, the model
performs best after four iteration steps. We find that the best validation
performance is obtained from 1.13 iterations on average. We provide the
average iteration steps in Appendix C used to report the results in Table 1.

Figure 6: The impact of the iterative pseudo labeling: loss curves of GCN on
the Cornell dataset.

#### Design choices of likelihood model

Table 2: Classification accuracy with various choices of likelihood model.
PosteL (local-1) and (local-2) indicate that the likelihood is estimated
within one- and two-hop neighbors of a target node, respectively. PosteL
(norm.), shortened from PosteL (normalized), indicates that the likelihood is
normalized based on the degree of a node.

| Cora | CiteSeer | Computers | Photo | Chameleon | Actor | Texas | Cornell
---|---|---|---|---|---|---|---|---
GCN | 87.14±1.01 | 79.86±0.67 | 83.32±0.33 | 88.26±0.73 | 59.61±2.21 | 33.23±1.16 | 77.38±3.28 | 65.90±4.43
+PosteL (local-1) | 88.26±1.07 | 81.42±0.46 | 89.08±0.31 | 93.61±0.40 | 65.36±1.25 | 33.48±1.03 | 79.02±3.11 | 71.97±4.10
+PosteL (local-2) | 88.62±0.97 | 81.92±0.42 | 88.62±0.48 | 93.95±0.37 | 65.10±1.55 | 34.63±0.46 | 78.20±2.79 | 73.28±4.10
+PosteL (norm.) | 89.00±0.99 | 81.86±0.70 | 89.30±0.39 | 94.13±0.39 | 66.00±1.14 | 34.90±0.63 | 80.33±2.95 | 80.00±1.97
+PosteL | 88.56±0.90 | 82.10±0.50 | 89.30±0.23 | 94.08±0.35 | 65.80±1.23 | 35.16±0.43 | 80.82±2.79 | 80.33±1.80

We explore various valid design choices for likelihood models. We introduce
two variants of PosteL: PosteL (normalized) and PosteL (local-$H$). In
Equation 2, each edge has an equal contribution to the conditional. The
conditional can be influenced by a few numbers of nodes with many connections.
To mitigate the importance of high-degree nodes, we alternatively test the
following conditional, denoted as PosteL (normalized):

$\hat{P}^{\text{norm.}}(Y_{j}=m|Y_{i}=n,(i,j)\in\mathcal{E})\coloneq\frac{\sum_{y_{u}=n}\sum_{v\in\mathcal{N}(u)}\frac{1}{\lvert\mathcal{N}(u)\rvert}\cdot\mathbbm{1}[y_{v}=m]}{\lvert\\{y_{u}=n\mid
u\in\mathcal{V}\\}\rvert}\;,$

where $\mathbbm{1}$ is an indicator function.

In PosteL (local-$H$), we estimate the likelihood and prior distributions of
each node from their respective $H$-hop ego graphs. Specifically, the
likelihood of PosteL (local-$H$) is formulated as follows:

$\displaystyle\hat{P}^{\text{local-$H$}}(Y_{j}=m|Y_{i}=n,(i,j)\in\mathcal{E})\coloneq\frac{\lvert\\{(u,v)|y_{v}=m,y_{u}=n,(u,v)\in\mathcal{E},u,v\in\mathcal{N}^{(H)}(i)\\}\rvert}{\lvert\\{(u,v)|y_{u}=n,(u,v)\in\mathcal{E},u,v\in\mathcal{N}^{(H)}(i)\\}\rvert}\;,$

where $\mathcal{N}^{(H)}(i)$ denotes the set of neighborhoods of node $i$
within $H$ hops. Through the local likelihood, we test the importance of
global and local statistics in the smoothing process.

Table 2 shows the comparison between these variants. The likelihood with
global statistics, e.g., PosteL and PosteL (normalized), performs better than
the local likelihood methods, e.g., PosteL (local-1) and PosteL (local-2) in
general, highlighting the importance of simultaneously utilizing global
statistics. Especially in the Cornell dataset, a significant performance gap
between PosteL and PosteL (local) is observed. PosteL (normalized)
demonstrates similar performance to PosteL.

#### Ablation studies

Table 3:  Ablation studies on three main components of PosteL on GCN. PS
stands for posterior label smoothing without uniform noise, UN stands for
uniform noise added to the posterior distribution, and IPL stands for
iterative pseudo labeling. We use ✓to indicate the presence of the
corresponding component in training and ✗ to indicate its absence. IPL with
one indicates the performance with a single pseudo labeling step.

PS | UN | IPL | Cora | CiteSeer | Computers | Photo | Chameleon | Actor | Texas | Cornell
---|---|---|---|---|---|---|---|---|---|---
✗ | ✗ | ✗ | 87.14±1.01 | 79.86±0.67 | 83.32±0.33 | 88.26±0.73 | 59.61±2.21 | 33.23±1.16 | 77.38±3.28 | 65.90±4.43
✓ | ✗ | ✗ | 88.11±1.22 | 80.95±0.52 | 88.86±0.40 | 93.55±0.30 | 64.53±1.23 | 33.48±0.62 | 78.52±2.46 | 68.52±4.43
✗ | ✓ | ✗ | 87.77±0.97 | 81.06±0.59 | 89.08±0.30 | 94.05±0.26 | 64.81±1.53 | 33.81±0.75 | 77.87±3.11 | 67.87±3.77
✓ | ✗ | ✓ | 88.56±0.90 | 81.64±0.57 | 88.70±0.27 | 93.70±0.37 | 64.25±1.93 | 34.71±0.76 | 80.82±2.79 | 80.16±1.97
✓ | ✓ | ✗ | 87.83±0.92 | 82.09±0.44 | 89.17±0.31 | 93.98±0.34 | 66.19±1.60 | 34.91±0.48 | 79.51±3.61 | 71.97±5.25
✓ | ✓ | 1 | 87.96±0.90 | 82.33±0.52 | 89.16±0.30 | 94.06±0.27 | 65.89±1.51 | 34.96±0.48 | 80.16±2.79 | 80.33±1.97
✓ | ✓ | ✓ | 88.56±0.90 | 82.10±0.50 | 89.30±0.23 | 94.08±0.35 | 65.80±1.23 | 35.16±0.43 | 80.82±2.79 | 80.33±1.80

To highlight the importance of each component in PosteL, we perform ablation
studies on three components: posterior smoothing without uniform noise (PS),
uniform smoothing (UN), and iterative pseudo labeling (IPL). Table 3 presents
the performance results from the ablation studies.

The configuration with all components included achieves the highest
performance, underscoring the significance of each component. The iterative
pseudo labeling proves effective across almost all datasets, with a
particularly notable impact on the Cornell dataset. However, even without
iterative pseudo labeling, the performance remains competitive, suggesting
that its use can be decided based on available resources. Additionally,
incorporating uniform noise into the posterior distribution enhances
performance on several datasets. Moreover, PosteL consistently outperforms the
approach using only uniform noise, a widely used label smoothing method.

#### Complexity analysis

The computational complexity of calculating the posterior label is
$O(|\mathcal{E}|K)$. Since the labeling is performed before the learning
stage, the time required to process the posterior label can be considered
negligible. The training time increases linearly w.r.t the number of
iterations with the pseudo labeling. However, experiments show that an average
of 1.13 iterations is needed, making our approach feasible without having too
many iterations. The proof of computational complexity is in Appendix C.

###  4.3 Training with sparse labels

Table 4:  Accuracy of the model trained with sparse labels. The ratio
indicates the percentage of nodes used for training.

| ratio | Cora | CiteSeer | Computers | Photo | Chameleon | Actor | Texas | Cornell
---|---|---|---|---|---|---|---|---|---
GCN | 5% | 80.03±0.57 | 70.19±0.49 | 85.32±0.60 | 92.39±0.24 | 45.96±2.48 | 25.20±0.83 | 54.23±6.35 | 50.58±5.84
+PosteL | 80.42±0.64 | 71.08±0.65 | 86.22±0.45 | 92.66±0.21 | 51.35±1.19 | 27.04±0.51 | 57.52±1.97 | 50.36±3.43
GCN | 10% | 83.05±0.51 | 72.09±0.46 | 86.68±0.59 | 92.49±0.29 | 51.55±1.67 | 26.78±0.68 | 60.08±2.56 | 53.64±3.49
+PosteL | 83.50±0.36 | 73.76±0.26 | 87.47±0.37 | 92.88±0.30 | 56.33±1.86 | 28.07±0.19 | 61.63±2.87 | 57.75±1.86
GCN | 20% | 84.46±0.68 | 73.93±0.69 | 87.12±0.33 | 93.24±0.33 | 55.57±1.18 | 27.42±0.76 | 63.33±2.05 | 52.91±2.65
+PosteL | 85.32±0.65 | 75.73±0.39 | 87.77±0.19 | 93.47±0.18 | 60.91±1.07 | 29.23±0.50 | 64.87±2.74 | 56.92±2.39
GCN | 30% | 85.76±0.46 | 75.56±0.44 | 87.02±0.49 | 93.14±0.27 | 59.41±1.08 | 28.81±0.50 | 65.64±4.36 | 60.40±3.96
+PosteL | 86.04±0.37 | 77.30±0.65 | 88.09±0.31 | 93.47±0.27 | 63.64±0.98 | 30.21±0.39 | 69.80±3.86 | 64.95±2.08
GCN | 40% | 86.32±0.43 | 77.17±0.52 | 87.88±0.58 | 93.76±0.20 | 60.44±1.20 | 29.71±0.72 | 67.88±2.47 | 62.00±2.12
+PosteL | 86.23±0.37 | 79.22±0.32 | 88.21±0.29 | 93.99±0.24 | 63.82±1.44 | 31.05±0.40 | 73.76±2.59 | 67.41±4.71

Our method relies on global statistics estimated from training nodes. However,
in scenarios where training data is sparse, the estimation of global
statistics can be challenging. To assess the effectiveness of the label
smoothing from graphs with sparse labels, we conduct experiments with varying
sizes of a training set. We vary the size of the training set from 5% to 40%
of an entire dataset and conduct the classification experiments with the same
setting used in the previous section. The percentage of validation nodes is
set to 20% for all experiments. Table 4 provides the classification
performance with sparse labels. Even in scenarios with sparse labels, PosteL
consistently outperforms models trained on ground truth labels in most cases.
These results show that our method can effectively capture global statistics
even when training data is limited.

##  5 Conclusion

In this paper, we proposed a novel posterior label smoothing method, PosteL,
designed to enhance node classification performance in graph-structured data.
Our approach integrates both local neighborhood information and global label
statistics to generate soft labels, thereby improving generalization and
mitigating overfitting. Extensive experiments across various datasets and
models demonstrated the effectiveness of PosteL, showing significant
performance gains compared to baseline methods despite its simplicity.

## References

  * Bi et al. (2022) Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang.  Make heterophily graphs better fit gnn: A graph rewiring approach.  _arXiv preprint arXiv:2209.08264_ , 2022.
  * Chen et al. (2020) Yu Chen, Lingfei Wu, and Mohammed Zaki.  Iterative deep graph learning for graph neural networks: Better and robust node embeddings.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 19314–19326. Curran Associates, Inc., 2020.
  * Chien et al. (2020) Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic.  Adaptive universal generalized pagerank graph neural network.  _arXiv preprint arXiv:2006.07988_ , 2020.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ , 29, 2016.
  * Franceschi et al. (2019) Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He.  Learning discrete structures for graph neural networks.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1972–1982. PMLR, 09–15 Jun 2019.
  * Gasteiger et al. (2018) Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  _arXiv preprint arXiv:1810.05997_ , 2018.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * He et al. (2021) Mingguo He, Zhewei Wei, Hongteng Xu, et al.  Bernnet: Learning arbitrary graph spectral filters via bernstein approximation.  _Advances in Neural Information Processing Systems_ , 34:14239–14251, 2021.
  * Hinton et al. (2015) Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean.  Distilling the knowledge in a neural network.  In _NIPS Deep Learning and Representation Learning Workshop_ , 2015.
  * Hu et al. (2019) Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.  Strategies for pre-training graph neural networks.  _arXiv preprint arXiv:1905.12265_ , 2019.
  * Jiao et al. (2020) Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu.  TinyBERT: Distilling BERT for natural language understanding.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 4163–4174. Association for Computational Linguistics, nov 2020.
  * Jin et al. (2021) Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han.  Universal graph convolutional networks.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Li et al. (2020) Weizhi Li, Gautam Dasarathy, and Visar Berisha.  Regularization via structural label smoothing.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1453–1463. PMLR, 2020.
  * Lienen and Hüllermeier (2021) Julian Lienen and Eyke Hüllermeier.  From label smoothing to label relaxation.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 35, pages 8583–8591, 2021.
  * Liu et al. (2019) Yifan Liu, Ke Chen, Chris Liu, Zengchang Qin, Zhenbo Luo, and Jingdong Wang.  Structured knowledge distillation for semantic segmentation.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2599–2608, 2019.
  * Lukasik et al. (2020) Michal Lukasik, Srinadh Bhojanapalli, Aditya Menon, and Sanjiv Kumar.  Does label smoothing mitigate label noise?  In _International Conference on Machine Learning_ , pages 6448–6458. PMLR, 2020.
  * McAuley et al. (2015) Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel.  Image-based recommendations on styles and substitutes.  In _Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval_ , pages 43–52, 2015.
  * Müller et al. (2019) Rafael Müller, Simon Kornblith, and Geoffrey E Hinton.  When does label smoothing help?  _Advances in neural information processing systems_ , 32, 2019.
  * Park et al. (2022) Joonhyung Park, Jaeyun Song, and Eunho Yang.  GraphENS: Neighbor-aware ego network synthesis for class-imbalanced node classification.  In _International Conference on Learning Representations_ , 2022.
  * Pei et al. (2020) Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.  Geom-gcn: Geometric graph convolutional networks.  _arXiv preprint arXiv:2002.05287_ , 2020.
  * Pereyra et al. (2017) Gabriel Pereyra, George Tucker, Jan Chorowski, Łukasz Kaiser, and Geoffrey Hinton.  Regularizing neural networks by penalizing confident output distributions.  _arXiv preprint arXiv:1701.06548_ , 2017.
  * Qu et al. (2021) Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, and Hongzhi Yin.  Imgagn: Imbalanced network embedding via generative adversarial graph networks.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 1390–1398, 2021.
  * Rong et al. (2020) Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang.  Self-supervised graph transformer on large-scale molecular data.  _Advances in neural information processing systems_ , 33:12559–12571, 2020.
  * Rozemberczki et al. (2021) Benedek Rozemberczki, Carl Allen, and Rik Sarkar.  Multi-scale attributed node embedding.  _Journal of Complex Networks_ , 9(2):cnab014, 2021.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 29(3):93–93, 2008.
  * Stanton et al. (2021) Samuel Stanton, Pavel Izmailov, Polina Kirichenko, Alexander A Alemi, and Andrew G Wilson.  Does knowledge distillation really work?  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 6906–6919. Curran Associates, Inc., 2021.
  * Szegedy et al. (2016a) Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2016a.
  * Szegedy et al. (2016b) Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna.  Rethinking the inception architecture for computer vision.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 2818–2826, 2016b.  doi: 10.1109/CVPR.2016.308.
  * Tang and Wang (2018) Jiaxi Tang and Ke Wang.  Ranking distillation: Learning compact ranking models with high performance for recommender system.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’18, page 2289–2298, New York, NY, USA, 2018. Association for Computing Machinery.
  * Tang et al. (2009) Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang.  Social influence analysis in large-scale networks.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 807–816, 2009.
  * Tian et al. (2023) Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh Chawla.  Learning MLPs on graphs: A unified view of effectiveness, robustness, and efficiency.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Van der Maaten and Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  _Journal of machine learning research_ , 9(11), 2008.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc., 2017.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ , 2017.
  * Yan et al. (2020) Bencheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou.  Tinygnn: Learning efficient graph neural networks.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’20, page 1848–1856, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450379984.  doi: 10.1145/3394486.3403236.
  * Yang et al. (2016) Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In _International conference on machine learning_ , pages 40–48. PMLR, 2016.
  * Zhang et al. (2021) Chang-Bin Zhang, Peng-Tao Jiang, Qibin Hou, Yunchao Wei, Qi Han, Zhen Li, and Ming-Ming Cheng.  Delving deep into label smoothing.  _IEEE Transactions on Image Processing_ , 30:5984–5996, 2021.
  * Zhao et al. (2021) Tianxiang Zhao, Xiang Zhang, and Suhang Wang.  Graphsmote: Imbalanced node classification on graphs with graph neural networks.  In _Proceedings of the 14th ACM international conference on web search and data mining_ , pages 833–841, 2021.
  * Zhu et al. (2020) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 7793–7804. Curran Associates, Inc., 2020.
  * Zhu et al. (2021) Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra.  Graph neural networks with heterophily.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 35, pages 11168–11176, 2021.

##  Appendix A Dataset statistics

We provide detailed statistics about the dataset used for the experiments in
Table 5.

Dataset | # nodes | # edges | # features | # classes
---|---|---|---|---
Cora | 2,708 | 5,278 | 1,433 | 7
CiteSeer | 3,327 | 4,552 | 3,703 | 6
PubMed | 19,717 | 44,324 | 500 | 3
Computers | 13,752 | 245,861 | 767 | 10
Photo | 7,650 | 119,081 | 745 | 8
Chameleon | 2,277 | 31,396 | 2,325 | 5
Actor | 7,600 | 30,019 | 932 | 5
Squirrel | 5,201 | 198,423 | 2,089 | 5
Texas | 183 | 287 | 1,703 | 5
Cornell | 183 | 277 | 1,703 | 5
Table 5: Statistics of the dataset utilized in the experiments.

##  Appendix B Detailed experimental setup

In this section, we provide the computer resources and search space for model
hyperparameters. Our experiments are executed on AMD EPYC 7513 32-core
Processor and a single NVIDIA RTX A6000 GPU with 48GB of memory. We use the
same model hyperparameter search space as He et al. [2021]. Specifically, we
set the number of layers for all models to two. The dropout ratio for the
linear layers is fixed at 0.5. For the GCN [Kipf and Welling, 2016], the
hidden layer dimension is set to 64. The GAT [Veličković et al., 2017] uses
eight heads, each with a hidden dimension of eight. For the APPNP [Gasteiger
et al., 2018], a two-layer MLP with a hidden dimension of 64 is used, the
power iteration step is set to 10, and the teleport probability is chosen from
$\\{0.1,0.2,0.5,0.9\\}$. For the MLP, the hidden dimension is set to 64. For
the ChebNet [Defferrard et al., 2016], the hidden dimension is set to 32, and
two propagation steps are used. For the GPR-GNN [Chien et al., 2020], a two-
layer MLP with a hidden dimension of 64 is used as the feature extractor
neural network, and the random walk path length is set to 10. The PPR teleport
probability is chosen from $\\{0.1,0.2,0.5,0.9\\}$. For BernNet [He et al.,
2021], a two-layer MLP with a hidden dimension of 64 is used as the feature
extractor, and the polynomial approximation order is set to 10. The dropout
ratio for the propagation layers in both GPR-GNN and BernNet is chosen from
$\\{0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9\\}$.

##  Appendix C Complexity analysis

In this section, we provide a detailed analysis of the time complexity of
Section 3.1. Specifically, we demonstrate the time complexity of obtaining the
prior and likelihood distributions separately. Finally, we determine the time
complexity of computing the posterior distribution using these distributions.

First, the prior distribution $\hat{P}(Y_{i}=m)$ can be obtained as follows:

$\hat{P}(Y_{i}=m)=\frac{\lvert\\{u\mid
y_{u}=k\\}\rvert}{\lvert\mathcal{V}\rvert}=\frac{\sum_{u\in\mathcal{V}}e_{um}}{\lvert\mathcal{V}\rvert}.$
(4)

The time complexity of calculating Equation 4 is $O(\lvert\mathcal{V}\rvert)$,
so the time complexity of calculating the prior distribution for $K$ classes
is $O(\lvert\mathcal{V}\rvert K)$.

Next, calculating the empirical conditional
$\hat{P}(Y_{j}=m|Y_{i}=n,(i,j)\in\mathcal{E})$ from Equation 2 can be
performed as follows:

$\hat{P}(Y_{j}=m|Y_{i}=n,(i,j)\in\mathcal{E})\propto\sum_{u:u\in\mathcal{V},y_{u}=n}\sum_{v\in\mathcal{N}(u)}e_{vm}.$
(5)

The time complexity of calculating Equation 5 for all possible pairs of $m$
and $n$ is $O(\sum_{u\in\mathcal{V}}|\mathcal{N}(u)|K)$. Since
$\sum_{u\in\mathcal{V}}\mathcal{N}(u)=2\lvert\mathcal{E}\rvert$, the time
complexity for calculating empirical conditional is $O(\lvert\mathcal{E}\rvert
K)$.

The likelihood is approximated through the product of empirical conditional
distributions, denoted as
$P(\\{Y_{j}=y_{j}\\}_{j\in\mathcal{N}(i)}|Y_{i}=k)\approx\prod_{j\in\mathcal{N}(i)}\hat{P}(Y_{j}=y_{j}|Y_{i}=k,(i,j)\in\mathcal{E})$.
Likelihood calculation for all training nodes operates in
$O(\sum_{u\in\mathcal{V}}\lvert\mathcal{N}(u)\rvert K)$ time complexity. So
the overall computational complexity for likelihood calculation is
$O(\lvert\mathcal{E}\rvert K)$.

After obtaining the prior distribution and likelihood, the posterior
distribution is obtained by Bayes’ rule in Equation 1. Applying Bayes’ rule
for $\lvert\mathcal{V}\rvert$ nodes and $K$ classes can be done in
$O(\lvert\mathcal{V}\rvert K)$. So the overall time complexity is
$O\left(\left(\lvert\mathcal{E}\rvert+\lvert\mathcal{V}\rvert\right)K\right)$.
In most cases, $\lvert\mathcal{V}\rvert<\lvert\mathcal{E}\rvert$, so the time
complexity of PosteL is $O(\lvert\mathcal{E}\rvert K)$.

Table 6: Average iteration counts of iterative pseudo labeling for each
backbone and dataset used to report Table 1.

| Cora | CiteSeer | PubMed | Computers | Photo | Chameleon | Actor | Squirrel | Texas | Cornell
---|---|---|---|---|---|---|---|---|---|---
GCN+PosteL | 2.5 | 2.2 | 1.5 | 1 | 0.9 | 0.9 | 1.1 | 0.7 | 1.8 | 2.5
GAT+PosteL | 1.6 | 1.8 | 1 | 1.2 | 0.7 | 0.8 | 2 | 1.1 | 3.1 | 2.4
APPNP+PosteL | 1.9 | 2 | 1.1 | 0.8 | 1.1 | 1 | 1.1 | 0.9 | 1.4 | 2.9
MLP+PosteL | 1.7 | 2.2 | 0.4 | 0.7 | 0.7 | 0.1 | 0.8 | 0.6 | 0.9 | 2.4
ChebNet+PosteL | 1.6 | 2.1 | 1.2 | 0.6 | 0.6 | 1 | 0.7 | 0.7 | 2 | 2
GPR-GNN+PosteL | 0.8 | 1.1 | 0.8 | 0.5 | 1.3 | 1 | 0.3 | 0.7 | 1.1 | 1
BernNet+PosteL | 1.5 | 1.8 | 0.9 | 0.8 | 1 | 1.5 | 1.5 | 0.5 | 1.2 | 2.1

In Section 3.2, iterative pseudo labeling is proposed, which involves
iteratively refining the pseudo labels of validation and test nodes to
calculate posterior labels. Since this process requires training the model
from scratch for each iteration, the number of iterations can be a significant
bottleneck in terms of runtime. Consequently, the iteration counts are
evaluated to assess this aspect. The mean iteration counts for each backbone
and dataset in Table 1 are summarized in Table 6. With an overall mean
iteration count of 1.13, we argue that this level of additional time
investment is justifiable for the sake of performance enhancement.

##  Appendix D Learning curves analysis for all datasets

The learning curves for all datasets are provided in Figure 8 and Figure 10.

(a) PubMed

(b) Computers

(c) Photo

(d) Cora

(e) CiteSeer

Figure 8: Loss curve of GCN trained on PosteL labels and ground truth labels
on homophilic datasets.

(a) Chameleon

(b) Squirrel

(c) Actor

(d) Texas

(e) Cornell

Figure 10: Loss curve of GCN trained on PosteL labels and ground truth labels
on heterophilic datasets.

##  Appendix E Empirical conditional distribution for all datasets

The empirical conditional distribution for all datasets is provided in Figure
11 and Figure 12.

(a) Chameleon

(b) Actor

(c) Squirrel

(d) Texas

(e) Cornell

Figure 11: Empirical conditional distributions between two adjacent nodes on
heterophilic graphs.

(a) Cora

(b) Citeseer

(c) PubMed

(d) Computers

(e) Photo

Figure 12: Empirical conditional distributions between two adjacent nodes on
homophilic graphs.