PaperlayerView exact revision on arXiv

Source-linked AI summary

Hypformer: Exploring Efficient Transformer Fully in Hyperbolic Space

Menglin Yang, Harshit Verma, Delvin Ce Zhang, Jiahong Liu, Irwin King, Rex Ying

arXiv:2407.01290v2cs.LGcs.AI

TL;DR

Prior hyperbolic Transformer efforts focused on self-attention and lacked basic components such as LayerNorm. Hypformer combines Lorentz-based foundational blocks with linear attention; experiments report lower computation cost and training time than existing hyperbolic softmax attention.

  • Problem

    Prior hyperbolic Transformer efforts focused on self-attention and lacked basic components such as LayerNorm and positional encoding.

    Source: §1 · p. 2

  • Method

    Hypformer uses Lorentz-based HTC and HRC blocks to define essential hyperbolic Transformer modules, together with linear attention.

    Source: §1 · p. 2

  • Results

    10-fold lower GPU computation cost and half the training time versus existing hyperbolic softmax attention, with consistent improvements over competitive baselines on tree-like and non-tree-like datasets.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The authors present Hypformer as a scalable and effective hyperbolic Transformer.

    Source: §7 · p. 9

    Directly changing curvature in LTF can lose learned information and distort embeddings, without guaranteeing preservation of relative distances.

    Source: §3.3 · p. 4

Abstract

from arXiv · show

Hyperbolic geometry have shown significant potential in modeling complex structured data, particularly those with underlying tree-like and hierarchical structures. Despite the impressive performance of various hyperbolic neural networks across numerous domains, research on adapting the Transformer to hyperbolic space remains limited. Previous attempts have mainly focused on modifying self-attention modules in the Transformer. However, these efforts have fallen short of developing a complete hyperbolic Transformer. This stems primarily from: (i) the absence of well-defined modules in hyperbolic space, including linear transformation layers, LayerNorm layers, activation functions, dropout operations, etc. (ii) the quadratic time complexity of the existing hyperbolic self-attention module w.r.t the number of input tokens, which hinders its scalability. To address these challenges, we propose, Hypformer, a novel hyperbolic Transformer based on the Lorentz model of hyperbolic geometry. In Hypformer, we introduce two foundational blocks that define the essential modules of the Transformer in hyperbolic space. Furthermore, we develop a linear self-attention mechanism in hyperbolic space, enabling hyperbolic Transformer to process billion-scale graph data and long-sequence inputs for the first time. Our experimental results confirm the effectiveness and efficiency of Hypformer across various datasets, demonstrating its potential as an effective and scalable solution for large-scale data representation and large models.

1 Introduction

Hypformer addresses the lack of complete hyperbolic Transformer modules and the quadratic complexity of prior hyperbolic attention. It combines foundational hyperbolic blocks with linear attention, and experiments report lower computation cost and training time alongside stronger baseline performance.

1 Introduction

  • Prior hyperbolic Transformer attempts focused mainly on self-attention, leaving basic components such as LayerNorm and positional encoding undefined.Hyperbolic representations are motivated by their fit with hierarchical and tree-like data structures.Source: §1 · p. 2
  • HTC and HRC provide foundational blocks for defining linear transformation and common Transformer operations in hyperbolic space.HTC works directly in the Lorentz model, supports curvature changes while preserving relative distance, and HRC supports operations including LayerNorm, activation, dropout, and concatenation.Source: §1 · p. 2
  • Hypformer introduces linear-complexity hyperbolic self-attention to address the quadratic cost of prior mechanisms on long sequences and large graphs.The paper also reports extending the model to billion-level graph data.Source: §1 · p. 2
  • GPU computation cost falls by a factor of 10 and training time is halved versus existing hyperbolic softmax attention, while performance surpasses competitive baselines on tree-like and non-tree-like datasets.Experiments cover graph analysis, text classification, and image classification.Source: §1 · p. 2

2 Related Work

Prior work uses hyperbolic neural networks to represent hierarchical data across several domains, while Transformer research has only limited hyperbolic adaptations. Existing adaptations vary in attention design and manifold use, and often retain quadratic attention or omit essential Transformer modules.

2.1 Hyperbolic Neural Networks

  • Hyperbolic neural networks have reported strong performance in computer vision, natural language processing, recommender systems, and graph learning.The cited motivation is hyperbolic space's ability to capture hierarchical and tree-like structures.Source: §2.1 · p. 2

2.2 Transformer and Hyperbolic Transformer

  • Transformers are used in language understanding, image processing, and graph learning, but self-attention's quadratic time can hinder scalability, especially for long sequences.Existing Transformer architectures predominantly operate in the Euclidean domain, with limited extensions to hyperbolic and other non-Euclidean spaces.Source: §2.2 · p. 2
  • Prior hyperbolic attention methods use hyperbolic distance with midpoint aggregation, but retain quadratic complexity and omit essential modules such as LayerNorm.Cho et al. [12] proposed linear-time kernelized non-Euclidean attention but rely heavily on tangent-space mappings; Ermolov et al. [19] map Euclidean Transformer features to hyperbolic space rather than building a fully hyperbolic Transformer.Source: §2.2 · p. 3

3 Preliminaries

The preliminaries establish the Lorentz model and review hyperbolic attention and Lorentz transformations. They describe the transformations’ computational and representational trade-offs.

3.1 Lorentz Model of Hyperbolic Geometry

  • Hypformer uses the Lorentz model for its numerical stability and can be adapted to other isometrically equivalent hyperbolic models.In this model, the time-like axis is distinguished from the space-like dimensions.Source: §3.1 · p. 3

3.2 Self-Attention Module

  • Hyperbolic attention uses negative hyperbolic distance for query-key similarity and a Lorentzian midpoint for attentive output, with quadratic token complexity.The described prior methods use negative distance and have O(N^2) complexity.Source: Figure 2 · p. 3, §3.2 · pp. 3–4

3.3 Lorentz Transformation

  • Lorentz Tangent Space Transformation maps an embedding to a tangent space, applies an operation, then maps it back to the Lorentz model.A shared reference point supports parallel computation but can cause mapping errors for distant points; local reference points require separate mappings and more computation.Source: §3.3 · p. 4
  • Changing curvature in the fully Lorentz transformation cannot guarantee preservation of learned relative distances and may distort the embedding.The method’s curvature is otherwise unchangeable without altering it.Source: §3.3 · p. 4
  • The fully Lorentz transformation’s W matrix and normalization term constrain some functions, and its definition cannot implement LayerNorm or concatenation.For example, dropout and activation operations need not interact with W, while normalization limits the transformation’s expressiveness.Source: §3.3 · p. 4

4 Method

Hypformer builds a Lorentz-space Transformer from HTC and HRC blocks and a linear-complexity hyperbolic attention module. Its method also specifies positional encoding, standard Transformer operations, and an overall encoder architecture.

4.1 Hyperbolic Transformation with Curvatures (HTC)

  • HTC transforms points directly in Lorentz space, supports variable curvature, and preserves relative distances across curvature changes.Unlike the tangent-space approach, HTC minimizes logarithmic and exponential mappings; its linear transformation is not entangled with a normalization term.Source: §4.1 · p. 5

4.2 Hyperbolic Readjustment and Refinement with Curvatures (HRC)

  • HRC implements readjustments such as LayerNorm and activation on space-like dimensions, preserving the causal structure while implicitly using time-like information.The paper motivates this choice by treating these operations as refinements within the same reference frame.Source: §4.2 · p. 5

4.3 Hyperbolic Linear Attention

  • Reordering attention computation gives linear complexity while operating on space-like features and recalibrating time-like values to satisfy the Lorentz constraint.The method changes (Q^T K)V to Q(K^T V), enabling more efficient handling of large datasets and long sequences.Source: §4.3 · pp. 5–6

4.4 Hyperbolic Positional Encoding

  • Relative positional encoding uses a trainable Lorentz position vector and is added before the self-attention block's linear transformation.The position vector is defined as HTC(x); the paper reserves more advanced positional encodings for future work.Source: §4.4 · p. 6

4.5 Hyperbolic LayerNorm, Dropout, Activation, and Concatenation

  • HRC defines LayerNorm, Dropout, activation, and concatenation operations in hyperbolic space because these functions act within the same reference system.Consecutive operations can be merged for computational efficiency.Source: §4.5 · pp. 6–7

4.6 Overall Architecture

  • Hypformer maps inputs to the Lorentz model, then uses HTC, hyperbolic attention with positional encoding, an HTC feedforward layer, and HRC LayerNorm.For graph inputs, the encoder can incorporate a GNN; the study uses a fully connected decoder for classification.Source: Figure 4 · p. 6, §4.6 · p. 7

5 Experiments

The experiments evaluate Hypformer on large and small/medium graphs, plus semi-supervised text and image classification. Across these settings, the reported findings emphasize strong benchmark performance and scalability.

5 Experiments

  • The evaluation spans graph node classification from millions to billions of nodes, five small/medium graph datasets, and semi-supervised classification on image and text datasets.The large-graph experiments include ogbn-arxiv, ogbn-protein, and Papers100M; the small/medium experiments use three low-degree and two high-degree hyperbolicity datasets.Source: §5.1 · p. 7, §5.2 · pp. 7–8, §5.3 · p. 8

5.1 Experiments on Large Graphs

  • Hypformer consistently outperforms other models on large-scale graphs, retaining an advantage on ogbn-papers100M where prior Transformer-based models have encountered limitations.The reported comparison includes state-of-the-art Euclidean GNNs and graph Transformers, as well as hyperbolic models.Source: §5.1 · p. 7

5.2 Experiments on Small/Medium Graphs

  • On small and medium graphs, Hypformer significantly surpasses standard and hyperbolic GNNs on both hyperbolic and non-hyperbolic datasets.The reported datasets include Disease and Airport, alongside Cora, CiteSeer, and PubMed.Source: Table 2 · p. 8, §5.2 · p. 8

5.3 Comparisons on Text and Vision Datasets

  • On Mini-ImageNet and 20News-Groups, Hypformer outperforms competing methods in seven of eight k-NN settings and shows greater stability as k varies.The input graph is constructed from the input features using k-NN.Source: §5.3 · p. 8

6 Analysis

The analysis tests scalability, compares linear and softmax attention, varies curvature, and ablates graph and Transformer components. It reports efficiency gains and dataset-dependent effects of the two components.

Scalability

  • Above 40K nodes, softmax attention runs out of memory, while linear attention continues; its memory use grows linearly with graph size and GPU cost is reduced 10X.The scalability test uses Amazon2M subsets ranging from 10K to 200K nodes, with other parameters held constant.Source: §6 · p. 8

Effectiveness of Curvature

  • Varying curvature performs better than unified curvature in the reported comparison.The experiment treats the two curvature parameters in HTC and HRC as trainable; the comparison is shown in Figure 6.Source: §6 · p. 8, Figure 6 · p. 9

Efficiency and Effectiveness

  • Linear attention halves training time compared with softmax attention in Hypformer and achieves better accuracy, with both variants performing well.The efficiency comparison reports running time per epoch; the accuracy comparison is shown for small/medium datasets.Source: §6 · p. 8, Table 4 · p. 9, Figure 6 · p. 9

Ablation Study

  • Ablations show graph structure matters on Cora, both components contribute on ogbn-proteins, and removing the graph component performs best on 20news.The paper suggests the 20news graph may not reflect document relationships; the Transformer alone is reported sufficient to capture semantic relationships there.Source: §6 · p. 9, Table 5 · p. 9

7 Conclusion

The conclusion presents Hypformer as a fully hyperbolic Transformer with linear attention and two foundational blocks. It also identifies curvature choices and task-specific decoders as unresolved challenges.

7 Conclusion

  • Hypformer operates directly on hyperbolic representations, uses linear attention, and introduces HTC and HRC as foundational blocks for hyperbolic models.The paper characterizes this work as an initial exploration.Source: §7 · p. 9
  • Future work includes determining suitable initial curvature, setting curvature across Hypformer levels, and designing decoders for different downstream tasks.Source: §7 · p. 9

A Exponential and Logarithmic Map

B Proof

The proof establishes that an HTC-transformed output belongs to its target Lorentz space, then proceeds through a distance inequality argument across curvature spaces.

B Proof

  • The proof defines the HTC output Lx and establishes that it belongs to the target Lorentz space.It uses the stated Lorentz norm condition and the output dimension after time-like dimension recalibration and concatenation.Source: B Proof · p. 11
  • The argument considers distances between points in one curvature space and their HTC-transformed counterparts in another.Source: B Proof · p. 11
  • The proof derives its desired inequality by applying a positive-curvature factor and substituting previously established expressions.Source: B Proof · p. 12

C.1 Data Processing for Large-graph Data

The large-graph experiments use public OGB splits for ogbn-proteins, ogbn-arxiv, and ogbn-papers100M, plus study-specific splits for Amazon2M.

C.1 Data Processing for Large-graph Data

  • Amazon2M contains 2.45 million nodes and 61.86 million edges, with splits following recent studies [72].The public OGB splits are used for ogbn-proteins and ogbn-arxiv.Source: §C.1 · p. 12
  • ogbn-papers100M, the largest dataset used, has 0.11 billion nodes and 1.61 billion edges.The experiments use its publicly available OGB splits.Source: §C.1 · p. 12
  • The experiments use public OGB splits for ogbn-proteins and ogbn-arxiv.Source: §C.1 · p. 12

C.2 Data Processing for Medium-graph Data

The medium-graph node-classification experiments use dataset-specific splits and metrics, and compare Hypformer with GNNs and graph and non-Euclidean Transformers.

C.2 Data Processing for Medium-graph Data

  • Disease and Airport use 30%/10%/60% and 70%/15%/15% train/validation/test splits, respectively, while citation networks use standard splits [34].Source: §C.2 · p. 12
  • Results average five node-classification runs; Disease and Airport use F1-score, while other datasets use accuracy.Source: §C.2 · p. 12
  • Comparisons include GCN [34], GAT [66], SGC [71], HGCN [8], LGCN [93], and HGNN [20], alongside Euclidean graph Transformers and HAN [26] and FPS-T [12].Euclidean comparators include Graphomer, GraphTrans [74], GraphGPS [55], NodeFormer [72], and SGFormer.Source: §C.2 · p. 12
  • NodeFormer [72] uses kernelized Gumbel-Softmax, while GraphGPS [55] separates local real-edge aggregation from a fully connected Transformer.Source: §C.2 · p. 12

C.3 Data Processing for Text and Image Data

The text and image experiments use specified class, split, and feature-processing settings; implementation details describe baseline reproduction, curvature tuning, and classifier choices.

C.3 Data Processing for Text and Image Data

  • Mini-ImageNet and 20News-Groups experiments use 30 classes, 600 images per class, and 50%/25%/25% train/validation/test splits.The 128 features are CNN-extracted; Mini-ImageNet features are extracted by the authors.Source: §C.3 · p. 12
  • A k-NN graph based on input features supports message passing, and image embeddings come from a four-convolutional-layer CNN followed by a fully connected layer.The resulting node features are 128-dimensional.Source: §C.3 · p. 12

C.4 Implementation Details

  • SGFormer results could not be fully reproduced because of official-code errors, so the authors report available information and acknowledge the discrepancy.Hypformer setup mainly follows SGformer configurations.Source: §C.4 · p. 12
  • Input and output curvatures and parameter p were searched over [1.0, 2.0, 3.0]; a more detailed curvature setting is left for future exploration.The Euclidean classifier performed better in most cases than the hyperbolic classifier.Source: §C.4 · p. 12
Loading 2407.01290v2…