How OpenGraph Enables Zero‑Shot Graph Learning Across Datasets

Research Background

Graph learning (Graph Learning) can mine and learn from complex relational data and has shown great value in recommendation systems, social network analysis, citation networks, traffic networks, and many other domains. Graph Neural Networks (GNNs) use iterative message‑passing to capture high‑order relationships in graph‑structured data and have achieved remarkable success.

Typical end‑to‑end GNNs require large amounts of high‑quality labeled data. Recent work therefore adopts a pre‑training‑and‑fine‑tuning paradigm, using self‑supervised tasks (contrastive learning, mask reconstruction, local‑global mutual information maximization, etc.) to pre‑train on unlabeled graphs before fine‑tuning on a small labeled set.

Although pre‑training improves performance, its generalization is limited when there is a distribution shift between pre‑training and downstream tasks—for example, when user preferences or item popularity change in recommendation scenarios. Prompt‑based fine‑tuning has been proposed to adapt pre‑trained graph models more efficiently.

Existing methods still assume that training and test graphs share the same node set and feature space, which severely restricts the applicability of pre‑trained graph models. This work therefore seeks to enable zero‑sample prediction on completely unseen graphs, i.e., to extract features and make accurate predictions for test graphs without ever seeing any of their nodes, edges, or features during training.

Model Overview

OpenGraph consists of three parts: (1) a unified graph tokenizer, (2) a scalable graph transformer, and (3) large‑language‑model (LLM) knowledge distillation.

Unified Graph Tokenizer

To handle the huge heterogeneity of nodes, edges, and features across datasets, OpenGraph first builds a tokenizer that maps any graph into a unified token sequence. Each token carries a semantic vector describing the corresponding node, and the tokenizer projects graphs into a common representation space.

Higher‑order smoothed adjacency matrix. The tokenizer incorporates powers of the adjacency matrix (after Laplacian normalization) so that high‑order connections are captured and sparsity of the raw adjacency is mitigated.

Topology‑aware mapping for arbitrary graphs. Because adjacency matrices from different datasets have different dimensions, the method first projects each adjacency matrix into a node‑representation sequence, then processes the sequence with a variable‑length model. To preserve structural information, a topology‑aware mapping is built using fast singular‑value decomposition (SVD); two rounds of SVD are sufficient in practice.

Scalable Graph Transformer

After tokenization, OpenGraph feeds the unified token sequence into a transformer that models complex node dependencies. Two sampling techniques are introduced to keep the model efficient.

Token sequence sampling. Instead of modeling all pairwise token interactions (quadratic in the number of nodes), the transformer samples only token pairs within the current mini‑batch, reducing computational complexity to the square of the batch size while still preserving global structural cues.

Anchor sampling in self‑attention. To further lower the quadratic cost, the transformer selects a small set of anchor tokens. All node‑to‑anchor relationships are learned in two stages, replacing full pairwise attention.

LLM Knowledge Distillation

Because real‑world graph data are often scarce or private, OpenGraph leverages large language models to generate synthetic graph data for pre‑training. The LLM‑driven augmentation aims to produce node features and edge structures that closely resemble real graphs.

LLM‑based node generation. Nodes are first created with textual descriptions. For large‑scale domains (e.g., e‑commerce with billions of products), the LLM is prompted to list fine‑grained sub‑categories iteratively, producing a hierarchical set of realistic node labels.

Prompt‑tree algorithm. The hierarchical generation follows a tree‑structured prompting strategy: a generic root node (e.g., “product”) is expanded into sub‑categories, which are further refined until leaf nodes represent concrete entities.

LLM‑guided edge generation with Gibbs sampling. Starting from a random graph, Gibbs sampling iteratively updates one dimension (edge) at a time. The conditional probability of adding an edge is estimated by the LLM from the textual node features. To keep sampling tractable, node embeddings from the LLM are used with a simple similarity measure, and three tricks are applied:

Dynamic probability normalization. Recent similarity scores are maintained, and the current estimate is mapped to a distribution centered on the mean with a standard‑deviation‑scaled range, yielding probabilities close to [0, 1].

Incorporating node locality. Each node receives a locality index; the probability of an edge decays with the absolute difference of these indices, reflecting the fact that real graphs exhibit local connectivity.

Injecting graph topology patterns. After an initial synthetic graph is generated, a lightweight graph convolution network refines node representations, and a second sampling pass produces the final graph structure.

Experimental Validation

Experiments use only LLM‑generated data for pre‑training OpenGraph, while testing on real‑world datasets for node classification and link prediction. Two evaluation regimes are considered.

Zero‑shot setting. The model is trained on synthetic data and directly evaluated on completely unseen real graphs with no overlap in nodes, edges, features, or labels.

Few‑shot setting. Baselines are pre‑trained on the same synthetic data and then fine‑tuned with a small number of labeled examples (k‑shot) on the target task.

Overall Performance Comparison

Across eight test datasets covering two tasks, OpenGraph consistently outperforms existing pre‑training methods in zero‑shot scenarios and narrows the gap in few‑shot scenarios, demonstrating superior cross‑dataset generalization.

Graph Tokenizer Study

Ablation experiments replace the topology‑aware mapping with simple one‑hot IDs, random mappings, or degree‑based embeddings. All alternatives degrade performance, confirming the importance of high‑order smoothing and topology‑aware projection.

Pre‑training Data Study

Training on different synthetic datasets—each missing one of the three augmentation tricks—or on real datasets (Yelp2018, Gowalla) and a related real dataset (ML‑10M) shows that the full synthetic pipeline yields the best results, while using unrelated real data can hurt performance due to distribution mismatch.

Transformer Sampling Techniques Study

Ablation of token‑sequence sampling (Seq) and anchor sampling (Anc) demonstrates that both reduce memory and time costs; Seq improves accuracy, while anchor sampling shows mixed effects depending on the dataset.

Conclusion

The paper presents OpenGraph, a highly adaptable framework that captures universal topological patterns in graphs and excels at zero‑sample graph learning across diverse downstream applications. By combining a unified tokenizer, an efficient transformer, and LLM‑driven data augmentation, the model achieves strong generalization on multiple benchmarks, opening avenues for future work on automatic noise detection and counterfactual structural learning.