Technical Summary: Generalizing Graph Foundation Models via Hyperbolic Retrieval-Augmented Generation

1. Problem Statement

Graph Foundation Models (GFMs) have established themselves as a dominant paradigm for graph representation learning, achieving strong generalization across diverse tasks through large-scale pre-training. However, their performance is inherently constrained by the distribution of their pre-training data. When faced with distribution shifts during inference, the parameterized knowledge within these models often fails to generalize, leading to degraded and unreliable performance.

To address this, Retrieval-Augmented Generation (RAG) has been introduced to allow GFMs to access external knowledge dynamically at inference time without retraining. Existing RAG frameworks for graphs, however, operate primarily in Euclidean space. The authors identify a fundamental geometric limitation in this approach: the polynomial volume growth of Euclidean space is mismatched with the exponential growth of tree-structured external knowledge bases. This geometric mismatch leads to two critical issues:

1. Loss of Semantic Granularity: Euclidean spaces struggle to distinguish between coarse-grained (global) and fine-grained (local) concepts. Concepts at different hierarchical depths are compressed into proximal regions, causing the model to treat them as equally informative and blurring semantic roles.
2. Emergence of Hubness: Due to limited representational capacity, many entities are forced into a small region of the embedding space. This results in "hubness," where certain entities frequently appear in the nearest neighbor sets of diverse queries, reducing retrieval diversity and query specificity.

2. Methodology: HyRAG Framework

The authors propose HyRAG (Hyperbolic Retrieval-Augmented Generation), a framework designed to enhance GFM generalization by leveraging the geometric properties of hyperbolic space. HyRAG consists of three core modules:

2.1 Hyperbolic Knowledge Indexing (HKI)

This module constructs a hierarchy-aware representation space for the external knowledge base.

• Hyperbolic Projection: Semantic features of entities and relations are first encoded in Euclidean space (e.g., via SBERT) and then mapped to a Poincaré ball model ($B^d$) using a learnable mapping network and the exponential map.
• Hierarchy-Aware Optimization: The model is trained using a joint objective to preserve both relational semantics and hierarchical entailment.
  • Distance Loss: Ensures relation-conditioned representations are geometrically consistent with tail entities. For hierarchical relations, it employs a rotation strategy under hyperbolic entailment cone constraints.
  • Angle Loss: Enforces that the entailment cone of a tail entity is geometrically contained within that of its head entity, preserving partial ordering.
  • Regularization: A penalty is applied to embeddings with radial norms exceeding a threshold to prevent drift toward the boundary of the Poincaré ball, ensuring stable hierarchical representation.

2.2 Multi-granularity Retrieval (MR)

To address the loss of semantic granularity, HyRAG retrieves knowledge at two distinct levels:

• Query Reformulation: A Large Language Model (LLM) reformulates the query node's textual attribute into a coarse-grained query (summarizing the core theme) and a fine-grained query (capturing specific details).
• Coarse-grained Retrieval: Retrieves top-$k$ entities based on hyperbolic distance. To ensure diversity and avoid redundancy, the Maximal Marginal Relevance (MMR) criterion is applied to select neighborhood entities, balancing relevance to the query with dissimilarity to already selected neighbors.
• Fine-grained Retrieval: Retrieves top-$k$ entities based on hyperbolic distance. Neighborhood expansion here focuses on specificity. Candidates are filtered using an angular violation score derived from hyperbolic entailment cones, ensuring selected neighbors are valid hyponyms (sub-concepts) of the retrieved entity.
• Graph Construction: Both retrieval processes generate sets of graphs (coarse-grained and fine-grained), which are summarized into compact graph-level representations via query-guided neighborhood aggregation.

2.3 Dual-path Fusion (DF)

This module integrates the retrieved knowledge into the GFM at both feature and structural levels:

• Feature-level Fusion: The initial representation of the query node is augmented by aggregating the coarse-grained and fine-grained knowledge representations. Weights are computed based on the hyperbolic distance between the query and the central entities of the retrieved graphs.
• Structure-level Fusion: To avoid introducing heterogeneous edges directly into the query's ego-graph, two auxiliary graphs (coarse-grained and fine-grained attribute graphs) are constructed. The GFM encoder independently processes the ego-graph and these auxiliary graphs to produce prediction logits.
• Uncertainty-Gated Injection: The predictions from the auxiliary graphs are fused into a unified knowledge prediction, weighted by the inverse entropy (confidence) of each source. This unified prediction is then injected into the original GFM prediction, gated by the entropy of the original prediction. If the original prediction is uncertain (high entropy), the model relies more heavily on the retrieved knowledge; if confident, it preserves the original prediction.

3. Key Contributions

The paper claims the following contributions:

1. Identification of Limitations: The authors identify and analyze two inherent limitations of existing Euclidean-based RAG paradigms for graphs: the loss of semantic granularity and the emergence of hubness due to geometric mismatch.
2. HyRAG Framework: They propose HyRAG, the first hyperbolic RAG framework tailored for graph foundation models. It provides a geometry-aware redesign of the RAG pipeline, encompassing knowledge indexing, multi-granularity retrieval, and dual-path fusion.
3. Empirical Validation: Extensive experiments on multiple graph benchmarks demonstrate that HyRAG consistently improves the zero-shot inference performance of GFMs without requiring task-specific fine-tuning.

4. Experimental Results

The authors evaluated HyRAG using GraphCLIP as the backbone GFM across seven datasets spanning academic, e-commerce, Wikipedia, and social domains (e.g., Cora, CiteSeer, WikiCS, Instagram).

• Node Classification: In the zero-shot setting, HyRAG achieved the best performance across all datasets, yielding an average improvement of 2.02% over state-of-the-art self-supervised methods and graph foundation models. Compared specifically to the Euclidean-based RAG method (RAGRAPH), HyRAG showed an average improvement of 0.82%.
• Link Prediction: Experiments on the link prediction task using AnyGraph as the backbone showed consistent improvements, with notable gains of 1.08% on Cora and 1.41% on CiteSeer.
• Ablation Studies:
  • Replacing the Hyperbolic Knowledge Indexing with a standard Euclidean index resulted in the largest performance drop (average decline of 1.99%), validating the necessity of hyperbolic geometry.
  • Removing either coarse-grained or fine-grained retrieval components led to significant performance degradation, confirming the synergistic value of multi-granularity retrieval.
  • Feature-level fusion was identified as the primary driver of generalization, while structure-level fusion provided complementary benefits.

5. Significance and Claims

The paper positions HyRAG as a solution to the generalization bottleneck of GFMs caused by distribution shifts. By aligning the geometric properties of the retrieval space (hyperbolic) with the structural nature of external knowledge (tree-structured hierarchies), the framework effectively mitigates semantic granularity loss and hubness. The authors claim that HyRAG enables GFMs to leverage global semantic anchors and local semantic nuances effectively, offering a promising direction for building robust and generalizable graph foundation models that do not rely on extensive retraining for new domains.