Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

1) 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. 

2) 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.

3) 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. 
 
review_title: an interesting work, but needs deeper study

final_score: rating: 6: Marginally above acceptance threshold
review_content: (Added on 11/29/2020)

**Post Rebuttal Comment**

I thank the authors for sincerely replying to my review comments. The authors' answers were reasonable to me.

-------------------------------------

**Review Summary**

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

**Summary and Contributions**

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

**Claim**

If I understand correctly, the main claims of this paper are as follows. I will evaluate this paper whether theories and experiments support these claims.

- Claim 1: C&S performs comparably in classification tasks with existing models.
- Claim 2: C&S is computationally cheap compared to existing models.
- Claim 3: C&S improves the predictive performance of existing models.

**Soundness of the claims**

Can theory support the claim?
- This paper did not provide a theoretical justification for the proposed method.

Can empirical evaluation support the claim?
- 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.
- 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.

**Significance and novelty**

Relation to previous work
 
- This paper mentioned the following models as related works.
  - 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)
  - Markov random field: Qu et al. (2019), Gao et al. (2019) (Section 1, Paragraph 4)
  - Shi et al. (2020) (Section 1, Paragraph 4)
- 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.
- 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.
- 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.
[Iscen et al., 2019] A. Iscen, G. Tolias, Y. Avrithis, O. Chum. "Label Propagation for Deep Semi-supervised Learning," CVPR 2019

Relevance to community
- 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.

**Correctness and Clarity**

Is the theorem correct?
- No theorems are provided.

Is the experimental evaluation correct?
- 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.

Is the experiment reproducible?
- Although the experiment code is not provided, the experiments' details are provided, such as hyperparameters and train/validation/test splits.

**Clarity**

Can I understand the main point of the paper easily?
- Yes

Is the organization of the paper well?
- Yes

Are figures and tables appropriately made?
- Yes

**Additional feedback**

Section 3 Paragraph (Base predictors and other models) Line 7: For For Cora ... → For Cora ...

review_title: Review Comment #1

final_score: rating: 7: Good paper, accept
review_content: Summary
-------------
A 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.
The 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.
In 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.

Strong/Weak Points
-------------
* (+) The method is simple and largely well-described, and it is interesting and notable that it is extremely competitive in this setting.
* (+) The experiments range over a substantial set of datasets, models and ablations, providing ample evidence that this is not just a fluke.
* (-) 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.
* (-) 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.

Recommendation
-------------
I 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.
However, 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.

Questions
-------------
* 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.
* Sect 3: What does "Plain GCN" refer to? How is it different from just writing "GCN"?
* Sect 3: Does "Base Prediction" refer to the case of not using any label propagation?

Detail Feedback
-------------
* Sect 2: For reproducibility purposes, it would be helpful to specify values for $\mu$, the number of iteration steps.
* 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.
review_title: Official Blind Review #4

final_score: rating: 7: Good paper, accept
review_content: ## Summary
This 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.

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

## Pros:
1. Provides evidence that diffusing label information is useful and can even beat conventional GNNs.
2. The results are promising, especially on the OGB products dataset.
3. Let the community rethink the value of the classical approach of the label diffusion for semi-supervised node classification.

## Concerns
1. 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. 
2. 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. 
3. 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? 
4. 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. 
5. 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.
6. 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)?
7. 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?
8. 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.
9. 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.
10. In Table 3, what if you use spectral embeddings for Plain GCN?
11. In Section 1.1, “but these methods focus on settings of low label rates” is unclear, and seems tangential to the actual methods. 
12. “Methods” column in Table 2 is unclear to me.
13. 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?
14. Figure 3 is hard to understand.
15. Standard deviations are not included. There should be randomness coming from MLP training.

====

Post-rebuttal: I am happy to accept this paper after seeing my concerns are mostly addressed.

review_title: Interesting results, but experiments do not support claims.

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