{'fraction_non_alphanumeric': 0.034420662687795846, 'fraction_numerical': 0.010701790491870755, 'mean_word_length': 5.009120420466842, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Node Classification on Graphs: Jointly from Bayesian Label Transition and Topology-based Label Propagation

Node classification using Graph Neural Networks (GNNs) has been widely applied in various real-world scenarios. However, in recent years, compelling evidence emerges that the performance of GNN-based node classification may deteriorate substantially by topological perturbation, such as random connections or adversarial attacks. Various solutions, such as topological denoising methods and mechanism design methods, have been proposed to develop robust GNN-based node classifiers but none of these works can fully address the problems related to topological perturbations. Recently, the Bayesian label transition model is proposed to tackle this issue but its slow convergence may lead to inferior performance. In this work, we propose a new label inference model, namely LInDT, which integrates both Bayesian label transition and topology-based label propagation for improving the robustness of GNNs against topological perturbations. LInDT is superior to existing label transition methods as it improves the label prediction of uncertain nodes by utilizing neighborhood-based label propagation leading to better convergence of label inference. Besides, LIndT adopts asymmetric Dirichlet distribution as a prior, which also helps it to improve label inference. Extensive experiments on five graph datasets demonstrate the superiority of LInDT for GNN-based node classification under three scenarios of topological perturbations.


INTRODUCTION
Among the various machine learning tasks on the graph data, node classification is probably the most popular with numerous realworld applications, such as, user profiling in online social networks (OSNs) [6,78,79], community detection [2,7], expert finding in community-based question answering [16,71], recommendation systems [15,19,67], and epidemiology study [25,33]. While many traditional approaches have been used for solving a node classification task [1,34,43,54], in this deep learning era various graph neural network models (GNNs) [3,11,12,23,32] have become popular for solving this task. The enormous appeal of GNN models for node classification is due to their ability to learn effective node-level representation by performing locality-based non-linear aggregation jointly over node attributes and adjacency information leading to superior prediction performance.
However, in recent years, compelling evidence emerges that the performance of GNN-based node classification may deteriorate substantially by changes in a graph structure [29,52], which raises concern regarding the application of GNNs in various real-life scenarios. For instance, in an online social network, non-malicious selfish users may randomly connect with many other nodes for promoting their business activities [22,78]; such random connections exacerbate over-smoothing [24,37], a well-known cause of the poor performance of GNNs. On the other extreme, the messagepassing mechanism of GNNs performs poorly on nodes with sparse connection [53,66], such as the nodes representing new users of OSNs, which lack sufficient links (edges) or profile information (feature). Third, GNNs may be vulnerable to adversarial attacks [9,10,61,80,81]. Such attacks may significantly deteriorate the performance of node classifications with slight and unnoticeable modification of graph structures and node features. In this paper, we refer to all such scenarios as topological perturbations.
Many recent works have been proposed to develop robust GNNbased node classification models against topological perturbations. Most of these works can be divided into two categories: the topological denoising methods, which design methodologies for denoising perturbed graphs in a pre-processing stage [13,62] or in the training stage [40,46,55,64,72], and the mechanism design methods, which make GCN's prediction robust by message-passing-based aggregation over the nodes [5,17,28,47,68] or through regularization [4,24,30,38,45,63,65,74]. Nevertheless, none of these works can fully address the topological perturbations. For one thing, topological denoising methods may fail to prune suspicious edges when the graph structure is sparse. For another, mechanism designing methods sometimes highly depend on heuristics explorations of topological connections among nodes. The mechanism may perform worse when the graph structure is under severe perturbations. arXiv:2208.09779v1 [cs.LG] 21 Aug 2022 In some recent works [77,78], the authors tackle the topological perturbation issues by developing a Bayesian label transition mechanism, which fixes the poor performance of GNNs by postprocessing the prediction; specifically, their approaches learn a label transition matrix through Bayesian inferences, which fixes the erroneous prediction of GNNs by replacing the GNN inferred labels to a different label. A key benefit of post-processing is that it is effective for dynamic network scenarios, in which the network structure and node features of test data may be different than the train data. However, Bayesian label transition [77] suffers slow convergence as the posterior distribution from which the Gibbs sampling samples the node labels adapt incrementally over a sequence of label-propagation followed by GNN re-training iterations. Slow convergence also leads to inferior performance because the labels on which the GNN is re-trained may not be accurate as the Bayesian label transition may have not yet been converged.
Although label transition is a relatively new idea in the node classification task, label propagation (LP) has been widely used in the semi-supervised learning paradigm [20,26,27,31,50,[57][58][59][60]76]. Recently, Huang et al. [26] demonstrated that graph semi-supervised learning using LP can exceed or match the performance of some variants of GNNs. Zhu and Ghahramani [76] have shown that label propagation is similar to mean-field approximation, which has fast convergence when the number of instances is large. The main assumption of LP is that closer data points tend to have similar class labels-this assumption is analogous to the graph Homophily assumption, which denotes that adjacent vertices have similar labels. Specifically, on noisy and perturbed graphs, the label prediction on a given (or a targeted) node can be affected severely, however, the prediction of other neighboring nodes may still be sufficiently good, and by the virtue of homophily, those predictions can help recovering the true label of the affected node. Inspired by these observations, in this work, we improve the robustness of GNN-based node classification through an integrated framework combining Bayesian label transition and graph topology-based label propagation. We name our proposed model LInDT 1 .
The main advantage of LInDT over a label-transition-based method, such as GraphSS [77], is that the former effectively utilizes LP when the sampling distribution of Bayesian label transition is uncertain. This immediately improves the label convergence and subsequently improves the label prediction performance. Besides, LInDT adopts a better Bayesian prior than GraphSS; specifically, LInDT follows an informative asymmetric Dirichlet distribution, but GraphSS follows a symmetric Dirichlet distribution, which allows LInDT to take advantage of the most up-to-date label distribution, leading to better performance. We evaluate LInDT's performance under random perturbations, information sparsity, and adversarial attacks scenarios, across five public graph datasets. The experimental results verify the following facts: First, the GNN-based node classifier benefits strongly from LInDT's proposed label inference as post-processing; Second, LInDT converges faster than a pure Bayesian label transition which only uses Gibbs based posterior sampling; Third, LInDT outperforms eight popular competing methods. We also perform an ablation study to verify the effectiveness 1 LInDT is built by taking the bold letters of "Label Inference using Dirichlet and Topological sampling", and its pronunciation is similar to the popular chocolate brand name. Source code is available at https://github.com/junzhuang-code/LInDT of LInDT's design choices. For example, our experiment validates that asymmetric Dirichlet distributions of LInDT help better label inference using Bayesian label transition.
Overall, we summarize our contributions in this paper as follows: • We propose a new label inference mechanism that can infer node labels jointly from a Bayesian and label propagation framework. Our model can converge faster than the Bayesian label transition using Gibbs sampling. • We release the constraint of symmetric Dirichlet distributions on the Bayesian label transition and verify that dynamically updating the vector (Dirichlet prior) can help better label inference. • Extensive experiments demonstrate that our model achieves robust node classification on three topological perturbation scenarios and outperforms eight popular defending models across five public graph datasets.

METHODOLOGY
In this section, we first briefly introduce the node classification using GNNs. We then describe the basic idea of Bayesian label transition. Besides, we discuss asymmetric Dirichlet distributions and introduce our proposed model. Lastly, we present the pseudocode and time complexity of our model.

GNN-based Node Classification
An undirected attributed graph is denoted as .., } is the set of vertices, is the number of vertices in G, and E ⊆ V × V is the set of edges between vertices. We denote A ∈ R × as symmetric adjacency matrix and X ∈ R × as the feature matrix, where is the number of features for each vertex. We choose the most representative variant of GNNs, GCN [32], as the node classifier f in this work. The layer-wise propagation of GCN is formulated as follows: In Eq. 1,Ã = A + ,D = D + , where is the identity matrix and D , = A , is the diagonal degree matrix. H ( ) ∈ R × is the nodes hidden representation in the -th layer, where H (0) = X. W ( ) is the weight matrix in the -th layer. (·) denotes a non-linear activation function, such as ReLU.
In general node classification tasks, a GNN-based node classifier f takes both A and X as inputs and is trained with ground-truth labels in train data. To obtain robust classification, some studies attempt to train the model using noisy labels as a regularization scheme [35,56]. In this study, we borrow this idea and train the GNN node classifier, f , after assigning a uniform random label to a percentage (in this work we use 10%) of the train nodes. We denote these noisy labels as Y ∈ R ×1 . The higher the percentage of noise ratio, the stronger the regularization. On the other hand, we denote the ground truth labels (a.k.a. latent labels) as Z ∈ R ×1 , which are unobserved (to the GNN), yet we want the GNN to be able to predict the unobserved label. So, the model's performance is optimized to predict Z by using a validation set. It may seem counter-intuitive to train a model with noisy labels and still expect it to perform well on the ground-truth label; however, this is feasible because both Z and Y take values from the same closed category set. Also, there is a strong correlation between Y and Z as only a fraction of the node's labels have been altered. But, as GNN is trained on the noisy labels, it becomes noise-resilient and robust, and performs well when the network is perturbed. Figure 1: The diagram of Bayesian label transition. V, Z, and Y denote copies of nodes, latent labels, and noisy labels, respectively. denotes the -class Dirichlet-based conditional label transition matrix parameterized by .

Bayesian Label Transition
A GNN suffers performance loss when applied in the test data, which undergoes various topological perturbations. To overcome this, recent works have applied Bayesian label transition to fix erroneous prediction of GNN by learning a label transition matrix on the fly (from the test data). We explain Bayesian label transition by utilizing the plate diagram in Fig. 1. The unobserved latent labels (Z) depend on the nodes, whereas the observed noisy labels (Y) depend on both Z and the conditional label transition matrix, , which is parameterized by . Both Z and Y are sampled from distributions of V, the predictions from the trained node classifier.
= [ 1 , 2 , . . . , ] ∈ R × consists of K transition vectors. The -th transition vector is sampled from corresponding Dirichlet distribution ℎ ( ), where is the -th element of the vector. Based on this dependency, the posterior of Z, which is conditioned on the nodes V, the noisy labels Y, and the Dirichlet parameter , can be formulated as follows: However, sampling from such a posterior distribution is difficult. GraphSS [77] applies Gibbs sampling to approximate this posterior, so that inferred labelsZ ∈ R ×1 matches to the latent labels (Z) as identically as possible.
In this study, we assume the test graph is perturbed through various structural changes and further develop the Bayesian label transition model to improve the robustness of GNN-based node classifiers against topological perturbations. Before summarizing the problem we aim to solve in this work, we first clarify that noisy labels in this work include both manual-annotated labels Y ∈ R ×1 and auto-generated labels Y ∈ R ×1 , where and denote the number of nodes on the train and test graphs, respectively. More specifically, we first train GNN with Y on the unperturbed train graph to generate Y . The prediction of the test nodes may perform worse when the test graph is under topological perturbations. At this point, we employ our proposed label inference model to iteratively recover the perturbed predictions by Y with several epochs of transition. After the label transition is converged, we expect that the inferred labels will be as identical as the latent labels. Overall, the above-mentioned problem could be formally described as follows: Problem 1. Given a graph G = (A, X) and the manual-annotated labels Y , which are used for training a GNN-based node classifier f on unperturbed G , we aim to develop a label inference model to improve the robustness of the node classifier f on perturbed G by approximating the inferred labelsZ to the latent labels Z as identical as possible.

Asymmetric Dirichlet Distributions
In Eq. 2, GraphSS [77] assumes the Dirichlet distribution is symmetric, i.e., the parameter vector has the same value, 1.0, to all classes. In this study, we release this constraint and investigate whether adopting asymmetric Dirichlet distributions as a prior can contribute to the label transition. Fig. 2 visualizes the Dirichlet distributions by equilateral triangles. The first triangle represents the symmetric Dirichlet distribution. The second triangle shows that data points tend to move to the corner with the same probability. The third triangle presents that data points have a higher probability to be assigned to the class whose value is higher. The intuition is that the ℎ inferred labelz may have higher probability to be transited to the ℎ class in the ℎ transition when is higher. Following this intuition, we dynamically update the ℎ -class value, , in the ℎ transition as follows: where (·) denotes an indicator function.

Label Inference Jointly from Bayesian Label Transition and Topology-based Label Propagation
GraphSS [77] applies Gibbs sampling to recover the multinominal distribution of nodes on perturbed graphs. However, such sampling may converge slowly and thus leads to inferior inference. This drawback can be mitigated by considering the fact that the majority of real-life networks exhibit homophily property, i.e., labels of the adjacent nodes are similar. So, if the inferred label of a node during label transition is uncertain, we can sample its label from the labels of adjacent nodes. This idea is inspired by well-known Label propagation algorithms [58]. Thus, LInDT integrates both Bayesian label transition and topology-based label propagation. More specifically, for each node on G , our model first infers the label from Bayesian label transition and then substitutes this label using topology-based label propagation when this inferred label is uncertain. We define the node label uncertainty during the inference as follows: Definition 1. In the ℎ transition, an inferred labelz is uncertain, such thatz ≠z −1 orz ≠ y.
Note thatz ≠z −1 will be happened when the inference is not converged yet, whereasz ≠ y indicates that the inferred labelsZ still deviates from the auto-generated labels Y . The intuition of our model is that unnoticeable perturbations may severely deteriorate the predictions of GNN-based node classifiers, but fortunately, such perturbations only alter a small number of topological structures. Based on the homophily assumption of the graph structure, i.e., intra-class nodes tend to connect with each other, sampling labels with topology-based label propagation can decrease the node label uncertainty by utilizing topological information of nodes. Note that we present the edge homophily ratio (EHR ∈ [0, 1]) [75], the percentage of intra-class edges, in Tab. 1 to verify the homophily property in the graph datasets. Higher EHR indicates stronger homophily property.

Algorithm 1: Label Sampling Jointly from Bayesian Label Transition and Topology-based Label Propagation
Updatez with the topology-based label sampler; 5 end 6 end 7 return Inferred labelsZ in the ℎ transition.
We present how our model samples labels jointly from Bayesian Label Transition and Topology-based Label Propagation in Algo. 1. In the ℎ transition, we first sample a labelz of the ℎ node from the categorical distribution P(z −1 | ) ∈ R × updated with a given label transition matrix −1 in the ( − 1) ℎ transition (Line 2). We then updatez with a given topology-based label sampler when this inferred label is uncertain (Line 3-4). In the end, we obtain the inferred labels in the ℎ transition. Besides Algo. 1, we further use a toy example to explain our proposed sampling method in Fig. 3. In the ℎ transition, our model first samples the inferred label of node A as the red class via Bayesian label transition. However, this inferred label is different from the auto-generated label of node A; let's say it's blue. In this case, we say that this node label is uncertain. Based on the assumption of homophily graphs and unnoticeable perturbations, i.e., the labels of majority neighbor nodes are predicted correctly in Y , we then apply the topology-based label sampler to substitute the label, i.e., replacing it from red to blue based on the topological information of node A.
Based on the above-mentioned intuition, we investigate three types of topology-based label samplers, random sampler (Random), majority sampler (Major), and degree-weighted sampler (Degree). All of these samplers sample a label from 1-hop neighborhood of the current node. We denote the set of classes from the 1-hop neighborhood as and the number of neighbour nodes as . We highlight the distinctions of these candidate samplers as follows and further explain them with toy examples in Fig. 4.
• Random sampler randomly samples a label. In the ℎ transition, the probability that the ℎ inferred labelz is equal to ℎ class can be formulated as Eq. 4.
• Majority sampler selects the majority class as the label, such that the number of nodes in majority class | | = { z = A : ∈ }. • Degree-weighted sampler chooses a label from the class , such that sum of the neighbor nodes' total degrees in is maximum. This maximum sum can be expressed as For example, we sample the node c using: Random: Major: Figure 4: Toy examples of our three proposed samplers. We use red, yellow, and blue color to represent three classes.
Analysis of Convergence. To analyze the convergence of our proposed sampling method, we discuss two conjectures as follows. Conjecture 1. Given a large enough iterations of transition , the transition of inferred labelsZ will eventually converge toZ .
Analysis: We formally state the transition as follows: Theoretical proof of this conjecture is difficult because both the categorical distribution P Z | V and the label transition matrix in each transition will be dynamically updated. Instead, we empirically examine this conjecture in the experiment. Note that the converged inferred labelsZ is not guaranteed to be the same as the latent labels Z, which translates to the possibility of erroneous prediction.
Conjecture 2. Label sampling jointly from Bayesian Label Transition and Topology-based Label Propagation helps the inference converge with fewer iterations of transition than the Bayesian-based sampling.
Analysis: Our proposed sampling method will substitute the inferred labels of uncertain nodes based on the topological information. On the homophily graphs, we can get smaller Total Variation Distance between current node label distributions of inferred labels in ℎ transitionZ and the convergence distributions of inferred labelsZ as follows: whereZ denotes the inferred labels using our proposed sampling method, whereasZ denotes the inferred labels using the Bayesian-based sampling method. ∥·∥ denotes the Total Variation Distance.
We argue that this conjecture is true as such substitutions can force the inferred labels to get closer to the convergence based on the homophily assumption, shortening the iterations of transition compared to using the Bayesian-based sampling method, e.g., Gibbs sampling. Our experiments empirically verify this conjecture.

Pseudo-code of Our Proposed Model
Algorithm 2: LInDT's Pseudo-code Input: Graph G and G , which contain corresponding symmetric adjacency matrix A and feature matrix X, Manual-annotated labels Y in G , Node classifier f , Initial , The number of warm-up steps , The number of transition . 1 Train f with Y on G ; 2 Generate initial categorical distribution P ( Z | V) and auto-generated labels Y by f ; 3 Compute warm-up label transition matrix ′ based on G ; 4 Define inferred labelsZ, dynamic label transition matrix based on G , and initial vector; 5 for ← 1 to do 6 if < then 7 SampleZ with warm-up ′ by Algo. 1; To warp up our model in Algo. 2, we discuss the pseudo-code and analyze the time complexity in this section. Training: Our model trains the node classifier f on the train graph G at first with manual-annotated labels Y (line 1) and then generates initial categorical distribution P (Z | V) and auto-generated labels Y by f (line 2). Inference: Before the inference, our model first computes a warm-up label transition matrix ′ by using the prediction over G (line 3). Our model then defines (creates empty spaces) the inferred labelsZ, the dynamic label transition matrix based on the test graph G , and also initializes the vector with a given initial value (line 4). In the warm-up stage, our model samples the inferred labels in the ℎ transition with the warm-up ′ , which is built with the categorical distribution of f and Y on G , via corresponding topology-based label sampler using Algo. 1 (line 7). After the warm-up stage, our model applies the same sampling method with the dynamic (line 10). This dynamic updates in each transition with current inferred labelsZ and corresponding Y . Simultaneously, our model dynamically updates the vector by Eq. 3 and the dynamic matrix (line 12). Besides, our model iteratively re-trains the node classifier with the current inferred labelsZ in the ℎ transition, and then updates the categorical distribution P Z | V modeled by the re-trained f (line 13). The transition will eventually reach convergence, approximating the inferred labels to the latent labels as identical as possible. In other words, our model can help recover the original predictions by dynamic conditional label transition on perturbed graphs.
According to Algo. 2, our model applies transitions in the inference. For each transition, our proposed sampling method traverses all test nodes once. Overall, the time complexity of the inference approximates to O ( · ), where denotes the number of transition, whereas denotes the number of nodes on the test graph.

EXPERIMENTS
In this section, we want to answer the following questions for evaluating our model.
• Can node classification benefit from our model against topological perturbations? • How's the convergence of our model? • How's our performance compared to competing methods? • Can asymmetric Dirichlet distributions contribute to the label inference?  Table 2: Examination of our model on top of GCN under three scenarios of topological perturbations across five datasets. "Original" denotes the original performance of GCN on perturbed graphs (before inference). GraphSS is our baseline model with a fixed value, 1.0. "Vanilla" denotes that we dynamically update the vector using Gibbs samplers. "Random", "Major", and "Degree" denote that we employ the corresponding topology-based label sampler based on our vanilla architecture instead of using Gibbs samplers. All methods are evaluated by classification accuracy (Acc.) and average normalized entropy (Ent.) on victim nodes. Experimental Settings. Before answering these questions, we first introduce the experimental settings. Datasets. Tab. 1 presents statistics of five public node-labeled graph datasets. Cora, Citeseer, and Pubmed are famous citation graph data [48]. AMZcobuy comes from the photo segment of the Amazon co-purchase graph [49]. Coauthor is co-authorship graphs of computer science based on the Microsoft Academic Graph from the KDD Cup 2016 challenge 2 . For all datasets, the percentage of train, validation, and test partition comprise 10%, 20%, and 70% of the nodes, respectively. Similar to GraphSS [77], only the train graphs contain manual-annotated labels, but the validation and test graphs don't. We simulate the manual-annotated labels by randomly replacing the ground-truth labels of 10% (noise ratio ) nodes with another label, chosen uniformly. Implementation of Topological Perturbations. We examine our model under three scenarios of topological perturbations as follows. 1) Random perturbations (rdmPert): perturbators in OSNs intend to randomly connect with many other normal users for commercial purposes, e.g., new brand promotion. In the experiments, we limit the number of perturbators to 1% of the validation/test nodes (a.k.a. victim nodes) and restrict the number of connections from each perturbator to 100. Note that rdmPert doesn't apply gradient-based attacks, such as FGSM [21], PGD [41] Adversarial attacks (advAttack): we execute node-level direct evasion non-targeted attacks [80] on both links and features ( & ) of the victim nodes on sparse graphs, whereas the trained node classifier remains unchanged. To ensure the sparsity, we sparse the denser graphs (AMZcobuy and Coauthor) and select the victim nodes whose total degrees are within (0, 10) for attacks. The intensity of perturbation is set as 2 for all datasets. The ratio of between applying on links and applying on features is 1: 10. Competing Methods. We first compare our model with seven popular competing methods which develop robust GNN-based node classifiers using topological information. Also, we consider MC Dropout as one of the competing methods for measuring uncertainty purposes. GNN-Jaccard [62] preprocesses the graph by eliminating suspicious connections, whose Jaccard similarity of node's features is smaller than a given threshold. GNN-SVD [13] proposes another preprocessing approach with low-rank approximation on the perturbed graph to mitigate the negative effects from high-rank attacks, such as Nettack [80]. DropEdge [46] randomly removes a number of edges from the input graph in each training epoch. GRAND [17] proposes random propagation and consistency regularization strategies to address the issues of over-smoothing and non-robustness of GCNs. RGCN [74] adopts Gaussian distributions as the hidden representations of nodes to mitigate the negative effects of adversarial attacks. ProGNN [30] jointly learns the structural graph properties and iteratively reconstructs the clean graph to reduce the effects of adversarial structure. GDC [24] proposes an adaptive connection sampling method using stochastic regularization for training GNNs. This method can learn with uncertainty on graphs. MC Dropout [18] develops a dropout framework that approximates Bayesian inference in deep Gaussian processes. Evaluation Metrics. We use both accuracy (Acc.) and average normalized entropy (Ent.) to measure the robustness of a node classifier. More specifically, Acc. evaluates the node classification performance (the higher the better), whereas Ent. represents the uncertainty of nodes' categorical distributions (the lower the better).

Methods
Node Classification Benefits from Our Model against Topological Perturbations. The performance of a node classifier may degrade on perturbed graphs. We present the comparison of node label distributions of test nodes among the ground-truth labels, the prediction on unperturbed graphs, and the prediction on perturbed graphs (under rdmPert) in Fig. 6 as an example. This comparison indicates that node label distributions may significantly change on perturbed graphs, causing performance degradation. In this study, our goal is to improve the robustness of the node classifier on perturbed graphs. In other words, we aim to increase the classification accuracy (Acc.) while maintaining the uncertainty (Ent.) at a low level.
To answer the first question, we examine whether the node classifier can benefit from our model under three scenarios of topological perturbations, random perturbations (rdmPert), information sparsity (infoSparse), and adversarial attacks (advAttack). We compare the performance between the baseline model, GraphSS [77], and the variants of our model architectures. The denotations of related methods are mentioned in the caption of Tab. 2. The results affirmatively verify that our model can outperform the baseline model and successfully achieve our goal in most cases. Besides, we have several observations as follows. At first, topological samplers could further boost accuracy under both rdmPert and advAttack but may fail under infoSparse because most links and features are sparsified under this scenario. Moreover, the majority sampler attains higher accuracy than the degree-weighted sampler on sparse graphs (Cora, Citeseer, and Pubmed) in most cases. Such a situation may be largely reversed on denser graphs (AMZcobuy and Coauther) because the degree-weighted sampler can further take the advantage of degree information from neighbors. Furthermore, the uncertainty may be lower under some scenarios, e.g., Ent. is 1.43% under advAttack on Cora. However, such kind of low uncertainty reveals that the node classifier may suffer severe perturbations, i.e., many nodes are certainly assigned to incorrect classes. Thus, lower uncertainty couldn't fully indicate robust performance. Last but not least, our model couldn't significantly decrease the uncertainty under rdmPert on Citeseer.

Unperturbed
Perturbed (Before Inference) We further investigate this unusual case by visualizing the node label distributions via confusion matrices in Fig. 7. The left matrix presents the predicted node label distributions on unperturbed graphs, whereas the middle and right matrices present the predicted and inferred distributions on perturbed graphs, respectively. The  visualization first shows that our model can recover the distribution as close as that on unperturbed graphs when the node label distribution is perturbed. These confusion matrices also indicate that the node classification on the unperturbed graphs already misses one class, leading to the inaccurate prior distribution. The label inference may probably fail to decrease the uncertainty due to this reason. Besides, this case reveals two limitations of our model. First, the inference highly depends on an accurate prior distribution. Second, our model couldn't recover the missing class, which implies that our model currently cannot handle the open-set classification.

Perturbed (After Inference)
Empirical Analysis of Convergence. To answer the second question, we conduct an empirical analysis of convergence to examine two proposed conjectures. Fig. 5 displays the empirical comparison between using the Gibbs sampler and using the topology-based label sampler (Major) during the label inference under rdmPert. The first row presents the curves of validation accuracy (%). The second row displays the curves of the ratio of uncertain nodes (%) on inferred labels. According to the results, the label inference using both sampling methods can eventually converge across five datasets. The convergence verifies that the first conjecture holds true. Also, the results show that the label inference using the topology-based label sampler reaches the convergence with fewer iterations of transition compared to using the Gibbs sampler. In other words, using the topology-based label sampler can help decrease the ratio of uncertain nodes faster, and further reduces the fluctuations of the curve. The comparison verifies the second conjecture. We notice that DropEdge and RGCN perform higher accuracy on larger graphs. For DropEdge, randomly dropping a certain number of edges is equivalent to data augmentation, which will be performed stronger when the size of the input graph is getting larger. RGCN adopts Gaussian distributions in hidden layers to reduce the negative impacts that come from the shift of node label distribution. The Gaussian-based hidden matrix has a higher capability to mitigate the negative impacts on larger graphs. From the perspective of total runtime (in second), we observe that topological denoising methods (GCN-Jaccard, GCN-SVD, and DropEdge) and MC dropout consume much less time than other methods. These are reasonable because topological denoising methods mainly process the input graph structure, and MC dropout can speed up the training by dropping some hidden units. On the contrary, ProGNN consumes much more time as the size of graphs increases. One of the reasons is that ProGNN iteratively reconstructs the graph by preserving low rank and sparsity properties. Such reconstructions will take a much longer time on larger graphs.

Analysis of Parameters.
In this study, we maintain the same values of both warm-up steps , 40, and retraining epochs , 60, as that in GraphSS [77]. To avoid over-fitting, we retrain the node classifier every 10 epochs during the inference. In the meanwhile, we analyze how the initial value affects accuracy, and conduct this analysis on the validation set. We fix the number of transition states as [100, 200, 80, 100, 90] for five datasets, respectively. Fig.  8 presents two curves of accuracy along different initial values. The blue curve denotes the case that we dynamically update the vector, whereas the red curve denotes the case with fixed values.
The results affirmatively answer the fourth question that adopting asymmetric Dirichlet distributions as a prior can contribute to the label inference using Bayesian label transition. Besides, the comparison between two curves verifies that the dynamic mechanism can further boost the accuracy in most cases. Based on this analysis, we select the initial values as [0.1, 0.3, 1.0, 0.7, 0.1] for five datasets, respectively.
Limitation and Future Directions. 1) Using the topologybased sampler may fail to boost the classification accuracy on extreme sparse graphs where most links and features are sparsified or missing. 2) Our label inference model highly depends on an accurate prior distribution. In other words, our model couldn't handle the poisoning attacks. In the future, integrating a denoising approach on the prior distribution would be a possible solution to mitigate this issue. 3) Our model couldn't recover the missing class from the prior distribution. This limitation implies that our model currently cannot handle the open-set classification. In the future, we could jointly utilize a distance-based label transition matrix to detect potential unseen classes during the inference.

RELATED WORK AND IMPACT
In this section, we further discuss how our work may contribute to other research fields as follows: 1) Noisy label learning. Learning GNNs with noisy labels has been widely studied [8,14,36,44,73]. We train the GCN with noisy labels for downstream inference. Our work could further contribute to this field as the Bayesian label transition model may recover the node label distribution using noisy labels with different noisy ratios. 2) Uncertainty estimation. Many researchers conduct studies on uncertainty estimation of node classifications using Bayesian approaches [39,42,51,69,70]. Our work could dedicate to this field since the experiments demonstrate that the label inference can significantly decrease the uncertainty of node classifications.

CONCLUSION
In this work, we aim to improve the robustness of a GNN-based node classifier against topological perturbations given that the node classifier is trained with manual-annotated labels. To achieve this goal, we propose a new label inference model, namely LInDT, that integrates both Bayesian label transition and topology-based label propagation. Extensive experiments demonstrate the following conclusions. Firstly, GNN-based node classification can benefit from our model under three scenarios of topological perturbations. Furthermore, our model converges faster, achieves higher accuracy on node classification while maintaining normalized entropy at a low level, and surpasses eight popular competing methods across five public graph datasets. Lastly, adopting asymmetric Dirichlet distributions as a prior can contribute to label inference.

ACKNOWLEDGMENTS
Our work is supported by NSF with grant number IIS-1909916.

A IMPLEMENTATION A.1 Hardware and Software
We conduct the experiments using Python 3.8 and PyTorch 1.7. on Ubuntu 18.04.5 LTS with Intel(R) Xeon(R) Gold 6258R CPU 2.70 GHz and NVIDIA Tesla V100 PCIe 16GB GPU.

A.3 Hyper-parameters of Competing Methods
We present the hyper-parameters of competing methods for reproducibility purposes. All models are trained by Adam optimizer. GNN-Jaccard GDC [24]: The number of blocks and layers is 2 and 4, respectively. The hidden units are 32. The dropout rate is 0.5. Both learning rate and weight decay are 5 × 10 −3 . The training epochs are 400. MC Dropout [18]: We use the same GCN architecture and training setting as ours except for the optimal dropout rate for each dataset as 0.7, 0.6, 0.9, 0.6, and 0.8, respectively. Note that MC Dropout will apply dropout in test data.