Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper presents NAFS (Node-Adaptive Feature Smoothing), a method that constructs node representations by relying on smoothing only, i.e. without parameter learning. To do this, the authors first provide a formulation for the smoothing operator after infinite steps, i.e. when the stationary state is reached. They then define over-smoothing distance as a way to assess how much a node is close to the stationary state after k smoothing steps. Finally, they use over-smoothing distances to calculate a different smoothing weight for each node.

Experiments show that representations obtained by smoothing with these weights, together with feature ensembles obtained by applying different convolution coefficients, provide performances in clustering and link prediction tasks which are comparable, if not better, than many other state-of-the-art approaches.
main_review: The paper tackles the problem of over-smoothing by proposing a method to differently weight the smoothing for each node. The problem is well known and in my opinion methods to better understand and solve it are very relevant for the community.

**Positive aspects**

While the connection of over-smoothing with powers of the adjacency matrix is not novel per se, I did not know about prior methods tackling the problem as it has been done in this paper. However, I should highlight that just recently another **very** similar paper was published on arxiv (Zhang et Al. "Node Dependent Local Smoothing for Scalable Graph Learning" https://arxiv.org/abs/2110.14377 ). While it seems recent enough to not put the contribute of this paper into discussion, I think it would be worth citing it and comparing its method to the presented one.

The approach is presented quite clearly and in a well-structured way. I appreciate that the authors introduce it as a baseline: better results might be obtained by adding a learning component to it, but it is interesting to see how far adaptive smoothing alone can go.

**Main concerns and chances for improvement**

By being introduced as parameterless, NAFS is compared with other methods (autoencoders, adversarial models) which are typically unsupervised. Moreover, the only supervised task it is tested on is the link prediction one. I think further experiments are required to better understand how useful the method can be. In particular, I think it would be interesting to see how it performs on other supervised tasks such as node classification (e.g. suing the linear evaluation protocol, used to assess the performances of many recent graph SSL methods).

The weighting scheme looks intuitively useful, but I believe it would be useful to understand how it actually impacts final representations from a more theoretical perspective. How do weights change node representations from converging to the same identical one? 

Few minor corrections:
- page 1: "and these methods share two major limitations" ("and" looks superfluous)
- page 2: $\hat{A} = A + I_n$ should be $\tilde{A} = A + I_n$
- the $r$ convolution coefficient which is introduced in Section 4.2 previously appears in Equation (1) and this makes the equation less clear. I think it would be easier for the reader to have its description close to (1) instead. 

summary_of_the_review: The paper tackles an interesting problem in a clear and reasonable way. The main issues I see here are the evaluation, that to me still looks quite limited, and the lack of a theoretical interpretation for the weighting scheme.

While a possibly negative outcome of the evaluation of a node classification task does not concern me too much (the method itself is defined as a baseline and I think it does not require to be state-of-the-art in every single benchmark for it to be valuable), I think motivating the weighting scheme by formally demonstrating how it impacts smoothing when $K$ grows is an important step to make the paper more convincing.

----
I have read the authors' replies to the other reviewers and myself and they look convincing to me. I particularly appreciate they addressed my comments on related works, theoretical analysis, and further experiments on supervised tasks. They also took care of adding mean/std results for both new and old experiments (even when results are deterministic, which is great to emphasize). This makes the paper way more convincing in my opinion and worth being accepted, which is why I increased my score accordingly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors of this paper took a novel perspective to present the node-adaptive feature smoothing (NAFS) algorithm, which generates node embeddings without explicit training/parameter learning. The method first performs feature smoothing, then combines the smoothed features using adaptive weights which are node-specific. They further enhanced this method by ensembling the smoothed features extracted with different hyper-parameters. The authors have conducted many experiments to validate the model performance, and demonstrate the model's efficiency empirically. 
main_review: The authors took a novel perspective and presented NAFS which does not explicitly require parameter learning. It is also a bold idea that, in addition to separate feature transformation from feature smoothing, the model removes feature transformation altogether. 

A few questions:
1. Since the method has no feature transformation step, the construction of node feature in the initial step seems to become rather important. What are the features used for each of the dataset in the experiment (Cora, Citeseer, PubMed, Wiki)? I would be good to state them clearly in the paper. 

2. Would be useful to comment on what the authors think might be the limitation of this method. For example, NAFS by design does not require task specific training, although hyper-parameter tuning allow the model to serve for different tasks. Then what types of graphs/tasks might work best with this model, or is it indifferent.

summary_of_the_review: In summary, the paper is well presented. The motivations and the authors' insights to this model is well explained. The method is clearly described. The authors performed many experiments to validate the model's performance, with additional ablation studies. Would be nice to have more discussion on which scenarios the model works better/worse.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper deals with (unsupervised) learning with graphs, specifically node-level tasks. Inspired by spectral GNNs, specifically Graph Convolutional Networks (GCN), the authors propose a simple neighborhood smoothing technique to capture the graph structure around each node in the given graph. Contrary to GNN, the proposed algorithm is parameter-free and hence scales better than their end-to-end trained GNN counterpart.                    

Motivated by the problem of over-smoothing of GCN (Li et al., 2018), they propose the so-called "over-smoothing distance" measuring how close a node's feature is to be over-smoothed, which is simply the row-wise distance between $A^k X$ and $A^{\infty}X$ with regard to the Euclidian distance, see Def. 3.1. Based on this distance they define the smoothing weight matrix which is then used to weight the neighboring node features during neighborhood aggregation. The resulting features $\hat{X}$ are computed as $\hat{X} =  \sum^{K}_{k=0} W(k)\hat{A}X$, where $W(k)$ is the $k$th smoothing weight matrix.

The proposed architecture is evaluated on standard, old, small-scale (unsupervsied) link and node classification (Cora, Citeseer, PubMed) tasks showing somewhat classification performance while showing a considerable speedup in computation time. 
main_review: **Strengths:**
1. Simple approach that seems to work well
2. Well-presented and easy to read
3. Rather large set of baseline methods used

**Weaknesses** 
1. Old, small-scale datasets
2. No error bars/standard deviations were reported 
3. Scalability experiments only carried out on synthetic graphs

**Suggestion**
1. Evaluate the method on more large-scale, modern datasets, e.g. OGB datasets or graphlearning.io
2. Perform scalability on real-world datasets 
3. Discuss "linear" GNN architectures, e.g., https://arxiv.org/abs/1810.05997
4. Discuss other scalable GNN alternatives, e.g., ones based on label propagation, see https://arxiv.org/abs/2010.13993

**Comments**
1.  The discussion in section 2.2 only applies to a specific GNN layer, namely GCN 

**Question**
1. Is your approach also liftable to other GNN architectures besides GCN?


summary_of_the_review: The approach is very simple, it offers no significant theoretical or methodological contributions, and the experimental study is not executed well enough, i.e., it only uses small-scale, old or synthetic datasets. Further, the are some problems in the experimental protocol, e.g., no standard deviations are reported.
review_title: null

Meta-review: The paper proposes NAFS (Node-Adaptive Feature Smoothing), which constructs node representations by only using smoothing without parameter learning.  The authors first provide a formulation for the smoothing operator. They then define over-smoothing distance to assess how much a node is close to the stationary state. Finally, they use the over-smoothing distance to calculate a smoothing weight for each node. Experiments are conducted to verify the efficacy.

Strength
* The paper tackles the problem of over-smoothing, which is a well-known issue in GNN.
* The solution appears to be effective. 
* The paper is generally clearly written.

Weakness
* The novelty and significance of the work might not be enough. Aspects of the contributions exist in prior work.

---

Additional experiments have been conducted during the rebuttal. The reviewers appreciate the efforts.

After rebuttal：

Reviewer SHxg increased the score accordingly.

Reviewer w2Qg says “Given the concerns proposed by the other reviewers, I adjusted my score.”

Reviewer YM4P says “I read the rebuttal and slightly increased my score.”
Decision: Reject