{'fraction_non_alphanumeric': 0.03991811668372569, 'fraction_numerical': 0.008137154554759468, 'mean_word_length': 5.010765918179022, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
GraFN: Semi-Supervised Node Classification on Graph with Few Labels via Non-Parametric Distribution Assignment

Despite the success of Graph Neural Networks (GNNs) on various applications, GNNs encounter significant performance degradation when the amount of supervision signals, i.e., number of labeled nodes, is limited, which is expected as GNNs are trained solely based on the supervision obtained from the labeled nodes. On the other hand,recent self-supervised learning paradigm aims to train GNNs by solving pretext tasks that do not require any labeled nodes, and it has shown to even outperform GNNs trained with few labeled nodes. However, a major drawback of self-supervised methods is that they fall short of learning class discriminative node representations since no labeled information is utilized during training. To this end, we propose a novel semi-supervised method for graphs, GraFN, that leverages few labeled nodes to ensure nodes that belong to the same class to be grouped together, thereby achieving the best of both worlds of semi-supervised and self-supervised methods. Specifically, GraFN randomly samples support nodes from labeled nodes and anchor nodes from the entire graph. Then, it minimizes the difference between two predicted class distributions that are non-parametrically assigned by anchor-supports similarity from two differently augmented graphs. We experimentally show that GraFN surpasses both the semi-supervised and self-supervised methods in terms of node classification on real-world graphs. The source code for GraFN is available at https://github.com/Junseok0207/GraFN.


INTRODUCTION
Recently, Graph Neural Networks (GNNs) are widely applied in IR applications ranging from recommender system [4,6,12,23,25], question answering [5,28] to web search [11,13]. Specifically, graph convolution-based methods [27,29] incorporate rich attributes of nodes along with the structural information of graphs by recursively aggregating the neighborhood information. Despite the success, the performance of GNNs on node classification significantly degrades when only few labeled nodes are given as GNNs tend to overfit to the few labeled nodes. To make the matter worse, GNNs suffer from ineffective propagation of supervisory signals due to the wellknown over-smoothing issue [9], which makes GNNs not being able to fully benefit from the given labeled nodes. Fig. 1 demonstrates a severe performance degradation of GCN as the rate of the labeled nodes decreases.
To train GNNs given limited labeled information, recent studies mainly focus on leveraging pseudo-labeling techniques. Specifically, arXiv:2204.01303v3 [cs.LG] 27 Apr 2022 Given a graph , we generate two differently augmented views˜and˜′ both of which are fed into a shared encoder to obtain node-level representationZ andZ ′ , respectively. Then, GraFN not only minimizes the difference between these two representations obtained from differently augmented graphs, i.e. node-wise consistency (L NC ), but also minimizes the difference between the predicted class distributions computed in a non-parametrically manner by using the similarity between the anchor node and support nodes, which are randomly sampled from labeled nodes, i.e., label-guided consistency (L LC ).
co-training [9] uses Parwalks [26] to provide confident pseudolabels to help train GNNs, and self-training [9] expands the label set by obtaining pseudo-labels provided by GNNs trained in advance. Moreover, M3S [18] leverages a clustering technique to filter out pseudo-labels that do not align with the clustering assignments for improving the pseudo-labeling accuracy. However, pseudo-labelingbased methods suffer from an inherent limitation originated from the incorrect pseudo-labels, which eventually incur confirmation bias [1]. To alleviate this issue, it is crucial to fully benefit from the given label information.
On the other hand, self-supervised methods for graphs [20,31,32] learn node representations without any requirements of labeled nodes. In particular, based on graph augmentations, contrastive learning-based methods pull positive pairs of nodes together while pushing negative ones apart, whereas consistency regularizationbased methods impose GNNs to consistently output the same node representations over various perturbations of the given graph. Although these methods have achieved the state-of-the-art results in node classification even outperforming the supervised counterparts, they fall short of learning class discriminative node representations since no labeled information is utilized during training. As shown in Fig. 1, although recent self-supervised methods for graphs, i.e., BGRL [20] and GRACE [31], outperform GCN [7] over various rates of labeled nodes, the performance degradation is still severe as the rate decreases.
To this end, we propose a simple yet effective semi-supervised method for graphs that fully leverages a small amount of labeled nodes to learn class discriminative node representations, called GraFN. The main idea is to consistently impose the representations of nodes that belong to the same class to be grouped together on differently augmented graphs. Specifically, we randomly sample support nodes from the labeled nodes and anchor nodes from the entire graph, and non-parametrically compute two predicted class distributions from two augmented graphs based on the anchorsupports similarity. By minimizing the difference between the two class distributions, GraFN not only learns augmentation invariant parameters, but also enforces the representations of nodes that belong to the same class to be grouped together. As shown in Fig. 1, GraFN consistently outperforms both the semi-supervised and self-supervised baselines over various rates of labeled nodes, especially outperforming when the number of labeled nodes is smaller, which demonstrates the robustness of GraFN.
Notations. Let = ( , ) denote a graph, where is the set of | | = nodes and is the set of edges between the nodes. The adjacency matrix is defined by A ∈ R × with each element A = 1 indicating the existence of an edge between nodes and , otherwise A = 0. The node attributes are denoted by X ∈ R × , where is the number of features of each node. Additionally, the label matrix is denoted by Y ∈ R × , where is the number of classes, and each row, i.e., Y ∈ R , is the one-hot label vector for node . We denote and as the set of labeled and unlabeled nodes, respectively. Our goal is to accurately predict the labels of nodes that belong to given few labeled nodes, i.e., | | ≪ | |.

PROPOSED METHOD : GraFN
1) Graph Augmentations and Encoding. Given a graph, we first generate two graph views by applying stochastic graph augmentations, which randomly mask node features and drop partial edges. Two differently augmented views are denoted by˜= (Ã,X) and ′ = (Ã ′ ,X ′ ). Each augmented view is fed into a shared GNN encoder, : R × × R × → R × , to obtain low dimensional node-level representations (Ã,X) =Z ∈ R × , and Note that we adopt GCN as the backbone of the GNN encoder.
2) Node-wise Consistency Regularization. Then, to learn augmentation invariant node representations, we minimize the difference, i.e., cosine distance, between the representations obtained from the two differently augmented graphs in a node-wise manner: Note that the above loss can be considered as a simplified version of the self-supervised loss proposed in BGRL. The major difference is that BGRL involves two separate encoders, where one encoder is updated by minimizing the distance between the node representations obtained from the two views, while the other one is updated by the exponential moving average of the parameters of the other encoder to prevent the collapsing of node representations to trivial solutions. On the other hand, GraFN trains only one shared encoder, and we find that the supervisory signals incorporated in the next step help avoid the collapse of representations.
3) Label-guided Consistency Regularization. Although the above self-supervised loss has been shown to be effective, the learned node representations are not class discriminative because the node label information is not involved in the training process. We argue that unlabeled nodes can be grouped together according to their classes by enforcing them to be consistently close with a certain class of labeled nodes on differently augmented graphs. Hence, we compute the similarity between few labeled nodes and all the nodes in the two augmented graphs, and maximize the consistency between the two similarity-based class assignments, expecting that this would help nodes that belong to the same class to be grouped together. More precisely, we first randomly sample labeled nodes per class to construct the support set S, and let Z S ∈ R ( × )× denote ( × ) support node representations 2 . Then, for each anchor node ∈ , we compute the similarity distribution, i.e., predicted class distribution, p ∈ R using anchor-supports similarity in a non-parametric manner by applying Soft Nearest Neighbors(SNN) strategy [2,15] as follows: where sim(·, ·) computes the cosine similarity between two vectors, and is a temperature hyperparameter. p can be considered as the soft pseudo-label vector for node since it is derived based on the labeled nodes in S. Having defined the predicted class distribution as in Eqn. 2, we compute the predicted class distributions for each node ∈ , i.e.,p andp ′ each of which is obtained from˜and ′ , respectively, where the former is considered as the prediction distribution, and the latter is considered as the target distribution. Then, we minimize the cross-entropy between them: where (y,ŷ) is the cross-entropy between the target y and the predictionŷ. Note that for each labeled node, instead of computing the predicted class distribution as in Eqn. 2, we simply assign its one-hot label vector, i.e.,p ′ = Y , ∀ ∈ , to fully leverage the label information. However, naively minimizing the above loss would incur confirmation bias [1] due to inaccuratep ′ computed for unlabeled nodes (i.e., ), which is detrimental to the performance of pseudo-labeling-based semi-supervised methods. To this end, we introduce a confidence-based label-guided consistency regularization: where conf = { |1(max(p ′ ) > ) = 1, ∀ ∈ } is the set of nodes with confident predictions, is the threshold for determining whether a node has confident prediction, and 1(·) is an indicator function.p ′ is considered to be confident if its maximum element is greater than . We argue that setting to a high value helps alleviate confirmation bias [1,17] by enforcing only high-quality target distributionp ′ to be able to contribute to Eqn. 4. It is important to note that we apply a relatively weak augmentation for graph˜′ = (Ã ′ ,X ′ ) that is used to computep ′ , because aggressive augmentations (e.g., dropping more than half of edges) drastically change the semantics of a graph, which may eventually incur inaccuratep ′ . A further benefit of the label-guided consistency regularization defined in Eqn. 4 is that since the class distributions are computed regardless of the structural information of graphs, the label information can be effectively propagated to distant nodes, whereas existing GNNs suffer from ineffective propagation incurred by the over-smoothing issue [9]. Moreover, to break the symmetry of the model architecture thereby preventing the collapsing of node representations to trivial solutions, we stop gradient for the target distribution (i.e.,p ′ ), and only update the parameters associated with the prediction distribution (i.e.,p).

4) Final
Objective. Finally, we combine L NC and L LC with coefficients 1 and 2 to compute the final objective function as follows: We add the cross-entropy loss, i.e., L sup , defined over a set of labeled nodes . The overall pipeline of GraFN is shown in Fig. 2.

EXPERIMENTS
Datasets. To verify the effectiveness of GraFN, we conduct extensive experiments on five widely used datasets (Table 2) including three citation networks (Cora, Citeseer, Pubmed) [16] and two copurchase networks (Amazon Computers, Amazon Photos) [14].
Baselines. We compare GraFN with fifteen baseline methods. (i) Two conventional methods: MLP and LP [30]. (ii) Five graph convolutionbased methods: GCN [7] and GAT [21]. SGC [24] simplifies GCN by removing repeated feature transformations and nonlinearities. APPNP [8] and GRAND [3] alleviate the limited receptive field issue of existing message passing models. (iii) Two self-supervised methods: GRACE [31] and BGRL [20] maximize the agreement of the representations of the same nodes from two augmented views 3 .
(iv) Three label-efficient methods: GLP [10] and IGCN [10] apply a low-pass graph filter to message propagation to achieve label efficiency. CGPN [22] leverages Graph Poisson Network to effectively spread limited labels to the whole graph, and also utilizes contrastive loss to leverage information on unlabeled nodes. (v) Three pseudo-labeling-based methods: Co-training [9], Self-training [9] and M3S [18].
Evaluation Protocol. We randomly create 20 splits to evaluate the effectiveness of GraFN on practical few-label setting. For citation networks, we closely follow the evaluation protocol of [9,19]. For co-purchase networks, we evaluate models with {0.15%, 0.2%, 0.25%} training label rates to match with the average number of labeled nodes per class of the citation networks. The remaining nodes are split into 1:9, and each split is used for validation and test, respectively. We report the averaged test accuracy when the validation accuracy is the highest. For baseline methods including GraFN, we search hidden dimension, learning rate, weight decay, and dropout ratio in  Table 1 shows the performance of various methods in terms of node classification over various label rates. We have the following observations: 1) GraFN outperforms methods that use advanced GNN encoders (i.e., APPNP and GRAND), and label efficient GNNs that effectively propagate label information to distant nodes (e.g., GLP and IGCN) and leverage unlabeled nodes with contrastive loss (i.e., CGPN). We argue that the label-guided consistency regularization helps GraFN to effectively propagate the label information to distant nodes, thereby learning class discriminative representations. Note that GraFN especially outperforms other methods when the label rate is small demonstrating the robustness of GraFN (also refer to Fig. 1). 2) Even though GraFN adopts a simple self-supervised loss with a single shared GNN-based encoder, i.e. node-wise consistency regularization, GraFN outperforms advanced self-supervised methods, i.e. GRACE and BGRL. We attribute this to the label-guided consistency loss that groups nodes that belong to the same class by leveraging the given few labeled nodes. 3) To empirically verify the benefit of the label-consistency regularization of GraFN, we compare the similarity search results of GRACE, BGRL and GraFN in Table 3. Since GRACE and BGRL consider node labels through conventional supervised loss with advanced self-supervised loss, whereas GraFN does so through the label-guided consistency regularization with a simple self-supervised loss, the superior performance of GraFN implies the benefit of the label-guided consistency regularization of GraFN despite its simple self-supervised loss. We indeed observe that GraFN generally outperforms GRACE and BGRL, which corroborates the benefit of the label-consistency regularization for learning class discriminative node representations. 4) We observe that the pseudo-labeling-based methods, i.e., Cotraining, Self-training and M3S, generally outperform vanilla GCN, which solely relies on the given label information. On the other hand, GraFN outperforms these methods without relying on the pseudo-labeling techniques. This implies that the pseudo-labeling techniques should be adopted with particular care as they may introduce incorrect labels. 5) GraFN shows relatively low performance on Pubmed dataset, which contains a small number of classes, i.e., 3 classes. Since GraFN assigns class distributions based on the similarity with labeled nodes in different classes, having more classes leads to more class discriminative node representations.

Performance Analysis
Adopting Pseudo-Labeling to GraFN. Since GraFN learns class discriminative node representations with few labels, we hypothesized that the confirmation bias [1] of the pseudo-labeling technique suffered by existing methods would be alleviated when the pseudolabeling technique is adopted to GraFN. Fig. 3(a) indeed demonstrates that adopting the pseudo-labeling technique to GraFN gives the best pseudo-labeling accuracy, which in turn results in further improvements of GraFN in terms of node classification ( Fig. 3(b)).
Performance Comparison on Different Node Degrees. In most real-world graphs, the node degrees follow a power-law distribution, which means that the majority of nodes are of low-degree. Since the training of GNNs is based on the neighborhood aggregation scheme, high-degree nodes receive more information than low-degree nodes, which eventually leads to the models overfit to high-degree nodes and underfit to low-degree nodes [19]. Fig. 4 demonstrates that the node classification accuracy is indeed highly correlated with the node degree, i.e., high-degree nodes tend to result in better classification performance. Furthermore, we observe that GraFN greatly outperforms other methods for low-degree nodes, while showing a comparable performance for high-degree nodes (i.e. degree ≥ 7). We attribute the superior performance of GraFN on low-degree nodes to the label-guided consistency regularization that promotes the supervision information to be evenly spread over the unlabeled nodes regardless of their node degree.

Ablation Studies
To evaluate each component of GraFN, we conduct ablation studies on Cora and Computers datasets on the lowest label rate, i.e. 0.5%, 0.15%, respectively. In Fig 5, we have the following observations: 1) Only using the supervised cross-entropy loss shows poor performance because it suffers from overfitting and ineffective propagation of supervisory signal. 2) Using both node-wise and label-guided consistency regularization (i.e., GraFN) is more beneficial than using either one of them. We argue that this is because these two losses are complementary. More precisely, using only the node-wise loss cannot fully leverage the given label information, whereas using only the label-guided regularization loss can suffer from inaccurate target distribution, which incurs confirmation bias.

CONCLUSIONS
In this paper, we present a novel semi-supervised method for graphs that learns class discriminative node representations with only few labeled nodes. GraFN not only exploits the self-supervised loss, i.e. node-wise consistency regularization, but also ensures nodes that belong to the same class to be grouped together by enforcing unlabeled nodes to be consistently close with a certain class of labeled nodes on differently augmented graphs. Through extensive experiments on real-world graphs, we show that GraFN outperforms existing state-of-the art methods given few labeled nodes. Moreover, it is worth noting that GraFN 1) alleviates underfitting problem of low-degree nodes by propagating label information to distant nodes, and 2) enjoys further improvements by adopting the pseudo-labeling technique.