Signed Graph Neural Networks: A Frequency Perspective
Authors: Rahul Singh
Yongxin Chen
Venue: Accepted by TMLR ()

Abstract: Graph convolutional networks (GCNs) and its variants are designed for unsigned graphs containing only positive links. Many existing GCNs have been derived from the spectral domain analysis of signals lying over (unsigned) graphs and in each convolution layer they perform low-pass filtering of the input features followed by a learnable linear transformation. Their extension to signed graphs with positive as well as negative links imposes multiple issues including computational irregularities and ambiguous frequency interpretation, making the design of computationally efficient low pass filters challenging. In this paper, we address these issues via spectral analysis of signed graphs and propose two different signed graph neural networks, one keeps only low-frequency information and one also retains high-frequency information. We further introduce magnetic signed Laplacian and use its eigendecomposition for spectral analysis of directed signed graphs. We test our methods for node classification and link sign prediction tasks on signed graphs and achieve state-of-the-art performances.

Published in Transactions on Machine Learning Research (02/2023)
Signed Graph Neural Networks: A Frequency Perspective
Rahul Singh
rasingh
Machine Leorning Center
Georgia Institute of Technology, Atlanta
Yongxin Chen
yongchen @gotech. yongchen@gatech.com
edu
School of Acrospace Engineering Georgia Institute of Technology, Atlanda
Reviewed on OpenReview: htips: // openreview. net/ mett forum? id- RZve Zbu
Abstract
Graph convolutional networks (GCNs) and its variants are designed for unsigned graphs containing only positive links. Many existing GCNs have been derived from the spectral domain analysis of signals lying over (unsigned) graphs and in each convolution layer they perform low-pass filtering of the input features followed by learnable linear transformation. Their extension to signed graphs with positive as well as negative links imposes multiple issues including computational irregularities and ambiguous frequency intorpretation, making the design of computationally elficient low pass filters challenging. In this paper, we address these issues via spectral analysis signed graphs and propose two different signed graph neural networks, one keeps only low-frequency information and one also retains high-frequency information. We further introduce magnetic signed Laplacian and use its cigendecomposition for spectral analysis of directed signed graphs. We test methods for node caasificatiion and link sign prediction tasks signed graphs and achieve state-of-the--a performances.
1 Introduction
Graph neural networks (GNNs) learn powerful node representations by capturing local graph structure and feature information [Ma & Tang 2021 Wu et al. 2021). The existing GNN architectures have focused almost exclusively on graphs with nonnegative edges, which encode some kind of similarity relation between the incident nodes. In contrast, negative edges are often useful to model dissimilarity relations (Kumar et al., 2016 Dittrich & Matz 2020): for instance, in social networks, users may have common political views, trust//dittrus one another's recommendations, can be modeled using signed graphs by allowing the edges to take both positive negative values. In this paper, we are interested in GNN designs for signed graphs.
like disllikkkkee cach other. Such dissimilarity relations
There exist several methods such as SGCN Derr et al. 2018 SiGAT (Huang et al. 2019 and SNEA et al. 2020 that consider signed links to learn node embeddings in a task-specific end-to to-end end manner. These GNN based models are based on structural balance theory for signed graphs (Heider 1946 Cartwright Harary 1956). In this work, we propose an alternative solution to GNNs for signed graphs from a frequency perspective via spectral domain analysis. Recall that the spectral domain analysis of unsigned graphs has been widely used to develop GNN architectures. Many well-known GNNs including spectral-GNN (Bruna ct al. 2014h, ChebNet (Defferrard et al.) 2016), GCN (Kipf & Welling 2017). AGCN (Li et al. 2018). and FAGCN (Bo et al., 2021) rely on spectral domain analysis. These designs are based on the frequency interpretation derived from the eigendecomposstionn of the normalized unsigned graph Laplacian. However, direct application of the existing spectral domain GNN designs to signed graphs is problematic, mainly due (i) possible zero diagonal entries in the degree matrix making the normalization of the Laplacian prohibitive and (ii) possible negative eigenvalues of the graph Laplacian, making the frequency ordering

---

Published in Transactions on Machine Learning Research (02/2023)
Table Different Laplacians and their applicability.
Unsigned
Directed
Signed
Directed Signed
Laplacian L
/
Magnetic Laplacian L Signed Laplacian T, Signed Magnetic Laplacion L
/
x
/
/
somewhat ambiguous, i.e., whether the smallest negative, positive, or absolute value, eigenvalues should be used as low frequency (Knyazev] 2017).
To address these issues, we turn lo signed graph signal processing (Dittrich & Matz 2020 which provides frequency interpretation for features lying on the signed graphs, and propose spectral domain signed GNNs based on it. Specifically, we propose two different GNN designs for signed graphs: Spectral-SGCN- and Spectral-SGCN-II. The former considers fixed low-pass filter keeping ouly low-frequency information during aggregation process, whereas the later is based on attention mechanism retaining low as well as higl-frequency information. Extending these methods to directed signed graphs is another challenge. For handling directed signed graph, we further introduce spectral methods for directed signed graphs. We evaluate the performance of our methods on node classification and link sign prediction lasks signed graphs. Our contributions are summarized below.
We present principled approach to designing graph neural networks for signed graphs based on the spectral domain analysis over signed graphs.
We instantiate our approach with two graph neural network architectures for signed graphs, one behaves like a low-pass filter and one also retains high-frequency information.
We introduce signed magnetic Laplacian (see Table for spectral analysis of directed signed graphs and utilize it in feature aggregation process.
We evaluate method through extensive evaluations node classification as well as link sign prediction tasks for signed graphs and achieve state-of-the-art, performances.
There exist many different methods to learn node representations (embeddings) on signed graphs. Most of these methods are derived from the balance theory (Cartwright & Harary 1956) that was motivated by social networks. The balance theory concept was inspired by the sociological observations that friends (enemies) of my friends are also my friends (enemies), and enemies of my enemies are my friends. Alternatively, balance theory is shown equivalent to simple assumption that the nodes in a signed graph can be divided into two conflicting groups. The existing signed graph embedding methods can be classified into two categories: signed netw embeddings and GNN based methods. Signed network embedding hoth including SiNE (Wang et al., 2017). SIDE (Kim et al., 2018), SIGNet (Islam et al., 2018), SLF (Xu al.) 2019), and ASINE (Lee et al., 2020 learn node reprosentations in task-independent manner that nodes connected via positive links in close proximity to each other, whereas nodes connected via negative links are distant from each other. SiNE (Wang et al. 2017) learns signed net work embedding with an objective function guided by the balance theory, while SIDE (Kim et al. 2018) and SIGNet (Islam et al. 2018)) use specifically designed random walks to model the balance theory. Moreover, SLF (Xu et al.) 2019) also performs two types (i.e.; positive and negative) of node embeddings for each target node and takes a combination of the two node embeddings as the final node embedding. These node emboddings are then used for task in hand separately.
Related Work:
GNN based methods including signed graph convolutional networks (SGCN) (Derr al. 2018 signed graph attention networks (SiGAT) (Huang et al. 2019). signed network embedding based on attention (SNEA) (Li el al. 2020), and are jointly trained to learn node embeddings along with the task in hand in an end-to-end manner. SGCN is a state-of-the-ar the-trt signed GNN model considering balanced and unbalanced paths motivated
from the balance theory to aggrogate local graph information with fixed coefficients. SNEA further extended
SGCN to incorporate learnable attention coefficients for aggregating balanced and unbalanced paths. SiGAT is motif-based GNN model to learn the node representation inspired by GAT (Velicković al. 2018
2

---

Published in Transactions on Machine Learning Research (02/2023)
Prodictions
Spectral-Signed-Ge
8 1:
Input graph and features
Predict node class
Spectral Fittering
Feature Transformation + Non-linearity
Predict link sign
X
PH
H a (H 6
Figure Spectral Signed GNNs. In the signed graph, Red color edges represent negative links and Green color edges represent positive links. The spectral signed GCN filters and transforms the features repeatedly throughout L. layers and then applies linear prediction.
These methods are not applicable to directed signed graphs. SDGNN (Huang et al. 2021 is a recent work applicable to signed directed graphs based on balance and status theory. SSSNET (He et al., 2022b) is another GNN based work with focus on the clustering of signed graphs. Recently, after this work was completed, we came to know about concurrent work Magnetic Signed GNN (MSGNN) (He et al. 2022a that also utilizes spectral domain approach. The focus of it is on directed signed graphs.
For balanced graphs, the cigenvectors of the signed Laplacian follow certain properties as analyzed in (Dittrich & Matz 2020). However, it is difficult to relate the signed spectral analysis with balance theory in case of unbalanced graphs. It is an interesting problem to explore the relationship between balance theory and spectral analysis for unbalanced graphs which out of scope of this work.
2 Problem Definition
Given a (directed) signed graph along with input node features, the goal is to learn low-dimensional latent node features (embeddingg)). These features are subsequently used for specific lask such as node classification and link sign prediction. Let g (V, E U be directed signed graph, where V is the of N number of nodes, E is the set of directed positive edges, and -- is the set of directed negative edges. The adjacency matrix of the graph is denoted as A E N*N and has entries from {+1, -1, If (i,j) is not an edge of the graph, then the corresponding entry is Aii,)) 0. Aii,j +1 denotes positive edge from node to j, whereas A(i,j) = denotes negative edge from node i to j. The input node features are represented as a matrix X E IR NxF with x; E R (column of X) representing the ęth feature channel of X and F denotes the total number of feature channels.
As depicted in Figure ! in each GCN layer the input features are first filtered and then (linearly) transformed followed by non-linear activation. In the fth GCN layer, the linear transformation part contains learnable parameters (f), After L number of GCN layers, the latent features are fed to the prediction head, which can be designed to either predict node labels or predict link signs. For both node label prediction (node classification) and link sign prediction tasks, cross-entropy loss can be used based on the available labels and signs, respectively. The spectral filtering operation in each signed GCN layer the main focus this work.
3 Preliminaries
Popular spectral domain designs of graph neural networks including ChebNet (Defferrard et al. 2016), GCN Kipf Welling 2017) and their further improvements such as AGCN (Li et al. 2018). Simplified GCN WW et al. 2019), and FAGCN (Bo et al.] 2021) are based on the spectral analysis signals (features) defined on an unsigned graph. The spectral analysis of graph signals has been studied under the umbrella
of the graph signal processing (GSP) framework (Shuman al.] 2013 Ortega et. al. 2018 Manoj et al.
3

---

Published in Transactions on Machine Learning Research (02/2023)
When the graph is signed, these existing spectral GNN methods encounter multiple challenges. In this section, we briefly discuss how spectral domain analysis of graphs is used for spectral domain GNN designs and point out the issues when dealing with signed graphs.
2018).
3.1 Graph Fourier Transform and Spectral Filtering
GSP is concerned with the generalization of classical signal processing concepts and tools to graph signals. GSP relates the verlex and spectral domains of a graph, much as classical signal processing connects the time and frequency domains of a time series (Cheung et al.) 2020). The eigenvalues and eigenvectors of the (unsigned) graph Laplacian provide a notion of frequency for signals defined on graph. The graph Laplacian cigenvectors associated with low frequencies, vary slowly across the graph, i.c., if two vertices are connected by an (unsigned) edge, the values of the eigenvector at those locations are likely to be similar. The eigenvectors associated with larger eigenvalues oscillate more rapidly and are more likely to have dissimilar values on vertices connected by an edge. The graph Fourier transform and its inverse give us way to equivalently represent a signal in two different domains: the verlex domain and the graph spectral domain.
The graph Fourier (spectral) analysis relies on the spectral decomposition of graph Laplacians. The traditional ,d3 and d, = -E Arj Based on the eigendecomposition of the graph Laplacian
combinatorial graph Laplacian is defined as L D A, with = diag its normalized version is Ln D DD-1/LDD-J == UAU", where U E IP N comprises of orthonormal eigenvectors and A = diag.Ai...... Av } is diagonal matrix of eigenvalues, the graph Fourier transform is defined with eigenvectors of the graph Laplacian being the graph Fourier modes (harmonics) and the corresponding cigenvalues being the graph frequencies (Shuman et al. 2013). Assuming À S >2 S ... S AN, Å corresponds to the lowest (zero) frequency and Av corresponds to the highest frequency of the graph. For the case of normalized Laplacian Ln, all the graph frequencies lie in the range [0 (Shuman et al. 2013 ; with d 0.
Let E R. be single-channel input signal on the graph, then the graph Fourier transform and the inverse Fourier transform are defined as x = U"x x and x = UX, respectively. Graph convolution of the input graph signal x with a filter g is
x x = U ( = UGU"x.
(1)
where G = diag(g) = diag(A IN h and @ denotes element-wise multiplication.
3.2 Spectral Domain GNN Designs
The graph convolution given by ① is used in GNNs to learn filters in the graph spectral domain. Spectral- GNN Bruna et al.] (2014) learns all the filter coefficients, which requires full cigendecomposition of the Laplacian matrix and is very expensive. For computational efficiency, the filter coefficients .1..... 99N can be approximated via Wth order polynomials of the graph frequencies (K << N), i.c., 9(A,) = = 0:25 with 0 E RK+1 being the (polynomial) filter coefficients. Then the graph convolution with such polynomial filter takes the form
K Σ 0,A0 U
K
x x* U
x= Σ O,L,X ==0
(2)
Note that the polynomial filters allows us to write graph convolution in spatial domain via polynomial in the graph Laplacian. ChebNet. (Defferrard et al. (016) proposed to approximate the graph convolution via K order Chebyshev polynomials. In GCN, (Kipf & Welling 2017) simplified the graph convolution by assuming first order polynomial filter (K = 1) with By = 20 and 01 = 0, and thereby reducing the graph convolution to
x * g (21 LL,) x= - D 1-12A 112) x.
As a different interpretation, the above can also be viewed as a combination of two operations: (i) Feature aggregation via term (I + D 1/2 11/2) and (ii) Feature transformation via learnable parameter Note that the feature aggregation operation corresponds low pass filtering since the spectral response of the spatial filter 21 Ln is ğ()) = 2 x which amplifies low-frequency signal (A ss 0) and restrains high-frequency signal (A 2s 2). Tn its final design, for numerical stability, the feature aggregation operation in GCN is modified
4

---

Published in Transactions on Machine Learning Research (02/2023)
g(A)
-3.34 -1007 0.81
P.L. of ioe (c)
[111 1]" for L
(a)
(b)
(d)
Figure 2: (a) A toy signed graph (Rod color edges represent negative links and Green color edges represent
positive links), (b) corresponding low-pass filter based on the unnormalized Laplacian, (c) Eigenvectior
correspouding to the lowest frequency based on the unsigned Laplacian, and (d) Eigenvector corresponding
to the lowest frequency based on the signed Laplacian.
by adding self-loops for each node and as a result the modified graph convoluttonn takes the form Kipp & Welling 2017 Wu et al. 2019
x g R. (D 11-1/2AD 1/2) x,
where À = A + and D = I When generalized to multi-channel input X, the output of the 4th layer of the GCN reads
- H (8-1)
O (0))
H (0) =X,-
(5)
where P = 1-112 1/2 is the low-pass feature aggregation filter, ( is a learnable transformation matrix, and a is non-linearity such as ReLU.
3.3 Issues with Signed Graphs
In each GCN layer, the feature aggregation operation corresponds to low pass filtering with the filter being first order polynomial in L, However for signed graphs, the inverse of the degree matrix D (or D) becomes problematic since the degree values might be zero negative values for some nodes and a consequence the normalized Laplacian L, is not well defined. Since the normalized Laplacian is not well defined, one is tempted to interpret the aggregation operator as a low pass filter based on unnormalized Laplacian L. This again poses difficulty in frequency ordering as the cigenvalues of the Laplacian can take negative values for signed graphs. The graph frequencies (Laplacian eigenvalues) are ordered based on the total variation (TV) of the corresponding eigenvectors on the graph (Sandryhaila & Moura, 2014 Ortega et al. 2018). TV quantifies global smoothness (or variation) of a graph signal. For unsigned graphs, the quadratic form Lx is often used as TV of signal x the graph (Shuman et al., 2013). However for signed graphs, the quadratic form LL may take negative values and thereby invalidating ils use TV. Another definition of TV of a graph signal x is (Singh et al. 2016) TV(x) = ||]x|| and it can be shown that TV(u;) > TV(u;), if [Ag] > IAyl- Thus the eigenvalues with smaller absolute values act as low frequencies and vice-versa.
Although one can order the signed frequencies based on the absolute eigenvalues of the graph Laplacian L, one nceds new designs of low pass filters to be used as aggrogation operator. For example, a low pass filter for the toy graph in Figure 2a with frequency response ğ(A) = 1 Malma is the maximum absolute frequency of the underlying graph. This filter design has certain drawbacks since it requires computation of |Mmax and cannot be directly realized as a first order polynomial (in the graph Taplacian) the spatial domain as the latter corresponds to straight line. One can go for higher order filters with additional computational cost.
AAL is shown in Figure 2b where [X] max
Moreover, the frequency interpretation also becomes ambiguous for signed graphs. Since the zero eigenvalue being the lowest frequency and the corresponding eigenvector being constant signal on the graph (as shown in Figure 2c). it is intuitive only under similarity assumption (i.c. positive edges). For example, focs/ /enemiisss (users connected via negative links) having similar opinions (Iraits or features) suggests a high amount of variation and friends (users connected via positive links) having similar opinions constitutes small variation. However, this intuition is violated when using unsigned Laplacian: lowest frequency cigenvector values at nodes and 3 connected via negative links in Figure 2c] have the same values. Our proposed methods address these issues to design interpretable spectral domain signed GNNs.
5

---

Published in Transactions on Machine Learning Research (02/2023)
4 Proposed Method
In this section we present our spectral domain analysis approach to graph neural networks for signed graphs. We then instantiate the approach to two specific network designs.
4.1 Spectral Domain Analysis of Signed Graphs
To address the issues mentioned in Section 3.3 while retaining the frequency interpretation of the aggregation
operation, we turn to the signed graph signal processing (Dittrich & Matz 2020). Instead the standard
graph Laplacian, we consider the signed Laplacian matrix (Kunegis al., 2010 Dittrich Matz, 2020
L L A, where D fia..d]...... dy }o is a diagonal matrix with d; Σ, Atyl. In (Dittrich & Matz 2020 the authors formalized the spectral domain analysis of the signals over signed graph via eigendecomposiiion of the signed Laplacian matrix with the eigenvalues being the signed graph frequencies and the corresponding cigenvectors being the signed graph harmonics.
More precisely, we consider the normalized signed Taplacian matrix
L D LD 1/2 - D 1/2 AD 1/2
The eigenvalues of the normalized signed Laplacian lie the range [0. 2] with smaller eigenvalues corresponding to low frequencies, and vice-versa. This frequency ordering directly follows from using quadratie Laplacian form
TV(x) = = =x
(7)
the definition of TV signed graphs Using the eigenvectors of the signed Laplacian graph harmonics provides natural frequency interpretation for signed graphs. The eigenvector corresponding to the lowest frequency of signed graph is shown in Figure 2d It can be seen that the nodes connected via negative links (foes) have opposite values and nodes connected via positive links (friends) have similar values thereby exhibiting small amount variation; this phenomenon is intuitive for being a low frequency signal.
Our approach to signed graph neural networks naturally follows by redefining graph convolution based on the normalized signed Laplacian in (6. Building this idca, we propose below two specific graph network designs for signed graphs: Spectral-SCCN- and Spectral-SCCN-II. The former behaves like low-pass filtering and can be viewed signed graph counterpart of the vanilla GCN (Kipf & Welling 2017). The latter is able to retain high-frequene information and can be viewed as a signed graph counterpart of FAGON (Bo et al. 2021.
4.2 Spectral-Signed-GCNN
Our first network design, Spectral-SGCN-I, is similar to the vanilla GCN Kipf & Welling 2017). p. It can be viewed as a low-pass feature aggregation on the underlying signed graph followed by feature transformation. At cach layer, the features are first aggregated via. low-pass filter P D-1/2 and D D + renormalization trick to improve mumerical stability (Kipf & Welling
1/2 AD-1/2 with Á A
It resembles (4) but uses the signed Laplacian. Note that, just like we adopt the
2017
In more details, the aggregated features in 4th layer is H = (H) Let H = [h h then the aggregation can be written in the message passing form
h (
d (E-1)
1
h
+ E
Σ REN,
h (1-1)
JENT
V (d. 1)(d, +1)
(d: + 1)(da +1)
A fter aggregation, the features are transformed via a learnable parameter matrix along with non-linearity to give node representation output in 4th layer as H = a (H (+))
The Spectral-SGCN-I aggregates only low frequency information via a low-pass aggregation filter as illustrated
in Figure 3al As it has been shown in (Wu et al.] 2019: that removing nonlinearities and collapsing

---

Published in Transactions on Machine Learning Research (02/2023)
Bop (-ba)
(h,)
B,
Low-pass
Low-puss
(-ha)
(h Low-pass
Low-pass
Bu 0 High-pass
High-pass 3g (-h,)
(he)
(a) Spectral-SGCN-I
(b) Spectral-SGCN-II.
Figure 3: Spectral-SGCN-I propagates only low-pass information from its neighbors. Spectral-SGCN--I propagates low-pass as well as high-pass information from its neighbors via attention cocfficients.
weight matrices between consecutive layers greatly simplifies the GCN complexity. Similarly, we propose spectral simplified signed graph convolution network (Spectral-S2GCN) such that the output of gth layer is H = - with θ being the only learnable parameter matrix.
4.3
GCN-1I
As has been noted FAGCN [Bo et al. 2021 , besides low frequency components, it is beneficial to incorporate the high frequency components during feature aggregation as well. Based on this idea and the frequency interpretation on signed graphs, we extend FAGCN to signed graphs by considering low as well as high frequency information. To this end, we use low pass filter plow I D AD /2 21 L, and high pass filter HHig I D 1-2 AD AD-1/2-- L, along with attention to learn the proportion of low-frequency and high-frequency features to be propagated.
Let Blow be the coefficient of attention aggregation for low frequency features from node j to node i. Similarly, let { gllighh be the coefficient of attention aggregation for high frequency features from node j to node i. Note if node i not connected to node j. For larget node i, define low-pass atlention matrix Blow diag Low
B Pij
aLow } and high-pass attention matrix as Bligghh diag (3 ....,, ....,,eN"" Highy, Let ...... IN
(e-11) 1) [h (c-1) hg (e-1) h 11-1)T be the node embeddings at layer & e 1, then the gth GNN layer reads
(assuming self-loops)
h
(E)
pLoW B Low H(e (())))
(Highh Hlghh (iigghlBBiHHHH((e---- (((-1)) -Hiihh
2
(3/gmm -Big
gHigh (e-1)
= (sLow + Highh (t-1)
h
(e-1)
Σ
ik
h2
V dedj
v djdy
jEA+
KEN
The coefficient f15m + shiish acts as a scaling factor and can be set to be for simplicity. Now denote 5 AHtigh Big. then the above becomes
h h. (1-1)) Σ 3rg
(1-1)-
Σ
hB Bik (e-1)
(8)
JEN!
V d:d
MEN-
V d,d4
When the attention coefficients are constant and equal to 1, the above reduces to Spectral-SGCN-T, Tn
Spectral-SGCNNII, the attention coefficients learned as Bi tanh (a h,]) taking values in range [-,, where a is learnable linear parameter. When By = 31 - HHigh > O, the low-frequency information is propagated from node j node and when Bi 0, the high frequency information is propagated, illustrated in Figure 3b Before passing the given input features X to the first layer, they are first.
transformed to get h (0ix;) and after L number of stacked layer, we get the final output embeddings
h, (2h(4) (4)

---

Published in Transactions on Machine Learning Research (02/2023)
Im
2mg
4/
40
e 2e0
Figure 4: Illustration of different directed signed scenarios and signed directional phase locations on complex plane with 0.125.
5 Directed Signed Graphs
The methods proposed in Section 4 are limited to undirected signed graphs. For unsigned graphs, the magnetic Laplacian (Fanuel et al. 2017 2018 Furutani et al. 2019 has been utilized to encode the edge directionality information. Recently, Zhang et al. (2021) used magnetic Laplacian for designing GNNs for directed (unsigned) graphs. In its original form, the magnetic Laplacian defined as
= = Ag o $9
(9)
where A, is symmetric adjacency matrix with entries A.i),) (A(,))) A(j,)), D diag(d1, d2, ................................ dNF with de = - Ai(i,)). Moreover, 4 is a Hermitian matrix with elements
Φ0(i.)) (0oo(
(10)
where is an indeterminate satisfying 2² = - and (.,0. is the phase parameter. The normalized magnetic Laplacian is Lg D D 1/2
It can be shown that L as well as Lg are positive semidefinite for the unsigned case and the cigenvalues of Lg lie the interval [0, 2]. However, when the underlying graph is signed, the degree matrix can have zero diagonal entries and the normalized magnetic Taplacian not well defined. Moreover, L becomes indefinite matrix for signed graphs. To handle these issues in directed signed graphs, we introduce signed magnetic Laplacion.
5.1 Signed Magnetic Laplacian
We define signed magnetic Laplacian as
L A D A. 2
(11)
where A o t8 contains the directional signed information via 49 and the degree matrix is considered to be D diag(d;, .2...., dy. with d; ΣØ= (i.)))) representing the connection strength of node i. Note that the phase parameter E [0, 0.25) for this signed directed settings (see Figure 4 for illustration of different scenarios). The normalized signed magnetic Laplacian is Lg = - 1-12 The eigendecomposition of Lg can be used for spectral analysis of directed signed graphs and directed signed convolution operations can defined as Section 3.2, The spectrum of our signed magnetic Laplacians follow desirable properties as given by the following propositions (sce Appendix for proofs).
Proposition The signed magnetic Laplacian L and normalized signed magnetic Laplacian Lg are positive semidefintt.
Proposition 2. The eigenvalues of the normalized signed magnetic Laplacian Lg lie in [0,2].
8

---

Published in Transactions on Machine Learning Research (02/2023)
5.2 Directed Signed Graph Convolution Network
Based on signed magnetic Laplacian, similar to MagNet (Zhang el al. 2021 we propose Signed-MagNet.. In its aggregation operation, Bgmed-MagNee aggregates features by performing low-pass filtering as
(i, hy ((-1)
h
(e-1) +1 h
Σ
(12)
d;
JEN; (d. 1)(d +1
where N₁ is the set of all the nodes connected to/from node i. Note that the latent embeddings in signed- MagNet are complex and at the last layer, we concatenate the real and imaginary parts. After aggregation operation each layer, the features are transformed via a learnable complex matrix O.
Remark 1. Note that we also eztend attention mechanism described in Section 4.3 to directed signed
graphs in order to take low as well as high frequency information into account.
6 Experiments
We evaluate our proposed methods for node classification and link sign predictions tasks on signed networks. We used Deep Graph Library (DGL) (Wang et al. 2019) for implementation our methods. We also utilized
PyTorch Geometric Signed Directed (He et al., 2022c for implementing existing signed GNN baselines for
node classification tasks. The code is available at https://githi: http://ggghhai....maaaaaaiiiaaaa cttm://aaulltgggccccamaaaaeeeaaa
Signed_GNN
6.1 Datasets
We perform node classification task on three datasets: Wiki-Editor, Wiki-Election, and Wiki-RíA. Wiki-Editor is extracted from the UMDWikipedia dataset (Kumar et al. 2015 There is positive edge between two users if their co-edits belong to the same categories and a negative edge represents the co-edits belonging to different categories. Each node is labeled as either benign or vandal. Wiki-RfA (West et al., 2014) and Wiki- Election [Leskovec et al., 2010p are datasets of editors of Wikipedia that request. to become administrators. A request for adminship (RfA) is submitted, either by the candidate or by another community member and any Wikipedia member may give supporting, neutral, or opposing vote. From these votes signed network is built for each dataset, where positive (resp. negative) edge indicates supporting (resp. negative) vote by a user and the corresponding candidate. The label of each node in these networks is given by the output of the corresponding request: positive (resp. negative) if the editor is chosen (resp. rejected) to become an administrator. We use dataset extraction code provided by Mercado et al. 2019
For link sign prediction, we use three additional datasets: Bitcoin-Alpha, Bitcoin-OTC, and Slashdot 2 Bitcoin-Alpha and Oitcoin-OTC (Kumar et al., 2016 2018) are two exchanges in Bitcoins, where nodes represent. Bitcoin users and edges represent the level of /distrdist they have in other users. A positive edge implies trust, while a negative edge represents distrust (fraud). Slashdot dataset (Kunegis et al. 2009 is a network of interactions among users on Slashdot. Nodes represent users and edges represent friends (positive) or foes (negative). See Appendix C for more on the dataset statistics.
6.2 Results
We first present experiments on synthetic data generated by signed stochastic block model Cucuringu el al.] (2019; ; He et al. (202bb) with different levels of imbalance. We simulate two clusters with intra-cluster edge probability of 0.02 having positive signs and inter-cluster probability of 0.01 having negative signs. Such a graph is balanced graph. We then flip the inter-cluster as well as intra-cluster edge signs with different probabilities q creating varying levels of imbalance. With only 2 node labels known per cluster for total of 1000 nodes, the node classification performance is shown in Figure 5 (one hot vectors input features and hidden dimension of 16). Binary cross-entropy loss based on the known labels is used as a loss function.
Clearly, our proposed methods outperform SGCN (Derr et al. 2018 and SNEA (Li et al. 2020 significantly.
httpps///ghhab..cm//mmepee///// hhttps///netwwokkkseeewww
9

---

Published in Transactions on Machine Learning Research (02/2023)
1.0
closs
class 2
Accurgcy Securgy
Spectral
0.8
Spectraltt
SOCN
0.6
flip signs with probability
0.0
Imbalance level
0.2
0.4
Figure 5: Performance with varying levels of imbalance.
Table 2: Test accuracies averaged over 20 different seeds for data shuffles and initializaaionss
Datases
WidEdditor
W WildElection
WIKIREA
%
GON
73.0 1: 0.8
73.3 0.8
74.5 4: 1.0
85.9 2 3.4
89.8 4: 3.7
89.9 2: 3.8
88.1 1: 2.2
89.4 3.3
80.0 1: 2.8
SAGE
70.3
72.8
76.1 0.5
1.2
87.9
89.9
98.3
PAGON
78.4 1-1
77.2
78.8
92.1 1.4
80.3 1: 0.9
95.4 0.7
81.5
92.4
84:1
SGCN
78.4 1111000
80.3
82.1
87.5 1.2
0.7
93.8 0.4
87.9
89.5
01.3
79.5
79.9
1.3
98.0
94.0
94.4 1.2
3DGNN
80.5 1.3
81.1 0.8
62.3 0.7
95.8 = 1.0
86.1 1: 0.6
96.7 2: 0.8
84.88 4: 1.1
95.0 0.7
R5-3 0.4
SpectralSGONN11
9 Specinl--CCCN-1
80.0 00.0 2.2
80.0 1.6
$2.8
06.7 = 1.0
97.4 # 0.8
08.0 #: 0.3
94.0 0.4
96.0 0.4
96.0 0.2
Spectral-S2GC
81.1
81.8
82.7
96.6 1: 0.9
97.3 1: 0.5
97.88 0.2
94.3
95.2
85.9
Sagned-MagNet
81.0
82.0 1: 0.8
83.0 1: 0.4
47.2 1: 0.6
97.6 d:
98.0 2: 0.2
96.0
98.2 0.3
966.4 1: 0.2
6.2.1 Node Classification
Next, we perform node classification task in semi-supervised setting, i.e., have access to the test data, but not the test labels, during training. For all the three datasets, use three different rat for training (known labels): 1%, 2%, 5% of the total nodes. Out of the remaining nodes, we use 90% for testing, and use rest of the nodes for validation. Since the features are not given for the nodes, we use truncated SVD of the symmetric adjacency matrix with dimension of 64 as input features. For comparison, we use traditional unsigned GNN designs namely GCN (Kipf Welling, 2017), GraphSAGE (Hamilton et al. 2017]. and FAGCN (Bo al., 2021). For these methods, do not consider the sign of the links, since the signed edge information is not applicable for these methods. We also use the state-of-the ofetth-rtttetttt GNN designs based balance theory including SGCN DDerr et al. 2018 SNEA (Li et al. 2020). and SDGNN (Huang et al. 2021 for comparison. For fair comparison, we use two layer networks with hidden dimension of 64 for all the GNN-based methods. Binary cross-entropy loss based on the known labels is used as a loss function. We use ReLU as the non-linearily function between the layers. Adam is used as the optimizer along with Ez-regularization to avoid overfitting. We tune the learming rate and weight docay (f--regularization) hyperparameters over validation data using a grid search. For Signed-MagNer implementation, we fix q = 0.125 for all the experiments. Further details on implementation and hyperparameter tuning are provided in Appendix.
The classification results are summarized in Table 2 The experiments were run for 300 epochs and the results are averaged over 20 different random splits of training and test data. The average of best accuracies along with the standard deviation over 20 runs is reported. The best performing model for each dataset is in bold. We observe that our proposed signed GNNs consistently outperform the other methods all the three datasets. For the two datasets Wiki-Election and Wiki-RfA, even traditional methods without signed information outperform SGCN.
6.2.2 Link Sign Prediction
Finally, we evaluate our methods for the task of link sign prediction that aims to predict the missing sign of a given edge. There exist three type of links in a signed graph: positive link, negative link, and no link. Denote this as set S E (+,-,?) -.?), with "?" represonting no link. Specifically, the training data contains sot of nodes V, and pairs and Sax E S denoting type of link between u and The final embeddings (obtained from the GNN
of link triplets T consisting of triplets of the form (u, v, suv) with u, being node
10

---

Published in Transactions on Machine Learning Research (02/2023)
Table 3: Link prediction results with Macro-Fl (left) and Micro-F1 (right) scores over 10 different runs.
Method
Biicoin- Biteoin-Alphe
Bitcoia-OPC
Slasades
WillElession
WikiBdioor
WIKIREA
BINE
0.6790
0.9440
0.6852
0.5122
0:7258
0.5192
0.6940
0.752
0.7858
0.8244
0.7263
0.5160
0.7475
0.9453
0.7 0.7483
0:54886
0.7943
0.8564
0.7616
0. 8487
0.7521
0.844-2
0.7881
0.86-0
SCON
0,6645
0.9154
0.7422
0.5260
0.7963
0.7510
SNEA
0.6796
0.0210
0.7580
0.0036
0.7431
0.5308
0.7388
0.8372
0.5290
0.8672
0.7542
0.5497
SDGNN
0.7412
0.9488
0.8020
0-8336
0.7820
0.8501
0.7550
0.8308
0.8529
0.8810
0.7332
0.8598
Spectral-8GCN-1
0.9044
Spectral-SGX--1
0.7630
0.9562
0.8366
0.9532
0.7724
0.8438
0.7645
0.80:12
0.8825
0.9237
0.7735
0.8476
Speckea--2GCN
0.7030
0.9418
0.7520
0.9294
0.7852
0.8194
0.7182
0.5890
0.5448
0.5088
0.7221
0.8278
Singned-Maguet
0.9432
0.0184
0.7002
Table 4: Link prediction results with AUC scores over 10 different runs.
Method
Bitcola Alpha
Bitcoln-OTC
Slashdot
WikiElection
WidEdittr
WIKIRAA
SINE
0.8351
0.0128
0.8578 + 0.0053
0.8108
0.0021
0.8040 = 0.0072
0.8831
0.0054
0.7963 E 0.0280
SLF
0.0151
SOCN
0.8420
0.0147
0.8780 + 0.0103
0.8545 0. 0084
0.8516
0.0030
0.9068
0.0040
0.5361
0.0078
SNEA
0.8458 0.0002
0.6792 + 0. 0.0022
0.5621
0.0154
0.5412 = 0.08
0.9278
0.0062
0.5259
0.0096
Spectral-8GCN-1
Specteal-CCCN-11
0.9146
0.0000
0.9309
0.0044
0.6677
0. 0090
0.8940
0.0018
0.9818
0.0047
0.8420
0.0026
Spectral-82CCN
0.8670
0.0178
0.8996 + 0.0095
0.8273
0.0291
0.5149
0.0816
0.9878
0.0121
0.8242 + 0.0189
SigNed-MogNet.
0.9227
0.9410 0.0070
0.8615
0.8881 0.0020
0.9567 0.0344
0,8612 0.0032
model) of the two nodes u and v are concatenated together [hu, h,] as the set of features for the edge and then fed to three-class MLP classifier. The models are trained using the labeled edges from the training data. Let one-hot encoded vector of link type Sue be Suv {0, (05 We multi-class (three) cross entropy loss:
C(O. W)
Σ
Σ
Suv(c) log(Sur(c)).
[T]
where (c)(c) is the predicted probability for class e via softmax function. In the above loss function, denotes the set of GNN parameters and W denotes the parameters of MLP classifier. We use 80% of the links for training and rest 20% for testing. We use twice the number of training links as "no links' obtained using negative sampling.
We use SiNE (Wang et al. 2017 SLF (X et al. 2019), SGCN (Derr et al. 2018), SNEA (Li et al. 2020), and SDGNN (Huang et al. 2021) as baselines for comparison on link sign prediction tasks. We use a two layer GNN model along with a single hidden layer MLP classifier. Truncated SVD of the symmetric adjacency matrix with dimension of 30 is used as input features. We utilize Marco-F1 and Micro-F1 scores for evaluation, since the positive and negative links are unbalanced. The comparison results in terms of F1 scores are listed in Table 3 Moreover, the results in terms of Area Under the receiver operating characteristic Curve (AUC) scores in Table 4 The results reported in these tables are average scorcs over 10 diffcrent runs. We observe that our methods outperform the baselines for all the dalaset except for Slashdot and WikiRIA. Note that all the numbers for other algorithms in the table are obtained by running the official codes provided by the respective authors. These could be slightly different from the numbers reported in those papers that may use filtered/ filtered/truncan ttunncteddd versions datasets.
7 Conclusion
In this paper, we proposed a new framework for GNN design for signed graphs based on spectral domain analysis over signed graphs, as opposed to existing balance theory based GNN methods. We also introduced signed magnetic Laplacian for handling directed signed graphs. We evaluated our methods for node classification well link sign prediction tasks on signed graphs and achieved state-of-the-art performance.
11

---

Published in Transactions on Machine Learning Research (02/2023)
Limitations and Ethical Considerations: One limitation of our method is that it does not consider scenario in directed signed graphs when there exist two opposite (directed) edges with different signs between a pair of nodes. All of our data is publicly available for research purposes and does not contain personally identifiable information or offensive content. The methods presented here has no greater or lesser impact on sociely than other graph neural nelwork algorithms.
Acknowledgements
We would like to thank the anonymous reviewers for their helpful feedback on earlier versions of this text. This work was supported by NSF under grant 1942523.
References
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950 3957, 2021.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In 2nd International Conference on Learning Representations, ICLR, 2014.
Dorwin Cartwright and Frank Harary. Structural balance: a generalization of heider's theory. Psychological review, (5):2777 1956.
Mark Cheung, John Shi, Oren Wright, Lavendar Y Jiang, Xujin Liu, and José MF Moura. Graph signal processing and deep learning: Convolution, pooling, and topology. IEEE Signal Processing Magazine, 37 (6):139- 149, 2020.
Mihai Cucuringu, Peter Davies, Aldo Glielmo, and Hemant Tyagi. SPONGE: generalized eigenproblem for clustering signed networks. The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1088- 1098-1098. PMLR, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, volume 29, 2016.
Tyler Dorr, Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In 2018 IEEE International Conference on Dala Mining (ICDM), pp. 929 934. IEFE, 2018.
Thomas Dittrich and Gerald Matz. Signal processing on signed graphs: Fundamentals and potentials. IEFE Signal Processing Magazine, 37(6))86 98, 2020. doi: 10.1109 M0.09/MMS.220
Michaël Famuel, Carlos M Alaiz, and Johan AK Suykens. Magnetic eigenmaps for community detection in directed networks. Physical Review E, (522):22 2017.
Michaël Fanuel, Carlos M Alaíz, Áugela Fernández, and Johan AK Suykens. Magnetic eigenmaps for the visualization of directed networks. Applied and Computational Harmonic Analysis, 44(1):189 199, 2018.
Satoshi Furutani, Toshiki Shibahara, Mitsuaki Akiyama, Kunio Hato, and Masaki Aida. Graph signal processing for directed graphs based on the hermitian laplacian. In ECML/PKDD (1), pp. 447-463, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Newral Information Processing Systems, volume 30, 2017.
Yixuan He, Michael Permultter, Gesine Reinert, and Mihai Cucuringu. Msgnn: A spectral graph neural network based novel magnetic signed laplacian. Xiv preprint arXim:22090005// 2022a.
12

---

Published in Transactions on Machine Learning Research (02/2023)
Yixuan He, Gesine Reinert, Songchao Wang, and Mihai Cucuringu. SSSNET: Semi-supervised signed network
clustering. In Proceedings of the 2022 SIAM International Conference on Dala Mining (SDM), pp. 244-252 SIAM, 2022b.
Yixuan He, Xitong Zhang, Junjie Huang, Benedek Rozemberczki, Mihai Cucuringu, and Gesine Reinert. PyTorch Geometric Signed Directed: A Survey and Software on Graph Neural Networks for Signed and Directed Graphs. arXiv preprint Xiv:2220 107993 2022c.
Fritz Heider. Attitudes and coguitive organization. The Journal of psychology, 21(1):107-112 1946.
Junjie Huang, Huawei Shen, Liang Hou, and Xueqi Cheng. Signed graph attention networks. In International Conference on Artificial Neural Nebworks, pp- 1666-777-10 Springer, 2019.
Junjie Huang, Huawei Shen, Liang Hou, and Xueqi Cheng. SDGNN: Learning node representation for signed directed networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 196 203, 2021.
Mohammad Raihanul Islam, B Aditya Prakash, and Naren Ramakrishnan. SIGNet: Scalable embeddings for signed networks. In Pacific-Asia Conference on Knowledge Discovery and Dala Mining, pp. 157-169. Springer, 2018.
Junghwan Kim, Haekyu Park, Ji-Fun Lee, and Kang- SIDE: representation learning in signed directed networks. In Proceedings of the 2018 World Wide Web Conference, pp. 509 518, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Andrew V Knyazev. Signed Laplacian for spectral clustering revisited. arXiv preprint arXiw:1701.013)) 1, 2017.
Srijan Kumar, Francesca Spezzano, and VS Subrahmanian, VEWS: A Wikipedia vandal early warning system. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 607-616, 2015.
Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos. Edge weight prediction in weighted signed networks. In 2016 IEEE 16th International Conference Data Mining (ICDM), pp. 221-230. IEFE, 2016.
Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and VS Subrahmanian. Rev2: Fraudulent user prediction rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Dala Mining, pp. 333 341. ACM, 2018.
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, pp. 741-750, 2009.
Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto W De Luca, and Sahin Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualization. In Proceedings of the STAM International Conference on Data Mining, pp. 559-570. STAM, 2010.
Yeon- Moon-Chang Lee, Nayoun Seo, Kyungsik Han, and Sang- Wook Kim. ASiNE: Adversarial signed net embedding. In Proceedings of the 49rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 609 618, 2020.
Jure Leskovee, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 19th international conference on World wide web, pp. 641-650, 2010.
Ruoyu Li, Sheng Wang, Feiyun Zhn, and Junzhou Huang. Adaptive graph convolutional neural networks. Proceedings of the AAAT Conference on Arlificial Intelligence, volume 32, 2018
13

---

Published in Transactions on Machine Learning Research (02/2023)
Yu Li, Yuan Tian, Jiawei Zhang, and Yi Chang. Learning signed network embedding via graph attention. In Proceedings of the AAAT Conference on Arlificial Intelligence, volume 34, pp. 4772-4779, 2020.
Yao Ma and Jiliang Tang. Deep learning on graphs. Cambridge University Press, 2021.
BS Manoj, Abhishek Chakraborty, and Rahul Singh. Compler networks: networking and signal processing perspective. Prentice Hall, 2018.
Pedro Mercado, Jessica Bosch, and Martin Stoll. Node classification for signed social networks using diffuse interface methods. In Joint European Conference on. Machine Learning and Knowledge Discovery in Databases, pp. 524 540. Springer, 2019.
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-82) 828, 2018.
Aliaksei Sandryhaila and Jose MF Moura. Discrete signal processing on graphs Frequency analysis. IEEE Transactions on Signal Processing, 62(12):3042 3054, 2014.
David Shuman, Sumil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3):83 98, 2013.
Rahul Singh, Abhishek Chakraborty, and BS Manoj. Graph Fourier transform based on directed Laplacian. In 2016 International Conference on Signal Processing and Communications (SPCOM), pp. 1-5. IEEE, 2016.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Linglan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, prrhlatperformant package for graph neural networks. arXiv preprint 2019.
Suhang Wang, Jiliang Tang, Charu Aggarwal, Yi Chang, and Huan Liu. Signed network embedding in social media. In Proceedings of the 2017 SIAM international conference on data mining, pp. 327-335. SIAM, 2017.
Robert West, Hristo S Paskov, Jure Leskovee, and Christopher Potts. Exploiting social network structure for serson-to-persor sentiment analysis. Transactions of the Association for Computational Linguistics, 2: 297-310, 2014.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861 6871. PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprchensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):
4 24, 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 Knowledge Discovery & Dala Mining, pp. 1046 1054, 2019.
Xitong Zhang, Yixuan He, Nathan Bruguone, Michael Perlmutter, and Matthew Hirn. Magnet: A neural network for directed graphs. In Thirty-Fifth Conference on Neurol Information Processing Systems, 2021.
14

---

Published in Transactions on Machine Learning Research (02/2023)
Table Notations used in this paper.
Notations
Description
b-dimensional Euelidean space
n-dimensional complex coordinate space Scalar, vector, and matrix
x,
X"
Matrix transpose
Matrix conjugate trauspose Number of nodes in the gruph Set of nodes neighboring node i Set neighbors connected to node via positive edges Set neighbors connected to node negative edges The adjarency matrix
N
N
NO
N
A
A,
The symmetric adjacency matrix The degree matrix
L
The Laplacian matrix
The normalized Laplacian
I
The signed Laplacian matrix
L
The uormalized signed Laplacian matrix
The magnetic Laplarian matrix
L
The normalized magnetic Laplacisn matrix
L
The signed magnetic Laplacian matrix The normalized signed magnetic Laplacian Identity matrix
X
Convolution x and g Graph frequency
P
A graph filter
Learnable transformation matrix the 8th GNN layer
h (
Latent feature vector of node i in the 8 GNN layer
O
All the latent feature vectors (each row correspouding to node) in the 8th GNN layer Phase parameter
A non-linear function
By
Attention coefficient from node to node
A Proof of Proposition
Proof. Let Xi be the conjugate transpose of and x E CN is easy to see that L a Hermitian matrix and therefore, the imaginary part Im(x = 0. Denoting ("(m, n) = (m..)))) where (9,m, n) 2Tq( (m, n) A(n,))). The real part
Re(x Σ D(n, ())
Σ
Am n)x(m)x" (m,())
m,n=1
(m) -
A. Am ())(m)(( cos ()))))))))mmmm
m,
m,2=1
N
N
Σ
(m)mm))l
Σ
(1)
2
2
m,n=1
1,m=1
N
Σ
(m) cos
m,==
1
Σ (()(m)) [x()) 2|x(m)xx (n) cos(( cos(
2
m,n=1
N
(m [x(n)] (xx))) -
2
m,n=1
N
(m, ((x(m) [x(n)))²
2
m,n=1
0.
15

---

Published in Transactions on Machine Learning Research (02/2023)
Letting y D-1//x and by definition of Lg. have
- XII 0.
B Proof of Proposition
Proof. Since Lg is positive semidefinite due to Proposition 1, we just show that the largest eigenvalue Av S 2. We know that the eigenvalue with largest absolute value is
x Lgx
An max xęU
xtx
Letting y D-1/22, we have
x x
yiloy
AN max
max y&0 y'Dy
x=40
x'x
Since the numerator in the above
y'L
Σ
A,(mm
Σ
(m n)y(m)y' (n) cm))
m,n=
m,==1
N
1
A (m. +
Σ
nm(
2
2 m,n=
m,n=1
N
(o)
cos
m. m,
2
N
(m (ly(m)) (lxm)) (xx())
m,n=1
N
Σ
(m, n)) 1x(m))2
m,a=1
Σ
Σ (m)
x(m))
N
Dm,, m) y(m))
m=1
Dy.
and thus, Av 2.
C Datasets
The statistics of the real-world datasets used in our experiments are summarized in Table 6 Moreover, the histogram of the spectrum of unsigned Laplacian depicted Figure 0 from which the presence of negative eigenvalues is evident. This Laplacian is not normalizable due to presence of zero degree values. Moreover, plot the spectrum of the normalized signed Laplacian in Figure
16

---

Published in Transactions on Machine Learning Research (02/2023)
Table 6: Signed graph datasets.
Wiki-Editor
Elections
WIkI-RIA
Bitcoin- Alpha
Bitcoin-OTTC
Slashdot
# Nodes
21535
7194
11381
3783
5881
79120
# Classes
2
# Positive Links
269251
81862
139345
22650
32029
392179
# Negative Links
79004
22497
39433
1563
3503
123218
%oositive Links
77.31 %
78.44 %
77.91 %
93.54 %
89.99 %
76.09 %
Eigenvalue rauge (L)
[-422.56, 793.33]
[-115.75,646 22]
[-134.91. 708.21]
[-56.14, 136.14,,04.00 03]
[-633 788, 02)
[-660.07, 2473)
%Negative Eigenvalues (L)
26.70
24.31 %
23.45 %
5.77 %
10.36 %
21.98 %
3000
1500
2500
1000
1500
1000
1000
500
500
0
(a) Wiki-Editor.
(b) Wiki-Election
(c) Wiki-Rfa.
1000
1500
x10*
1.5
600
400
500
200
0
-50
50
(d) Bilcoin-Alpha.
(e) Bitcoin-OTC.
(I) Slashdot
Figure Histogram the Laplacian (L) eigenvalues for different datasets.
Further Implementation Details
All the experiments were run on Intel Core i9-9900 machine equipped with NVIDIA GeForce RTX 2080 Ti GPU. We use two layer networks with hidden dimension of 64 for all the GNN-based methods (a standard practice unsigned GNN literature). ReLU uonlinearity was used in the experiments. For the implementation of Signed-Maguet, we used ReLU non-linearity for real and complex parts separately. The only hyperparameters tune are learning rate and regularization (weight decay) coefficient. For all of our methods we use feature dropout with rate of 0.5. For Opectral-SGCN-IL
use attention and feature dropout with dropout rate of 0.5. We tune the learning rate with different. values (on log scale) in the range [Le-3, 1e_1] and regularization rate in the range [1e-6, 1e For node classification task, the hyperparameters were tuned based on the validation accuracy with 1% known training labels for each dataset.
Complexity Analysis: Although the time complexity of the existing signed GNN designs (balance theory basod) and our methods is O(EE) for sparse graphs or ((V(?) in worst-caso, the number of parameters per layer for these methods are different. For example, SDGNN utilizes four different encoders for capturing different directionality scenarios. In contrast, our signed spectral methods employ single (transformation) encoder in each layer. We provide training times per epoch (averaged over 300 epochs) for different signed GNN methods in Figure
E Clustering of Directed Signed Graphs
We present experiments on synthetic data generated by directed signed stochastic block model with different levels of imbalance. In particular, we simulate two clusters (classes) with directed intra-cluster edge probability of 0.05 having positive signs and directed inter-cluster edge probability of 0.05 having negative signs. Such
17

---

Published in Transactions on Machine Learning Research (02/2023)
4000
3000
4000
2000
2000
1000
2000
0
0
(a) Wiki-Editor.
(b) Wiki-Election.
(c) Wiki-Rfa.
1000
2000
30000
20000
500
1000
10000
0
0
2
0
2
0
2
(d) Bitcoin-Alpha.
(e)
Bitcoin-OTC.
(f) Slashdot.
Figure 7: Histogram of the normalized signed Laplacian (L.) eigenvalues for different datasets.
70
60
20
10
50CN
SOGNN
S2GON Signed-Magket
Figure 8: Time taken per epoch for different methods (on WikiRfA dataset for node classification task with batch size = 64, number of GNN layers 2, hidden dimension 64).
graph is balanced graph. We then flip the inter-cluste as well as intra-cluster edge signs with different probabilities creating varying levels of imbalance.
The nodes can clustered based on the first (complex) eigenvector of the signed magnetic Laplacian corresponding to the cigenvalue with smallest absolute value plotted on the complex plane. Figure shows clustering results on directed signed graphs with varying levels of imbalance.
F
Connections to SGCN
SGCN (Derr et al. 2018 its design consider balanced and unbalanced node sets based on balance theory in feature aggregation process. The balanced node set for target node is the of nodes that have even number of negative links along path connecting to i. An ê-hop balanced set of nodes for target node i is
18

---

Published in Transactions on Machine Learning Research (02/2023)
011
011
005
0.05
0.00
8
3045
-0.0
4.85
(a) imbalance prob. O.
(b) imbalance prob. = 0.1.
(c) imbalaace prob. = 0.2.
Figure 9: Clustering results with 100 nodes per cluster for directed signed stochastic block model.
0.95
Accuracy
Editor
Accuracy
0.9
Editor
0.85
Rts
Rfa
0.8
Input feature size
Input feature size
Figure 10: Spectral-SGCN-I (left) and Spectral-SGCN-II (right) performance with varying dimensions of input features (5% known labels).
denoted as (l( and unbalanced set of nodes as UE) For example graph in Figure 2 Bı = {2) and (1) (3, 4).
The node representations for these balanced and unbalanced are treated separately in feature aggregation process and are concatenated together to form final node embeddings. In the 9th layer of the model, it reads
B(t-1)
((--1)
h
h
(())
B(E)
Σ
h
B(e-1)
WN!T1
W
LEEN
KEN,
((e-1)
h
B(--1)
h (0)
(U))
W h,
U(e-1)
LiENT
KEN,
where BL)) and ( linear transformation parameters for balanced and unbalanced paths, respectively
and the node representation at gth layer is the concatenation of the two embeddings h()) = m(,)) h (1
Instead of treating positive and negative neighbors separately, in our architecture of Spectral-SGCN-I we are aggregating them weighted by their signs and corresponding (absolute) degrees be seen from 12
G Effect of Input Feature Size
We also perform the study on the classification accuracy with varying number of input feature sizes. Figure shows the performance of Spectral-SGCNNII with respect varying nunber of input features. As expected, the performance improves with increase in the dimension of input features.
19


Reviews:
[{"review_id": "AMGeuGeGTs", "reviewer": "Reviewer_HEUa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* The consideration of signed graphs with graph neural networks based on their spectral analyses is novel and interesting.\n* This paper is extremely well-written and easy to follow.\n* The quality of illustrations for explaining their signed graph neural networks is high.\n* The proposed methods outperform relevant baselines.\n\n### Weaknesses\n* I don't see any major weaknesses.\n* Please see minor improvements, in the requested changes section below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces new graph neural networks for signed graphs based on their spectral analyses, where one graph neural network mostly considers low frequency as in graph convolutional network, while the other graph neural network considers both low and high frequencies with attention mechanisms. Also, the authors extend their signed graph neural networks to signed directed graphs. The authors evaluate their methods on node classification and link prediction tasks for singed graphs, showing performance improvements against baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Suggestions and Questions\n* I am wondering, the attention mechanism for considering both low- and high-frequency information could be applied to Singed-MagNet.\n* In Section 5.2, it is unclear which is flipped to generate varying levels of imbalance, when experimenting with synthetic graphs.\n* In Table 4, it is better to denote whether the left or the right column for each dataset is Macro-F1 or Micro-F1.\n* In link prediction experiments, why the proposed methods are outperformed by existing methods on Slashdot and WikiRfA datasets?\n* In Section 6, there is a typo: different signs signs.", "broader_impact_concerns": "The authors explicitly mention the broader impacts in Section 6, and I do not have any concerns about them. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "I15Z49tG5S", "reviewer": "Reviewer_fhAS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I have not worked on Graph Neural Networks.\n\nThe contributions in this paper are incremental and the algorithms are similar to previous work other than the use of signed laplacian. This is not a problem with TMLR. I did not find incorrect claims or glaring issues with the methodology in this paper.\n\nThese are my main questions:\n\n1. I had a hard time understanding the experiment in 5.2. What is SNEA is this experiment and is there any intuition why the proposed method works better in high levels of imbalance?\n\n2. Is there any evidence that the problem of negative eigenvalues actually happens to the baselines in the real-world datasets?\n\n3. What is the connection between the possibility of negative eigenvalues and the final performance of the algorithm? Is there any previous theoretical bound that assumes nonnegative eigenvalues or one that deteriorates when some eigenvalues are negative?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission extends Graph Convolutional Networks, Frequency Adaptation Graph Convolutional Networks, and Magnetic Laplacian to signed graphs. The main contribution is incorporating signed laplacian in these algorithms. Experiments show that the algorithm based on the extension of magnetic laplacian generally outperforms baselines on node classification and link sign prediction tasks on signed graphs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See previous section", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5PpGFNEFec", "reviewer": "Reviewer_Ua9S", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I will preface my review by stating that I am not really qualified or experienced enough to review the technical content in this paper.  I have **no** experience with graph methods, spectral methods, Laplacians or the datasets and problem domains tackled.  Therefore, my review will be somewhat high-level.  \n\n## Strengths\nThe paper is fairly well written and appears to be thoroughly benchmarked on a number of widely used examples.  From what I can gather, it also seems to be a timely and novel method that is well-placed amongst several recent other publications.  \n\n## Weaknesses\nMy main complaints about the paper are centred on the presentation.  \n\n(1)  The authors have clearly done a lot of good work.  However, the paper is very intense, and requires the reader to already be an expert in graph and spectral methods to get **anything** out of the paper.  Basic terms and concepts are not really defined anywhere (e.g. how does a graph have a frequency...?).  I think this is okay... but will severely limit the reach and impact of the paper.  The paper would benefit from introducing more slowly some of the basic terminology and ideas.  (Also see (i) below.)\n\n(2)  The review of existing work feels like more of a hat-tipping exercise than actually introducing the reader to the landscape of the field.  The weaknesses of existing methods are curtly stated, and not really fleshed out at all.  \n\n(3)  The paper can easily be reduced in length to make space for my recommendations.  Some of the information on the datasets can be cut to the supplement;  paragraphs two and three in the intro can be combined + shortened + thinned to the relevant work section;  I believe much of Section two could be made shorter and more direct.\n\n## Minor Weaknesses / Typographical Comments\n(a)  Figures should be floated to the top of pages (cf. Figure 1, 3, 4, Table 1).\n\n(b)  \\eqref should be used for referencing equations, i.e. \"equation \\ref{X}\" -> \"\\eqref{X}\".\n\n(c)  Footnotes should be avoided where possible.\n\n(d)  What is $\\mathcal{V}$ in the definition of $\\mathcal{G}$?  It doesn't seem to be used anywhere.  \n\n\n## Summary\nOverall, I think the submission itself is of publication quality, though I cannot reasonably comment on the \"science\".  There is a good amount of work to be done to make the paper more accessible (see \"Requested Changes\").\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new method for handling graphs with signed connections, by analysing the spectral representation of the graph.  The method is accompanied by some theoretical analysis.  The method is then benchmarked fairly thoroughly against other methods, and appears to perform favourably. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I consider all of these changes \"critical\", since they are all easy-to-change typographical things that would help the reader.\n\n(i)  Insert a short additional \"Problem Definition\" section before Section 2.  This will take some of the notation from the first paragraph of what is currently Section 2.  This section should concretely define the problem structure:  what are the inputs and outputs (and their spaces), what is the loss function (or at least the type of loss function), what are the parameters, what constituted a \"good\" outcome, what does a typical application  look like etc.  There should be little-to-no math in this section, other than defining terms.  Currently, you introduce some preliminaries, and then dive straight in to very low-level details, and never really \"pop back up\".  It is also reasonable as the final paragraph in this section to (re-)outline how and what your method will overcome.  \n\n(ii)  A banner diagram at the top of page 2 that visually describes the problem and solution.  I think Figure 1 is a good starting point for this, but I would like to see it enriched with an illustration of the method (if possible).  This diagram should prime the reader for the material that is subsequently presented.\n\n(iii)  I would like a table of notation added as the first section in the supplement, since the paper is very notationally heavy.\n\n(iv)  Add introduction of core terminology and ideas.", "broader_impact_concerns": "No concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies extensions of the basic GNN architecture based on low-pass filtering (GCN) to signed graphs, that is, whose edges may be either +1 or -1. While several other architectures exist to process such graphs, the current manuscript derives an interesting alternative with good results. 
Decision: Accept (poster)