Signed Graph Diffusion Network
Authors: Jinhong Jung
Jaemin Yoo
U Kang
Venue:  (2021)
Keywords: graph neural network
signed graph analysis
representation learning
graph diffusion
random walk
link sign prediction

Abstract: Given a signed social graph, how can we learn appropriate node representations to infer the signs of missing edges?
Signed social graphs have received considerable attention to model trust relationships.
Learning node representations is crucial to effectively analyze graph data, and various techniques such as network embedding and graph convolutional network (GCN) have been proposed for learning signed graphs.
However, traditional network embedding methods are not end-to-end for a specific task such as link sign prediction, and GCN-based methods suffer from a performance degradation problem when their depth increases.
In this paper, we propose Signed Graph Diffusion Network (SGDNet), a novel graph neural network that achieves end-to-end node representation learning for link sign prediction in signed social graphs.
We propose a random walk technique specially designed for signed graphs so that SGDNet effectively diffuses hidden node features.
Through extensive experiments, we demonstrate that SGDNet outperforms state-of-the-art models in terms of link sign prediction accuracy. 

Under review as a conference paper at ICLR 2021
SIGNED GRAPH DIFFUSION NETWORK
Anonymous authors
Paper under double-blind review
ABSTRACT
Given a signed social graph, how can we learn appropriate node representations to infer the signs of missing edges? Signed social graphs have received considerable attention to model trust relationships. Learning node representations is crucial to effectively analyze graph data, and various techniques such as network embedding and graph convolutional network (GCN) have been proposed for learning signed graphs. However, traditional network embedding methods are not end-to-end for a specific task such as link sign prediction, and GCN- based methods suffer from a performance degradation problem when their depth increases. In this paper, we propose SIGNED GRAPH DIFFUSION NETWORK (SGDNET), novel graph neural network that achieves end-to-end node representation learning for link sign prediction in signed social graphs. We propose random walk technique specially designed for signed graphs so that SGDNET effectively diffuses hidden node features. Through extensive experiments, we demonstrate that SGDNET outperforms state-of tftt--t--te--rt models in terms of link sign prediction accuracy.
INTRODUCTION
Given a signed social graph, how can we learn appropriate node representations to infer the signs of missing edges? Signed social graphs model trust relationships between people with positive (trust) and negative (distrust) edges. Many online social services such as Epinions (Guha et al.) (2004) and
Slashdot (Kunegis al. 2009) that allow users express their opinions are naturally represented as signed social graphs. Such graphs have attracted considerable attention for diverse applications including link sign prediction (Leskovec et al., [010aa Kumar al. (016),, node ranking (Jung it al. 2016 Li et al. (011bb). community analysis (Yang et al.) 2007: Chu et al.] 2016)), graph generation (Derr et al.) 2018a; Jung et al., 2020). and anomaly detection (Kumar et al. 2014). Node representation learning
fundamental building block for analyzing graph data, and many researchers have put tremendous efforts into developing effective models for unsigned graphs. Graph convolutional networks (GCN) and their variants (Kipf & Welling 2017 Velickovic et al. 2018)
have spurred great attention in machine learning community, and recent works (Klicpera et al. 2019
Li et al. 2019a) have demonstrated stunning progress by handling the performance degradation caused by over-smoothing (Li et al, 2018 Oono & Suzuki, (020) (i.e., node representations become indistinguishable the number of propagation increases) the vanishing gradient problem (Li et al. 2019g) in the first generation of GCN models. However, all of these models have limited performance on node representation learning in signed graphs since they only consider unsigned edges under the homophily assumption (Kipf & Welling 2017).
Many studies have been recently conducted consider such signed edges, and they are categorized into network embedding and GCN-based models. Network embedding (Kim et al., 2018 Xu et al. 2019b) learns the representations of nodes by optimizing an unsupervised loss that primarily aims to locate two nodes' embeddings closely (or far) if they are positively (or negatively) connected. However, they are not trained jointly with a specific task in an end-to-end manner, i.e., latent features and the task are trained separately. Thus, their performance is limited unless each of them is tuned delicately. GCN-based models (Derr et al., 2018b Li et al. 2020) have extended the graph convolutions to signed graphs using balance theory (Holland & Leinhardi 1971) in order to properly propagate node features on signed edges. However, these models are directly extended from existing GCNs without consideration of the over-smoothing problem that degrades their performance. This problem hinders them from exploiting more information from multi-hop multi-hop neighbors for learning node features in signed graphs.

---

Under review as a conference paper at ICLR 2021
H
tanh
Homophily
Loss
(1)
Feature Transformation
SGD Layer
pll)
M
Skip Connection
Locel
F.):): Signed Random Walk Dilfusion
9 SGD Layer
H
(1))
5
SGD Layer
Festure Transtomation
(0)
Heterophily
(a) SGDNET
(b) 1-th SGD layer
(c) Signed random walk diffusion
Figure 1: Overall architecture of SGDNET. (a) Given a signed graph 9 and initial node features X, SGDNNET with multiple SGD layers produces the final embeddings H(2), which is fed to a loss function under end-to-end framework. (b) A single SGD layer learns node embeddings based on signed random walk diffusion. (c) Our diffusion module aggregates the features of node o so that they are similar to those connected by + edges (e.g., node u), and different from those connected by- - edges (e.g., node t). Also, it injects the local feature (i.e., the input feature of each module) of node at each aggregation to make the aggregated features distinguishable.
We propose SGDNET (SIGNED GRAPH DIFFUSION NETWORK), a novel graph neural network for node representation learning in signed graphs. Our main contributions are summarized as follows:
End-to-end learning. We design SGDNET that performs end-to-end node representation learning. Given signed graph, SGDNET produces node embeddings through multiple signed graph diffusion (SGD) layers (Figure I(a). which are fed into a loss function of a specific task such as link sign prediction.
Novel feature diffusion. We propose a signed random walk diffusion method that prop- agates node embeddings signed edges based on random walks considering signs, and injects local features (Figure [[c]). This enables SGDNET to learn distinguishable node representations considering multi-hop neighbors while preserving local information.
Experiments. Extensive experiments show that SGDNET effectively learns node represen- tations of signed social graphs for link sign prediction, giving at least 3.9% higher accuracy than the statc-of-ther the-the-tt art models in real datasets (Table
2 RELATED WORK
2.1 GRAPH CONVOLUTIONAL, NETWORKS ON UNSIGNED GRAPHS
Graph convolutional network (GCN) Kipf & Welling 2017) models the latent representation of node by employing a convolutional operation on the features of its neighbors. Various GCN- approaches (Kipf & Welling 2017 Velickovic et al.] 2018 Hamilton et al., (017) have aroused considerable attention since they enable diverse graph supervised tasks (Kipf & Welling, 2017 Yao ctt al. 2019 Xu al. (019a) to be performed concisely under an end-to-end framework. However, the first generation of GCN models exhibit performance degradation due to the over-smoothing and vanishing gradient problems. Several works (Li et al.] 2018 Oono & Suzuki, 2020) have theoretically revealed the over-smoothing problem. Also, Li et al. (Li et al. (209aa) have empirically shown that stacking more GCN layers leads to the vanishing gradient problem as in convolutional neural networks (He et 2016). Consequently, most GCN- models (Kipf & Welling 2017] 2
Velickovie et al. 2018: Hamilton et al. (017) 7) are shallow; i.e., they do not use the feature information in faraway nodes when modeling node embeddings.
A recent research direction aims at resolving the limitation. Klicpera et al. (Klicpera et al. 2019) proposed APPNP exploiting Personalized PageRank (Jeh & Widom 2003) to not only propagate hidden node embeddings far but also preserve local features, thereby preventing aggregated features from being wwrrssoothed.. Li et al. (Li et al. 2019a) suggested ResGCN adding skip connections between GCN layers, as in ResNet (He et al. 2016). However, all of these models do not provide how to use signed edges since they are based the homophily assumption (Kipf & Welling 2017). i.e.,
2

---

Under review as a conference paper at ICLR 2021
users having connections are likely to be similar, which is not valid for negative edges. As opposed to the homophily. negative edges have the semantics of heterophily (Rogers 2010), ie., users having connections are dissimilar. Although these methods can still be applied to signed graphs by ignoring the edge signs, their trained features have limited capacity.
2.2 NETWORK EMBEDDING AND GRAPH CONVOLUTIONAL. NETWORKS ON SIGNED GRAPHS
Traditional methods on network embedding extract latent node features specialized for signed graphs in an unsupervised manner. Kim et al. (Kim et al. 2018) proposed SIDE which optimizes a likelihood over direct and indirect signed connections on truncated random walks sampled from a signed graph. Xu et al. (Xu et al. 2019h) developed SLF considering positive, negative, and non-linked relationships between nodes to learn non-negative node embeddings. However, such approaches are not end-to-end, i.e. they are not directly optimized for solving supervised task such as link prediction.
There are recent progresses on end-to-end learning on signed networks under the GCN framework. Derr et al. (Derr et al. 2018b) proposed SGCN which extends the GCN mechanism to signed graphs considering balanced and unbalanced relationships supported by structural balance theory (Holland & Leinhardt I97I). Yu et al. (Li et al., 2020) developed SNEA using attention techniques reveal the importance of these relationships. However, such state-of-the-arr models do not consider the over-smoothing problem since they directly extended from GCN.
PROPOSED METHOD
We propose SGDNET (SIGNED GRAPH DIFFUSION NETWORK), novel end-to-end model for node representation learning in signed graphs. Our SGDNET aims to properly aggregate node features on signed edges, and to effectively use the features of multi-hop neighbors so that generated features not over-smoothed. Our main ideas are to diffuse node features along random walks considering the signs of edges, and to inject local node features each aggregation.
Figure deepicts the overall architecture of SGDNET. Given a signed graph G and initial node features X E d as shown in Figure (a) SGDNET extracts the final node embeddings HI e Rexd, through multiple SGD layers where is the number of nodes, L is the number of SGD layers, and d; the embedding dimension of the (-th layer. Then, ( is fed into loss function of specific task so that they are jointly trained in an end-to-end framework. Given (!-),, the 1-th SGD layer aims learn H based on feature transformations and signed random walk diffusion Fa(-) as shown in Figure [(b) The layer also uses the skip connection to prevent the vanishing gradient problem when the depth SGDNET increases.
Figure [cc illustrates the intuition behind the signed random walk diffusion. Each node has two features corresponding to positive and negative surfers, respectively. The surfer flips its sign when moving along negative edges, while the sign is kept along positive edges. For example, the positive (or negative) surfer becomes positive at node v it moves from a positively connected node u (or a negatively connected node t). As result, the aggregated features node become similar to those connected by positive edges (e.g.. node u). and different from those connected by negative edges (e.g., node 1). In other words, it satisfies homophily and heterophily the same time while unsigned GCNs cannot handle the heterophily of negative edges. Furthermore, we inject the local feature (i.e., the input feature of the module) of node v at each aggregation so that the resulting features remain distinguishable during the diffusion.
3.1 SIGNED GRAPH DIFFUSION LAYER
Given signed graph G and the node embeddings (1)) from the previous layer, the 1-th SGD layer
learns new embeddings O as shown in Figure ((b) It first transforms ( into hidden features ( as (1 = H
w-!!) w(( with learnable parameter w! e -1111 Then, it applies the signed
random walk diffusion which is represented as the function Fa ())) that returns " E xd and
M e nxx as the positive and the negative embeddings, respectively (details in Section 3.2 The embeddings are concatenated and transformed as follows:
H o ([D() (( w!ll + H H"-
(1)
3

---

Under review as a conference paper at ICLR 2021
(k-1)
1)
((0
(R)
v
1/|N.1
1/|N.|
+
(R-1)
(R)
(K-1)
m
m
(a) Signed random walks
(h) Feature diffusion for P (8)
and m
(8)
Figure 2: Feature diffusion by signed random walks in SGDNET. (a) Signed random walks properly consider edge signs. (b) The positive and the negative feature vectors (k) and m are updated from the previous feature vectors and the local feature vector ( as described in Equation 2
where ob-) () is non-linear activator such as tanh, || denotes horizontal concatenation of two matrices, and w R22d xdi is trainable weight matrix that learns relationship between p(()) and M
We use the skip connection (He et al., 2016 Li et al. 2019a) with H in Equation TT to avoid the
vanishing gradient issue which frequently occurs when multiple layers are stacked.
3.2 SIGNED RANDOM WALK DIFFUSION
We design the signed random walk diffusion operator Fa(.) used the 1-th SGD layer. Given the signed graph G and the hidden node embeddings H the diffusion operator Fa(-) diffuses the node features based on random walks considering edge signs so that it properly aggregates node features on signed edges and prevents the aggregated features from being over-smoothed.
Signed random walks are performed by a signed random surfer (Jung et al. (016) who has the or sign when moving around the graph. Figure ((a) shows signed random walks on four cases according to edge signs: 1) a friend's 's friend, 2) friend's enemy, 3) an enemy's is friend, and 4) an enemy's enemy. The surfer starts from node with the + sign. If it encounters negative edge, the surfer flips its sign from + to or vice versa. Otherwise, the sign is kept. The surfer determines whether target node is friend of node not according its sign.
Fa(-) exploits the signed random walk for diffusing node features on signed edges. Each node is represented by two feature vectors which represent the positive and negative signs, respectively. Let denote the number of diffusion steps random walk steps. Then, p E 14 and m (8) x are
aggregated at node v, respectively, where paa) (or m! ( is the feature vector visited by the positive (or negative) surfer at step k. These are recursively obtained by the following equations:
d = (1 - c) Σ
Σ
m (k- (k-1)) + ch!
WE
#C
m (1
c)
P
(k-1)
1)
m (k-1)
N
NE
where Ñ is the set of incoming neighbors to node connected with edges of sign 5, N. is the set of outgoing neighbors from node regardless of edge signs, h.!9) is the local feature of node (i.e., the v-th row vector of (()), and 0 < c < 1 is a local feature injection ratio. That is, the features computed by the signed random walk feature diffusion with weight 1 and the local feature
injection with weight with the following details.
(N) and m are diffused Signed Random Walk Feature Diffusion. Figure 2(b) illustrates how p.
by the signed random walks according Equation (2) Suppose the positive surfer visits node step k. For this to happen, the positive surfer of an incoming neighhor u at step k - should choose the edge (u + v +) by a probability 1/1 N/N. ..]. This transition to node e along the positive edge allows to keep the surfer's positive sign. At the same time, the negative surfer of incoming neighbor
u.-) -) by probability 1/1 1/|Rel. cl. In this case, the surfer step k- should move along the edge - -,,
4

---

Under review as a conference paper at ICLR 2021
flips its sign from to +. Considering these signed random walks, pad is obtained by the weighted aggregation of (k-1) and m m Similarly, m is aggregated as shown in Figure 2(b)
p
Local Feature Injection. Although the feature diffusion above properly considers edge signs, the generated features could be over-smoothed after many steps if depend solely the diffusion. In other words, it considers only the graph information explored by the signed random surfer, while the local information in the hidden feature 6,) is disregarded during the diffusion. Hence, as shown in Figure 2(b), we explicitly inject the local feature h to f with weight c at each aggregation in Equation (2) so that the diffused features are not over-smoothed. The reason why local features only injected to + embeddings is that we consider a node should trust (+) its own information (i.e., its local feature).
3.3 CONVERGENCE GUARANTEE SIGNED RANDOM WALK DIFFUSION
(K) represent the positive and negative embeddings of all nodes, respectively, where denotes vertical concatenation. Let A. be the adjacency matrix for sign such that A is for signed edge (u - s), and 0 otherwise. Then, Equation (2 vectorized as follows:
Suppose that ( [p] (R) ;.... Pa J and M [m (A)T ;.... mm
(kk) (1 ((k + A cH
= ((() = -1-
- BT cQ (3)
( (1 - (A_ A.M()-)
where A, D D A, is the normalized matrix for sign and D is diagonal out-degree matrix (i.e., 3 is compactly represented as the right equation where
DR = N :). The left equation of Equation
T
A
(1)
(
B
Q
M (R)
Then, (k) is guaranteed to converge shown in the following theorem.
Theorem The diffused features in (k) converge to equilibrium for E (0, follows:
k-1 Σa-cy'B Q -L--
T lim (R))
lim k-+00
( = cQ]
we iterate Equation
K times for k < K, the exact solution T is approximated
T (()
Q + (1-c)BC BQ + (1 - -B (1--))BBTTT)
(5)
[P()]
where T
(T)) < (1 c) IT' ( and (())
is the initial value of M
Equation
Proof A proof sketch is to show the spectral radius of B is less than or equal to 1, which guarantees the convergence of the geometric series with (1-c)B. See the details in Appendix
According to Theorem I B is the node features diffused by K-step signed random walks with Q where BK is interpreted as the transition matrix of K K-step signed random walks. Thus, the approximation the sum of the diffused features from 1 K steps with a decaying factor c, ie.. the effect of distant nodes gradually decreases while that of neighboring nodes is high. This is the reason why SGDNET prevents diffused features from being over-smoothed. Also, the approximation error T ( | exponentially deceases K increases due to the term (1 c)² Another point is that the iteration of Equation (3) converges to the same solution no matter what p(o) and ( are given. In this work, we initialize (0) with ()) and randomly initialize (9) in [11
The signed random walk diffusion operator Fa(-) iterates Equation ( K times for 1 < < K where K is the number of diffusion steps, and it returns plu) <- (() and M (K) as the outputs the diffusion module at the (-th SGD layer. The detailed pseudocode of SGDNET is described in Appendix A.3, and its time complexity is analyzed in Appendix A.2
5

---

Under review as a conference paper at ICLR 2021
Table 1: Dataset statistics of signed graphs. [V] and E are the number of nodes and edges, respectively, Given sign E {+, - |E|| and p(s) are the number and percentage of edges with sign s, respectively.
Dataset
[
[R]
E
F
p(+)
p(-)
Bitcoin-Alpha AAppa'
3,783
24.186
22,650
1,536
93.65%
6.35%
Bitcoin-OTCC
5,881
35,592
32,029
3,563
89.99%
10.01%
Slashdot
79.120
515,397
392,326
123,071
76.12%
23.88%
Epinions
131,828
841,372
717,667
123,705
85.30%
14.70%
httpss//saap.tt wtw.aaannodddddddeaadeeaa www.e/eeeeettteeeeeeeeeeeee woo.oooooooooooooooooooooooooooo
htLp://konee und kob Leg.enn,,a wat.rrka/ssaaaaee. 200
bttp://wwer www.://wssste.....m. www.stee...g//.hh...............
Epiniens _atases
3.4 Loss FUNCTION FOR LINK SIGN PREDICTION
The link sign prediction is to predict the missing sign of given edge. As shown in Figure I(a
SGDNET produces the final node embeddings H(4) The embeddings are fed into a loss function C(G, H( θ) Leign (G, H()) )+= + rCreg (0) where @ is the set of model parameters, Leign (-) is the
binary cross entropy loss, and Creg (-) is the L2 regularization loss with weight decay X. For signed
edge (u -> U, s). the edge feature is E 1 h. [lb!" where h is the u-th row vector of
H Let be the set of signed edges. Then, fusggn (.) is represented as follows:
Lsign (9, X) =- E Σ
Il( s) log (softmax, (Zue W))
(E-FO,))E AE(+-)
where W E R2 x2 a learnable weight matrix, so ao is the probability for sign t after softmax operation, and I(-) returns 1 if given predicate is true, and 0 otherwise.
4 EXPERIMENTS
We evaluate the effectiveness of SGDNET through the link sign prediction task.
Datasets. We perform experiments on four standard signed graphs summarized in Table Bitcoin- Alpha (Kumar et al., 2016)) Bitcoin-OTC (Kumar et al., (2016). Slashdot (Kunegis et al. (009). and
Epinions (Guha et al. 2004). We provide the detailed description each dataset Appendix A.4 We also report additional experiments Wikipedia dataset (Leskovec et al. 2010b) in Appendix A.5
Competitors. We compare our proposed SGDNET with the following competitors:
APPNP (Klicpera al.) 2019): an unsigned GCN model based on Personalized PageRank.
ResGCN et et
al. 2019a): another unsigned GCN model exploiting skip connections to deeply stack multiple layers.
SIDE (Kim et al., 2018): a network embedding model optimizing the likelihood over signed
edges using random walk sequences to encode structural information into node embeddings.
SLF (Xu et al. 2019b): another network embedding model considering positive, negative, and non-linked relationships to learn non-negative node embeddings.
SGCN (Derr et al. 2018b): a state-of-theeart signed GCN model considering balanced and
unbalanced paths motivated from balance theory propagate embeddings.
SNEA (Li et al. 2020): another signed GCN model extending SGCN by learning attentions on the balanced and unbalanced paths.
We use the absolute adjacency matrix for APPNP and ResGCN since they handle only unsigned edges. All methods are implemented by PoTor and Numpy in Python. We use machine with Intel E5-2633 v4 2.2GHz CPU and Geforce GTX 1080 Ti for the experiments.
Evaluation Metrics. We randomly split the edges of signed graph into training and test sets by the 8:2 ratio. As shown in Table the sign ratio is highly skewed to the positive sign, i.e., the sampled datasets are naturally imbalanced. Considering the class imbalance, we measure the area under the curve (AUC) to evaluate predictive performance. We also report F1-macro measuring the average of the ratios correct predictions for each sign since negative edges need to be treated as important as positive edges (i.e., it gives equal importance to each class). A higher value of AUC Fl F1-macro indicates better performance. We repeat each experiment 10 times with different random seeds and report the average and standard deviation of test values.

---

Under review as a conference paper at ICLR 2021
Table 2:
SGDNET gives the best link sign prediction performance in terms of AUC. The best model is in bold, and the second best model is underlined. The % increase measures the best accuracy against the second best accuracy.
AUC
Bitcoin-Alpha
Bitcoin-OTC
Slashdot
Epinions
APPNP (Klippera et al. 2019)
0.854+0.010
0.867=00009
0.837=:0.003
0.870=+0.000
ResGCN (L. el al. 2019a
0.853
0.876=0.010
0.744110000
0.871++0.002
SIDE (Kim et all 2018)
0.801=0.020
0.839-10.013
0.814:1.000
0.880-10.003
SLF (Xu ct am 20196)
0.779-10.023
0.797110.014
0.833:10.006
0.876.10.005
SGCN (Derr et al 2018b)
0.824=000188
0.857=0.008
0.827=00.004
0.895=t0.000
SNEA (1.i ct al.
2020
0.855+000006
0.858+00.008
0.754+00.005
0.771+50.004
SGDNet (proposed)
0.911-1.007
0.921
0.005
0.886110.001
0.932.10.001
% increase
6.4%
4.9%
5.9%
3.9%
Table 3: SGDNET gives the best link sign prediction performance in terms of Fl Fl-macro.
F1-macro
Bitcoin-Alpha
Bitcoin-OTC
Slashdot
Epinions
APPNP (Klicpera et al. 2019) ResGCN (L. ot al. 201
0.682-10.000 0.658
0.762-10.009
0.748
0.773-10.004
0.735=+00015
0.609:10.000
0.784++0.003
SIDE Kim et al 2018)
0.663
0.709-10.00%
0.685110.009
0.785110.009
SLF (Xu et al. 20196)
0.615=0.027
0.641=0.025
0.733:10.008
0.810=E0.008
SGCN (Derr et al. 2018b)
0.690+000014
0.776+00.008
0.752-+0.013
0,844++0.002
SNEA (Li el al.
2020
0.670110.005
0.742.10.01T
0.690.L0.005
0.80510,000
SGDNet (proposed)
0.757-10.012
0.799--0.007
0.778+-0.002
0.854+0.002
% increase
7.4%
1.6%
3.5%
1.2%
Hyperparameter Settings. We the dimension of final node embeddings to 32 for all methods so that their embeddings have the same learning capacity (see its effect in Appendix A.6)). We perform 5-fold coss-validation for each method find the best hyperparameters and measure the test accuracy with the selected ones. In the cross-validation for SGDNET, the number L of SGD layers is sought between 1 and and the restart probability is selected from 0.05 0.95 by step size 0.1. We set the number K of diffusion steps to 10 and the feature dimension d, of each layer to 32. We follow the range each hyperparameter recommended in its corresponding paper for the cross-validation of other models. Our model is trained by the Adam optimizer (Kingma & Ba 2015), where the learning rate 0.01, the weight decay À is 0.001, and the number of epochs is 100. We summarize the hyperparameters used by SGDNET for each dataset in Appendix A.7
4.1 LINK SIGN PREDICTION
We evaluate the performance of each method on link sign prediction. Tables 2 and B summarize the experimental results in terms of AUC and F1-macro, respectively. Note that our SGDNET shows the best performance in terms of AUC and F1-macro scores. SGDNET presents 3.9 6.4% and 1.2 7.4% improvements over the second best models in terms of AUC and F1-macro, respectively. We have the following observations.
The unsigned GCN models APPNP and ResGCN show worse performance than SGDNET, which shows the importance of using sign information.
The performance of network embedding techniques such SIDE and SLF is worse than that of other GCN-hased models; this shows the importance of jointly learning feature extraction and link sign prediction for the performance.
The performance of SGCN and SNEA which use limited features from nodes within 2 ~ 3 hops is worse than that of SGDNET which exploits up to K-hop neighbors' features where K is set to 10 in these experiments. It indicates that carefully exploiting features from distant nodes as well as neighboring ones is crucial for the performance.
4.2 EFFECT OF DIFFUSION STEPS
We investigate the effect of the feature diffusion in SGDNET for learning signed graphs. We use one SGD layer, and set the restart probability 0.15 evaluate the pure effect of the diffusion
7

---

Under review as a conference paper at ICLR 2021
0.75
0.78
F1-marro
0.7
F1-mecro
0.78
F1-macro
0.76
0.80
0.74
0.65
0.826
0.72
@863Nee (850CN
@:50NNel BB0ONN
@5GONet B5OON
@503Ner BB5G
6
10
6
10
Diffusion Steps
Diftusion Steps
Diffusion Steps
Diffusion Steps
(a) Bitcoin-Alpha
(b) Bitcoin-OTCC
(c) Slashdot
(d) Epinions
Figure 3: Effect of SGDNET's feature diffusion compared to state-of-the-art SGCN. The performance of SGDNET is boosted while that of SGCN degrades the number K of diffusion steps increases.
0.78
0.75
0.786
0.775
Emacoo
Ft-macro
0.70
21-marr
F1-macro
0.05
0.775
0.77
0.73
0.77
-0.44
0.72
0.706
0.785
0.1
0.5
0.78
0.70
0.5
0.54
Local Injection Ratio
Injection Ratio
Local Injection Ratio
Local Injection Ratio
(a) Bitcoin-AIpha
(b) Bitcoin-Ore OTC
(c) Slashdot
(d) Epinions
Figure 4: Effect of local injection ratio e of SGDNET. A relatively small value (0.15 ~ 0.35) of
the best for the Bitcoin-Alpha and Bitcoin-OTC (small) datasets while around 0.5 shows better accuracy for the Slashdot and Epinions (large) datasets.
module; we vary the number K of diffusion steps from 1 to 10 and evaluate the performance of SGDNET in terms of F1-macro for each diffusion step. Also, we compare SGDNET to SGCN, state-of-the-art-r the-art-mode! for learning signed graphs. The number of diffusion steps of SGCN is determined by its number of layers. Figure 3 shows that the performance of SGDNET gradually improves K increases while that of SGCN dramatically decreases over all datasets. This indicates that SGCN suffers from the performance degradation problem when its network becomes deep. i.e., it is difficult to features of farther nodes, and generates more expressive and stable features than SGCN does. Note that the performance of SGDNET converges in general after sufficient number of diffusion steps, which is highly associated with Theorem
information beyond 3 hops in SGCN. On the other hand, SGDNET utilizes
4.3 EFFECT OF LOCAL INJECTION RATIO
examine the effect of the local injection ratio e the diffiusion module of SGDNET. We use one SGD layer, and set the number K of diffusion steps to 10; we vary from 0.05 to 0.95 by 0.1, and measure the performance the link sign prediction task in terms of F1 -a-mo. Figure shows the effect of the predictive performance of SGDNET. For small datasets such Bitcoin-OTCC, between 0.15 and 0.35 provides better performance. On the other hand, around 0.5 shows higher accuracy for large datasets such Slashdot and Epinions. For all datasets, low too high value of e (c.g.. 0.05 or 0.95) results in poor performance.
Eitcoin-Alpha and
CONCLUSION
In this paper, we propose SIGNED GRAPH DIFFUSION NETWORK (SGDNET), a novel graph neural network that performs end-to-end node representation learning for link sign prediction in signed graphs. propose signed random walk diffusion method to properly diffuse node features on signed edges, and suggest a local feature injection method to make diffused features distinguishable. Our diffusion method empowers SGDNET to effectively train node embeddings considering multi- hop neighbors while preserving local information. Our extensive experiments show that SGDNET provides the best accuracy outperforming the state-of-the-a models in link sign prediction. Future research directions include extending method for multi-view networks.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Lingyang Chu, Zhefeng Wang. Jian Pei, Jiannan Wang, Zijin Zhao, and Enhong Chen. Finding gangs in war from signed networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pp. 1505-1514. ACM, 2016.
Tyler Derr, Charu C. Aggarwal, and Jiliang Tang. Signed network modeling based on structural balance theory. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pp. 557-566. ACM, 20
Tyler Derr, Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In IEEE International Conference on Data Mining, ICDM 2018, Singapore, November 17-20, 2018, pp. 929-934. IEEE Computer Society, 2018b.
Ramanathan V. Guha, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. Propagation of trust and distrust. In Proceedings of the 13th international conference on World Wide Web, WWW 2004, New York, NY, USA, May 17-20. 2004, pp.
ACM, 2004.
Nathan Halko, Per-Gunnar Martinsson, and Joel A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev., 53(2): 217-288, 2011.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1024- 1034,, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference Computer Vision and Patter Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016.
Paul W Holland and Samuel Leinhardt. Transitivity in structural models of small groups. Comparative group studies, 2(2): 1971.
Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the Twelfth International World Wide Web Conference, WWW 2003, Budapest, Hungary, May 20-24, 2003, pp. 271-279. ACM. 2003.
Jinhong Jung, Woojeong Jin, Lee Sael, and U Kang. Personalized ranking in signed networks using signed random walk with restart. In IEEE 16th International Conference on Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, pp. 973-978, IEEE Computer Society, 2016.
Jinhong Jung, Ha-Myung Park, and Kang. Balansing: Fast and scalable generation of realistic signed networks. In Proceedings of the 23rd International Conference on Extending Database Technology, EDBT 2020, Copenhagen, Denmark, March 30- April 02, 2020, pp. 093-204. Open- Proceedings.org. 2020.
Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang. SIDE: representation learning in signed directed networks. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pp. 509-518. ACM, 2018
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.

---

Under review as a conference paper at ICLR 2021
Srijan Kumar, Francesca Spezzano, and S. Subrahmanian. Accurately detecting trolls in slashdot zoo via decluttering. In 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2014, Beijing, China, August 17-20, 2014, pp. 188-195. IEEE Computer Society, 2014.
Srijan Kumar, Francesca Spezzano, V. S. Subrahmanian, and Christos Faloutsos. Edge weight prediction in weighted signed networks. In IEEE 16th International Conference Data Mining, ICDM 2016, December 12-15, 2016, Barcelona, Spain, pp. 221 230. IEEE Computer Society, 2016.
Jérôme Kunegis, Andreas Lommatzsch, and Christian Bauckhage. The slashdot zoo: mining social network with negative edges. In Proceedings of the 18th International Conference on World Wide Web, WWW 2009, Madrid, Spain, April 20-24, 2009, pp. 741-750. ACM, 2009.
Jure Leskovec, Daniel P. Huttenlocher, and Jon M. Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 19th International Conference on World Wide Web, WWW 2010, Raleigh, North Carolina, USA, April 26-30, 2010, pp. 641-650 ACM, 2010a.
Jure Leskovec, Daniel P. Huttenlocher, and Jon M. Kleinberg. Signed networks in social media. In Proceedings of the 28th International Conference on Human Factors in Computing Systems, CHI 2010, Atlanta, Georgia, USA, April 10-15, 2010, pp. 1361-1370. ACM, 2010b.
Guohao Li, Matthias Müller, Ali K. Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? 2019 IEEE/CVE International Conference on Computer Vision ICCV 2019, Scoul, Korea (South), October 27 November 2, 2019, pp. 9266-9275. IEEE, 2019a
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for supi-supe learning. In Proceedings of the Phirty-Secome AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the Sth AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp. 3538-3545. AAAI Press, 2018.
Xiaoming Li, Hui Fang, and Jie Zhang. Supervised user ranking in signed social networks. In The Thirty-Thire AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-Fire Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolula, Hawaii, USA, January February 1, 2019, pp. 184-191. AAAI Press, 2019b.
Yu Li, Yuan Tian, Jiawei Zhang, and Yi Chang. Learning signed network embedding via graph attention. In The Thirty-Fourey AAAI Conference on Artificial Intelligence, AAAI 2020, The Teiond-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY. USA, February 7-12, 2020, pp-
AAAI Press, 2020.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Everett M Rogers. Diffusion of innovations. Simon and Schuster, 2010.
Lloyd N Trefethen and David Bau III. Numerical linear algebra, volume 50. Siam, 1997.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lid, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019a.
10

---

Under review as a conference paper at ICLR 2021
Pinghua Xu, Wenbin Hu, Jia Wu, and Bo Du. Link prediction with signed latent factors in signed social networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, pp. 1046-1054. ACM, 2019b.
Bo Yang, William K. Cheung, and Jiming Liu. Community mining from signed social networks. IEEE Trans. Knowl. Data Eng.. 19(10):1333-1444 2007.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In The Thirly-Third AAAI Conference Artificial Intelligence, AAAI 2019, The Thirty-First Innova- live Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 February 1, 2019, pp. 7370-7377, AAAI Press, 2019.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 CONVERGENCE ANALYSIS
Theorem (Convergence of Signed Random Walk Difflusion The diffused features in T(k) con-
verge to equilibrium for E (0, 1) as follows:
1-1
T lim (
lim k
Ea-
Q (I-
c) B -Q
Q .Q)
k-000
1=0
we iterate Equation 3 K times for k K, the exact solution T is approximated
T= T(()
Q + +1-c)BB
+ (1 (1-c)K--p - (1 c) (T
[(())
where
TT T()) < (1 - c) I T [1,, and T(0) = M
is the initial value of
Equation
Proof The iteration of Equation
is written as follows:
(*) = (1 - (T) + cQ
(1- - c)B² 2 (k + (I) ā
k-1 Σ ((1 ②
& (()) = -(I-
(6)
Note that the spectral radius (BB) is less than equal to 1 by Theorem for << 1, the spectral radius of (1 is less than 1, i.e., p((1 c1(1c))
(1 c)p S (1-c) 1. Hence, if k > Do, the power of (1 B) converges to O, i.e., lim
B² 0. Also, the second term in Equation (6) becomes the infinite geometric series of (1 cB which converges as the following equation:
Σ (1--)) ( à -- Q
T lim (k) + lim k00
k+000
where the convergence always holds if p((1 c)B) < 1. The converged solution T satisfies T (1 (11-))B c) + cQ. Also, T* is approximated Equation G). Then, the approximation error IT - <T(K)]/ is bounded as follows:
T -T- [1(1 BT - -1 S c) B|] (KK-))
s (1 [1-c)][T T -T(K-1)11
< (1 T (T00)
where Il:1/1 -oomorm of matrix. Note that the bound [B]] S of Theorem derivation.
is used in the above
Theorem 2 (Bound of Spectral Radius of B) The spectral radius of B in Equation or equal to
is less than
ie., pl (B) < BB|] 1.
O
Proof 2
According to spectral radius theorem Trefethen & Bau III
1997 (()) S [B]]] where I|:I1
denotes Lą-norm of a given matrix, indicating the maximum absolute column sum of the matrix. Note non-negative probabilities; thus, the absolute column sums of B are equal to
that the entries of its column sums which are obtained as follows:
2mr B = [ IJĀ AJ
L = bT bJ]
(8)
12

---

Under review as a conference paper at ICLR 2021
where À = =AT +II. and 1n is an n--dimensional one vector. Note that A A for sign where D is a diagonal out-degree matrix (i.e., D IN a.).) Then, 1, A is represented as
A "
(IAII,) D D'' =b=
where A A + A_ is the absolute adjacency matrix. The u-th entry of |A[1, indicates the out-degree of node denoted by [N... Note that D is 1/|Nul if is non-deadend. Otherwise, D qa = 0 (i.e. a deadend node has no outgoing edges). Hence, the u-th entry of b is if node D=1
not deadend, or otherwise; its maximum value is less than equal to 1. Therefore,
((B)
B S.
A.2 TIME COMPLEXITY ANALYSIS
Theorem 3 (Time Complexity of SGDNET) The time complexity of the 1-th SGD layer is mmKmd + nd(-1d;) where K is the number of diffusson steps. di is the feature dimension of the 1-th layer, and and are the namber of edges and nodes, respectively. Assuming all of di are set to d, SGDNET with I. SGD layers takes QLL mn + Land time.
O
Proof The feature transform operations require O(nd-1di) time due to their dense matrix mul- tiplication. Each iteration of the signed random walk diffusion in Equation (3) takes O(md) time due to the sparse matrix multiplication (-) where the number of non-zeros of B (m)). Thus, mm) is required for K iterations. Overall, the total time complexity of the I-th SGD layer is O(Kmd, + ndj-1di).
A.3 PSEUDOCODE OF SGDNET
Algorithm Tenrrtthmmmesseeee describes SGDNET's s overall procedure which is depicted in Figure Given signed adjacency matrix A and related hyper-parameterr (c.g., numbers L and K of SGD layers and diffusion steps, respectively), SGDNET produces the final hidden node features H(L) which are fed to loss function as described in Section 3.4 first computes the normalized matrices A., and A. (line 1). Then, it performs the forward function of SGDNET (lines 3 ~ 12). The forward function repeats the signed random walk diffusion K times (lines 6 and then performs the non con-lincar feature transformation skip-connected with H (!-) (line
Algorithm 1:
Pscudocode of SGDNET
Input:
signed adjacency matrix A, initial node feature matrix X, number K of diffusion steps, number L of SGD layers, and local feature injection ratio
Output: hidden node feature matrix (L)
1: compute normalized matrices for each sign, i.e., A = D D- and A = D-
2: initialize (0) with X
3: for 1 < 1 to L do
start the forward of SGDNET
4: perform the feature transformation as ( (
5: initialize p(0) with (!) and randomly initialized ( [-1,1]
6: for & < to K do
perform the signed random walk diffusion in Equation
7: ((k) - (1- (A (k-1) A [M + ()
8: (()) <- (1 AA
A (
9: end for
set (()) +- (() and M (K)
11: compute I-th hidden node features H (pan w! + ((-1))
12: end for
13: return (4)
13

---

Under review as a conference paper at ICLR 2021
A.4 DETAILED DESCRIPTION DATASETS
The Bitcoin-Alpha and Bitcoin-OTC datasets (Kumar et al. 2016 are extracted from directed online trust networks served by Bitcoin Alpha and Bitcoin OTC, respectively. The Slashdot dataset (Kunegis) et al.) 2009) is collected from Slashdot, a technology news site which allows a user to create positive or negative links to others. The Epinions dataset (Guha al. 2004) is directed signed graph scraped from Epinions, product review site in which users mark their trust or distrust to others.
The publicly available signed graphs do not contain initial node features even though they have been utilized as standard datasets in signed graph analysis. Due to this reason, many previous works (Derr et all.,,2011 2018b Li et al. 2020) on GCN for signed graphs have exploited singular vector decomposition (SVD) to extract initial node features. Thus, we follow this setup, i.e., X UΣa is the initial feature matrix for all GCN-based models where A U V is obtained by a truncated SVD method, called Randomized SVD (Halko et al. 2011), with target rank d, 128. Note that the method is very efficient (i.c., its time complexity Is ((nd)) where n is the number of nodes) and performed only once preprocessing in advance; thus, does not affect the computational performance of training and inference.
A.5
ADDITIONAL EXPERIMENTS ON WIKIPEDIA DATASET
0.88
0.8
0.7
F1-magro
F1-macro
0.78
0.7
0.6
0.78
0.7
0.6
0.74
0.80
@SGGNNer
(BSGON
APmp
Reasch
BatON Si.
BESDNe BNEA
APPPP
ReadON
sime
SLF
BSSON
GNEA
GEaNNe
2
4
8
10
0.72
0.5
Diffusion Staps
Local Injection Ratio
(a) Predictive performance (b) Predictive performance in terms of AUC
(c) Effect of the feature diffusion
(d) Effect of the local
terms of F1-macro
feature injection ratio
Figure 5:
Experimental results Wikipedia dataset.
We perform additional experiments on Wikipedia dataset (Leskovec et al. 2010b) which has been also frequently used in signed graph analysis. The Wikipedia dataset is signed graph representing the administrator election procedure in Wikipedia where a user can vote for (+) or against (-) candidate. The numbers of nodes and edges are 118 and 103, 675, respectively. Figure shows the experimental results on the dataset. As seen in Figures ( and and 5b) SGDNET outperforms other methods in terms AUC and F1-macro, respectively. Figure indicates our diffusion mechanism still works on the Wikipedia dataset. Figure shows the effect of the local feature injection ratio indicating properly selected e such as 0.5 is helpful for the performance.
A.6 EFFECT OF EMBEDDING DIMENSION
OSGDNet
* ResGGCN
BAPPNPP
4SLF SSGNN
+SNNAA
SIDE
0.85
0.85
0.9
0.89
0.85
0.85
AUC
0.80
0.65
0.8
0.75
0.75
0.75
0.7
0.7
0.55
23
24
29
2
24
25
24
23
g²
25
26
2
24
24
28
Embedding dimension
Embedding dimension
Embedding
Embedding dimension
(a) Bitcoin-Alpha
(b) Bitcoin-OTC
(c) Slashdot
(d) Epinions
Figure 6: Effect of the embedding dimension of each model.
14

---

Under review as a conference paper at ICLR 2021
We investigate the effect of the node embedding dimension of each model in the datasets listed in Table [ For this experiment, we vary the dimension hidden and final node embeddings from 8 to 128, and observe the trend of AUC in the link sign prediction task. As shown in Figure 6 SGDNET outperforms its competitors over all the tested dimensions, and it is relatively less sensitive to the embedding dimension than other models in all datasets except Bitcoin-Alpha.
A.7 HYPERPARAMETER CONFIGURATION
Table 4: We summarize the configurations of SGDNET's hyperparameters, which are used in the experiments of this paper.
Hyperparameter
Bitcoin-Alpha
Bitcoin-OTC
Slashdot
Epinions
Wikipedia
Number L of SGD layers
2
2
Local injection ratio
0.35
0.25
0.55
0.55
0.5
Number K of diffusion steps
10
Input feature dimension d; Hidden embedding dimension d:
128
32
Optimizer
Adam (leaming rate: 0.01, weight decay A: 0.001)
Number of epochs
100
15


Reviews:
[{"review_id": "g5KzPHdPDng", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Main Idea:\n\nIn this paper, the author studied the problem of node embedding in signed networks. The authors proposed SGDNet which combines the idea of diffusion/random work in signed networks and Residual connection in GCN. The network is trained directly with classification loss on edge sign prediction. The authors carried out extensive experiments on several real-world networks with comparison to several state-of-the-art methods. The proposed method showed superior performance in the sign prediction task.\n\nStrength:\nThe paper is technically sound and well written. The authors provide analysis on the convergence of the diffusion kernel to show that the injection of input signals prevents the degradation with depth increment.\nThe authors carried out thorough experiments on four real-world networks with comparison to several strong baselines.\nThe authors carried out parameter sensitivity analysis on two of the important parameters: diffusion depth and signal injection strength.\n\nWeakness\nThe authors trained the model and evaluated performance only on existing edges with signs. However, in practice, it is usually useful to predict the existence of edges or not in the network. It is interesting to see how the method generalizes to this situation which more resembles the graph reconstruction task.\nThe comparison of depth in SGCN with K is kind of unfair. A more direct comparison would be the number of layers L which controls the depth of the network. Since there are no trainable parameters involved in the diffusion step.\nThe authors mentioned that the embedding dimension is fixed to 32 for all methods. First, as an important hyperparameter, it is interesting to see how performance of different methods varies with it. Second, the embedding dimension of the proposed method is effective 64 as positive and negative are separated and combined.\n\nQuestions\nIn equation (2), what is the motivation to inject h only to positive but not the negative as well.\nHow is m^{(0)}_t and p^{(0)}_t initialized. Are they initialized to all zero?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VPFq0MXCWge", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to leverage signed random walk as hidden representation propagations to construct a signed graph diffusion network model. \n\nPros: \n1. The idea of the proposed model is simple but very effective according to the experiment evaluations.\n2. It's very interesting that the proposed model achieves better performance as the number of layers increases, even up to K=10.\n3. The writing of the paper is in a good shape and everything is clear to follow.\n4. The authors also prove the convergence of the proposed diffusion layer.\n\nCons:\n1. My major concern is the novelty of the paper. The key part of the model (i.e., signed diffusion layer) totally borrows from the existing work. Even the figure used in this paper is same as the reference paper (e.g., Figure 2 (a) in this paper vs. Figure 2 (b) in reference paper).\n      Jung, Jinhong, et al. \"Personalized ranking in signed networks using signed random walk with restart.\" 2016 IEEE 16th \n      International Conference on Data Mining (ICDM). IEEE, 2016.\n2. In addition, authors need to compare with the above paper as well as it's very effective in link prediction even though it's not an embedding-based method.", "extra_scores": {}, "extra_text": {}}, {"review_id": "R1fRpbLksm2", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents an interesting new graph neural network technique customized for the specific setting of signed graphs. This is a paper I have reviewed before.\n\nThere has been an increasing interest in the last several years on the problem of clustering/link prediction/representation learning of signed graphs, where edge weights are allowed to take either positive or negative values. The main contribution is the end to end pipeline targeted at link sign prediction and the feature diffusion step. The signed random walk diffusion is neat, and appears to be new I believe, in this context. The numerical results are somewhat convincing, with improvements in the single digit percentages; on some data sets fairly small, but consistent improvement across the board. There is some theoretical component, which is rather light, but this is fine.\n\nMight have been good to compare against non GCN based methods, for example \nChiang, Kai-Yang, et al. \"Prediction and clustering in signed networks: a local to global perspective.\" The Journal of Machine Learning Research 15.1 (2014): 1177-1213.\nPerhaps also worth placing this work in the context of some of the growing literature of signed clustering/link prediction that typically rely on spectral methods/matrix completion. However, since the authors already compare against non-GCN methods and it is fine to leave this for future work. \n\nIt would have been good to see a comparison on synthetic data as well. There exist signed stochastic block models which have been looked at, which could be augmented with features, or use no feature information at all. Another compelling story could be made around better clustering performance, by leveraging the embedding obtained via the authors’ proposed approach. There is a growing literature on clustering signed graphs, and it would be interesting to see to what extend the proposed method embedding is applicable in that setting and how cluster recovery performance looks like. \n\nRegarding the features - they play a central role in the paper, but towards the end the reader finds out that the input signed graphs do not have initial node features.. It would be have been good to identify a data set where the nodes come with some covariate information. Or, as stated above, a synthetic model could be put forth, with a set (or subset) of features which correlate with cluster membership/edge sign. \n\nIn SBM model, it would be interesting to see how does the link prediction accuracy vary with the number of clusters, and also the graph sparsity. Most spectral methods out there for this task face difficulties when handling very sparse graphs (ie, typically below the threshold connectivity limit of (log n)/n, both theoretically and empirically, and require various regularisation techniques). It would be good for the authors to comment on this aspect (very sparse graphs), as it could be a strong edge over spectral methods which tend to underperform in the very space regime.\n\nMight also be interesting to comment on how seed information could be used, if available? See for example some of the literature on polarization in signed graphs. \n\nOverall the paper appears to be technically sound, clearly written and very well structured, and I think overall a good addition to the signed network embedding literature.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-DrNlWUCLi8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The strength:\n\n- Empirical results show improvements of the proposed method over the baseline methods, including methods for unsigned graphs, signed embedding emthods, and signed GCN methods not addressing over-smoothing.\n\nThe weakness:\n\n- The proposed method is a straightforward integration of existing methods on signed graphs and on handling over-smoothing in GCNs. There is very little new idea in the proposed method.\n\n- The convergence result (Theorem 1) is straightforward based on linear algebra, and it is only for the diffusion part in each GCN layer. There is no overall theoretical results on the SGDNet architecture.\n\nOverall, the method proposed is a simple combination of past methods on handling signed graphs and handling over-smoothing in graphs. It is just that the two has not been combined together, and so the only contribution I see is the combination of these two methods and verify it in the signed edge prediction task. The theoretical result on convergence is only on the diffusion convergence at each layer, and it is a straightforward application of the linear algebra. It is unclear to me why we need a diffusion convergence at each layer and then also need GCN with multiple layers. What is the connection between the diffusion steps K and the GCN layers L? \n\nIn summary, the paper shows improvement when combining previous methods on signed networks and on handling over-smoothing. It may fit into a second-tier conference to record the result, but I feel that it does not meet the high bar of ICLR.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses an interesting problem of clustering/link prediction/representation learning of signed graphs, where edge weights are allowed to take either positive or negative values. The paper proposed an end to end pipeline targeted at link sign prediction and the feature diffusion step. The reviewers think the proposed method is a straightforward integration of existing methods, and the convergence result is straightforward. The paper can be improved by including more novel ideas or analysis. 
Decision: Reject