A Signed Graph Approach to Understanding and Mitigating Oversmoothing
Authors: Jiaqi WANG
Xinyi Wu
James Cheng
Yifei Wang
Venue: NeurIPS 2025 poster ()
Keywords: graph neural networks
oversmoothing
structural balance
Primary area: deep_learning
TL;DR: We understand oversmoothing through the lens of signed graphs and propose a plug-and-play method to address it.

Abstract: Deep graph neural networks (GNNs) often suffer from oversmoothing, where node representations become overly homogeneous with increasing depth. While techniques like normalization, residual connections, and edge dropout have been proposed to mitigate oversmoothing, they are typically developed independently, with limited theoretical understanding of their underlying mechanisms. In this work, we present a unified theoretical perspective based on the framework of signed graphs, showing that many existing strategies implicitly introduce negative edges that alter message-passing to resist oversmoothing. However, we show that merely adding negative edges in an unstructured manner is insufficient—the asymptotic behavior of signed propagation depends critically on the strength and organization of positive and negative edges. To address this limitation, we leverage the theory of structural balance, which promotes stable, cluster-preserving dynamics by connecting similar nodes with positive edges and dissimilar ones with negative edges. We propose Structural Balanced Propagation (SBP), a plug-and-play method that assigns signed edges based on either labels or feature similarity to explicitly enhance structural balance in the constructed signed graphs. Experiments on nine benchmarks across both homophilic and heterophilic settings demonstrate that SBP consistently improves classification accuracy and mitigates oversmoothing, even at depths of up to 300 layers. Our results provide a principled explanation for prior oversmoothing remedies and introduce a new direction for signed message-passing design in deep GNNs. Our code is available at https://github.com/kokolerk/sbp.

A Signed Graph Approach to Understanding and Mitigating Oversmoothing
Xinyi 2u The Chinese University of Hong Kong { [jqwang23, jcheng) @cse. cuhk. edu. hk
Jiaqi Wang
James Cheng' MIIT IDSS & LIDS
Yifei Wang
MMIT CSAIL
(xinyiwu, yifei_w) @mit eemit.edu edu
Abstract
Deep graph neural networks (GNNs) often suffer from oversmoothing, where node representations become overly homogeneous with increasing depth. While tech- niques like normalization, residual connections, and edge dropout have been pro- posed mitigate oversmoothing, they typically developed independently. with limited theoretical understanding of their underlying mechanisms. this work, we present unified theoretical perspective based the framework of signed graphs, showing that many existing strategies implicitly introduce negative edges that alter messaag-ppssing to resist oversmoothing. However, show that merely adding negative edges in an unstructured manner is insufficient- asymptotic behavior of signed propagation depends critically on the strength and organization of positive and negative edges. To address this limitation, we leverage the theory of structural balance, which promotes stable, nodes with positive edges and dissimilar ones with negative edges. We propose Structural Balanced Propagation (SBP), plug-and and-play method that assigns signed edges based on either labels or feature similarity to explicitly enhance structural balance in the constructed signed graphs. Experiments on nine benchmarks across both homophilic and heterophilic settings demonstrate that SBP consistently im- proves classification accuracy and mitigates oversmoothing, even at depths of up 300 layers. Our results provide a principled explanation for prior oversmoothing remedies and introduce a new direction for signed message-passing design in deep GNNs, Our code is available at htttt::// //gi thub. com www.oooo///.//ee kom
dynamics by connecting similar
Introduction
Graph neural networks (GNNs) powerful framework for processing graph-structured data from diverse application domains [1 2
6 77 Most GNN models follow the message-passine paradigm, where node representations are computed by recursively aggregating information from neighboring nodes along the edges S 9 1O IT.. Despite their empirical success, deep GNNs often suffer from oversmoothing- the tendeney of node features to become indistinguishable layers increase-leading to performance degradation in deeper models [12
3
5
15).
Numerous techniques have been proposed to mitigate oversmoothing in GNNs, including normal- ization layers 16 17,. residual connections [18 19 20). and random edge dropout (2T 22 While empirically effective, these methods are typically developed independently, with limited theoretical understanding the mechanisms that underlie their success. A common challenge is that many of them introduce architectural modifications that alter the wessage-passing process [23], making difficult to precisely characterize their effects on propagation dynamics and the resulting node
"Equal contribution. 'Correspondigg authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

X1
+
+
(a) Unsigned graph (b) Signed Graph
(c) Structurally balanced graph
(d) Label-SBP
(e) Feature-SBP
Figure 1: Examples of signed graph structures. Blue and orange circles represent nodes from different classes. Solid lines denote real edges, while dashed lines represent edges introduced by SBP. Black and purple lines indicate positive and negative edges, respectively. Let æ; the node features for node i. (a) Initial unsigned graph. (b) Signed graph. (c) Ideal structurally balanced graph. (d)(() Graphs induced by Label-SBP and Feature-SBP, respectively.
representations. Moreover, their ability prevent oversmoothing is often limited, especially in deep GNNs, where they are observed to fail to preserve discriminative node features at extreme propagation depths [6 20 24
In this work, we present a unified theoretical perspective on oversmoothing in GNNs, showing that many existing mitigation techniques can be interpreted implicitly introducing negative edges into the graph used for message- paassgg... We formalize this insight using the framework of signed graphs (25], where edges carry either positive or negative signs (Figure b)). In this view, positive edges promote alignment, while negative edges introduce repulsion, shaping the long-term dynamics further show that simply adding negative edges in an unstructured manner is insufficient, as the asymptotic behavior of signed message- passing depends not only on the presence of negative edges but also on the strength and organization of positive and negative edges. To address this, we turn to the theory of structural balance (26), which characterizes graphs where positive edges connect nodes within clusters and negative edges connect nodes across clusters (Figure cc)) We prove that message- passiing on such graphs yields stable, puuserr-presrviig dynamics, preventing oversmoothing while enhancing class separation.
of node features under signed propagation. However,
Motivated by this theory, we propose Structural Balance Propagation (SBP), a simple, plug-and- play module without introducing learnable parameters for constructing signed graphs that promote structural balance. SBP comes in two variants: (1) Label-SBP, which assigns signs based on ground- truth labels (Figure d)), and (2) Feature-SBP. which estimates signs from feature similarity for label-scarce settings (Figure Ie)). We theoretically show that Label-SBa SBP induces structural balance under mild conditions. Empirically, we evaluate both variants on nine synthetic and real-world benchmarks across homophilic and heterophilic settings. Our results show that SBP consistently improves classification performance and mitigates oversmoothing, validating our theoretical findings. Finally, we analyze the robustness of SBP to design choices, highlighting its adaptability and reliability across diverse GNN settings.
Our main contributions are summarized as follows:
We provide a unified theoretical perspective showing that many oversmoothing mitigation tech- niques such as normalization, residual connections, and edge dropout, can be interpreted as implicitly introducing negative edges into the graph. We formalize this insight through the framework of signed graphs and further show that the asymptotic behavior of signed propagation depends critically on the strength and organization of both positive and negative edges.
We identify structural balance as an ideal condition for resisting oversmoothing, proving that it guarantces stable, class-distinct representations under signed message-passing
Based on this theory, we propose Structural Balanced Propagation (SBP), a simple, plug-and-play method that constructs signed graphs designed to promote structural balance, using either label information (Label-SBP) or feature similarity (Feature-SBi)
Extensive experiments on nine benchmarks demonstrate that SBP consistently improves classifica- tion and mitigates oversmoothing across both homophilic and heterophilic graphs. Our analysis also highlights the method's 's robustness and adaptability to different design choices.

---

2 Related Work
Theory of Oversmoothing. The notion of oversmoothing was first introduced by [2], who observed that node representations tend to converge to common value as GNN depth increases. Subsequent work [13 [3] provided rigorous proofs showing that this convergence occurs at exponential rate for GCNs and attention- based GNNs. [24] further showed that oversmoothing can arise even in shallow networks under specific random graph models. [23] proved that residual connections and normalization layers can mitigate oversmoothing, but they introduce their own limitations by altering the original message-passing process.
Signed Graph-Inspired Methods. Several methods have drawn inspiration from signed graph propagation to handle heterophilic graphs [27 [8 [2]] 30 [3], where vanilla GNNs tend to perform
worse than on homophilic graphs. [29] 30 leveraged negative edges to encode dissimilarity and
introduce repulsion in m passing. 31 made layer aggregation coefficients learnable and observed that negative edges naturally emerge in heterophilic settings. However, [22 showed that oversmoothing still occur in signed propagation under certain random graph models, suggesting that simply adding negative edges is not sufficient to guarantee expressive representations. This highlights broader limitation of existing approaches, which often rely on heuristic designs without a principled understanding of when and why signed message-passing is effective. In this work, we provide a theoretical characterization of how the strength and structure of negative edges influence the asymptotic behavior of node representations, and we propose Structural Balanced Propagation (SBP) to promote stable and discriminative representations on general graphs.
3 How Oversmoothing Happen in GNNs? A Signed Graph Perspective
In this section, we present a generalized messaag-passingg framework based on signed graphs, by incorporating both attractive (positive) and repulsive (negative) interactions. We show that many oversmoothing mitigation techniques can be reinterpreted as implicitly introducing negative edges. However, demonstrate that presence of negative edges is not sufficient- the asymptotic behavior of signed propagation depends critically on the strength of positive and negative edges.
Signed Graphs. We represent unsigned, undirected graph with n nodes by g (A, where A E 10, 1 denotes the adjacency matrix and X E RRnxd is the node feature matrix. For node i E (1,2,.., n). A., = if and only if node i.j are connected by an edge in G and X; E Rd represents the features of node i. We let 11, be the all-one vector of length and D (A1,) be the degree matrix of G.
A signed graph associates each edge with positive or negative sign, capturing the notion of attraction or repulsion between nodes. In this paper, we extend 9 to the signed graph G. = {A+,, AA= XX) where A+ A E {0, 1)axn are the positive and negative adjacency matrices capturing positive and negative edges, with the degree matrix D+ = diag(A 1,,, and D = diag( A 1,,, respectively.
Signed Graph Propagation. Following (25 33), we define the signed propagation which happen over both positive and negative edges with neighboring nodes (25 as
x
a B)x
Σ X
x()
8
Σ x((
(1)
D
D.
JEN!
JEN;
where N and N represent the set of positive and negative neighbors for node i, DJ and DT represent the positive and negative degrees for node i, respectively.
To allow for general formulation, introduce two hyperparameters: a. B O. which control the strength of the propagation over the positive and negative edges, respectively. In particular, when B = 0 and 1, (1) would correspond to the unsigned graph propagation x; D. EjeNt x ((
in vanilla message- passing.
message-pussing.
Prior Methods from the Lens of Signed Graphs. Many previously proposed oversmoothing mitigation techniques can be reinterpreted as special cases of the signed graph propagation in (1) In particular, we observe the following:
Proposition 3.1 Normalization layers, residual connections, and random edge dropout can all be ex- pressed as instances of signed graph propagation in 7 where the vanilla unsigned message-passinn
3

---

is modified by implicitly injecting non-trivial negative edges. A summary of these correspondences is provided in Table in Appendix
To isolate the effect of signed propagation on oversmoothing, we focus our theoretical analysis on the linear setting by removing the activation function and setting (xr) = æt as in prior works [9] 24 In the following theorem, formally characterize how the strength of negative edges governs the long-term behavior of node representations.
Theorem 3.2 Suppose that in signed graph 9s. where A+ represents connected graph and x(k) represents the value of node i after propagation steps under
D Then for any < a <
1/ max4ex D there exists a critical value B, 2 O such that:
(i) B < B., then we have limg-toc X Eド= x) /n for all initial values X x!!:
(ii) i 3 > B.. then lom ||x( for almost all initial values w.E.. Lebesgue measure.
The proof is provided in Appendix C Theorem 3.2 highlights the pivotal role of the negative edge weight 8: it acts repulsive force that counterbalances the homogenizing effect of positive- edge aggregation. When / is small, especially the extreme case where 3 = O, negative edges vanish from the dynamics, and the model degenerates into standard unsigned propagation, leading to inevitable oversmoothing, regardless of the choice of a. Crucially, although increasing /3 can prevent oversmoothing by preserving heterogeneity in node representations, excessively strong repulsion causes the dynamics to become unstable, with representations diverging toward infinity. This tradcoff' poses a challenge: how can we retain the benefits of negative edges to mitigate oversmoothing without destabilizing the model?
To address this, we turn to the theory of structural balance, which characterizes configurations of signed graphs where the tension between positive and negative edges is globally well-structured.
4 Our Proposal: Structural Balance Propagation
In this section, we propose that pessaag--passing over structurally balanced signed graphs exhibit controllable and stable asymptotic behavior, making them theoretically well- rell-suited for mitigating oversmoothing in deep GNNs. Building on this insight, we introduce Structural Balanced Propagation (SBP), simple and effective approach that explicitly promotes structural balance in the constructed signed graph.
4.1 Asymptotic Behavior of Propagation over Structurally Balanced Graphs
In the previous section, demonstrated that oversmoothing arises when the influence of negative edges is insufficient to counteract the homogenizing effect of positive-edge propagation. Conversely, overly strong negative edges lead to divergence and instability. This reveals fundamental tension in signed gressage-passingg to avoid oversmoothing while ensuring stability, the distribution and strength of signed edges must be carefully controlled.
To address this challenge, we turn to a special class of signed graphs known as structurally balanced graphs. These graphs encode an ideal configuration in which positive edges connect nodes within the same cluster, and negative edges span across clusters. Crucially, under signed propagation, such structure leads to stable asymptotic behavior that preserves intra-cluster similarity and inter- cluster distinction- Distinction--prciiseyy the property needed to resist oversmoothing and enhance classification performance in deep GNNs (24). Formally, following 25 26 follows:
we define structural balance as
Definition 4.1 (Structurally Balanced Graph) signed graph G, is called structurally balanced if there is a partition of the node set into V = V1 U V22 with V1 and V2 being nonempty and mutually disjoint, where any edge between the two node subsets V1 and V2 negative, and any edge within each V; is positive.
The structural balance property partitions the graph into two disjoint node sets, Vi and V2, such that positive edges connect nodes within the same group, while negative edges connect nodes

---

Overal
Ovaral
(d) Node representa-
(a) Adjacency matrix in- duced by Label-SBP
(b) Node representa-
(c) Adjacency matrix in- duced by Feature-SBi
tions under Feature- SBP
tions under Label-SBP
Figure 2: The visualization the signed adjacency matrix A A induced by SBP and resulting node representations on 2-CSBM under Layer= 300. (a)(c): The X-axis and Y-axis denote the nodes 0-99, where 0-49 is from class 0 and 50-99 is from class 1. (b)(d): The t-SNE visualization of the node representations learned by SBP.
across groups, as illustrated in Figure (c). This organization of edge signs induces well cell-structured propagation dynamics. We characterize the asymptotic behavior of signed message-passe passing on structurally balanced graphs as follows:
Theorem 4.2 Assume that node is connected to node j and x!!)) represents the value of node i after i propagation steps in 1 F(z), is a bounded function such that: if < -c, F(2). C; > c, F(z)c = c; -c z C, F(2)c 2. Let
if the edge {i,j} positive and 0
if the edge [i.j] is negative. Consider the constrained signed propagation update:
x(x+t) = Fo((1 0) 0)x!*) +
)x
Let a E (0,1/2). Assume that Ge is a structurally balanced complete graph under the partition V = Vi U V2. When is sufficiently large, we have that
P lim x (K) = c Vi; lim x. -c,i Vo) = 1.
(3)
The proof is provided Appendix The result above shows that if the graph is structurally balanced and the signed graph propagation is constrained with bounded function F.,, node features converge asymptotically to group-specific values under the propagation rule defined in (I). Moreover, nodes belonging to different groups are repelled from one another, resulting in asymptotically distinct representations across groups. This behavior implies that structurally balanced graphs provide provable mechanism for mitigating oversmoothing, by assigning positive and negative edge signs in accordance with the underlying class structure encouraging intra-class consistency while maintaining inter-class separation.
Remark 4.3 The two-group result above can be generalized to multiple groups by introducing more general notion known as weak structural balance. See detailed discussion in Appendix G
4.2 Method: Design Structural Balance Propagation for GNNs
Building on the theoretical insights from the previous section, we propose Structural Balance Propagation (SBP), principled approach for promoting structural balance in the message-passing process of GNNs. Specifically, we introduce two variants: Label-SBP and Feature-SBI. which inject signed edges that approximate structurally balanced configurations using label supervision and feature similarity, respectively.
Label Induced Structural Balance Propagation (Label-SBP), We extend the original adjacency matrix to the positive and negative ones. Let the positive adjacency matrix be the original adjacency matrix A+ = A. we then construct a label-informed negative adjacency matrix A,- designed to introduce repulsion between classes and promote attraction within classes. Specifically, for node pairs with known labels, we assign a value of 1 if the labels differ (to repel), - 1 if the labels match (to attract), and otherwise to preserve the original structure when labels are unknown. Formally:
if y + Uj
(A, Dgp
if v U₁ otherwise.
(4)
5

---

where yi is the ground truth label for node i. We theoretically show that Label-SBP induces structurally balanced graph under mild conditions (see formal statement and proof in Appendix [H)
Theorem 4,4 (Informal) Assume class labels are balanced, and let denote the ratio of labeled nodes. As p increases, the degree of structural balance improves, and the graph becomes fully structurally balanced when p 1.
Figure 2a shows the signed adjacency matrix A+ - A, constructed by Label-SBP on the the Contextual Stochastic Block Model with two blocks (2-CSBM) [34,, highlighting its structural balance: positive edges appear within label blocks, and negative edges span between them. Figure 2b visualizes the learned node representations, demonstrating that Label-SBP achieves clear class separation even at depth L = 300, attaining a high classification accuracy of 97.50%, which is consistent with Theorem 4.2
Furthermore, to tackle scenarios where labels are scarce, we propose a variant of SBP that estimates the negative adjacency matrix based on feature similarities.
Feature Induced Structural Balance Propagation (Feature-SBP). We retain the positive adjacency matrix in Feature-SBP as in Label-SBP, setting.A+ = A. To construct the negative adjacency matrix Ay. We leverage feature similarity assign positive and negative Snges--proootin attraction between similar nodes and introducing repulsion between dissimilar ones-without relying on labels. Specifically, we define:
A = (x -x (
(5)
where (0) denotes the initial node features. While this approach may be less precise than Label-SBP due to the absence of label supervision, it leverages the full feature set, including test nodes, to improve the overall alignment with structural balance across the graph.
Figure and 2d illustrate the signed adjacency matrix A+ A A7 and learned node representations on the 2-CSBM data. Notably, Feature-SBP preserves structural balance patterns similar to Label-SBP and achieves strong classification performance with an accuracy of 80.00%.
Implementation Details. We implement the constrained function Fe in Theorem 4.2 by Layer- Norm (35] To avoid numerical instability for repeated message-passing, we ensure that the sum of the coefficients combining the node representations ( and the node representations updates by our SBP remains 1. We employ a row-stochastic adjacency matrix A as the positive adjacency matrix, denoted Á+. Additionally, we apply the softmax function to the negative matrix, resulting in Ā softmax A As result, Label/Feeture-SBP can be written as:
((++1) (1 (x) X a ( - 3A -A- x
where X <, 8 are the hyperparameters controlling the strength of positive and negative edges.
Scalability on Large-Scale Graphs. Although SBP improves the structural balance property for message-passing in GNNs, it may reduce graph sparsity and cause out-of-memory issues on large- scale graphs. To adapt SBP in large-scale graphs, we propose Label-SBP-v,, which removes only inter-class edges instead of explicitly adding negative ones. This preserves sparsity by avoiding the addition of new edges, thereby reducing computational overhead while still encouraging structural balance.
For Feature-SBP, the original negative adjacency matrix has quadratic complexity (n?dd), which is prohibitive for large n. To improve efficiency, we replace the node-level similarity matrix -XXT T e Rax* with its transposed form - X X E Raxd, following [16]. This shifts repulsion to the feature dimension and reduces complexity O(nd)), which is significantly more scalable when n > d. More detailed analysis is provided in Appendix I.3
Experiments
In this section, conduct comprehensive evaluation of SBP various benchmark datasets, including both homophilic and heterophilic graphs. We aim to answer the following three key research questions:

---

Table 2: Node classification accuracy using standard-depth GNNs (%). Best results are highlighted in blue; second-hest results shown in gray. Overall, SBP performs best on hoth homophilic and heterophilic datasets.
II(G) D.81 Com
0:74 Citeseer
0.80
0.22
0.58
0.21 Texas
0.11 Wisconsin
0.30 Cornell
Datnset
PubMed
Squirre
Amazon-ratings
MLP
48.82 1: 0.98
47.89 1 1.21
69.20 0.83
32.58
0.19
38.14 1: 0.03
73.51 a 2.36
70.98 L18
68.11 4 2.65
SGC
80.21 1: 0.07
71.88 1: 0.27
76.99
0.38
43,30 2 0.30
42,83 0.04
45,95 1: 0.00
47.06
0.00
48.11 3.15
BatchNorm
77.90 1: 0.00
60.85 1: 0.09
72.15
4: 0.09
44,22 0.11
39.68
0.01
39.73 4: 1.24
52.94
0,00
46.49 +: 1.08
PairNorm
80.30 + 0.05
70.83 + 0.06
77.69
0.26
46.21
42.30 + 0.05
51.35 0.00
58,82
0.00
0.00
ContraNorm
81.60 + 0.00
72.25 +: 0:08
79.30
= 0.10
48.63 = 0.16
42.98 +: 0.04
48.38 = 4.43
1,53 49.61
48.63 # 0.16
DrapEide
+ 2.76
65.63 + 1.76
59.46 +
52.55
45.95
7.05
Residual
77.81 +: 0.03
71.61 +: 0.17
77.40 ::400::00 0.06
43.63 =: 0.34
42.69 + 0.03
66,95 +: 1.32
63.73
0.98
61.89 +:999:35 3.91
APPNP
77.78 + 0.93
1,31
74.52
0.17
0.03
4.37
65.10
JKNET
78.20 1: 0.20
66.80
1: 0.33
75.62
0.3 0.37
48.16
0.25
42.21
+: 0.05
60.00 :: 2.36
42.55
1: 2.92
39.73
2.72
DAGINN
65.98 1.49
60.04 1,98
72.39
0.90
33.39
0.19
40.61
0.03
61.35 1.73
57.45
44.87
3.34
Feature-SBP
82.46 1. 0.07
70.63 1. 0.52
77.41 1: 0.21
49.16
1 0.19
42.31 1: 0.03
78.38 1: 0.00
80.39
1 0.00
72.97
0.00
LBP
82,90 +: 0.00
73:04 +: 0.10
80.32
0.04
45.60
0.11
42.41 +: 0.02
78.38
0.00
80.39
0.00
70.27
0.00
RQ1 How does SBP perform in node classification tasks using standard-depth GNNs?
RQ2 How effectively does SBP mitigate oversmoothing in deep layers?
RQ3 How sensitive, robust, and scalable is SBP to different hyperparameters, model backbones, and graph homophily levels?
Datasets. We use nine widely-used node classifi- cation benchmark datasets (Table (7), where four of them are heterophilic (Texas, Wisconsin, Cornell, Squirrel, and Amazon--ating (36)), and the remain- ing four are homophilic (Cora [37], Citeseer (38). and PubMed [39]), including one large-scale dataset (ogbn-arxiv (4)).. Details of these datasets, including their homophily levels, are summarized in Table We also experiment on the Contextual Stochastic Block Model (CSBM) (34] to show the performance of SBP on different homophily levels with detailed settings in Appendix [.]
Table I: Summary of datasets. HG) denotes the edge homophily level, with higher values indicat- ing more homophilic graphs
Dataset
H(G)
Classes
Nodes
Edges
Cora
0.81
7
2,708
5,429
Citeseer
0.74
6
3,327
4,732
PubMed
19,717
44,338
Texas
0.21
5
183
205
Cornell
0.30
280
Amazon-ratings
0.38
5
24,492
93,050
Wisconsin
0.11
5
251
466
Squirrel
0.22
4
198.493
2,089
ogbn-arxiv
0.65
40
16,9343
1,166,243
Baselines and Experiment Settings. We implement SBP along with the following 10 baselines, all using
the Simplified Graph Convolution Network (SGC) as the backbone GNN to ensure a fair compar- ison. 1) Classic models: MLP, vanilla SGC 19. 2) Normalization methods: BatchNorm [41],
PairNorm 177 and ContraNorm [16. 3) Edge dropping methods: DropEdge (2). 4) Residual
connections: Residual, APPNP 42). JKNET [18] and DAGNN [19]
All methods are trained using the same setting, following 43). For SBP, we select the optimal value of À from the set 10. 0.5, 0.9), fix = 1, and then choose the best value for 3 from 10. 0.5, 0.9). Ablation studies on the influence of hyperaarameters and the effectiveness of SBP with other GNN backbones can be found in Section 5.3
5.1 RQ1: Node Classification Performance Using Standard-Deptt GNNs
To evaluate the effectiveness of SBP under typical GNN settings, we assess its performance on node classification tasks using standard-depth models. Table T reports the mean node classification accuracy and standard deviation across 10 random seeds, using a 2-layer SGC backbone 44]. The results show that SBP improves node classification performance in standard-depth GNNs, yielding an average gain of 3 percentage points on homophilic graphs and 5 points on heterophilic graphs Overall, SBP achieves superior performance across datasets, with I Label/Feature- SBP attaining the highest accuracy on 7 datasets.
7

---

BatchWom
...
Contralom
Teature SBP
Latel5BP
10
130
100
100
80
(a) Oversmoothing analysis.
(b) Label ratio analysis.
Figure 3: Model performance under varying number of layers. SBP remains effective up to 300 layers, while normalization methods degrade with depth due to oversmoothing. The X-axis denotes number of layers and the Y-axis denotes accuracy. (b) Sensitivity of Label-SBP to training label ratio. Lahel-SBP's performance improves with increasing label ratio, aligning with our theory. The X-axis denotes training label ratio and the Y-axis denotes accuracy.
LBP
Fenture-S00 SSP
100
100
100
100
Acturayy
60
49
0.1
0.1
5 10
10
50
100
50
100
(a)p
0.75 H(G) 0073
(b)ø
0.25 H(G) 0.328
(c)6 0.25
H(G) 0.673
(d) 0.75 (G)) 0.928
Figure 4: Impact negative edge strength SBP under different homophily levels CSBM. e controls the homophily level (G). The X-axis denotes 3 and Y-axis denotes accuracy. Homophilic graphs favor smaller 3, while heterophilic graphs benefit from larger values.
5.2 RQ2: Anti-Oversmoothing Analysis
We further evaluate SBP's ability to counter oversmoothing in deep GNNs by varying the number of layers K. Figure B(a) compares Label-/Fcature-SB against BatchNorm and PairNorm on both homophilic (Cora, Citeseer) and heterophilic (Cornell) benchmarks. For homophilic graphs, we test K (2, 10, 50, 100, 300}, and for the heterophilic graph, K {2, 10, 20, 503.
Notably, SBP maintains strong performance even at 300 layers, effectively mitigating oversmoothing in deep GNNs. In contrast, normalization- based methods exhibit substantial performance degradation as depth increases, reaffirming their vulnerability to oversmoothing
[23]. Interestingly, we also observe that to maintain performance on heterophilic datasets, SBP requires larger repulsion strength 3 than typical settings (e.g., 3 E (0.1, 0.5, 0.9)). As shown Table [2] setting / > enables SBP sustain approximately 60% accuracy in deep-layer regimes on the Cornell dataset.
5.3
RQ3: Robustness, Sensitivity, and Scalability of SBP
Sensitivity of Label-SBP to Training Label Ratio. Since Label-SBP relies on ground-truth labels to construct the negative graph, conduct ablation study examine its sensitivity the proportion of labeled training data. As shown in Figure Bb), Label-SBP's performance on the CSBM and Cora datasets improves with increasing label ratio when using 2-layer SGC backbone. This aligns with our theoretical result that greater label availability leads to better structural balance in the signed graph, enhancing classification performance.
Nonetheless, even with a modest training ratio of 20%, Label-SBP achieves over 80% accuracy, while models trained with 80% labels approach 100% accuracy. Furthermore, shown in Table 2 Label- SBP outperforms existing methods even under the default training splits of standard benchmarks, highlighting its robustness and practical effectiveness in real-world graph settings.
Analysis of Negative Edge Strength Under Different Homophilic and Heterophilic Levels. In order to evaluate the performance of SBP on graphs with arbitrary levels of homophily, we conduct an ablation study in the CSBM setting with controllable homophilic and heterophilic levels, following the setup from (31. We examine wide range of 3 values, while keeping À 0.5, 1 and using a hyperparameter CSBM, & to control the homophily level. The graph homophily measured by H (G).

---

Label-07
Table 3: Node classification accuracy (%) on the larg--ccale dataset ogbn-arxiv. Best results highlighted in blue.
Rourany
Model
#L-2
#L-4
*L-8
#L-16
65.54
59.13
BarchNorm
20.14 1. 0.28
70.93 +: 0.15
70.14
= 0.43
63.24 2: 1.40
PaisNorm
70.48 + 0.20
71.59 + 0.17
71.24
- 607
68.92 +04
ContraNarm
OOM
OOM
00M
00M
Figure 5: Impact of negative edge strength 3 in SBP
DrapEdge
0.27
044
on real graphs. The X-axis denotes & and the Y-axis denotes accuracy.
Residual
66 66.90.
1 0.14
66.67 1 0.25
61.76
1 0.62
53.25 0.755
Label-SBPw22
70.55
71.54 a 0.18
71,07 0:288
69.33
Table Performance SBP with different GNN backbones. Best results are highlighted in blue.
0.25
nagod
=2
=
#1=8
#L=16
0.351
30.95 10.00
+Feature-SBP
80:44 10.83
79. 26
11.18
78.56
10.59
71.22
10.55
Corn
SBP
GCNII
78.58
80.31
0.00
77.76 0.24
79.
73.47
79:50
+0:00
3.82
78.12
71.43
1.32
+Label-SaP
78.74
1.54
78.87 0.00
79.14
1: 0.35
79.17
1: 0.41
0.55
FEature-SBP
77,95 = 0.91
78.82 0.00
78.11
= 1.62
78.82
0.29
GCN
67.45 10.51
65.62 10.25
37.22
12:46
22.03
1:476
Num
Feature-SBP
67.38 10.68
66.94 10.00
66.29 1..00
65.35 11.99
Ciesser
+Label-SSH SBP
67.23 +0.64
66.72 +0.00
66.29
+0.80
65:50 #2.13
Figure 6: Real runtime (in scconds) of various methods.
0.64
-Label-SSP
65.31 0.63
63.93 3.66
68.33 1: 0.99
66.46 1: 0.00
SFeatureSBBP
Figure 4 shows the performance of Feature/Label-SBP across different / values. In Figures a) and (b), where Φ < indicates heterophilic graphs, increasing significantly improves performance. Conversely. in Figures[4cr and (d), where ø >> 0 corresponds to homophilic graphs, performance deteriorates as increases. We observe similar trends on real-world homophilic and heterophilic graph datasets, shown in Figure 5 These results further highlight the role of 3 as repulsive force in the cessage-passsing process, supporting our signed graph perspective for understanding and mitigating oversmoothing.
Performance on Large-Scale Dataset. To preserve graph sparsity and reduce computational overhead, we adopt SBP variants designed for large-scale graphs, as detailed in Section 4 Results on the ogbn-arxiv dataset are shown in Table 3 Overall, Label-SBP-v2 matches or outperforms existing normalization methods, particularly in the deep setting L 16. These results demonstrate the empirical robustness and scalability of SBP-v2, which effectively leverages label information to mitigate oversmoothing even at large scale.
SBP with Different GNN Backhones. Beyond the SGC backbone, SBP can be seamlessly integrated into other GNN architectures, consistently yielding performance gains. Table the results for SBP applied to GCN and GCNII across various model depths. SBP improves GCN performance by up to 47 points, particularly at depth L = 16, and also boosts the performance of GCNII, a state-of-the-an model explicitly designed address oversmoothing. These results further support our insight that promoting structural balance is an effective strategy for mitigating oversmoothing in deep GNNs.
Time Efficiency of SBP. SBP is highly efficient, adding only minimal overhead compared to vanilla backbones. Figure 6 reports the actual runtime of various methods integrated with SGC CSBM. Feature-SBP is the fastest among all methods, while Lahel-SBP ranks third-slightly slower than DAGNN but still more efficient than the normalization- approaches. Additional analysis of SBP's runtime on large-scale graphs is provided Appendix [.4.6
6 Conclusion
In this work, we present a unified signed graph perspective on oversmoothing in GNNs, identifying structural balance as an ideal condition for preserving expressive node representations. Building on this insight, we propose Structural Balanced Propagation (SBP), simple and plug-and-play method that constructs signed graphs to promote structural balance and mitigate oversmoothing. Extensive experiments demonstrate SBP's robustness, scalability, and consistent performance gains

---

across diverse settings. Beyond practical improvements, our work provides theoretical foundation for understanding message-passing dynamics beyond vanilla GNNs and opens new directions for principled signed message-passingg design.
References
[1] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IJCNN, 2005.
[2] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2009.
[3] Joan Bruna, Wojeiech Zaremba, Arthur D. Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
[4] David Kristjanson Duvenaud, Dougal Maclaurin, Jorge Bombarelli, Timothy D. Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. In NewrlPS, 2015.
Rafael Gómez-
[5] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. NeurlPS, 2016.
[6] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and koray kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NeurIPS, 2016.
[7] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In ICLR, 2016.
[8] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[9] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In ICML, 2019.
[10] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[11] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[12] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
[13] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
[14] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. In ICML. Graph Representation Learning and Beyond (GRL+) Workshop, 2020.
[15] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention-based graph neural networks. In NeurlPS, 2023.
[16] Xiaojun Guo, Yifei Wang, Tianqi Du, and Yisen Wang. ContraNorm: A contrastive learning perspective on oversmoothing and beyond. In ICLR, 2023.
[17] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in gnns. ArXiv, 2019.
[18] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICLR, 2018
[19] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 2020.
10

---

[20] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.
[21] Taoran Fang, Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. Dropmes- sage: Unifying random dropping for graph neural networks. In AAAI Conference Artificial Intelligence, 2022.
[22] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. ArXiv, 2019.
[23] Michael Scholkemper, Xinyi Wu, Ali Jadbabaie, and Michael T.. Schaub. Residual connections and normalization can provably prevent oversmoothing in gnns. In NeurlPS, 2025.
[24] Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. In ICLR, 2023.
[25] Guodong Shi, Claudio Altafini, and John S Baras. Dynamics over signed networks. SIAM Review, 2019.
[26] Dorwin Cartwright and Frank Harary. Structural balance: generalization of heider's theory. Psychological review, 1956.
[27] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. Journal of Machine Learning Research, 2023.
[28] Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. Ordered gnn: Ordering message passing to deal with heterophily and over-smoothing. arXiv preprint arXiv:2302.01524, 2023.
[29] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In ICDM, 2022.
[30] Yuelin Wang, Kai Yi, Xinliang Liu, Yu Guang Wang, and Shi Jin. ACMP: Allen-cahn message passing with attractive and repulsive forces for graph neural networks. In ICLR, 2022.
[31] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
[32] Langzhang Liang, Sunwoo Kim, Kijung Shin, Zenglin Xu, Shirui Pan, and Yuan Qi. Sign is not remedy: Mulliist-to-muliieett message passing for learning on heterophilic graphs. arXiv preprint arXiv:2405.20653 2024.
[33] Tyler Derr, Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In ICDM, 2018.
[34] Yash Deshpande, Andrea Montanari, Elchanan Mossel, and Subhabrata Sen. Contextual stochastic block models. NeurlPS, 2018.
[35] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. ArXiv, 2016.
[36] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302. 11640, 2023.
[37] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000.
[38] C Lee Giles, Kurt D Bollacker, and Steve Lawrence. CiteSeer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, 1998.
[39] Kathi Canese and Sarah Weis. PubMed: the bibliographic database. The NCBI handbook, 2013.
[40] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint axXiv:2005.00688 2020.

---

[41] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML. 2015.
[42] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. ArXiv, 2018.
[43] Yifei Wang, Qi Zhang, Tianqi Du, Jiansheng Yang, Zhouchen Lin, and Yisen Wang. A message passing perspective on learning dynamics of contrastive learning. In ICLR, 2022.
[44] Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process linear graph convolutional networks. In NeurIPS, 2021.
[45] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020.
[46] Moshe Eliasof, Lars Ruthotto, and Eran Treister. Improving graph neural networks with learnable propagation operators. International Conference on Machine Learning, 2022.
[47] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiaoming Chang, and Doina Precup. Revisiting heterophily for graph neural networks. ArXiv, 2022.
[48] Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. In Neural Information Processing Systems, 2021.
[49] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. survey on oversmoothing in graph neural networks. ArXiv, 2023.
12

---

Appendix
Contents
Limitations
14
Background on GNNs
14
B.1
Graph Convolution Networks
14
B.2
Simplified Graph Convolution Networks
14
B.3 Signed Graph Propagation
14
Proof of Theorem 3.2
15
D Proof of Theorem 4.2
16
A Signed Graph Perspective on Existing Oversmoothing Countermeasures
17
Normalizations
18
E.2 Dropping
20
Residual Connections
20
F
Oversmoothing Metrics
21
Weakly Structural Balance
22
H
Statement and Proof of Label-SBP
22
Details of Experiments
24
Details of the Dataset
24
1.2
Experiments Setup
25
1.3
Time Complexity Analysis and the Modified SBP
................................
25
1.4
Results Analysis
26
1.4.1
CSBM results
26
GCN Results
................................
26
1.4.3
3 Analysis on Heterophilic Datasets
27
SBP more benchmarks
27
1.4.5
Different Backbones
28
.4.6
SBP on Large-scale graphs
28
4.7
Further Optimization
28
13

---

A Limitations
This work evaluates wide range of GNNs. However, due to the diversity GNN methods, is impractical to assess all of them. Therefore, the proposed method focuses on classic techniques that utilize normalization, dropout, and residual connections. Moreover, due to limited computational resources and time, the proposed method has not been evaluated on super-large graphs, such as those with IG nodes. SBP focuses on the oversmoothing problem, which leads degraded performance in GNNs. Other factors that can negatively impact GNN performance are not discussed in this paper.
B Background on GNNs
B.1
Graph Convolution Networks
To deal with non-Euclidean graph data, Graph Convolution Networks (GCNs) are proposed for direct convolution operation over graph, and have drawn interests from various domains. GCN is firstly introduced for spectral perspective [8], but soon it becomes popular as general message-passiieg algorithm in the spatial domain. In the feature transformation stage, GCN adopts a non non-linear activation function (e.g.. ReLU) and layer-specific learnable weight matrix W for transformation. The propagation rule GCN can formulated as follow:
H())
(6)
B.2 Simplified Graph Convolution Networks
Simplified Graph Convolution Networks (SGC (9) simplifies and separates the two stages of GCNs: feature propagation and (non-linear) feature transformation. It finds that utilizing only a simple logistic regression after feature propagation (removing the non-linearities), which makes it linear GCN, can obtain comparable performance to canonical GCNs. The propagation rule of GCN can formulated follow:
(()) = (H( (()) = A A (W)
Moreover, SGC transforms (1)) to general learnable parameter W, so the formula of SGC can be this:
H(m = Ho)
(8)
B.3 Signed Graph Propagation
Classical GNNs 8
primarily focused on message-passe passing on unsigned graphs graphs composed solely positive edges. For example, there exists a edge {i,j} or the sign edge (i,j} is positive, the node x; updates its value by:
9
10 11
i = x; + c( - -x,) = (1 - a.). + oæzj, E (0,1). 1).
(9)
Compared the unsigned graph, signed graph extends the edges either positive or negative. Notably, if the sign of edge {ř,}} is negative, the node update its value using the following expression:
f I; ((z 2x)) = (1+ 9)z; 3r, $ E (0.1).
(10)
In words, the positive interaction equation 9 indicates the attraction while the negative interac- tion equation [0 indicates that the nodes will repel their neighbors.
More generally, when considering of the neighbors of node I,, let N denote the positive neighbor set while N; denote the negative neighbor set, where N N; N and N O n.;: 0. The representation of x; is thus updated by:
f. = a1-a
B)z
Σ E
Σ D JEN,
(11)
IN
N
JENT
In particular, the two parameters a and 3 mark the strength of positive and negative edges, respec- tively.
14

---

For further proof' of the theorems and propositions in the paper, we give more simple and detailed definition in this section.
and D = diag(degī ,.... deg be the degree matrices of the positive subgraph and negative subgraph, respectively. Let Act be the adjaceney matrix of the graph G with [Ac+ly = 1 if {i E Et and [Aa+Iis = 0 otherwise. The adjacency matrix Ag- of the negative subgraph G is defined by [Ag las -1 for {i.j} E E- and [Ac lis 0 for {i,j} $ E-
Let D++ = (iag(deg" .... deg,)
The Laplacian plays central role in the algebraic representation of structural properties of graphs.
In the presence negative edges, more than one definition of Laplacian is possible; see [25]. The Laplacian of the positive subgraph G is L == D Act, while for the negative subgraph
G the following two variants can be used: L. == Dg- - Ag- and lig = -D AG- Consequently, have the following definitions.
Definition Given the signed graph G, its opposing Laplacian defined as
LG == Lo+ LG- = Do+ + Do- - -co+ AG-,
(12)
and its repelling Laplacian is defined as
L LG+ + --- DE+ DG- Act AG-
(13)
Time is slotted at 0, 1, ..... Each node holds state 2f( Ω time and interacts with its neighbors at each time to revise its state. The interaction rule is specified by the sign of the links. Let a,8 2 O. We first focus on a particular link {i.j} E and specify for the moment the dynamics
along this link isolating all other interactions.
The DeGroot Rule:
Iz(l + =1) (1)++ol (()=_(()--200) = (1- at) +)z where -8 E {i.j} \ {8} with a 10
(14)
The Opposing Rule:
z.(1 1) (1) + 81---- (1, (1 -1- 3)x,(() (1);
(15)
or The Repelling Rule:
(1 + 1) = (1( - ((x= - xx.()) = (1+ B),, - 3x (1).
(16)
The Repelling Negative Dynamics:
(t + 1) = (t) a Σ (z)(t) - xx(+)) - 3 Σ (z²(1) xt))))
JEN
JEN;
(17)
= (1 adeg + Bdeg, }x:(1) + Σ at B Σ 2z(t).
JENT
JENT
Denote x(1) = (x1(1) .,, ( We can now rewrite 17 in the compact form
x(t + 1) = Mcx(t) = (1 aLG, - (3x_)x(())
(18)
Here,
I --
abo- - BL6 = - 1-1-Lg L
(19)
with -." = aLg= + BLC being the repelling weighted Laplacian of G. From Equation
18
M9l always holds. We present the following result, which by itself is merely straightforward look into the spectrum of the repelling Laplacian L
C Proof of Theorem 3.2
Now consider the combined theorem.
Theorem C.1 Suppose that the positive edges connected. Then along Equation 17 for any 0 < a < 1/ maxee deg," there exists critical value 3, 2 for 3 such that
(i) B < B., then we have lim, = -+ x (0) nnon/foff for all initial values z(0);
(i) if 3 > B., then lim ||x(t)]| oc for almost all initial values w.r.t. Lebesgue measure.
15

---

Proof. we change the signed graph update to the equivalent version of (t( read as:
ri(t + (1) +
Σ
(z,(1) z.(1)) - Σ (1 =x(1)).
JEN!
JEN;
This can be expressed as:
z(t + 1) = a deg
+Bdeg )x;(t) + Σ
2²(t) - Σ
2z(t).
(20)
JEN+
JEN
Algorithm 20 can be written as:
can
z(t = = MGx(() -
(L))x(1).
(21)
Here, Mg / aL gL.. with Ln a + 3 being the repelling weighted Laplacian
of G. defined in Sec [.3 From Eq.equation 21 Mcl = 1 always holds. We present the following
result, which by itself is merely a straightforward look into the spectrum the repelling Laplacian LG.
So theorem C.1 can be changed the following version:
Suppose G+ is connected. Then along Eq.equation 21 for any 0 < a < 1/ maxiev deg,", there exists critical value 3 for such that:
(i) if B < B., then average consensus is reached in the sense that lime-soo zi(() E (0) for all initial values <0));
(ii) if 3 B., then lim,-+o0 [|a(t)]||
for almost all initial values w.r.t. Lebesgue measure.
Proof. Define J= n,. Fix a E (0, m deg," and consider f(3) Amax (T a BLG - J). and g = Amin (I [ - aL - BLG J). The Sourant-Fischer Theorem implies that both f() and g(.) are continuous and nondecreasing functions over [0, oo). The matrix J always commutes with I- aL .LG. and I is the only nonzero eigenvalue of J. Moreover, the eigenvalue 1 of J shares common eigenvector with the eigenvalue 1 of I aL - BLG.
Since G+ is connected, the second smallest eigenvalue LG+ is positive. Since 0 < a < maxigy deg,"" there holds Amin (I aLG+) 2 -1, again due to the Gershgorin Circle Theorem.
Therefore, ((0) < 1, g(0) 2 -1. Noticing f(o)) = > 1, there exists 8. > 0 satisfying
f(3.) We can then verify the following facts:
There hold ((3) < and g(3) > -1 -1 if < B.. In this case, along Eq.equation 21 lim -J - J)((t) O, which in turn implies that z(t) converges to the eigenspace corresponding to the eigenvalue of Mg. This leads to the average consensus statement in (i).
There holds f(3) 2 1 1f > 8.. In this case, along Eq.equtioon 21 x (t) diverges as long the initial value z0) has nonzero projection the eigenspace corresponding to Amax (Ma) of Mg. This leads to the almost everywhere divergence statement in (ii).
The proof is now complete.
D Proof of Theorem 4.2
Theorem D.1 let A > 0 be a constant and define F(z)e =
[-c, c). and F(z). = 0, > c. Define the function 0 E + R so that 0((i,j)) = a if [i,j} E E+ and 0 ((ti,j)) 3 if [i,j} E E Assume that node interacts with node time and consider the following node interaction under the signed propagation rules:
zt + 1) = =F())(((1 ()x,(() + (t). (i,j)-
(22)
let a E (0,1/2). Assume that is a structurally balanced complete graph under the partition == Vi U V2. When B is sufficiently large, for almost all initial values z00)) w.r.t Lebesgue measure, there exists a binary random variable (x(()) taking values in {-c, c} such that
P
lim (t())) 1(x(0)), E V1; lim 2x(() (xx()))) Vo) =1.
(23)
40000
64000
16

---

Proof.
The proof is based on the following lemmas.
Lemma D.2 Fix a E (0, 1) with a + 2. For the dynamics 22 with the random pair selection process. there exists 8 (ax) > O such thut
(um max (x:(t) x,(() 2A =1 ++000 JEV
for almost all initial beliefs 3 3".
Lemma D.3 Fix (1/2. 1) and 3 2 2/ 1). Consider the dynamics 22 with the random
pair selection process. Let G be the complete graph with k(G*) 2 2. Suppose for time there are d1 V with Es, (t)
and j (t) Then for any E [0, (2a 2)c/ and any i, V,
the following statements hold:
(i) There exist an integer Z(e) and sequence of node pair realizations, Gr+s(w), for 0, .l.....2 Z 1, under which xi, (1+ Z)(w) --A +
(ii) There exist an integer ((c) and sequence of node pair realizations, Ge+s(w), for 0, 0. Z - under which xz, (t ()) 2 A -
Proof. From our standing assumption, the negative graph G contains least one edge. Let k., m. E V share negative link. We assume the two nodes i1,1 E V labeled in the lemma are different from k., m., for ease presentation. We can then analyze all possible sign patterns among the four nodes i1, J1, Ki,, m.. We present here just the analysis for the case with
{i1. k.) E E+ m,] 5t, k.) E E (ii, E+ The other cases are indeed simpler and can be studied via similar techniques.
Without loss of generality we let Zm. (t) 2 Zk. (t). First of all we select G. = (i1,ka] and G4+1 m. It then straightforward to verify that
Im, (L + 2) 2 Fk. (1 + 2) + 2ac.
By selecting GG+2 {m,,k, we know from 8 2 (2a (2a-1) a
that
JR. Jx. (1+ -, Tm. (1 + 3) c.
There will be two cases:
(a) Let E (m,,ke }. Noting that R(G+) 2 2, there will be a path connecting to k; from i,
without passing through m, in G+ It then obvious that select finite number Z of links which alternate between {m., k. and the edges over that path so that x;, (1+3+ Zi) > -c -c Here Zı depends only on and n.
(b) Let í. E {m., k. We only need to show that we can select pair realizations so that Tm..
can get close to -c, and Ti. gets close to e after + 3. Since G+ connected, either m, or
k. has at least one positive neighbor. For the moment assume m' is positive neighbor of m. and k a positive neighbor of k. with m' + k'. Then from part (a) we can select Zz
node pairs that
Em. (t +3+ 22) S cc kk. +t Z2) c-E.
Thus, selecting the negative edge {m,,ki for 1+5+ Z2 implies Tm. (1+6+ e for B 2 12 The case with m' = k'' can be dealt with by a similar treatment, leading to the same conclusion. This concludes the proof of the lemma.
In view of Lemmas D.2 and D.3 the desired theorem a consequence of the second Borel-Cantelli Lemma.
E A Signed Graph Perspective on Existing Oversmoothing Countermeasures
We defined the signed graph propagation over the whole graph 9 written in the matrix form as:
X = (1 a1-a+- B)x + +att + X BÂ-A X,
(24)
17

---

Table 5: The mathematically equivalent normalized positive and negative adjacency matrices in signed graph propagation various anti-oversmoothing methods.
Method
Characteristic
Positive A
Negative A
GCN
K K-layer graph convolutions
0
SGC
K-layer linear graph convolutions
BatchNorm
Normalized with column means and variance
1,
PairNorm
Normalized with the overall means and variance Uniformed norm derived from contrastive loss
1, /n (XX*)A
ContraNorm
DropEdge
Randomized augmentation
Åm
Residual
Last layer connection
APPNP
Initial layer connection
gk+1 a
j- As
JKNET
Jumping to last layer
A
Σ x
= A
DAGNN
Adaptively incorporating different layer
Y 2 a 1'
A
-- A
Feature-SBP (ours)
Label-induced negative graph
softmax (A)
Label-SBP (ours)
Feature-induced negative graph
softmax(A)
where A is the raw normalized version of the positive adjacency matrix A 10,1]axn and À is that of the negative adjacency matrix A E {0, 1
We summarize eight specific methods with their corresponding positive and negative graphs in T
E.1 Normalizations
BatchNorm BatchNorm centers the node representations to zero mean and unit variance and can be written as BatchNorm(z:)) Voz4e (z; -- where e and o² is the variance of node features. We rewrite BatchNorm the signed graph propagation form as follows:
x = ÁX 1,12 ÁXT A
1, AX
(25)
7
where Fa = diag(o .a) is diagonal matrix that represents column- wise variance with of 1/ ((X)) 1, AX/n)3, and X XT is normalized version of X. We can
correspond to the positive graph A to Å and the negative graph to I.II" À equation 25
PairNorm We then introduce another method called PairNorm where the only difference between it and BatchNorm is that PairNorm scales all the entries in X using the same number rather than scaling each column by its own variance. The formulation PairNorm can be rewritten as follows:
x Ax
1 11 Ax 1 (Ax n
(Ax
1,17 AX),
(26)
n
where r' [(Á [1) We observe that PairNorm shares the same positive and negative graphs (up to scale) BatchNorm. Another normalization technique, ContraNorm, turns out to extend the negative graph to an adaptive one based on node feature similarities.
Proposition E.1 Consider the update:
- A 1 AX,
(27)
where A E {0, (0,1)axn is the adjacency matrix. Define the overall signed graph adjacency matrix A, as 2-27 A. Then we have that the signed graph is (weakly) structurally balanced only if the original graph can be divided into several isolated complete subgraphs.
18

---

Proof. Assume that there is no isolated node and no node has edges with all the other nodes. (A,)i, (A)i.) degi If (A)..) L, then we have (A.)i, O. If (A)s. 0, then we have (Ag)i, <0.
If the nodes can be divided into several isolated complete subgraphs, then the nodes set V Vi V2... Vn,, where [Vi| > 1, m is the number of the isolated complete subgraphs. So only the nodes within the same set have edges, thus relative entries of A, > O, while nodes from different sets do not, thus relative entries of A, < O.
On the other hand, if A. is (weakly) structurally balanced, then the nodes set can be expressed as V = Vi V2 ... Ve where [Vi| 1, is the number of the separated parties in the signed graph. The entry of A, in the same parties is positive, while between different parties is negative, According to (A,)..) (A),.) degs n we know that nodes in the parties are connected in the original graph while not connected in the original graph between different parties. So the graph can be divided into several isolated complete subgraphs.
Overall, the signed graph is (weakly) structurally balanced only if the original graph can divided into several isolated complete subgraphs, the proof is over.
The Proposition shows that in order for the structural balance property to hold for the signed graph of normalization, the graph needs to satisfy an unrealistic condition where the edges strictly cluster the nodes.
ContraNorm ContraNorm is inspired by the uniformity loss from contrastive learning, aiming to alleviate dimensional feature collapse. For simplicity, consider the spectral version of ContraNorm that takes the following form:
== (1 +
(28)
where a E (0, 1) and are hyperparameters. We can that Á is again the positive graph and (XXT)A is the negative graph in the corresponding signed graph propagation.
Consider the update:
XXT
X
AX
AX,
(29)
Define the overall signed graph adjacency matrix A, = xx" where (Aa)i. = (A)ss
-
yn I. (A)).
Assume that the nodes feature is normalized every update, that is ||æ,|12 1 for every i.
(A)i, 1, then we have that
(A.) -A))ss 1 Di r (A)
>i 1 (A)
(30)
ンズー (A)k.s
dj
>
n
That means if (A)e, = 1, then (Az).s > However, if (A)s. 0, then we have that
(A.) (A)i.j 1
Ekm m. (A)
n
Dine (A)k.j
(31)
EKEN, xf
Intuitively, if x; has similar features to xy neighbors, then we have that (As)ss < 0, which means trying to repel nodes with similar representations. If x; has different features to 2y neighbors,
19

---

then we have that (A > O, which means trying to aggregate nodes with original different representations.
graph G is a completed graph, then all entries of ( (A,) > 0, however, when all the nodes coverage each other, - (A)k.- Eh 2 will also become bigger.
E.2 Dropping
For DropMessage 21. it is unified way of DropNode, DropEdge and Dropout but with a more flexible mask strategy. We have discussed the DropNode and DropEdge our paper. DropMessage can be viewed as randomly dropping some dimension of the aggregated node features instead of the whole node or the whole edge. We give the unified positive and negative graph of DropMessage in the term of the signed graph. The propagation of DropMessage can be expressed H]()
AH((-1) Mm, where dropping A AH then My AH else Mij = 0.
E.3 Residual Connections
The standard residual connection 44
45
directly combines the previous and the current layer features
together. It can be formulated as:
x= x X X +aAx - aTX
(32)
For residual connections, the positive adjacency matrix Á and the negative adjacency matrix I in the corresponding signed graph propagation.
APPNP
We reformulate the method APPNP 42 as the signed propagation form the initial node feature. Another propagation process is APPNP [2 which can be viewed layer-wise graph convolution with residual connection to the initial transformed feature matrix (0),, expressed as:
((++1) (1 ax) + (A)
(33)
sx++1 Theorem E.2 With A+ = Di=0 a² A' and À = a l As, the propagation process of APPNP
following the signed graph propagation.
Proof. Easily prove with mathematical induction.
In addition combining with the last and initial layer features, the last type integrates several intermediate layer features. The established representations are JKNET 18 and DAGNN [19].
JKNET JKNET is deep graph neural network which exploits information from neighbor- hoods of differing locality. JKNET selectively combines aggregations from different layers with Concatenation/Max-ponnn poolling Boooling/Attennni Attention the output, i.e., the representations "jump" to the last layer. Using attention mechanism for combination at the last layer, the k + 1-layer propagation result of JKNET can be written as:
(R+1)) x() x1 + ....... (x))
(34)
= - A'x(0,'''''))
where Olg, "', Og the learnable fusion weights with E6
Deep Adaptive Graph Neural Networks (DAGNN) 19 tries to adaptively add all the features from the previous layer to the current layer features with the additional learnable coefficients. After decoupling representation transformation and propagation, the propagation mechanism of DAGNN similar to that JKNET.
DAGNN
x (k+1) = Dk A (0) (x(
(35)
H = fo()())) is the non-linear feature transformation using MLP network, which is con- ducted before the propagation process and On, 01,, ... Og are the learnable fusion weights with 2 1.
20

---

Theorem E.3 With A+ = ='' + A and A E At, the propagation process of JKNET and DAGNN following the signed graph propagation.
Proof.
Easily prove with mathematical induction.
As for more residual inspired methods 20 discussion as follows.
46
47
48
we select GCNII and wGCN to give a detailed
As for GCNII 20] it is an improved version of APPNP with the learnable coefficients og and changes the learnable weight W to (1 - 3,) + B,W each layer, so it shares the same positive and negative graph as APPNP.
As for the wGCN [46), it incorporates trainable thannel-wise weighting factors w to learn and mix multiple smoothing and sharpening propagation operators at each layer, same as the init residual combines but change parameters a to be learnable with a more detailed selection strategy.
F Oversmoothing Metrics
There exist a variety of different approaches to quantify over-smoothing in deep GNNs, here we choose the measure based on the Dirichlet energy graphs 15 49]
c (t) = l Eiev EsEN.Il=;()) - -0,(t))())) (t)
(36)
where e is the number of the nodes, (t) is the node feature of node i at time t. N, represents the neighbor set of node i, In the signed graph, it including nodes connected to by both positive and negative edges. Oversmoothing means that when the layers infinity, all of the node features will converge, that is to say lim e (1) - O.
In Theorem
3.2 there are 2 cases:
ifß B., then we have lim 22(() =2 n for all initial values x0)
2y(0
if3 > Be, then lim;-soe ||I(t)]| = oo for almost all initial values w.r.t. Lebesgue measure.
In the first case, all the node features will coverage to the mean of them and therefore lim; (X(()) - O, then oversmoothing happens. In the second case, the node features will diverge to infinity and thus l (()) - 0 or co which is also not what we want.
Theorem 3.2 demonstrated that both insufficient repulsion and excessive repulsion caused by the negative graph can hinder performance in signed graph propagation. From this, we conclude that relying solely on the negative signs is insufficient to alleviate oversmoothing. Therefore, we propose the provable solution: a structurally balanced graph to efficiently alleviate oversmoothing in Theorem 4.2 Specifically, we have the following conclusion from the structurally balanced graph in Theorem
PP m s2(()) = (x((0),, e Vi; lim xx(1) = -(x(0)), V/)) =1. 1.
(37)
Then we have:
lim e ((((1))
= lim Evev E, 1iEN,1lx:(0) 2z((1 (-220
(38)
lim Yev, MeN [I)(t)) - =z, (t)1 + 1 Dee 2 Mye,, (x: - -x;0))x;(())))) (t)l
(39)
1
lim E,vv, Eye (1) - 2t) + Eiev, Eiev, [lx((t) - x, (t)
1-000
y
(40)
v 2
1
-im Evevi
- 2c
(41)
[+x00
2
"
1
v
v
v
lim
-
x
2c
+
26)
(42)
6-220
2
2
2 0
(43)
21

---

(a) structural balance
(b) weakly structural balance
(c) unbalance
Figure 7: Examples structural balanced (left), weakly structural balanced (middle), and unbalanced signed graphs (right). Here red lines represent positive edges; black dashed lines represent negative edges; gray and blue circles represent nodes from different labels
So Theorem 4.2 proves that under certain conditions, structural balance can alleviate oversmoothing even when the layers are infinity.
G Weakly Structural Balance
To clarify the concept of structural balance, weakly structural balance and unbalance signed graph, we give the examples as shown in Figure 7 The notion of structural balance can be weakened in the following definition G.I
Definition G.1 A signed graph G is weakly structurally balanced there is partition of V into = Vi U V/2 U... U Vm. m 2 2 with Vı,... Vn being nonempty and mutually disjoint, where any edge between different V; is negative, and any edge within each V; is positive.
Then we show that when complete graph, weak structural balance also leads to clustering of node states.
Theorem G.2 (25), Theorem 10) Assume that node interacts with node j and xt(() represents the value of node at time Let 0 = if the edge {i,j} is positive and 0 = 3 if the edge {i,5} is negative. Consider the constrained signed propagation update:
(t 1) Fa((1 ()z,(t)) (x.
(44)
Leta E (0, Assume that G is a weakly structurally balanced complete graph under the partition V = U2- U Vm- When is sufficiently large, for almost all initial values x(0) w.r.. Lebesgue measure, there exists m random variable 4 (x(0),, (2(x(0)), ..., Im (x()()), each of which taking values in {-c, e} such that
lim 21 1)(=)))) Vg.j 1....,m, =1.
(45)
H Statement and Proof of Label-SBP
In this section, we show that our method Label-SBP can create a structurally balanced graph under certain conditions and thus provably alleviate oversmoothing the number of propagation steps increases. To achieve this, we introduce a metric, structural imbalance degree (SID), to quantify the level of structural balance in arbitrary signed graph. Specifically, SID counts the number of edges that must be changed to achieve the structural balance.
Definition H.1 (Structural Imbalance Degree) For each node in signed graph G. of nodes, lei (v)) denote the subset of nodes that has the same label as but connected v by a non- positive edge; let (v) denote the subset of nodes that has different label from but connected
22

---

Table STD on CSBM (Contextual Stochastic Block Model with different methods. We set the two class means = -1 and U2 = respectively, the number of nodes N 100, intra-class edge probability p= = log 100 100/100 and inter-class edge probability 4 = log 100/100.
Method
P.
N
SID
DropEdge
92.62
100.00
96.31
Residual
90.87
100.00
95.44
GCN/SGC
89.87
100.00
94.94
APPNP
0.00
100.00
50.00
JKNET
0.00
100.00
50.00
DAGNN
0.00
100.00
50.00
BatchNorm
89.87
4.56
47.22
PairNorm
89.87
4.56
47.22
ContraNorm
89.87
4.56
47.22
Feature-SDae SBlurre-BPPPa (ours)
89.87
4.56
47.22
Label-SBP (ours)
32.46
36.16
34.31
to v by a non-negative edge. Then the structural imbalance degree of G is defined as SID(G.) 1
2n Eveg, (P())] (W()))).
SID exhibits fundamental characteristic: it increases more edge signs deviate from the criteria of a structurally balanced graph, suggesting a higher degree structural imbalance. Specifically, when the signed graph achieves the structural balance, we can assert that STD 0 as follows:
Proposition H.2 For structural balanced complete graph Gah, we have SID(G 0.
Proof If the graph is structurally balanced, we can see that for node v. P(v) and (v) due to the structural balance complete graph assumption. So SID(g) 0.
Based the SID, we can quantity the degree of structural balance in the equivalent signed graphs induced by anti-oversmoothing methods discussed in the previous section, as shown in Table Our results show that previous anti-oversmoothing methods either remain high STD imbalance P and N. In contrast, our methods effectively reduce the STD, resulting in more structurally balanced graph, or at least be on par with previous methods.
Besides the empirical observation, we present the following theoretical result which demonstrates that Label-SBP can be guaranteed to achieve certain level of structure balance:
Proposition H.3 Assuming balanced node label classes with |Yi = Y2l. a labeled node ratio
denoted as p, and the signed gruph 9 created by Label-SBP, then we have SID(G!) S (1 1al-ppa p)n/2.
Proof Without loss of generality, assume that the node feature has been normalized which means that ||æ/||2 for every i. iy and vj has the same label, then we have that, (As)s. = (A)s, + 1 1. If x; and z, has different labels, then we have that (As)ks (A) 1 < 0.
We first prove that SID(G.P) p) s (1 10ppp p) where n the nodes number and p is the label ratio. We have that
P(v) + (v() < (1-p)n,
(46)
because for a single node only the remaining (1 p)n nodes' labels are unknown and therefore their edges may need to change so that
SID(G) Σ (IP()) (W(()
p)n
(47)
(1 p)
23

---

We know that when (g) O, then we have that the nodes V set can be divided into V UV ...U Vt, where L is the number of the node classes. There are only positive edges with the node subset and only negative edges between the node subset.
Since C = the node According to Theorem 4.2 we have that the nodes in V1 will converge to the where ||c||2 = 1 and the nodes 1/2 will converge cc. Thus under Label-SBP propagation, the oversmoothing will only happen within the same label and repel different labels to the boundary.
be divided into V1 and V2, the signed graph is structurally balanced.
Proposition H.3 suggests that Label-SBP constrains SID linearly with the training ratio p. indicating that SID diminishes with an increase in the labeling ratio p. In particular, it implies that Label-SEP strictly establish structurally balanced graph for any graph under the full supervision condition, making the model easier to distinguish nodes with different labels as the number of layers increases:
Theorem H.4 Under full supervision = 1), the signed graph G' induced by Label-SBP achieves SID(C)) 0. Consequently, under the constrained signed propagation given by equation nodes from distinct classes will converge towards unique constants.
lim x =ciee Vi; lim x -c, V2)
(48)
k000
I Details of Experiments
L.1 Details of the Dataset
Table 7: Summary of datasets. (G') refers to the edge homophily level: the higher, the more
homophilic the dataset is.
Datasct
H(G)
Classes
Nodcs
Edges
Cora
0.81
7
2,708
5,429
Citeseer
0.74
6
3,327
4,732
PubMed
0.80
3
19,717
44,338
Texas
0.21
5
183
295
Cornell
0.30
5
183
280
Amazon-ratings
0.38
5
24,492
93,050
Wisconsin
0.11
5
251
466
Squirrel
0.22
4
198,493
2,089
Ogbn-Arxiv
0.65
40
16,9343
1,166,243
We consider two types of datasets: Homophilic and Heterophilic. They are differentiated by the homophily level of a graph.
Number of v's neighbors who have the same label as v Number of v's neighbors
H Σ
PEV
The low homophily level means that the dataset more heterophilic when most of the neighbors are not in the same class, and the high homophily level indicates that the dataset is close to ho- mophilic when similar nodes tend to be connected. In the experiments, we use four homophilic datasets, including Cora, CiteSeer, PubMed, and Ogbn-Arxiv, and four heterophilic datasets, includ- ing Texas, Wisconsin, Cornell, Squirrel, and Amazon-rating (36 The datasets we used covers various homophily levels.
CSBM Settings. To quantify the structural balance of the mentioned methods, we simplified the graph 2-CSBM(N, p. q. f1, U22 )²) following (24). consists of two classes C₁ and C2 of nodes of equal size, in total with N nodes. For any two nodes in the graph, if they are from the same class, they are connected by an edge independently with probability p. or if they are from different classes, probability is For each node Ci 11, the initial feature X,, is sampled independently from Gaussian distribution N N(js, )²), where μ4 = C,, a T. In this paper, we assign N 100 and the feature dimension is 8.
24

---

1.2 Experiments Setup
For the SGC backbone, we follow the [4 setting where we run 10 runs for the fixed seed 42 and calculate the mean and the standard deviation. Furthermore, we fix the learning rate and weight decay in the same dataset and run 100 epochs for every dataset. For the GCN backbone, we follow the [16] settings where we run 5 runs from the seed {0, 1, 2, 3, 4) and calculate the mean and the standard deviation. We fix the hidden dimension to 32 and dropout rate to 0.6. Furthermore, we fix the learning rate to be 0.005 and weight decay to be 5e - and run 200 epochs for every dataset. We use the default splits in grom_eec..ttic. We use Tesla- 10t----000--X--22-0000 in all experiments.
1.3 Time Complexity Analysis and the Modified SBP
Label-SBP As shown in equation 4.2, we maintain the positive adjacency matrix A+ = Å and construct the negative adjacency matrix A by assigning when nodes i, have different labels, -1 when they share the same label, and when either label unknown. We then apply softmax to A to normalize the negative adjacency matrix. The overall signed adjacency matrix is Asign aA+ - f tefa((ma(Aj (Ai), where a and | are hyperparameters. Given n, training nodes and edges in the graph, our Label-SBP increases the edge count from O(d) to O(n)), thereby increasing the computational complexity to (nf
Feature-SBP When labels are unavailable, we propose Feature-SBP, which uses the similarity matrix of node features to create the negative adjacency matrix. As depicted in equation 4.2 we design the negative adjacency matrix as A
Xo We then apply softmax Ay normalize it. The overall matrix follows the same format as Label-SBP: Asign aA+ @ssofmart (max(Ay), where a and B are hyperparameters. The additional computational complexity primarily stems from the negative graph propagation, which involves Xx.X. E R increasing the overall complexity to O(n'd) d).
We show the computation time of different methods in the Table g On average, we improve performance on 8 out of 9 datasets (as shown in Table with less than 0.05s overhead even faster than three other baselines. We believe this time overhead is acceptable given the benefits it provides.
Table 8: Estimated training time of SBP Cora dataset. All experiments the abbreviation for second. Precompute time is the aggregation time across layers, train time is the update time of the SGC weight W. total time is the sum of them.
under 2 layers. is
Label-SBP
Feature-SBP
BatchNorm
ContraNorm
Residual
JKNET
DAGNN
SGC.
Precompute time
0,1809s
0.1320s
0.1860s
0.1888s
0.0604s
0.0577s
0.1438s
0.1307s
Train time
0,1071s
0.1060s
0.1076s
0.1038s
0.1368s
0.1446s
0.1348s
0.1034s
Total time
0.2879s
0.2580s
0.2935s
0.2926s
0.1972s
0.2023s
0.2786s 5
0.2341s
Rank
4
8
2
3
Scalability of SBP on large-scale graph For large-scale graphs, we introduce a modified version Label-SBP-v2 by only removing edges when pairs of nodes belong different classes. This approach allows Label-SBP SBP-v2 to eliminate the computational overhead of the negative graph, further enhancing the sparsity of large-scale graphs. For Feature- SBP, as the number of nodes n increases, the complexity of this matrix operation grows quadratically, i.e., O d). To address this, we reorder the matrix multiplication from -x XX E Raxn to XJ Xo E Rdxd, This preserves the distinctiveness of node representations across the feature dimension, rather than across the node dimension as the original node-level repulsion. The modified version of Feature-She SBP can be expressed as:
(Feature-SBP-v2) X
softmax( ()-1 X(xxx( (00)taa X))) (49)
This transposed alternative has a linear complexity in the number of samples, i.c., O(nd)), signifi- cantly reducing the computational burden in cases where n >>
We compare the compute time SBP with other baselines on agbn-arxiv dataset over 100 epochs for a fair comparison. Among the training times of the baselines, our Label-SBP-v2 achieves the 3rd fastest time while Feature-SBP-v2 ranks 5th. Therefore, we recommend using Label-SBP-v2 for large-scale graphs since they typically have a sufficient number of node labels. We believe that although there is slight time increase, is acceptable given the benefits.
25

---

Table Estimated training time of SBP on ogbn-ariig arixv dataset. All experiments are run under layers and 100 epochs. is the abbreviation for second.
Label-SBP
Feature-SBP
BatchNorm
ContraNorm
DropEdge 9.5727
SGC 5.3097
Train time (s)
5,5850
6.1333
5,3872
5.8375
Rank
3
5
2
4
6
The code for the experiments will be available when our paper is acceptable. We will replace this anonymous link with non-anonymous GitHub link after the acceptance. We implement all experiments in Python 3,9 with PyTorch Geometric on one NVIDIA Tesla VI00 GPU.
1,4
Results Analysis
14.1
CSBM results
The comparative results of Label-SBP and Feature-SBP against SGC are presented in Table T0 As the number of layers increases, SGC's node features suffer from oversmoothing, causing the two classes converge and accuracy to drop by nearly 30 points from its peak at 2 layers, down to 45%. Conversely, after 300 layers, SBP maintains strong performance, with node features of different classes repelling each other. This effect limits oversmoothing to within-class interactions, and improves performance from 85 to 91 in Label-SBP and from 48 to 82 in Feature-SBP, further substantiating our approach to mitigating oversmoothing.
We visualize the node features learned by Label-SBP in Figure We can see that from layer 0 to layer 200, the node features from different labels repel each other and aggregate the node features from the same labels. And we also visualize the adjacency matrix of Label-SBP and Feature-SPB in Figure 10 and Figure respectivvly, further verifying the effectiveness our theorem and insights.
20
15-
10
-10
-5-
-10
-10
-15
-20
(a) SGC, acc= 47.50
(b) Feature-SBP, acc= 80.00
(c) Label-SBP, acc= 97.50
Figure 8: The t-SNE visualization of the node features and the classification accuracy from 2-CSBM and Layer= 300. Left is the result of the vallina SGC, and the middle and right are the results of SBP.
Table 10: CSBM test accuracy (%) comparison results. The best results are marked in blue on each layer. The second best results are marked in gray on each layer. We run 10 runs for the seed from 0 - 9 and demonstrate the mean + std in the table.
Model
#1
#1
#1.110
#1=20
#1=500
#1
#1 #1.=200
SGC
73,25 1. 6.90
44.50 1. 9.34
45.75
1 9.36
45.75
1 9.36
45.75
1. 9.36
45.75 1 9.36
45.75 1. 9.36
SeP
48.75 4:
53.75
4 6445
63.75
6:255
77.00
4 5.45
82.00
4.58
82.50
4.11
82.00 5.45
Label-SBP
85.75
93.50
4.06
93.50
93.50
92.25
3.44
93.25
91.25
L4.2 GCN Results
The results for GCN are detailed in Table II respectively. Overall, SBP consistently outperforms all previous methods, especially deeper layers. Beyond 16 layers GCN, SBP maintains superior performance, affirming the effectiveness of our approach. Notably, SBP exceeds the best results of prior methods by at least 10% and up 30% points GCN's deepest layers, marking significant improvements. Moreover, unlike previous methods that perform best in shallow layers, SEP excels in
26

---

104
-5
28
69
25
75
100
L=1
L=10
50
30
L=50
T==100
T,=200
Figure 9: CSBM node features visualization, We update the features by Label-SBP. is the propaga- tion layer number. 0,1 represent different classes.
Adjacency Matrix
Label-induced
675
850
028
0.30
003
1.00
(a) positive graph
(b) negative graph
(c) overall signed graph
Figure 10: The visualization of the adjacency matrix Label-SBP. Here left the positive graph; middle is the negative graph; right is the overall signed graph.
moderately deep layers, as observed in GCN across all datasets. This further confirms the effectiveness of SBP.
L.4.3 8 Analysis on Heterophilie Datasets
Our method SBP can outperform other baselines under 8 = 1 across different layers, we do not tune our hyper-parameters carefully. However, since the weight of the negative adjacency matrix (equation 4.2) representing the repulsion between different nodes, seen in Figure Tigure4andd and 5 the best performance of SBP appears when 3 is larger in the heterophilic graphs, so the result in Figure Ba(a) a) not the best performance of our SBP. To further show the effectiveness of our SBP, we conduct experiments on Cornell with different Table 12 the best 20 where performance increases 25 points in deep layer 50.
1.4.4 SBP on more benchmarks
We further compare our with SGC on six additional datasets 36 Table 13
Our SBP out-
performs SGC on five out of these six datasets. We believe that these six datasets, combined with
27

---

100
1.00
Ad
Matrix
Overall Ad
0.75
10
20
Overall bolge Prosecee
Coge
0.00
03
60-
70-
-0.25
80
60
(a) positive graph
(b) negative graph
(c) overall signed graph
Figure 11:
The visualization of the adjacency matrix of Feature-SBP. Here left is the positive graph; middle is the negative graph; right is the overall signed graph.
the nine datasets presented in Table of our paper, provide sufficient evidence to demonstrate the effectiveness of our approach.
1,4.5 Different Backbones
In this paper, we focus introducing novel theoretic signed graph perspective for oversmoothing analysis, so we do not take many tricks into account or carefully fine-tune our hyperparameters. Thus, our results in the paper are not comparable previous baselines [20] 47 48). However, existing oversmoothing researches are indeed hard to compare, because they are often composed of multiple techniques such as residual, BatchNorm, data augmentation are often heavily (over-)tuned on small-scale datasets. And it becomes clear that to attain SOTA performance, one needs essentially compose multiple such techniques without fully understanding their individual roles. For example, GCNII uses both initial residual connection and identity map, futher combined with dropout.
and the parameters
Our goal to provide a new unified understanding of these techniques, so we justified it by showing that SBP single simple technique can attain good performance. And believe that would work complementarily with other techniques in the field, because oversmoothing is still challenging solve with very larger depth.
To further verify the effectiveness, we combine our SBP to one of the SOTA settings GCNII 20 and the results demonstrates greater robustness as the layers go deeper, particularly in the middle layers (layer=8), highlighting the efficacy of our signed graph insight.
in Table 14 The results indicate that after combining method, GCNII
I.4.6 SBP on Large-scale graphs
We conducted experiments with a larger graph ogbn-products than ogbn-arxiv under 100 epochs and 2 layers in Table 13 The results indicate that our SBP outperforms the initial GCN baselines. Given the results presented for ogbn-arxiv Table of our paper, we believe these findings adequately demonstrate the performance of our SBP on large-scale graphs.
1.4.7 Further Optimization
Based on the experiment results, we want to propose 2 strategies for further optimization.
1) hyper-parameter tuning the negative weight B. As seen in Figures and 5 we found that / influences the performance a lot, our default / = 1 for Table and is certainly not optimal for the above homophilic datasets. We suggest tuning higher for the heterophilic graphs since they need more repulsion and smaller for the homophilic datasets. As the layer deepens, maybe greater weight should be placed the negative adjacency graphs alleviate oversmoothing.
2) adapt our SBP to more effective GNNs. Our method simple, architecture-free without addi- tional learnable parameters, and thus be flexibly applied in various architectures. As seen in
28

---

Table 11: GCN test aceuracy (%) comparison results. The best results are marked in blue and the second best results are marked in gray on every layer. We run 5 runs for the seed from 0 - 4 and demonstrate the mean std the table.
Model
#L=2
#L
#L=8
#L=16
#L=32
#L=64
Cora B7
GCN
80.68 =0.09
79.69 =0.00
74.32 +0.00
30.95 =0.00
30.95 #0.00
24.85
77.46
GAT
10
81.48 0.48
80.69
0.93
58.59 = 1.95
25.17 5.67
31.93 0.21
28.38
0.00
wGCN [46
80.97 0.28
80.51 = 0.00
80.46 = 1.77
70.53 22.09
80.02
0.12
27.90
6.09
BatchNorm 1
78.09 =0.00
77.87 #0.02
73.62
+0.57
70.79 #0.00
53.90 #2.19
35.32
#3.41
PairNorm 17
79.01 10.00
78.26 10.50
73.21 10.00
62.96 10.00
48.13 10.91
44.01 13.46
ContraNorm 16
81.55 #0.21
79.61 #0.75
77.71 +0.00
63.35 =0.00
44.56 14.83
38.97
=0.00
DropEdge
78.38 1:000
74.47 10.00
22.24
25.98
16.00
Residual
80.68 10.09
78.77
10.00
79.26
10.21
40.91
10.00
30.95
10.00
27.90
16.00
Feature-SBP
80.44 +0.83
79.26 1118
78.56
+0.59
77.22 #0.55
73.65 10.48
61.62 #5.24
Label-SBP
80.31 1.770
79.16
11.30
1.000 79.50
77.43
11.49
74.52
65.02
SiteSeer (38)
GCN 8
67.45 =0.54
65.62 =0.25
37.22 22.46
22.03 #4.76
19.65
+0.00
19.65
=0.00
GAT 10
69.91 0.86
67.47 = 0.22
44.71 = 3.07
23.48 = 1.36
24.40 0.40
25.95
2.17
wGCN [46
66.21 + 0.63
66.49 1.69 0.69
66.79 + 0.00
17.54
19.65
0.00
19.65 0.00
BatchNorm
41
63.44 =0.94
62.34 20.25
61.36 10.00
50.58 11.24
$1.00
PairNorm
63.58 10.63
10.95
61.95
50.06
11.87
10.07
ContraNorm 16
66.83 10.49
64.78 10.92
60.70 10.60
44.79 11.65
37.36 10.25
30.85 10.81
DropEdge 22
63.86 -0.03
62.24 20.90
24.73 55.72
20.65 +0.00
20.04
10.19
19.95
20.09
Residual
67.45 1.054
66.21
10116
67.34 10.00
33.21 1:000
19.65
1.000
19.65
1..00
Feature-SBP
67.38 10.66
66.94
10.00
66.29
10.02
65.35 11.99
61.43
10.00
42.09
1165
Label-SBP
67.23 20.64
66.72
10.00
66.29 +0.80
65.50 12.13
59.93
10.85
44.41
#1.57
PubMed
GCN 8
76.44 10.34
76.52
10.32
69.58
15580
39,92 +0.00
39.92 10.00
39.92
10.00
+BatchNorm
75.52=0.12 =0.12
77.15
=0.00
77.10
=0.00
76.92 =0.00
75.43 +0.00
69.33 1.01
+PairNom
75.66 10.11
76.71
10.00
10.00 77.99
77.22 10.39
75.52 12.02
71.22 13.68
ContraNorm
76.05 10.33
78.42 10.00
OOM
0OM
0OM
0OM
+DropEdge 2Y
73.41 +0.03
73.96 20.79
52.51 #10.91
40,27
#0.00
39.90
+0.59
40.08
=0.39
+Residual
76.44 1.0.4
77.28
10.00
77.38 10.00
63.14 13.05
39.92
1..00
39.92 10.00
Feature-SBP
75.72 10.06
76.84
10.00
78.39
10.00
79.71
10.00
77.59
10.23
78.06
10.13
Label-SBP
76.33 #0.25
76.91
#0.00
77.60
#0.49
76.31
#0.00
77.17
20.67
78.01
#0.16
Table 12: Ablation study of negative weight / on Cornell dataset.
Layer
10
20
50
3 0.1
72.97 0.00
51.53 + 0.00
15.14::0.00
29.73 + 0.00
B (default)
72.97 = 0.00
67.57 0.00
51.53 = 0.00
45.95
$::95=00 0.00
35.14 + 0.00
70.27 0.00
67.57
58.11 = 1.35
5.05
51.53 0.00 0.00
8 20 (best)
70.27 +: 0.00
70.27
67.57
4: 0.00
5..46
59.46 + 0.00
64.60 0.00
40.54 0.00
40.54 + 0.00
40.54 0.00
40.54 + 0.00
Appendix 1.4.5 we adapt our SBP to the GCNII models, and the results increase more than adaptation
in vanilla GNN as shown in Table 2 and 3 Besides, compared the GCNII, our SBP is more robust and stable to the layers as seen in Table
Table 13: Performance Comparison on more datasets
actor
penny94
roman-empire
Tolokers
Questions
Minesweeper
SGC
29.18 + 0.10
72.56 = 0.05
40.83 = 0.03
78.18 + 0.02
97.09 + 0.00
80.43 0.00
Feature-SBP
34,93 + 0.00
75.68 = 0.01
66.48 0.02
78.24 + 0.04
97.14 +: 0.02
80.00 0.00
Label-SBP
34,94 +: 0.00
75.74 = 0.01
66.32
0.01
78.46 + 0.08
97.15 4 0.02
80.00 0.00
29

---

Table 14: Performance Comparison between SBP and GCNII under the GCNII settings on Cora and
Citesser datasets
4
16
32
GCNI
78.58 = 0.00
17.7600.24
73.47 = 3.82
78.12
1.32
82.54
0.00
81.34 0.53
Cora
Label-SBP
78.74 + 1.54
78.87
0.00
79.14 + 0.35
79.17
+ 0.41
80.86 + 0.32
81.38 + 0.30
Fea
77.95 = 0.91
78.82
0.00
78.11 1 1.62
78.82 + 0.29
81.82 - 0.47
81.65 + 0.40
GCNII
61.66 1 0.67
63.23 1.
64.58 1 2.66
66.21 1 0.64
69.38 1 0.83
69.73 1 0.26
Citesser
Label-SBP
= 0.63
63.93 +
68.33 0.99
66.46
+ 0.00
70.00
+ 0.81
69.47 :
Feature-SBP
65.63 0.87
64.43 +.43::3555 3.35
68.44 1.19
66,94
0.00
69.98
0.93
69.66 + 0.28
Table 15: Performance of different models on ogbn-products dataset. Time means the runtime, the format is (hour: minutes: seconds).
Method
Accuracy
Time
GCN
73.96
00:06:33
BatchNorm
74.93
00:06:18
Feature-SBP
74.90
00:06:43
Label-SBP
76.62
00:06:39
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
We discuss the limitations.
Guidelines:
The answer NA means that paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
30

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Refer to Section and Appendix C and
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Refer to Section for implementation. We will release the code and models when this paper is published.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
31

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., , a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We provide the code in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/guides: (ogoli/cuuldas//deeebbbssssssss
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https cttt:ps.cc.uublicc// htw.bl/cc/ggidss///oooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Refer to Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
32

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We experiments on five random seeds and provide the mean and std Table ??.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Refer to Section 5.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp::/neurrpps: httpa//rww.p...pp.a.//cccccsaaaa
Answer: [Yes]
Justification:
The research conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
33

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: This paper describes safeguards that have been put in place for the responsible release of data or models that have a high risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
34

---

Answer: [Yes]
Justification: We cite all papers that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswithcode
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The new assets introduced the paper are well documented and the documen- tation is provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
35

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our LLM policy //npur:////urraie cc. Cc//oonferencee/22255///// for what should or should not be described.
36


Reviews:
[{"review_id": "lxd8PL2ak4", "reviewer": "Reviewer_mzv3", "summary": "This paper studies oversmoothing from the perspective of structural balance and proposes constructing signed graphs based on node labels or feature similarity to introduce  positive and negative edges that connect similar and dissimilar nodes, respectively, to enable better clustering/classification of nodes from which both homophilic and heterophilic inputs can benefit with the apprpriate setting of hyperparameters.", "questions": "Questions:   \n1. Line 122: What is meant by 'non-trivial negative edges'?\n2. Is $A^+=A$ necessary? The notation is a little confusing as the statement on line 135 about beta=0 resulting in the model degenrating into standard unsigned propagation is only true in this case. If inter-class egdes are removed in Label-SBP-v2, is $A^+ \\neq A$? Along similar lines, why are the alpha values fixed to 1 and not varied? 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? \n3. In Figure 3(b), how do the baselines perform at these lower label rates? This would highlight the gain of Label-SBP over them in high label rates particularly, and of Feature-SBP in low label rates. \n4. Was Feat-SBP-v2 also evaluated on OGB-Arxiv dataset? The results are missing in Table 5. \n5. Has the effect of ablating the residual connection the strength of which is controlled by $\\gamma$ been studied? How much of SBP's success in alleviating over-smoothing can be attributed to the signed graph component (particularly in deeper layers) than the residual component?\n6. Is the result of Feature-SBP for #$L=2$ a typo in Table 10? \n7. Is SBP  applicable to only node classification or could it also cater to other graph tasks such as link prediction? \n\n[4] GNNs Use Graphs When They Shouldn't (ICML 2024)\n\n[5] GATE: How to Keep Out Intrusive Neighbors (ICML 2024)\n\n[6] When Are Graph Neural Networks Better Than Structure-Agnostic Methods? ICBINB (NeurIPS 2022)", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1. Several existing strategies to mitigate oversmoothing that were developed individually and intuitively are unified under the framework of signed graphs which further elucidates their underlying principles.\n2. The study is quite comprehensive - identifies a unifying perspective on existing techniques, analyzes the conditions under which signed graphs optimally benefit node classification, addresses scalability problems, considers both homophilic and heterophilic graphs, extensive experiments across varying datasets, baselines and GNN backbones for prposed SBP method. \n3. I particularly appreciate the position of the paper as one that aims to provide more understanding of the matter through theoretical and empirical analysis rather than chasing a SOTA performance using various 'tricks'. This could potentially provide the groundwork for further developing SBP-based techniques.\n\nWeaknesses:\n1. The hyperparameter beta as an essential component is most likely difficult to tune, specially since it is unbounded. \n2. Albiet not rooted in structural balance theory, other approaches such as GRAFF[1], $\\omega$GAT[2], FAGCN[3] that also use signed representations on the original graph structure itself to improve attraction and repulsion between similar and dissimilar nodes, respectively, are not discussed. Could the authors comment on how they are related to SBP and perhaps provide a comparison to see what the more effective approach to using signs to model attraction and repulsion is? \n3. Minor: readability is compromised by several missing references in the appendix. (e.g. lines 551, 846, 898, 926, 933).\n\n\n[1] Understanding Convolution on Graphs via Energies (TMLR 2023)\n\n[2] Improving Graph Neural Networks with Learnable Propagation Operators (ICML 2023)\n\n[3] Beyond Low-frequency Information in Graph Convolutional Networks (AAAI 2021)", "was_revised": true, "final_justification": "Given the strengths of the paper listed in the original review, and adequate answers provided by the authors to my questions during the rebuttal, I recommend acceptance of this paper.", "rebuttal": "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:\n\n- W – Weakness\n- Q - Question\n\n**W1 The hyperparameter $\\beta$ is difficult to tune.**\n\n---\n\nThank you for your comment.\n\nIn 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.\n\n**W2 Would be better to discuss and compare with other methods using signed representations.**\n\n---\n\nThank you for the comment.\n\nWe 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.\n\nWe will also include a discussion of signed representation methods in the Related Work section of the revised manuscript.\n\n| methods | acc |\n| --- | --- |\n| GRAFF[1] | 80.91 |\n| $w$GCN[2] | 78.58 |\n| gat  | 81.48 |\n| Feature-SBP | **82.46** |\n| Label-SBP | **82.90** |\n---\n[1] Understanding Convolution on Graphs via Energies (TMLR 2023)\n\n[2] Improving Graph Neural Networks with Learnable Propagation Operators (ICML 2023)\n\n**W3 References citation in the appendix.**\n\n---\n\nThank you for noting this! We will fix these reference typos in the revision.\n\n**Q1 Clarification.**\n\n---\nBy “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.\n\n\n**Q2 Clarification.**\n\n---\nRegarding $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.\n\n\n\n**Q3 Label ratio ablation on baselines.**\n\n---\n\nThank you for the question.\n\nWe 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.\n\n| train percentage | 20 | 40 | 60 | 80 |\n| --- | --- | --- | --- | --- |\n| batchnorm | 80.25 | 83.00 | 85.50 | 88.25 |\n| contranorm | 83.00 | 86.50 | 86.75 | 90.00 |\n| Label-SBP | **87.00** | **91.50** | **91.50** | **97.50** |\n\n**Q4 Feature-SBP-v2 on ogbn-arxiv.**\n\n---\n\nThank 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.\n\n|  | L=2 | L=4 | L=8 | L=16 |\n| --- | --- | --- | --- | --- |\n| GCN | 67.32 | 67.79 | **65.54** | 59.13 |\n| Feature-SBP-v2  | **67.89**   | **68.47**  | 65.09 | **60.34** |\n\n**Q5 Ablation on residual parameters.**\n\n---\n\nThank 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.\n\n|  | 0.1 | 0.5 | 0.9 |\n| --- | --- | --- | --- |\n| Feature-SBP | 79.00 | 83.75 | 88.00 |\n| Label-SBP | 85.75 | 88.25 | 91.50 |\n\n**Q6 Clarification.**\n\n---\nThe notation “#L = 2” in Table 10 is intentional and not a typo; it indicates that the number of layers $L$ is 2.\n\n**Q7 Is SBP applicable to other graph tasks, such as link prediction?**\n\n---\n\nThank you for the question.\n\nWe 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.\n| methods | acc |\n| --- | --- |\n| gcn | 0.8389 |\n| Feature-SBP | 0.8430 |\n| Lable-SBP | **0.8617** |\n\n-------\nWe appreciate your questions and comments very much. Please let us know for any further questions."}, {"review_id": "rm1dDre2lg", "reviewer": "Reviewer_3cVw", "summary": "This paper proposes a method based on signed graphs to understand and mitigate the over-smoothing problem in Graph Neural Networks (GNNs). Through the framework of signed graphs, the authors demonstrate that various existing techniques for mitigating over-smoothing can be interpreted as implicitly introducing negative edges. Furthermore, the authors propose the Structural Balance Propagation (SBP) method, which enhances structural balance in the constructed signed graph by assigning signed edges based on either labels (label-SBP) or feature similarity (feature-SBP). For large-scale graphs, they also introduce Label-SBP-v2. Experiments show that SBP effectively improves classification accuracy and alleviates over-smoothing in deep GNNs with up to 300 layers. This method provides a theoretical explanation for existing over-smoothing mitigation methods and offers a new direction for the design of signed message-passing in deep GNNs.", "questions": "1. Despite being supported by structural balance theory, can SBP be further optimized to adapt to more complex graph structures?\n    \n2. The experimental settings for large-scale graphs are not sufficiently detailed. Could you provide more details to support the applicability of SBP on large-scale graphs? Additionally, could you provide experimental data on larger-scale graphs and differentiate the experiments for settings such as large-scale vs. small-scale graphs and homogeneous vs. heterogeneous graphs?\n    \n3. The paper lacks experiments on GCNs with deep layers for heterogeneous graphs. The number of experiments on heterogeneous graphs is notably less than on homogeneous graphs.\n    \n4. The experiments lack a detailed description of F(z)c​ (e.g., the range of values for c).", "limitations": "The authors have adequately discussed the limitations of their work, particularly regarding the scope of the method's evaluation and its applicability to large-scale graphs.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. The proposed SBP method is introduced clearly, is easy to understand, and demonstrates good scalability and adaptability.\n    \n2. The theoretical analysis is solid and strongly supports the proposed method, offering a new perspective for understanding the over-smoothing problem in GNNs.\n    \n3. Empirical results on various datasets show that the proposed method effectively improves performance and mitigates over-smoothing under multiple settings.\n    \n4. Several details about the proposed method are not sufficiently clear. For instance, the analysis of its adaptability to large-scale graphs could be more detailed.\n    \n5. There is a lack of illustrative diagrams to show the propagation process of SBP. \n    \n6. The discussion on the applicability of the method to different types of graphs (homogeneous and heterogeneous graphs) could be more in-depth.", "was_revised": true, "final_justification": "The authors have addressed my questions, so I will maintain my positive score.", "rebuttal": "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:\n\n- W – Weakness\n- Q - Question\n\n**W4 The analysis of its adaptability to large-scale graphs could be more detailed.**\n\n---\n\n\nWe 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.\n\n\n**W5 Lack of illustrative diagrams to show the propagation process of SBP.**\n\n---\n\nThank 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.\n\n**W6 The discussion on the applicability of the method to different types of graphs (homogeneous and heterogeneous graphs) could be more in-depth.**\n\n---\n\nThat 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.\n\n**Q1 Can SBP be further optimized to adapt to more complex graph structures?**\n\n---\n\nOur 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.\n\n**Q2 Could you provide more details to support the applicability of SBP on large-scale graphs? Distinguish different graph settings.**\n\n---\n\n We conducted large-scale experiments on the ogbn-arxiv and ogbn-products datasets, which contain millions of nodes and edges, as summarized as follows.\n\n   | Datasets       | Nodes      | Edges        | Type  |\n|----------------|------------|--------------|-------|\n| Cora           | 2,708      | 5,429        | Small |\n| OGBN-Arxiv     | 3,774,768  | 16,518,948   | Large |\n| OGBN-Products   | 2,449,029  | 61,859,140   | Large |\n\nThe 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:\n\n  | Method        | Accuracy | Time      |\n|---------------|----------|-----------|\n| GCN           | 73.96    | 00:06:33  |\n| BatchNorm     | 74.93    | 00:06:18  |\n| Feature-SBP   | 74.90    | 00:06:43  |\n| Label-SBP     | **76.62**| 00:06:39  |\n\n\nHomophilic 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. \n\n\n | Dataset   | Nodes  | Edges  | Homophily Level |\n|-----------|--------|--------|------------------|\n| Cora      | 2,708  | 5,429  | Homo             |\n| Squirrel  | 198,493| 2,089  | Heter            |\n\n\n**Q3 Lack of heterogeneous graphs results.**\n\n---\n\nThank you for the comment.\n\nDue 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.\n\nWe will clarify this placement in the revision.\n\n**Q4 The experiments lack a detailed description of $F_C(Z)$**\n\n---\n\nThank you for the comment.\n\n- **Theoretical:** As discussed in lines 178–180, $F_C(Z)$ refers to any function that ensures boundedness and prevents divergence in node features.\n- **Experimental:** As noted in line 224, we implement $F_C(Z)$ using layer normalization.\n\nWe will clarify this more explicitly in the revision.\n\n-------\nWe appreciate your questions and comments very much. Please let us know for any further questions."}, {"review_id": "sZiC78IVqS", "reviewer": "Reviewer_xGFU", "summary": "The author addresses the common oversmoothing problem in deep graph neural networks (GNNs) by proposing a unified perspective of \"signed graphs\" to reinterpret existing alleviation strategies such as normalization, residual connections, and random edge deletion. The paper first proves that these methods are essentially equivalent to implicitly adding negative edges in the graph, thus introducing an \"attraction - repulsion\" mechanism during information propagation. Subsequently, the author points out that simply adding negative edges is still insufficient to completely solve oversmoothing; the truly crucial factor is the \"structured organization\" of positive and negative edges. Based on the structural balance theory, the author proposes a Structural Balanced Propagation (SBP) that requires no additional learnable parameters and can be plugged in directly. SBP has two implementations:\n\n1. Label - SBP — Using known labels, positive edges are set between nodes of the same class, and negative edges are set between nodes of different classes.\n2. Feature - SBP — In scenarios with scarce labels, the signs of edges are automatically inferred based on feature similarity.\n\nTheoretically, the author provides sufficient conditions for SBP to suppress oversmoothing and proves that node representations on balanced signed graphs will converge to class - specific steady - state values. Experiments demonstrate the superiority of SBP on 9 homogeneous/heterogeneous datasets with a depth of 300 layers, and a sparsified version is provided for large - scale graphs.", "questions": "View the Weaknesses in Strengths And Weaknesses.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- Unified theoretical perspective: It subsumes various known techniques as \"implicit negative edges\", provides clear mathematical derivations, and offers novel theoretical insights. \n- Comprehensive experiments: Covering 9 benchmarks, homogeneous and heterogeneous graphs, ultra-deep layers (300 layers), and the large-scale OGBN-ArXiv dataset, with consistently leading results. \n\nWeaknesses\n- Idealized theoretical assumptions: The key convergence theorem relies on assumptions such as linear propagation, complete graphs, or bipartite clustering, which still have a gap from real sparse graphs.\n- Parameter - sensitivity: Performance is highly sensitive to the negative edge weight β. The paper only uses grid search, lacking an automatic or adaptive adjustment mechanism. \n- Risk of graph densification: By default, SBP requires constructing n² - level negative edges, resulting in significant memory consumption for large graphs. Although the v2 scheme improves this, the accuracy slightly decreases. \n- Insufficient comparison with the latest methods: There is no systematic comparison with recent anti-oversmoothing or heterogeneity methods.", "was_revised": true, "final_justification": "5", "rebuttal": "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:\n\n- W – Weakness\n- Q - Question\n\n\n**W1 The theorem relies on assumptions such as linear propagation, complete graphs, or bipartite clustering, which still have a gap from real sparse graphs.**\n\n---\n\nWe 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:\n\n- 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.\n\n- 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.\n\n- 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.\n\nWe will add the discussion about the assumptions in the revision.\n\n**W2 Performance is sensitive to negative weight $\\beta$, lacking an automatic or adaptive adjustment mechanism.**\n\n---\n\n\nIn 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.\n\nMoreover, 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.\n\n**W3 SBP results in significant memory consumption for large graphs.**\n\n---\nWe 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.\n\n**W4 Insufficient comparison with the latest methods.**\n\n---\n\nThank 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.  \n\n| methods | acc |\n| --- | --- |\n| graff[1] | 80.91 |\n| g2[2]  | 78.11  |\n| feature-sbp | 82.46 |\n| label-sbp | **82.90** |\n\n\nNevertheless, 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.\n\n[1] Understanding Convolution on Graphs via Energies (TMLR 2023)\n\n[2] Gradient Gating for Deep Multi-Rate Learning on Graphs\n\n---------------\nWe appreciate your questions and comments very much. Please let us know for any further questions."}, {"review_id": "MbJZkj34EK", "reviewer": "Reviewer_WoFN", "summary": "Oversmoothing is a well-known problem that plagues GNNs as increasing the number of layers leads to the indistinguishability of features indicating collapse (or consensus) to a single feature (or label) across nodes. This inhibits the use of deep GNNs in practice and a number of strategies have been proposed to ameliorate this problem. \n\nThis article provides a different and novel strategy: it uses a unified analytical framework based on the theory of signed graphs. Oversmoothing is defined as a consensus where all node features collapse to the average in the infinite depth limit. This is dynamically characterized by a structured balance (between positive (attractive) and negative (repulsive)) edges and crisp boundary in terms of a parameter $\\beta$ provided in Th. 3.2. This notion of structured balance arises in social network analysis and its use in this context is novel. Many existing techniques (dropout, normalization, residuals) are shown to implicitly introduce negative edges. \n\nThe authors go beyond just analysis of existing techniques and propose SBP, a plug- and play module to construct signed graphs promoting structural balance, which can be used with any GNN backbone, with positive edges for connecting similar nodes (intra-class) and negative edges for dissimilar nodes (inter-class). 2 variants (Label-SBP and Feature-SBP) are proposed.\n\nThe authors test their method on 9 datasets, both homophilic and heterophilic, and show that their method does better than traditional ways to ameliorate oversmoothing. In particular, the use of very deep graphs (300 layers) and the resulting lack of deterioration of performance is noteworthy.", "questions": "Please address the questions mentioned in the Weaknesses section. In particular, the questions on continuous metrics for over smoothing, comparison with SOTA, task diversity and scaling.", "limitations": "Please see the weaknesses section. I am happy to raise the score if some of the weaknesses are addressed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths: \n\n-- Addressing an important problem in GNNs. \n\n--- Introduces a novel framework for over smoothing, based on signed graphs and structured balance. While signed graphs have been used in the context of heterophilic datasets, their explicit use in this setting appears to be totally novel. \n\n--- Crisp criterion for over smoothing in terms of consensus.  Thrm 3.2 provides an exact phase transition on when over smoothing occurs and when it does not. \n\n---  SBP is a new plug-and-play module to overcome over smoothing. \n\n--- Provides decent empirical benchmarking and showcases the use of very deep GNN layers. \n\n--- Very interesting addition to the GNN literature by introducing a different framework for understanding over smoothing. \n\nWeaknesses: \n\n--- Theory assumes exact structural balance in a signed graph. Is this even possible for real-world data ? Can the authors at least comment on whether this criterion is satisfied for the datasets that they consider. They mention weak-balance but do not analyze it here.\n\n--- This reviewer's main theoretical concern is with the binary over smoothing/non-oversmoothing nature of the consensus criterion. If you compare with other criteria such as the decay in Dirichlet energy or Cosine similarity (see Ref.[49] for a detailed survey), they clearly provide a layer-dependent rate and an easily computable criterion for measuring over-smoothing. The authors' metric is qualitative and they only use accuracy as a proxy for the extent of over smoothing. This lack of a quantification for over-smoothing is the key limiting factor in practical applications. \n\n--- SBP is a fixed signed edge construction. The signs are assigned and cannot be altered, learned or adapted. This might be a straitjacket for the method. In particular, the graph is modified prior to the training and there is no mechanism to alter it during training. \n\n-- The paper does not measure over smoothing through numerous criteria that have been proposed for it -- such as Dirichlet energy ? Cosine Similarity ? Gradient norms ? Just using accuracy as a proxy for oversmoothing is not entirely convincing. The authors should at least Dirichlet energy as a function of width to see if the method is able to actually overcome over smoothing or not. \n\n-- The experimental evaluation is limited. In particular, only traditional methods such as edge-dropout, normalizations, residual connections are considered. What is missing is comparison with state of the art methods to overcome over smoothing. For instance, G2 (arXiv:2210.00513) is very strong baseline as it has been rigorously shown to prevent collapse of Dirichlet energy and hence, over smoothing and it can scale to very large graphs (Snap-patents, 3M nodes, 13M edges). A comparison with the state of the art is necessary. Moreover, SIGN, GPR-GNN, and other adaptive propagation models can be compared with to justify empirical performance. \n\n--- The backbones that the paper proposes are limited to GCN variants and other classes of more frequently used backbones such as (variants of) GAT and GraphSAGE are missing. Perhaps, it is essential to use atleast GAT as a backbone in one of the datasets. \n\n--- The task diversity is very limited, only to transductive node classification. This is too specific -- the authors could other tasks, link prediction, molecular property prediction or PPI , inductive node classification etc. \n\n--- Scaling: the authors only showcase performance on limited size datasets with Obgn-Arxiv being the largest. Scaling to something like snap-patents, a very heterophilic graph  with 3M nodes and 13M edges would be a very interesting challenge for the method. There is a fundamental issue in terms of scaling as the Feature-SBP has a dense similarity matrix (quadratic scaling in nodes) and although the authors mention low-rank approaches, they do not consider it in any detail. The reviewer's concern is that SBP will not scale to large scale graphs.", "was_revised": true, "final_justification": "As my detailed review and the authors' rebuttal and discussions show, this article is a significant contribution to the vexing problem for over smoothing for GNNs. It certainly does not resolve all the issues and its assumptions are strong as far as the theory is concerned. Moreover, the experiments for very large graphs are limited. However, the contribution is solid and there is much to build on.", "rebuttal": "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:\n\n- W – Weakness\n- Q - Question\n\n**W1 How to apply structural balance to real-world data.**\n\n---\n\nThank 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.\n\n**W2 & W4 Lack of metrics for measuring oversmoothing.**\n\n---\n\nThank 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.\n\n**W3 SBP is a fixed signed edge construction.**\n\n---\n\nThank 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.\n\n\n\n**W5 & W6 Comparison with SOTA/different backbones**\n\n---\n\nThank you for the suggestions! We compare our SBP with the aforementioned methods on the Cora dataset. As shown better, SBP achieves better performance.\n\n| Methods | acc |\n| --- | --- |\n| g2 | 78.11  |\n| sign | 69.3 |\n| gpr-gnn | 79.51 |\n| gat | 81.48 |\n| GraphSAGE | 70.89 |\n| feature-sbp | 82.46 |\n| label-sbp | **82.90** |\n\nWe 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.\n\n| Methods | acc |\n| --- | --- |\n| gat | 81.48 |\n| label-sbp(gat) | **83.31** |\n| feature-sbp(gat) | 82.59 |\n\nWe will add these experiments in the updated manuscript. Thank you for the suggestions!\n\n[1] Gradient Gating for Deep Multi-Rate Learning on Graphs\n\n[2] SIGN: Scalable Inception Graph Neural Networks\n\n[3] Adaptive Universal Generalized PageRank Graph Neural Network\n\n**W7 Task diversity**\n\n---\n\nThank 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.\n| Methods | acc |\n| --- | --- |\n| gcn | 0.8389 |\n| feature-sbp | 0.8430 |\n| lable-sbp | **0.8617** |\n\n**W8 Scaling to large-sized graphs.**\n\n---\n\nThank 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. \n\n|  | nodes | edges |\n| --- | --- | --- |\n| snap-patents | 3,774,768 | 16,518,948 |\n| ogbn-products | 2,449,029 | 61,859,140 |\n\nThe results, presented in Appendix I.4.6 (Table 15), show that our SBP method outperforms the baselines, highlighting its scalability.\n\n| Methods | acc | time |\n| --- | --- | --- |\n| gcn | 73.96 | 00:06:33 |\n| batchnorm | 74.93 | 00:06:18 |\n| feature-sbp | 74.90 | 00:06:43 |\n| label-sbp | **76.62** | 00:06:39 |\n--------------------\nWe appreciate your questions and comments very much. Please let us know for any further questions."}]

Author rebuttal:

Meta-review: This paper tackles the over-smoothing problem in GNNs by introducing a unified "signed graph" perspective, demonstrating that common mitigation strategies are equivalent to implicitly adding negative edges and inducing an "attraction-repulsion" mechanism. The authors emphasize that the structured organization of positive and negative edges is key, rather than their mere presence. To this end, they propose Structural Balanced Propagation (SBP), a parameter-free, plug-and-play method grounded in structural balance theory, with both label-based and feature-based variants. Theoretical analysis and experiments on nine datasets, including deep (300-layer) models, show SBP’s superiority over traditional approaches.

Reviewers unanimously recognized the paper’s valuable and novel theoretical contributions and recommended acceptance, while noting some limitations such as strong assumptions and relatively limited large-scale experiments. The AC concurs with the reviewers and recommends acceptance.
Decision: Accept (poster)