A Signed Graph Approach to Understanding and Mitigating Oversmoothing

We thank the reviewer for taking the time to review our paper and providing constructive feedback. In what follows, we provide detailed responses to the comments raised by the reviewer. For clarity, we use the following notations:

• W – Weakness
• Q - Question

W1 How to apply structural balance to real-world data.

---

Thank you for the question. We address this in Appendix H, where we introduce the Structural Imbalance Degree (SID), as defined in Definition H.1, to quantify structural balance in real-world data. As shown in Table 6, our SBP method consistently achieves lower SID scores compared to other anti-oversmoothing baselines, indicating its effectiveness in enhancing structural balance.

W2 & W4 Lack of metrics for measuring oversmoothing.

---

Thank you for your comment. We also used the Dirichlet energy to measure oversmoothing. Furthermore, in Appendix F, we theoretically demonstrate that structural balance mitigates oversmoothing from the perspective of Dirichlet energy even in the infinite-depth regime, highlighting the robustness of our approach.

W3 SBP is a fixed signed edge construction.

---

Thank you for your insightful comments. We appreciate the suggestion to extend the positive $\alpha$ and negative weights $\beta$ as learnable parameters, and we will consider this for future work. In the current study, we modify the graphs based on prior information to create more structurally balanced graphs, which helps alleviate oversmoothing. Our goal is to demonstrate the effectiveness of our unified signed graph framework. We look forward to exploring learnable parameters in subsequent research.

W5 & W6 Comparison with SOTA/different backbones

---

Thank you for the suggestions! We compare our SBP with the aforementioned methods on the Cora dataset. As shown better, SBP achieves better performance.

We also adapt our SBP method to GAT backbones on the Cora dataset as suggested. As shown in the results below, SBP remains effective with the GAT backbone.

We will add these experiments in the updated manuscript. Thank you for the suggestions!

[1] Gradient Gating for Deep Multi-Rate Learning on Graphs

[2] SIGN: Scalable Inception Graph Neural Networks

[3] Adaptive Universal Generalized PageRank Graph Neural Network

W7 Task diversity

---

Thank you for the comment. We have evaluated our SBP method on the link prediction task, and the results on Cora are shown below. SBP achieves better accuracy, demonstrating its effectiveness beyond node classification.

W8 Scaling to large-sized graphs.

---

Thank you for the comment. We conduct experiments on the ogbn-products dataset, which is comparable in scale to snap-patents and contains even more edges.

The results, presented in Appendix I.4.6 (Table 15), show that our SBP method outperforms the baselines, highlighting its scalability.

---

We appreciate your questions and comments very much. Please let us know for any further questions.

Thank you for taking the time to review our paper and providing constructive feedback. Below, we provide individual responses to your comments and questions. For clarity, we use the following notations:

• W – Weakness
• Q - Question

W4 The analysis of its adaptability to large-scale graphs could be more detailed.

---

We present the detailed formulation and implementation of SBP-v2, which is specifically designed to scale effectively with large graphs. In Appendix I.3 of ogbn-arxiv, SBP achieves a performance score of 69.53 at layer 16, surpassing GCN's score of 59.13. Additionally, in Table 15 of ogbn-products, SBP attains a score of 76.62, outpacing the Baseline BatchNorm's score of 74.93. Appendix I.3 includes key equations and practical considerations for applying SBP-v2 in large-scale settings.

W5 Lack of illustrative diagrams to show the propagation process of SBP.

---

Thank you for your comment. We have included visualizations of node features from layer 0 to 200 in Figures 8 and 9 of Appendix I. These figures demonstrate that the node features induced by baseline SGC converge to the same clusters as the layer increases, while our SBP's node features converge to distinct clusters even under layer 200. We will add more illustrations in the revision to enhance the explanation of our SBP evolution.

W6 The discussion on the applicability of the method to different types of graphs (homogeneous and heterogeneous graphs) could be more in-depth.

---

That is a good question. Our SBP can be tailored to the hyperparameters based on the homophily level. In Table 12 on the heterogeneous graph Cornell, we enlarge the negative weight $\beta$ of SBP, and it performs even better than the small ones. Follow your suggestions, we in-depth scale from 0.1 to 100 the negative weight with the controllable homophily level in Figure 4, and we find that the accuracy increases with beta in heterogeneous graphs and decreases in homogeneous graphs. These results further highlight the role of $\beta$ as a repulsive force in the message-passing process, supporting our signed graph perspective for understanding and mitigating oversmoothing. We have included the detailed discussion in the revision.

Q1 Can SBP be further optimized to adapt to more complex graph structures?

---

Our SBP can be adapted to arbitrary graph structures, provided that informative node features or node labels are available to construct a structurally balanced framework during propagation. However, if the node labels contain significant noise or if the node features are unhelpful or harmful, our method may become ineffective. We will add more discussion in the next version.

Q2 Could you provide more details to support the applicability of SBP on large-scale graphs? Distinguish different graph settings.

---

We conducted large-scale experiments on the ogbn-arxiv and ogbn-products datasets, which contain millions of nodes and edges, as summarized as follows.

The results for the ogbn-product dataset are detailed in Appendix I.4.6 (Table 15), while the results for ogbn-arxiv are presented in Table 3. Our SBP method consistently outperforms the baselines, demonstrating its scalability. For clarity, we include Table 15 below:

Homophilic and heterophilic data are classified based on their homophily levels (as defined in Equation H I.1). A high homophily level (>0.7) indicates homophilic data, while a low level (<0.4) indicates heterophilic data. The homophily levels for each dataset are summarized in Table 1. Our findings indicate that SBP performs well across both homophilic and heterophilic datasets.

Q3 Lack of heterogeneous graphs results.

---

Thank you for the comment.

Due to space constraints, we have included the results on heterogeneous graphs in the appendix (Tables 12 and 13), where we evaluate SBP on six additional heterogeneous datasets (Actor, Penny94, Roman-Empire, Tolokers, Questions, and Minesweeper) across 2 to 50 layers. Our SBP achieves results that are on par with, or better than, the baselines.

We will clarify this placement in the revision.

Q4 The experiments lack a detailed description of $F_C(Z)$

---

Thank you for the comment.

• Theoretical: As discussed in lines 178–180, $F_C(Z)$ refers to any function that ensures boundedness and prevents divergence in node features.
• Experimental: As noted in line 224, we implement $F_C(Z)$ using layer normalization.

We will clarify this more explicitly in the revision.

---

We appreciate your questions and comments very much. Please let us know for any further questions.

We appreciate that you found our theory clear and our experiments comprehensive. We value the opportunity to address your concerns and provide clarification in this rebuttal. Please find our detailed responses to your specific questions below. For clarity, we use the following notations:

• W – Weakness
• Q - Question

W1 The theorem relies on assumptions such as linear propagation, complete graphs, or bipartite clustering, which still have a gap from real sparse graphs.

---

We understand that you have concerns about the generality of the analysis, but in fact, our analysis can be easily extended to broader scenarios that align with practice:

• Linear propagation: Our current linear activation ($\sigma(x) = x$) is generalized to a bounded activation $f(Z)_c$ as described in Theorem 4.2. It could be further extended to the monotonically increasing activation function.

• Complete graphs: The purpose of having $\mathcal{G}$ as a complete graph is to ensure connectivity. This requirement can be relaxed to the number of connected components $k(\mathcal{G}^+) > 2$, with $\mathcal{G}^-$ containing at least one negative edge, generalized to the graph consisting of multiple disjoint subsets, thus capturing a wider variety of scenarios. This modification satisfies the constraints of Lemma D.3 and supports the proof of Theorem 4.2 in Appendix D.

• Bipartite clustering: We have expanded our approach to multiple clusters, namely weakly structual balance, in Remark 4.3, see detailed theorems and proofs in Appendix G.

We will add the discussion about the assumptions in the revision.

W2 Performance is sensitive to negative weight $\beta$, lacking an automatic or adaptive adjustment mechanism.

---

In our experiments, we empirically observe that setting $\beta = 0.9$ consistently yields strong performance across both homogeneous and heterogeneous graphs, making it a reasonable default choice.

Moreover, we provide a detailed sensitivity analysis of $\beta$ in Section 5.3. Specifically, we vary $\beta$ from 0.1 to 100 and observe consistent trends: for heterogeneous graphs, a larger $\beta$ (e.g., 10) improves performance, whereas for homogeneous graphs, a smaller $\beta$ (e.g., 0.1) is more effective (see lines 303–313). This analysis highlights the impact of $\beta$ and can guide practitioners in selecting appropriate values depending on the graph type.

W3 SBP results in significant memory consumption for large graphs.

---

We understand that you are worried about the memory consumption of our SBP. To make it scalable, we have improved the next version (v2) of our Label/Feature-SBP. Among them, Label-SBP-v2 is very scalable (even enhances the sparsity of the natural graph structure) and performs well, as shown in Table 3, particularly at deeper layers (16), addressing the memory issues.

W4 Insufficient comparison with the latest methods.

---

Thank you for your comment. In response to your suggestion, we have compared our method to the latest baselines graff[1] and g2[2] recommended by Reviewer WoFN and mzv3 on Cora. Our SBP demonstrates higher accuracy than these baselines.

Nevertheless, we would like to emphasize that our work is not solely focused on achieving SOTA performance; its primary contribution lies in the unified theoretical framework we introduce. This framework offers a novel signed perspective that connects and generalizes existing over-smoothing mitigation methods, providing deeper insights into their underlying mechanisms.

[1] Understanding Convolution on Graphs via Energies (TMLR 2023)

[2] Gradient Gating for Deep Multi-Rate Learning on Graphs

---

We appreciate your questions and comments very much. Please let us know for any further questions.

We are very encouraged by your positive assessment of our work. Below we provide detailed answers to your comments and questions. For clarity, we use the following notations:

• W – Weakness
• Q - Question

W1 The hyperparameter $\beta$ is difficult to tune.

---

Thank you for your comment.

In Table 1 settings, $\beta$ was chosen as the best from {$0.1, 0.5, 0.9$}. Our SBP performs best on 7 out of 8 graphs across both homogeneous and heterogeneous graphs. We suggest using 0.9 as the default and trying 0.1 for homogeneous graphs, while a larger value, such as 10, may be more effective for heterogeneous graphs, following our observations of the performance trend relative to $\beta$ in Figure 9.

W2 Would be better to discuss and compare with other methods using signed representations.

---

Thank you for the comment.

We compare our SBP method with the signed representation approaches[1][2] suggested in the review on the Cora dataset. As shown, SBP achieves better accuracy than these baselines.

We will also include a discussion of signed representation methods in the Related Work section of the revised manuscript.

---

[1] Understanding Convolution on Graphs via Energies (TMLR 2023)

[2] Improving Graph Neural Networks with Learnable Propagation Operators (ICML 2023)

W3 References citation in the appendix.

---

Thank you for noting this! We will fix these reference typos in the revision.

Q1 Clarification.

---

By “non-trivial,” we refer to methods whose negative graphs are constructed via deterministic equations. We provide their mathematical formulations in Table 5 and detail the derivation process in Appendix E.

Q2 Clarification.

---

Regarding $A^+ = A$: here, $A^+$ denotes the positive adjacency matrix used in signed graph propagation, while $A$ refers to the original adjacency matrix of the input graph. Although they may coincide in some cases, conceptually they are distinct.

Q3 Label ratio ablation on baselines.

---

Thank you for the question.

We conducted a label ratio ablation study for the baselines on the 2-CSBM dataset. As expected, baseline performance improves with increasing label ratio; nevertheless, our SBP consistently outperforms them across all settings.

Q4 Feature-SBP-v2 on ogbn-arxiv.

---

Thank you for the question. Here are the Feature-SBP-v2 results on ogbn-arxiv. While it outperforms the vanilla GCN, it underperforms compared to the normalization-based baselines and its label-based counterpart, Label‑SBP‑v2.

Q5 Ablation on residual parameters.

---

Thank you for the question. We present ablation results on the residual parameter $\lambda$ for the CSBM dataset, varying it over {0.1, 0.5, 0.9}. We observe that larger values of $\lambda$ lead to better performance.

Q6 Clarification.

---

The notation “#L = 2” in Table 10 is intentional and not a typo; it indicates that the number of layers $L$ is 2.

Q7 Is SBP applicable to other graph tasks, such as link prediction?

---

Thank you for the question.

We have evaluated SBP on the link prediction task, and the results on Cora are provided below. SBP retains high accuracy, demonstrating its applicability beyond node classification.

---

We appreciate your questions and comments very much. Please let us know for any further questions.

Thank you for your reply.

W2 would be better to add the results on the heterophilic dataset

---

Thank you for your comments! Here, we compare SBP and the baselines on the heterophilic Texas dataset. As shown, SBP achieves better accuracy than these baselines.

We will also include these discussions in the Related Work section and the experiments in the revised manuscript.

Q2 Further clarification and deep analysis of $A^+=A$

---

Thank you for your question regarding further clarification and analysis of $A^+ = A$.

Is $A^+ = A$ necessary?

$A^+ = A$ is not necessary. In this paper, we summarize nine classic anti-oversmoothing methods (as seen in Table 5) and observe that most of their $A^+$ matrices are either equal to $A$ or are linear combinations of $A$. Following these analyses, in our paper, we set $A^+ = A$ of our SBP and designed the negative adjacency matrix $A^-$ accordingly, to enhance the overall structurally balanced properties for the signed graph propagation.

The statement on line 135 about beta=0 resulting in the model degenrating into standard unsigned propagation is only true in this case.

We appreciate your observation; Our meaning in the paper is that if $\beta = 0$, there will be no negative edges contributing to the propagation in equation 1, leaving only the positive edges corresponding to attraction, which is indeed similar to the unsigned graph propagation that only considers attraction.

Thank you for your point that if $A^+$ is not equal to $A$, it is not strictly the same. We will clarify this point in our revision; thank you for bringing it to our attention.

If inter-class edges are removed in Label-SBP-v2, is $A^+ \neq A$?

Thank you for the question. Edges are removed through the negative adjacency $A^-$ (see (4)), and the resulting removal inter-class edges are reflected on the overall signed adjacency matrix $A_s$, so $A^+ = A$ still holds in this case.

Why are the $\alpha$ values fixed to 1 and not varied?

Both $\alpha$ and $\beta$ are hyperparameters. For simplicity, we fix $\alpha$ and vary the range of $\beta$ from 0.1-100 (refers to accuracy curves versus $\beta$ in Figure 4) to represent changes in the relative strengths of attraction and repulsion.

Even in the case $A^+ = A$, could it not be possible that the existing graph is not always fully useful [4,5,6] and thus its contribution can be lowered?

We appreciate your insightful suggestion: It is possible that existing graphs may not always be fully useful as suggested by [4, 5, 6], and their contributions can indeed be lower. In this paper, our SBP aims to consider the comprehensive signed adjacency matrix $A_s=\alpha A^+-\beta A^-$, which we assign positive and negative edges, respectively, to mitigate intra-class convergence and thus prevent oversmoothing. The point you mentioned is what we had not previously explored in depth, and we sincerely appreciate your suggestion. We will include a discussion of this aspect of the full use of $A$ in as a potential future direction in our revision.

Thank you once again for your insightful comments.

Q4 Further analysis of Feature-sbp-v2

---

Thank you for your insightful question! Indeed, we found that feature-SBP-v2 is slightly less effective than label-SBP-v2 on large-scale graphs, but not significantly worse. In Table 15, we tested on ogbn-products, and the results are shown below. Notably, feature-SBP-v2 still outperforms vanilla GCN. Therefore, we recommend using label-SBP-v2 for large graphs, as it yields better performance and enhances graph sparsity (Related discussion refers to Appendix I.3).

Q5 Clarification of Ablation on $\lambda$

---

We used a layer count of 200. Below are the results of only using residual connections. We found that the accuracy of the residuals is quite low, indicating that they have already experienced oversmoothing. This suggests that the improvement in accuracy is not due to the residual connections themselves, but rather because of our effective configuration of intra-class positive and inter-class negative edges.

Q6

---

Thank you for pointing it out! We are sorry for the typo when generating the table. The numbers are correct, we will correct the highlight in the revision.

---

We appreciate your questions and comments very much. Please let us know for any further questions or adjustments.