Improving Graph Few-shot Learning with Hyperbolic Space and Denoising Diffusion

1. Problem Statement

The paper addresses the challenges of Graph Few-Shot Learning (FSL), specifically the unsupervised few-shot node classification task. The goal is to classify nodes into novel categories using only a small number of labeled support nodes ($M$-shot) and a large number of unlabeled query nodes, without relying on labeled data during the meta-training phase.

The authors identify two critical limitations in existing Graph FSL methods:

1. Euclidean Space Limitations: Most current models learn node representations in Euclidean space. However, real-world graph data (e.g., organizational structures, academic taxonomies) often possesses inherent hierarchical or tree-like structures. Euclidean geometry suffers from significant distortion when embedding such structures, failing to capture the true geometric relationships.
2. Distributional Bias & Overfitting: In the meta-testing phase, models typically train classifiers on a very small support set. This leads to two issues:
   • The empirical distribution of the small support set often deviates significantly from the true underlying class distribution (distributional shift).
   • Training directly on sparse data causes severe overfitting, impairing generalization to the query set.

2. Methodology: IMPRESS Framework

The proposed framework, IMPRESS (IMproves Praph Representation with Enhanced Space and Sampling), operates in two phases: Meta-Training and Meta-Testing. It integrates Hyperbolic Geometry and Denoising Diffusion Models.

A. Meta-Training Phase

1. Hyperbolic Node Representation Learning:

   • Instead of Euclidean space, the model learns node embeddings in a Poincaré ball (Hyperbolic space), which naturally accommodates hierarchical structures.
   • Architecture: A Variational Graph Autoencoder (VGAE) is used.
     • Encoder: Node features are projected from Euclidean space to the tangent space of the hyperbolic manifold using the logarithmic map. Graph convolution (GCN) is performed in the tangent space. The resulting embeddings are mapped back to hyperbolic space via the exponential map.
     • Decoder: Reconstructs the graph adjacency matrix using the inner product of latent variables in the hyperbolic space.
   • Objective: The model is trained unsupervisedly (using only graph structure and features) to minimize the reconstruction loss and the KL-divergence, learning latent distributions that preserve hierarchical geometry.

2. Prototype-Guided Denoising Diffusion:

   • Since labels are unavailable during meta-training, the model uses unsupervised clustering (DBSCAN) on the learned latent embeddings to assign pseudo-labels and compute class prototypes.
   • A Denoising Diffusion Probabilistic Model (DDPM) is trained on these latent embeddings.
   • Conditioning: The diffusion process is conditioned on the class prototypes via a cross-attention mechanism. This allows the model to learn the data distribution of each class without explicit ground-truth labels, preparing it to generate samples for novel classes later.

B. Meta-Testing Phase

1. Embedding Generation:
   • For a new task with a small support set ($S_{tes}$) and query set ($Q_{tes}$), the pre-trained VGAE encodes the nodes into hyperbolic latent space.
   • Class prototypes are computed from the labeled support set.
2. Data Augmentation:
   • The trained diffusion model generates $D$ new synthetic node embeddings for each novel class, conditioned on the support set's prototypes.
   • These generated samples are combined with the original support set to form an augmented support set ($\tilde{S}_{tes}$), effectively increasing the sample size from $M$ to $M+D$.
3. Classification:
   • A linear classifier is trained on the augmented support set and evaluated on the query set.

3. Key Contributions

1. Novel Framework (IMPRESS): The first framework to combine Hyperbolic Space for structural representation and Denoising Diffusion for distribution enrichment in the context of unsupervised graph few-shot learning.
2. Theoretical Advancement:
   • Proved that hyperbolic encoding provides a tighter generalization bound ($O(e^{-\delta})$) compared to Euclidean encoding for $\delta$-hyperbolic graphs.
   • Derived a classification error bound showing that the proposed method reduces error by minimizing intra-class variance, maximizing inter-class distance, and reducing the Wasserstein distance between generated and true distributions.
3. Prototype-Guided Diffusion: Introduced a mechanism to guide diffusion models using class prototypes in an unsupervised setting, solving the challenge of generating samples for novel classes without prior label information.
4. Empirical Superiority: Demonstrated consistent state-of-the-art performance across multiple benchmarks.

4. Experimental Results

The model was evaluated on six benchmark datasets: CoraFull, Coauthor-CS, Cora, WikiCS, Cora-ML, CiteSeer, and the large-scale ogbn-arxiv.

• Performance: IMPRESS consistently outperformed a wide range of baselines, including:
  • Graph embedding methods (GCN, SGC).
  • Traditional meta-learning (ProtoNet, MAML).
  • Graph meta-learning (Meta-GNN, GPN, TEG, COSMIC).
  • Unsupervised graph meta-learning (VNT, NaQ).
  • Example: On ogbn-arxiv (5-way 3-shot), IMPRESS achieved 61.11% accuracy, significantly beating the runner-up (COSMIC at 52.98%). On CoraFull, it reached 85.49% (vs. 75.18% for the next best).
• Ablation Studies:
  • Removing the hyperbolic component (w/o hyp) caused a significant performance drop, confirming the necessity of hyperbolic geometry for hierarchical data.
  • Removing the diffusion component (w/o dif) also degraded performance, validating that data augmentation via diffusion effectively mitigates label scarcity and distributional bias.
• Hyperparameter Sensitivity:
  • Optimal curvature ($c$) was found between 0.5 and 2.0.
  • The number of generated samples ($D$) showed an inverted-U trend, with optimal performance at $D=50$.

5. Significance

This work bridges the gap between geometric deep learning and generative modeling for graph data.

• Geometric Insight: It validates that real-world graphs are better modeled in hyperbolic space, offering a theoretical and practical solution to the "distortion" problem of Euclidean embeddings.
• Data Scarcity Solution: By leveraging diffusion models to synthesize high-quality, class-conditioned samples, it offers a robust strategy to overcome the "small data" bottleneck in few-shot learning, reducing overfitting and improving decision boundaries.
• Unsupervised Capability: The ability to train diffusion models using pseudo-labels derived from unsupervised clustering makes the framework highly applicable to real-world scenarios where labeled data is expensive or non-existent.