Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a novel algorithm, node-dependent local smoothing (NDLS), which allows controlling the smoothness of every node by setting a node-specific smoothing iteration and applies to both feature smoothing and label smoothing. NDLS theoretically analyzes what influences the smoothness and gives a bound to guide how to control the extent of smoothness for different nodes. Extensive experiments on seven real-world graph datasets demonstrate that NDLS pipeline enjoys state-of-the-art performance on node classification tasks, can be combined with any GNN models, and is scalable and efficient.
main_review: ----------Strengths----------

(1) The proposed NDLS algorithm is novel and generalizes some existing smoothing techniques.

(2) NDLS shows state-of-the-art performance across various datasets. Thus the algorithm is robust and generally reliable in practice.

(3) The paper is generally well written. The authors provide some theoretical analysis of the space and time complexities of the proposed NDLS pipeline. Moreover, the experimental results are summarized using some nice figures.

(4) The NDLS kernel can act as a drop-in replacement for other graph kernels and be combined with some existing models.

----------Weaknesses----------

(1) The NDLS pipeline effectively unifies and generalizes the feature and label smoothing algorithms used in GCN, SGC, APPNP, etc. The authors claim NDLS is advantageous because it allows controlling the smoothness to avoid under-smoothing or over-smoothing. However, it seems that this work does not provide deeper insight into the success of smoothing methods, especially why the control of smoothness is critical to improve the existing feature and label smoothing algorithms. In this sense, the overall contribution seems limited and a little bit incremental. The performances gain in experiments are also relatively small.

(2) Apart from SGC, SIGN, and GBP, I think it is also a good idea to compare with C&S [1] if possible. C&S uses a different smoothing procedure which is called Correct and Smooth (C&S). It is interesting to discuss whether the proposed NDLS algorithm can be combined with C&S.

----------Overall----------

Overall, I think this work is an interesting generalization of the existing smoothing algorithms for graph learning. However, it seems unclear to me why setting a node-specific smoothing iteration is crucial. Hence, I recommend weak rejection.

----------References----------

[1] Huang, Q., He, H., Singh, A., Lim, S.N. and Benson, A.R., 2020. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.13993.
limitations_and_societal_impact: The potential negative social impact of the work is not presented in the paper. Although the reviewer does not foresee any potential negative impacts, the authors are encouraged to add such discussions if space permits.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed a node-dependent local smoothing method for graph neural networks via computing a local smoothing iteration value. Experimental evaluation was conducted on seven datasets.
main_review: The paper is well-written on the whole. Illustrations are intuitive and can help readers understand the proposed idea greatly. Nonetheless, there are several questions/problems as detailed below:

1. The use of acronyms, particularly in the abstract, is problematic to me. SGC and APPNP are acronyms unknown to me at least. Acronyms should be defined before using.

2. Notations are not always consistent. For example, I think the X in line 109 and 111 should be in bold normal font, as previously appeared.

3. Since the "Industry" dataset is not in the public domain, it will be helpful to provide an explanation why this dataset is chosen instead of another public dataset.

4. Could you do a paired t-test at least for GBP vs NDLS in Table 3 to study the statistical significance of the improvements?

5. Training efficiency study in Sec. 6.2 and Figure 3: Why to choose the private "Industry" dataset instead of a public dataset for this study. Do you have similar studies and plots for other datasets? Using a public dataset will make the result more reproducible.

6. From Figure 5(a), I am wondering whether using the node degree will be a simpler alternative than the proposed LSI for the proposed framework, e.g. 1/node_degree or similar. Have you studied such a simple choice?

7. Although Appendix A.5 provided hyperparameter details, it is not always clear how certain hyperparameters were chosen. For example, for k=200 in stage (1) and k=40 in stage (3), were these number just magically set by the authors or from tuning? If by tuning, how was it done? More importantly, I did not find studies on the performance sensitivity w.r.t. such hyperparameters.

8. Consistency issue: why is the caption for Table 4 at the bottom while captions for other tables are at the top?

9. Anonymity issue: the supplementary material is not fully anonymized. The readme shows a username with a local path "C:\Users\......\Desktop\NDLS", where I replaced the name with "......".


limitations_and_societal_impact: See the above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors proposed a GNN structure name NDLS which comprises three parts: i) the feature propagation part, NDLS-F, ii) a MLP for label prediction and iii) a post processing label smoothing part NDLS-L. The first and last part and are done individually as pre-processing and post-processing, where each node propagates its feature/label representation according to their local smooth iteration (LSI). The LSI is computed per node based on its connectivity and designed to avoid over-smoothing instead of using same step for all nodes. Due to the simplified framework, the model can be trained efficiently without losing performance when compared to SOTA baselines. 
main_review: The paper is very well-written and easy to follow, with intuitive figures for better understanding the concept. The authors did extensive experiments and the results are nicely interpreted. 

pros: 
- The difference of LSI distribution in different datasets is a nice indicator of how over-smoothing is also a data-dependent issue and should be treated adaptively.
- Detailed experiments with analysis on how different component of the model affect the results.
- Efficient algorithm with separated component that can be precomputed.
- Intuitive interpretation of results and trained models. 

cons: 
- The definition of LSI in equation (4) implicitly assumes a monotonous decreasing distance with k, which I am not sure if this is the case.  
- Improvement on inductive settings are marginal, and wether separate pre/post processing is needed is not clear.
limitations_and_societal_impact: The authors did not addressed the possible limitation and negative societal impact of their work. Protecting personal privacy especially in social network data is always worth discussion.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work proposes NDLS, a strategy to estimate a different number of 'propagations' for each node in the graph, delimiting the neighborhoods used to update node embeddings. The authors apply NDLS both as a pre-processing (feature space) and post-processing (prediction space) technique. Between pre-processing and post-processing, any vanilla (non-Graph) classifier can be used.
main_review: Intuitively, NDLS chooses neighborhood sizes so that all nodes are equally far from oversmoothing. Overall, I like this idea and its simplicity. Scalability is also an asset, and the idea for computing node-dependent numbers of propagations is intuitive. I think this work fits well in the current trend of simplifying graph ML. The idea is significantly novel and the technical developments appear sound. The writing is passable.

### Questions and issues
* How does this work compare to https://arxiv.org/abs/2010.13993 ?

* Why are the results in Table 3 different from the ones in the OGB leaderboard? For instance, Table 3 shows SIGN achieving $64.2$ average accuracy on ogbn-papers100M. However, OGB leaderboards (https://ogb.stanford.edu/docs/leader_nodeprop/) show $65.68$.

* Previous works (https://arxiv.org/abs/2003.00982) have shown that small datasets --- such as Cora, Citeseer and Pubmed --- are not reliable benchmarks. Do you have results for other OGB large-scale benchmarks?  

* Are the bounds in section 3 used only for interpretation or to avoid directly computing $k$? 

* How is $k(\cdot, \cdot)$ computed in practice and how expensive is it? Does the method require computation of eigenvalues (as in Theorem 3.1, eq 5)?

* As a curiosity, how important is the normalization factor in Eq. 8? Do you have any ablation studies for this?

* In the sparse graph experiments, what do the authors do with missing features? Fill with some default value?

* Can the authors add more plots like Figure 3 (times vs. performance) either in the manuscript or appendix?


### Typos, etc
* The authors often use acronyms without introducing them (e.g. in the abstract and first paragraph of intro)
* Line 40: 'poorly connected nodes needs' -> poorly connected nodes need 
* Lines 56-57: authors say real-world graphs have long-tailed degree distributions. Not all real-world graphs do have it. Probably better to be careful.
* Line 75 and 76: a matrix should not be defined as a set

limitations_and_societal_impact: The authors adequately discussed limitations.
review_title: null

Meta-review: This paper proposes a node-dependent local smoothing (NDLS) algorithm to control the smoothness of every node. NDLS provides a bound to guide how to control the extent of smoothness for different nodes. Extensive experiments on seven real-world graph datasets demonstrate that NDLS pipeline enjoys state-of-the-art performance on node classification tasks, can be combined with any GNN models, and is scalable and efficient.


The proposed NDLS algorithm is novel and generalizes some existing smoothing techniques. The NDLS kernel can act as a building block to replace other graph kernels and be combined with some existing models. The authors also provide some theoretical analysis of the space and time complexities of the proposed NDLS pipeline. 

The paper is very well-written and easy to follow, with intuitive figures for better understanding the concept. 

NDLS shows state-of-the-art performance across various datasets. The results are nicely interpreted.  Thus the algorithm is robust and generally reliable in practice.

Therefore, we recommend accepting this paper. 





Decision: Accept (Spotlight)