Graph Foundation Models Datasheet v1.0¶

Text is a sequence. An image is a grid. A graph is relation. A node's position is not its index in a file; it is defined by the topology and attributes of the system.

1. Fundamental state¶

Graph:

\[ G=(V,E) \]

with:

nodes \(V\);
edges \(E\subseteq V\times V\).

With attributes:

\[ G=(V,E,X_V,X_E) \]

where:

\[ X_V\in\mathbb R^{|V|\times d_v} \]

\[ X_E\in\mathbb R^{|E|\times d_e} \]

2. Graph types¶

directed / undirected;
weighted / unweighted;
homogeneous / heterogeneous;
static / temporal;
signed;
hypergraph;
knowledge graph;
molecular graph;
web/social graph.

“Graph model” without specifying the graph type is almost as vague as saying “data model.”

3. Permutation invariance/equivariance¶

If we relabel node IDs using a permutation \(P\), the graph's structural meaning does not change.

For graph-level prediction we want invariance:

\[ f(PX,PAP^T)=f(X,A) \]

For node-level representations we want equivariance:

\[ F(PX,PAP^T)=PF(X,A) \]

This is a fundamental symmetry that a conventional sequence does not preserve automatically.

4. Message Passing Neural Network¶

State of node \(v\) at layer \(l\):

\[ h_v^{(l)} \]

Message:

\[ m_v^{(l)} = \bigoplus_{u\in\mathcal N(v)} \psi_l(h_v^{(l)},h_u^{(l)},e_{uv}) \]

Update:

\[ h_v^{(l+1)} = \phi_l(h_v^{(l)},m_v^{(l)}) \]

\(\bigoplus\) should typically be permutation-invariant:

sum;
mean;
max;
attention aggregation.

5. Receptive field¶

After 1 layer, a node sees its 1-hop neighborhood.

After \(L\) layers:

\[ ReceptiveField\approx L-hop \]

But neighborhood size can grow exponentially:

\[ |N_L(v)|\sim d^L \]

with \(d\) an effective branching factor in an approximately homogeneous tree-like regime. Average degree alone does not bound a particular node neighborhood: a hub can be much larger. Bounds require maximum degree or explicit sampling fanouts, accounting for repeated nodes.

This creates memory and sampling problems.

6. Oversmoothing¶

With many layers, node embeddings may converge:

\[ \|h_u^{(L)}-h_v^{(L)}\|\rightarrow0 \]

and lose discriminative power.

More depth does not automatically mean better representations.

7. Oversquashing¶

Large amounts of distant information must pass through a fixed-dimensional bottleneck:

\[ Many\ distant\ signals \rightarrow h_v\in\mathbb R^d \]

Even without oversmoothing, the ability to transmit long-range dependencies can collapse.

This is a topological/information bottleneck.

8. Graph Attention¶

For edge \((v,u)\):

\[ q_v=W_Qh_v, \quad k_u=W_Kh_u, \quad v_u=W_Vh_u \]

Score:

\[ e_{vu}=\frac{q_v^Tk_u}{\sqrt d}+b_{vu} \]

\[ \alpha_{vu}=softmax_{u\in\mathcal N(v)}(e_{vu}) \]

Update:

\[ h'_v=\sum_{u\in\mathcal N(v)}\alpha_{vu}v_u \]

Bias \(b_{vu}\) may encode structure, relation type, or distance.

9. Graph Transformer¶

A vanilla Transformer has no intrinsic knowledge of adjacency.

Structure must be injected through mechanisms such as:

attention masks;
shortest-path bias;
edge encodings;
degree encodings;
Laplacian eigenvectors;
random-walk features;
structural tokens.

The fundamental question is:

\[ How\ is\ topology\ represented\ to\ attention? \]

10. Laplacian positional encoding¶

For this construction, assume an undirected graph with symmetric nonnegative adjacency \(A\), degrees \(d_i=\sum_jA_{ij}\), and \(D=diag(d_i)\). The inverse-degree formula below initially assumes \(d_i>0\) for every node; signed or directed graphs require an appropriate separate construction.

Graph Laplacian:

\[ L=D-A \]

or normalized:

\[ L_{sym}=I-D^{-1/2}AD^{-1/2} \]

To include isolated vertices, define diagonal \(S\) by \(S_{ii}=d_i^{-1/2}\) when \(d_i>0\) and \(S_{ii}=0\) otherwise, then use:

\[ L_{sym}=S(D-A)S \]

This convention gives zero rows/columns at isolated vertices, including a zero diagonal; it agrees with the preceding formula on positive-degree nodes.

Eigenvectors:

\[ Lu_i=\lambda_i u_i \]

may provide spectral coordinates.

Caveat¶

Eigenvectors have sign ambiguities and degeneracies; the architecture must account for them.

11. Random-walk structural encoding¶

With nonnegative row weights \(A_{ij}\), let \(D\) contain row sums (out-degrees for a directed graph). If all out-degrees are positive, the transition matrix is:

\[ P=D^{-1}A \]

If some out-degrees are zero, normalize each positive-degree row as \(P_{ij}=A_{ij}/d_i\) and assign each zero-degree node an absorbing row: \(P_{ii}=1\) and \(P_{ij}=0\) for \(j\ne i\). Other dangling-node policies must be declared. Every row then sums to one; signed edge weights cannot be used directly as transition probabilities. Entries below give transition probabilities after \(k\) steps (diagonal entries are return probabilities):

\[ P^k \]

carry local and global structural information.

12. Heterogeneous graphs¶

Types:

\[ type(v)\in\mathcal T_V \]

\[ type(e)\in\mathcal T_E \]

Messages may depend on relation type:

\[ m_{u\rightarrow v} =\psi_{type(e)}(h_u,h_v) \]

Knowledge graphs are a natural instance of this setting.

13. Temporal graphs¶

An edge carries a timestamp:

\[ e=(u,v,t) \]

State becomes event-dependent:

\[ h_v(t^+)=F(h_v(t^-),event_t) \]

Now the system has all three simultaneously:

topology;
time;
memory.

14. Node-level tasks¶

\[ P(y_v|G,X) \]

Examples:

classification;
regression;
anomaly/fraud scoring.

15. Edge / link prediction¶

\[ G_{obs}=(V,E_{obs},X),\quad Y_{uv}=\mathbf 1[(u,v)\in E_{target}] \]

Here \(X\) contains only attributes available to the predictor; \(E_{obs}\) is its observed context and \(E_{target}\) defines prediction labels. Model:

\[ p_\theta(Y_{uv}=1\mid G_{obs},u,v) \]

Declare train/validation/test edge splits and compute embeddings from the permitted context. Hide evaluated target edges, including reverse copies for undirected relations, from message passing and derived features. Temporal prediction uses only information available through the cutoff to predict later edges. Conditioning on the full graph that already contains the queried edge would make its membership known.

Simple score:

\[ s(u,v)=h_u^Th_v \]

or an MLP, bilinear form, or relation-aware scorer.

Negative sampling is a critical part of training.

16. Graph-level prediction¶

Readout:

\[ z_G=Readout(\{h_v\}_{v\in V}) \]

The readout must respect permutation invariance.

Then:

\[ P(y_G|z_G) \]

Example: molecular-property prediction.

17. Graph generation¶

We want:

\[ p(G) \]

or conditionally:

\[ p(G|C) \]

Possible decompositions include:

node generation;
edge generation;
adjacency generation;
graph diffusion;
autoregressive graph construction.

The state has no natural sequential ordering; any serialization imposes an artificial one.

18. Autoregressive graph generation¶

For a valid terminating discrete serialization \(S=(action_1,\ldots,action_T)\), including the stop action:

\[ p(S)=\prod_{t=1}^{T}p(action_t|action_{\lt t}) \]

with actions such as:

add node;
add edge;
set attribute;
stop.

Different action orders may represent the same graph. For a model supported on valid terminating sequences, the graph marginal is:

\[ p(G)=\sum_{S:decode(S)=G}p(S) \]

The decoder must fix what counts as the same graph (including any equivalence under relabeling). Identifying this marginal with one sequence probability requires a canonical bijection and model support restricted to canonical sequences; choosing one training order alone does not establish that identity.

19. Graph diffusion¶

Corruption can be applied to:

node attributes;
edge states;
adjacency;
coordinates in molecular/3D graphs.

Then denoise:

\[ G_t\rightarrow G_{t-1} \]

The process must respect structural and discrete constraints.

20. Graph tokenization¶

Foundation models need a way to map heterogeneous graphs into a shared interface.

Possibilities include:

node tokens;
subgraph tokens;
motif tokens;
random-walk sequences;
structural encodings + features;
learned graph patches.

There is no universal tokenizer analogous to BPE.

21. Graph foundation model¶

Goal: learn an operator transferable across graphs and tasks:

\[ f_\theta(G,task/context)\rightarrow output \]

Challenges:

different feature dimensions;
different node/edge semantics;
different graph sizes;
different graph types;
different task types.

22. Feature projection¶

A new graph may have:

\[ X\in\mathbb R^{N\times d_{new}} \]

while the backbone expects \(d_h\).

Projector:

\[ H=XW_p \]

If every dataset requires a new projector, “foundation” loses part of its ideal zero-shot character.

Acacia 2026 is relevant precisely because it aims to accept arbitrary dimensionalities/semantics without training additional projectors.

23. In-context graph learning¶

Analogy:

\[ ContextGraphs/Labels + QueryGraph \rightarrow Prediction \]

or examples of node/link tasks embedded in the structural context.

This moves adaptation from weight updates into inference/context.

24. Neighborhood sampling¶

On a very large graph, the full neighborhood is infeasible.

Fanout:

\[ K_1,K_2,\ldots,K_L \]

For one root, the final sampled hop in a full sampling tree contains:

\[ N_{leaf}=\prod_{l=1}^{L}K_l \]

The total across all hops, including the root, is:

\[ N_{tree}=1+\sum_{l=1}^{L}\prod_{j=1}^{l}K_j \]

These are sampling-tree occurrences with every fanout filled. Distinct node counts can be smaller because of overlap, repeated samples, or insufficient degree; multiple roots can also share nodes. The last product alone is a dominant-order approximation only in suitable fanout/depth regimes.

Trade-off:

\[ Fanout\uparrow\Rightarrow Coverage\uparrow,Memory\uparrow \]

25. Full-batch vs mini-batch graph learning¶

Text/image datasets contain relatively independent examples.

A single giant graph contains shared dependencies.

Mini-batching therefore requires mechanisms such as:

subgraph sampling;
neighborhood sampling;
cluster partitioning;
graph batching.

This changes the data-pipeline engineering.

26. Memory scaling¶

Node states:

\[ M_V\approx |V|d_hb \]

Edge states:

\[ M_E\approx |E|d_eb \]

Here \(b\) is bytes per stored scalar. These estimates count one set of node/edge representations; layer activations, gradients, optimizer state, adjacency indices, and materialized messages are separate. Global attention over all nodes has a pair count of:

\[ O(|V|^2) \]

quickly becomes infeasible.

For width d and fixed layer/head counts, sparse attention mixing or aggregation over edges costs:

\[ O(|E|d) \]

This excludes projections, typically \(O(|V|d^2)\), and learned message functions; a dense width-d MLP per edge can add \(O(|E|d^2)\). Materializing all messages can use \(O(|E|d)\) memory, while fused implementations may avoid that tensor. Compute and stored-state estimates are different quantities.

27. Scaling laws in graphs¶

GraphBFF 2026 demonstrates predictable scaling with model/data capacity in a graph-foundation-model regime and trains a 1.4B-parameter Transformer on 1B samples.

The relevant insight:

the old intuition that “GNNs do not scale like Transformers” can no longer be treated as a universal law; architecture, batching, and pretraining diversity change the regime.

28. Web graph as a pretraining corpus¶

Acacia 2026 trains directly on the Common Crawl web graph and demonstrates:

node classification;
link prediction;
clustering;
graph generation;
in-context behavior;
no dependency on LLM pretraining.

This reinforces the idea that graph structure itself can serve as a foundation signal.

29. Graph + text multimodality¶

Many graphs contain node text:

\[ h_v=Fuse(GraphFeature_v,TextEncoder(text_v)) \]

Do not confuse a graph foundation model with “an LLM serializing edges.”

The two can coexist.

30. Metrics¶

Node classification:

accuracy/F1/AUC/PR-AUC.

Link prediction:

Hits@K;
MRR;
ROC-AUC;
PR-AUC.

Graph regression:

MAE/RMSE.

Generation:

validity;
uniqueness;
novelty;
structural/property distributions.

31. Failure surfaces¶

oversmoothing;
oversquashing;
neighborhood explosion;
heterophily;
feature-semantics mismatch;
projector dependence;
graph-size shift;
degree-distribution shift;
temporal leakage;
negative-sampling bias;
disconnected components;
permutation/order artifacts in serialization;
graph-sparsification loss.

32. Graph FM dissection checklist¶

What kind of graph?
What is the node/edge state?
Message passing or global attention?
How does structure enter attention?
Is there positional/structural encoding?
What is the receptive field?
How are oversmoothing/oversquashing mitigated?
How does mini-batching work?
Is neighborhood sampling used?
What is the task interface?
Does it accept arbitrary feature dimensions?
Does it require a projector/fine-tune per dataset?
Does it support in-context graph learning?
How does it scale with |V| and |E|?
What is the cost of graph generation?

Snapshot references¶

Billion-Scale Graph Foundation Models / GraphBFF — https://arxiv.org/abs/2602.04768
Acacia: Training Graph Foundation Models on The Web Graph — https://arxiv.org/abs/2609.30894