Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Connection Laplacians and Gauge Theory on Graphs

7 minute read

Published:

TL;DR: A cellular sheaf with orthogonal restriction maps O_{u▷e} ∈ O(d) is called a connection or vector bundle with connection on G. Its Sheaf Laplacian is the Connection Laplacian L_C, which appears in angular synchronisation, cryo-EM reconstruction, and 3D point cloud alignment. Gauge transformations act as O(d) rotations at each node; gauge-invariant quantities (spectrum of L_C, holonomy around cycles) are the only physically meaningful ones. Equivariant sheaf GNNs are exactly gauge-equivariant models on vector bundles over graphs.

From General Sheaves to Connections

A general cellular sheaf has restriction maps F_{v▷e} ∈ ℝ^{d×d}. When these maps are constrained to be orthogonal matrices — F_{v▷e} ∈ O(d) — the sheaf is called an O(d)-connection (or vector bundle with connection) on G.

The Connection Laplacian is:

[L_C]_{uv} = −O_{u▷e}ᵀ O_{v▷e} (for adjacent u, v via edge e) [L_C]_{uu} = deg(u) · I_d

This is exactly the Sheaf Laplacian Δ_F when all F_{v▷e} are orthogonal. Note: O_{u▷e}ᵀ O_{v▷e} = O_{u▷e}ᵻ O_{v▷e} (since Oᵀ = O⁻¹ for orthogonal matrices).

The (u,v) block of L_C is an orthogonal matrix (times −1) — each off-diagonal block encodes the “relative orientation” between nodes u and v, as seen from the edge e.

Gauge Symmetry

A gauge transformation at node v is an invertible linear map g_v : F(v) → F(v) applied locally. For O(d)-connections, gauge transformations are rotations g_v ∈ O(d).

Under a gauge transformation {g_v : v ∈ V}, the restriction maps transform as:

O_{v▷e} ↦ g_{target(e)} · O_{v▷e} · g_v⁻¹

where target(e) is the edge stalk (which has its own gauge). This is exactly the gauge transformation of a vector bundle connection in differential geometry.

Gauge invariance of L_C: The eigenvalues of L_C are gauge-invariant — they depend only on the holonomy of the connection, not on the choice of local frame at each node. This is why the spectrum of L_C is a meaningful invariant of the graph-with-connection.

Gauge equivariance of sheaf diffusion: The solution X(t) to dX/dt = −L_C X transforms equivariantly: if X(0) transforms by {g_v}, then X(t) transforms by {g_v} for all t. Equivariant sheaf GNNs encode this symmetry exactly.

Holonomy: Curvature Around Cycles

For a cycle γ = (v₀, v₁, v₂, …, v_k = v₀), the holonomy of the connection around γ is:

Hol(γ) = O_{v₀▷e₀₁}ᵻ O_{v₁▷e₀₁} · O_{v₁▷e₁₂}ᵻ O_{v₂▷e₁₂} · ... · O_{v_{k-1}▷e_{k-1,k}}ᵻ O_{v_k▷e_{k-1,k}}

(composing the “transport” around the cycle). The holonomy Hol(γ) ∈ O(d) measures how a vector is rotated after parallel transport around γ.

Trivial holonomy: Hol(γ) = I for all cycles γ. This means the connection is flat — there exists a consistent global gauge where all restriction maps are the identity. A flat connection has dim H⁰ = d (full-rank global sections).

Non-trivial holonomy: The connection has curvature — information is “twisted” as it travels around cycles. For H¹ ≠ 0, cycles contribute non-trivial holonomy that cannot be gauged away.

Intuition for neural networks: When a sheaf GNN learns orthogonal restriction maps, it is learning a discrete connection on a graph — assigning a relative rotation to each edge. If the learned connection has high holonomy (strong curvature), the model has encoded that information about the graph's relational structure changes as one moves around cycles. This is richer than what a standard GNN can represent.

Angular Synchronisation: The Classic Problem

Problem: Given a graph G and noisy measurements of relative angles θ_{uv} ∈ SO(2) for each edge (u,v), recover the absolute angles θ_v ∈ SO(2) for each node.

This is equivalent to: given an O(2)-connection with measurements O_{u▷e}ᵻ O_{v▷e} ≈ R(θ_{uv}), find the gauge transformation {g_v} that makes all restriction maps close to identity.

The Connection Laplacian arises naturally: the synchronisation problem can be solved via:

min_{θ} Σ_{(u,v)∈E} ||θ_v − R(θ_{uv})θ_u||²_F = min_X xᵀ L_C x

where x = (θ_v)_v is the concatenation of angle vectors. The solution is the bottom eigenvectors of L_C — the global sections of the O(2)-connection.

Applications: cryo-EM reconstruction, sensor network localisation, 3D point cloud alignment, camera calibration from relative poses.

General d: SO(d) Synchronisation

The angular synchronisation problem generalises to SO(d) synchronisation:

min_{R_v ∈ SO(d)} Σ_{(u,v)∈E} ||R_v − O_{uv} R_u||²_F

where O_{uv} ∈ SO(d) are noisy relative rotations. Again solved via the bottom eigenvectors of the Connection Laplacian.

Singer & Wu (2011) proved that for random measurements with sufficient signal-to-noise ratio, the spectral method based on L_C recovers the true orientations with high probability. This is the foundational result connecting spectral graph theory, sheaf theory, and synchronisation.

Gauge-Equivariant Sheaf GNNs

A sheaf GNN is gauge-equivariant if its output transforms equivariantly under gauge transformations: for all gauge transformations {g_v ∈ O(d)},

f({g_v · x_v}, {O_{v▷e}}) = {g_v · f({x_v}, {O_{v▷e}})}

where f is the network mapping node features to output node features.

Conditions for gauge equivariance:

  1. The message computation must use only gauge-invariant information (e.g., inner products xᵤᵀ O_{u▷e}ᵻ O_{v▷e} x_v)
  2. The aggregation must be equivariant: when x_u transforms by g_u, the aggregated message at v transforms by g_v
  3. The update function must be O(d)-equivariant

Standard NSD achieves approximate gauge equivariance by learning orthogonal-ish maps (constrained to near-orthogonal via regularisation or parameterisation). True gauge-equivariant sheaf GNNs require explicit orthogonal parameterisation of restriction maps.

Parameterising Orthogonal Maps

Learning O(d)-valued restriction maps requires differentiable parameterisation of the orthogonal group:

Exponential map: O = exp(A) where A is skew-symmetric (Aᵀ = −A). Parameterise A, compute O via matrix exponential. Differentiable but expensive for large d.

Cayley map: O = (I−A)(I+A)⁻¹ for skew-symmetric A. Cheaper than exp, covers the same O(d) component.

Householder: Build O as a product of Householder reflections. Used in some equivariant network parameterisations.

Gram-Schmidt: Parameterise a general matrix M ∈ ℝ^{d×d}, then orthogonalise via Gram-Schmidt. Differentiable (via the orthogonalization gradient).

Givens rotations: O = ∏{i<j} G{ij}(θ_{ij}) where G_{ij} is a 2D rotation in the (i,j) plane. Parameterise the d(d−1)/2 angles θ_{ij}.

Connection to Geometric Deep Learning

The Connection Laplacian is the discrete analogue of the gauge-covariant Laplacian in differential geometry, which acts on sections of a vector bundle. In this analogy:

  • Graph nodes → points on a manifold
  • Node stalks → fibres of a vector bundle
  • Restriction maps → parallel transport maps
  • Connection Laplacian → Bochner Laplacian

This connection to Riemannian geometry explains why sheaf GNNs with orthogonal maps are naturally positioned to handle geometric graph learning tasks — molecular force fields, protein structure, point cloud alignment — where the relevant symmetries are continuous rotation groups.

References

You May Also Enjoy

Open Problems and Future Directions in Sheaf Neural Networks

5 minute read

Published:

Sheaf Neural Networks are a young field with many open research problems. This post surveys the most important unsolved questions: scalability to million-node graphs, stochastic sheaves for uncertainty quantification, sheaf autoencoders for generative models, connections to persistent homology, and unification with other topological deep learning frameworks.

Sheaf GNNs for Molecular Property Prediction

7 minute read

Published:

Molecular graphs are naturally heterophilic — atoms of different types bonded together — and have rich geometric structure (bond angles, torsion angles). Sheaf GNNs can encode this structure via restriction maps that represent the relational geometry between bonded atoms. This post explores how sheaf theory applies to molecular property prediction.

Sheaf GNNs for Heterophilic Node Classification: Benchmarks and Results

6 minute read

Published:

A systematic comparison of sheaf GNNs against baselines on standard heterophilic node classification benchmarks. Which datasets benefit most from sheaf structure? How does stalk dimension d affect performance? When do sheaves win — and when don’t they?

Sheaves Meet Attention: Transformer-Inspired Sheaf Models

6 minute read

Published:

Graph Transformers use global attention to capture long-range dependencies that local message passing misses. Sheaf Transformers combine sheaf-based local aggregation (with learnable relational geometry) with global attention (for long-range dependencies). This post surveys the design space of sheaf-augmented attention models.