How Powerful is Implicit Denoising in Graph Neural Networks
Authors: Songtao Liu
Zhitao Ying
Hanze Dong
Lu Lin
Jinghui Chen
Dinghao Wu
Venue: Submitted to ICLR 2023 (2023)
Keywords: GNN denoising
GNN theory

Abstract: Graph Neural Networks (GNNs), which aggregate features from neighbors, are widely used for processing graph-structured data due to their powerful representation learning capabilities. It is generally believed that GNNs can implicitly remove feature noises. However, existing works have not rigorously analyzed the implicit denoising effect in graph neural networks. In this work, we conduct a comprehensive theoretical study and analyze when and why implicit denoising happens in GNNs. Our theoretical analysis suggests that the implicit denoising largely depends on the connectivity and size of the graph, as well as the GNN architectures. Motivated by adversarial machine learning in improving the robustness of neural networks, we propose the adversarial graph signal denoising (AGSD) problem. By solving such a problem, we derive a robust graph convolution, where the smoothness of the node representations and the implicit denoising effect can be enhanced. Extensive empirical evaluations verify our theoretical analyses and the effectiveness of our proposed model.


Reviews:
[{"review_id": "dJu3p8zbJm", "reviewer": "Reviewer_Jway", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper aims to analyze the Denoising effect provided by GNNs (on corrupted graph data, typically with noisy labels).\n\nIt recalls the Neumann Graph Convolution (NGC) perspective and how it connects with Graph Signal Denoising (GSD).\n\nIt defines the High-order Graph Connectivity Factor, \\tau, which is a measure of the average connectivity of the graph, and of its structure.\n\nIt 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.\n\nIt proposes an adversarial setup, the adversarial graph signal denoising problem, and its solution, in the form of an algorithm, Robust NGC.\n\nThe 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).\n", "summary_of_the_review": "Overall, this paper does not produce what it claims to, both empirically and theoretically.\n\nIn 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).", "strength_and_weaknesses": "Strengths:\n- The key concepts and intuitions are explained and after a bit of work, are inferred from the paper.\n- Figure 1 clearly illustrates the notion of High-order Graph Connectivity Factor, albeit only on very simple graphs.\n\nWeaknesses:\n- 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.\n\n    In Table 5, NGC's results are not reported (Also Table 4 does not report error bars).\n\n    (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.)\n\n- The theoretical analysis suffers two main problems:\n    * 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.\n    * it does not predict any kind of non-trivial, precise or insightful denoising effects. Authors claim themselves :\n      > \"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.\n     > \"Besides, GNN architectures also affect the convergence rate. Deeper GNNs can have a faster convergence rate.\" -> this also seems very trivial to me.\n\n     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)\n- 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 ?\n- 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "UHdswra2DE", "reviewer": "Reviewer_2Src", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "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.", "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. ", "strength_and_weaknesses": "Strengths:\n+ The readability of this work is good. It is easy to follow since the motivation and presentation are quite clear;\n+ The theoretical formulation and analysis are generally solid;\n+ 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.\n\nWeaknesses:\n+ The relationship between NGC and the existing multi-scale GNNs is not clear. Some remarks on clarifying this issue are helpful;\n+ 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;\n+ 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;\n+ 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;\n+ To develop RNGC, the authors have used a little trick that \"....approximate Eq. (16) by replacing the F with X in the\ninverse matrix on the right-hand side....\" The rationale should be discussed. Also, how is the convergence property of RNGC?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "THcz9bJTAY", "reviewer": "Reviewer_ZXuu", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "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. ", "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.\n\n-------\nAfter rebuttal, I increase my score to 5.", "strength_and_weaknesses": "# Strength:\n\n1. The paper is clearly written and easy to follow.\n\n2. 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.\n\n3. 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).\n\n\n\n# Weakness：\n\n1. 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.\n\n2. 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.\n\n3. 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).\n\n4. 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. \n\n5. The experimental results are not convincing. \n\n(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. \n\n(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.\n\n\n[1] Predict then Propagate: Graph Neural Networks meet Personalized PageRank, ICLR 2019\n[2] Graph Neural Networks with Adaptive Residual, NeurIPS 2021", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9hkxFi0u6n", "reviewer": "Reviewer_J8PX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "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.", "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.", "strength_and_weaknesses": "This paper makes a comprehensive theoretical research and analysis on the time and reason of implicit denoising in GNN.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject