Source-linked AI summary
Hyperbolic Graph Convolutional Neural Networks
Ines Chami, Rex Ying, Christopher Ré, Jure Leskovec
TL;DR
Euclidean GCNs can distort hierarchical and scale-free graph structure, while existing hyperbolic methods do not fully combine hyperbolic geometry with rich node features and inductive GCNs. HGCN derives hyperbolic GCN operations with hyperbolic attention and trainable layer-wise curvature, and experiments report improved performance over Euclidean baselines, including new state-of-the-art results on PUBMED. The method is most effective on graphs with high hyperbolicity, while its performance depends on graph structure and tangent-space assumptions.
Problem
Euclidean GCN embeddings can have high distortion on hierarchical and scale-free graphs, motivating a method that combines graph neural networks with hyperbolic geometry.
Method
HGCN maps Euclidean features into hyperbolic embeddings, derives hyperboloid-model GCN operations, uses hyperbolic attention, and learns curvature at each layer.
Results
HGCN reduces error by up to 63.1% for link prediction and 47.5% for node classification compared with Euclidean state-of-the-art GCNs, while improving PUBMED results.
Takeaways & Limitations
HGCN’s gains are strongest on graphs with high hyperbolicity, where the paper reports average error reductions of 45.4% for link prediction and 12.3% for node classification.
Takeaways & Limitations
The authors conjecture that HGCN works better on graphs with small δ-hyperbolicity, and tangent-space operations require shared north-pole tangent spaces across curvatures.
Abstract
from arXiv · showhide
Graph convolutional neural networks (GCNs) embed nodes in a graph into Euclidean space, which has been shown to incur a large distortion when embedding real-world graphs with scale-free or hierarchical structure. Hyperbolic geometry offers an exciting alternative, as it enables embeddings with much smaller distortion. However, extending GCNs to hyperbolic geometry presents several unique challenges because it is not clear how to define neural network operations, such as feature transformation and aggregation, in hyperbolic space. Furthermore, since input features are often Euclidean, it is unclear how to transform the features into hyperbolic embeddings with the right amount of curvature. Here we propose Hyperbolic Graph Convolutional Neural Network (HGCN), the first inductive hyperbolic GCN that leverages both the expressiveness of GCNs and hyperbolic geometry to learn inductive node representations for hierarchical and scale-free graphs. We derive GCN operations in the hyperboloid model of hyperbolic space and map Euclidean input features to embeddings in hyperbolic spaces with different trainable curvature at each layer. Experiments demonstrate that HGCN learns embeddings that preserve hierarchical structure, and leads to improved performance when compared to Euclidean analogs, even with very low dimensional embeddings: compared to state-of-the-art GCNs, HGCN achieves an error reduction of up to 63.1% in ROC AUC for link prediction and of up to 47.5% in F1 score for node classification, also improving state-of-the art on the Pubmed dataset.
1 Introduction
Real-world hierarchical and scale-free graphs can be poorly represented by Euclidean GCN embeddings, motivating inductive GCNs built in hyperbolic geometry. HGCN addresses feature transformation, neighborhood aggregation, and layer-wise curvature selection while improving benchmark performance.
- Motivation: Euclidean embeddings incur high distortion on scale-free and hierarchical graphs because graph volume grows exponentially while Euclidean ball volume grows polynomially.Scale-free graphs have tree-like structure, creating a mismatch between graph geometry and Euclidean geometry.
- Motivation: Hyperbolic embeddings reduce distortion for scale-free and hierarchical graphs, but existing hyperbolic methods often omit node features, scalability, or inductive inference.The cited comparison highlights the limitations of shallow hyperbolic embeddings relative to deep GCNs.
- HGCN: HGCN derives hyperboloid-model GCN operations, introduces hyperbolic attention aggregation, and learns trainable curvature separately at each layer.These components target Euclidean inputs, hyperbolic aggregation, and the choice of geometry across layers.
- HGCN: HGCN jointly trains convolution weights, layer-wise curvatures, and hyperbolic attention to learn inductive embeddings that reflect graph hierarchies.The model transforms between hyperbolic spaces at different layers to seek low distortion and class-label separation.
- Results: HGCN reduces error by 11.5%–47.5% for node classification and 28.2%–63.1% for link prediction against Euclidean state-of-the-art graph neural networks.It also achieves new state-of-the-art results on PUBMED and analyzes geometry transformation from Euclidean features to hyperbolic embeddings.
2 Related Work
Graph representation learning includes shallow transductive embeddings and inductive GCNs. Shallow methods can miss node features, fail to generalize to unseen graphs, and scale poorly with graph size.
- Transductive shallow embeddings: Shallow embedding methods optimize node embeddings directly through reconstruction objectives, using an embedding look-up from graph nodes to vectors.Examples include matrix factorization, random-walk methods, and hyperbolic embedding approaches.
- Transductive shallow embeddings: Shallow Euclidean and hyperbolic methods fail to leverage rich node features, limiting their usefulness for tasks such as node classification.The passage identifies feature omission as one of three major downsides.
- Transductive shallow embeddings: Shallow methods are transductive and therefore cannot perform inference on unseen graphs.This distinguishes them from GCNs, which learn mappings from graph structure and node features.
- Transductive shallow embeddings: Shallow methods scale poorly because their number of model parameters grows linearly with the number of nodes.The related-work discussion contrasts this parameterization with neural mappings used by graph neural networks.
3 Background
The paper formulates graph representation learning over Euclidean node features and introduces GCN message passing alongside the hyperboloid model of hyperbolic space. Hyperbolic operations use tangent spaces and exponential/logarithmic maps to enable Euclidean-style computation.
- Problem setting: Graph representation learning seeks a mapping from graph structure and d-dimensional input node features to lower-dimensional embeddings for downstream tasks.The embeddings are intended to capture structural and semantic information for node classification and link prediction.
- Graph convolutional neural networks: A GCN layer transforms a node’s representation and aggregates messages from its neighbors using learned weights and a nonlinear activation.Aggregation weights may be computed by different mechanisms, and multiple layers propagate messages across neighborhoods.
- Hyperboloid model: The hyperboloid model represents hyperbolic space with constant negative curvature −1/K and uses a Minkowski inner product.The manifold and tangent space are defined through constraints involving that inner product.
- Tangent spaces: Tangent spaces provide local Euclidean approximations where operations undefined in hyperbolic space can be performed.The restriction of the Minkowski inner product to a tangent space is positive definite.
- Manifold maps: Exponential and logarithmic maps convert between tangent-space vectors and hyperbolic points, enabling operations to move into tangent spaces and back.In hyperbolic space, these maps form a bijection between the manifold and a tangent space at a point.
4 Hyperbolic Graph Convolutional Networks
HGCN extends inductive GCNs to hyperbolic geometry by mapping Euclidean features into hyperbolic space and performing transformation, attention-based aggregation, and curvature-aware message passing. Its trainable layer-wise curvature and hyperbolic operations support embeddings for downstream link prediction and node classification.
- Feature transformation: Hyperboloid feature transformation uses logarithmic and exponential maps around Euclidean tangent spaces to implement matrix multiplication and bias translation.The weight matrix acts in a tangent space, while parallel transport supports bias addition on the manifold.
- Neighborhood aggregation: Hyperbolic attention computes neighbor importance in the tangent space and aggregates representations locally around each center point.This avoids the unavailable closed-form Fréchet mean and yields lower-distortion local aggregation than aggregation at the origin.
- Empirical behavior: HGCN preserves hierarchy on DISEASE embeddings and improves class separation on CORA visualizations, while GCN embeddings capture DISEASE hierarchy poorly.The reported visualizations use the Poincaré disk for HGCN embeddings.
- Architecture: HGCN maps Euclidean input features to the hyperboloid manifold and stacks hyperbolic graph-convolution layers with trainable curvature.Each layer transforms and aggregates neighbor embeddings in the center node’s tangent space before projecting to a hyperbolic space with different curvature.
- Prediction tasks: The model converts final hyperbolic embeddings for link prediction or node classification using a Fermi-Dirac decoder or logarithmic-map-based Euclidean regression.Link prediction is trained with cross-entropy and negative sampling; node classification also includes a link-prediction regularization objective.
5 Experiments
HGCN is evaluated across diverse graph datasets, tasks, and settings, with analyses of hyperbolicity, components, embeddings, and attention. It generally improves over Euclidean and other baselines on hierarchical graphs, while results depend on graph structure and model components.
- Experimental setup: Experiments cover node classification and link prediction across transductive and inductive settings, comparing HGCN with shallow and GNN-based baselines.The evaluation uses a variety of open graph datasets and includes visual analyses of hierarchical structure and link-prediction expressiveness.
- Results: HGCN’s gains over Euclidean GNNs correlate with graph hyperbolicity, with average error reductions of 45.4% for LP and 12.3% for NC on graphs with low δ.The authors conjecture that HGCN performs better on graphs with smaller δ-hyperbolicity, which indicates more tree-like structure.
- Results: On CORA, HGCN does not outperform Euclidean GNNs, but remains significantly more effective than GCN at small dimensions and achieves better label separation.The result suggests that Euclidean geometry better matches CORA’s underlying graph structure, while low-dimensional HGCN embeddings can still separate classes effectively.
- Ablations: Both hyperbolic attention and trainable curvature improve performance, with their combination producing further gains over fixed-curvature, no-attention HGCN.Attention also outperforms aggregation in tangent space at the origin.
- Visualizations: HGCN embeddings preserve tree structure and hierarchy, with nodes near the center representing higher positions in the hierarchy.The visualization uses 3-dimensional hyperbolic embeddings mapped to the Poincaré disk for comparison with GCN.
- Visualizations: In DISEASE neighborhoods, HGCN assigns greater attention to high-hierarchy nodes such as a center node’s parent or grandparent.This hyperbolic attention is linked to disease-spread structure, where sick parents propagate disease to their children.
6 Conclusion
HGCN learns hyperbolic embeddings with graph convolutional networks, mapping Euclidean input features into hyperbolic spaces with trainable curvatures at every layer.
- HGCN learns hyperbolic embeddings using graph convolutional networks for real-world hierarchical and scale-free graphs.
- Geodesic distance is defined as the infimum of curve lengths over continuously differentiable curves joining two points.
- Hyperbolic space is a complete, simply connected Riemannian manifold with constant negative sectional curvature.
- The Poincaré ball model represents hyperbolic space as a Riemannian manifold with constant negative curvature −1 in d dimensions.
A.2.2 Hyperboloid model
The hyperboloid model represents hyperbolic space using the Minkowski inner product and supports projections, distance computations, and connections to the Poincaré disk.
- The hyperboloid model defines hyperbolic space through the Minkowski inner product in d dimensions with constant negative curvature −1.
- The induced distance between two points in the hyperboloid model is computed from the model’s geometric structure.
- Geodesics in the hyperboloid model provide the basis for extending results to curvature −1/K and learning K as an HGCN parameter.
- Projections constrain embeddings and tangent vectors to remain on the manifold and their tangent spaces during optimization.
- The hyperboloid model is more stable for optimization, while the Poincaré model is more interpretable and directly visualizable on the Poincaré disk.
B Proofs of Results
The proofs establish geodesic, exponential, and logarithmic-map results for hyperbolic spaces with arbitrary curvature.
- The appendix re-derives hyperbolic-geometric results for arbitrary curvature using the unit-speed geodesics of the hyperboloid model.
- The unique unit-speed geodesic in the hyperboloid model is used to derive the intrinsic distance between two points.
- Proposition 3.2 gives the exponential and logarithmic maps for points and tangent vectors in the hyperboloid model.
- The derivation normalizes a nonzero tangent vector by its Lorentz norm before constructing the corresponding geodesic.
B.2 Curvature
The curvature results show that embeddings can be transferred between hyperbolic spaces with different curvatures while preserving link-prediction expressiveness.
- A mapping between hyperbolic spaces with curvatures −1/K and −1/K′ scales all pairwise Minkowski inner products by a curvature-dependent constant.
- The mapping preserves membership in the target hyperboloid because the transformed self-inner product equals −K′.
- With infinite precision, hyperbolic spaces with varying curvatures have the same expressive power for link prediction.
- The Fermi-Dirac decoder can reconstruct the same graph after changing curvature when decoder parameters are adjusted.
- The reconstructed graph from H′ is identical to the graph reconstructed from H.
C.1 Dataset statistics
This section refers readers to Table 3 for detailed dataset statistics.
- Dataset statistics are detailed in Table 3.
C.2 Training details
HGCN’s training pipeline uses Euclidean parameterization to support regularization and applies projections to constrain hyperbolic embeddings.
- Parameter optimization: Linear transformations and attention are defined on tangent spaces, with their parameters represented in Euclidean space.
- Regularization: DropConnect randomly zeros elements of Euclidean neural-network parameters during training to improve HGCN generalization.
- Projections: Projections are applied after feature transforms and logarithmic or exponential maps to constrain hyperboloid embeddings.