Abstract
This paper introduces SigMaNet, a generalized Graph Convolutional Network (GCN) capable of handling both undirected and directed graphs with weights not restricted in sign nor magnitude. The cornerstone of SigMaNet is the Sign-Magnetic Laplacian (LSM), a new Laplacian matrix that we introduce ex novo in this work. LSM allows us to bridge a gap in the current literature by extending the theory of spectral GCNs to (directed) graphs with both positive and negative weights. LSM exhibits several desirable properties not enjoyed by other Laplacian matrices on which several state-of-the-art architectures are based, among which encoding the edge direction and weight in a clear and natural way that is not negatively affected by the weight magnitude. LSM is also completely parameter-free, which is not the case of other Laplacian operators such as, e.g., the Magnetic Laplacian. The versatility and the performance of our proposed approach is amply demonstrated via computational experiments. Indeed, our results show that, for at least a metric, SigMaNet achieves the best performance in 15 out of 21 cases and either the first- or second-best performance in 21 cases out of 21, even when compared to architectures that are either more complex or that, due to being designed for a narrower class of graphs, should—but do not—achieve a better performance.
Introduction
Most spectral Graph Convolutional Networks (GCNs)—the backbone of many graph-based AI applications—rely on the graph Laplacian matrix. Traditionally, this matrix requires two strict conditions: the graph must be undirected, and edge weights must be non-negative. While researchers have developed "Magnetic Laplacians" to handle directed edges, these existing solutions suffer from two major drawbacks: negative weight intolerance and scaling inconsistency. Specifically, they fail to remain positive semidefinite when edges have negative weights (e.g., "dislike" or "debt" relationships), and scaling the magnitude of an edge weight can accidentally flip the directional information encoded in the spectral domain. SigMaNet aims to bridge this gap by creating a single operator that works for any graph, regardless of direction or weight sign.
Methods
The authors introduce the Sign-Magnetic Laplacian ($L^\sigma$), a novel spectral operator that leverages complex-valued linear algebra to provide a robust framework for complex graph types.
The Sign-Magnetic Laplacian ($L^\sigma$)
$L^\sigma$ is a Hermitian matrix where the real part captures symmetric relationships and the imaginary part encodes the direction of the edges. Unlike previous iterations, $L^\sigma$ is specifically designed to remain positive semidefinite even when weights are negative. It treats a negative weight from node $A$ to $B$ as mathematically equivalent to a positive "flow" from $B$ to $A$.
Key theoretical insights include:
- Positive Homogeneity: Theorem 4 proves that $L^\sigma$ is robust to scaling. If all weights are multiplied by a constant, the Laplacian scales proportionally without changing its structural properties, solving the "sign-pattern inconsistency" found in previous models.
- The Flow Invariant: Theorem 5 demonstrates that flipping an edge's direction while simultaneously flipping its sign leaves the Laplacian unchanged, aligning with physical intuitions of "flow."
- Parameter-Free Efficiency: Unlike the standard Magnetic Laplacian, which requires tuning an "electric charge" parameter ($q$), SigMaNet is entirely parameter-free, simplifying deployment.
SigMaNet Architecture
The SigMaNet architecture uses the $L^\sigma$ matrix to define spectral convolutions. It employs a complex version of the ReLU function (CReLU), which activates based on the real part of the complex number. To interface with standard neural network layers, the model "unwinds" the complex-valued output by concatenating the real and imaginary components into a single real-valued vector.
Experimental Evaluation
The model was evaluated on a diverse set of benchmarks, including signed/directed networks (Bitcoin-Alpha, Bitcoin-OTC, WikiRfa, Slashdot, and Epinions) and weighted/directed networks (Telegram). Synthetic benchmarks using a Directed Stochastic Block Model (DSBM) were also employed to test handling of varying graph densities and large weight magnitudes.
Link Sign Prediction
SigMaNet demonstrated superior versatility and performance in link sign prediction. It achieved the best performance in 15 out of 21 test cases and was either first or second-best in all 21 cases, even when compared to more complex, task-specific architectures.
Node Classification
On synthetic datasets where weight magnitude is critical, SigMaNet outperformed its closest spectral rival, MagNet, by roughly 10% on average. Despite its broader applicability, SigMaNet uses half the weights of MagNet, proving that a better mathematical foundation can lead to more efficient models.
Conclusion
SigMaNet introduces a powerful, generalized framework for GCNs by utilizing the Sign-Magnetic Laplacian. Its ability to handle directed graphs with arbitrary weight signs in a parameter-free manner sets a new standard for spectral graph learning. Future work will focus on optimizing computational complexity for massive graphs and exploring alternative complex-valued activation functions.
Summary updated