Source-linked AI summary
Hyperbolic Graph Attention Network
Yiding Zhang, Xiao Wang, Xunqiang Jiang, Chuan Shi, Yanfang Ye
TL;DR
Most GNNs use Euclidean geometry even though graph data can have non-Euclidean structure, leaving hyperbolic attention largely unexplored. The paper introduces HAT, which combines gyrovector operations, hyperbolic-proximity attention, and logarithmic/exponential-map acceleration; experiments on four datasets demonstrate superiority over state-of-the-art methods.
Problem
Most GNNs are designed for Euclidean spaces, despite graph structures that can have hierarchical, power-law, and other non-Euclidean properties.
Method
HAT performs graph attention in hyperbolic spaces using gyrovector operations, hyperbolic proximity, and logarithmic and exponential mappings for acceleration.
Results
Experiments on four datasets demonstrate HAT's superiority over state-of-the-art methods in node classification and node clustering.
Takeaways & Limitations
The work provides a first hyperbolic graph attention network for learning graph representations with hyperbolic geometry.
Abstract
from arXiv · showhide
Graph neural network (GNN) has shown superior performance in dealing with graphs, which has attracted considerable research attention recently. However, most of the existing GNN models are primarily designed for graphs in Euclidean spaces. Recent research has proven that the graph data exhibits non-Euclidean latent anatomy. Unfortunately, there was rarely study of GNN in non-Euclidean settings so far. To bridge this gap, in this paper, we study the GNN with attention mechanism in hyperbolic spaces at the first attempt. The research of hyperbolic GNN has some unique challenges: since the hyperbolic spaces are not vector spaces, the vector operations (e.g., vector addition, subtraction, and scalar multiplication) cannot be carried. To tackle this problem, we employ the gyrovector spaces, which provide an elegant algebraic formalism for hyperbolic geometry, to transform the features in a graph; and then we propose the hyperbolic proximity based attention mechanism to aggregate the features. Moreover, as mathematical operations in hyperbolic spaces could be more complicated than those in Euclidean spaces, we further devise a novel acceleration strategy using logarithmic and exponential mappings to improve the efficiency of our proposed model. The comprehensive experimental results on four real-world datasets demonstrate the performance of our proposed hyperbolic graph attention network model, by comparisons with other state-of-the-art baseline methods.
Introduction
Existing GNNs mainly model graphs in Euclidean spaces despite evidence that many graph structures have non-Euclidean, hierarchical, and power-law geometry. HAT addresses this gap with hyperbolic graph attention, gyrovector operations, an acceleration strategy, and experiments on four datasets.
- Most existing GNN models are designed for Euclidean graphs, although graph data can exhibit non-Euclidean latent anatomy.
- Hyperbolic spaces suit hierarchical and power-law graph structures because they expand exponentially and provide a tree-like geometry.
- Hyperbolic GNN design must replace unavailable Euclidean vector operations such as addition and subtraction in non-vector hyperbolic spaces.
- HAT uses gyrovector spaces to process graph features and hyperbolic proximity to define its attention mechanism.
- HAT accelerates hyperbolic computation with logarithmic and exponential mappings while preserving hyperbolic properties.
- Experiments on four datasets report HAT superiority over state-of-the-art methods in node classification and node clustering.
Related Work
Prior GNN research extends neural networks to graph-structured data and incorporates convolutional or attention operations, but these models operate in Euclidean spaces. Hyperbolic representation learning has developed separately for hierarchical graph embeddings and deep models.
- Graph Neural Network: GNNs extend deep neural networks to arbitrary graph-structured data through spectral, localized convolutional, and attention-based approaches.
- Graph Neural Network: Existing GNNs summarized in this work model graphs in Euclidean spaces.
- Hyperbolic Representation Learning: Hyperbolic representation learning has addressed hierarchical graph representations, directed acyclic graphs, and deep learning models.
Preliminaries
Hyperbolic geometry expands faster than Euclidean geometry, making it suitable for graph structures with hierarchy and power-law distributions. Gyrovector spaces provide the algebraic operations needed to work with hyperbolic representations.
- Hyperbolic Spaces and Graph Data: A two-dimensional hyperbolic disk has perimeter 2π sinh r and area 2π(cosh r −1), both growing as e^r, versus linear and quadratic Euclidean growth.
- Hyperbolic Spaces and Graph Data: This exponential expansion makes hyperbolic spaces suitable for graphs with hierarchical structure and power-law distributions.
- Gyrovector Spaces: Gyrovector spaces supply an algebraic formalism for hyperbolic geometry because ordinary vector addition, subtraction, and scalar multiplication are unavailable there.
- Gyrovector Spaces: Gyrovector operations are defined inside an open d-dimensional ball whose radius depends on c; c = 0 recovers Euclidean space.
The Proposed Model
HAT projects node features into hyperbolic space, uses hyperbolic-distance attention and gyrovector operations for aggregation, and accelerates computation through logarithmic and exponential mappings. The resulting operations can be parallelized, giving complexity comparable to standard GNNs and substantially faster convergence in the reported Cora example.
- Hyperbolic feature projection: HAT first projects input node features into hyperbolic space, then applies a shared Möbius matrix-vector transformation to obtain latent representations.The projection uses an exponential map; the transformed representation is the hidden-layer feature.
- Hyperbolic attention mechanism: HAT computes neighbor attention coefficients from hyperbolic distance, normalizes them with softmax, and aggregates latent representations using Möbius operations.The self-attention coefficient is computed for graph neighbors, while the normalized weights form the aggregation.
- Acceleration of HAT: Möbius addition in the original aggregation is noncommutative and nonassociative, requiring ordered serial computation that becomes impractical for high-degree hubs.The acceleration strategy addresses this bottleneck by using a commutative and associative accumulation operation.
- Acceleration of HAT: The logarithmic map moves hyperbolic representations into a tangent-space vector space, where they can be combined before the exponential map returns them to hyperbolic space.This replaces serial Möbius accumulation with an operation that can be computed in parallel.
- Complexity Analysis: HAT has time complexity O(|V| · d · d′ + |E| · d′), on par with GAT and GCN, and its node and edge operations can be parallelized.On Cora using an NVIDIA GTX 1080 Ti, accelerated HAT converged in about 84 seconds, whereas the unaccelerated model did not converge within 12 hours.
Experiments
Experiments evaluate HAT on four real-world graph datasets across node classification, node clustering, attention behavior, and two-dimensional visualization. HAT generally outperforms the baselines, with especially clear advantages in low-dimensional settings and clearer class separation in Pubmed representations.
- Experimental Setup: HAT is evaluated on Cora, Citeseer, Pubmed, and Amazon Photo against graph embedding and graph neural network baselines.The baselines include DeepWalk, Node2vec, LINE, PoincaréEmb, GCN, and GAT.
- Node Classification: HAT achieves the best node-classification performance in most cases, with stronger superiority in low-dimensional settings.The comparison reports average accuracy over 10 runs with random weight initialization.
- Node Clustering: HAT outperforms the baselines in most node-clustering cases, including Amazon Photo where some graph embedding methods exceed GCN and GAT.Clustering results are reported using normalized mutual information averaged over 10 runs.
- Analysis of Attention Mechanism: For node P1728, same-class neighbors receive higher attention values than irrelevant-class neighbors, while the node itself receives the highest value.The analysis identifies P2599, P961, and P2555 as the next-highest neighbors, with P1358 and P2257 receiving the smallest values.
- Graph Visualization: On Pubmed, HAT, GCN, and GAT distinguish three node classes, while HAT produces clearer boundaries and larger separated regions than GCN and GAT.The visualization uses two-dimensional learned representations, with each point representing a paper and its color representing its label.
Conclusion
The paper introduces HAT as an initial hyperbolic graph attention network. It combines gyrovector-space graph operations, hyperbolic-proximity attention, and logarithmic/exponential mapping acceleration, with experiments showing superiority over state-of-the-art methods.
- Conclusion: HAT redesigns graph operations in hyperbolic spaces using gyrovector spaces and defines attention through hyperbolic proximity.The model also uses an acceleration strategy based on logarithmic and exponential mappings.
- Conclusion: Experiments on four datasets demonstrate HAT's superiority compared with state-of-the-art methods.