Combining Label Propagation and Simple Models out-performs Graph Neural Networks
Authors: Qian Huang
Horace He
Abhay Singh
Ser-Nam Lim
Austin Benson
Venue: ICLR 2021 Poster (2021)
Keywords: graphs
graph neural networks
label propagation
simple
residual

Abstract: Graph Neural Networks (GNNs) are a predominant technique for learning over graphs. However, there is relatively little understanding of why GNNs are successful in practice and whether they are necessary for good performance. Here, we show that for many standard transductive node classification benchmarks, we can exceed or match the performance of state-of-the-art GNNs by combining shallow models that ignore the graph structure with two simple post-processing steps that exploit correlation in the label structure: (i) an “error correlation” that spreads residual errors in training data to correct errors in test data and (ii) a “prediction correlation” that smooths the predictions on the test data. We call this overall procedure Correct and Smooth (C&S), and the post-processing steps are implemented via simple modifications to standard label propagation techniques that have long been used in graph-based semi-supervised learning. Our approach exceeds or nearly matches the performance of state-of-the-art GNNs on a wide variety of benchmarks, with just a small fraction of the parameters and orders of magnitude faster runtime. For instance, we exceed the best-known GNN performance on the OGB-Products dataset with 137 times fewer parameters and greater than 100 times less training time. The performance of our methods highlights how directly incorporating label information into the learning algorithm (as is common in traditional methods) yields easy and substantial performance gains. We can also incorporate our techniques into big GNN models, providing modest gains in some cases.

Published as a conference paper at ICLR 2021
COMBINING LABEL PROPAGATION AND SIMPLE MOD- ELS OUT-PERFORMS GRAPH NEURAL NETWORKS
Qian Huangl, Horace He Abhay Singh', Ser-Nam Lim Austin R. Benson
Corelll University*, Facebook", Facebook A
ABSTRACT
Graph Neural Networks (GNNs) are a predominant technique for learning over graphs. However, there is relatively little understanding of why GNNs are suc- cessful in practice and whether they necessary for good performance. Here, we show that for many standard transductive node classification benchmarks, we exceed or match the performance of state-of-the-an GNNs by combining shal- low models that ignore the graph structure with two simple post-processing steps that exploit correlation in the label structure: (i) an "error correlation" that spreads residual eтrors in training data to correct errors in test data and (ii) a "prediction correlation" that smooths the predictions on the test data. We call this overall pro- cedure Correct and Smooth (C&S), and the post post-processing steps are implemented via simple modifications to standard label propagation techniques that have long been used in graph-based based semi-supervised learning. Our approach exceeds or nearly matches the performance of state-of-the-art GNNs on wide variety of benchmarks, with just a small fraction of the parameters and orders of magnitude faster runtime. For instance, we exceed the best-known GNN performance on the OGB- CrB-Products dataset with 137 times fewer parameters and greater than 100 times less training time. The performance of our methods highlights how directly incor- porating label information into the learning algorithm (as common in traditional methods) yields easy and substantial performance gains. We can also incorporate our techniques into big GNN models, providing modest gains in some cases.
INTRODUCTION
Following the success of neural networks in computer vision and natural language processing, there are now a wide range of graph neural networks (GNNs) for making predictions involving relational data (Battaglia et al., 2018; Wu et al., 2020). These models have had much success and sit atop leaderboards such as the Open Graph Benchmark (Hu et al., 2020). Often, the methodological devel- opments for GNNs revolve around creating strictly more expressive architectures than basic variants such as the Graph Convolutional Network (GCN) (Kipf & Welling, 2017) or GraphS (Hamilton et al., 2017a) 7a); examples include Graph Attention Networks (Veličković et al., 2018), Graph Isomor- phism Networks (Xu et al., 2018), and various deep models (Li et al., 2019; Rong et al., 2019; Chen adapted from new architectures in models
et al., 2020). Many ideas for new GNN architectures for language (c.g., attention) or vision (c.g., deep CNNs) with the hopes that success will translate to graphs. However, these models become more complex, understanding their performance gains is a major challenge, and scaling them to large datasets is difficult.
how far derstanding where there are easy opportunities for performance improvements in graph learning, particularly transductive node classification. We propose simple pipeline with three main parts (Figure 1): (i) a base prediction made with node features that ignores the graph structure (c.g.. shallow multi-layer perceptron or just linear model); (ii) a correction step, which propagates un- certainties from the training data across the graph to correct the base prediction; and (iii) smooth- ing of the predictions over the graph. Steps (ii) and (iii) are post-processing and implemented with classical methods for graph- semi-supervised learning, namely, label propagation techniques
Here,
get by combining much simpler models, with an emphasis
"Equal contribution
Work done while Comell University

---

Published as a conference paper at ICLR 2021
Dataset
Correct and Smooth
MLP
Scale
Input Features
Base Model Prediction
Smooth wi Labels
Smoothed Résidual Residual Corretation
Train Labels
Prediction Correlation
Figure 1: Illustration of our GNN-free model, Correct and Smooth (C&S), with toy example. Nodes in the left and right clusters have different labels, marked by color (orange or blue). We use multilayer perceptron (MLP) for base predictions, ignoring the graph structure. We assume this gives the same prediction on all nodes in this example (which could happen if, e.g., all nodes had the same features). After, base predictions are corrected by propagating errors from the training data. Finally, corrected predictions are smoothed with label propagation.
(Zhu, 2005).² 1 With few modifications and new deployment of these classic ideas, achieve state- of-the-art performance on several node classification tasks, outperforming big GNN models. In our framework, the graph structure is not used to learn parameters (which is done in step (i)) but instead as a post-processing mechanism. This simplicity leads to models with orders of magnitude fewer parameters that take orders of magnitude less time to train and can easily scale to large graphs. We can also combine our ideas with state-of-the-art GNNs, although the performance gains are modest.
A major source of performance improvements is directly using labels for predictions. This idea is not new early liffusiio-based semi-supervised learning algorithms on graphs such as the spectral graph transducer (Joachims, 2003), Gaussian random field models (Zhu al., 2003), and and label spreading (Zhou et al., 2004) all use this idea. However, the motivation for these methods was supi-super learning on point cloud data, so the "node features" were used to construct the graph itself. Since then, these techniques have been used for learning on relational data consisting of graph and some labels but no node features (Koutra al., 2011; Gleich Mahoney. 2015: Peel, 2017: Chin et al., 2019); however, they have largely been ignored in the context of GNNs. (That being said, we still find that even simple label propagation, which ignores features, does surprisingly well number of benchmarks.) This provides motivation for combining two orthogonal sources of prediction power- - one coming from the node features (ignoring graph structure) and one coming from using the known labels directly in predictions.
Recent research connects GNNs to label propagation (Wang & Leskovee, 2020; Jia & Benson, 2020; 2021) well Markov Random fields (Qu et al., 2019; Gao al., 2019), and some techniques use ad hoc incorporation of label information approaches are usually still expensive to train, while use label propagation in two understand- able and low-cost ways. We start with a cheap "base prediction" from a model that uses only node features and ignores the graph structure. After, we use label propagation for error correction and then to smooth final predictions. These post-processing steps are based on the fact that errors and labels on connected nodes tend be positively correlated. Assuming similarity between connected nodes is at the center of much network analysis and corresponds to homophily ing (McPherson et al., 2001; Newman, 2003; Easley & Kleinberg, 2010). In the semi-supervised learning literature, the analog is the smoothness or cluster assumption (Chapelle et al., 2003; Zhu, 2005). The good performance of label propagation that we see across a wide variety of datasets suggests that these correlations hold common benchmarks.
the features (Shi et al., 2020). However, these
assortative mix-
OOn of the main methods that we use (Zhou et al., 2004) is often called label spreading. The term "label propagation" is used in a variety of contexts (Zhu, 2005; Wang & Zhang. 2007; Raghavan et al., 2007: Gleich & Mahoney, 2015). The salient point for this paper is that assume positive correlations neighboring nodes and that the algorithms work by "propagating" information from one node another.
2

---

Published as a conference paper at ICLR 2021
Overall, our methodology demonstrates that combining several simple ideas yields excellent per- formance in transductive node classification at a fraction of the cost, in terms of both model size (i.e., number of parameters) and training time. For example, the OGB- OGB-Products benchmark, out-perform the current best-known GNN with more than two orders of magnitude fewer parame- ters and more than two orders of magnitude less training time. However, our goal is not say that current graph learning methods are poor or inappropriate. Instead, we aim to highlight casier ways in which to improve prediction performance in graph learning and better understand the source of performance gains. Our main finding is that more direct incorporation of labels into the learning algorithms is key. We hope that our approach spurs new ideas that can help in other graph learning tasks, such as inductive node classification, link prediction, and graph prediction.
1.1 ADDITIONAL RELATED WORK
The Approximate Personalized Propagation of Neural Predictions (APPNP) framework is most rel- evant to our work, as they also smooth base predictions (Kliepera et al., 2018). However, they focus on integrating this smoothing into the training process so that their model can be trained end to end. Not only is this significantly more computationally expensive, it also prevents APPNP from incorporating label information at inference. Compared APPNP, our framework produces more accurate predictions, is faster to train, and more easily scales to large datasets. That being said, APPNP can also be used without end-to-end training, which can make it faster but less accurate. Our framework also complements the Simplified Graph Convolution (Wu et al., 2019) and other algorithms designed to increase scalability (Bojehevski et al., 2020; Zeng et al., 2019; Frasca al., 2020). The primary focus of our approach. however, is using labels directly, and scalability is byproduct. There also prior work connecting GCNs and label propagation. Wang & Leskovec (2020) use label propagation label propagation as a post-processing step and avoid GNNs. Jia & Benson (2020; 2021) use label propagation with GNNs for regression tasks, and our error correction step adapts some of their ideas for the case of classification. Finally, there are several recent approaches that incorporate nonlinear- ity into label propagation methods to compete with GNNs and achieve scalability (Eliav & Cohen, 2018: Ibrahim & Gleich, 2019; Tudisco et al., 2021), but these methods focus on settings of low label rates and do not use feature-based learning.
pre- pre-processing step weight edges for GNNs, whereas we use
2 CORRECT AND SMOOTH (C&S) MODEL
We start with some notation. We assume that we have an undirected graph G = (V,E), where there are n = [V] nodes with features on each node represented by a matrix X E Rnxp. Let A be the adjacency matrix of the graph, D be the diagonal degree matrix, and S be the normalized adjacency matrix D-1/2 AD-122 For the prediction problem, the node set V is split into disjoint set of unlabeled nodes U and labeled nodes I., which are subsets of the indices (1....,n)) n). We will further split the labeled nodes into a training set I,, and validation set I,,. We represent the labels by a ane-hot-encoding known to be in class j. and 0 otherwise, where the ith row of Y is all zero if E U), Our problem is transductive node classification: assign each node j E U a label in (1...., c), given G. X, and Y.
matrix Y E gaxe, where e is the number of classes (i.c., Yú, = i E L is
Our approach starts with simple base predictor on node features that does not rely on any learning over the graph. After, we perform two types of label propagation (LP): one that corrects the base predictions by modeling correlated error and one that smooths the final prediction. We call the combination of these two methods Correct and Smooth (C&S; Figure 1). The LPs are only post- processing steps, and our pipeline is not trained end-to-end. Furthermore, the graph only used in the post-processing steps (and in a pre-processing step to augment the features X), but not for the base predictions. This makes training fast and scalable compared Moreover, we take advantage of both LP (which performs fairly well on its own without features) and the node features. We find that combining these complementary signals yields excellent predictions.
standard GNN models.
2.1 SIMPLE BASE PREDICTOR
To start, we use a simple base predictor that does not rely on the graph structure. More specifically, train model f to minimize Eiel, {(f(x:), vi). where x; is the vth row of X, yi is the ith row
3

---

Published as a conference paper at ICLR 2021
of Y, and & is a loss function, For this paper, f is either linear model or shallow multi-layer perceptron (MLP) followed by a softmax, and is the cross-entropy loss. The validation set Lu is used to tune hyperparameters such as learning rates and the hidden layer dimensions for the MLP. From f. we get a base prediction Z E IR TR,xe, where each row of Z is a probability distribution resulting from the softmax. Omitting the graph structure for these base predictions avoids most of the scalability issues with GNNs, In principle, though, we can use any base predictor for Z, including those based on GNNs, and we explore this in Section 3. However, for our pipeline to be simple and scalable, we just use linear classifiers or MLPs with subsequent post- post-processing, which we describe next.
2.2 CORRECTING BASE PREDICTIONS WITH ERROR CORRELATION
Next, we improve the accuracy of the base prediction Z by incorporating labels to correlate errors. The key idea is that we expect errors in the base prediction to be positively correlated along edges in the graph. In other words, an error at node i increases the chance of a similar error at neighbors of Thus, we should "spread" such uncertainty over the graph. Our approach here is inspired in part by residual propagation (Jia & Benson, 2020), where a similar concept is used for node regression tasks, as well as generalized least squares and correlated error models more broadly (Shalizi, 2013). To this end, we first define an error matrix E E Raxe, where error is the residual on the training data and zero elsewhere:
Zin Et.,: =
Ev. =. 0.
The residuals in of E corresponding training nodes are only when the base predictor makes a perfect prediction. We smooth the error using the label spreading technique of Zhou et al. (2004), optimizing the objective
É arg min trace(W" (I- S)W) + w||lW - ElE
WERnxe
The first term encourages smoothness of the error estimation over the graph, and is equal to Σi=1 E(snee (Wa/VD. - Ws,//D,,)² The second term keeps the solution close the initial guess E of the error. As derived in Zhou et (2004), the solution can be obtained via the iteration E(-1) (1- E + aSE(), where = 1/(1 u)) and (X)) E, which converges rapidly to E. This iteration is a propagation (or diffusion or spreading) of the error, and we add the smoothed errors to the base prediction to get corrected predictions Z(r) = + É. We emphasize that this is a post-processing technique and there is no coupled training with the base predictions.
This type of propagation is motivated by particular correlated Gaussian error assumption for re- gression problems (Jia & Benson, 2020; 2021). For the classification problems we consider, we find that the smoothed errors E might not be at the right scale. We know that
||
1| S (1 F| + o ||| (X ||2 (1 a) + o:l| 1/
(3)
When ()) = F, we then have that || ||(00) || S F| Thus, the propagation cannot completely correct the errors on all nodes in the graph, as does not have enough "total mass." and find that adjusting the scale of the residual can help substantially in practice. To do this, we propose two variations of scaling the residual.
Autoscale. Intuitively, we want to scale the size of errors in É be approximately the size of the errors in E. We only know the true errors at labeled nodes, so we approximate the scale with the average error over the training nodes. Formally, let eς E R and éÿ correspond to the jth rows of E L. Ejet, [e5]11.. Then we define the corrected predictions unlabeled node i E U to be _! Z, + 7/Iealla . .T.
and É and define
Scaled Fixed Diffusion (FDiff-scale). Alternatively, we can use diffusion like the one from Zhu et al. (2003), which keeps the known errors at training nodes fixed. More specifically, we 1TDD'AE()]a and keep fixed EL!. EL.: until convergence É, starting with iterate E [t++1)
E(O) = F. Intuitively, this fixes error values where we know the error (on the labeled nodes L.), while other nodes keep averaging over the values of their neighbors until convergence. With this type of propagation, the maximum and minimum values of entries in E(t) do not go beyond those in Er. We still find it effective to select a scaling hyperparameter to produce Z(r Z + sb.
4

---

Published as a conference paper at ICLR 2021
2.3 SMOOTHING FINAL PREDICTIONS WITH PREDICTION CORRELATION
At this point, we have score vector ((r), obtained from correcting the base predictor Z with a model for the correlated еπтоr É. To make a final prediction, we further smooth the corrected predictions. The motivation is that adjacent nodes in the graph are likely have similar labels, which is expected given network homophily or assortative properties of a network. Thus, we can encourage smoothness over the distribution over labels by another label propagation. First, we start with our best guess H E Ruxe of the labels:
H YEass HI,UU, Z(r) LOUU""
(4)
Here, the true labels are used at the training nodes and the corrected predictions are used for the validation and unlabeled nodes, the latter of which no longer correspond to probability distributions. We can (and should) also use the true labels at the validation labels, which we discuss later in the experiments, but the setup in Equation (4) aligns more closely with standard GNN evaluation. We then iterate ((++)) = (1 H)H + oSH(1) (1) with (0) = until convergence to give the final prediction Y. The classification for node E U is arg m Yij-
As with error correlation, the smoothing here is a post-procces post-procsssing step. decoupled from the other steps. This type of prediction smoothing is similar in spirit to APPNP (Klicpera et al., 2018), which we compare against later. However, APPNP is typically trained end-to-end, propagates final-layer representations instead of softmaxes, does not use labels, and is motivated differently.
2.4 SUMMARY AND ADDITIONAL CONSIDERATIONS
To summarize, start with cheap base prediction Z, using only node features but not the graph structure. After, estimate errors É by propagating errors on the training data. Then, we add these errors back to the base predictions, forming corrected predictions. Finally, we treat the corrected predictions as score vectors on unlabeled nodes, and combine them with the known labels via another LP step for smoothed final predictions. We call this pipeline Correct and Smooth (C&S).
Before showing that this pipeline achieves state-of-the-art performance on transductive node classi- fication, we briefly describe another simple way of improving performance: feature augmentation. The hallmark of deep learning is that we can learn features instead of engineering them. However, GNNs still rely on informative input features to make predictions. There are numerous ways to get useful features from just the graph topology to augment the raw node features (Henderson al., 2011; 1; 2012; Hamilton et al., 2017b). In our pipeline, we augment features with a regularized spectral embedding (Chaudhuri et al., 2012: Zhang & Rohe, 2018) coming from the leading eigenvectors of the matrix D- D/1/3(A + )D,11)D;//! 1/2 where 1 is a vector of all ones, T is a regularization pa- rameter set to the average degree, and D, is diagonal with ith diagonal entry equal to D₃; + т. The underlying matrix is dense, but we can apply matrix-vector products in time linear in the number of edges and use iterative eigensolvers to compute the embeddings quickly.
3 EXPERIMENTS ON TRANSDUCTIVE NODE CLASSIFICATION
To demonstrate the effectiveness of our methods, we use nine datasets (Table 1). The Arxiv and Products datasets are from the Open Graph Benchmark (OGB) (Hu et al., 2020); the Cora, Cite- seer, and Pubmed are three classic citation network benchmarks (Getoor et al., 2001; Getoor, 2005; web graph (Mernyei Cangea, 2020). In these datasets,
Namata et al., 2012); and wikiCS classes are categories of papers, products, pages, and features are derived from text. We also use Facebook social network of Rice University, where classes are dorm residences and features attributes such as gender, major, and class year (Traud et al., 2012), well as geographic dataset of US counties where classes are 2016 election outcomes and features are demographic (Jia an email dataset of a European research institute, where classes
& Benson, 2020). Finally, are department membership and there are no features (Leskovec et al., 2007; Yin et al., 2017).
Data splits. The training/validationnte splits for Arxiv and Products are given by the benchmark, and the splits for wikiCS come from Mernyei & Cangea (2020). For the Rice, US counties, and email data, we use 40% 40%/10%550 0%/50% random splits. For the smaller citation networks, use 60%/20%/20%
5

---

Published as a conference paper at ICLR 2021
Table 1: Summary statistics of datasets and model performance. For the accuracy of our best C&S model compared to the state-of-the-an GNN method (see text), we report the change in the number of parameters and the accuracy. We also list the training time with time to compute the spectral em- bedding in parentheses (even if not used in the best model). Our methods require fewer parameters, are typically more accurate, and are fast to train. Also see Tables and
Datasets
Classes
Nodes
Edges
Parameter A
Accuracy A
Time (s)
Arxiv
40
169,343
1,166,243
84.90%
+0.26
12 (+90)
Products
47
2,449,029
61,859,140
-9.44%%
+1.74
171 (+2959)
Cora
2,708
5,429
-98.37%
+1.09
< (+7)
Citeseer
6
3,327
4,732
89.68%
-0.69
<1 (+7)
Pubmed
19,717
44,338
96.00%
-0.30
<1 <1 (+14)
Email
42
1,005
25,571
97.89%
+4.33
43 (+17)
Rice31
10
4,087
184,828
999.02%
+1.39
39 (+12)
US County
3,234
12,717
-74.56%
+1.77
39 (+12)
wikiCS
10
11,701
216,123
-84.8%%
+2.03
7 (+11)
random splits, as in Wang & Leskovec (2020). Standard deviations prediction accuracy over splits is 1% in most experiments and such variance does not change qualitative comparisons.
C&S setup and baselines. We use Linear and MLP models as simple base predictors based on node features. When spectral embedding is included as node feature, refer to these models as Linear-SE and MLP-ŞE. We also evaluate Label Propagation itself (L.P: specifically. the Zhou et al. (2004) version), which only uses labels. In all cases, the number of LP iterations is fixed to 50.
For GNN models comparable to our framework in terms of simplicity or style, we use GCN, SGC, and APPNP. For GCNs, add residual connections from the input to every layer and from every layer to the output, as well as dropout. Thus, GCN is not the original model Kipf & Welling (2017) and instead serves as fairly strong representative of out-of-the-bbo GNN capabilities. The number of layers and hidden layer dimensions for the GCNs are the same as the MLPs used by our base predictors. The GCN only uses raw node features, and additional results in Appendix C show that including spectral embeddings minimally changes performance. APPNP uses a linear model for base predictions, also with the raw node features.
Finally, we include several "state-of-the-art" (SOTA) baselines. For Arxiv and Products, this is UniMP (Shi et al., 2020) (top of OGB leaderboard, as of October 1, 2020). For Cora, Citeseer and Pubmed, we use the top scores from Chen et al. (2020). For Email and US County, we use GCNII (Chen et al., 2020). For Rice31, 1, we use GCN with spectral embedding as additional features, which is the best GNN-based model that found. For wikiCS, we APPNP as reported by Mernyei & Cangea (2020). Hyperparameters are tuned using the validation set.
All of the above models select hyperparameters using the validation See Appendix A for addi- tional model architecture details.
3.1 FIRST RESULTS ON NODE CLASSIFICATION
In our first set of results, we only use the training labels our C&S framework, these are what GNNs typically use to train models. For the results discussed here, this is generous to our baselines. The ability include validation labels an advantage of our approach (and LP in general), and this improves performance of our framework even further (Table 1). We discuss this in the next section.
Table 2 reports the results, and we highlight few important findings. First, within our model, there are substantial gains from the LP post-processing steps (c.g., the MLP-SE base prediction accuracy increases from 63% to 84% on Products). Second, even Linear with C&S outperforms GCNs in many cases, and simple LP is often competitive with GCNs. This is striking given that the main motivation for GCNs was to address the fact that connected nodes may not have similar labels (Kipf' & Welling, 2017). Our results suggest that directly incorporating correlation in the graph with simple use of the features often a better idea. Results in Appendix show that both label propagation post- processcnns steps important for performance. Third, model variants SOTA on Products, Cora, Email, Rice31, and US County (often substantially so). On the other datasets, there is not much difference between the best C&S model and the SOTA.
out-perform

---

Published as a conference paper at ICLR 2021
Table Performance our C&S framework, using only the training labels as ground truth in final prediction smoothing (Equation (4)). Further improvements can be made by including ground truth validation labels (Table 3). The Email dataset has no raw node features, so some methods are not evaluated. APPNP ran out of memory (OOM) on the products dataset.
Method
Arxiv
Products
Cora
Citeseer
Pubmed
LP
68.5
74.76
86.50
70.64
83.74
GCN
71.74
75.64
85.77
73.68
88.13
SGC
69.39
68.83
86.81
72.04
84.04
APPNP
66.38
OOM
87.87
76.53
89.40
SOTA
73.79
82.56
88.49
77.99
90.30
Linear
52.32
47.73
73.85
70.27
87.10
Linear-SE
70.08
50.05
74.75
70.51
87.19
MLP-SE
71.51
63.41
74.06
68.10
86.85
Linear C&S (Autoscale)
71.11
80.24
88.62
76.31
89.99
Linear-SE C&S (Autoscale)
72.07
80.25
88.73
76.75
89.93
MLP-SE + C&S (Autoscale)
72.62
78.60
87.39
76.31
89.33
Linear + C&S (Fdiff-scale)
70.60
82.54
89.05
76.22
89.74
Linear-SE C&S (Fdiff-scale)
71.57
83.01
88.66
77.06
89.51
MIP-SE + C&S (Fdiff-scale)
72.43
84.18
87.39
76.42
89.23
Method
Email
Rice31
US County
wikiCS
LP
70.69
82.19
87.90
76.72
GCN
15.45
84.13
78.61
SGC
16.59
83.92
72.86
APPNP
11.34
84.14
69.83
SOTA
71.96
86.50
88.08
79.84
Linear
9.84
75.74
72.45
Linear-SE
66.24
70.26
84.07
74.29
MLP-SE
69.13
17.16
87.70
73.07
Linear + C&S (Autoscale)
75.99
85.25
79.57
Linear-SE C&S (Autoscale)
72.50
86.42
86.15
79.53
MLP-SE + C&S (Autoscale)
74.55
85.50
89.64
78.10
Linear + C&S (Fdiff-scalee)
73.66
87.38
79.54
Linear-SE C&S (Fdiff-scale)
72.53
87.55
88.11
79.25
MLP-SE + C&S (Fdiff-scale)
75.74
85.74
89.85
78.24
To get a sense of how much using ground truth labels di- rectly helps, we also evaluate a version of C&S where we smooth base predictions from a linear model or MLP, using the Zhou al. (2004) version of label propagation. We call these Linear-SE- find that they often outperform GCNs (right). Again, these results suggest that smoothed outputs important, aligning with recent research (Wu al., 2019; Bojchevski et al., 2020), and that the original motivations for GCNs might be misleading. However, there still gaps in performance between these models and those in Table that directly use labels. Next, we see how to improve performance C&S even further by using more labels.
Method
Arxiv
Products
Linear-SE-smooth
71.42
78.73
MLP-SE-smooth
72.48
80.34
and ML.-SSE-smood and
GCN
71.74
75.64
3.2 FURTHER IMPROVEMENTS BY USING MORE LABELS
We improve the C&S performance by using both training and validation labels, instead just the training labels in Equation (4). Importantly, we do not use validation labels to update the base prediction model - they are just used to select hyperparameters. Using validation labels boosts performance even further: Table 3 shows accuracies and Table 1 shows gains ability to incorporate validation labels a benefit of our approach. On the other hand, GNNs do not have this advantage, they often rely early stopping prevent overfitting, may not always
SOTA. The

---

Published as a conference paper at ICLR 2021
Table 3: Performance of C&S, using both training and validation labels as ground truth in the final prediction smoothing (cf. Equation (4), Table 2).
Method
Arxiv
Products
Cora
Citeseer
Pubmed
Linear + C&S (Autoscale)
72.71
80.55
89.54
76.83
90.01
Linear-SE C&S (Autoscale)
73.78
80.56
89.77
77.11
89.98
MLP-SE + C&S (Autoscale)
74.02
79.29
88.55
76.36
89.50
Linear C&S (Fdiff-scale)
72.42
82.89
89,47
77.08
89.74
Linear-SE C&S (Fdiff-scale)
72.93
83.27
89.53
77.29
89.57
MLP-SE C&S (Fdiff-scale)
73.46
84.55
88.18
76.41
89.38
SOTA
73.65
82.56
88.49
77.99
90.30
Methods
Email
Rice31
US County
wikiCS
Linear + C&S (Autoscale)
76.59
85.22
81.87
Linear-SE C&S (Autoscale)
73.33
87.25
86.38
81.57
MLP-SE + C&S (Autoscale)
73.45
86.13
89.71
80.75
Linear + C&S (Fdiff-scale)
75.31
88.16
81.18
Linear-SE C&S (Fdiff-scale)
72.57
87.89
88.06
81.06
MLP-SE + C&S (Fdiff-scale)
76.22
86.26
90.05
80.83
SOTA
71.96
86.50
88.08
79.84
ogbn-products
Table 4: C&S with GNN base predictions.
82
Dataset
Model
Performance
Accurccy
GAT
73.56
ogbn-arxiv
GAT + C&S
73.86
78-
SOTA
73.79
OGB Leaderboard
76
C&S (Ours)
US County
GCNII (SOTA)
88.08
10
10
10"
GCNII + C&S
89.59
Figure 2: Accuracy and model size on Products.
benefit from more data (e.g., under distributional shift), and do directly labels. Thus, comparisons in Table 2 are more generous than needed. With validation labels, our best model out-performs SOTA in seven of nine datasets, often by substantial margins (Table 1).
The evaluation procedure for GNN benchmarks differ from those for LP. For GNNs, sizable valida- tion set is often used (and needed) for substantial hyperparameter tuning, as well as early stopping. With LP, one can use the entire set of labeled nodes L with cross-validation to select the single hyperparameter a. Given the setup of transductive node classification, there no reason not to use validation labels at inference if they are helpful (e.g., via LP in our case). The results in Tables and show the true performance of our model and the proper point of comparison.
Overall, our results highlight two important findings. First, big and expensivetto-train GNN models are not actually necessary to achieve top performance for transductive node classification on many datasets. Second, combining classical label propagation ideas with simple base predictors outper- forms graph neural networks on these tasks.
3.3 TRAINING TIME AND IMPROVING EXISTING GNNS
Our C&S framework often has significantly fewer parameters compared to GNNs or other SOTA solutions. As example, we plot parameters vs. performance for the Products dataset in Fig- ure 2. While having fewer parameters useful, the real gain is in faster training time. Our models typically orders of magnitude faster train than models with comparable accuracy because we do not use the graph structure for our base prediction models. As one example, although our MLP-SE C&S model for the Arxiv dataset has similar number of parameters compared to the
8

---

Published as a conference paper at ICLR 2021
(b) Linear-SE SE C&S predictions
Oreus
(a) Ground Truth
(c) GCN-SE predictions
Figure 3: (a) US County visualizations, where the embedding is given by Graph and colors correspond to class labels. (b) Panels corresponding parts of (a) that show at which stage Linear- SE + C&S made correct prediction. (c) The same panels showing GCN predictions.
"GCN+-ineur-labels" method on the OGB leaderboard (Wang, 2020), our model runs 7 times faster epoch and converges much faster. In addition, compared to the SOTA for the Products dataset, our framework with a linear base predictor has higher accurucy, trains over 100 times faster, and has 137 times fewer parameters.
We also evaluated our methods on an even larger dataset, the papers 1 100M OGB benchmark (Hu et al., 2020). Here, we obtain 65.33% using C&S with the Linear model the base predictor, which out-performs the state-of-the-art (63. 29%, as of October 1, 2020).
Our pipeline can also be used to improve the performance of GNNs in general. We used C&S with base predictions given by GCNII or GAT. This improves our results on some datasets, such as ogbn- arxiv (Table 4). However, the performance improvements sometimes only minor, suggesting that big models might be capturing the same signal as our simple C&S framework.
3.4 PERFORMANCE VISUALIZATION
To aid in understanding the performance of our C&S framework, we visualize the predictions the US County dataset (Figure 3). As expected, the residual error correlation tends to correct nodes where neighboring counties provide relevant information. For example, see that many errors in the base predictions are corrected by the residual correlation (Figure 3b, left and right panels). In these cases, which correspond parts of Texas and Hawaii, the demographic features of the counties are outliers compared to the rest of the country, leading both the linear model and GCN astray. The error correlation from neighboring counties is able fix the predictions. We also see that the final prediction correlation can fix eтrors when nearby nodes are correctly classified, as shown in the center panel of Figure 3b. We observe similar behavior on the Rice31 dataset (Appendix D).
4 DISCUSSION
GNN models becoming expressive, parameterized, and expensive train. Our results suggest that we should explore other techniques for improving performance, such as label propagation and feature augmentation. In particular, label propagation and its variants longstanding, powerful ideas. More directly incorporating them into graph learning models has major benefits, and we have shown that these can lead to both better predictions and faster training.
Acknowledgments. This research was supported by Facebook AI, NSF Award 183S-4,3027, ARO Award 1 1NF19-1-0000 ARO MURI, and JP Morgan Chase & Co. We also thank Comell University Artificial Intelligence for their support, as well as Mare Brockschmidt, Matthias Fey, Stephan Günnemann, Weihua Hu, and Junteng Jia for insightful discussions.

---

Published as a conference paper at ICLR 2021
REFERENCES
P. Battaglia, Jessica B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, Mateusz Malinowski, Andrea Tacchetti, D. Raposo, Adam Santoro, R. Faulkner, Çaglar Gülçehre, Song, A. Ballard, J. Gilmer, G. Dahl, Ashish Vaswani, Kelsey R. Allen, C. Nash, V. Langston, Chris Dyer, N. Heess, Daan Wierstra, Pushmeet Kohli, M. Botvinick, Oriol Vinyals, Y. Li, and Razvan Pascanu. Rela- tional inductive biases, deep learning, and graph networks.
2018.
Alcksandar Bojchevski, Johannes Kliepera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate PageRank. In International Conference on Knowledge Discovery and Data Mining, 2020.
Olivier Chapelle, Jason Weston, and Bernhard Schölkopf. Cluster kernels for semi-supervised learn- ing. In Advances in Neural Information Processing Systems, 2003.
Kamalika Chaudhuri, Fan Chung, and Alexander Tsiatas. Spectral clustering of graphs with general degrees the extended planted partition model. In The Conference on Learning Theory, 2012.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.
Alex Chin, Yatong Chen, Kristen M. Altenburger, and Johan Ugander. Decoupled smoothing on graphs. In The Web Conference, 2019.
David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Buchnik Eliav and Edith Cohen. Bootstrapped graph diffusions: Exposing the power of nonlinearity. International Conference on Measurement and Modeling of Computer Systems, 2018.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Benjamin Chamberlain, Michael Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks. In ICMI. Workshop on Gruph Representation Learning and Beyond, 2020.
Hongchang Gao, Jian Pei, and Heng Huang, Conditional random field enhanced graph convolutional neural networks. In The 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
Lise Getoor. Link-based classification. In Advanced Methods for Knowledge Discovery from Com- plex Data, 2005.
Lise Getoor, Nir Friedman, Daphne Koller, and Benjamin Taskar. Learning probabilistic models of relational structure. In International Conference on Machine Learning. 2001.
David F Gleich and Michael W Mahoney. Using local spectral methods to robustify graph-based learning algorithms. In International Conference on Knowledge Discovery and Data Mining, 2015.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017a
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017b.
Keith Henderson, Brian Gallagher, Lei Li, Leman Akoglu, Tina Eliassi-Rad Hanghang Tong, and Christos Faloutsos. It's who you know; graph mining using recursive structural features. In International Conference Knowledge Discovery and Data Mining, 2011.
Keith Henderson, Brian Gallagher, Tina Eliassi-Rar Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. RolX: structural role extraction mining in large graphs. In International Conference Knowledge Discovery and Data Mining, 2012.
10

---

Published as a conference paper at ICLR 2021
Weihua Hu, M. Fey. M. Zitnik, Yuxiao Dong, H. Ren, Bowen Liu, Michele Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Infor- mation Processing Systems, 2020.
Rania Ibrahim and David Gleich. Nonlinear diffusion for community detection and semi-supervised learning. In The Web Conference, 2019.
Junteng Jia and Austin R. Benson. Residual correlation in graph neural network regression. In /CML Workshop on Graph Representation Learning and Beyond workshop, 2020.
Junteng Jia and Austin R Benson. unifying generative model for graph learning algorithms: Label propagation, graph convolutions, and combinations. arXiv:2101.07300, 2021.
Thorsten Joachims. Transductive learning via spectral graph partitioning. In International Confer- ence on Machine Learning. 2003.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Danai Koutra, You Ke, U Kang, Duen Horng Polo Chau, Hsing-Kuo Kenneth Pao, and Christos Faloutsos. Unifying guiltbby-association approaches: Theorems and fast algorithms. Joint European Conference Machine Learning and Knowledge Discovery in Databases, 2011.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data, 2007.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In IEEE International Conference Computer Vision, 2019.
Leland McInnes, John Healy, Nathaniel Saul, and Lukas Großherger. UMAP: Uniform Manifold Approximation and Projection. Journal of Open Source Software, 2018.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual Review of Sociology, 2001.
P'eter Mernyei and Cătälina Cangea. Wiki-CS: A wikipedia-based benchmark for graph neural networks. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
Galilco Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In International Workshop on Mining and Learning with Graphs, 2012.
Mark EJ Newman. Mixing patterns in networks. Physical Review E, 2003.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 2019.
Leto Peel. Graph-based semi-supervised learning for relational networks. SIAM International
Conference on Data Mining, SIAM, 2017.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph markov neural networks. In International Conference on Machine Learning. 2019.
Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
11

---

Published as a conference paper at ICLR 2021
Cosma Shalizi. Advanced data analysis from elementary point of view. Cambridge University Press, 2013.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, and Yu Sun. Masked label prediction: Unified mas- sage passing model for semi-supervised classification. arXiv:2009.03509, 2020.
Amanda Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks.
Physica A: Statistical Mechanics and its Applications, 2012.
Francesco Tudisco, Austin R Benson, and Konstantin Prokopchik. Nonlinear higher-order label spreading. The Web Conference, 2021. To appear.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. IEEE Transac- lions on Knowledge and Data Engineering, 2007.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propa- gation. arXiv:2002.06755, 2020.
Yangkun Wang. Gen+linear+labels. 2020.
https: htttts///oop.tttffooddeeebbbbb eddde///eer.d/bbbeeeeeeerr... leader_
nodeprop/ 2020.
Felix Wu, Amauri Souza, Tianyi Zhang. Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In International Conference on Machine Learning, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Zhang, and Philip S. Yu. compre- hensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018
Hao Yin, Austin R Benson, Jure Leskovec, and David Gleich. Local higher-order graph clustering. In International Conference on Knowledge Discovery and Data Mining. 2017.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. International Conference on Learn- ing Representations, 2019.
Yilin Zhang and Karl Rohe. Understanding regularized spectral clustering via graph conductance. In Advances in Neural Information Processing Systems, 2018.
Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learn- ing with local and global consistency. Advances Neural Information Processing Systems, 2004.
Xiaojin Zhu, Zoubin Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In International Conference on Machine Learning, 2003.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Technical report, University of CicconsinMMadioon Department of Computer Sciences, 2005.
12

---

Published as a conference paper at ICLR 2021
A MODEL DETAILS
Here we provide some more details on the models that we use. In all cases we use the Adam opti- mizer and tune the learning rate. We follow the models and hyperparameters provided in OGB (Hu et al., 2020) and wikiCS (Meryyei & Cangea, 2020) and manually tune some hyperparameters on the validation data for the potential of better performance.
For our MLPs, every linear layer is followed by batch normalization, ReLU activation, and 0.5 dropout. The other parameters depend on the dataset as follows.
Products and Arxiv: layers and 256 hidden channels with learning rate equal to 0.01.
Cora, Citseer, and Pubmed (Getoor et al., 2001; Getoor, 2005; Namata et al., 2012) and Email (Leskovec al., 2007; Yin et al., 2017): layers and 64 hidden channels with learning rate = 0.01.
wikiCS: 3 layers and 256 hidden channels with learning rate equal to 0.005.
US County (Jia & Benson, 2020) and Rice31 (Traud et al., 2012): layers and 256 hidden channels with learning rate equal 0.005.
SOTA models for most datasets are taken from existing benchmarks. We determined SOTA for Email, US County, and Rice31 by evaluating several models discussed in the paper. The best per- forming baselines were follows. For Email, GCNII with 5 layers, 256 hidden channels, learning rate equal to 0.01. For US County, GCNII with layers, 256 hidden channels, learning rate equal to 0.03. For Rice31, reused our GCN architecture and trained it over spectral embedding, which substantially outperformed the other GNN variants.
All models were implemented with PyTorch (Paszke al., 2019) and PyTorch Geometric (Fey & Lenssen, 2019).
B PERFORMANCE RESULTS WITH ONLY THE CORRECTION STEP
Table 5 shows results with and without smoothing in the final predictions, i.e., just the "C step" vs. C&S. Including final prediction smoothing provides substantial performance boost in many
C ANALYSIS OF PERFORMANCE GAINS FROM SPECTRAL EMBEDDINGS
Table 6 shows the effect of including spectral embeddings node features the accuracy of the MLP-based and GCN models. In the case of the Arxiv dataset, including the spectral embedding improves the MLP base prediction performance substantially and the C&S performance modestly, but hardly changes the performance of the GCN. For Pubmed, including the spectral embeddings barely changes the performance of any model.
D ADDITIONAL VISUALIZATION
Full visualizations of C&S and GCN-SE performance for the US County dataset are in Figures to 6. Similar visualizations for the Rice3l are in Figures to 9, which are generated by project- ing the 128-dimensional spectral embedding used in the main text down two dimensions with UMAP (McInnes et al., 2018).
13

---

Published as a conference paper at ICLR 2021
Table 5: Performance of C&S framework with and without the final prediction smoothing. In cases where final prediction smoothing used, only ground truth training are used.
Method
Arxiv
Products
Cora
Citeseer
Pubmed
Linear + (Autoscale)
66.89
74.63
79.56
72.56
88.56
Linear C&S (Autoscale)
71.11
80.24
88.62
76.31
89.99
Linear-SE: C (Autoscale)
71.52
70.93
79.08
70.77
88.84
Linear-SPe SE C&S (Autoscale)
72.07
80.25
88.73
76.75
89.93
MLP-SE + C (Autoscale)
71.97
69.85
74.11
71.78
87.35
MLP-SE C&S (Autoscale)
72.62
78.60
87.39
76.31
89.33
Linear + (Fdiff-scale)
65.62
80.97
76.48
70.48
87.52
Linear C&S (Fdiff-scale)
70.60
82.54
89.05
76.22
89.74
Linear- Seear-SE-aa (Fdiff-scale)
70.26
73.89
79.32
70.53
84.47
Linear-S SEr--SE-aa C&S (Fdiff-scale)
71.57
83.01
88.66
77.06
89.51
MLP-SE C (Fdiff-scale)
71.55
72.72
74.36
71.45
86.97
MLP-SE + C&S (Fdiff-scale)
72.43
84.18
87.39
76.42
89.23
Method
Email
Rice31
US County
wikiCS
Linear + C (Autoscalc)
43.97
82.60
77.49
Linear C&S (Autoscale)
75.99
85.25
79.57
Linear-SE (Autoscale)
73.39
86.19
84.08
74.06
Linear-S E C&S (Autoscale)
72.50
86.42
86.15
79.53
MLP-SE (Autoscale)
71.64
84.61
88.83
78.72
MLP-SE + C&S (Autoscale)
74.55
85.50
89.64
78.10
Linear C (Fdiff-scale)
72.44
87.16
75.98
Linear + C&S (Fdiff-scale)
73.66
87.38
79.54
Linear-SE C (Fdiff-scale)
71.31
85.22
88.27
73.86
LinearSSE: C&S (Fdiff-scale)
72.53
87.55
88.11
79.25
MLP-SE (Fdiff-scale)
72.59
85.42
89.62
78.40
MLP-SE + C&S (Fdiff-scale)
75.74
85.74
89.85
78.24
14

---

Published as a conference paper at ICLR 2021
Table 6: Comparison of models with and without spectral embeddings, using only ground truth training labels for final prediction smoothing within C&S.
Method
Arxiv
Products
Cora
Citeseer
Pubmed
GCN
71.74
75.64
85.77
73.68
88.13
GCN-SE
71.76
76.12
85.83
73.60
88.32
MLP
59.67
59.23
74.21
69.34
86.73
MLP-SE
71.51
63.41
74.06
68.10
86.85
MLP C&S (Autoscale)
71.76
79.42
87.56
76.42
89,29
MLP-SE + C&S (Autoscale)
72.62
78.60
87.39
76.31
89.33
MLP + C&S (FDiff-scale)
71.57
83.8
87.61
76.44
89.28
MLP-SE C&S (Fdiff-scale)
72.43
84.18
87.39
76.42
89.23
Method
Email
Rice31
US County
wikiCS
GCN
15,45
84.13
78.61
GCN-SE
74.51
38.54
89.72
78.15
MLP
15.73
87.77
71.42
MLP-SE
69.13
17.16
87.70
73.07
MLP C&S (Autoscale)
85,05
89.67
78.92
MLP-SE C&S (Autoscale)
74.55
85.50
89.64
78.10
MLP + C&S (FDiff-scale)
86,40
89.64
78.10
MLP-SE C&S (Fdiff-scale)
75.74
85.74
89.85
78.24
15

---

Published as a conference paper at ICLR 2021
Republican Democratic
Figure 4: US County ground truth class labels.
16

---

Published as a conference paper at ICLR 2021
Correction step
Smoothing stop
Incorrect
Figure 5: Linear-SE + C&S prediction performance on US County.
17

---

Published as a conference paper at ICLR 2021
Train Correct Incorrect
Figure 6: GCN-SE prediction performance on US County.
18

---

Published as a conference paper at ICLR 2021
Figure 7: Rice31 ground truth class labels.
19

---

Published as a conference paper at ICLR 2021
Train Bave Correction step
Smouthing stop Inco roct
Figure 8: Linear-SE C&S prediction performance on Rice31.
20

---

Published as a conference paper at ICLR 2021
Train Corrod noot Inco read
Figure 9: GCN-SE prediction performance on Rice31.
21


Reviews:
[{"review_id": "xHtSUDftqRJ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "(Added on 11/29/2020)\n\n**Post Rebuttal Comment**\n\nI thank the authors for sincerely replying to my review comments. The authors' answers were reasonable to me.\n\n-------------------------------------\n\n**Review Summary**\n\nThis paper has conducted an extensive comparison with many existing GNNs with a wide variety of datasets. It supported an underlying hypothesis that using label information directly is helpful for better performance. Several studies have questioned the architecture of the current standard GNNs. Considering that, it is important to rethink whether the modules taken for granted are redundant. This research has given empirical evidence that an end-to-end node aggregation scheme might not be a critical component for good performance. It deepens the understanding of GNN models. \n\n**Summary and Contributions**\n\nIt proposed Correct and Smooth (C&S) for solving graph-learning problems. The model consists of a shallow model that ignores underlying graph structures followed by two label correction based on label propagation algorithms. This paper tested C&S with several benchmark datasets and compared it with popular GNNs. Also, this paper applied the proposed correction methods to GNNs and showed that it provided performance gain.\n\n**Claim**\n\nIf I understand correctly, the main claims of this paper are as follows. I will evaluate this paper whether theories and experiments support these claims.\n\n- Claim 1: C&S performs comparably in classification tasks with existing models.\n- Claim 2: C&S is computationally cheap compared to existing models.\n- Claim 3: C&S improves the predictive performance of existing models.\n\n**Soundness of the claims**\n\nCan theory support the claim?\n- This paper did not provide a theoretical justification for the proposed method.\n\nCan empirical evaluation support the claim?\n- Claim 1, 2 are supported by experiments in Table 2 (Section 3.2) and Table 1. Remarkably, this paper used nine datasets, which have a relatively wider variety compared to standard GNN papers. I agree that C&S + Autoscale or FDiff-scale can achieve comparable performance with a small number of parameters.\n- Claim 3 is supported by experiments in Table 5 (Section 3.3). As pointed out by authors, the performance gain obtained by incorporating C&S to GAT and GCNII is modest. The difference in performance between GCNII and GCNII+C&S is within the standard deviation. So, I do not think the experimental results well support claim 3.\n\n**Significance and novelty**\n\nRelation to previous work\n \n- This paper mentioned the following models as related works.\n  - label propagation: APPNP (Klicpera et al, 2018) (Section 1.1, Paragraph 1), GCN-LPA (Wang & Lescovec, 2020)), C-GCN (Jia & Benson, 2020) (Section 1, Paragraph 4)\n  - Markov random field: Qu et al. (2019), Gao et al. (2019) (Section 1, Paragraph 4)\n  - Shi et al. (2020) (Section 1, Paragraph 4)\n- As pointed out by this paper, several existing methods have incorporated the label propagation algorithms to GNNs, such as APPNP, GCN-LPA, and C-GCN. The authors discussed the difference between these methods in Section 1, Paragraph 4, and claimed that the proposed method is advantageous in computational cost. The author tested in Fig.2. I want to confirm which methods are used as the OGB Leaderboard in Figure 2.\n- Regarding the difference from C-GCN, this paper discussed that while Jia & Benson (2020) focused on regression tasks, this study is interested in classification tasks.\n- Iscen et al. (2019) employed the idea of combining label propagation and MLP in semi-supervised learning. However, the problem setting of Iscen et al. (2019) is different from this paper in that the former one does not have underlying graph structures a priori while the latter one has.\n[Iscen et al., 2019] A. Iscen, G. Tolias, Y. Avrithis, O. Chum. \"Label Propagation for Deep Semi-supervised Learning,\" CVPR 2019\n\nRelevance to community\n- Several studies have questioned the architecture of the current standard GNNs. For example, SGC (Wu et al., 2018) questioned the role of non-linearity, gfNN (NT and Maehara, 2019) questioned the interleaving of node aggregations and non-linear transformations. If I understand correctly, this study has a similar spirit in common.\n\n**Correctness and Clarity**\n\nIs the theorem correct?\n- No theorems are provided.\n\nIs the experimental evaluation correct?\n- In the paragraph starting with \"Under a Gaussian assumption ...\" in Section 2.2, the authors hypothesized why plain C&S is insufficient for classification tasks from the difference between regression and classification tasks. Based on this discussion, they introduced Autoscale and FDiff-scale. Table 2 showed that the C&S methods do not perform comparably with existing methods without the autoscale or FDiff-scale methods in classification tasks. If the above hypothesis is correct, I expect that the plain C&S performs well in regression tasks. However, we cannot confirm the hypothesis because no experiments are performed on regression tasks.\n\nIs the experiment reproducible?\n- Although the experiment code is not provided, the experiments' details are provided, such as hyperparameters and train/validation/test splits.\n\n**Clarity**\n\nCan I understand the main point of the paper easily?\n- Yes\n\nIs the organization of the paper well?\n- Yes\n\nAre figures and tables appropriately made?\n- Yes\n\n**Additional feedback**\n\nSection 3 Paragraph (Base predictors and other models) Line 7: For For Cora ... → For Cora ...\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "mOSU2s6Eu9r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------------\nA method to perform transductive node classification in graphs is presented. This is the case in which a model is trained on a large graph in which only some nodes are labeled, and the inference task is to label the remaining nodes correctly.\nThe method uses a simple per-node prediction model $f$ (ignoring the graph structure) and then two post-processing steps: (1) propagating information about errors made by $f$ on labeled nodes to its neighbours, and (2) \"smoothing\" predictions, e.g., encouraging that adjacent nodes have the same label.\nIn experimental results on a variety of datasets, the method has comparable to or better performance than substantially more complex Graph Neural Networks, while requiring 1-2 orders of magnitude fewer parameters and less compute time.\n\nStrong/Weak Points\n-------------\n* (+) The method is simple and largely well-described, and it is interesting and notable that it is extremely competitive in this setting.\n* (+) The experiments range over a substantial set of datasets, models and ablations, providing ample evidence that this is not just a fluke.\n* (-) The zoo of model variants is not well-described and confusingly named (\"Base Model\" <-> \"Base Prediction\", \"Linear\" vs. \"Plain Linear\", etc.). This part of the paper could be substantially improved by better naming and editing.\n* (-) The title (mainly, + some of the abstract, and a bit of the text) is overly focused on the relation to GNNs instead of creating clarity about the method. This is somewhat misplaced as it is not applicable to a majority of GNN use cases (such as graph-level uses for property predictions of molecules, proteins, etc.; or the modelling of mathematical proofs or programs; or anything that isn't transductive node classification). The paper is interesting in itself, but puts focus on its weaknesses by this aggressive sales pitch.\n\nRecommendation\n-------------\nI think this paper should be accepted for publication, as it serves as a much-needed reality check for some of the more frothy publication trends in GNN research at the moment.\nHowever, I would strongly recommend to reduce the sales focus. For example, \"Label Propagation is all you need for Transductive Node Classification\" would be a what-counts-as-witty-in-the-ML-community title that is more informative and less combative than the current one.\n\nQuestions\n-------------\n* Sect 3: I believe that \"plain linear\" refers to an initial per-node prediction layer that operates only on the raw node features, distinguished from the \"linear\" variant which uses the raw node features and additionally the spectral features as described in Sect. 2.4. Is this correct? It would be helpful to update the text to clarify this.\n* Sect 3: What does \"Plain GCN\" refer to? How is it different from just writing \"GCN\"?\n* Sect 3: Does \"Base Prediction\" refer to the case of not using any label propagation?\n\nDetail Feedback\n-------------\n* Sect 2: For reproducibility purposes, it would be helpful to specify values for $\\mu$, the number of iteration steps.\n* Table 2: This would be much easier to read with either all results next to each other (resizebox may help here) or with a spatial separation between the two sets of results.", "extra_scores": {}, "extra_text": {}}, {"review_id": "X_2UeDXR2TG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis paper presents C&S method that predicts node labels in the transductive semi-supervised node classification setting. C&S uses the three-stage-pipeline approach. First, label probabilities are predicted with simple and scalable classifiers such as MLP. Then, the predicted errors are diffused over graphs. Finally, the labels are further smoothened to give the final node label prediction. The authors demonstrate that their simple C&S approach beats many existing GNN approaches.\n\nAlthough the paper makes interesting claims, I also have many concerns about whether the experiments support the central claims. The experiments need to be well-organized and improved to support the claims.\n\n## Pros:\n1. Provides evidence that diffusing label information is useful and can even beat conventional GNNs.\n2. The results are promising, especially on the OGB products dataset.\n3. Let the community rethink the value of the classical approach of the label diffusion for semi-supervised node classification.\n\n## Concerns\n1. For many datasets, C&S with the plain linear base predictor does not give good performances, This implies that spectral embeddings capturing graph structure are important for C&S. However, in the abstract and introduction, I got the impression that the base predictor ignoring graph structure is enough for C&S to achieve good performance. \n2. If spectral embeddings benefit C&S, why not use the embeddings also for the other GNN models? The central claim of the paper is that C&S algorithm (label diffusion) could be better than GNNs (feature diffusion), but there is a confounding factor that GNNs are not utilizing spectral embeddings as model input. \n3. In Section 2.4, the authors mentioned 15 seconds for 1M edges, but in Table 1, on the OGB Arxiv dataset (with about 1M edges), time is only 9.89s. Why is that? \n4. Computing spectral embeddings is quite expensive on large graphs, while the authors claim it is fast. To demonstrate this, in Table 1, please make sure to include the time for computing spectral embeddings (and all other computations in C&S), and compare the time with existing GNN models. \n5. Table 1 is confusing because C&S is using validation labels, and the absolute numbers are not reported. Reporting absolute numbers, time, and SOTA method names is important because SOTA will quickly change over time.\n6. The model used for the papers100M dataset is not mentioned. What model did you use to achieve 65.33% accuracy? Why don't the authors treat papers100M dataset in the same way as the other datasets (by including the result in Tables 1 and 2)?\n7. Ablation studies of doing only C or S is missing. Table 3 is kind of doing ablation studies of only retaining the S part, but I’d like to see more pure ablation studies. How much does each component contribute to the final accuracy?\n8. Sensitivity of scaling hyper-parameters $s$ in FDiff-scale and the number of iterations in graph diffusion is not mentioned. Especially, $s$ seems to be quite important.\n9. In Section 3.2, the authors claim that GNNs do not take advantage of validation labels; however, this is not immediately obvious to me. Please justify this through experiments.\n10. In Table 3, what if you use spectral embeddings for Plain GCN?\n11. In Section 1.1, “but these methods focus on settings of low label rates” is unclear, and seems tangential to the actual methods. \n12. “Methods” column in Table 2 is unclear to me.\n13. In Table 2, why did the authors mark 88.73 in bold (89.05 seems to be the best)? If Auto-scale is consistently worse than FDiff-scale, does it make sense to drop it entirely?\n14. Figure 3 is hard to understand.\n15. Standard deviations are not included. There should be randomness coming from MLP training.\n\n====\n\nPost-rebuttal: I am happy to accept this paper after seeing my concerns are mostly addressed.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5_7yKQeheHo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows modified label propagation can perform better than GCN. The idea is as follows: it first uses MLP on node features to get the initial labels, and then use two steps--correction and smoothness to postprocessing the labels. And this postprocessing is based on the traditional label propagation algorithm. It shows that this simple method matches GCN performances on various datasets. \n\n1) To my understanding, this method can be viewed as proposing a 'better' initialization for label propagation.  In label propagation, we usually start from random for these unlabeled nodes, while this method use MLP over node features to get the initial guesses for these unlabeled node's labels. Therefore in terms of novelty I am not quite about the contribution. \n\n2) Since this work is on improving label propagation for node classification, various label propagation algorithms are better to compared with to show the benefit of MLP other than just comparing with GCN methods.\n\n3) Can the proposed method be used for inductive setting? or other graph tasks other than node classification? The power of GCN is that it learns node embeddings and then used for various end-tasks. Also does the features for each node need to be very good to achieve good performance? If that is case, what if we just use features with some traditional ML algorithms such as kernel SVM? How about the results on some social network where the graph has strong connections between nodes? Without answering all these questions, it is hard to tell the usability of the proposed method, and get readers a deep understanding why GCN is not performing well with this simple heuristics. \n ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After rebuttal the reviewers unanimously agree that this is a strong paper and should be accepted
Decision: Accept (Poster)