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

For Weakness 1 and Q1 on more downstream tasks:

Thanks for your constructive comments. Existing SGNN methods focus primarily on the link sign prediction task, and they ignore the performance on other tasks. We experiment with the performance (metric: Average Accuracy± standard deviation) of SGA on different baselines in node classification and community detection tasks. The datasets were sourced from [16] .

1. Node Classification

2. Community Detection

Based on the experimental results, the SGA shows minimal improvement for the node classification task, but it significantly enhanced the performance for the community detection task.

For Weakness 2:

Please see Common Concern.

For Weakness 3 and Q3 on computational overheads:

1. Model parameter statistics |Model|#params| |:-:|:-:| | SGCN |14851| |GSGNN |30580| |SiGAT |185600| |SGCN+SGA|29702| |GSGNN+SGA|45431| |SiGAT+SGA|200451|

2. model training time cost BitcoinOTC: |Model|time(s)| |:-:|:-:| |SGCN|75.4 ± 6.4| |GSGNN|142.8 ± 17.2| |SiGAT|277.0 ± 30.7| |SGCN+SGA|149.6 ± 42.7| |GSGNN+SGA|5217 ± 48.0| |SiGAT+SGA|351.2 ± 41.2|

The method proposed maintains a relatively stable number of additional parameters and training time, even for large models, avoiding increased computational complexity. Training is efficient and can be completed quickly. The additional operations required by the method can be optimized using parallelization, divide-and-conquer strategies, and feature reduction algorithms. More detailed statistical results are available in the referenced PDF.

For Q2 on the performance on large datasets:

We tested the performance of SGA on the Amazon-CD dataset [17]. The dataset contains 895,266 edges and 97,731 nodes, making it one of the larger signed graph datasets we could find.

Based on the experimental results, our method improves the performance of the baselines on the Amazon-cd dataset.

For Limitation on alternative theoretical framework:

Regarding the analysis of SGA's generalization, we have conducted the following brief discussion.

SGA prevents the formation of unbalanced triangles in the input graph while selecting beneficial training samples. This stabilization of the graph structure preserves the eigenvalue distribution, thereby enhancing the quality of the graph embedding. Let $L$ be the Laplacian matrix with unbalanced triangles and $\lambda_i$ its eigenvalues. After eliminating unbalanced triangles, the Laplacian matrix and eigenvalues become $L'$ and $\lambda'_i$, with $\Delta L$ representing the matrix perturbation. The corresponding change in eigenvalues can be expressed as

$\Delta\lambda_i=\lambda_i^{'}-\lambda_i=\mathbf{v}_i^T\Delta L\mathbf{v}_i,$

Where $v_i$ the eigenvector of $L$, $Z$ the original embedding vector, and $Z'$ the embedding vector after eliminating unbalanced triangles. Removing unbalanced triangles reduces the absolute values of the Laplacian matrix's non-diagonal elements, decreasing the perturbation matrix $\Delta L$. Consequently, the change in eigenvalues $\lambda_i$ decreases, leading to $\mathrm{Var}(\lambda) > \mathrm{Var}(\lambda')$. By Spectral Graph Theory, this implies $\mathrm{Var}(Z) > \mathrm{Var}(Z')$.

Let $H$ be the original embedding space and $H^{'}$ be the embedding space after variance reduction. Since the variance of the embedding vectors becomes smaller, the distribution range of the embedding vectors becomes smaller. We have:$\|\|\mathbf{Z}_i-\bar{\mathbf{Z}}\|\|^2>\|\|\mathbf{Z}_i^{'}-\bar{\mathbf{Z}}^{'}\|\|^2.$

Thus, coverage number $N(\epsilon,\mathrm{H}^{\prime},\|\cdot\|)$ will be less than coverage number $N(\epsilon,\mathcal{H},\|\cdot\|)$ for the same $\epsilon$.

In particular, the covering number can be used to define an upper bound on Rademacher complexity [15]. $H$ is the hypothesis space, $N(\epsilon,\mathcal{H},\|\|\cdot\|\|)$ is the number of covers, and Rademacher complexity $R_n(H)$ can be defined by the following inequality:

$\mathrm{R}_n(\mathrm{H})\leq2\epsilon+3\sqrt{\frac{\log N(\epsilon,\mathrm{H},\|\|\cdot\|\|)}n}.$

We've got $\log N(\epsilon,\mathrm{H}^{'},\|\|\cdot\|\|)<\log N(\epsilon,\mathrm{H},\\||\cdot\|\|).$

Thus we finally show that SGA can be useful in improving the generalization performance by decreasing the number of coverages in the embedding space while increasing the number of samples, which ultimately shrinks the upper bound of $R_n(H)$.

For Weakness 1 on other augmentation methods:

Thank you for the reviewers' suggestions. We carefully reviewed the recommended papers [1-4]. Although the data augmentation methods discussed in those articles are not specifically designed for the link sign prediction task, their underlying concepts have been highly inspiring for our work. We will include a discussion of the aforementioned methods in the Related Work section of the final version. We selected one method each from the mixup-based methods and spectrum-based methods as augmentation techniques, namely S-Mixup [2] and DP-noise [4], to be applied in link sign prediction on Bitcoin-otc dataset.

Based on the experimental results, S-Mixup did not effectively enhance the baseline, because the fusion operation of the S-Mixup at the feature level loses the structural information of the graph. However, DP-noise demonstrated effectiveness on certain metrics, and we believe that this kind of method of preserving the graph structure is worth further exploring. We will include these experimental results in the final version.

For Weakness 2 and Q2 on parameter number and training time:

1. Model parameter statistics

2. Model training cost time statistics

Bitcoin-alpha:

BitcoinOTC:

3. Complexity analysis please see Common Concern.

Overall, the amount of additional parameters and training time for our method is relatively stable. When the model is large, our method does not bring greater computational complexity. Training can be carried out in a relatively short amount of time.

For Weakness 3 on Figure 3:

Thank you for your suggestion. We have made revisions to Figure 3 and have submitted a revised version, which is included in the uploaded PDF. Due to time constraints, we will continue making further modifications later.

For Q1 on randomly adding edges：

Due to space limitations, we only present the performance of different baselines on the bitcoin-otc dataset with a randomly increased proportion of edges. The performance on other datasets is provided in the uploaded PDF file. Please refer to the uploaded PDF for detailed statistical results across more datasets.

SGCN:

GSGNN:

SiGAT:

Overall, randomly adding edges tends to degrade the model's performance, and the decline is more significant compared to randomly removing edges (refer to Fig.2 in the paper).

(1) For Weakness 1 on some training samples removed :

Our theoretical analysis indeed demonstrates that reducing the number of edges during training can degrade model performance. However, the SGA method does not reduce the overall number of edges. Specifically, we take a cautious approach to edge removal by setting a high threshold (over 0.9, up to 1) before executing any edge removal operation, as detailed in our published code. As a result, the number of edges in the training set actually increases after the data augmentation process. This is corroborated by Table 2, where the graph density is shown to improve following data augmentation.

(2) For Weakness 2 on limitation part:

Regarding the issues raised in the limitations:

Most existing SGNN methods are built on the GCN architecture, and it has been shown [6] that such models struggle to learn appropriate representations from unbalanced cycles. Our data augmentation method relies heavily on these SGNN models to identify suitable potential candidates (i.e., edges). Therefore, designing a signed graph representation framework based on alternative architectures could better address this issue. For example, leveraging large language models (LLMs) could be a promising approach. However, the integration of LLMs with graph structures is still in its early stages, and, to our knowledge, no studies have specifically targeted signed graphs. The reliability of directly applying existing frameworks to this context remains uncertain and requires further validation. Overall, this is a problem worth exploring in greater depth.

(3) For Weakness 3 on typos:

Thank you for the reviewer’s comments. We will correct the typos in the final version of the paper.

(4) For Limitations on influence:

Signed graphs, which assign positive or negative signs to edges, are powerful tools for modeling complex relationships across various fields. They offer valuable insights into social network dynamics, biological and chemical interactions, recommendation systems, and international relations. By capturing both positive and negative interactions, signed graphs facilitate a deeper understanding of intricate systems, providing sophisticated analytical methods to address challenges in multiple disciplines.

(1) For weakness 1 on application scope:

Compared to more generalized graphs, signed graph analysis has its exclusive downstream task (i.e., link sign prediction) which are important and very interesting, such as product reviews [10], bill votes [11], paper reviews, polarization study [14], echo chambers [12]. In addition to social networks, the field of bioinformatics also utilizes this approach, for example, to predict upregulation and downregulation relationships between diseases and genes [13].

(2) For weakness 2 on other graph augmentation methods and limitation issues:

Regarding the current graph data augmentation methods that cannot be directly applied to signed graphs, we primarily discuss this in the 3rd paragraph of the introduction. In summary, it mainly includes two aspects:

1. Most methods are designed for node classification [5], graph classification [1-2], and link prediction tasks, with no existing approaches specifically targeting link sign prediction. Moreover, these methods rely on side information, such as node features and labels, which are often missing in most real-world signed graph datasets that contain only structural information [7-8].

2. Random structural perturbation based augmentation methods [15] cannot improve SGNN performance. We have verified this from both experimental and theoretical perspectives. (see Fig.2 and Sec.4)

Regarding the issues raised in the limitations:

Given that most current SGNN methods are designed based on the GCN architecture, and This paper [6] has demonstrated that current SGNN models based on such architectures are unable to learn suitable representations from unbalanced cycles. Our data augmentation method heavily relies on this kind of SGNN models to mine suitable potential candidates (i.e., edges), so designing a signed graph representation encoding framework based on alternative architectures could better address the current issue. For instance, using large language models to tackle this problem could be a promising approach. However, the integration of large language models with graphs is still relatively limited. According to our research, there is currently no studies specifically targeting signed graphs. Whether it is reliable to directly use some of the existing frameworks also needs further validation. Overall, this is a very worthwhile problem to explore.

(3) For weakness 3 on Experimental Results:

Here are two observations regarding the experimental results:

1. The performance improvement of the methods based on balance theory architectures, namely SGCN [7] and SiGAT [8], is more significant compared to GS-GNN [9]. In other words, the improvements achieved by SGCN and SiGAT are more noticeable, whereas the improvements with GS-GNN are relatively smaller.

2. The overall performance on the first four datasets (Bitcoin-alpha, Bitcoin-otc, Epinion, Slashdot) is better than on the last two datasets (Wiki-elec, Wiki-Rfa).

Regarding Observation 1, from the perspective of method design, the information fusion mechanism of the model itself influences the performance of SGA. We believe the reasons might include two aspects. First, as indicated by the analysis in RSGNN [6], the current SGNN methods based on balanced theory [7] (i.e., SGCN, SiGAT) fail to learn appropriate representations from unbalanced cycles, whereas SGA effectively reduces the proportion of unbalanced cycles (see Table 3), leading to better enhancement for these two methods. Second, since GS-GNN [9] is not limited to the balanced theory assumption, it can handle unbalanced cycles well, thus the enhancement effect from SGA is less significant.

Regarding Observation 2, from the perspective of dataset balance, we believe that the performance of SGA is related to the balance of the dataset. As shown in Table 3, the initial balance degree (BD %) of the first four datasets is better than that of the last two datasets. Considering that we use SGCN as the link sign prediction model to identify potential candidates, its prediction performance is poorer for datasets with low balance degree. As evidenced in Table 1, this conclusion holds true. Therefore, for datasets with low balance, it is more challenging to identify suitable potential candidates, leading to a decrease in the overall data augmentation effectiveness.

(4) For weakness 4 on typos:

Thank you for the reviewer’s comments. We will carefully review the paper and correct typos in the final version.