PaperlayerView exact revision on arXiv

Source-linked AI summary

OpenGraph: Towards Open Graph Foundation Models

Lianghao Xia, Ben Kao, Chao Huang

arXiv:2403.01121v4cs.LGcs.AIcs.SI

TL;DR

Graph models can struggle to generalize to unseen graphs with different characteristics, limiting zero-shot transfer across domains. OpenGraph combines LLM-generated graph data, a unified graph tokenizer, and a scalable graph transformer. It outperforms baselines across eight datasets without overlap between pre-training and downstream data.

  • Problem

    Graph pre-training can struggle to generalize across domains with different node sets, features, and relation semantics, while domain-specific graph data may be scarce.

    Source: §1 · pp. 1–2

  • Method

    OpenGraph uses LLM-generated augmented graphs, a topology-aware unified graph tokenizer, and a scalable transformer to model node-wise dependencies.

    Source: §1 · p. 2

  • Results

    OpenGraph outperforms baselines on all 8 datasets across different categories without overlap between pre-training and downstream data.

    Source: §4.2 · p. 5

  • Takeaways & Limitations

    The authors conclude that OpenGraph generalizes across diverse zero-shot graph learning tasks and applications.

    Source: §6 · p. 8

    OpenGraph does not model heterogeneous relations or node types, which may affect performance and generalization on strongly heterogeneous graphs such as knowledge graphs.

    Source: §7 · p. 9

Abstract

from arXiv · show

Graph learning has become essential in various domains, including recommendation systems and social network analysis. Graph Neural Networks (GNNs) have emerged as promising techniques for encoding structural information and improving performance in tasks like link prediction and node classification. However, a key challenge remains: the difficulty of generalizing to unseen graph data with different properties. In this work, we propose a novel graph foundation model, called OpenGraph, to address this challenge. Our approach tackles several technical obstacles. Firstly, we enhance data augmentation using a large language model (LLM) to overcome data scarcity in real-world scenarios. Secondly, we introduce a unified graph tokenizer that enables the model to generalize effectively to diverse graph data, even when encountering unseen properties during training. Thirdly, our developed scalable graph transformer captures node-wise dependencies within the global topological context. Extensive experiments validate the effectiveness of our framework. By adapting OpenGraph to new graph characteristics and comprehending diverse graphs, our approach achieves remarkable zero-shot graph learning performance across various settings. We release the model implementation at https://github.com/HKUDS/OpenGraph.

1 Introduction

OpenGraph targets zero-shot graph learning across domains, where shifts in node sets, feature semantics, and relation meanings challenge generalization. It combines LLM-based graph augmentation, universal graph tokens, and a scalable graph transformer.

1 Introduction

  • Graph pre-training can struggle to generalize across downstream domains, where shifts in node sets and relation semantics can degrade performance.The paper also identifies variation in node sets and feature semantics across diverse domains as a challenge for prompt-tuned models.Source: §1 · p. 1
  • LLM-generated augmented graphs, paired with tree-of-prompt regularization and Gibbs sampling, are proposed to address domain-specific data scarcity.The authors say these graphs resemble real-world instances and support pre-training that captures downstream task context.Source: §1 · p. 2
  • A topology-aware tokenizer creates universal graph tokens, while a scalable transformer models node-wise dependencies in global context.The transformer uses two-stage self-attention and token-sequence sampling to reduce sequence length while preserving crucial context.Source: §1 · p. 2
  • OpenGraph is reported to show remarkable generalization across diverse datasets and settings.The introduction describes experiments on diverse datasets but provides no specific metric or numerical comparison here.Source: §1 · p. 2

2 Preliminaries

The preliminaries define graph learning and zero-shot graph learning, then state the objective of learning across graph domains with no shared nodes, edges, or node features.

2 Preliminaries

  • A graph comprises nodes, edges, and node attributes; graph learning produces representations that encode structural and attribute information for tasks such as link prediction and node classification.The passage describes these tasks as predicting node connections and categories, respectively.Source: §2 · p. 2
  • Zero-shot graph learning evaluates a model on different test graphs without shared graph tokens, assessing generalized topology and node-wise dependencies.The stated objective is to minimize prediction error on the test graph.Source: §2 · p. 2
  • Training and test graphs share no nodes, edges, or node features, creating distribution shifts across graph domains.The objective is a universal architecture whose parameters are learned by minimizing graph-learning losses on training graphs.Source: §2 · p. 2

3 Methodology

OpenGraph combines topology-aware graph tokens, a scalable graph transformer, and LLM-generated graph data to model diverse graphs and support downstream graph learning.

3.1 Unified Graph Tokenizer

  • The unified tokenizer maps input graphs to sequences of node tokens with semantic vectors in a shared representation space.It uses smoothed adjacency and a topology-aware projection to standardize representations across graphs.Source: §3.1 · p. 3

3.1.1 Smoothed High-Order Adjacency

  • Combining normalized adjacency matrices at multiple powers captures high-order connectivity and sparse node-wise relations.The maximum power order considered is L.Source: §3.1.1 · p. 3

3.1.2 Topology-aware Projection with Arbitary Graphs

  • Fast SVD projects varying-size adjacency into sequence data, with two iterations reported to preserve topology with minimal computational overhead.Layer normalization reduces numerical variance across datasets, and the resulting node tokens incorporate topology information.Source: §3.1.2 · p. 3

3.2 Scalable Graph Transformer

  • Token-sequence sampling reduces transformer input length from |V| to 3 × B, while anchor-based two-stage attention lowers complexity from O(B^2 × d) to O(B × S).Sampled topology-aware embeddings retain local structural information and reflect overall graph structure.Source: §3.2 · p. 3

3.3 Knowledge Distillation from LLM

  • LLM-generated graph data is designed to approximate real-world graph characteristics and make augmented pre-training data more relevant.The paper motivates this augmentation partly by privacy-related difficulty obtaining diverse domain datasets.Source: §3.3 · pp. 3–4

3.3.1 LLM-based Node Generation

  • Tree-of-prompt generation iteratively divides broad node categories into finer semantic subcategories until entities resemble real-world instances.The process structures general nodes as tree roots and fine-grained entities as leaves.Source: §3.3.1 · p. 4

3.3.2 Edge Sampling using Node Profiles

  • Gibbs sampling generates edges from node representations: LLM-derived hidden vectors estimate connection probabilities, which are dynamically normalized and adjusted for node locality.The locality adjustment uses exponential decay to prevent excessive connections among semantically related nodes.Source: §3.3.2 · pp. 4–5

3.3.3 Graph Topological Pattern Injection

  • A GCN refines initial node embeddings to capture graph topology and align graph-derived representations with textual embeddings before final edge generation.The authors describe this as avoiding distribution shifts between graph and textual spaces.Source: §3.3.3 · p. 5

4 Evaluation

The evaluation tests zero-shot transfer across eight real-world datasets and two graph-learning tasks, then examines tokenizer choices, pretraining data, sampling, and model scale. OpenGraph outperforms baselines across all eight datasets without overlap between pretraining and downstream data, while the component studies reveal performance and efficiency trade-offs.

4.1 Experimental Settings

  • The evaluation uses eight real-world datasets for link prediction and node classification, with original train-test splits and zero-shot OpenGraph predictions compared against few-shot baselines.The baselines are evaluated in two few-shot settings.Source: §4.1 · p. 5

4.2 Overall Performance Comparison (RQ1)

  • OpenGraph outperforms few-shot baselines on all eight datasets in zero-shot evaluation, with no overlap between pretraining and downstream data.The comparison covers link prediction and node classification.Source: §4.2 · p. 5, Table 1 · p. 6

4.3 Investigation on Graph Tokenizer (RQ2)

  • Adjacency smoothing and topology-aware SVD projection outperform tokenizer alternatives; zero smoothing damages topology, and one-hot, degree, and random projections lag.The best nonzero smoothing order varies: L=2 for Movielens-1M, and L=3/L=1 for OGBL-ddi top-20/top-40, respectively.Source: §4.3 · pp. 5–6, Figure 2 · p. 7

4.4 Influence of Pre-training Datasets (RQ3)

  • Generated pretraining data performs best except on ML-1M and ML-10M, where related ML-10M pretraining leads; removing -Norm, -Loc, or -Topo hurts downstream results.Yelp and Gowalla pretraining does not provide an advantage over generated data.Source: §4.4 · pp. 6–7, Table 2 · p. 7

4.5 Impact of Sampling in Transformer (RQ4)

  • Removing both sampling strategies causes ML10M out-of-memory errors; sequence-only sampling reduces training memory and performs best on OGBL-ddi, while anchor sampling reduces test cost but lowers performance.Without sequence sampling, training efficiency decreases; without either strategy, OGBL-ddi memory and time efficiency are lowest.Source: Table 3 · p. 7, §4.5 · p. 7

4.6 Impact of Model Scale (RQ5)

  • More transformer layers increase training and testing time linearly without consistent performance gains; wider hidden dimensions cost quadratically but improve performance by reducing graph-token projection information loss.Performance is measured by Recall@20, and time by 100 training and 100 test steps.Source: §4.6 · pp. 7–8, Figure 3 · p. 8

4.7 End-to-End Training Performance (RQ6)

  • OpenGraph also demonstrates strong graph-learning capability in supervised learning when compared with baselines trained on the same few-shot datasets.Detailed results and analysis are provided in Appendix A.3.6.Source: §4.7 · p. 8

5 Related Work

Prior work uses graph neural networks, self-supervised learning, and LLM-based graph analysis, but generalization across graph domains remains a challenge. OpenGraph targets transferable structural patterns, including where textual node features are unavailable.

Graph neural networks

  • GNNs use message passing to propagate information from neighboring nodes; representative methods include Graph Convolutional Networks (GCNs) and Graph Attention Networks (GATs) (Jin et al., 2021; Yuan et al., 2020; Gao et al., 2018; Zhang et al., 2021; Zhang et al., 2022b; Liao et al., 2019).Source: §5 · p. 8

Self-supervised graph learning

  • Self-supervised graph learning addresses limited labels, while contrastive and adaptive-augmentation methods use graph structure and patterns for data-efficient training (Wu et al., 2021b; Lee et al., 2022; Xia et al., 2023).GraphCL and SGL contrast positive and negative samples; JOAO and GCA use adaptive augmentation (You et al., 2020; Wu et al., 2021a; You et al., 2021; Zhu et al., 2021).Source: §5 · p. 8

LLM-based graph analysis

Generalization and structural patterns

  • Existing approaches struggle to generalize across tasks, while some domains lack high-quality textual node features; OpenGraph seeks universal structural patterns without requiring textual data.The passage identifies user-behavior and neuronal graphs as examples where such features can be difficult to obtain.Source: §5 · p. 8

6 Conclusion

OpenGraph combines a scalable graph transformer with LLM-enhanced data augmentation to capture topological patterns across diverse graph structures. The authors report zero-shot generalization across applications and plan to explore counterfactual learning.

Conclusion

  • OpenGraph demonstrates exceptional generalization in zero-shot graph learning tasks across various applications.The framework is described as adaptable to complex topological patterns in diverse graph structures.Source: §6 · p. 8
  • The framework uses a scalable graph transformer and LLM-enhanced data augmentation, and benchmark experiments validate its performance.Source: §6 · p. 8
  • Future work will incorporate counterfactual learning to investigate noisy connections and influential structures while learning transferable structural patterns.Source: §6 · p. 8

7 Limitations

The authors identify limitations in OpenGraph’s representation of heterogeneous graphs, breadth of evaluation, and explainability. They characterize the work as an initial exploration of graph foundation models focused on LLM-derived generalization without textual features.

Scope

  • This initial exploration focuses on distilling LLM generalization capabilities without relying on textual features.The authors state that limitations remain for future work.Source: §7 · p. 9

Heterogeneous graphs

  • OpenGraph does not model heterogeneous relations or node types, which may affect performance and generalization on strongly heterogeneous graphs such as knowledge graphs.Source: §7 · p. 9

Evaluation breadth

  • Evaluation covers eight datasets spanning different domains, and the authors call for additional datasets from more diverse application domains.Source: §7 · p. 9

Explainability

  • OpenGraph’s explainability remains unexplored, which the authors say hinders applicability and understanding of its generalization.Source: §7 · p. 9

Future directions

  • The authors prioritize heterogeneous representation learning, broader dataset evaluation, and improved explainability for wider applicability and deeper insight.Source: §7 · p. 9

A Appendix

The appendix provides supplementary material on OpenGraph’s model, graph generation, and experiments.

Appendix contents

A.1.1 Zero-Shot Node Classification

OpenGraph recasts node classification as link prediction between regular nodes and special class nodes, using observed class-node relations for zero-shot prediction.

A.1.1 Zero-Shot Node Classification

  • OpenGraph turns node classification into link prediction between regular nodes and special nodes representing classes, enabling zero-shot prediction from observed class-node relations.Source: §A.1.1 · p. 11

A.1.2 Handling Node Features

OpenGraph converts heterogeneous node attributes into a unified graph structure that its tokenizer and transformer can process, and adds edges between the most similar node pairs.

A.1.2 Handling Node Features

  • OpenGraph converts textual, numerical, and categorical attributes into a unified graph structure for tokenization and transformer processing.Source: §A.1.2 · p. 11
  • For datasets with node features, it adds augmented edges between the top B × K most-similar node pairs in each batch.Each batch contains B × |V| candidate edges, ranked by pairwise similarity scores.Source: §A.1.2 · p. 11

A.1.3 Details of Scalable Graph Transformer

OpenGraph combines anchor-based attention, generated graph data, and unified projections for cross-dataset learning. Its end-to-end models perform best on all tested datasets and show less degradation in sparse one-shot settings.

A.1.3 Details of Scalable Graph Transformer

  • Anchor-based self-attention reduces a 3 × B sequence to S elements before reversing the process; S = d/H < B keeps memory costs similar to other fully connected components.Each layer also uses a fully connected block with residual connections and layer normalization.Source: §A.1.3 · p. 11

A.1.4 Model Optimization

  • MAE pretraining removes label edges and jointly trains generated graphs with random alternations; graph projections are regenerated every 10 steps.The reported setup uses three generated datasets, embedding size d = 1024, and 256 sampled anchor nodes.Source: §A.1.4 · p. 11, §A.3.3 · p. 13

A.2.1 Prompt Template and Examples of Generated Nodes

  • The LLM recursively divides general nodes into finer, real-world-like categories, while Gibbs sampling uses LLM-given node representations to generate edges.Source: §A.2.3 · p. 12

A.3.2 Evaluation Protocol

  • Evaluation covers eight real-world datasets—five for link prediction and three for node classification—with zero-shot tests using target-graph training information.Link prediction uses Recall@20 and Recall@40; node classification uses Accuracy and Macro-F1.Source: §A.3.1 · p. 12, §A.3.2 · p. 13

A.3.4 Baselines

  • The evaluation includes nine baseline models from four research lines: graph-agnostic methods, non-pretraining GNNs, graph pretraining, and graph prompt tuning.Source: §A.3.4 · p. 14

A.3.6 End-to-end Training (RQ6)

A.3.5 Alternative Projection Methods (RQ2)

  • Random projection outperforms one-hot and degree embeddings in the described comparison; it assumes no particular node distribution, which the authors say reduces overfitting risk.Source: §A.3.5 · p. 14
Loading 2403.01121v4…