PaperlayerView exact revision on arXiv

Source-linked AI summary

Constant Curvature Graph Convolutional Networks

Gregor Bachmann, Gary Bécigneul, Octavian-Eugen Ganea

arXiv:1911.05076v3cs.LGcs.AI

TL;DR

Graph neural networks are largely formulated with Euclidean operations despite evidence that some data are better represented by non-Euclidean geometries. The paper extends GCNs to products of constant-curvature spaces with a unified gyro framework and differentiable curvature interpolation, reporting competitive or improved task performance while noting limitations in existing theoretical analysis and intrinsic optimization costs.

  • Problem

    Standard graph neural networks are limited to Euclidean geometry, although hierarchical, scale-free, spherical, and cyclical data can be better represented by non-Euclidean geometries.

  • Method

    The paper combines a unified κ-stereographic gyro framework with GCNs to learn representations in products of constant-curvature spaces.

  • Results

    The models are competitive with Euclidean GCNs and outperform Chami et al. (2019) on Citeseer and Cora for node classification, while the best distortion architecture matches the graph's underlying geometry.

  • Takeaways & Limitations

    The unified models interpolate differentiably between positive, zero, and negative curvature and extend GCN representations beyond the hyperbolic setting.

  • Takeaways & Limitations

    Some intrinsic quantities can require prohibitively expensive optimization with gradients through the solution, and the adaptation of existing theoretical analysis to positive curvature is left for future work.

Abstract

from arXiv · show

Interest has been rising lately towards methods representing data in non-Euclidean spaces, e.g. hyperbolic or spherical, that provide specific inductive biases useful for certain real-world data properties, e.g. scale-free, hierarchical or cyclical. However, the popular graph neural networks are currently limited in modeling data only via Euclidean geometry and associated vector space operations. Here, we bridge this gap by proposing mathematically grounded generalizations of graph convolutional networks (GCN) to (products of) constant curvature spaces. We do this by i) introducing a unified formalism that can interpolate smoothly between all geometries of constant curvature, ii) leveraging gyro-barycentric coordinates that generalize the classic Euclidean concept of the center of mass. Our class of models smoothly recover their Euclidean counterparts when the curvature goes to zero from either side. Empirically, we outperform Euclidean GCNs in the tasks of node classification and distortion minimization for symbolic data exhibiting non-Euclidean behavior, according to their discrete curvature.

1. Introduction

Non-Euclidean geometries provide useful inductive biases for hierarchical, scale-free, spherical, and cyclical data, but standard GCNs operate through Euclidean geometry. The paper introduces a unified constant-curvature framework that extends GCN representations beyond Euclidean space.

  • Graph convolutional networks generalize convolutional architectures to graphs by sharing parameters consistently with graph geometry.
  • Non-Euclidean geometries can better represent hierarchical, scale-free, spherical, or cyclical data than Euclidean geometry.
  • Euclidean embeddings can incur large distortion when representing trees because the number of nodes grows exponentially with tree depth.
  • Hyperbolic space provides a tree-like geometry whose ball volume grows exponentially with radius, supporting embeddings of hierarchical and scale-free structures.
  • The paper proposes GCNs whose representations lie in products of constant-curvature spaces with either curvature sign, using a unified gyro framework.

2. The Geometry of Constant Curvature Spaces

The paper develops a κ-stereographic model that unifies Euclidean, hyperbolic, and spherical geometries through gyrovector operations and Riemannian quantities. Its geometric formulas support continuous and differentiable interpolation across curvature, including the Euclidean limit.

  • The κ-stereographic model uses the spherical stereographic projection for positive curvature and the Poincaré model for negative curvature.
  • The framework extends gyrovector-space operations from hyperbolic geometry to positive curvature and connects them with Riemannian quantities.
  • Closed-form expressions cover distances, geodesics, exponential maps, and logarithmic maps in the constant-curvature model.
  • At κ = 0, the model recovers Euclidean quantities and continuously interpolates between positive and negative curvature geometries.
  • The geometric quantities are differentiable with respect to curvature around zero, with matching first-order derivatives from both sides.

3. κ-GCNs

The κ-GCN extends graph convolutional message passing to constant-curvature spaces by replacing Euclidean matrix operations with κ-stereographic analogues. Its construction combines curvature-aware right multiplication, gyro-based aggregation, and an intrinsic treatment of normalized adjacency matrices.

  • κ-stereographic GCN: κ-GCN operates on node embeddings in the κ-stereographic model, which unifies positive and negative constant curvatures.The model uses stereographic spherical projection for positive curvature and the Poincaré model for negative curvature.
  • Matrix multiplications: Right matrix multiplication transforms each embedding independently, while left multiplication aggregates neighboring embeddings through curvature-aware operations.The paper distinguishes these operations because curvature makes left and right matrix multiplication fundamentally different.
  • Graph convolution: The κ-GCN layer replaces Euclidean adjacency multiplication with curvature-aware aggregation followed by a nonlinearity, preserving the graph-convolutional message-passing structure.In Euclidean GCNs, each node receives a weighted combination of neighboring embeddings before applying σ.
  • Gyro-based aggregation: The κ-left-matrix-multiplication generalizes Euclidean weighted linear combinations by κ-scaling a gyro­midpoint of the input embeddings.This provides the weighted aggregation required to adapt graph message passing to the κ-stereographic model.
  • Intrinsic aggregation: Right-stochastic adjacency matrices make κ-left-multiplication intrinsic to the metric space and compatible with isometries.Because the row weights sum to one, the operation reduces to a gyromidpoint and therefore commutes with isometries.
  • Alternative aggregations: Fréchet/Karcher means and tangential aggregation are alternative intrinsic centroids, but Fréchet/Karcher means can require prohibitively expensive optimization with differentiable solutions.For the κ-stereographic space, uniqueness of the Fréchet/Karcher minimizer holds if and only if κ ≥0.

4. Experiments

The experiments evaluate constant-curvature GCNs on node classification and graph-metric distortion, using real and synthetic datasets designed to exhibit different geometries. Results indicate that geometry-matched models reduce distortion and are competitive for classification.

  • Evaluation: The evaluation covers node classification and minimizing embedding distortion on synthetic and real datasets.Distortion compares embedding distances with graph shortest-path distances.
  • Datasets: The synthetic benchmarks include a depth-5, branching-factor-4 tree, a torus graph, and a spherical graph.The tree contains 1365 nodes and 1364 edges; the torus contains 1000 nodes and 30626 edges.
  • Distortion: The distortion results show that the best-performing architecture matches the graph’s underlying geometry.Models were trained for 10000 epochs, with minimal achieved distortion reported.
  • Node classification: The node-classification comparison uses Citeseer, Cora-ML, and Pubmed against Euclidean and hyperbolic GCN baselines.Table 2 reports average accuracy across 5 splits with 95 percent bootstrap uncertainties; H and S denote hyperbolic and spherical models.
  • Node classification: The proposed models are competitive with Euclidean GCN and outperform the hyperbolic baseline on Citeseer and Cora.The reported comparison attributes this result to the proposed architecture.

5. Conclusion

The paper extends graph convolutional networks from Euclidean vector spaces to constant-curvature geometries and frames graph embeddings through distortion. It presents this as a unified route for message passing and representation across non-Euclidean spaces.

  • Conclusion: The paper introduces a natural extension of GCNs to stereographic models with both positive and negative curvature.The construction supports differentiable interpolation between curvature signs.
  • Conclusion: The unified curvature model permits curvature to be trained independently of its initial sign choice.This follows from differentiable interpolation between positive and negative curvature.
  • Graph convolutional networks: Graph convolutional networks use shared parameters and neighborhood aggregation to produce node embeddings for classification.The same weight matrices are shared across nodes, while neighboring embeddings are averaged through message passing.
  • Embedding distortion: A D-embedding bounds metric-space distances between embedded nodes by scaled graph distances, and the infimum of D is the embedding distortion.A perfect embedding has D = 1.

B.1. Trees and Hyperbolic Space

Trees expose a limitation of Euclidean embeddings because their node counts grow exponentially with depth, whereas hyperbolic geometry expands in a tree-like manner. The section contrasts this with Euclidean distortion bounds and hyperbolic near-isometric embeddings.

  • Trees and Euclidean space: A balanced tree’s exponentially increasing node count makes it difficult for Euclidean space to preserve its geometric structure.The embedding space effectively runs out of room as depth increases.
  • Euclidean lower bound: Every Euclidean embedding of the 3-star K1,3 has distortion at least √3.The lower bound applies in any Euclidean dimension k ∈ N.
  • Hyperbolic geometry: Hyperbolic space remedies this tree-embedding problem because distances diverge near the Poincaré-disk boundary.This boundary expansion mirrors the increasing separation of nodes on different tree branches.
  • Hyperbolic geometry: Trees can be embedded in hyperbolic space with distortion 1 + ϵ for arbitrarily small ϵ.The construction moves points toward the disk boundary.
  • Cycles and spherical geometry: Euclidean space also shortens cycle diagonals, while spherical space can embed any cycle with distortion 1 in one dimension.The spherical construction places cycle nodes evenly around a circle.
  • Spherical model: The standard spherical model depends directly on curvature through a hard constraint, so its domain becomes ill-defined as curvature approaches zero.The stereographic construction is introduced to avoid this issue for interpolation across curvature values.

C.2.2. PROOF OF THEOREM 2

The proof constructs geodesics in the stereographic model by projecting spherical geodesics and inverting the projection. It then obtains the logarithmic and distance maps, with the exponential map converging to its Euclidean counterpart as curvature vanishes.

  • Geodesic construction: A unit-speed geodesic in the stereographic model is obtained by projecting a corresponding geodesic on the sphere.The proof identifies projected initial position and direction before applying the inverse projection.
  • Geodesic construction: The stereographic geodesic expression is derived by applying the inverse projection to the spherical geodesic.This inversion yields the displayed formula for γx,v(t).
  • Maps and distance: The logarithmic map is verified as the inverse of the exponential map, and the distance follows from the norm of the logarithmic map.These identities connect the geodesic construction to the model’s metric operations.
  • Euclidean limit: As curvature tends to zero, the exponential map converges to the Euclidean exponential map.The limit is written as x(v) →κ→0 x + v.

C.2.3. PROOF OF THEOREM 3

The proof expands κ-dependent operations around zero and uses differentiability of their component functions to establish smooth dependence on curvature. It also shows the generalized aggregation preserves key gyrovector and isometry properties.

  • The κ-addition is expanded around zero using a Taylor development, with Euclidean vector addition recovered as the leading term.The first-order curvature correction is expressed through norms and inner products of x and y.
  • Although individual expressions involving |κ|^1/2 are not differentiable at κ = 0, the composed functions used by the model are differentiable there.This applies to κ-dependent tangent expressions and related inverse-square-root terms.
  • The operations ⊗κ, expκ, logκ, and dκ are differentiable functions of κ under Theorem 3’s assumptions.
  • The gyromidpoint is invariant to scalar rescaling, and the resulting aggregation reduces to a gyromidpoint for right-stochastic matrices.

C.2.6. PROOF OF THEOREM 6

The proof establishes algebraic identities for κ-gyrovector operations and uses them to characterize isometries as translations followed by orthogonal transformations. These properties support invariance of the generalized aggregation under isometries.

  • Orthogonal maps commute with κ-addition, providing a key identity for transporting the aggregation through rotations and reflections.
  • The generalized gyration is defined from κ-addition and satisfies linearity, norm preservation, and compatibility relations with κ-addition.
  • Every κ-stereographic isometry is represented as φ(x) = z ⊕κ Rx with R an orthogonal matrix.

D. Logits

The logit layer extends feed-forward classification to κ-stereographic spaces by replacing Euclidean hyperplanes and logits with curvature-aware constructions. The positive-curvature formula is used experimentally, but its geodesic-distance interpretation is not rigorously proved.

  • The κ-GCN adds a curvature-aware logit layer because classification requires mapping representations to label scores.
  • Hyperbolic logits are derived by rewriting Euclidean softmax terms through hyperbolic hyperplanes and κ-dependent distances to those hyperplanes.
  • The positive-curvature softmax formula is inspired by the identity i sin(x) = sinh(ix) and is used for spherical experiments.
  • The rigorous proof that the positive-curvature expression equals distance to geodesic hyperplanes is left for future work.

E. Additional Experiments

An empirical study trains κ-GCNs across curvatures from −5 to 5 on a tree-embedding distortion objective. The results show a smooth geometry transition, with distortion favoring hyperbolic curvature over spherical curvature.

  • κ-GCNs were trained at 200 evenly spaced curvatures in [−5, 5] to embed a small tree while minimizing distortion.Curvature was fixed during training, and a Euclidean GCN with the same architecture was also trained.
  • The distortion changes smoothly across the curvature range, indicating a smooth transition between the different geometries.
  • Distortion improves as hyperbolicity increases and worsens as the embedding space becomes more spherical.
  • A small kink in the spherical model is attributed to numerical issues.

F. More Experimental Details

The experiments use structured data splits for node classification and estimate dataset curvature with the procedure outlined in Algorithm 1. Learned curvatures are reported for the node-classification experiments.

  • The data are divided into training, early-stopping, validation, and test sets through known and unknown node subsets.Most graphs use nknown = 1500, while the airport dataset uses nknown = 2700.
  • Dataset curvature is estimated using the procedure outlined in Algorithm 1, which averages the ψ values computed over sampled graph nodes and neighborhoods.
  • Citation-graph training sets contain 20 data points per label, with 500 nodes reserved for early stopping and the remaining known nodes for validation.
  • The airport known subset is divided into 2100 training nodes, 300 validation nodes, and 300 early-stopping nodes.
  • The whole graph structure and all node features are used unsupervised during the embedding process.
  • Learned curvatures for node classification are reported in Table 3.
Loading 1911.05076v3…