Combating Bilateral Edge Noise for Robust Link Prediction

Summary

This paper focuses on the robustness of graph neural networks (GNNs) in the presence of edge noise during link prediction on graphs. The authors empirically investigate the impact of edge noise on both the input topology and target labels, revealing significant performance degradation and representation collapse. To address this challenge, they propose a novel principle called Robust Graph Information Bottleneck (RGIB), which leverages information theory to extract reliable supervision signals and prevent representation collapse. The paper explores two instantiations of RGIB, RGIB-SSL and RGIB-REP, which utilize self-supervised learning and data reparametrization techniques, respectively, for implicit and explicit data denoising.

Strengths

Overall, this paper makes a valuable contribution to understanding and enhancing the robustness of GNNs in link prediction tasks affected by edge noise. The main novelty is based on systematic study of Bilateral Edge Noise including its empirical influence, visualization, and two instantiations of Robust Graph Information Bottleneck with data reparameterization and data augmentation. This paper also provides theoretical analysis for noisy dataset convergence relaxations.

Weaknesses

This paper provides a novel method and analysis for the edge noise issue for the GNN, through the lens of information theory. The method is clearly explained, and the performance is supported with grounded evaluations with visualizations. I did not carefully check the theory proofs, but from the main paper, there is no obvious limitation.

Questions

If the SSL and REP versions are parallel methods, could the authors discuss the guidelines on method selection? Are they be simultaneously used while still improve? It would be better to add a section of such discussions with supportive case evidence.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See above.

Summary

This paper proposes to tackle the bilateral edge noise via mutual information. The authors start from empirical observations that existing GNNs are vulnerable to bilateral edge noises. To tackle this issue, the authors propose a robust graph information bottleneck which is information-theory guided. In practice, a self-supervised regularization and a purification mechanism are proposed. The extensive evaluation on various datasets as well as models demonstrates the effectiveness of proposed algorithm.

Strengths

1. The paper is well-written and well-organized. 2. The introduced bilateral edge noise is an interesting and challenging problem in GNNs. 3. The proposed robust graph information bottleneck is well-motivated by both sufficient empirical observations as well as theoretical analysis. 4. The experiments are extensive, including various datasets and GNNs. Various ablation studies demonstrate the effectiveness of RGIB-SSL and RGIB-REP.

Weaknesses

I have several concerns: 1. In RGIB-SSL, the authors introduce hybrid graph augmentation which shows superiority over other contrastive learning methods. However, how the proposed augmentation outperforms other graph contrastive methods needs more clarification to provide some insights of this design. 2. It is recommended to demonstrate the robustness of the proposed algorithm under attacks, such as [4, 8, 46].

Questions

1. Please clarify the motivation of hybrid graph augmentation and the highlight the contribution compared to those in [18, 47]. 2. Please include the evaluation under attacks [4, 8, 46] if possible, or discuss the generalization of the proposed algorithm against adversarial attacks.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors have not discussed the limitations.

Summary

This paper focuses on the robustness of GNNs under the edge noise. The authors disclose the influence of bilateral edge noise and the corresponding robustness issue via a series of empirical studies on edge noise. Based on the observations of bilateral noise, the authors propose an information-theory-guided principle, Robust Graph Information Bottleneck (RGIB) and its two instantiations, RGIB-SSL and RGIB-REP. Experimental results verify the effectiveness of RGIB instantiations.

Strengths

- The paper is well written and structured. - The emprical studies and relative experiments are clear and convincing. - Experiments are comprehensive and complete. - The proposed RGIB principle is simple yet effective.

Weaknesses

- There is a lack of more comprehensive studies on other graph representation learning tasks, such as node classification. - RGIB is proposed under the assumption of edge noise, however the motivation statement is not very convincing. The relationship between GIB and bilateral noise should be further explained.

Questions

- I wonder how RGIB improves other graph representation learning tasks, like node classification? - Why the model performance on original graphs are not reported? Since the graphs without additional noises are not considered as completely clean, RGIB should be able to provide performance gain as well.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Please refer to the weaknesses.

Summary

The authors extend the Graph Information Bottleneck (GIB) to "bilateral" structural noise and label noise. That is, both the adjacency matrix and the labels are being randomly perturbed. The authors observe that the bilateral noise leads to "poorer alignment and a worse uniformity". To handle this noise, the authors decompose the term used in GIB and, due to its intractability, propose two efficient, practical instantiations.

Strengths

1. The authors propose two methods that significantly and consistently outperform the baselines 1. The approach is principled due to its roots in the powerful concept of information bottleneck 1. The experiments are extensive and are convincing that the method has some merit for certain applications The paper is generally well-written and logically structured.

Weaknesses

1. The method seems to rely heavily on the assumption that the node features are clean. It would be good to study how sensitive the model is to feature noise. 1. The authors could elaborate more on the assumptions etc., that make their instantiations tractable and when these assumptions are met. Minor: margins between lines 215 & 216 seem violated.

Questions

1. Would it make sense / be possible also to evaluate the method using an attack that optimizes for $\tilde{A}$ or $\tilde{Y}$, e.g., using first-order optimization? 1. As you do not provide code, I wonder if the clean labels/adjacency are used in any way during training?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors should elaborate more and more prominently on what the computational requirements of their method are and how it compares to the other baselines.

Summary

This paper tackles the challenge of link prediction on graphs in the presence of edge noise, a topic that has seen little exploration despite the advancements in graph neural networks (GNNs). Through an empirical study, the authors reveal that edge noise can adversely affect both input topology and target labels, leading to performance degradation and representation collapse. In response, the paper introduces an information-theory-guided principle named Robust Graph Information Bottleneck (RGIB), which aims to extract reliable supervision signals and prevent representation collapse. RGIB achieves this by decoupling and balancing the mutual dependencies among graph topology, target labels, and representation, which creates new learning objectives for building robust representations in the face of bilateral noise. The authors present two specific implementations of RGIB, namely RGIB-SSL (which employs self-supervised learning) and RGIB-REP (which uses data reparametrization), for implicit and explicit data denoising respectively. The effectiveness of the proposed RGIB methods is validated through extensive experiments on six datasets and three GNNs under various noisy conditions.

Strengths

The paper is well-written with clear motivation and structure. Overall interesting problem; good mathematical exposition; solid theoretical results and analysis. This paper has a very comprehensive experimental analysis including the experiments in the appendix.

Weaknesses

This paper is overall good.

Questions

Most of my concerns are addressed in the appendix. I have no further questions or suggestions for this work.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

Board impact is discussed in the appendix.

Thank you for the rebuttal

All my comments have been addressed. I think it would help the presentation if the adversarial attack experiments from Appendix D.4 were moved to the main part in a revision of the submitted paper.