Hermitian Representations for Directed Graph Neural Networks

144 concepts61 papers2 proposals

Spectral Graph Neural Networks (GNNs) and spectral clustering algorithms owe their theoretical elegance to the Graph Fourier Transform. By projecting graph signals onto the eigenvectors of a graph Laplacian, these methods allow us to filter noise, detect communities, and capture global structural patterns.

However, this mathematical machinery traditionally comes with a strict caveat: the underlying graph must be undirected. For the math to work smoothly, the graph's adjacency matrix must be symmetric, which guarantees that the resulting Laplacian is symmetric and positive semi-definite. This symmetry ensures two critical properties: all eigenvalues are real-valued (acting as clean analog frequencies), and the eigenvectors form an orthogonal basis.

When we try to apply standard spectral methods to directed graphs (digraphs), this elegant framework shatters. Asymmetric adjacency matrices yield complex eigenvalues and non-orthogonal eigenvectors, leading to severe numerical instability and training divergence during spectral filtering, as noted by Koke.

Historically, the standard workaround has been symmetrization—simply treating the directed graph as undirected by averaging the forward and backward edges. But as Fiorini et al. point out, this brute-force fix causes "topology collapse," erasing the very source-sink dynamics, reciprocal relationships, and directional flows that define the network. Monti et al. attempted to preserve directionality by decomposing graphs into multiple motif-based Laplacians, but this adds significant computational complexity.

How can we preserve directional asymmetry while maintaining the mathematical stability of symmetric operators? The answer lies in mapping graphs to the complex plane using Hermitian matrices.

The Intuition: Phase-Encoded Directionality

A Hermitian matrix $H$ is equal to its own conjugate transpose ($H = H^*$). Crucially, linear algebra guarantees that all eigenvalues of a Hermitian matrix are real, and its eigenvectors can form an orthonormal basis—exactly like a real symmetric matrix.

By representing a directed graph using a complex-valued Hermitian matrix, we can encode asymmetric directional flow into the imaginary components while keeping the overall operator mathematically stable. The core mechanism relies on a beautiful geometric division of labor:

  1. Magnitude ($|z|$) encodes the existence or strength of a connection (the underlying undirected geometry).
  2. Phase Angle ($\arg(z)$) encodes the direction or flow of the connection.

Imagine two nodes, $u$ and $v$. If there is a directed edge from $u \to v$, we assign it a complex value with a positive phase shift, such as $e^{i\theta}$. To maintain the Hermitian property, the reverse edge $v \to u$ must be assigned the complex conjugate, $e^{-i\theta}$.

   e^{iθ} (Forward Flow: +θ Rotation)
  u ───────────────────────────────► v
    ◄───────────────────────────────
   e^{-iθ} (Backward Flow: -θ Rotation)

This formulation treats directional flow as a geometric rotation in the complex plane. Moving along the direction of the edge rotates the signal forward, while moving against it rotates it backward. Because the matrix is Hermitian, these complex rotations perfectly cancel out when computing the matrix's quadratic form, forcing the resulting eigenvalues to remain real. As Zhang et al. and Lin et al. demonstrated, this allows researchers to apply standard spectral graph convolutions and multi-scale framelet transforms directly to directed graphs without losing directional information.

The Magnetic Laplacian

The primary mathematical vehicle for this idea is the Magnetic Laplacian. In standard graph signal processing, the Laplacian penalizes the difference between neighboring node values. The Magnetic Laplacian extends this by incorporating the phase shift $e^{i\theta}$ directly into the difference operator.

As Jaquard et al. explain, the Magnetic Laplacian penalizes the discrepancy between a node's value and its neighbor's value after adjusting for the specific phase offset defined on the edge. If a signal's values change smoothly along the direction of the network's flow, the phase-adjusted differences will be small, corresponding to a low "magnetic frequency." If the signal fights the flow, the penalty spikes.

This phase-encoding trick is remarkably flexible. Beyond just direction, the phase angle can simultaneously encode multiple edge properties:

  • Signs and Directions: He et al. (introducing the Magnetic Signed Laplacian) and Fiorini et al. (introducing SigMaNet) showed that edge direction and edge sentiment (positive vs. negative relationships) can be unified into a single phase angle.
  • Universal Graph Learning: Ko et al. leveraged this unified representation to perform graph contrastive learning across undirected, directed, and signed graphs simultaneously without changing the underlying network architecture.
  • Physical Flow Constraints: Fuchsgruber et al. applied complex phase shifts to graph boundary operators, allowing GNNs to simulate physical orientation-equivariant edge signals (like water flow in pipes) without sign-flipping ambiguities.

To accelerate practical adoption, He et al. consolidated these various complex-valued operators into the open-source library PyTorch Geometric Signed Directed (PyGSD), making it easier to deploy Hermitian GNNs on real-world asymmetric networks like citation and financial transaction webs.

Why It Works for Spectral Clustering

The benefits of Hermitian representations extend far beyond neural networks into unsupervised community detection. In traditional spectral clustering, separating a graph into $k$ distinct communities requires calculating the first $k$ eigenvectors of the Laplacian, using the sign or magnitude of the entries to group nodes.

When we move to the complex plane, a single eigenvector contains twice as much information because each entry has both a real and an imaginary part. Sun et al. discovered a powerful property of Hermitian adjacency matrices: the phase angles of a single complex-valued eigenvector can distinguish multiple clusters simultaneously.

Instead of just finding dense, isolated clusters, the bottom eigenvector of a normalized Hermitian Laplacian maps nodes to different angles around the complex unit circle based on their functional roles in a sequential flow (e.g., separating sources, intermediaries, and sinks).

                 Im (Imaginary)
                       ▲
                       │    Intermediate Nodes
                       │         (90°)
                       │        *  *
                       │      *      *
                       │     *        *
  Source Nodes (180°)  │                *  Sink Nodes (0°)
  * * * * * * * * * * *┼──────────────────* * * * * * * * * ► Re (Real)
                       │     *        *
                       │      *      *
                       │        *  *
                       │    (270°)
                       │  Cyclic / Feedback Nodes

By encoding directed edges as complex roots of unity, algorithms developed by Martin et al. and analyzed by Tyler et al. can automatically discover complex, non-symmetric meta-graphs—such as large-scale cycles or multi-tiered hierarchies—that are completely invisible to real-valued spectral methods.

Scaling to Higher-Order Topologies

Real-world systems rarely consist of simple pairwise interactions. Often, relationships occur in groups (hypergraphs) or require tracking how vector spaces twist across a network (cellular sheaves). The intuition of phase-encoded directionality scales naturally to these advanced topological structures.

Directed Hypergraphs

In a directed hypergraph, a single hyperedge connects a set of source nodes to a set of target nodes (for example, representing a chemical reaction where multiple reactants combine to create multiple products). Fiorini et al. (GeDi-HNN) and Mule et al. (DSHN) solved this by constructing complex-valued incidence matrices. Nodes are assigned specific phase angles based on whether they act as a source or a sink within the hyperedge, yielding a stable, positive semi-definite hypergraph Laplacian. Fiorini demonstrated that this approach provides massive performance boosts when classifying complex chemical transformations via directed line graphs.

Directed Cellular Sheaves

Cellular sheaf neural networks generalize GNNs by associating distinct vector spaces (stalks) with each node and edge, using restriction maps to pass signals. Historically, these models were blind to edge direction. Fiorini et al. (Sheaves Reloaded) introduced Directed Cellular Sheaves by embedding edge directionality directly into the phase of complex-valued restriction maps. This topological integration allows models to handle highly heterophilic graphs (where connected nodes have completely different labels) while maintaining the strict numerical stability required for deep diffusion-based learning.

By mapping asymmetric relationships into symmetric complex spaces, Hermitian representations successfully bridge the gap between directional structure and spectral stability, providing a unified mathematical foundation for learning on complex networks.

Key Foundational Work

Unsupervised Clustering of Human Pose Using Spectral Embedding (2012) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 76 papers
  2. Version 1 · 2026-10-04 · 107 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_complex_valued_graph_representation_ba3b85ee,
  title = {complex-valued graph representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complex-valued-graph-representation/rdr_ba3b85ee15c54f83a1aa5b3ed4df7478},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_complex_valued_graph_representation_ba3b85ee_v2,
  title = {complex-valued graph representation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/complex-valued-graph-representation/rdr_ba3b85ee15c54f83a1aa5b3ed4df7478/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake