DropEdge not Foolproof: Effective Augmentation Method for Signed Graph Neural Networks

Summary

The paper presents a novel Signed Graph Augmentation (SGA) framework designed to enhance the performance of Signed Graph Neural Networks (SGNNs). The primary focus is on addressing two persistent issues in SGNNs: graph sparsity and unbalanced triangles. The authors demonstrate that the commonly used DropEdge method is ineffective for signed graph augmentation. Instead, they propose SGA, which integrates structure augmentation, candidate edge selection, and a new data augmentation perspective to improve training. Experiments on six real-world datasets show significant performance improvements in link sign prediction tasks.

Strengths

Originality: The paper introduces a new augmentation framework specifically designed for SGNNs, which addresses the unique challenges of signed graphs. Quality: The methodology is well-validated through extensive experiments on multiple real-world datasets, demonstrating substantial improvements in performance metrics. Clarity: The paper is well-organized, with clear explanations of the proposed methods and thorough discussions of experimental results. Significance: This work provides valuable insights and tools for improving SGNNs, which are crucial for tasks like link sign prediction in social networks.

Weaknesses

Generalization: The effectiveness of SGA on other types of signed graph tasks, such as node classification or community detection, has not been explored. Complexity: The proposed framework involves multiple steps and parameters, which may complicate its implementation and tuning. Resource Intensive: The computational requirements for the proposed method may be high, potentially limiting its practical application in resource-constrained environments.

Questions

- Can the proposed SGA framework be adapted for other signed graph tasks, such as node classification or community detection? - How does the performance of SGA scale with larger datasets or more complex network structures? - What are the computational overheads associated with the different components of the SGA framework, and are there ways to optimize them?

Rating

5

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

The authors acknowledge that their data augmentation method is based on balance theory, which may not be applicable to all real-world signed graph datasets. Additionally, the method has only been validated on link sign prediction tasks, and its effectiveness on other tasks remains untested. To improve, the authors could explore the generalization of SGA to other tasks and consider alternative theoretical frameworks for signed graph augmentation. Potential societal impacts, especially in contexts involving negative social interactions, should also be addressed.

Summary

This work addresses the scarcity of effective data augmentation strategies tailored for signed graphs, especially considering the dearth of auxiliary information in real-world datasets. By presenting the generalization error bound for SGNNs and disproving the universal benefit of random DropEdge, this paper introduces Signed Graph Augmentation (SGA). SGA innovates with a structure augmentation module identifying potential edges from network patterns and employs a selective strategy to enrich training data. The proposed method significantly improves SGNN performance.

Strengths

The paper is well structured and has clear writing. The task of signed graph augmentation is interesting and novel. The experimental results show the effectivity of the proposed method.

Weaknesses

1. Regarding the experimental results shown in Table 1, the paper only shows the results of solely using the backbone model and with SGA augmentation method. The efficiency of the proposed method will be more convincing if it can be compared with another augmentation method. In addition to the DropEdge method, there are still other augmentation methods, e.g., mixup-based methods [1,2] and spectrum-based methods [3,4]. 2. Though the performance when using SGA is better, compared to do not using any augmentation method, it introduces many modules to train, e.g., the encoder and the MLG classifier, thus introducing many more parameters. A comparison of a number of parameters and the training time will be better. 3. Minor comments: Figure 3 can be improved to be more clear. The Encoder, MLG classifier, and the classifier loss are not explicitly shown in the figure. Reference: [1] G-mixup: Graph data augmentation for graph classification. ICLR’22 [2] Graph mixup with soft alignments. ICML’23 [3] Spectral augmentation for self-supervised learning on graphs. ICLR’22 [4] Through the Dual-Prism: A Spectral Perspective on Graph Data Augmentation for Graph Classification. arXiv'24

Questions

1. In Section 4, according to ‘the generalization performance of the model is affected by the number of edges’, will randomly adding edges will be more effective than dropping edges in signed graphs? Is there any empirical evidence about this? 2. Lack of complexity analysis and cost time comparison. Is SGA efficient in large-size datasets? ### After rebuttal Most of my concerns have been addressed. I raise my score to 6.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors discussed the limitations of the proposed method.

Summary

Link sign prediction is a significant downstream task in graph data analysis. Current graph data augmentation methods seldom explore this task. This paper analyzes, both theoretically and experimentally, why existing graph data augmentation methods perform poorly on this task and proposes a new data augmentation method tailored for signed graph analysis. Its main contributions include the following two aspects: - It provides a generalization error bound for signed graph neural networks and theoretically verifies that the widely used random edgedrop method is not suitable for the link sign prediction task. - It proposes a novel signed graph data augmentation framework to address two major issues in current signed graph neural networks (SGNNs), namely sparsity and imbalanced triads.

Strengths

1. Although significant progress has been made in the field of graph augmentation, data augmentation methods specifically for signed graphs and link sign prediction are relatively new research directions. Currently, there are relatively few data augmentation methods specifically designed for edge-level tasks in graph augmentation. 2. In this data augmentation module, the authors propose an intriguing new approach, which is to treat the training difficulty of training samples as a feature for augmentation, thereby adjusting the training weights of these samples. 3. The paper is well structured, logically coherent and very easy to understand.

Weaknesses

1. According to the authors' theoretical analysis, reducing the number of training samples does not contribute to improving model performance. However, in Section 3.2, we observed that some training samples were removed because they belonged to imbalanced triplets. Does this observation contradict the theoretical analysis? 2. The authors mention in the limitations section that "for real-world datasets that do not strongly conform to balance theory, our data augmentation may be less effective." What is the basis for this statement? Are there possible solutions proposed by the authors for this issue? 3. Some typographical errors: on line 164, the concatenation operation should use [,] instead of [.]. On line 225, there is a missing space between SGNN and "our results". Also, some formulas have punctuation while some do not.

Questions

Please refer to Weaknesses.

Rating

7

Confidence

5

Soundness

4

Presentation

3

Contribution

3

Limitations

The paper argues that the data augmentation method can alleviate rather than completely solve the current obstacles of SGNN methods. This claim is supported by experimental and theoretical analyses. However, a limitation of this article is that it only addresses a subset of issues within GNN models and their impact on downstream tasks, thus its influence may be somewhat limited.

Summary

This paper proposes a new research subfield focusing on data augmentation methods for signed graphs. Unlike the widely studied unsigned graph augmentation, this method targets the downstream task of link sign prediction rather than the mainstream node classification [1] or graph classification [2]. As far as I know, most current graph data augmentation methods mainly address node classification tasks, while there is relatively little enhancement work for edge tasks, or their effectiveness for link prediction is not significant [3]. Additionally, this article provides the first generalization error bound for signed graph neural networks, which is used to analyze why current commonly used data augmentation methods yield unstable results for signed graphs. In designing data augmentation methods, the article introduces a new perspective from curriculum learning. [1] Kazi, Anees, et al. "Differentiable graph module (dgm) for graph convolutional networks." IEEE Transactions on Pattern Analysis and Machine Intelligence 45.2 (2022): 1606-1617. [2] Chen, Yu, Lingfei Wu, and Mohammed Zaki. "Iterative deep graph learning for graph neural networks: Better and robust node embeddings." Advances in neural information processing systems 33 (2020): 19314-19326. [3] Gasteiger, Johannes, Stefan Weißenberger, and Stephan Günnemann. "Diffusion improves graph learning." Advances in neural information processing systems 32 (2019).

Strengths

- This paper proposes a new subfield of research with a wide range of applications. According to my investigation, this article is indeed the first paper on this topic. - This paper introduces a novel approach to data augmentation, which involves using curriculum learning to adjust the training weights of challenging edges. This perspective is quite insightful. - This paper presents the first generalization error bound for signed graph neural networks and, based on this, analyzes the reasons why current commonly used graph data augmentation methods (such as random edge deletion) yield unstable results for link sign prediction.

Weaknesses

- Although the article introduces a new problem within a subfield, its application scope is relatively narrow compared to more generalized graph structures. - Why can't current graph augmentation methods be directly applied to signed graph representation learning? In the limitations, the authors mention that for datasets with poor balance, the effectiveness of this data augmentation method decreases. Are there any good solutions to this problem? - Can the authors provide a more detailed analysis of the factors affecting SGA's performance? Specifically, why do some unsigned and signed GNNs show significant performance enhancements on certain datasets, while others exhibit only marginal improvements or none at all? - Some typos: In line 231, there is a missing space after "algorithm 2". In line 236, there is also a missing space after "the main result".

Questions

See weaknesses.

Rating

7

Confidence

5

Soundness

3

Presentation

2

Contribution

3

Limitations

See weaknesses.