MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian

In plain words

Many real networks have edges that are not just "connected or not". An edge can be friendly or hostile (a sign), and it can point one way (a direction). A graph neural network (GNN) learns node representations from such a graph, but most GNNs assume plain undirected, unsigned edges.

This paper gives the graph a matrix, the "magnetic signed Laplacian", that carries both kinds of information at once. Each entry keeps the sign in its real value and the direction in its angle, so the matrix uses complex numbers. Spectral GNNs filter node signals through this matrix, much as a sound filter works on frequencies. The paper's network, MSGNN, does that filtering with two small layers.

The authors test it on two jobs: sorting nodes into groups, and predicting what kind of link joins two nodes (its sign, its direction, or both). They also add a synthetic graph generator and new datasets built from lead-lag relationships between stock returns.

TL;DR

• Defines a Hermitian "magnetic signed Laplacian" that generalises the signed Laplacian and the magnetic (directed) Laplacian §3.2.
• MSGNN is a two-layer spectral GNN with first-order Chebyshev filters and complex weights §3.3, §3.4.
• Author-reported: highest accuracy on all 25 link-prediction cells (24 outright, one tie) and generally the fastest runtime §4.4.2, tab. 1, app. B.
• Relevant if you need a GNN for signed, directed graphs; check the Pitfalls, since the paper and code differ on several settings.

Problem

Spectral GNNs need a graph Laplacian. For signed and directed graphs, that Laplacian should be positive semidefinite, have a bounded spectrum after normalisation, and encode both sign and direction §1. Earlier work covered only unsigned directed graphs (the magnetic Laplacian) or only signed undirected graphs (the signed Laplacian) §2. A concurrent signed magnetic Laplacian (SigMaNet) gives a node degree zero when its positive and negative unweighted links balance; the authors argue this is undesirable §3.2. The paper also notes that most earlier signed-graph GNNs were spatial and were evaluated mainly on link sign prediction §1, §2.

Method

Setting §3.1. The input is a weighted graph with signed edge weights w(e) that are nonzero, possibly directed, with optional node features X of shape n × d_in. Self-loops are allowed; multi-edges are not. The signed adjacency matrix is A, with A_ij = w(i→j) if the edge exists, else 0.

Magnetic signed Laplacian §3.2.

1. Symmetrise the signed adjacency: Ã_ij = (A_ij + A_ji) / 2.
2. Build the absolute-value degree D̃_ii = ½ Σ_j (|A_ij| + |A_ji|). Absolute values keep D̃ positive on connected graphs.
3. Build the phase matrix Θ^(q)_ij = 2πq (A_ij − A_ji). q is the "charge" parameter.
4. Form the Hermitian matrix H^(q) = Ã ⊙ exp(iΘ^(q)). For q = 0, H is just Ã.
5. Unnormalised Laplacian: L_U^(q) = D̃ − H^(q) eq. 1.
6. Normalised Laplacian: L_N^(q) = I − (D̃^(−1/2) Ã D̃^(−1/2)) ⊙ exp(iΘ^(q)) eq. 2. Because D̃ is diagonal, this equals D̃^(−1/2) L_U D̃^(−1/2) §3.2, app. A.
7. Theorem 1: L_U and L_N are positive semidefinite for every real q §3.2. Theorem 2: the eigenvalues of L_N lie in [0, 2] for every real q §3.2.
8. Reduction: with no signs, the matrix becomes the magnetic Laplacian. With no direction (q = 0 or undirected), it becomes the signed Laplacian. With neither, it becomes the standard normalised Laplacian §3.2.
9. Edge flip: reversing an edge conjugates its entry in H^(q) §3.2.

Spectral convolution §3.3. Given an eigendecomposition L = U Λ U†, a signal x has Fourier transform x̂ = U† x, and a filter is a diagonal matrix Σ in that basis eq. 4. Following Defferrard et al. (cited as Defferrard2018), the authors take Σ as a Chebyshev polynomial in the rescaled eigenvalues Λ̃ = (2/λ_max) Λ − I eq. 5. The resulting filter Σ_k θ_k T_k(L̃) involves only products with L̃, so it avoids computing eigenvectors and has about one parameter per polynomial order. The filter is permutation-invariant and reaches K hops in the undirected, unsigned version of the graph; it treats out-neighbours and in-neighbours symmetrically §3.3. The authors state that the cost is that of the unsigned undirected counterpart, since only the entries on existing edges are computed §3.3.

MSGNN architecture §3.4.

• A layer is X^(ℓ) = σ(Σ_i Y_ij^(ℓ) x_i^(ℓ−1) + b_j^(ℓ)) eq. 6, where σ is a complex ReLU and Y is a Chebyshev filter.
• The authors use K = 1 and L = L_N^(q). Then X^(ℓ) = σ(X^(ℓ−1) W_self + L̃ X^(ℓ−1) W_neigh + B) §3.4.
• Biases satisfy Re(b) = Im(b) eq. 6.
• The complex ReLU keeps z when −π/2 ≤ arg(z) < π/2 and sets it to 0 otherwise §3.4.
• The default is L = 2 layers §3.4, app. B.
• The output is unwound into a real n × 2F matrix §3.4.
• Node clustering: a linear layer with softmax over the unwound features §3.4.
• Link prediction: concatenate the pair's rows of the unwound features, then a linear layer and softmax §3.4.

Pseudocode. The official code computes the same quantities; see Paper vs code for the differences.

# Magnetic signed Laplacian, normalised  [§3.2] [eq. 2]
# Input:  A (n, n) signed weighted adjacency, A[i, j] = weight of i -> j
# Input:  q (scalar) charge; 0 for undirected graphs
# Output: L (n, n) complex Hermitian, eigenvalues in [0, 2]  [§3.2, Thm. 2]

def magnetic_signed_laplacian(A, q):
    # Self-loops: the paper allows them, the official code removes them
    # [§3.1] [code: src/get_magnetic_signed_Laplacian.py#L46]
    A = A with its diagonal set to zero
    # Symmetrised signed adjacency  [§3.2]
    A_sym = (A + transpose(A)) / 2
    # Absolute-value degree, one entry per node  [§3.2]
    degree = sum over j of (abs(A[i, j]) + abs(A[j, i])) / 2   # (n,)
    # Phase matrix, skew-symmetric  [§3.2]
    theta = 2 * pi * q * (A - transpose(A))
    # Hermitian matrix carrying sign and direction  [§3.2]
    H = A_sym * exp(1j * theta)                 # elementwise product
    # Isolated nodes: 1/sqrt(0) is replaced by 0  [code: src/MSConv.py#L178]
    D_inv_sqrt = diag(1 / sqrt(degree)), with 0 where degree is 0
    # L = I - D^-1/2 H D^-1/2 equals eq. 2 because D is diagonal  [eq. 2]
    return identity - D_inv_sqrt @ H @ D_inv_sqrt

# MSGNN convolution with K = 1  [§3.3] [§3.4] [eq. 5] [eq. 6]
# Input:  X (n, F_in) complex node signal (real and imaginary parts)
# Input:  L (n, n) complex, from magnetic_signed_laplacian
# Output: (n, F_out) complex

def msgnn_layer(X, L, W_self, W_neigh, bias_real):
    # Rescale the spectrum to [-1, 1]: L_tilde = 2 L / lambda_max - I
    # [eq. 5]. For sym normalisation, lambda_max is fixed to 2 in code
    # [code: src/MSConv.py#L178], so L_tilde = L - I. See Pitfalls.
    L_tilde = L - identity
    # Real weight matrices applied to complex signals  [eq. 6]
    out = X @ W_self + L_tilde @ X @ W_neigh
    # Complex bias with equal real and imaginary parts  [eq. 6]
    out = out + (bias_real + 1j * bias_real)
    # Complex ReLU: keep entries with Re >= 0, zero the rest  [§3.4]
    # [code: src/complex_relu.py#L19]
    keep = real(out) >= 0
    return out * keep

# Link head for a candidate pair (i, j)  [§3.4] [code: src/MSGNN.py#L85-L91]
# Input:  H_real, H_imag (n, hidden) from the last layer
# Output: log-probabilities over link classes

def link_log_probs(H_real, H_imag, i, j):
    # Concatenate both endpoints' real and imaginary parts: 4 * hidden
    feats = concat(H_real[i], H_real[j], H_imag[i], H_imag[j])
    # Dropout on the pair features during training; rate not stated in paper
    # [code: src/parser_link.py#L14]
    feats = dropout(feats, p=0.5)
    # Linear layer to the classes, then log-softmax  [code: src/MSGNN.py#L59]
    return log_softmax(linear(feats))

Hyperparameters

Results

Author-reported. Link prediction accuracy (%), mean ± standard deviation over five random splits, compared with six baselines §4.4.2, tab. 1. For FiLL, the "avg." row averages over 42 yearly networks and then reports mean ± SD over five runs §4.4.2. Datasets: BitCoin-Alpha and BitCoin-OTC §4.3, Slashdot and Epinions §4.3, and FiLL-pvCLCL and FiLL-OPCL (financial lead-lag, 2000–2020) §4.3. Tasks: sign prediction (SP), direction prediction (DP), and the 3-, 4- and 5-class tasks that need both §4.1.

Bold marks MSGNN. On FiLL 5C, SNEA and MSGNN both reach 64.8±0.1 tab. 1.

• Runtime (seconds, link tasks, after preprocessing) is in app. B. MSGNN is fastest in most rows; for example, on Slashdot SP it takes 227 s, against 342 s for SSSNET and 5792 s for SNEA. On Epinions 3C, SSSNET is fastest (471 s) and MSGNN second (510 s).
• Node clustering §4.4.1, fig. 2: synthetic data only (SSBM, Pol-SSBM and SDSBM). Metric is ARI over ten runs (five networks, two splits each). The authors report MSGNN ahead of SigMaNet on every synthetic dataset and competitive with SSSNET. SSSNET is slightly ahead on SSBM and Pol-SSBM. Error bars are one standard error. The figure's values are not tabulated.
• Ablation §4.4.3, app. C: nonzero q usually helps the directional tasks (DP, 3C, 4C, 5C), and the authors recommend q0. Signed input features help sign tasks. Building features from positive and negative subgraphs separately helps. Treating weights as unit magnitude helps or hurts depending on the dataset; edge weights matter for FiLL.
• Layers app. C: going from 2 to 4 layers gives small gains, which often fall within one SD; performance falls slightly at 10 layers. Normalised and unnormalised variants differ by less than one SD in most cases.

Paper vs code

Code: official repository SherylHYX/MSGNN at da5cfd40ba10f21d3843b6c00e3ab29773d5f042, MIT, copyright Yixuan He LICENSE. The paper links this repo in §4.4 §4.4, so no further search was needed. The paper also says the code is in the PyTorch Geometric Signed Directed library §4.4.

• Self-loops. The paper allows self-loops §3.1. The code removes them before building the Laplacian get_magnetic_signed_Laplacian.py and again inside the layer MSConv.py.
• Phase sign and degree. The code's phase is w_ij − w_ji, which matches Θ = 2πq(A_ij − A_ji) §3.2 get_magnetic_signed_Laplacian.py get_magnetic_signed_Laplacian.py. The symmetrisation and absolute-value degree match the paper's definitions §3.2 get_magnetic_signed_Laplacian.py. Consistent.
• λ_max for sym normalisation. The paper gives L̃ = (2/λ_max) L − I eq. 5 but does not say which λ_max is used with normalised Laplacians. The code computes λ_max only for non-sym normalisation and otherwise fixes it to 2 MSConv.py. Since Theorem 2 bounds the spectrum by 2 §3.2, this is the upper bound, not necessarily the largest eigenvalue of each graph.
• Charge q, three statements. §3.2 sets q to q0 = 1/(2 max_ij (A_ij − A_ji)) for the directed tasks other than the ones with q = 0 §3.2. It then says q = 0.25 is used "for simplicity" in most experiments §3.2. The SDSBM node runs use q = 0.25 app. B. The link-prediction ablation recommends q0 §4.4.3. The code's link scripts run q as 55 (= q0), 0, and 11–44 (fractions of q0) a0.sh main_signed_directed_link.py. The code's SDSBM ablation sweeps q over 0–0.25 and 55 a5.sh. Which q produced the main link table is not stated in the paper.
• q0 is computed once, from the first split. In main_signed_directed_link.py, q is converted from the 55 flag inside a loop over splits main_signed_directed_link.py main_signed_directed_link.py. After the first split, args.q is a float, so the test args.q in [11, 22, 33, 44, 55] is false for later splits. As written, every split after the first keeps the q0 computed on the first split's graph. This reading is from the code; I did not run it.
• Input features default. The paper uses 4-dim in/out-degree features split by sign app. B. The code's default is 2-dim unsigned degrees; the 4-dim variant needs --sd_input_feat main_signed_directed_link.py. The execution scripts pass that flag in the variants labelled A and C a0.sh.
• Complex ReLU boundary. The paper keeps z when −π/2 ≤ arg z < π/2 §3.4. The code keeps entries with Re ≥ 0 and applies the same mask to both parts complex_relu.py. They differ only on the imaginary axis: the code keeps points with Re = 0 and Im > 0, which the paper zeroes.
• Link head dropout. The paper does not state dropout; the code applies dropout 0.5 to the concatenated pair features MSGNN.py parser_link.py.
• Hidden size. The paper gives no MSGNN hidden size; the code default is 16 parser_link.py.
• Epochs and model selection. The paper says 300 epochs for link prediction app. B. The code trains for that many epochs and reports test accuracy at the last epoch, with no validation split by default main_signed_directed_link.py parser_link.py.
• Node loss. L_2 and L_1 as written app. B match the code's loss: sup × (CE + triplet ratio × triplet) + PBNC + imbalance main_SDSBM_node.py. Defaults match parser_node.py parser_node.py parser_node.py.
• Undirected node features and the SSBM runs are described in app. B; the code for those runs was not checked.
• Consistent: the K = 1 Chebyshev layer with real weights, the complex bias with Re = Im, and the concatenated pair head eq. 5, eq. 6, §3.4 MSConv.py MSConv.py MSGNN.py.

Pitfalls

• Self-loops. The paper's formulas keep self-loops in Ã; the official code removes them. A graph with self-loops will give different results from the paper's text.
• λ_max. The rescaling constant for sym normalisation is not stated. The code uses 2, the bound from Theorem 2, so the Chebyshev filter is L − I. A different λ_max rescales the filter.
• q is data-dependent. q0 = 1/(2 max(A_ij − A_ji)). With unit-magnitude signed weights, the max is 2 only if some pair has A_ij = 1 and A_ji = −1; otherwise q0 differs from 0.25 §3.2. The code computes it from the split's graph main_signed_directed_link.py.
• Setting q. The q behind the main link table is not stated. Any reproduction must pick a q and report it. The code's link scripts sweep q0 (flag 55), 0, and fractions 11–44 of q0. The formula gives 0.2, 0.4, 0.6 and 0.8 of q0 for flags 11, 22, 33 and 44 main_signed_directed_link.py. The parser's help text lists 1/5, 1/5, 3/5 and 4/5 parser_link.py, which disagrees with the formula. The paper's q-ablation table uses 0.2q0 to 0.8q0 app. C.
• Feature flags. Without --sd_input_feat, the code's link model has 2-dim input, not the 4-dim input described in the paper main_signed_directed_link.py.
• Ties in the claim. The paper says MSGNN has the highest accuracy in all 25 cases §4.4.2. Table 1 shows a tie on FiLL 5C (both 64.8 ± 0.1) tab. 1. The claim holds for 24 cells only.
• Evaluation timing. The code's link-prediction numbers come from the last epoch, with no validation split by default main_signed_directed_link.py. The paper gives no early-stopping rule for link prediction app. B.
• Complex arithmetic. The filter and biases are complex. The code keeps real and imaginary parts of the output separately and returns both MSConv.py; implementations need the same split.
• Theorem constant. The LoG version gives Θ entries in [0, π]; the arXiv version gives [−π, π] and says a different constant gives [−π/2, π/2] §3.2 footnote. The code uses q0 = 0.5/max, which matches the arXiv range.
• Cost. The paper states that the convolution computes only entries on existing edges, so its cost matches the unsigned undirected version §3.3. The Chebyshev form avoids the eigendecomposition §3.3. The paper gives no separate runtime figure beyond the table in app. B.
• Dataset access. FiLL is built from CRSP prices accessed via WRDS §4.3. The paper says the lead-lag matrices are public. Rebuilding them from raw prices needs CRSP data. The repo ships data/Lead_Lag files Lead_Lag.
• Sparsification. FiLL graphs keep the 20% largest-magnitude edges §4.3. The repo ships *_10p2.npz files; I did not check their sparsification in code.

Lineage

• Builds on: Chebyshev spectral filters of Defferrard et al. (cited as Defferrard2018) §3.3; the magnetic Laplacian GNN "MagNet" (cited as zhang2021magnet). With positive weights, the paper's GNN reduces to MagNet's §2. The MagNet arXiv identifier is 2102.11391 per the code docstring complex_relu.py.
• Signed-graph baseline: SSSNET (cited as he2022sssnet), whose loss and hyperparameters are reused app. B.
• Compared against: SGCN, SDGNN, SiGAT, SNEA, SSSNET, SigMaNet §4.4. SigMaNet is a concurrent signed magnetic Laplacian GNN §2, §3.2.
• Concurrent work: a signed-network GNN developed independently (cited as singh2022signed) §2 footnote.
• Superseded by: not stated.