Abstract
We introduce QuaterGCN, a spectral Graph Convolutional Network (GCN) with quaternion-valued weights at whose core lies the Quaternionic Laplacian, a quaternion-valued Laplacian matrix by whose proposal we generalize two widely-used Laplacian matrices: the classical Laplacian (defined for undirected graphs) and the complex-valued Sign-Magnetic Laplacian (proposed to handle digraphs with weights of arbitrary sign). In addition to its generality, our Quaternionic Laplacian is the only Laplacian to completely preserve the topology of a digraph, as it can handle graphs and digraphs containing antiparallel pairs of edges (digons) of different weights without reducing them to a single (directed or undirected) edge as done with other Laplacians. Experimental results show the superior performance of QuaterGCN compared to other state-of-the-art GCNs, particularly in scenarios where the information the digons carry is crucial to successfully address the task at hand.
Introduction: The Challenge of Directed Graphs
Graph Convolutional Networks (GCNs) are the gold standard for processing data structured as networks. However, most "spectral" GCNs—those grounded in the elegant mathematics of graph signal processing—have a major blind spot: directed graphs (digraphs).
In the real world, relationships are rarely symmetric. A specific challenge arises with digons—pairs of antiparallel edges where node A points to B, and B points back to A.
Existing models usually handle this by "collapsing" the relationship: they either treat it as an undirected edge or average the weights. If user A trusts user B with a score of 50, but B only trusts A with a score of 2, most GCNs see this as a symmetric relationship of 26. This loss of topological detail, termed "topology collapse," makes it impossible for models to accurately learn from complex, asymmetric networks like trust platforms or citation indices.
Methods: The Quaternionic Laplacian ($L^{\text{\textqoppa}}$)
We propose moving graph learning into "4D" using quaternions. While real numbers have one component and complex numbers have two ($a + ib$), quaternions have four ($q = q_0 + iq_1 + jq_2 + kq_3$). The core innovation is a new Laplacian matrix that uses these four dimensions to encode different types of graph structures simultaneously: the real part encodes symmetric relationships, while the imaginary parts encode directed edges and the specific asymmetries of digons.
As shown in the comparison above, $L^{\text{\textqoppa}}$ is the only Laplacian that completely preserves the topology of a digraph by allowing digons where $w_1 \neq w_2$. This mathematical generality allows it to act as a superset of classical and complex-valued Laplacians, providing a robust, unified tool for graph representation.
QuaterGCN Architecture and Results
We built QuaterGCN, a network using quaternion-valued weights and a convolution operator based on $L^{\text{\textqoppa}}$. To ensure compatibility with standard deep learning outputs, an "unwind" layer transforms the 4D quaternionic features back into a high-dimensional real-valued matrix for the final classification step.
Experimental results across real-world trust networks (Bitcoin-OTC, Bitcoin-Alpha) and synthetic benchmarks (DBSM, Di500) demonstrate QuaterGCN's superiority:
- Node Classification: It achieved the best results in 9 out of 10 experimental scenarios. Notably, on the sparse Di500 dataset—designed to test digon handling—it outperformed the second-best model by a staggering 242%.
- Edge Prediction: In multi-class tasks predicting link sign and direction, QuaterGCN was the top performer in 8 out of 10 cases.
- Ablation vs. QGNN: When compared to QGNN (which uses quaternion weights but a standard real-valued Laplacian), QuaterGCN performed 309% better on average. This proves that the quaternionic representation of the graph's topology is the primary driver of performance.
Conclusion
QuaterGCN provides a robust solution to the problem of topology collapse in directed graphs. By leveraging the non-commutative algebra of quaternions, it preserves the full richness of reciprocal relationships. While quaternionic arithmetic increases computational complexity, the gain in expressiveness is substantial for complex networks. Future work will explore extending this framework to multi-relational and temporal graphs, where the extra dimensions can encode relationship types and time-varying structures.
Summary updated