Graph Learning in 4D: A Quaternion-Valued Laplacian to Enhance Spectral GCNs

Stefano Fiorini, Stefano Coniglio, Michele Ciavotta, Enza Messina

TL;DR

Spectral Graph Convolutional Networks (GCNs) historically struggle with directed graphs, especially when pairs of opposing directed edges (digons) have different weights. QuaterGCN solves this by formulating the Quaternionic Laplacian—a 4D quaternion-valued graph operator that cleanly segregates undirected edges, one-way directed edges, and asymmetric digons across its real and imaginary components. The result is a mathematically rigorous spectral GCN that preserves complete graph topology without collapsing edge directions or signs.

What Problem Does This Paper Address?

Spectral GCNs rely on algebraic graph theory and Fourier transforms over the graph Laplacian. While powerful, the classical graph Laplacian only works naturally on unweighted, undirected graphs.

Recent extensions introduced complex numbers to handle directionality and negative weights (such as the Magnetic Laplacian and Sign-Magnetic Laplacian). However, real-world networks—such as financial transactions, traffic, and citation networks—frequently contain asymmetric digons: bidirectional links where edge weight $A_{uv} \neq A_{vu}$ (for example, author $u$ citing author $v$ 50 times, but $v$ citing $u$ only twice). Prior Laplacians either averaged these links or collapsed them into a single dominant edge, erasing critical topological information.

Methods

The authors leverage the quaternion number system ($\mathbb{H}$), an extension of complex numbers with three distinct imaginary units satisfying $i^2 = j^2 = k^2 = ijk = -1$.

The Quaternionic Laplacian ($L^\ϙ$)

A quaternion entry $q = q_0 + i q_1 + j q_2 + k q_3$ provides four orthogonal dimensions. The Quaternionic Laplacian $L^\ϙ = \bar{D}_s - H^\ϙ$ maps graph topology into these dimensions:

  • Real component ($q_0$): Encodes undirected edges and symmetric digons ($A_{uv} = A_{vu}$).
  • First imaginary component ($i$): Encodes one-way directed edges that have no reverse edge.
  • Second and third imaginary components ($j$ and $k$): Encode asymmetric digons ($A_{uv} \neq A_{vu}$), recording the forward edge along $j$ and the backward edge along $k$.

The authors prove that $L^\ϙ$ is Hermitian, positive semidefinite, has a spectrum upper-bounded by 2, and generalizes both the classical Laplacian and the complex Sign-Magnetic Laplacian.

QuaterGCN Architecture

Using a first-order Chebyshev polynomial approximation of the spectral convolution, the network updates quaternion-valued node representations:

  1. Quaternion convolutional layers aggregate signals using $L^\ϙ$ and learnable quaternion parameter matrices $\Theta \in \mathbb{H}^{c \times f}$.
  2. A component-wise activation function (e.g., ReLU applied separately to each of the four components) preserves quaternion structure.
  3. An unwind layer unpacks the resulting $n \times f$ quaternion matrix into a real-valued $n \times 4f$ matrix, which feeds into standard dense classification layers.

Datasets

The authors evaluated QuaterGCN on both real-world and synthetic datasets:

  • Real-world networks:
  • Directed graphs with signed weights: Bitcoin-OTC, Bitcoin Alpha, and WikiRfa.
  • Directed graphs with positive weights: Telegram.
  • Graphs with sign-only edges ($\{-1, 0, +1\}$): Slashdot and Epinions.
  • Synthetic networks:
  • DSBM: Directed stochastic block models with cluster structures (digon-free).
  • Di150 & Di500 (Newly introduced): Synthetic directed graphs with 150 and 500 nodes per cluster, respectively, parameterized with a controllable proportion of asymmetric digons ($\delta \in \{0.2, 0.5, 0.7\}$).

Key Insights and Ideas

  • Topology preservation without collapse: By utilizing 4D hypercomplex space, QuaterGCN is the first spectral method that does not lose edge directionality or relative edge magnitudes in bidirectional links.
  • Laplacian over architecture: Previous quaternion graph networks (like QGNN) simply applied quaternion network weights on top of a standard real-valued Laplacian. QuaterGCN demonstrates that the real expressive boost comes from constructing the Laplacian itself in quaternion space.
  • Sparsity resilience: As graphs become sparser and digon-heavy, traditional methods degrade rapidly (often dropping to random guessing). The structured phase encoding of $L^\ϙ$ provides strong inductive bias when edge signals are scarce.

Key Results

  • Node Classification (NC): QuaterGCN achieved the top performance in 9 out of 10 benchmark setups, averaging a 68.27% improvement over the second-best models. On the sparse synthetic dataset Di500 ($\delta=0.7$), it scored 71.58% accuracy, whereas all existing baseline methods collapsed to roughly 20%. Compared directly to QGNN, QuaterGCN outperformed it by 309% on average.
  • Edge Prediction (3CEP, 4CEP, 5CEP): On multi-class link prediction across signed and directed benchmarks, QuaterGCN achieved best or second-best accuracy in nearly all cases:
  • Ranked first on 7 of 9 datasets for 3-class edge prediction.
  • Ranked first on 8 of 10 tasks across 4-class and 5-class signed edge prediction (e.g., reaching 61.74% on Bitcoin Alpha and 81.10% on Epinions in 4CEP).

Limitations and Future Work

  • Computational Overhead: While the asymptotic complexity remains quadratic in the number of nodes ($O(n^2)$)—matching other spectral methods—a quaternion product requires 8 real multiplications and 7 additions (versus 1 multiplication for real numbers). Certain low-level kernel operations can run significantly slower in constant-factor time.
  • Future Directions: The authors plan to extend the quaternionic framework to multi-relational graphs (such as knowledge graphs with multiple edge relation types) and temporal/dynamic graphs where directions and weights shift over time.

Summary updated

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 within the spectral GCN SigMaNet to handle digraphs with weights of arbitrary sign). In addition to its generality, QuaterGCN is the only Laplacian to completely preserve the (di)graph topology that we are aware of, as it can handle graphs and digraphs containing antiparallel pairs of edges (digons) of different weight without reducing them to a single (directed or undirected) edge as done by 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.
BibTeX
@inproceedings{fiorini2024graph,
  author = {Stefano Fiorini and Stefano Coniglio and Michele Ciavotta and Enza Messina},
  title = {{Graph Learning in 4D: A Quaternion-Valued Laplacian to Enhance Spectral GCNs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=VEeRRgeswX},
}

Loading related content...

Figure