PaperlayerView exact revision on arXiv

Source-linked AI summary

Riemannian Graph Tokenizer for Structural Knowledge Transfer

Qimin Zhou, Haibo Liu, Yujie Wang, Li Sun, Chuan Shi

arXiv:2610.15427v1cs.LG

TL;DR

Graph tokenizers still face challenges representing non-Euclidean structure and capturing structural semantics for cross-domain transfer. RGT quantizes geometric structural patterns into discrete tokens and uses a geometry-aligned decoder. The paper reports improved transferability across graph domains, including better performance than existing GFMs on node classification and link prediction.

  • Problem

    Graph tokenizers remain early-stage, with challenges in handling multi-domain non-Euclidean structures and capturing structural semantics for effective cross-domain transfer.

    Source: §1 · p. 2

  • Method

    RGT quantizes tree, cycle and sequence patterns into geometric tokens and uses a geometry-aligned decoder to unify representations across geometric spaces.

    Source: §1 · p. 2, §3.1.3 · p. 5

  • Results

    RGT performs better than existing GFMs on node classification and link prediction, and paired tests find it significantly outperforms RiemannGFM at the 99% confidence level on Pubmed.

    Source: §4.2 · pp. 6–7

  • Takeaways & Limitations

    Experiments across multiple real-world graph datasets indicate that RGT exhibits significant cross-domain generalization.

    Source: §1 · p. 2

    RGT is framed for mapping subgraphs or structural patterns to codebook tokens, with adaptation to new graph domains described as requiring minimal parameter updates.

    Source: §2 · pp. 2–3

Abstract

from arXiv · show

Foundation models are at the forefront of artificial intelligence. A tokenizer, converting the raw input into discrete representations that the model can understand, plays an important role to the success of foundation models. Unlike the text tokenizer that is well studied in large language models, graph tokenizer is still at its early stage, facing the challenges of tackling the non-Euclidean structures and capturing the structural semantics. How to design a graph tokenizer for structural knowledge transfer? To this end, we propose a Riemannian Graph Tokenizer (RGT) that bridges the structural knowledge and quantized representations to support cross-domain structural knowledge transfer. The connection is established by Riemannian geometry. Specifically, we first define the geometric vocabulary (trees, cycles and sequences), which captures fundamental structural patterns and reflects the intrinsic geometry of graph. Second, we construct a Riemannian quantizer with Riemannian Straight-Through Estimator to tokenise graph structures across multiple domains into discrete tokens. To ensure consistency and transferability across diverse geometric spaces, RGT further incorporates a geometry-aligned decoder that projects manifold-specific tokens into a unified tangent space. The theoretical analysis and geometric interpretations are provided to support the effectiveness of our proposed method. Extensive experiments across diverse datasets demonstrate that RGT significantly enhances structural knowledge transferability across graph domains.

1 Introduction

Graph tokenizers face difficulty representing diverse non-Euclidean structures and transferring structural knowledge across graph domains. RGT uses geometric patterns and Riemannian quantization to create transferable discrete tokens, with experiments reporting cross-domain generalization.

1 Introduction

  • Prior work includes unified graph tokenization and structural-vocabulary approaches, yet transferring structural knowledge across graphs remains a challenge.OpenGraph combines a graph tokenizer and scalable graph transformer; RiemannGFM uses structural vocabulary without textual features.Source: §1 · p. 2
  • Graph tokenization remains underexplored for multi-domain non-Euclidean structures and structural semantics, limiting effective structure-level transfer across graph domains.Existing approaches may rely on text alignment or distill GNNs into lightweight MLPs; trees and cycles alone do not capture the full diversity of graph structures.Source: §1 · p. 2
  • RGT quantizes geometric vocabulary—trees, cycles and sequences—into discrete tokens in constant-curvature spaces for cross-domain structural knowledge transfer.Its Riemannian quantizer uses a Riemannian straight-through estimator, and its decoder reconstructs structural features after parallel transport to a tangent space.Source: §1 · p. 2
  • RGT's experiments on multiple real-world graph datasets report competitive graph-task performance and significant cross-domain generalization.The paper also provides theoretical analysis of the quantizer and its preservation of intrinsic manifold geometry.Source: §1 · p. 2

2 Preliminaries

The preliminaries define constant-curvature geometry and formulate graph tokenization as mapping structural patterns to geometry-aware codebook tokens. They describe structure awareness and cross-domain transfer as the tokenizer's core capabilities.

2 Preliminaries

  • A Riemannian manifold pairs a smooth manifold with a metric that supplies inner products on tangent spaces and supports geometric quantities such as lengths, angles and distances.Curvature measures deviation from flat Euclidean space; constant curvature means the curvature is the same at every point.Source: §2 · p. 2
  • The κ-CCS formulation recovers Lorentz/hyperbolic, spherical and Euclidean spaces when κ is negative, positive or zero, respectively.The north pole is defined as a reference point on the manifold.Source: §2 · p. 2
  • The tokenizer maps a graph subgraph or structural pattern to a discrete geometry-aware token selected from a codebook on a constant-curvature manifold.The tokenizer is pretrained on multi-domain graphs through self-supervised learning and parameterized by θ.Source: §2 · p. 2
  • The stated capabilities are learning generalizable representations of trees, cycles and sequences, then adapting with minimal parameter updates to new graph domains.The target domains may vary in structural or attribute distributions.Source: §2 · p. 3

3 RGT: Riemannian Graph Tokenizer for Structural Knowledge Transfer

RGT tokenizes graph structure through geometric patterns represented in curvature-matched spaces, then quantizes and fuses their representations. Its encoder, quantizer, decoder, and joint training objective are designed to preserve structural geometry while supporting cross-domain alignment.

3 RGT: Riemannian Graph Tokenizer for Structural Knowledge Transfer

  • Trees are modeled in hyperbolic space, cycles in spherical space, and sequences in Euclidean space to bridge topological heterogeneity.These patterns form the core geometric vocabulary.Source: §3 · p. 3

3.1.1 Geometric Vocabulary Encoder.

  • The encoder samples trees, cycles, and sequences with BFS and encodes their structural coordinates in the corresponding geometric spaces.For trees and cycles, attention-weighted Fréchet means aggregate node coordinates on the manifold.Source: §3.1.1 · p. 3

3.1.2 Riemannian Quantizer.

  • The Riemannian quantizer maps geometric vocabulary to manifold codebooks; its analysis establishes local consistency and minimum expected geodesic distortion.The Riemannian straight-through estimator retains quantization error in the tangent space for gradient propagation, preserving manifold structure and alleviating codebook collapse.Source: §3.1.2 · p. 4

3.1.3 Geometry-Aligned Decoder.

  • The geometry-aligned decoder projects or transports manifold-specific tokens to a shared north-pole tangent space, then fuses them into a unified representation.The fused representation is used to reconstruct structural features.Source: §3.1.3 · p. 5

3.2 Loss Function and Optimization

  • Training combines reconstruction loss with cross-geometry contrastive loss, which aligns representations from different spaces in the shared tangent space.The model is pretrained with the combined objective, and the stated computational complexity is O(|V|^2 + |E|).Source: §3.2 · p. 5

4 Experiment

Experiments test RGT across cross-domain transfer, few-shot learning, geometric vocabulary choices, pretraining datasets, and web-scale graphs. Results report advantages over graph foundation models, with sensitivity to vocabulary geometry and codebook size.

4.1 Experimental Setups

  • The experiments use three pretraining datasets and seven evaluation datasets spanning text-, mixed-, non-attributed, and web-scale graphs.Pretrained codebooks remain frozen during evaluation while a GNN classifier is fine-tuned on target test datasets; results are averaged across runs.Source: §4.1 · p. 6

4.2 Results and Discussion

  • RGT outperforms existing graph foundation models on node classification and link prediction, with particular strength on non-attributed graphs compared with RiemannGFM.On citation networks, it is comparable to within-domain self-supervised methods for node classification and yields superior link prediction results.Source: §4.2 · p. 6, Table 1 · p. 6, Table 2 · p. 6
  • In few-shot node classification, RGT remains competitive despite no target-domain pretraining on Pubmed and improves as more structural information becomes available in five-shot settings.It is competitive on both reported metrics for Github and particularly strong on non-attributed graphs, except against GraphMAE and GFT in the five-shot setting.Source: §4.2 · p. 6, Table 3 · p. 7, Table 4 · p. 7
  • Assigning trees to hyperbolic space, cycles to spherical space, and sequences to Euclidean space performs best among nine geometric-vocabulary configurations.Mismatched or single-space configurations perform significantly worse on link prediction AUC.Source: §4.2 · p. 7, Table 5 · p. 7
  • A limited codebook can achieve competitive performance, but increasing its size too far degrades results through increased codebook-collapse risk.The codebook-size study evaluates node classification and link prediction across multiple datasets.Source: §4.2 · p. 7, Figure 2 · p. 7
  • On Pubmed, paired t-tests across five independent experiments find RGT significantly outperforms RiemannGFM at the 99% confidence level.Table 6 reports mean and standard deviation for accuracy and F1.Source: §4.2 · p. 7, Table 6 · p. 8
  • RGT and RiemannGFM maintain stable cross-domain link-prediction performance across pretraining datasets, whereas OpenGraph drops on Citeseer after Flickr or AComp pretraining and cannot handle non-attributed graphs.The experiments compare pretraining on Flickr, AComp, and WikiCS.Source: §4.2 · p. 8, Table 7 · p. 8
  • RGT shows competitive performance and scalability on ogbn-products, with inference overhead primarily from eigenvalue computation and subgraph sampling.Figure 5 presents cross-domain node-classification results on the web-scale graph.Source: §4.2 · p. 8, Figure 5 · p. 8

5 Conclusion

The paper presents RGT for quantizing and transferring structural knowledge across graph domains. It reports evaluation on attributed and non-attributed graphs and identifies joint encoding of structural semantics and textual features as future work.

5 Conclusion

  • RGT is designed to quantize and transfer structural knowledge across graph domains.The work identifies this tokenizer as its primary contribution.Source: §5 · p. 8
  • The Riemannian Straight-Through Estimator is proposed to maintain intrinsic structure during quantization.The paper describes the quantizer as facilitating structural knowledge transfer.Source: §5 · p. 8
  • RGT is evaluated on attributed and non-attributed graph datasets, and future work may jointly encode structural semantics and textual features.The empirical results are described as demonstrating RGT's superiority.Source: §5 · p. 8

A Theoretical Analysis

The analysis treats trees, cycles, and sequences as a complete geometric vocabulary for graph structures. It associates each structure with a constant-curvature space and presents this vocabulary as a basis for cross-domain transfer.

A.1 The Completeness of Geometric Vocabulary

  • Trees and cycles together suffice to reconstruct graph topology in terms of connectivity, through a spanning-tree backbone and non-tree edges.The passage frames any graph as a combination of tree and cycle structures.Source: §A.1 · p. 10
  • Sequences add a locally flat, zero-curvature linear substructure that serves as a first-order Euclidean approximation.Source: §A.1 · p. 10
  • Trees map to hyperbolic space, cycles to spherical space, and sequences to Euclidean space, matching their respective structural patterns.The mappings correspond to negative, positive, and zero curvature.Source: §A.1 · p. 10
  • Together, the three structures form a complete vocabulary for representing arbitrary graphs across structural patterns, topologies, and geometric characteristics.Figure 6 illustrates cross-domain transferability based on the geometric vocabulary.Source: §A.1 · p. 10, Figure 6 · p. 10

A.2 Proof of The Theorem 1

The supplied passage states that the theorem is proved but gives no further proof steps or result details.

A.2 Proof of The Theorem 1

  • The passage concludes that the theorem is proved, without specifying the theorem's claim or proof steps.Source: §A.2 · p. 10

A.3 Proof of The Theorem 2

The proof characterizes the quantizer as minimizing expected geodesic distortion across domains. The accompanying material describes Riemannian gradient handling, codebook-collapse mitigation, and the presence of a training algorithm.

A.3 Proof of The Theorem 2

  • Theorem 2 concludes that the quantizer minimizes total expected geodesic distortion across multiple domains.The passage identifies the quantizer defined in Eq. (6) as the optimal structure-level Riemannian quantization strategy.Source: §A.3 · p. 10

B.1 Riemannian Straight-Through Estimator

  • Because nearest-neighbor quantization is non-differentiable, the Riemannian Straight-Through Estimator is introduced for the quantization step.The displayed formulation and stop-gradient operator are referenced, but their full roles are not stated in these passages.Source: §B.1 · p. 11

B.2 RSTE Alleviates Codebook Collapse

  • The described Riemannian approach propagates gradients in the tangent space and encourages codeword diversity, mitigating codebook collapse.The passage contrasts this with Euclidean interpolation, which can concentrate use on a small subset of codebook entries.Source: §B.2 · p. 11

C Algorithm

D.1 Experimental Setup

RGT’s experimental setup specifies geometric sampling and model hyperparameters, then trains structural tokens for downstream evaluation with frozen pretrained codebooks.

Hyperparameter settings

  • Tree sampling uses two layers, cycles are triangles, structural embeddings and code dimensions are 32, and the codebook contains 128 entries.The spherical, hyperbolic, and Euclidean curvatures are set to 1, −1, and 0; hyperparameters are selected by grid search.Source: §D.1 · p. 11, Table 8 · p. 11

Experimental setup

  • RGT samples substructures from its geometry vocabulary, updates coordinates through cross-geometry attention, quantizes structures into tokens, and decodes them with geometric alignment.The algorithm takes multi-domain graphs and RGT hyperparameters as input and outputs model parameters.Source: §D.1 · p. 11

Pretraining and evaluation

  • Evaluation keeps pretrained codebooks frozen, fine-tunes a GNN classifier on target test datasets, and averages results over multiple runs.RGT uses the same pretraining datasets as RiemannGFM, while baselines follow their original pretraining datasets.Source: §D.1 · p. 11

Pretraining and fine-tuning

  • Pretraining uses Adam at learning rate 0.001 for three epochs and three iterations; downstream node classification and link prediction each train for 120 epochs.Pretraining uses batch size 32 and dropout 0.1; node-classification and link-prediction hidden dimensions are 128 and 256, respectively.Source: §D.1 · p. 11

Comparison with GFT and VQGraph

  • RGT targets cross-domain structural transfer through geometric consistency, using multi-domain pretraining and unified fusion of tokens in a shared tangent space.The supplied comparison characterizes GFT as a general-purpose reasoning model and VQGraph as a lightweight structure-aware model for node classification.Source: §D.1 · p. 12

D.2 Additional Results

Additional experiments report competitive or superior cross-domain node-classification performance, strong link-prediction performance, and competitive results under one-shot and five-shot supervision.

Cross-domain node classification

  • RGT is competitive with or superior to existing baselines across all three additional cross-domain node-classification datasets.The authors describe this as reinforcing robustness and adaptability across diverse domains and graph structures.Source: §D.2 · p. 12

Cross-domain link prediction

  • RGT maintains consistently strong performance across domains in link prediction on the three datasets.The supplied table caption identifies the results as cross-domain transfer learning performance for link prediction.Source: §D.2 · p. 12

One-shot node classification

  • RGT remains competitive in one-shot node classification across three datasets, although performance varies across methods and datasets.The results are presented as evidence of potential transfer learning in extremely data-scarce settings.Source: §D.2 · p. 12, Table 11 · p. 12

Five-shot node classification

  • In five-shot node classification, RGT is stable and competitive, surpassing all baselines on Citeseer and Brazil.The comparison covers three additional datasets.Source: §D.2 · p. 12, Table 12 · p. 12

Pretraining-dataset analysis

  • Across target datasets, RGT achieves superior or competitive cross-domain node-classification results regardless of the pretraining dataset.The authors report more stable and transferable representations overall than baseline methods across the compared configurations.Source: §D.2 · p. 12, Table 13 · p. 12

Related papers

Loading 2610.15427v1…