PaperlayerView exact revision on arXiv

Source-linked AI summary

Training Graph Foundation Models on The Web Graph

Ryoma Sato

arXiv:2609.30894v1cs.AIcs.LG

TL;DR

Many graph foundation models depend on pretrained LLMs or require extra heads or projectors for new graphs and labels. Acacia is trained on the Common Crawl web graph and supports varied graph features and tasks without additional training. Its weights show nontrivial unsupervised clustering and in-context learning, providing evidence of graph-model capabilities acquired from scratch.

  • Problem

    Many graph foundation models depend on pretrained LLMs or need additional heads or projectors for new graphs or labels, while graph feature dimensions and meanings vary across domains.

    Source: §1 · p. 1, §2.3 · p. 5

  • Method

    Acacia is trained exclusively on the Common Crawl web graph and uses autoregressive token prompts to support varied graph features and tasks without additional training.

    Source: §1 · p. 1, §2.1 · p. 4

  • Results

    Acacia-315m achieves nontrivial node-clustering accuracy in a fully unsupervised setting and possesses in-context learning capabilities.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Acacia provides evidence that graph models can acquire emergent capabilities from scratch like LLMs.

    Source: §5 · p. 9

Abstract

from arXiv · show

We introduce Acacia, a graph foundation model, trained on the web graph. Acacia (i) supports arbitrary feature dimensionalities and semantics without additional training, (ii) supports a wide range of tasks, including node classification, link prediction, node clustering, and graph generation, without additional training, (iii) has in-context learning capabilities, and (iv) does not rely on pretrained LLMs. In particular, existing graph foundation models often require training additional classification heads or feature projectors to accommodate new graphs or new labels, whereas Acacia does not. Moreover, existing graph foundation models often gain their capabilities by being stitched together with pretrained LLMs, whereas Acacia is trained from scratch using only the Common Crawl web graph. This is also an important result because it provides evidence that graph models can acquire emergent capabilities from scratch like LLMs.

1 Introduction

Graph models can share an architecture, but conventional models are tied to fixed feature dimensions, feature semantics, and tasks, while many graph foundation models depend on pretrained LLMs or added components. Acacia is trained on the Common Crawl web graph and uses one autoregressive model across multiple tasks without additional training.

1 Introduction

  • Conventional graph models use fixed feature dimensionalities, semantics, and tasks, while many graph foundation models rely on LLMs or added heads and projectors for new graphs or labels.One For All expresses features as text for an LLM; AnyGraph uses task-dependent routing but does not fully align new graphs or labels.Source: §1 · p. 1
  • Acacia supports arbitrary feature dimensionalities and semantics, multiple graph tasks, and in-context learning without additional training or pretrained LLMs.The listed tasks include node classification, link prediction, node clustering, and graph generation.Source: §1 · p. 1
  • Training exclusively on the Common Crawl web graph uses its naturally connected, diverse link topologies as a basis for handling varied graph structures.The paper presents this as an expectation for what learning web structure enables.Source: §1 · p. 1
  • Acacia is a decoder-only autoregressive Transformer that performs different tasks by generating node, edge, and label tokens in chosen input arrangements.For example, supplying a graph and continuing with labels supports classification or clustering; prepending labeled examples supports in-context learning.Source: §1 · pp. 1–2
  • Acacia-315m has 315M parameters and was trained on 11 billion tokens; it achieves nontrivial unsupervised node-clustering accuracy and has in-context learning capabilities.The paper presents obtaining these capabilities from scratch, without pretrained LLMs, as an important result.Source: §1 · p. 2

2 Acacia

Acacia encodes graphs as typed tokens and uses autoregressive prompting to support several tasks, including in-context learning. Its training combines Common Crawl subgraphs, altered features, and a staged recipe that starts from scratch.

2.1 Overview

  • Acacia uses headers, nodes, edges, and labels as token types, with shared-dimensional blocks encoding IDs, node features, edge endpoints, and label IDs.The token layout lets all token types be treated uniformly.Source: §2.1 · p. 2
  • Prefilling a graph supports label or edge prediction; omitting labels yields clustering, while adding labeled graph components provides in-context examples.Examples can be fixed or retrieved from graphs with structures similar to the test graph.Source: Figure 2 · p. 3, §2.1 · pp. 4–5, Figure 3 · p. 4

2.2 Training on the Web Graph

  • Training graphs come from Common Crawl pages and hyperlinks, sampled by breadth-first search from random nodes at sizes of 8–128.Different conditioning and prediction token types are mixed; smaller graphs are included because large-only training can impede early learning.Source: §2.2 · p. 5

2.3 A Structure Independent of Feature-Dimension Alignment

  • To reduce dependence on feature-dimension meanings, Acacia hashes page text, sometimes replaces node features with random samples, and projects test features to 64 dimensions.The shared test-time projection corresponds to training-time hashing; random-feature examples also support cases where test-time node features are unavailable.Source: §2.3 · pp. 5–6

2.4 The Acacia Recipe

  • Acacia-315M is a 315M-parameter, 32-layer decoder-only model with a 960-dimensional hidden state, using an architectural configuration but no pretrained weights.Training starts from random initialization; the recipe first uses page titles, then adds page-body text and explicitly constructed in-context graphs.Source: §2.4 · p. 6

3 Experiments

Acacia is evaluated without weight updates across node classification, in-context learning, and unsupervised clustering. It outperforms an untrained model and chance in the reported settings, with PubMed node classification an exception without in-context examples.

3 Experiments

  • The experiments test whether Acacia-315M adapts across tasks and datasets without weight updates, using Cora, CiteSeer, PubMed, and ogbn-products with differing features, labels, and graph structures.The standard node-classification setup predicts a test node’s label from a breadth-first-search neighborhood of up to 128 nodes, with labels supplied only for training nodes.Source: §3 · p. 6, §3.1 · p. 6

3.1 Node Classification

  • On three datasets, Acacia outperforms the untrained model and chance for node classification; PubMed is the exception because only 60 of 19,717 nodes are labeled.In many PubMed neighborhoods, no training label or correct label is present, so predictions are necessarily counted as incorrect; the authors say in-context learning is useful in such cases.Source: Table 3 · p. 7, §3.1 · p. 7

3.2 In-Context Learning

  • With in-context learning, Acacia outperforms the untrained model and chance on every dataset, including PubMed, where classification without in-context learning was close to chance.The authors identify this as evidence that LLM-style in-context learning through token prompts is possible using graph data alone.Source: Table 4 · p. 7, §3.2 · p. 7

3.3 Clustering

  • In every clustering setting and dataset, Acacia outperforms both the randomly initialized untrained model and chance.ARI and AMI are used for evaluation; labels are not provided to the model.Source: Table 5 · p. 8, §3.3 · p. 8

4 Related Work

The paper positions Acacia as a pure graph model trained from scratch on the web graph, in contrast to approaches relying on curated graph data or pretrained models from other domains.

4 Related Work

  • Prior graph foundation models commonly pretrain on citation, molecular, in-house, or synthetic data; the authors aim to learn general capabilities from the less curated Common Crawl web graph.The authors note that such existing data may improve performance on related datasets without necessarily guaranteeing generality to other tasks.Source: §4 · p. 8
  • Acacia’s stated distinction is GPT-style in-context learning built from scratch and applicability to new graphs with different node features, unlike limitations the authors identify in PRODIGY and VISION [16] [10].The paper acknowledges that graph-data in-context learning methods already exist [10] [16].Source: §4 · p. 8
  • LLM- and tabular-model-based approaches can achieve high accuracy, but may be difficult to apply to data that cannot readily be converted into text or tables.The authors also say it can be difficult to distinguish performance due to pretrained models from performance due to graph learning.Source: §4 · p. 8

5 Conclusion

The conclusion presents Acacia as a web-graph-trained model that handles varied features and tasks without additional training or pretrained LLMs. Its results are offered as evidence that graph models can acquire emergent capabilities from scratch.

5 Conclusion

  • Acacia supports arbitrary feature dimensionalities and semantics and multiple tasks without additional training, while providing in-context learning without pretrained LLMs.The listed tasks include node classification, link prediction, node clustering, and graph generation.Source: §5 · p. 9
  • Trained on the web graph, Acacia achieves nontrivial downstream performance without adaptation while learning diverse graph structures.Source: §5 · p. 9
  • The authors present Acacia as evidence that graph models can acquire emergent capabilities from scratch, as LLMs do.Source: §5 · p. 9
Loading 2609.30894v1…