Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper makes a comprehensive theoretical research and analysis on the time and reason of implicit denoising in GNN, which is an interesting and well written research. Graph Neural Networks (GNN) is widely used in graphic structured data processing because of its powerful representation learning ability. The convergence of noise matrix is studied in this paper. Theoretical analysis shows that implicit denoising depends on connectivity of noise matrix, graph size and GNN structure to a large extent. A robust graph convolution is obtained by solving the signal denoising problem of the extended graph, which improves the smoothness of the NOD representation and the corresponding denoising effect. Extensive empirical evaluation verifies the effectiveness of the proposed model.
strength_and_weaknesses: This paper makes a comprehensive theoretical research and analysis on the time and reason of implicit denoising in GNN.
clarity,_quality,_novelty_and_reproducibility: This paper makes a comprehensive theoretical research and analysis on the time and reason of implicit denoising in GNN, with fair quality.
summary_of_the_review: I am not currently engaged in research in this field, and I am not very familiar with the research content. AC can make decisions based on the opinions of other reviewers.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper provides an analysis of the denoising effect of GNNs and reveals the impact of graph size, connectivity, and GNN architectures. It also proposes a robust Neumann graph convolution (RNGC) model based on the defined adversarial graph signal denoising problem. 
strength_and_weaknesses: # Strength:

1. The paper is clearly written and easy to follow.

2. The paper provides a theoretical analysis of the denoising effect of graph convolution. The impact of graph size, connectivity, expansion order are discussed. This further strengthens previous unified understanding of designing GNNs from the graph signal denoising perspective.

3. The paper proposes a robust Neumann graph convolution model inspired by adversarial training. This perspective is novel and interesting (but with many concerns as discussed below).



# Weakness：

1. The theoretical analysis is based on a specific and simplified GNN architecture (a linear layer followed by a diffusion approximated by a Naumann series). This does not align with classic and popular GNN architectures and therefore might not correctly reveal the denoising effects of GNNs. Moreover, the problem being analysed in Section 3 (Eq. (8)) is a fully-supervised problem with all nodes being labeled data. It is unclear how it aligns with the common semi-supervised setting in GNNs.

2. I believe there is much literature about graph signal processing with statistical analysis on noise, but the paper does not cite any of them. It will be better to discuss how the theoretical results improve what has been done in the literature if there are any.

3. The is a lack of right intuition in the proposed robust Neumann graph convolution model (RNGC). In the definition of the adversarial graph signal denoising problem, the adversary tries to perturb the graph which enlarges the distance between connected neighbors. In other words, in the forward computation of RNGC, the graph is perturbed such that dissimilar nodes are connected as shown in Eq. (17). Intuitively, this will have a negative impact on the final performance even in the clean feature setting. Furthermore, the noise in the feature might make similar nodes (measured by original clean features) dissimilar (measured by noise features), which makes it even worse. It is unclear how the proposed formulation can help mitigate the impact of noise features (or noise graphs).

4. The theoretical analysis does not provide new insight into how to design better GNNs. In fact, the analysis is irrelevant to the proposed idea in Section 4. 

5. The experimental results are not convincing. 

(1) First of all, the comparison between the proposed model and the baselines is unfair. For instance, it is mentioned in Section 5 that GCN and GAT have 2 layers, IRLS has 8 layers (or more but unclear), while NGC and RNGC have 16 layers. Since more layers might achieve better denoising effect, such a comparison can not justify the advantages of the proposed models. 

(2) Moreover, the baselines are quite weak. I wonder how APPNP [1] and AirGNN [2] perform in the considered settings with a fair number of propagation layers. APPNP is a GNN that exactly follows the graph denoising problem in Eq. (1). AirGNN is a GNN specifically designed for handling noise features with a new graph denoising problem. In terms of graph structure attacks, ProGNN [3] and many others usually provide much stronger baselines than those being compared in the paper. It will be more convincing to include this baseline as well.


[1] Predict then Propagate: Graph Neural Networks meet Personalized PageRank, ICLR 2019
[2] Graph Neural Networks with Adaptive Residual, NeurIPS 2021
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. The novelty is good but lacks the right intuition and convincing experiments.
summary_of_the_review: The paper analyzes the denoising effect of graph convolutions and proposes a robust Neumann graph convolution inspired by adversarial training. The proposed idea lacks the right intuition and more convincing experiments are needed.

-------
After rebuttal, I increase my score to 5.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper aims to analyze the Denoising effect provided by GNNs (on corrupted graph data, typically with noisy labels).

It recalls the Neumann Graph Convolution (NGC) perspective and how it connects with Graph Signal Denoising (GSD).

It defines the High-order Graph Connectivity Factor, \tau, which is a measure of the average connectivity of the graph, and of its structure.

It proposes a theoretical estimation of the denoising effect of a GNN, in the NGC framework, in the form of theorem 1: denoising is stronger for larger graphs, and linearly depend on \tau, the above-defined High-order Graph Connectivity Factor.

It proposes an adversarial setup, the adversarial graph signal denoising problem, and its solution, in the form of an algorithm, Robust NGC.

The RNGC algorithm does not significantly outperform the pre-existing NGC approach: average performance is almost always exactly equal, and is always perfectly in the same range of performance (error bars overlapping with average value).

strength_and_weaknesses: Strengths:
- The key concepts and intuitions are explained and after a bit of work, are inferred from the paper.
- Figure 1 clearly illustrates the notion of High-order Graph Connectivity Factor, albeit only on very simple graphs.

Weaknesses:
- the main (empirical) claim, that RNGC outperforms others (NGC, mainly) is not backed by evidence: in fig 1 and table 1,2,3,4, they perform as well, or with very similar accuracy, within the error bar of each other.

    In Table 5, NGC's results are not reported (Also Table 4 does not report error bars).

    (it is not highlighted, but is mentioned that "Compared with NGC, the additional computation cost is O(|E|)." (understand: linear in the number of edges). This can be large compared to the number of nodes, in industrial graphs. If it's just a +O(E), it's ok. If it's multiplicative, it is not negligible at all.)

- The theoretical analysis suffers two main problems:
    * it does not convincingly apply to other GNNs than NGC ("Besides, if we remove the non-linear functions in GCN (Kipf & Welling, 2017), it also can be covered by our model.") This is not convincing. Further more, the 4 assumptions (esp. 3 and 4) of Lemma 1 are not convincingly applicable to most GNNs/datasets (at least it's not obvious). This hinders the generality of the theorem 1, which is the theoretical contribution of the work.
    * it does not predict any kind of non-trivial, precise or insightful denoising effects. Authors claim themselves :
      > "We prove that with the increase in graph size and graph connectivity factor, the stochasticity tends to diminish, which is called the “denoising effect” in our work." -> This result is very intuitive and pretty trivial, it seems.
     > "Besides, GNN architectures also affect the convergence rate. Deeper GNNs can have a faster convergence rate." -> this also seems very trivial to me.

     Other than this, the effect of graph structure is hidden in the "High-order Graph Connectivity Factor" \tau, which is not very transparent, but could be argued is an important contribution (it's hard to say, it's not advertized this way)
- The authors fail to discuss the compromise between Denoising and Over-smoothing, although at first sight this seems like a very obvious problem to me ! Then, somehow NGC performs well on heterophilic graphs.. but why, I do not understand. Maybe precisely because NGC does not smooth directly, as a GNN would do ?
- Actually, oversmoothing appears in 4 and 5, hidden in the Appendix: on the original tasks (without added noise), the performance decreases when adding too many layers.

clarity,_quality,_novelty_and_reproducibility: 
Clarity:
- paper is not well written. More importantly, some sentences are incomplete:
> The relationship between GSD and GCN can be briefly illustrated as follows (Ma
et al., 2021).
- some important quantities are not defined: for instance, In Eq (1) and (2), lambda is not defined. I could try to guess it's like a Lagrange multiplier, but it's not obvious.  It is set to 64 in Fig. 1
- In Eq. (31), d does not appear.
- some parts are especially unclear, like the top of page 6.
- remark 3 refers to sec 3 (twice), which it is in.. ?

Quality: 
- discussion of denoising vs oversmoothing compromise is missing, making the point of the whole paper unclear.
- many quantities are not defined where they should in equations. 
- many arguments are not convincing (see other parts of my review above)
- empirical results are not convincing, albeit rather well reported (error bars are missing in table 5). 

Novelty: 
- as admitted, NGC is not new. RNGC is, but does not significantly outperform.

Reproducibility:
I did not find the link to the code.


summary_of_the_review: Overall, this paper does not produce what it claims to, both empirically and theoretically.

In addition, the very point of the paper (denoising) is not clearly made (I would expect more denoising also means more oversmoothing, i.e. not always better performance).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies in-depth the implicit denoising effect in graph neural networks, which remains an open issue from the theoretical perspective. Rigorous theoretical analysis is provided to uncover the underlying philosophy of GNNs for graph signal denoising. The theoretical results and discussion suggest that the implicit denoising effect is related to the graph structure, size, and the GNN model's architecture. A robust GNN model is developed by solving a novel adversarial graph signal denoising probelm. Extensive experimental studies are presented to verify the obtained theoretical results and the effectiveness of the proposed robust GNN model.
strength_and_weaknesses: Strengths:
+ The readability of this work is good. It is easy to follow since the motivation and presentation are quite clear;
+ The theoretical formulation and analysis are generally solid;
+ The proposed adversarial graph signal denoising problem is interesting and may potentially attract more researchers who are expecting to develop advanced GNNs via solving the GSD problem.

Weaknesses:
+ The relationship between NGC and the existing multi-scale GNNs is not clear. Some remarks on clarifying this issue are helpful;
+ Based on the experimental results shown in Section 5, the advantages of RNGC over NGC are not significant. More discussion on possible reasons are beneficial for improving the clarity of this work;
+ The footnote of Remark 1 mentions that you adopt another form of normalized adjacency matrix in the experiments, instead of the exact form presented in Remark 1. The influence is not studied/clarified with any empirical results;
+ Although the authors present Figure 1 as a case study on the influence of graph structure on implicit denoising, more details (to be added in the Appendices) are needed to show how the $\tau$ values are calculated. Also, the records for Graph 1~4 are not very convincing to conclude the insight (5), that is, "In terms of graph size, the graph with a larger size has a better denoising effect." Please clarify this issue;
+ To develop RNGC, the authors have used a little trick that "....approximate Eq. (16) by replacing the F with X in the
inverse matrix on the right-hand side...." The rationale should be discussed. Also, how is the convergence property of RNGC?

clarity,_quality,_novelty_and_reproducibility: The quality, clarity, and originality of this work are generally above the average bar of ICLR publication. 
summary_of_the_review: Overall, I vote for a weak accepting. I like the idea of studying the implicit denoising effect via defining and analyzing the high-order graph connectivity factor. My major concern is about the weaknesses raised above. Hopefully, the authors can address my concern in the rebuttal period.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies the phenomenon of implicit denoising in GNNs. The reviewers raised several concerns, among which the fact that the theoretical analysis is based on a simplified GNN architecture that is dissimilar from typically used GNNs, putting doubt in the applicability of the analysis. There was also concern about the discrepancy between theoretical claims and experiments. Some of the doubts were addressed in the rebuttal, but we believe the paper is below the conference bar. 
justification_for_why_not_higher_score: somewhat limited novelty
Decision: Reject