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 ($L^{\sigma}$), a new Laplacian matrix introduced to bridge the gap in spectral GCN theory for directed graphs with both positive and negative weights. $L^{\sigma}$ encodes edge direction and weight naturally, is parameter-free, and robust to weight magnitude. Experimental results demonstrate that SigMaNet achieves state-of-the-art performance across 21 benchmarks, outperforming more complex or specialized architectures by achieving the best performance in 15 cases and either first- or second-best in all 21.
Introduction
Graph Convolutional Networks (GCNs) are typically categorized into spatial and spectral methods. Spectral GCNs, while mathematically rigorous, have historically been limited by the properties of the graph Laplacian. Traditional spectral methods require graphs to be undirected and possess non-negative weights to ensure a valid eigenvalue decomposition. While extensions like the Magnetic Laplacian were developed to handle directed edges, they often struggle with negative weights (representing "distrust" or "dislike") and suffer from "sign-pattern inconsistency"—where scaling weights can fundamentally alter the model's perception of edge direction.
SigMaNet addresses these limitations by introducing the Sign-Magnetic Laplacian ($L^\sigma$), a single operator designed to work across directed, undirected, signed, and unsigned graphs. By providing a unified mathematical foundation, SigMaNet aims to be a universal operator for graph representation learning.
The Sign-Magnetic Laplacian ($L^\sigma$)
The core innovation of SigMaNet is the Sign-Magnetic Laplacian ($L^\sigma$), a complex-valued Hermitian matrix. Unlike standard Laplacians that rely on real numbers, $L^\sigma$ utilizes the complex plane to represent graph topology:
- Encoding Direction and Sign: The imaginary component of the complex numbers encodes edge direction, while the real component handles symmetric relationships.
- The Signum Function: A critical feature of $L^\sigma$ is the use of the signum function. This ensures that directional information remains stable and is not "washed out" by large variations in weight magnitude, a common failure point in previous spectral methods.
- Parameter-Free Design: Many existing directed Laplacians, such as the Magnetic Laplacian, require the tuning of a "charge" parameter ($q$). $L^\sigma$ is entirely parameter-free, simplifying the training pipeline and improving generalizability.
- Positive Homogeneity: The authors prove that $L^\sigma$ scales linearly with weight magnitude. This property ensures that the structural interpretation of the graph remains consistent regardless of whether the weights are scaled up or down.
SigMaNet Architecture
Building on $L^\sigma$, the SigMaNet architecture adapts the standard GCN framework to the complex domain. Since the Laplacian is complex-valued, the hidden states of the network are also complex. To handle this, the model employs:
- Complex ReLU: A specialized activation function designed for complex-valued inputs.
- Unwind Operation: To interface with standard output layers (e.g., for classification or regression), the model "unwinds" the final hidden state by concatenating the real and imaginary components into a single real-valued vector.
Experimental Evaluation
The authors evaluated SigMaNet across 21 experimental setups involving four distinct tasks using both real-world and synthetic data:
- Real-World Signed Graphs: Datasets including Bitcoin-OTC, Bitcoin Alpha, WikiRfa, Slashdot, and Epinions. These datasets contain explicit trust and distrust ratings, representing unrestricted weights.
- Real-World Directed Graphs: The Telegram dataset, an influence network of political channels.
- Synthetic Data: Directed Stochastic Block Models (DSBM) were used to test the model's robustness against varying weight magnitudes (ranging from 2 to 1000).
Key Results and Insights
SigMaNet demonstrated remarkable versatility and performance across all benchmarks:
- Dominance in Performance: SigMaNet achieved the best performance in 15 out of 21 cases and ranked either first or second in every single test case.
- Robustness to the "Magnitude Trap": A significant finding was the fragility of previous models. While the Magnetic Laplacian's performance can degrade if weights are scaled, SigMaNet remains stable due to its signum-based construction.
- Efficiency vs. Complexity: Despite having fewer parameters than many competing deep neural networks, SigMaNet consistently outperformed them. This suggests that a mathematically grounded representation of graph geometry is often more effective than simply increasing model depth.
- Node Classification: On the Telegram dataset and synthetic DSBMs, SigMaNet outperformed its closest spectral rival, MagNet, by approximately 10% on average.
Conclusion and Future Work
SigMaNet provides a robust, parameter-free framework for spectral graph convolutions on the most general class of graphs. By resolving the inconsistencies associated with weight magnitude and edge direction, it sets a new standard for spectral GCNs.
Future research directions include extending the Sign-Magnetic Laplacian to handle multi-graphs (where multiple edge types exist between nodes) and temporal graphs where the topology evolves over time. Additionally, the integration of $L^\sigma$ into more complex architectures, such as Graph Attention Networks (GATs), remains a promising avenue for exploration.
Summary updated