FASTRAIN-GNN: Fast and Accurate Self-Training for Graph Neural Networks
Authors: Amrit Nagarajan
Anand Raghunathan
Venue: Accepted by TMLR ()

Abstract: Few-shot learning with Graph Neural Networks (GNNs) is an important challenge in expanding the remarkable success that GNNs have achieved. In the transductive node classification scenario, conventional supervised training methods for GNNs fail when only few labeled nodes are available. Self-training, wherein the GNN is trained in stages by augmenting the training data with a subset of the unlabeled data and the predictions of the GNN on this data (pseudolabels), has emerged as a promising approach to few-shot transductive learning. However, multi-stage self-training significantly increases the computational demands of GNN training. In addition, while the training set evolves considerably across the stages of self-training, the GNN architecture, graph topology and training hyperparameters are kept constant, adversely affecting the accuracy of the resulting model as well as the computational efficiency of training. To address this challenge, we propose FASTRAIN-GNN, a framework for efficient and accurate self-training of GNNs with few labeled nodes. FASTRAIN-GNN performs four main optimizations in each stage of self-training: (1) Sampling-based Pseudolabel Filtering removes nodes whose pseudolabels are likely to be incorrect from the enlarged training set. (2,3) Dynamic Sizing and Dynamic Regularization find the optimal network architecture and amount of training regularization in each stage of self-training, respectively, and (4) Progressive Graph Pruning removes selected edges between nodes in the training set to reduce the impact of over-smoothing. On few-shot node classification tasks using different GNN architectures, FASTRAIN-GNN produces models that are consistently more accurate (by up to 4.4%), while also substantially reducing the self-training time (by up to 2.1X) over the current state-of-the-art methods. Code is available at https://github.com/amrnag/FASTRAIN-GNN.

Published in Transactions on Machine Learning Research (04/2023)
FASTRAIN-GNN: Fast and Accurate Self- Gelf-nnaining for Graph Neural Networks
Amrit Nagarajan
nagaraj9@purdue..cm edu
School of Electrical and Computer Engineering Purduc University
Anand Raghunathan
raghnaahann &purdue. edu
School of Flectrical and Computer Engineering
Purdue University
Reviewed on OpenReview: https: // wwwpr/veeeee.ee....mm net/ forum? id- 1IYJfuJt1
Abstract
Few-shot learning with Graph Neural Networks (GNNs) is important challenge in ex- panding the remarkable success that GNNs have achieved. In the transductive node clas- sification scenario, conventional supervised training methods for GNNs fail when only few labeled nodes are available. Self-training, wherein the GNN is trained in stages by aug- menting the training data with a subset of the unlabeled data and the predictions the GNN on this data (pseudolabels), has emerged as promising approach to few-shot trans- ductive learning. However, multi-stage self-training significantly increases the computa- tional demands of GNN training. In addition, while the training set evolves considerably across the stages of self-training, the GNN architecture, graph topology and training hy- perparameters are kept constant, adversely alfecting the accuracy of the resulting model as well as the computational efficiency of training. To address this challenge, we propose FASTRAIN-GNT framework for efficient and accurate self-training GNNs with few labeled nodes. FASTRAIN-GNY performs four main optimizations in each stage of self- training: (1) Sampling- based Psendolabel Filtering removes nodes whose pseudolabels are likely to be incorrect from the enlarged training set. (2,3) Dynamic Sizing and Dynamic Regularization find the optimal network architecture and amount of training regularization in each stage of sell-trinnng, respectively, and (4) Progressive Graph Pruning removes se- lected edges between nodes in the training set to reduce the impact of smoothin.. On few-shot node classification tasks using different GNN architectures, FASTRAIN-GNN pro- duces models that are consistently more accurate (by up to 4.4%), while also substantially reducing the self-training time (by up to 2.1x) over the current state-of-the-art methods. Code is available at https: / htt.tttttttttt/t///////ee com aawaaa//FASTRRIIN---O
1 Introduction
Advances in supervised training of Graph Neural Networks (GNNs) have revolutionized the field of graph- based learning. As result, GNNs find wide-spread applications in several fields, ranging from friend and product rocommendations in social media networks to molecular property prediction for drug discovery. However, real world graphs are often sparsely-labeled, and training GNNs in a few-shol setting remains challenging. While conventional supervised training methods for GNNs (Kipf & Welling, 2017 Velickovid et al.] 2018 Hamilton et al.] 2017) work well in the presence of large amounts of labeled training data, their performance drops rapidly training data becomes more scarce due to insufficient propagation of information from labeled data.

---

Published in Transactions on Machine Learning Research (04/2023)
Two main classes of semi-supervised training algorithms have been proposed to address this challenge in the context of node classification using GNNs: pre-training and self-training. Pre-training is effective in the inductive node classification setting (where new, unseen graphs are presented at testing time; the goal is to label the unlabeled nodes in the new graphs). Since training GNNs with good gencralization performance is the key for effective inductive node classification, large amounts of non-targeted labeled data can be used to pre-train the GNN, followed by few iterations of fino-tuning on the limited task-specific data. As a result, prior works on pre-training GNNs (Hu et al., 2020 Lu et al. 2021) have demonstrated significant improvements on few-shot inductive node classification. On the other hand, the transductive node classifica- tion setting (a small number of nodes in large graph are labeled; the goal is to label the unlabeled nodes in the graph) benefits more from self-training. In particular, since the entire graph (consisting of both labeled and unlabeled nodes) is available at (raining time, effective transductive node classification is achieved by targeted training on the input graph (learning from the topology and vast amounts of unlabeled data in the graph). Consoquently, prior works on self-training (Li et al. 2018 Sun et al.) have demonstratod good performance on few-shot transductive node classification.
In this work, we focus self- training GNNs for few-shot transductive node classifica- tion, which is outlined in Fig. I Self-training is performed in multiple stages, where a GNN model is trained in each stage using the current train- ing set. At the end of each stage, the training set is en- larged by adding nodes that are likely to be predicted cor- rectly by the trained GNN along with their associated pseudolabels. Typically, confidence used as the metric assess correctness of predictions - if the confidence of the GNN in predicting a node is above a threshold (T2), the node is added to the training set for the next stage. The enlarged training set results in greater fraction of nodes in the graph participating in the training process (through message passing), leading to better node representations, and hence, better classification accuracy. While the conventional self- training framework has led to substantial accuracy improvements over single-stage supervised training (Li et al. 3 Sun et al.), it presents significant computational overheads during training. For example, on [Cora, Citeseer and Pubmed] datasets with 4 labeled nodes/class, 4-stage self-training takes (4.6x, 5.2x and 5.4x] longer than single-stage fully-supervised training (not exactly 4x longer, since the training set is also enlarged in each stage, see Appendix Ap. In addition, while prior efforts have led to significant improve- ments in the accuracy of pseudolabels added to the training set in each stage, the GNN architecture, graph topology and training hyperparameters (such as strength of regularization) have been kept constant through- out self-training, adversely impacting both the accuracy of the model and the efficiency of the self-training process.
Confidence-baseee training set augmentation: If confidence (node]> T, add node to training set
Graph
Augment training set
GNN model
Train
Enlarged training set
Training set
Trained
Repeat for K stages
GNN
Figure 1: An overview of self-training for GNNs.
We present FASTRAIN-GNN, a framework for fast and accurate self-training of GNNs. FASTRAIN-GNN adds four main optimizations to the conventional self-training loop. First, we observe that incorrect training labels have large detrimental effect on the accuracy of the trained model, and propose Sampling- based Pseudolabel Filtering (SPF) to improve the accuracy of pseudolabels added to the training set. We also propose Dynamic Regularization (DR) to reduce the impact of residual errors in training labels (after SPF) during self-training. Second, we note that the "layer effect in GNNs (Sun et al.) plays a major role during the different stages of trafnnnr Deep GNNs outperform shallow GNNs when training on few labeled nodes due to larger message passing coverage (leading to better propagation of information from labeled nodes) in deep GNNs. However, as the number of labeled nodes increases, the larger message passing coverage leads oversmoothing in deep GNNs, where nodes belonging to different classes acquire similar representations and become less discernible from each other. As a result, shallow GNNs outperform deep GNNs when training on large numbers of labeled nodes. Based on this observation, we propose Dynamic Sizing (DS) to adapt the network architecture across the stages of self-training. Finally, we observe that inter-class edges in the graph
2

---

Published in Transactions on Machine Learning Research (04/2023)
add noise during message passing, and propose Progressive Graph Pruning (PGP) to incrementally prune inter-class edges between nodes in the training set. While different pruning techniques such as the Lottery Ticket Hypothesis (Chen et al. 2021) and sampling (Zhang et al. 2023) have been proposed for improving the training and inforence efficiency of GNNs, SPF and PGP use pruning for achieving gains beyond just efficiency. SPF randomly prunes a small subset of edges in the graph to lest. the robustness of predictions to perturbations the graph structure, thereby filtering out incorrect training labels. On the other hand, PGP prunes inter-class edges reduce over-smoothing from noisy message passing, thereby leading to better generalization performance. In addition to producing more accurate self-trained models, the four proposed optimizations also considerably improve the efficiency of the self-training process. SPF reduces the size of the training set, while DS, DR and PGP result in smaller GNNs being trained on sparser graphs.
We summarize our main contributions as follows:
We introduce FASTRAIN-GNN, a framework for fast and accurate self-training of GNNs In particular, FASTRAIN-GNN focuses on optimizing the GNN architecture, training data, training parameters, and the graph topology during self-training.
We propose Sampling-based Pseudolabel Filtering to generate smaller training sets with more accurate pscudolabels in cach stage.
We propose Dynamic Sizing and Dynamic Regularization to overcome the layer effect in GNNs and reduce the impact of incorrect training labols, respectively.
We propose Progressive Graph Pruning to improve the information--o-nniss ratio during message passing and reduce the impact of over-smoothing in GNNs.
Across four different transductive node classification datasets using different GNN architectures and with varying numbers of labeled nodes, we demonstrate that FASTRAIN-GNN simultancously improves both the accuracy of the self-trained models and the efficiency of self-trinnng over the previous slate-of-the-arl.
2 Related Work
Prior work on self- self-training GNNs has almost exclusively focused on the problem of generating more accurate training labels (pseudolables) in each stage of self-training. [i et al. (2018) proposed four different techniques for gencrating more accurate training labcls. Co-training trains random walk model along with the GNN to explore the graph structure, and adds the most confident predictions of the random walk model to the training set. Self-training adds the most confident predictions from the GNN to the training set. Union adds a union of the most confident nodes found by the GNN and the random walk model, while Interscction adds the common subset of most confident predictions of both models to the training set. Recent works have proposed improvements to these original baselines. Some notable examples include DSGCN (Zhou let al. 2 ; which uses negative sampling and confidence-based based weighting of samples to reduce the impact of incorrect training labels. M3S (Sun et al.) introduces checker based on DeepCluster (Caron et al. 2018
that verifies the correctness of the most confident predictions before adding them to the training set. TFC- GCN (Hu et al.
2021 rectifies incorrect pseudolabels based on feature clustering. GraphMix (eerma et al.) trains a fully-connected neural network along with the GNN to improve the accuracy of GNN predictions.
CGCN (Hui et al. 2020) validates pseudolabels based on predictions from a graph clustering network that
combines variational graph auto-encoders with Gaussian mixture models. Self-enhanced GNN (Yang et al., 2021) enlarges the training set using the most confident predictions from an ensemble of GNNs. Finally, the current state-of-the-art method (see Appendix C for self-training is CaGCN (Wang et al.) 2021 which uses confidence calibration (Guo et al. 2017) to improve the accuracy of the most confident predictions. Complementary to these works, we focus on the problem of how the enlarged training set can be used to efficiently self-train GNNs to high accuracies, with a specific focus on optimizing the GNN architecture, training parameters and graph topology during self-training. In addition, we also propose a simple filtering mothod based on robustness to sampling that quickly identifics and removes nodes that are likely to be incorrectly labeled from the enlarged training set. While sampling has been demonstrated to be an effective regularizer for improving both the training efficiency (Chen et al. 2018 Ramezani et al., 2020 Zhang et al.
3

---

Published in Transactions on Machine Learning Research (04/2023)
2023 and generalization ability (Hamilton et al 2017 Li et al. 2022 of GNNs, show that sampling
also be used to test. the robustness of GNN predictions to small perturbations ions in the graph structure.
3
The FASTRAIN-GNE framework
Repeat for K stages
Sparser (Pruned) Graph
Graph
DR
GNN model
DS
Smaller GNN model
Augment training set
SPF
PGP
Train
Trained GNN
Enlarged training set
Training set
Smaller (filtered) enlarged training set
Figure 2: An overview of the FASTRAIN-GNN framework.
We present FASTRAIN-GNN, a framework for efficient and accurate self-supervised training of GNNs. Fig presents an overview of the FASTRAIN-GNN framework. First, the appropriate GNN architecture is chosen based on the current size of the training set (DS), and the model weights are randomly initialized. This random initialization is different from the majority of previous works (such as Zhou al. (2019); ; Li et al. (2018) etc.) that initialize the model using the trained weights from the previous stage (see Appendix B Then, the GNN model is trained on the current training set, and the amount of regularization during training is chosen based on the stage of self-training (DR). The training set is subsequently enlarged by predicting the unlabeled nodes with the trained GNN, and adding nodes that are likely to be predicted correctly to the training set. Here, we use confidence- based pseudolabeling, where nodes that are predicted with confidence above a threshold (T2) are added to the training set along with their pscudolabels. The enlarged training set is then filtered based on the robustness of predictions small perturbations in the graph topology (SPF), to produce smaller training set with more accurate labels. Finally, inter-class edges between nodes in the training set progressively pruned (PGP) to improve informationnto-nooie ratio during message passing (when the pruned graph is used to train the GNN model in the next stage). This process is repeated K times, where each iteration of this loop constitutes one stage of sell-training.
Cora
Citeseer
Pubmed
Trained modal accuracy (35
Trained model accuracy
90
60
70
Trained
50
60
60
90
100
60
70
80
90
100
60
70
80
90
100
Training label accuracy (%)
Training label accuracy (%)
Training label accusacc (94)
Sampling rate:
00..9
Sampling rate:
Sampling rate:
Figure 3: Impact of incorrect training labels on GCN training. Results are reported based on fully-supervised training of 2-layer GCN model, following the settings described in (Rong et. al.) 2020). random subset of training labels are changed to an incorrect (random) class for this study, and results are averagod across 100 runs (error bars indicate standard deviation).

---

Published in Transactions on Machine Learning Research (04/2023)
In summary, FASTRAIN-GNY adds four main optimizations to the conventional self self-training loop SPF, DS, DR and PGP. We describe these opt optimizations in the following subsections, with more detailed explanations in Appendix D
3.1 Sampling- baase Pseudolabel Filtering (SPF)
SPF is performed immediately after the training set is enlarged by adding nodes with highly confident predictions and their pseudolabels. Since the accuracy of the self-trained model de- grades rapidly with decrease in accuracy of the training labels (Fig. B. it vital to ensure that the psoudolabels are highly accurate. While confidence is the current state-of the-arrtr met- ric for quantifying the correctness of predictions, we observe that the labels generated by confidence-based pseudolabeling still contain substantial noise that has a detrimental impact on the final model accuracy. SPF takes advantage of the fact that correct predictions are significantly more robust to small perturbations in the graph topology compared incorrect pre- dictions (Fig, 4 to filter out nodes that are likely have in- describes the procedure used to perform SPF. We randomly sample the input graphs with sampling rate of spf upf_sampling rate (denoting the fraction of edges that are retained). This is repeated across spf_iterations,, with each iteration testing on a different sam- pled graph. Only those nodes whose predictions are invariant. under sampling are included the filtered training set. As result, SPF produces smaller training set with more accurate training labels, leading to improvements in both the efficiency of lif--training and the accuracy of the self-trained model.
100
Accuracy nodes with
consistent prediction (%)
80
Sampling rate
Cora
Citeseer
Pubmed
Figure 4: Accuracy of consistent predictions with different. sampling rates. Results are reported based on full-supervised training a 2-layer GCN model. Here, "consistent predictions" indi- cates that node predictions do not change when predicted from 10 different randomly sampled graphs.
correct labels from the training set. Algorithm [
Algorithm 1: Sampling based Pseudolabel Filtering (SPF)
Input Enlarged training set after confidence-based pseudolabel generation (Tinse), graph (G) Output: Filtered training set (Tritteeed)
spf ______amppg__aaa prate sampling rate to test prediction consistency
_tterraiion number of sampling iterations test prediction consistency Tyttered Timst
Initial Initial_prediineee p..ppecciiosssse predict(nodes(())
for sampling ileration in range(spf jiterations) do range((ppfiitrrations)
Grampied Sample(G, spʃ spf_ samplling _rate)
predictions Sampled__pediictions for each node in Tfittered do if Sampled (redictions/node] != Initial predictions/node then Tratsred filtered node
10
11 return Tyatteed
3.2 Dynamic Regularization (DR)
While SPF significantly improves the accuracy of training pseudolabels, incorrect labels are inevitable when they are generated from the predictions of a neural network. DR aims to reduce the impact of residual errors in pseudolabels, since even a small number of incorrect labels can lead to large deterioration in accuracy of the trained model (Fig. 3). While overfitting to incorrect labels problematic for all classes deep neural networks, we find that et al. (202).. Nodes that acquire representations that cause them be incorrectly classified during training adversely impact the classification of all their neighbors due to message passing. Therefore, it is vital to
especially true for GNNs due to the effects of error propagation (Nagarajan)
5

---

Published in Transactions on Machine Learning Research (04/2023)
Algorithm 2: Dynamic Regularization (DR) and Dynamic Sizing (DS)
Input
Stage of self-training (stage), Training set (T)
Output: GNN model (gun) and sampling rate (sampling rate) to be used in stage
sampling r_terat______ init: sampling rate used in the first stage of self-training when only nodes with golden labels are used for training
sampling_ rate__te____________ rate_finall= final:
sampling rate used in the later stage of self- training when nodes with both golden- and pseudo-labels are used for training
deep deep_grat gnn urchilecture of the deep GNN used in the initial stages of sell-training when only few nodes are used for training
shallow_ gnn architecture of the shallow GNN used in the later stages of self-training when large numbers of nodes are used for training
DS Threshold: the size of the training set at which the deep gra is be replaced by the shallow_ grem if stage = then
sampling_ rate sampling rate irit
else
sampling rate sampling_rod pratengggrrreeee final final
if cordinality(T) DS Thrrshold then
11
gan = deep_gnn
12 else
gnn deep_gmn gmn
14 return grm, sampling rate
incorporate techniques that minimize the impact incorrect labels in the self-training loop to prevent error propagation. Increased regularization has been shown to improve training the presence of noisy labels (Liul et al. 2020), , and we find that sampling (Hamilton al. 2017 Chen al.) (0088) is an effective regularizer that prevents overfitting to incorrect labels (Fig. 3). We propose DR to dynamically alter the sampling rate during soff-training to account for noisy labels in the enlarged training set. The procedure for performing DR is depicted in Algorithm In the first stage of self-training, training labels are golden (100% accurate), and hence, we use high sampling rates (most edges are retained in the graph). We then dynamically reduce the sampling rate as pseudolabeled nodes are added to the training set to account for the reduced accuracy of training labels. effect, DR provides the dual benefit resilience to noisy pseudolabels during self- tralniga,nnng, and improved efficiency from training on sparser graphs in the later stages of self-training.
3.3 Dynamic Sizing (DS)
DS overcomes the layer effect (Sun et al.) in GNNs during the different stages of self-training. Deep GNN models perform better than shallow GNN models when only a small number of labeled nodes are available
Cora
Citeseer
Pubmed
90
90
90
80
Accurscy (%)
Accuracy (%)
70
70
70
Recuresy
50
50
50
30
30
16
92
16
32
nodes/class
nodes/class
Labeled nodes/class
2-layer 2-layer 3-layyr 3-layer
2-layer Z-layer 3-layyr 3-layer
#--layer 2-layer GAT 3-layer 3-layer
Figure 5: Demonstration of the layer-effect in GNNs. Results are averaged across 100 random train- test splits, and error bars indicate the standard deviation.

---

Published in Transactions on Machine Learning Research (04/2023)
due to better propagation of label information. In particular, since all L-hop neighbors participate in the prediction of node through message passing in T-layer GNN, more nodes participate in the training process in deeper GNNs, leading to better node representations. As the number of training nodes increases, there is greater supervision during training, and hence, shallow GNN architectures start performing better due greater message passing coverage (Fig. 5 Eventually, under sufficient supervision, shallow GNNs start outperforming deeper GNNs due to the oversmoothing problem deeper GNNs (Chen et al. 2020a Due to the smoothing effect of GNN layers, the representations of nodes belonging to different classes become less distinguishable from each other when large number of labeled nodes used to train deep GNNs. During self-training, as the training set is progressively enlarged, we observe that the layer effect plays a major role. Initially, when the training set is small, deeper GNNs are more accurate. As the training set is enlarged by generating more and more pseudolabels, shallow GNNs perform better. DS varies the model architecture used in each stage of self-training based on the size of the training set. The procedure for performing DS is also depicted Algorithm 2 When the size of the training set excoeds a threshold (DS Threshold), shallow GNN is used for all further stages.
3.4 Progressive Graph Pruning (PGP)
Pruning edges from graphs used for transductive node classifi- cation can have a significant impact on training (and inference) efficiency of GNNs due to the exponential complexity of mes- sage passing (Chen et al., 2021 Nagarajan et al. 2022). In addition, it has been proven that pruning inter-class edges in homophilous graphs (where connected nodes are likely to have similar labels) improves the information- to to-ioe ratio during message passing and helps alleviate the over-smoothing prob- Jem to an extent (Chen al., 2020ap. In particular, mes- sage passing between nodes of different classes causes all nodes in the graph to acquire similar representations (making them indistinguishable). When inter-class edges are pruned, nodes belonging to different classes acquire distinet representations, thereby leading to better class separation, and hence, better classification performance (Fig. G). When only few labeled nodes are available for training, identifying inter-class edges is challenging. Hence, propose progressively pruning inter- class edges in each stage based the pseudolabels of nodes added to the training set. Since nodes added to the training set are significantly more likely to be predicted correctly com- pared to other nodes, restricting PGP to operate only on nodes in the training set minimizes the risk of accidentally pruning intra-class edges.
Trained model accuracy
90
80
75
20
40
60
80
100
Percentage inter-class edges
Cora
Citeseer
Pubmed
Figure 6: Impact of pruning inter-class edges between training nodes on ac- curacy. Results are reported based on full- supervised training of a 2-layer GCN model. A random subset of inter-class edges are pruned, and results are averaged across 10 runs (error bars indicate standard devia- tion).
Algorithm 3: Progrossive Graph Pruning (PGP)
Input: Enlarged training set after SPF (Tyittered); graph (G) Output: Pruned graph Gpruned
Predictions = predict (nodect(oo))((G) Gpraned G
for each node in Tytttrred do for each neighhor of node do
5
if neighbor in Tylttered then
if Predictions/node; != Predictions/neighbor/ then Gpruned = G Gyraned ende, neighbor)
7
return Gyruned

---

Published in Transactions on Machine Learning Research (04/2023)
Algorithm demonstrates PGP. After SPF generates enlarged training set with pseudolabels, PGP then prunes inter-class edges between nodes in the training set. Since the training set is progressively enlarged in each stage of self-training, PGP progressively prunes inter-class edges during self-training, thereby making each iteration of the self-training loop faster than the previous iteration. When GNNs are self-trained on heterophilous graphs (where connected nodes are likely to have dissimilar labels), we modily PGP prune intra-class edges instead of inter class edges (sce Appendix
4 Experiments and Results
We implement FASTRAIN-GNT using DGL in PyTorch, and evaluate it on GeForce RTX 2080 Ti GPU with 11GB mem--
Table 1: Dataset characteristics.
Dataset Classes
Nodes
Edges
Feature size
ory. We randomly select (labels/class) nodes of each class as training nodes, and report results on the rest of the nodes in the graph (we do not require a separate held-out validation set for any of the FASTRAIN-GNN oplimizations). We repeat.
Cora
7
2708
5429
1433
Citeseer
6
3327
4732
3703
Pubmed
3
19717
44338
500
CoraFull
19793
126842
8710
this process 100 times for each value of (labels/ /class, and all results reported in this section are averaged across 100 different training splits (with error bars indicating accuracy range), unless otherwise specified. summarized in Table [ Since some classes contain too few nodes to get
The datasets used for testing meaningful train-test split in CoraFull, we do not present results with 16 labels/class, The details of the hyperparameters used in all experiments are presented in Appendix D
Table 2: Results of training GCN with different label rates. The most accurate model without confidence calibration underlined, while the most accurate model overall is displayed in bold. Subscripts denote standard deviation.
Labels/
FASTRAIN -GCN
Self-train -CaGCN
FASTRAIN -CaGCN
Dataset
GCN
Co-train
Union Intersection
Self-train
Class
48.92.4
53.32.0
53.62.2
51.8
52.72.2
56.9
57.2
61.62.1
64.31.
66.51.
66.32.2
64.21.7
66.11.9
68 68.81
69.514
73.01.
Cora
69. l2.1
71.11.
71.2
69.71.3
70.8
72.71.5
71.9
74.1
8
74.8p.9
75.0p.
75.70.9
74.70.9
75.5g.7
77.4p.s
79.4g.
81.6p.5
16
78.8
78.90.
78.8p.7
78.20.7
79.1a.8
80.6p
82.2
83.4g.6
1
38. 18.1
39.8
39.5a.1
38 38.22.a
39.3s.4
43.1
46.22
53.1g.1
49.9a.2
52.42.
52.62.9
52.62.6
52.926
54.8
53.924
57.12.4
Citeseer
58.12.3
60.42.2
60.32.5
60.72.2
60.12.5
63.82
64.71.0
68.2
8
64.41.4
66.21.6
65.91.7
66.0t.6
66.81.5
68.91.a
70.6
72.81.1
16
19.1
70.2
70.10.
70.3
70.01.1
71.6
72.
73.1
42.8
58.22.7
57.92.5
56.82.
57.7
60.42.
66.52.3
71.4g.1
56.12.2
68 68.22.1
68.62.8
67.92.2
68.42.7
69.62.5
73.92.1
Pubmed
63.31.7
19.42.1
69.62.4
69.62.1
69.71.9
71.12.1
70.9
74.31.
69.9h.
71.4..1
71.3p.8
71.0
71.71.4
72.9 :s
74.3p.7
76.21.0
16
76.7p.
77.21.1
77.4p.
77.5p.
77.40.4
78. 78.66
78.1
79.4g.5
1
26.43.6
30.42.
30.14.1
27.3a.3
29.1
31.1a.8
30.6g.
31.8g.a
2
29.6
32.8s.8
33.1g.9
29.7g.1
33.04.3
35.14.0
33.82.
35.6g.3
CoraFull
4
43.22.4
44.82.0
44.9a.1
43.92.
44.72.1
46. 62.62
45.9
47.22.a
53.22.6
55.01.9
55.22.2
54.62.0
55.62.2
56.41.9
56.31.
57.21.
4.1 Primary Results
We present results on the Cora, Citeseer, Pubmed and CoraFuul datasets with different label rates using different GNN architectures GCN in Table 2 and GAT in Table B To provide fair comparison of ensure the following (1) the same set of nodes
FASTRAIN-GNN with other methods (except CaGCN), threshold T. is fixed at 0.8. (3) 4 stages of self- are labeled for all training methods. (2) The confidence training are performed, with 500 epochs of training in each stage in all methods. For all experiments on CaGCN, we follow the best hyperparameter settings described by the authors (Wang et al., 2021). We note that our implementation of the bascline self-training methods (Co-training, Union, Intersoction, Self- training) achieves significantly higher accuracy (by up 10%) than previously reported (Li al. 2018 Zhou al. 2019). This because optimize the baselines (see Appendix B by choosing the optimal

---

Published in Transactions on Machine Learning Research (04/2023)
number of GNN layers for different label rates, and by randomly initializing the GNN model at the start of each stage of self-training (rather than initializing with the trained weights from the previous stage). We find that FASTRAIN-GNN consistently outperforms conventional self-training methods under different In addition to producing models that are up to 4.2% more accurate than these optimized baselines, FASTRAIN-GNY also accelerates the self-training process, reducing the wall-clock self-training time by (1.7x, 1.9x, 2.1x and 1.7x] on {Cora, Citeseer, Pubmed and CoraFull) respectively compared to conventional self-training. In addition, we demonstrate that FASTRAIN-GNN can be used in conjunction with the current state-of-the-art method (to the best of our knowledge) for self-training CaGCN (Wang et al. (021). This combination, which we call FASTRAIN-C&GON and I'ASTRAIN-CGGAI, uses confidence calibration to improve the quality of pseudolabels generated in each stage to achieve further accuracy gains of up to 4.4% using the same hyperparameters and initial set labeled nodes.
label rates (Tables 2 3
Table 3: Results of training GAT with different label rates. The most accurate model without confidence calibration is underlined, while the most accurate model overall is displayed in bold. Subscripts
denote standard deviation.
Labels/
FASTRAIN
Self-train -CaGAT
FASTRAIN
Dataset
GAT
Co-train
Union
Intersection
Self-train
Class
-GAT
-CaGAT
1
49.72.7
54.82.
54.52.
53.62.8
53.92.
57.12
59.32
63.32.4
2
65.
67.62.3
67.71.
66.41.7
66.31.9
69.62.
70.422
74.11.
Cora
4
70.21.7
71.81.
71.62.
70.62.1
71.91.5
73.21.9
72.914
75.81.4
8
75.41.8
76.21.4
76.71.4
75.0 .
76.31.3
78.41 .
79.814
81.71.0
16
79.
79.41.5
79.81.a
78.80.7
80.0g.s
82. lo.6
83.01
84.2u.7
36.94.1
38.74.3
38.84.7
37.73.9
38.34.4
40.24.6
44.8
48.9a.9
2
49.03.6
51.6g.7
51.73.7
51.91.3
51.7s.5
53.65
52.5g.9
55.83.7
Citesoer
4
56.42.
58.8a.1
58.2a.
59.12.7
59.2s.0
61.9s.
62.314
65.729
8
62.81.
64.92.6
64.32.
65.22.
65.22.2
66.61
67.421
69.52.
16
66.82.1
68.7
68.82.0
69.3
69.0
70.2
70.8
72.0
40.72.
55.42.6
55.92.7
54.82.7
54.52.4
57 57.22
59.92.
63.7
2
52.62.1
64.72.9
64.62.3
63.82.6
15.
68.42.
68.62.1
72.42.7
Pubmed
4
62. 12.3
68.4g.
68.12.1
68.6
68.51.8
7U.32
70.12,
73.61.
8
69.th.7
70.91.7
71.21.5
71.11.8
71.418
72.61
73.714
75.61.7
16
76.30.7
76.9..1
77.01.0
77.
77.20.7
78.40.7
77.90.4
79.0p.7
28.64.4
31.84.7
32.1a.9
29.74.3
31.6g.9
32.74.
33.1
34.64.2
31.2s.7
33.74.5
34.21.7
32.9s.7
33.84.6
35.5
34.23.9
36.73.6
CoraFull
4
45.4a.2
47.2a.3
47.44.2
46.62.9
46.92.9
48.3a.a
47.74.5
49.0g.7
8
53.42.7
55.62.1
55.72.0
55.02.2
55.72.5
56.52
56.22.1
57.42.3
4.2 Ablation Study: Breakdown of benefits from different FASTRAIN-GNA optimizations
We perform ablation study to evaluate the impact of each optimization performed by the FASTRAIN- GNN framework. The results are presented in Table g SPF improves accuracy by removing nodes whose pseudolabels are likely to be incorrect from the training set in each stage, and it improves efficiency by reducing the number of training samples in each stage. DS and DR improve accuracy by taking advantage of the layer effect GNNs (Sun et al.),, and by reducing the impact of incorrectly labeled nodes in the training set, respectively. In addition, they improve efficiency by training smaller GNNs on sparser graphs in later stages. Finally, PGP improves accuracy by reducing noise from inter-class edges CCen al. 2020a). and it improves efficiency by making the graphs more sparse. We also note that the different optimizations add minimal overheads (Appendix B In the following subsections, we discuss and analyze the contribution of each FASTRAIN-GNN optimization in improving the accuracy and efficiency of the previous state-of state-of-the-art self-training mothod (CaGCN).
4.2.1 SPF improves the quality of generated pseudolabels.
Confidence- pscudolabeling can lead noisy labels, even when the models are confidenco-calibraated,, as seen in Fig. 7 By adding second layer of filtering based on robustness to small perturbations in the graph structure, SPF consistently generates more accurate pseudolabels than confidence-based pseudolabeling,

---

Published in Transactions on Machine Learning Research (04/2023)
Table 4: Accuracy and efficiency gains from the different FASTRAIN-GNI optimizations on
Cora. Speedup is computed over self-training of the more accurate among 2/3-layer models, and averaged across different train/test splits and label rates.
Self-Training-
CaaninnngCGGNNNNN CaGCN
with SPF and DR
with SPF,
with SPF, DR,
Labels/ Class
(2-layer/ 3-layer CaGCN) (2-layer/ 3-layer CaGCN)
DR and DS
DS and PGP
55.82.1 / 57.219
57.12. 58.31s
60.419
61.62.1
2
64.4 69.51.4
66.1 70.9..
72.21.7
73.0
68.21. / 71.91.
6..1 72.616
73.41.1
74.11.2
8
79.40.6 / 77.61.1
80.31.1 78.90.9
60.90.s
81.6p.5
16
82.2g.6 80.3a.8
82.7o.4 81.5p.s
82.70.5
83.4p.6
Average Speedup
1X
1.3X
1.6X
1.7X
While the quality of confidence- based pseudolabels can be improved by increasing the confidence threshold, demonstrate that SPF produces (1) more accurate pscudolabels when both methods add the same number of nodes to the training set, and (2) smaller set of training nodes with more accurale pseudolabels for different confidence thresholds in Fig. In fact, with confidence threshold of 0.99, SPF generates training sets that are 1.2x smaller with 5.3% more accurate labels on Cora (4 labeled nodes per class) during self- training. Similarly, with 8 labeled nodes per class, SPF generates training sets that are 1.2x smaller with 4.8% more accurate labels compared to training sets generated solely based on confidence. We find that using 10 spf _if_reteioo with spf sis_sssmllnng___ rate of 0.9 works well in all our experiments. While the accuracy of training labels can be marginally improved by using smaller values of spf sampling rale (Fig D. the number of nodes added to the training set in each stage decreases greatly. For instance, on Cora with 4 labels per class, 1801 nodes are added to the training set (label accuracy 85.1%) over the course of self-training with spf sampling rate of 0.9. When a spf sampling rate of 0.8 is used, only 1206 nodes are added to the training set (label accuracy = 85.4%). As a result, the accuracy gains from multi-stage self- ouffttraining are diminished when _tal__samlligggg___ rate is too small.
Training label accurscy (%)
Cora (4 labels/class)
Training accuracy (%)
Cora (8 labels/class)
90
85
80
70
75
60
70
1000
1500
2000
2500
3000
1500
2000
2500
3000
Size of training set
Size of training set
Confidence
Confidence + SPF
Confidence
Confidence SPF
Figure 7: Accuracy of pseudolabels generated for different confidence thresholds with and with- out SPF. Results shown are based on all the nodes added to the training set during self- training of a 3-layer CaGCN model. The different points on the curves are obtained by varying the confidence threshold from 0.2 (far-right) to 0.99 (far-left). For SPF, 10 spf ileralions are used with a spʃ sampling rale of 0.9 to test consistency of predictions.
4.2.2 DR reduces the impact noisy training labels.
While SPF helps reduce noise in training labels by filtering out nodes that are likely to be incorrectly classified, DR minimizes the impact of rosidual crrors in training labels after SPF. We demonstrate that dynamically altering the sampling rate is elfective at reducing the impact of label noise in Fig. g During the first stage of self tnff-training (when golden labels are used), higher sampling rates provide better accuracy. As label accuracy decreases, lower sampling rates prevent overfitting to noisy labels. Therefore, we find that reducing the sampling rate after the first stage of self training leads to significant improvement in accuracy of the final self-trained model (Fig. R and we empirically find that reducing the sampling rate from 0.9 (10% of incident edges of node are randomly pruned in each training epoch) in the first stage 0.8 after the first stage provides highest accuracy across datasets and GNN architectures.
10

---

Published in Transactions on Machine Learning Research (04/2023)
Cora (4 labels/class)
Cora (8 labels/class)
78
Accura
76
74
Sampling Self-training stage
Self-training stage
(0.9.0.8,0...0008))
Sampling rate:
(0.90088,0.8.00.8
Figure 8: CaGCN accuracy across self-training stages with different sampling rates. Results are obtained from self-training a 3-layer CaGCN model with confidence threshold 0.8.
4.2.3 DS overcomes the layer effect across different self-training stages to improve final accuracy.
Prior research has demonstrated the 'layer effect" in GNNs, where deeper GNNs are required effective information propagation the presence of very few training nodes (Sun al.). As the number of training nodes increases, GNNs with less layers tend to achieve higher accuracy due to the over-smoothing problem Chen et al. 2020a) in deeper GNNss Here, demonstrate that the 'layer effect" plays significant role during the different stages of self-training (Fig. 9h. With 4 labeled nodes CaGCN outperforms the 2-layer CaGCN due to better propagation of label information. However, we demonstrate that substantial accuracy gains can be achioved by switching to a 2-layer CaGCN model after the first stage of self-training when more nodes are added to the training sel (approximately 300 nodes per class this case). When starting with 8 labeled nodes per class, the 2-layer CaGCN model achieves higher accuracy at the end of self-training, even though 3-layer CaGCN model is more accurate (and hence, generates more accurate pscudolabels) after the first stage. Since the accuracy gap between the models at the end of the first stage is small, we find that the over-smoothing issue outweighs the advantages of a more accurate training set in the 3-layer CaGCN model. Therefore, we find that using a 3-layer CaGCN model in the first stage of self-training and 2-layer CaGCN model in all subsequent stages enables reaping the benefits of a more accurate training set without encountering the over-smoothing problem, leading to the most accurate predictions on unlabeled nodes. Across different datasets and GNN architectures, we empirically observe that when approximately 2.5% of all nodes in the graph labeled, there is sufficient supervision for 2-layer models to outperform 3-layer (and deeper) models in all stages of self-training. As result, when number of labeled nodes per class increases, the accuracy gains from DS diminish, since there is sufficient supervision to cause over-smoothing in deep GNNs even in the first self- self-training stage (Table
class Cora, the 3-layer
Cora (4 labels/class)
Cora labels/class)
Accuracy (N)
Accuracy
70
79
76
60
70
4
2
Self fiff-traiinn stage
Self talf-training stage
B layers
Bi layers
DS (3,2,2,2) layers
2 layers
B layers
ii DS (3,2,2,2) layers
Figure 9: Stage-wise accuracy during self-training of CaGCN with confidence threshold of 0.8.
11

---

Published in Transactions on Machine Learning Research (04/2023)
4.2.4 PGP significantly outperforms single-shot pruning of inter-class edges.
PGP only prines inter-class edges between nodes in the train- ing set in each stage. PGP improves accuracy over methods that do not prune inter-class odges, since inter-class edges add noise and exacerbate the over-smoothing problem (Fig. [0].
Cora
90
Accuracy (56)
80
When only few training nodes are available, PGP also signifi cantly outperforms one-shot pruning (edges are pruned based predictions of all nodes after the first stage of self- relf-training: if the prediction of node does not match the prediction of its neighbor, then the edge between the node and its neighbor is pruncd). In fact, the difference in accuracy between PGP and one-shot pruning can be as high as 15%, and this difference is highest. when the number of labeled nodes/class (Fig. 10). In fact, we find that with 4 labels/ / /class, one-shot pruning prunes 54% of all inter-class edges in the graph, while also incorrectly pruning 21% of all intra-class edges, thereby leading to a large drop in accuracy. In contrast, PGP prunes 62% of all inter-class edges, while pruning only 7% of all intra-class edges at the end of sell-training.
60
4 labels/clee class
labels/class
No pruning
B One-shot pruning
PGP
minimum
Figure 10: CaGCN accuracy with dif- ferent pruning methods. Results are ob- tained from self-training a 3-layer CaGCN model with confidence threshold 0.8.
5 Discussion
In this section, we describe limitations of the proposed framework and identify directions for future research.
While SPF, DR and DS work well on homophilous and heterophilous graphs, pruning inter-class edges through PGP is applicable only to homophilous graphs, where connected nodes are expected to have similar labels (for example, citation networks, where authors are likely to cite authors working in similar fields). the case of heterophilous graphs, connected nodes have dissimilar labels, and hence, pruning inter-class edges highly undesirable. In graphs that rely on the heterophily assumption, slightly modified version of PGP pruming intra-class edges instead of inter-class edges leads to accuracy gains by reducing the effect of over-smoothing (see Appendix
F However, PGP cannot be trivially modified to work with graphs where both inter-class and intra-class edges are prominent (for example, molecular graphs, where aloms are connected to both other atoms of the same kind, and to atoms of different kinds).
In FASTRAIN-GNN, we only consider optimizations that simultancously improve both accuracy and com- pulational efficiency. Future work can use insights from FASTRAIN-GNN to maximize either the accuracy or training efficiency of self- self-training but not both. For instance, adding virtual intra-class edges (in addition to pruning inter-class edges with PGP) can further improve the information-to-nonn
during message passing, and hence, further increase accuracy at the cost of training elficiency. Similarly, pruning less-imporlant edges also during PGP (using methods such Lottery Ticket Hypothosis CCen et al. 2021 can lead to further efficiency gains at small accuracy cost.
6 Conclusion
In this work, we presented FASTRAIN-GNN, a framework for fast and accurate self-supervised training of GNNs. The framework introduced four major optimizations to conventional multi-stage self-training. compling-basede Pseudolabel Filtering was proposed to obtain smaller training sets with more accurate train- ing labels. Dynamic Regularization was proposed to reduce the impact of residual errors in training labels after SPF. Dynamic Sizing was introduced to overcome the layer effect during self-training. Finally, Progres- sive Graph Pruning incrementally removed inter-class edges from the graph to improve the information-te noise ratio during message passing. We demonstrated that FASTRAIN-GNN simultancously accelerates the self- seff-training process and improves the accuracy of the self-trained models over the current state-of tfefthh-rrtt methods.
12

---

Published in Transactions on Machine Learning Research (04/2023)
7 Acknowledgement
This work was supported in part by the Center for the Co-Design of Cognitive Systems (CoCoSys), a JUMP2.0 center sponsored by the Semiconductor Research Corporation (SRC) and DARPA, and in part by SRC under the ATHW program.
References
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsupervised lcarning of visual features. In Computer Vision ECCV 2018 15th European Conference, Mumich, Germany, Seplember 8-14, 2018, Proceedings, Parl XIV, volume 11218 of Lecture Noles in Compuler Science, pp. 139-156, Springer, 2018. URL nattps://dois http://ooo.rrg//....
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topologiaal view. In The Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, pp. 3438-3445. AAAI Press, 2020a. URL https:///osss..... aaai. org/
index. index.php/AAAA wttp:p//AA./aaatcceeeeleee//////
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. In 6th International Conference on Learning Representations, TCLR 2018, Van- couver, BC, Canada, April 30- May 2018, Conference Track Proceedings. OpenReview.net, 2018. URL sttps://oop //perreveeeeeeeeee.e.oe nwt. fort/fooum?iii (o-orrnnndrrttttWWA
Ming Chen, Zhewei Wei, Zengleng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, JCML 2020, 19-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 1725 1735. PMLR, 2020b. URL http:://proceedings. mlr. press/vi19h cww.//chen2vv..mm .ttll
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery licket hypothesis for graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 1695 1706. PMLR, 2021. URL http:///proceedings mlr. ppreas/v139/chemme html
Chuan Guo, Gcoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 Proceedings of Machine Learning Research, pp. 1321-1330. PMLR, 2017. URL httpp///proceedings mlr. wwwpp/wwossseeeeeee www./////oo7a..hm...
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference Newral Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1024 1034, 2017. URL/https:// seweeeddings.neurip.. httpiapp.ccppppppe http//////eaaassaaaaaaaaaaaaaaaa haa. html
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In 8th International Conference Learning Rep- resentations, TCL. 2020, Addis Alabo, Elhiopia, April 26-30, 2020. OpenReview.nel, 2020. URL
https://openrevieer www//eeueetnnieee met//forumm1d
Zhihui Hu, Guang Kou, Haoyu Zhang, Na Li, Ke Yang, and Lin Liu. Rectifying pseudo labels: Iterative feature clustering for graph representation learning, In CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1- 5, 2021, pp. 720-729. 729. ACM, 2021. URL https: httt:::://oo..r//1....11 144144////35963334444499999
Binyuan Hui, Pengfei Zhu, and Qinghua Hu. Collaborative graph convolutional networks: Unsupervised learning moets semi-supervised learning. In The Fourth-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Secona Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intellgence, EAAT 2020, New York,
13

---

Published in Transactions on Machine Learning Research (04/2023)
NY, USA, February 7-12, 2020, pp. 4215-4222. AAAI Press, 2020. URL http:::////s..aaa..rr//////
/844
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, httpppereeeieeeeeetorrriiiiaaaaa
2017, Conference Track Proceedings. OpenReview.net, 2017. URL
SJU4ayYg1
Hongkang Li, Meng Wang, Sijia Liu, Pin-Yr Chen, and Jinjun Xiong. Generalization guarantee of training graph convolutional networks with graph topology sampling. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Ballimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 13014 13014-13051. 13051. PMLR, 2022. JRLLittpp://prrcceddnngs mll. htt.://..........eee/////////111 wtwpp//v1e/11220222022
html
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the Thirty-Second AAAT Conference on Artificial Intelligence, (AAAI-18), pp. 3538 3545. AAAI Press, 2018. URL https: hittps://wwy http://wwa.ai.../////// wwaii.rr//oaaeaaeeeaaaae //////ndxxxxx www.ddx..pp//AAA... S.AI18/paper/vieee
Sheng Liu, Jonathan Niles- Narges Razavian, and Carlos Fernandez Early-learning reg- ularization prevents memorization of noisy labels. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020,
December 6-12, 2020, virtual, 2020. URL bttpa://prooeedings.eeurrr
6888220eer68226666111666600000 Aattoo--bsttatt.... html
Yuanfu Lu, Xunqiang Jiang, Yuan Fang, and Chuan Shi. Learning to pre-train graph neural networks. Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Chirty-Thime Conference on Inmova- tive Applications of Artificial Intelligence, TAAT 2021, The Fleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pp. 4276-4284 AAAI Press, 2021. URL https://ojs. wwwporrgg...o..../eooeoeoeee.eee htt.aaaa..a....a.ppaapppaaaaaaaa
Amrit Nagarajan, Jacob R. Stevens, and Anand Raghumathan. Efficient ensembles of graph neural networks. In DAC '22: 59th ACM/IEE2 Design Automation Conference, San Francisco, California, USA, July 10 14, 2022, pp. 187-192. ACM, 2022. URL
http://///11.11133133111111 3530441
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Anand Sivasubramanian, and Mahmut T. Kandemir. GCN meets GPU: Decoupling "When to Sample' from 'How to Sample'. Tn Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020. URL
d71 676626G7766G51116666444666666 Abstract.. html
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Represenlations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRoview.nee 2020. URL h.RLl/tcppss//pperrvvevvee.////
id=HkxxqqrkKrr
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. J. Mach. Learn. Res., 15(1):1929 1958, 2014.
URL https://al acm. 0rgg6o5//0..555//2777333 5555/2627435 2670313
Ke Sun, Zhouchen Lin, and Zhanxing Zhu. Multi-stage self-supervised lcarning for graph convolu- tional networks on graphs with few labeled nodes. In The Thirby- Fourth AAAI Conference on Ar- tificiall Intelligence, AAAT 2020, pages = 5892-5899, publisher = AAAT Press, year = 2020, wrl = wrwp//de.//idd.bbeee php/ AaAAlaarticl/vveee
https:///oss.uaii.or
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
URL htttps://openreriee..coo wwwp::eetttftoeeee http://eweeeeetetettoo//////d/dd
14

---

Published in Transactions on Machine Learning Research (04/2023)
Vikas Verma, Meng Qu, Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Improved training of gnns for semi-supervisel learning. In Thirly-Figth AAAT Conference Artificial Intelligence, AAAI 2021.
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neu- ral networks via confidence calibration. In Advances in Neural Information Processing Systems 34:
Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp- 23768 23779, 2021. URL http://pooeednn....arrrs...cpppp
Han Yang, Xiao Yan, Xinyan Dai, Yongqiang Chen, and James Cheng. Self-enhanced GNN: improving graph neural networks using model outputs. In International Joinl Conference on Newral Networks, IJCNN 2021, Shenzhen, China, July 18-2 22, 2021, pp. 1-8. IEEE, 2021. URL http::://aa....o//..0./1./////// 110011115200011/05527777
Shuai Zhang, Meng Wang, Pin- Yu Chen, Sijia Liu, Songtao Lu, and Miao Liu. Joint edge-model sparse learning is provably efficient for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023. URL
Ziang Zhou, Shenzhong Zhang, and Zengfeng Huang, Dynamic self- framework for graph convolu- tional networks. CofR, abs/1910.02663 2019. URL http://awww...rrr//////9900..000
A Computational demands of conventional self-training
Conventional self-training can lead to substantial ac- curacy gains (up to 14.9% absolute gain) over super- vised training, but it comes cost (Table 5). We find that 4-stage self- training al- ways takes 4x longer than single-stage supervised training on only the labeled nodes for two reasons: (1) each stage of self-training is performed on a pro-
Absolute accuracy gain (%6
large computational
4
gressively larger training set, and (2) training set augmentation also adds some overhcads, since unlabeled nodes need to be predicted (see Appendix FJ. As the number of labeled nodes increases, the ac- curacy gain from self-training decreases, since there is sufficient supervision to learn effectively from only the labeled nodes. We also analyze the impact of the number of stages of self-training on both accuracy and wall-clock training time (Fig. I1]. Initially, as the number of self-training stages, the accuracy of the self-trained model also increases. However, when the number of stages is increased beyond certain number, the accuracy gain saturates, while the wall-clock training time continues to increase. We observe that this accuracy saturation happens because very few nodes are added to the training set in the later stages of self-training
0
3
7
Normalized wall-clock training time
Cora
Citeseer
Pubmed
Figure 11: Impact of number of stages of sclf- training. Gains in accuracy (wall-clock training time) are reported over (normalized to) training using only the labeled nodes (4 labeled nodes/class).
B Optimized Baselines
We present simple optimizations the conventional self self-training loop that improves the accuracy of previously reported baselines by up to 10%.
15

---

Published in Transactions on Machine Learning Research (04/2023)
Table 5: Benefits and overheads of conventional self-training. Results are obtained from 4-stage self- training of GCN model with all hyperparameters set to their optimal value. Gains in accuracy (absolute points)/ wall-clock training time reported over/ normalized to supervised training using only the labeled nodes, and averaged across 100 random train-test splits.
Dataset Labeled nodes class
Accuracy gain Normalized training time
3.8
4.9
1.8
Cora
4
1.7
4.6
8
0.7
4.4
16
0.3
4.1
1.2
5.7
2
3.0
5.4
Citeseer
2.0
8
2.4
4.9
16
0.9
14.9
5.5
2
12.4
5.5
Pubmed
8
1.8
5.2
16
0.8
5.0
B.1 GNN model architecture selection for different label rates
At low label rates, deeper GNNs are accurate due to better propagation of label information. At higher label rates, deeper GNNs suffer from the over-smoothing problem, where nodes belonging to different classes acquire very similar representations. As a result, shallow GNNs outperform deeper GNNs at higher label rates. Therefore, choosing the appropriate GNN architecture for the given label rate is vital, and leads to substantial accuracy improvements over previously reported baselines that always use 2-layer GNNs (Table
Table 6: Results of training GCN with different label rates. GCN-opt chooses the appropriate GCN architecture the given label rate. self-training initializes the GCN model in each stage using the trained weights from the previous stage (random stage 1), while Sclf-training-op randomly initializes the GCN model in all stages. Both versions of self-training train the GCN-opt model.
Dataset Labels/ Class
2-layer GCN GCN-opt Self-training Self-training-opt
41.1
48.9
51.3
52.7
2
60.7
64.3
65.0
66.1
Cora
4
67.2
69.1
69.6
70.8
8
74.6
74.8
75.1
75.5
16
78.8
78.8
78.9
79.1
1
34.8
38.1
38.6
39.3
2
40.7
49.9
50.7
52.9
Citeseer
4
51.1
58.1
58.8
60.1
8
64.2
64.4
65.6
66.8
16
69.1
69.1
69.4
70.0
1
40.7
42.8
49.8
57.7
2
54.5
56.1
60.3
68.4
Pubmed
4
62.1
63.3
66.2
69.7
8
69.4
69.9
70.5
71.7
16
76.7
76.7
77.1
77.4
1
25.8
26.4
28.2
29.1
2
27.4
29.6
31.8
33.0
CoraFull
4
41.1
43.2
43.7
44.7
8
53.0
53.2
54.8
55.6
16

---

Published in Transactions on Machine Learning Research (04/2023)
B.2 Random initialization of the GNN model in each stage
The majority of previous works (such as Zhou al. 2 Li al. 2018) etc.) initialize the model using the trained weights from the previous stage (when stage 1), and randomly initialize the weights only in stage 1. However, at the end of self-training (Fig. [2]. In particular, we find that the total training loss is very small when weights are initialized from the trained model in the previous stage (even after the training set is enlarged), since only nodes with highly confident predictions are added the training set. As a result, multi-stage self-training only leads lo a small improvement. accuracy over single-stage training. In contrast, randomly initializing the model in each stage enables the model to make the best use of the enlarged training set (by effectively forgetting everything learnt in the previous stage, and learning the enlarged training set from scratch, leading to better node representations). However, also note that random initialization in all stages requires larger number of training epochs in each stage for convergence, and hence, incurs larger training overheads. In our experiments, we find that the number of training epochs needed for convergence in each stage is approximately 50-100 with random initialization, and 25-50 when initializing from the previous stage.
find that randomly initializing the weights in all stages leads to more accurate models
Cora (4 labels/class)
Cora (8 labels/class)
80
Accuracy
Accuracy
60
60
40
40
Epoch
500
1000
1500
2000
Epoch
500
1000
1500
2000
Initializationn from previous stage
Initialization from previous stage
random Initialization
random Initialization
Figure 12: Accuracy with and without random initialization in all stages. Accuracy is measured on all unlabeled nodes the graph (3-layer GCN model, 4-stage self-training, 500 training epochs per stage, confidence threshold 0.8).
C Comparison of previously proposed self-training methods
Table 7: Results of training GCN with different self-training methods on Cora. The most accurate
model without using FASTRAIN-GNN framework underlined, while the most accurate model overall is displayed in bold.
Self-training method
Accuracy of self-trained model
Labels/ Class
4 Labels /Class Labels/ /Class
Co-train Li ct al. 2018
66.5
71.1
75.0
Union
el al. 2018
66.3
71.2
75.7
Intersection
et al. 2018
64.2
69.7
74.7
Self-train Li al. 2018
66.1
70.8
75.5
M3S Sun al.
61.5
67.2
75.6
DSGCN Zhou et al. 2019)
68.9
72.6
77.6
CGCN Hui et al.
(2020)
64.3
72.4
76.8
Sell-train-CaGo (Wang et al.
2021
69.5
71.9
79.4
MASTRAIN-CaGGE (Ours)
73.0
74.1
81.6
While the the optimizations proposed FASTRAIN-GNN can be usod conjunction with different pscu- dolabeling methods, we demonstrate that CASGRAIN-C&GCN produces more accurate models compared
previously proposed self-training methods (Table 7 For M3S and CGCN, report results directly from
17

---

Published in Transactions on Machine Learning Research (04/2023)
the respective papers. For all other methods, report the average accuracy across 100 different random train-test splits.
D Hyperparameter Tuning
We describe how the different hyperparameters introduced in the FASTRAIN-GNN framework can be tuned to maximize the accuracy of the self-trained models. We note that PGP does not involve any hyperparam- eters. While the exact hyperparameters used in our experiments are listed in Table g we describe insights from our hyperparameter tuning experiments the following subsections to enable faster hyperparameter optimization in future works.
Table 8: Hyperparamctors used in our experiments. The exact same hyperparameters are used in all our experiments spanning different datasets, GNN architectures and label rates. Hyperparameter
Description
Value
Fraction edges retained in the graph
spf sompling_mroe rate (SPF)
0.9
in each sampled configuration
Number of sampled configurations generated
spf iterations (SPF)
10
for testing robustness predictions
Sampling rate used in the
sampling_ Baciing__re___iieeee init (DR)
0.9
first stage of self-training
Sampling rate used from the
sampling Bacppling_rtt___e__ prae__at____ final (DR)
0.8
second stage of self- tofftrriinng onward Architecture of the deep GNN used the
deep_ grn (DS)
layer GCN/ GAT
initial stages of self-training
Architecture of the shallow GNN used in the
shallow gree (DS)
2-layer GCN/ GAT
later stages of self-training
The size of the training set at which the deep deep_gnn gnn
>= 2.5% of nodes in the graph are labeled or pseudolabeled
DS Thrresholdd (DS)
is to be replaced by the shallow gra
D.1 SPF hyperparameters
SPF uses two hyperparameters. (1) spf sampling rale denotes the fraction of edges that retained in the graph in each sampled configuration used to test the robustness of predictions, and (2) spf iterations denotes the number of sampled configurations that are used to test the robustness of predictions (only those nodes whose predictions remain constant across all sampled configurations are added to the training set).
Table 9: Impact of sas__ssmmppnggg__ee rale on accuracy of the self-trained model. Results are obtained from self-training a CaGCN model using different sas____smm__g______ rates (all other hyperparameters are set to their optimal valuc).
Number of nodes
Accuracy of nodes added to training set
Accuracy self-trained model
Dataset
_as__ssmmlingggg added to training set
0.95
2194
83.9
73.2
0.9
1801
74.1
Cora (4 labels/class)
0.85
1745
85.3
73.9
0.8
1206
85.4
73.5
0.7
917
85.6
73.3
0.95
2421
83.1
82.7
0.9
2168
83.4
Cora (16 labels/ /class)
0.85
1947
87.8
83.4
0.8
1601
88.1
82.9
0.7
1105
82.7
When _rs___smlliggrrrr rate is too large (>=0.95), we find that there is insufficient perturbation the graph structure to distinguish between robust and non-robust predictions. As result, the predictions of the vast
18

---

Published in Transactions on Machine Learning Research (04/2023)
majority of candidate nodes remain constant across sampled configurations, and SPF becomes ineffective (Table 9 On the other hand, when spʃ samplingmgreeeee rale is too small (<=0.8), the number of nodes with consistent predictions decreases drastically. The primary reason for the high effectiveness of self-training for few-shot transductive node classification is the increased number of nodes taking part in the training process through training set augmentation (either because they are added to the training sel, or because they are neighhors of nodes added the training set). As a result, the decreased coverage of nodes taking part training with a small spf sampling rate outweighs the benefits of more accurate training labels (Table 9 In our experiments, we find that spf_ sam__samligg__ai nodes seen during training and the accuracy of training labels (across all datasets and label rates).
0.9 provides the best trade-off between coverage of
Since sampling randomly prunes edges from the graph, some sampled configurations will not have any impact on a given node. As a result, jpf_iterations should be sufficiently high to ensure that perturbations affect the computation graphs of all candidate nodes (Table T0 In our experiments, we find that spf_ _ff__etetiions 10 is sufficient to distinguish between robust and non-robust predictions (across all datasets and label rates). We note that the computational complexity of SPF is directly proportional to spf ileralions, and statistically significant accuracy gains are not obtained with increasing spf iterations beyond 10.
Table 10: Impact of _it__tetts on accuracy of the self-trained model. Results are obtained from self-training CaGCN model using different _iteratit (all other hyperparameters are set to their optimal value).
Number of nodes
Accuracy of nodes
Accuracy of self-trained model
Dataset
spf iiterations
added to training set.
added to training set
2
2068
84.2
73.4
2008
84.6
73.8
Cora (4 labels/class)
10
1801
85.1
74.1
20
1797
85.3
74.2
50
1796
85.3
74.2
2378
85.7
82.9
5
2182
86.9
83.1
Cora (16 labels/class)
10
2168
87.3
83.4
20
2167
87.3
83.4
50
2164
87.4
83.4
D.2 DR hyperparameters
DR uses two hyperparameters. (1) sampling_ Bati__rt______ init denotes the sampling rate in the first stage of self training (when only nodes with golden labels are used for training), and (2) faallinn_rtt__inna denotes the sampling rate used when pseudolabeled nodes are added to the training set. We use sampling rale inil in the first stage of self- self-training, and sampling B_tig____________ rate_final in all subsequent stages. Sampling in GNNs is analogous to dropout (Srivastava et al. 2014) in other classes of neural networks. Dropout (a commonly used regularizer for training DNNs) prunes random subset of neurons in the model in each training iteration. Similarly, sampling prunes random subset of edges in the graph in each training iteration. As a result, sampling provides a regularization effect that prevents overfitting to training labels, thereby improving generalization performance (Li et al. 2022). The benefits of sampling can also be seen in Fig. 3 A dropout rate of p indicates that the probability of a neuron being pruned a given training iteration (1-p). Similarly, a sampling rate of also indicates that the probability of an edge in the graph being pruned in a given training iteration is (1-s).
In the first stage of self-training, the labels are 100% accurate. In addition, only small number of training nodes are available. Therefore, we use high value for sampling sasi___at________ init to maximize the number of nodes laking part in the training process, thereby enabling better propagation of information from labeled nodes. We find that sampling_ Bilig__rte__iiiieee rate_initt = 0.9 works well across datasets and label rates in our experiments (Fig. 3) In fact, we observe that even the presence of only golden labels, the regularization effect from sampling important (when sampling_rate rate cnnee_ init >= the limited training data).
0.95, there is an accuracy drop due to overfitting
19

---

Published in Transactions on Machine Learning Research (04/2023)
While sampling is effective regularizer for preventing overfitting to noisy training labels, we find that under-sampling the graph adversely affects convergence during training, thereby preventing learning from correct labels also. We empirically find that sampling rater_ae________ sint__iill== = 0.8 works well across datasets and label rates in our experiments, since it provides the best balance between preventing overfitting and convergence. This can be seen Fig. g where a sampling rale of 0.8 typically leads to the most accurate trained models when the accuracy of training labels is between 80% and 100%.
D.3 DS hyperparameters
DS uses three hyperparameters. (1) deep_ geep-gmn denotes the architecture of the deep GNN used in the initial stages self training. (2) shallow gren denotes the architecture of the shallow GNN used in the later stages of self training. (3) DS Threshold determines the stage of self self-training at which the deep gnn is replaced by the shallow gmn.
The choice of architecture for both deep grm and shallow gon depends on the GNN model that is used for self-training, since different GNN variants require different numbers of layers for best accuracy. On the widely studied GCN and GAT models used in our experiments, 2-layer models have been reported to be the most accurate for supervised training on a large number of labeled nodes. We observe that 3-layer models are most accurate for few-shot learning. Therefore, we choose 3-layer GCN/ GAT models as deep gnn, and 2-layer GCN/ GAT models as shallow ggn.
When training with few labeled nodes, deep GNNs outperform shallow GNNs due to larger message passing coverage (enabling more unlabeled nodes to be "seen" during training). On the other hand, the increased message passing coverage leads to oversmoothing in deep GNNs when training on a large number of labeled nodes, resulting in shallow GNNs outperforming deep GNNs. The DS_Thresholl is used to indicate the point at which oversmoothing outweighs the benefits of increased message passing coverage as the training set is augmented during self-training. We empirically observe that when approximately 2.5% of all nodes the graph are labeled, there is sufficient coverage for shallow grass to outperform deep .gans (Fig. 5), since >75% of all nodes in the graph take part in training using shallow GNNs (either because they are added to the training set, or they are neighbors of nodes in the training set). This holds across the different datasets, label rates and GNN architectures used in our experiments. We also find that this holds irrespective of the choice of initial training nodes. For instance, on Cora with 4 labeled nodes/class, the 3-layer GCN model achieves higher accuracy than the 2-layer GCN model at the end of the first stage of self- telf-training in all 100 out of 100 trials with random train-test splits. Similarly, on Cora with 16 labeled nodes /class, the 2-layer GCN model achieves higher accuracy than the 3-layer GCN model at the end of the first stage of self-training in 98 out of 100 trials.
E
Overheads of the FASTRAIN-GNN optimizations
We find that the different FASTRAIN-GNT optimizations add minimal overheads (Fig. 13p. SPF involves generating spʃ ilerations different sampled configurations (which takes only a few milliseconds), and predicting the high-confidence candidate nodes with different sampled configurations. We find that the fraction of runtime spent in SPF (8-10% of the total
% of wall-clock self-training
100%
80%
60%
time
40%
20%
runtime) is similar to the fraction of runtime spent in comput- ing the prediction confidence of all unlabeled nodes. This is because the additional computational complexity of predicting candidate nodes multiple times is amortized by two factors: (1) the set of candidate nodes is typically a small subset of all unla- beled nodes in the graph, and (2) each prediction is faster, since edges in the graph are pruned through sampling. DS and DR together account for <0.01% of the total runtime, since they only involve modifying hyperparameters. PGP involves identi- fying and pruning inter-class edges between labeled nodes. At
0%
Citeseer
Pubmed
Training a Computing confidence
SPF
PGP
Figure 13: Fraction of wall-clock self- training time spent in each step. Re- sults are obtained from self-training 3- layer GCN model with confidence threshold of 0.8.
20

---

Published in Transactions on Machine Learning Research (04/2023)
the end of each stage of self-training PGP analyzes the labeled neighbors of nodes that were added to the training set in that stage to identify inter-class edges. Since 1- hop neighbors of labeled nodes can be quickly identified from the adjacency matrix, PGP only adds small overheads, typically accounting for <2% of the total runtime.
F Results on heterophilous graphs
In this section, present results heterophilous graphs, where connected nodes are likely to have dissimilar labels. We follow the procedure described in GC- N11 CCen et al. 2020b) for processing the datasots. Similar to the experimen- tal setup for homophilous graphs, we ran- domly select (labels/class) nodes of each class training nodes, and report results
Table 11: Dataset characteristics. Homophily ratio is the ratio
of edges connecting nodes of the same class to the total number of edges.
Dataset
Classes
Nodes
Edges
Feature size
Homophily Ratio
Chameleon Texas
2277
36101
2325
0.23
183
309
1703
0.11
Wisconsin
0.21
Cornell
183
1703
0.3
on the rest of the nodes in the graph. We repeat this process 100 times for each value of (labels/class)) and all results reported this section are averaged across 100 different training splits. The datasets used for testing are summarized in Table []] Since some classes contain too few nodes to get a meaningful train-test split the Texas, Wisconsin and Cornell datasets, we do not present results with 16 labels/class, We use the same hyperparameters for these experiments as those used for homophilous graphs (listed in Table 8
Table 12: Results of training GCN with different label rates on heterophilous graphs. Results are averaged across 100 runs with random train-test splits (subscripts indicate standard deviation).
Dataset Labels/ Class
GCN
Self-train-GCN FASTRAIN-GCN
1
22.74.9
26.24.9
28.84.5
2
28.43.8
31.94.
35.614
Chameleon
4
33.8
35.13.6
38.43.9
8
35.03.2
36.911
39.33.7
16
40.52.9
41.42.2
42.8s.1
1
28.33.6
32.44.1
35.33.9
2
38.24.8
41.44.4
44.74.7
Texas
4
45.52.5
47.23.1
49.42.8
8
50.61.7
51.51.4
52.71.5
1
31.73.4
33.33.2
36.43.8
2
36.04.4
37.93.8
40.24.2
Wisconsin
4
44.83.3
46.42.4
48.93.1
8
49.21.3
50.61.8
51.71.9
1
33.54.4
36.43.9
38.74.4
2
40.14.6
43.04.0
45.93.5
Cornell
4
47.83.1
49.14.2
52.23.6
8
53.92.5
54.82.1
56.12.1
We present results on the Chameleon, Texas, Wisconsin and Cornell datasets with different label rates in Table 12 While SPF, DR and DS are used without any modifications, PGP is modified to prune intra- class edges instead of inter-class edges for heterophilous graphs. If we have no prior knowledge about whether the graph is homophilous or heterophilous, we can decipher this from the training set (containing nodes with actual labels and pseudolabels) at the end of the first stage of self-training. The homophily ratio (ratio of edges connecting nodes of the same class to the total number of edges) of edges connecting nodes in the training set indicates whether the graph is homophilious or heterophilious. For instance, Cora (a homophioous graph) has an average homophily ratio of 0.83 among nodes the training after the first stage of self-training, while Chameleon (a heterophilous graph) has homophily ratio of 0.2. We
21

---

Published in Transactions on Machine Learning Research (04/2023)
find that FASTRAIN-GNN consistently outperforms conventional self-training under different label rates heterophilous graphs also. In addition to producing models that are more accurate, FASTRAIN-GNN also accelerates the self-training process (Table 13).
Table 13: Accuracy and efficiency gains from the different FASTRAIN-GNN optimizations on Chameleon. Speedup is computed over self-training of the more accurate among 2/3-layer models, and averaged across different train/test splits and label rates. +Intra-class edges are pruned in PGP instead of inter-class edges.
Self-Training- GGN
with SPF and DR
with SPF,
with SPF, DR, DS and PGP+
Labels/ CClas
(2-layer/ 3-layer GCN)
(2-layer/ 3-layer GCN)
DR and DS
23.43.6
26.219
24.03.2 26.83.8
27.73.9
28.8
2
28.72.9
31.94.5
30.0g.3 / 33.24.1
34.54.6
35.64.4
4
33.93.1
35.13.6
35.0g.
36.22.9
37.11.1
38 43..3..9
8
36.94.1
36.13.9
38.0
37.53.6
38.63.5
39.3g.7
16
41 41.42 2 / 38. 3..9
41.92.. 39.91.1
41.92.4
42.8
Average Speedup
1X
1.2X
1.7X
1.9X
22


Reviews:
[{"review_id": "fEYETIlX1G", "reviewer": "Reviewer_1Nc3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n* The paper is generally written clearly and easy to follow.\n\n* Some of the proposed modules seem new and effective, e.g. the sampling based pseudolabel filtering. \n\n* I like the experimental results comparing different label rates. \n\nWeaknesses:\n\n* Although the paper proposed four optimization procedures for self-training, none of them is attractive enough. In other words, the paper lacks a striking point, which makes it more like an engineering pipeline. \n\n* No clear explanation of the motivation and no theoretic justification of the proposed method. SPF is seemingly interesting, but it lacks a theoretic justification; similarly, DR has the same issue. For example, the authors claim, “we find that sampling is an effective regularizer”, but why? It does not have a detailed discussion. Without detailed explanation of the motivation and theoretic advantages, the proposed modules will only be regarded as heuristic tricks and novelty will look trivial.\n\n* One big issue of the experiments are the datasets. One of the focuses of this paper is to accelerate the self-training, but all the datasets are relatively small in the graph learning community; and all of them actually have enough labels. To demonstrate the proposed method is practically useful, readers may be more convinced if they see a practical scenario with bigger data size and less labels. Moreover, all the datasets in this paper are citation datasets but we do not know whether the method also work for other types of graph datasets (especially heterophily graphs). That makes the generalizability of the method also questionable.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper focused on self-training GNNs for few-shot transductive node classification. The proposed FASTRAIN-GNN introduced four major optimizations in each stage of self-training:\n(1)\tSampling based Pseudolabel Filtering to generate more reliable pseudo labels.\n(2,3) Dynamic Sizing and Dynamic Regularization to overcome the layer effect and reduce the impact of incorrect training labels.\n(4) Progressive Graph Pruning to remove inter-class edges and improve information-to-noise ratio during message passing.\nThe approach is claimed to accelerate the self-training as well as to improve the accuracy.\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. adding more theoretic explanation why the proposed module is useful\n\n2. experiments on different types of datasets (especially heterophily graphs) and bigger datasets\n", "broader_impact_concerns": "The paper may bring some ideas to improve self-training of GNNs, but it does not have enough theoretic or empirical justification. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "L1GFEzNZPd", "reviewer": "Reviewer_XEHk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The intuitions for the algorithm are well-presented.\n\n2. The experiments results justify the efficiency and accuracy of the proposed self-training approach for GNNs.\n\nWeakness:\n\n1. The training time of GNNs increases dramatically as the training samples increase. Could the author report the improved test accuracy (over training GNN using labeled data only) against the enlarged training time (over training GNN using labeled data only) by varying the number of unlabeled data used in the experiments? Therefore, we could have a better idea for the efficiency of using self-training in GNN.\n\n2. ResGNN can overcome the oversmoothing issue caused by the layers. Could the author discuss the possibility of using ResGNN in your framework?\n\n3. Although the intuitions are well-presented, the implementation of the algorithm is not clear to the readers. Some sampling questions, (1) what sampling rate should we choose in practice? Can we keep the same sampling rate if we change the dataset? (2) when decreasing the layer number and sampling rate as the training samples increase, how should we decrease them based on the number of training samples? Therefore, I hope the authors can explore more about the proposed algorithms, for example, (2.1) what is the benefits of selecting a large (or small) sampling rate in SPF? when should we choose a relatively large (or small) sampling rate in SPF? Besides sampling, is there any ways in existing works to test the robustness of GNNs, and how do you compare your methods with theirs? (2.2) how the threshold in DS is derived? how should we select the threshold given different datasets? would it be better to set multiple sets of the threshold and corresponding GNN model in the algorithms?  (2.3) how do we quickly detect the inter-class edges? What is the relationship between the computational times in detecting inter-class edges and computing self-training using the sampled nodes? \n\n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a framework for fast and accurate self-training of GNNs using unlabeled data. Specifically, first, it proposes the sampling-based Pseudo-label Filtering approach to actively select pseudo-labeled data with a high confidence score. Second, it proposes the Dynamic Sizing and Dynamic Regularization to reduce the oversmoothing problem raised by multi-layer GNN and residual error in pseudo-labels.  Third, it proposes the Progressive Graph Pruning approach to address the oversmoothing problem raised by the inter-class edges. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I hope the author provides either theoretical computation or numerical experiments to justify my concerns in the weakness. ", "broader_impact_concerns": "I did not see any broader impact concerns in this paper. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CjOUov2wrv", "reviewer": "Reviewer_PMSV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**:\n1. The intuition in the paper makes sense to me, and it is also verified by experiments. \n2. The empirical experiments, especially the comparison with existing methods, show the advantages of the proposed technique in terms of performance and training speed. \n3. The writing is clear. It is easy to follow. \n\n**Weakness**:\n1. The writing is not concise enough.\n2. The experiments need improvement in terms of presentation.\n3. Some necessary motivation and introduction might be missing in the introduction section.\n4. Some discussion about limitations and future directions is missing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed FASTRAIN-GNN, which is an improved framework for the self-training of GNNs in terms of learning performance and speed, mainly for transductive node classification tasks. It consists of four major parts:  Sampling-based Pseudolabel Filtering,  Dynamic Regularization, Dynamic Sizing, and Progressive Graph Pruning. The motivation for these parts is from the intuition and experiments on empirical graph datasets about the quality of pseudo-labels,  graph sampling/pruning, layer effects (over-smoothing), and homophily of the graph. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Major**:\n1. In Section 3, it is better to use some concise words to describe the method instead of such long paragraphs. Some mathematical equations or the format of algorithms are helpful. Actually, I can feel that in this part, the authors focus on introducing more about intuition and the understanding of the method. Therefore, a complete algorithm for DR and DS is expected to know the complete architecture and idea of the technique (just like Algorithms 1 and 2). \n2. Some experimental results are quite close between curves, e.g., Figure 3, 5, 8; Table 2, 3. The setup of random seeds and the error bar might be necessary for these figures and tables.\n3. I recommend adding some introduction about the lottery ticket hypothesis because the methods of SPF and PGP are related. I also recommend adding a discussion of related works in Section 2. Some references include:\n(a) https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf, \nhttp://proceedings.mlr.press/v139/chen21p/chen21p.pdf,  \nhttps://arxiv.org/pdf/1801.10247.pdf%EF%BC%89 (The authors have cited them, but introducing it in Section 2 is also appropriate.)        \n(b) https://proceedings.neurips.cc/paper/2020/file/d714d2c5a796d5814c565d78dd16188d-Paper.pdf,  \nhttps://proceedings.mlr.press/v162/li22u/li22u.pdf,   https://openreview.net/forum?id=4UldFtZ_CVF. (These are theoretical understanding of efficient graph learning with sampling, from training and generalization.)\n4. From the testing datasets and the intuition of the PGP method, I feel the proposed method is mainly for homophilous graphs. It is unsure how the proposed tool works on heterphilous graphs. Will you consider adding virtual edges between nodes in any case? Discussions about limitations and future works are needed.\n\n**Minor**:\n1. On page 7, in the second to last line in the paragraph above Table 2, it should be \"Table 1\" instead of \"Table 4\", right?\n", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studied different optimization methods for improving graph neural networks in self-training settings. In the first round, all reviewers made very constructive comments about the submission. The authors did a good job revising and improving the paper, and most of the major concerns have been addressed.

However, there are several post-rebuttal suggestions on adding additional discussions to further clarify the claims (especially from Reviewer 1Nc3). I deemed the changes as necessary and therefore recommend "accept with minor revision". I ask the authors to prepare a response and post it on openreview to explain how they incorporate the reviewers' comments and suggestions in the final version.


Decision: Accept (poster)