When Do Graph Foundation Models Transfer? A Data-Centric Theory

Graph foundation models (GFMs) aim to reuse a single backbone across diverse graph domains, yet their transfer is often uneven and can exhibit negative transfer. While most prior work improves transfer through architectural or adaptation choices, we ask a data-centric question: which properties of two graph domains determine how much a fixed representation model changes its outputs? Using a graphon-based continuous limit for dense graphs, we show that for both set-based and message-passing tokenizations, any Lipschitz backbone admits an explicit decomposition of cross-domain output shift into (i) graph-specific finite-sample approximation terms and (ii) an intrinsic, relabeling-invariant domain discrepancy capturing structural mismatch. A key ingredient is positional-encoding (PE) stability: we establish stability guarantees for spectral PEs and highlight contrasting behaviors of eigenvector- versus subspace-based PEs. Experiments on synthetic and real graphs validate the theory and translate the decomposition into guidance for data curation in GFM transfer.

Many real-world data are naturally represented as graphs, such as social networks, recommendation systems, biological interactions, and cybersecurity events. Recent graph foundation models aim to train one reusable model that can work across many graph domains. However, in practice, a model that works well on one type of graph may perform poorly on another, and it is often unclear whether the failure comes from the model, the training data, or the difference between domains. This paper studies this problem from a data-centered perspective. We develop a theory that separates transfer difficulty into three parts: errors caused by observing only finite graphs, mismatch between the underlying structures of two graph domains, and instability from how graph structure is encoded for the model. Our experiments show that simply using larger graphs during training does not always improve performance, that carefully adding larger synthetic graphs can help in some cases, and that some graph encodings become unstable when too many structural features are used. These findings provide practical guidance for evaluating and curating data for graph foundation models.