pith. sign in

arxiv: 2605.29828 · v1 · pith:WQRP2GLNnew · submitted 2026-05-28 · 💻 cs.LG

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

Jiajun Zhu , Ying Chen , Peihao Wang , Yixuan He , Pan Li , Aditya Akella , Zhangyang Wang This is my paper

Pith reviewed 2026-06-29 08:27 UTC · model grok-4.3

classification 💻 cs.LG
keywords graph foundation modelstransfer learninggraphon limitdomain discrepancypositional encoding stabilitymessage passingset-based tokenizationdata curation
0
0 comments X

The pith

Graph foundation model output shifts decompose into finite-sample approximation terms and an intrinsic structural domain discrepancy.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper asks what data properties control transfer performance when a fixed graph backbone is applied across domains. It derives an explicit split of cross-domain output change that holds for both set-based and message-passing tokenizers whenever the backbone is Lipschitz. The split isolates graph-specific sampling effects from a relabeling-invariant discrepancy that measures structural mismatch via the graphon limit. Stability results for spectral positional encodings are included as a supporting ingredient. Experiments on synthetic and real graphs confirm the decomposition and convert it into concrete rules for choosing source data.

Core claim

Using a graphon-based continuous limit for dense graphs, the paper shows that for both set-based and message-passing tokenizations any Lipschitz backbone admits an explicit decomposition of cross-domain output shift into graph-specific finite-sample approximation terms and an intrinsic, relabeling-invariant domain discrepancy that captures structural mismatch.

What carries the argument

The graphon-based continuous limit together with the resulting decomposition of output shift into finite-sample terms and domain discrepancy.

Load-bearing premise

Graph domains admit a graphon-based continuous limit for dense graphs.

What would settle it

Measure output shifts on families of dense graphs whose graphon limits are known and check whether the observed shifts fail to separate into the predicted finite-sample terms plus a relabeling-invariant discrepancy.

Figures

Figures reproduced from arXiv: 2605.29828 by Aditya Akella, Jiajun Zhu, Pan Li, Peihao Wang, Ying Chen, Yixuan He, Zhangyang Wang.

Figure 1
Figure 1. Figure 1: Size shift. As λ increases, the train–test token￾distribution discrepancy (left axis) decreases monotonically. Let tG(1) , tG(2) be the (discrete) PE token maps on graphs and tW(1) , tW(2) the corresponding graphon PE maps. As￾sume PE stability holds with a uniform constant CPE in the sense that the induced token discrepancies satisfy ∥tG(1) − tW(1) ∥L2 ≤ CPE ε1, ∥tG(2) − tW(2) ∥L2 ≤ CPE ε2, ∥t(W(1))π − tW… view at source ↗
Figure 3
Figure 3. Figure 3: Size shift with GIN. The test error remains U-shaped. Models, training, and metrics. Unless stated otherwise, we use a DeepSets backbone on node tokens and adopt Eig-PE by default (top-k eigenvectors, with k = 32). To demonstrate that the data-centric terms are not tied to a specific backbone, we further include GIN (Xu et al., 2019b) as a message-passing backbone in the following results. We report test e… view at source ↗
Figure 6
Figure 6. Figure 6: Graphon shift. We evaluate the model trained at λ = 0.2 while perturbing the test graphon with increasing perturbation level (larger L2 distance). The training error is essentially zero. 5.4. PE’s Effect on Generalization In this subsection, we analyze how the hyperparameters and eigen-gaps affect the PE-related constants, and how these changes translate into differences in generalization performance. Eig-… view at source ↗
Figure 7
Figure 7. Figure 7: Eig-PE sweep: test error vs chosen k. We evaluate test error with its ID and OOD components versus the Eig-PE dimension k. We set λ = 0.2 and fix the train/test graph dataset. Each point averages 5 independent training runs. The top axis reports the stability proxy log10√ k/ min(eigengap) , indicating that larger k corresponds to smaller minimum eigengaps and less stable tokens. the PE module is trained j… view at source ↗
Figure 9
Figure 9. Figure 9: GIN + Eig-PE: test error vs. k with a message-passing backbone. Mean over 5 independent runs. The GIN backbone exhibits the same qualitative expressivity–stability trade-off as in the DeepSets experiments: small k underfits, intermediate k performs best, and larger k degrades again, especially on the OOD-size subset. The top axis reports log10( √ k/min eigengap), which increases with k and reflects the eig… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims that, under a graphon-based continuous limit for dense graphs together with Lipschitz assumptions on the backbone, both set-based and message-passing tokenizations admit an explicit decomposition of cross-domain output shift into (i) graph-specific finite-sample approximation terms and (ii) an intrinsic, relabeling-invariant domain discrepancy; it further establishes stability guarantees for spectral positional encodings and validates the theory on synthetic and real graphs to guide data curation for graph foundation models.

Significance. If the central decomposition holds under the stated assumptions, the work supplies a data-centric theoretical lens for predicting and improving GFM transfer that is currently missing from the literature. Credit is due for the explicit decomposition separating finite-sample effects from structural mismatch and for the contrasting stability analysis of eigenvector- versus subspace-based PEs.

major comments (2)
  1. [Abstract / theoretical setup] Abstract and theoretical-setup paragraph: the explicit decomposition of cross-domain output shift into finite-sample terms and relabeling-invariant domain discrepancy is derived under the graphon continuous limit that requires edge densities bounded away from zero as n o∞. For the sparse regimes (average degree O(1) or log n) typical of most GFM applications, the appropriate limiting objects differ and the claimed separation need not hold, rendering the decomposition inapplicable to the data regimes the theory is intended to address.
  2. [Abstract] Abstract: the claim that any Lipschitz backbone admits the stated decomposition is presented without an accompanying error-bound or convergence-rate analysis that would quantify how the finite-sample terms behave when the graphon assumption is only approximately satisfied; this gap makes it impossible to assess whether the decomposition remains useful once the dense-graph hypothesis is relaxed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and for highlighting the importance of clearly delineating the scope of the graphon-based analysis. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract / theoretical setup] Abstract and theoretical-setup paragraph: the explicit decomposition of cross-domain output shift into finite-sample terms and relabeling-invariant domain discrepancy is derived under the graphon continuous limit that requires edge densities bounded away from zero as n→∞. For the sparse regimes (average degree O(1) or log n) typical of most GFM applications, the appropriate limiting objects differ and the claimed separation need not hold, rendering the decomposition inapplicable to the data regimes the theory is intended to address.

    Authors: The manuscript already states that the results are obtained under a graphon continuous limit for dense graphs. The decomposition and the separation into finite-sample terms and relabeling-invariant discrepancy are derived precisely in that regime. We will revise the abstract and the opening of the theoretical-setup section to state the dense-graph assumption more explicitly and will add a short paragraph in the discussion section acknowledging that sparse-graph regimes require different limiting objects. This makes the intended scope unambiguous while preserving the contribution for the dense case where the stated separation holds. revision: partial

  2. Referee: [Abstract] Abstract: the claim that any Lipschitz backbone admits the stated decomposition is presented without an accompanying error-bound or convergence-rate analysis that would quantify how the finite-sample terms behave when the graphon assumption is only approximately satisfied; this gap makes it impossible to assess whether the decomposition remains useful once the dense-graph hypothesis is relaxed.

    Authors: The abstract presents the decomposition as holding exactly under the graphon limit (with finite-sample terms already accounting for the distance to that limit). We do not claim quantitative guarantees once the graphon assumption is relaxed. We will revise the abstract to include an explicit qualifier that the result is exact in the limit. A general convergence-rate analysis for approximate graphons lies outside the current technical development; we will note this limitation and flag it as future work in the conclusion. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained under stated assumptions

full rationale

The paper derives an explicit decomposition of cross-domain output shift for Lipschitz backbones under a graphon-based continuous limit assumption for dense graphs. This produces finite-sample approximation terms plus an intrinsic relabeling-invariant domain discrepancy from structural mismatch, for both set-based and message-passing tokenizations. The derivation relies on establishing PE stability guarantees rather than fitting parameters or renaming inputs. No self-citation load-bearing steps, self-definitional reductions, or fitted-input-called-prediction patterns appear in the abstract or claim description; the central result is a mathematical decomposition under explicit assumptions and is independent of the target quantities by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on modeling graph domains via graphon limits and assuming Lipschitz continuity of the backbone; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Graph domains can be modeled via graphon-based continuous limits for dense graphs
    Foundational modeling choice used to obtain the decomposition and relabeling-invariant discrepancy.
  • domain assumption Any backbone is Lipschitz continuous
    Required for the explicit decomposition to hold for set-based and message-passing tokenizations.

pith-pipeline@v0.9.1-grok · 5704 in / 1273 out tokens · 31399 ms · 2026-06-29T08:27:25.558828+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 6 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Graph based anomaly detection and description: a survey

    Akoglu, L., Tong, H., and Koutra, D. Graph based anomaly detection and description: a survey. Data mining and knowledge discovery, 29 0 (3): 0 626--688, 2015

    2015

  3. [3]

    T., Cohn, H., and Zhao, Y

    Borgs, C., Chayes, J. T., Cohn, H., and Zhao, Y. An l^p theory of sparse graph convergence i: Limits, sparse random graph models, and power law distributions. Transactions of the American Mathematical Society, 372 0 (5): 0 3019--3062, 2019

    2019

  4. [4]

    R., Soman, J., Regep, C., Liu, G., Hayter, J

    Gaudelet, T., Day, B., Jamasb, A. R., Soman, J., Regep, C., Liu, G., Hayter, J. B., Vickers, R., Roberts, C., Tang, J., et al. Utilizing graph machine learning within drug discovery and development. Briefings in bioinformatics, 22 0 (6), 2021

    2021

  5. [5]

    S., Riley, P

    Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In International conference on machine learning, pp.\ 1263--1272. Pmlr, 2017

    2017

  6. [6]

    M., Rasch, M

    Gretton, A., Borgwardt, K. M., Rasch, M. J., Sch \"o lkopf, B., and Smola, A. A kernel two-sample test. The journal of machine learning research, 13 0 (1): 0 723--773, 2012

    2012

  7. [7]

    G-mixup: Graph data augmentation for graph classification

    Han, X., Jiang, Z., Liu, N., and Hu, X. G-mixup: Graph data augmentation for graph classification. In Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pp.\ 8230--8248. PMLR, 2022. URL https://proceedings.mlr.press/v162/han22c.html

    2022

  8. [9]

    On the stability of expressive positional encodings for graphs,

    Huang, Y., Lu, W., Robinson, J., Yang, Y., Zhang, M., Jegelka, S., and Li, P. On the stability of expressive positional encodings for graphs. In International Conference on Learning Representations (ICLR), 2024. URL https://arxiv.org/abs/2310.02579

    work page arXiv 2024

  9. [10]

    Convergence and stability of graph convolutional networks on large random graphs

    Keriven, N., Bietti, A., and Vaiter, S. Convergence and stability of graph convolutional networks on large random graphs. In Advances in Neural Information Processing Systems, volume 33, pp.\ 21512--21523, 2020

    2020

  10. [11]

    Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017

    2017

  11. [12]

    L., L \'e tourneau, V., and Tossou, P

    Kreuzer, D., Beaini, D., Hamilton, W. L., L \'e tourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems (NeurIPS), 2021. URL https://arxiv.org/abs/2106.03893

    work page arXiv 2021

  12. [13]

    arXiv preprint arXiv:2202.13013 , year=

    Lim, D., Robinson, J. D., Zhao, L., Smidt, T., Sra, S., Maron, H., and Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. In International Conference on Learning Representations (ICLR), 2022. URL https://arxiv.org/abs/2202.13013

    work page arXiv 2022

  13. [14]

    One for all: Towards training one graph model for all classification tasks

    Liu, H., Feng, J., Kong, L., Liang, N., Tao, D., Chen, Y., and Zhang, M. One for all: Towards training one graph model for all classification tasks. In The Twelfth International Conference on Learning Representations

  14. [15]

    Large networks and graph limits, volume 60

    Lov \'a sz, L. Large networks and graph limits, volume 60. American Mathematical Soc., 2012

    2012

  15. [16]

    Position: Graph foundation models are already here

    Mao, H., Chen, Z., Tang, W., Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang, J. Position: Graph foundation models are already here. In Forty-first International Conference on Machine Learning, 2024

    2024

  16. [17]

    Transferability of graph neural networks: an extended graphon approach

    Maskey, S., Levie, R., and Kutyniok, G. Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63: 0 48--83, 2023

    2023

  17. [18]

    Generalization bounds for message passing networks on mixture of graphons, 2024

    Maskey, S., Kutyniok, G., and Levie, R. Generalization bounds for message passing networks on mixture of graphons, 2024. URL https://arxiv.org/abs/2404.03473

    work page arXiv 2024

  18. [19]

    Gromov--wasserstein distances and the metric approach to object matching

    M \'e moli, F. Gromov--wasserstein distances and the metric approach to object matching. Foundations of computational mathematics, 11 0 (4): 0 417--487, 2011

    2011

  19. [20]

    Graphon neural networks and the transferability of graph neural networks

    Ruiz, L., Chamon, L., and Ribeiro, A. Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33: 0 1702--1712, 2020

    2020

  20. [21]

    All in one: Multi-task prompting for graph neural networks

    Sun, X., Cheng, H., Li, J., Liu, B., and Guan, J. All in one: Multi-task prompting for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.\ 2120--2131, 2023

    2023

  21. [22]

    Equivariant and stable positional encoding for more powerful graph neural networks

    Wang, H., Yin, H., Zhang, M., and Li, P. Equivariant and stable positional encoding for more powerful graph neural networks. In International Conference on Learning Representations (ICLR), 2022. URL https://arxiv.org/abs/2203.00199

    work page arXiv 2022

  22. [23]

    P., Liu, S., Wei, R., and Li, P

    Wang, H. P., Liu, S., Wei, R., and Li, P. Generalization principles for inference over text-attributed graphs with large language models. In Forty-second International Conference on Machine Learning, 2025

    2025

  23. [24]

    Gft: Graph foundation model with transferable tree vocabulary

    Wang, Z., Zhang, Z., Chawla, N., Zhang, C., and Ye, Y. Gft: Graph foundation model with transferable tree vocabulary. Advances in Neural Information Processing Systems, 37: 0 107403--107443, 2024

    2024

  24. [25]

    and Huang, C

    Xia, L. and Huang, C. Anygraph: Graph foundation model in the wild. arXiv preprint arXiv:2408.10700, 2024

    work page arXiv 2024

  25. [26]

    Xu, H., Luo, D., Zha, H., and Duke, L. C. Gromov-wasserstein learning for graph matching and node embedding. In International conference on machine learning, pp.\ 6932--6941. PMLR, 2019 a

    2019

  26. [27]

    How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019 b

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019 b

    2019

  27. [28]

    L., and Leskovec, J

    Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L., and Leskovec, J. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp.\ 974--983, 2018

    2018

  28. [29]

    Yun, S., Jeong, M., Kim, R., Kang, J., and Kim, H. J. Graph transformer networks. In Advances in Neural Information Processing Systems, pp.\ 11960--11970, 2019

    2019

  29. [30]

    R., and Smola, A

    Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and Smola, A. J. Deep sets. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp.\ 3391--3401. Curran Associates, Inc., 2017. URL http://papers.nips.cc/paper/6931-deep-sets.pdf

    2017