Pith. sign in

REVIEW 3 major objections 4 minor 92 references

Toward a Graph Foundation Model: Pre-Training Transformers With Random Walks

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random walks plus shortest-path distances make node neighborhoods fully reconstructible by a Transformer sequence.

desk verdict A strong empirical recipe for cross-domain graph pre-training via random walks, but the advertised theory does not hold as stated. read the letter →

arxiv 2506.14098 v1 pith:PZTKKXXU submitted 2025-06-17 cs.LG cs.AI

Ziyuan Tang , Jie Chen This is my paper · ORCID
classification cs.LGcs.AI
keywords graphfoundationmodelrandomwalkstransformerpre-trainingshortest-pathpositionalencodingcontextpredictionlosstransferlearningrepresentation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks whether a single pre-trained Transformer can act as a foundation model for graphs, analogous to language models for text. Its central move is to represent each node by several random walks through the graph, with a node's position in the sequence given by its shortest-path distance from the root node; this converts graphs of any size and domain into fixed-length ordered sequences. The authors claim this representation is sufficient, not heuristic: Theorem 4.4 states that with $k=\Theta(\max(nr,n^2/r^2))$ walks of length $\ell=\Theta(r)$, the walks plus the distance encodings fully reconstruct the node's $r$-hop ball, and Theorem 4.5 states that the resulting balls are distinguishable by a positive-definite kernel. They pair this with a self-supervised context-prediction loss and show empirically that the pre-trained model transfers across citation networks, knowledge graphs, and molecules, outperforming the strongest graph foundation baseline on seven of eight tasks. If the claims hold, this is a path to label-free pre-training and cross-domain adaptation for graph learning at scale.

What carries the argument

The load-bearing object is the random-walk sequence $\mathrm{seq}(i)=[i_0,i^1_1,\ldots,i^k_\ell]$: $k$ biased random walks of length $\ell$ from a root node, concatenated walk by walk, with the shortest-path distance from the root serving as each token's positional encoding and a dataset-specific virtual token prepended. A per-walk attention mask lets each walk attend only to itself, the root, and the virtual token, cutting the attention cost by about a factor of $k$ while keeping walks as independent structural probes. The mechanism that carries the theoretical argument is the pseudo shortest-path oracle: when a walk has a monotone depth-increasing subsequence, the difference in walk indices equals the true shortest-path distance, so $\Theta(r)$-length walks supply $\Theta(n^2)$ accurate distance estimates for the ball; those estimates are enough, by known bounds, to reconstruct the ball. The pre-training objective is a context-prediction loss that maximizes mutual information between the root representation and averaged $j$-step contexts over all walks while contrasting against other nodes' contexts.

What would settle it

Run the prescribed sampling on bounded-degree graphs (for example, 2D grids and binary trees with a few added edges): take $k=\Theta(\max(nr,n^2/r^2))$ walks of length $\ell=\Theta(r)$ for every node, compute distances from walk-index differences on outward-moving segments, and attempt to reconstruct each $r$-ball. If any ball is not recovered for a graph that satisfies the theorem's assumptions, Theorem 4.4 is false as stated.

Watch

Extended reading notes

Core claim

The discovery is that a Transformer fed with random walks is not just a workable heuristic but is carrying enough structural information to rebuild a node's local graph. For an undirected connected graph with bounded degree, Theorem 4.4 says the ball $B_{u,r}$ with $n$ nodes is fully reconstructible from the concatenated random-walk sequence of Eq. (1) together with the shortest-path distance of every node from the root $u=i_0$, whenever $k=\Theta(\max(nr,n^2/r^2))$ and $\ell=\Theta(r)$. The reconstruction goes through a pseudo shortest-path oracle: on any segment of a walk where distances from the root increase by one at each step, the index difference between two nodes equals their true distance; with enough walks these accurate oracles accumulate, and known graph-reconstruction bounds finish the job. Theorem 4.5 then gives a positive-definite kernel that distinguishes non-isomorphic balls, so the random-walk representation is expressive for node representation learning. Empirically, the paper reports that the pre-trained model beats the strongest existing graph foundation baseline on seven of eight tasks across node, link, and graph levels, and that pre-training on a single domain already transfers to unseen datasets.

Load-bearing premise

The theorem's load-bearing premise is that, with the prescribed walk count and length, every pair of nodes in the ball will appear together in some outward-moving stretch of a walk, so that the walk-based distance estimate equals the true shortest-path distance; the proof bounds only the expected number of such pairs, not the guarantee that all pairs are covered.

Editorial extensions

If this is right

  • A single pre-trained encoder can be adapted to node, link, and graph-level tasks by training only a task head, because all three output types derive from the same per-node random-walk sequences.
  • Graph batching stops being a bottleneck: any graph, from a molecule with tens of atoms to a network with millions of nodes, becomes a set of fixed-length walk sequences that fit a standard Transformer context.
  • The theoretical sufficiency result means the random-walk encoding is a principled tokenizer for graph Transformers, not an ad hoc sampling choice; this justifies using it as the input format in a foundation model.
  • Walks of modest length reach far beyond small-hop neighborhoods, so the model can capture long-range dependencies; the experiments on long-range benchmarks are consistent with that.
  • Transfer experiments indicate that a small representative set of pre-training datasets, or even one domain, already yields strong performance on unseen graph datasets, lowering the data barrier for building graph foundation models.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: if the reconstruction guarantee in Theorem 4.4 can be strengthened from an expected-count argument to a high-probability coverage bound, random walks would become a provably universal tokenizer for graph Transformers, independent of the quality of node text features.
  • A testable extension the authors do not run: pre-train with hand-crafted structural features instead of LLM-generated text features on non-textual graphs, to isolate how much of the cross-domain transfer comes from the random-walk encoding and how much from language-model vocabulary unification.
  • Editorial inference: the per-walk attention mask keeps walks independent, so the model may be blind to correlations between walks; allowing a few cross-walk attention slots in later layers could improve expressivity without restoring full quadratic cost.
  • The context-prediction loss is a hierarchical infomax objective; a natural follow-up is to treat the number of context windows as a scale selector, letting one model serve tasks that need local versus global information.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes RWPT, a Transformer-based graph foundation model that represents each node by multiple biased random walks, encodes the walks with shortest-path-distance positional encodings and per-walk attention masks, and pre-trains with a novel context-prediction contrastive loss. The authors pre-train on ten datasets and adapt to node-, link-, and graph-level tasks, reporting strong cross-domain transfer and few-shot results against ten baselines. The paper additionally claims two theoretical results: that the random-walk sequence plus SP-distance encoding can fully reconstruct an r-ball (Theorem 4.4) and that a positive-definite kernel can distinguish non-isomorphic balls (Theorem 4.5).

Significance. If the theoretical reconstruction claims were sound, the paper would make a substantial contribution to graph foundation models by justifying random-walk sequences as an information-theoretically sufficient input format for Transformer-based graph representation learning. The empirical contribution is strong and carefully executed: the pipeline is specified in detail, hyperparameters are fixed across datasets, results are reported with ten seeds and error bars, and the ablations isolate the contributions of random-walk sampling, the context-prediction loss, edge-feature conditioning, and the attention mask. The cross-domain and few-shot transfer results are internally consistent and demonstrate the practical value of the approach. However, the theoretical section currently overclaims what the proofs establish, and this gap is load-bearing because the abstract and introduction advertise the expressivity analysis as a central contribution.

major comments (3)
  1. [Appendix C.1 (Lemma C.5 and Theorem C.8)] The proof of Theorem 4.4 does not establish that the ball can be "fully reconstructed." Lemma C.5 bounds only the expected number of distinct reliable pseudo-SP oracles (Eqs. 17-21); it provides no coverage guarantee that every node pair in B_{u,r} is included among those oracles, nor a concentration or high-probability argument. Propositions C.6 and C.7 require the actual all-pairs distance/edge structure of the ball, so an expected count of Θ(n^2) distinct pairs is insufficient: many pairs could remain uncovered, and exact reconstruction would fail. The theorem as stated therefore does not follow from the supplied lemmas.
  2. [Appendix C.2 (Theorem 4.5 and Proposition C.9)] Theorem 4.5 is unsupported as written. The proof invokes Proposition C.9, but the cited shortest-path kernel of Borgwardt and Kriegel is not known to be isomorphism-complete; in fact, shortest-path kernels do not distinguish all non-isomorphic graphs with the same shortest-path distance multiset. Moreover, the proof of Theorem 4.5 relies on Theorem 4.4's exact recovery of all SP oracles within a ball, which is itself not established. The claim that a positive-definite kernel distinguishes non-isomorphic balls therefore needs either a different completeness argument or a weakened statement.
  3. [Appendix C.1 (Lemma C.4)] The derivation of the walk count k = O(nr) in Lemma C.4 is not justified. The coupon-collector argument for covering m nodes in a DFS tree yields k = Θ(m log m) walks, and with m ≤ n this gives O(n log n), not O(nr), unless one assumes r ≥ log n, which is not stated or proven. Since this k bound feeds into the complexity expression in Theorem 4.4, the stated Θ(max(nr, n^2/r^2)) complexity is not established by the given reasoning.
minor comments (4)
  1. [Table 1] The column header "GRAPH CLASSI ." appears truncated; it should read "GRAPH CLASSIFICATION."
  2. [Section 5.3] The phrase "a fewN-wayk-shot experiments" contains a typographical error; it should be "a few N-way k-shot experiments."
  3. [Section 3.4 (Eq. 9)] The notation "∀other" in the loss is informal; clarifying that the negative contexts are sampled from other root nodes in the same batch would improve precision.
  4. [Section 5.2] The claim that RWPT outperforms GFT on seven of eight tasks is correct, but it would be helpful to also report the one task where GFT wins (PubMed) in the main text for full transparency.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: empirical results are benchmarked externally and the theoretical claims rest on external reconstruction theorems; the proof gap in Lemma C.5 is a correctness issue, not circularity.

full rationale

No circularity found. The paper's central empirical claim is benchmarked against external baselines (GCN, GIN, GAT, DGI, BGRL, GraphMAE, GIANT, PRODIGY, OFA, GFT), with random-walk and Transformer hyperparameters fixed across datasets (Appendix F: k=8, l=4, p=1.0, q=0.1) and verified by ablations over sampling, loss, and attention mask; no parameter is fit to a test set and then reported as a prediction. The theoretical expressivity claim is an independent argument: Theorem 4.4 proposes that a ball can be reconstructed from the random-walk sequence (Eq. 1) plus SP distances from the root, and its proof relies on external results (Lemma 4.7 of Blum-Hopcroft-Kannan; Propositions C.6/C.7 from Reyzin-Srivastava and Mathieu-Zhou) rather than on the paper's own conclusions. The input includes the SP distance of every node from the root, but that is part of the stated representation, not a fitted output, and it does not by itself determine the edges of the ball; reconstructing edge structure from pairwise oracles is the actual external reconstruction step. The one weakness visible in the proof of Theorem 4.4 - Lemma C.5 gives only an expected count Theta(n^2) of reliable pseudo-SP oracles and does not prove coverage of every pair needed for exact reconstruction - is a correctness/concentration gap, not a circularity: the theorem's conclusion is not equivalent to its assumptions by construction. Theorem 4.5 is likewise a direct application of the cited shortest-path kernel [5] plus Theorem 4.4, with no self-citation chain or ansatz smuggled in. The paper's few self-references (e.g., [9], FastGCN) are not load-bearing for the main claims.

Assumptions & free parameters 5 free parameters · 4 assumptions · 2 invented entities

The empirical method depends on hand-set walk hyperparameters and per-dataset mixture weights; the theoretical reconstruction argument additionally imports distance-oracle reconstruction results and an unsupported kernel expressivity assumption. No new physical entities are introduced; the virtual dataset token is a standard architectural prompt, and the pseudo SP oracle is a proof artifact.

free parameters (5)
  • walk length ℓ = 4
    Set to 4 by default; ablation (Table 8) shows larger ℓ (8) improves Long Range Graph Benchmark results, so the choice is dataset-dependent and made by hand.
  • number of walks k = 8
    Default k=8; ablation varies k from 4 to 16 with no uniform best; hand-chosen.
  • node2vec bias p = 1.0
    Chosen to favor depth over breadth; not derived from theory.
  • node2vec bias q = 0.1
    Chosen to favor outward movement; Lemma C.1's condition (10) requires this kind of bias for linear hitting time, but the value is empirical.
  • dataset mixture multiplier α_D = PubMed 3.0, Products 0.5, WikiCS 2.0, Arxiv 0.7, WN18RR 0.8, FB15k237 0.1, PCBA 0.2, ChEMBL 0.1, HIV 1.0, Tox21 2.0
    Hand-picked to balance dataset sizes in pre-training batches (Section F); affects the pre-training distribution.
assumptions (4)
  • standard math Graph reconstruction from all-pairs shortest-path distances requires Θ(n^2) oracle queries for general graphs, reducible to Θ(n^{3/2}) with randomization (Propositions C.6, C.7).
    Invoked in the proof of Theorem 4.4 without proof; accepted from cited literature [62, 53].
  • domain assumption The input graphs to Theorem 4.4 are undirected, connected, and of bounded degree d.
    Stated in Theorem 4.4; many real graphs (knowledge graphs, molecules) are not connected or have unbounded degree, which limits the scope.
  • ad hoc to paper The biased random walk satisfies 1/q ≥ ((C+1)/(C-1))(1/p) + (1/(C-1))d for some C≥2 (Eq. 10), so the expected walk length to reach distance r is O(r).
    This condition is imposed to make the hitting-time analysis tractable; the paper's chosen p=1.0, q=0.1 is asserted to satisfy it for typical degree d, but it is not derived from data.
  • ad hoc to paper There exists a shortest-path graph kernel that is positive definite, polynomial-time computable, and distinguishes graphs up to isomorphism (Proposition C.9).
    Attributed to [5], but the cited paper does not establish isomorphism-completeness; in fact the shortest-path kernel fails to distinguish graphs with identical distance multisets, so Theorem 4.5 inherits this unsupported premise.
invented entities (2)
  • Virtual dataset token v
    purpose: Prepended to every node sequence to inform the Transformer which dataset or domain a graph comes from (Eq. 2), enabling joint pre-training across domains.
    A learned prompt-like token; no falsifiable prediction outside the paper. Its effectiveness is shown indirectly through cross-domain transfer, but removing it is not separately ablated.
  • Pseudo shortest-path oracle ψ~_w (Eq. 17)
    purpose: A proof device that estimates pairwise distances from random-walk index differences; used in Lemma C.5 to argue that random walks provide enough distance information to reconstruct balls.
    It is an analytical construct, not a model component; its reliability is argued only under strict monotone-depth conditions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Toward a Graph Foundation Model: Pre-Training Transformers With Random Walks." pith.science (2026). https://pith.science/paper/PZTKKXXU

@misc{pith2026250614098,
  author       = {Pith},
  title        = {Pith review of: Toward a Graph Foundation Model: Pre-Training Transformers With Random Walks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PZTKKXXU}},
  note         = {Machine review of arXiv:2506.14098}
}
read the original abstract

A foundation model like GPT elicits many emergent abilities, owing to the pre-training with broad inclusion of data and the use of the powerful Transformer architecture. While foundation models in natural languages are prevalent, can we build similar models for graphs? This paper describes an approach toward a graph foundation model that is pre-trained with diverse graph datasets by adapting the Transformer backbone. A central challenge toward this end is how a sequence model encodes graphs of varying sizes and from different domains. We propose representing a node as multiple random walks, such that the Transformer can extract node representations from sequences, which in turn form edge and graph representations. We develop a novel context prediction loss for these random walks and theoretically analyze their expressive power in distinguishing neighborhoods and graphs. We also demonstrate the pre-training of our model and its adaptation to downstream tasks, showcasing its potential as a foundation for processing and reasoning with graph-structured data.

Figures

Figures reproduced from arXiv: 2506.14098 by the authors.

Figure 1
Figure 1. Pipeline of RWPT. Each node is represented by multiple random walks formulated into one [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Context learning. In our case, we use a per-walk attention mask to improve scalability. See [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Aggregated transfer learning per￾formance. “Best of baselines” denotes the highest score among (semi-)supervised and self-supervised methods. “OOD” (resp. “ID”) indicate that the datasets for pre-training and downstream testing are from the same (resp. different) domain. “Pre-Train w/ THREE” and “Pre-Train w/ ALL” follow the definitions in [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

92 extracted references · 42 canonical work pages

  1. [1]

    Battaglia, Jessica B

    Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zam- baldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre, Francis Song, Andrew Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierst...

    arXiv 2018

  2. [2]

    Foundations of data science

    Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of data science. To appear, 280, 2015

    2015

  3. [3]

    On the opportunities and risks of foundation models

    Rishi Bommasani et al. On the opportunities and risks of foundation models. Preprint arXiv:2108.07258, 2021

    arXiv 2021

  4. [4]

    Translating embeddings for modeling multi-relational data

    Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013

    2013

  5. [5]

    Shortest-path kernels on graphs

    Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM’05), pages 8–pp. IEEE, 2005

    2005

  6. [6]

    Graphllm: Boosting graph reasoning ability of large language model

    Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. Graphllm: Boosting graph reasoning ability of large language model. arXiv preprint arXiv:2310.05845, 2023

    arXiv 2023

  7. [7]

    Structure-aware transformer for graph representation learning

    Dexiong Chen, Leslie O’Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In ICML, 2022

    2022

  8. [8]

    Learning Long Range Dependencies on Graphs via Random Walks

    Dexiong Chen, Till Hendrik Schulz, and Karsten Borgwardt. Learning long range dependencies on graphs via random walks. Preprint arXiv:2406.03386, 2024

    work page Pith review arXiv 2024

Show all 92 references
  1. [9]

    FastGCN: Fast learning with graph convolutional networks via importance sampling

    Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018

    2018

  2. [10]

    NAGphormer: A tokenized graph transformer for node classification in large graphs

    Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: A tokenized graph transformer for node classification in large graphs. In ICLR, 2023

    2023

  3. [11]

    Simple and deep graph convolutional networks

    Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020

    2020

  4. [12]

    Llaga: Large language and graph assistant

    Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.08170, 2024

    2024 arXiv

  5. [13]

    Exploring the potential of large language models (LLMs) in learning on graph

    Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, and Jiliang Tang. Exploring the potential of large language models (LLMs) in learning on graph. In NeurIPS Workshop, 2023

    2023

  6. [14]

    Node feature extraction by self-supervised multi-scale neighborhood prediction

    Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction. In ICLR, 2022

    2022

  7. [15]

    Rethinking attention with performers

    Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In ICLR, 2021

    2021

  8. [16]

    Convolutional 2d knowledge graph embeddings

    Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  9. [17]

    A generalization of transformer networks to graphs

    Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. In AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021

    2021

  10. [18]

    Long range graph benchmark

    Vijay Prakash Dwivedi, Ladislav Rampášek, Mikhail Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In NeurIPS Track on D&B, 2022. 10

    2022

  11. [19]

    Talk like a graph: Encoding graphs for large language models

    Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In ICLR, 2024

    2024

  12. [20]

    Towards foundation models for knowledge graph reasoning

    Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. arXiv preprint arXiv:2310.04562, 2023

    2023 arXiv

  13. [21]

    Predict then propagate: Graph neural networks meet personalized pagerank

    Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019

    2019

  14. [22]

    Chembl: a large-scale bioactivity database for drug discovery

    Anna Gaulton, Louisa J Bellis, A Patricia Bento, Jon Chambers, Mark Davies, Anne Hersey, Yvonne Light, Shaun McGlinchey, David Michalovich, Bissan Al-Lazikani, et al. Chembl: a large-scale bioactivity database for drug discovery. Nucleic acids research, 40(D1):D1100– D1107, 2012

    2012

  15. [23]

    Citeseer: An automatic citation indexing system

    C Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89–98, 1998

    1998

  16. [24]

    Schoenholz, Patrick F

    Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017

    2017

  17. [25]

    node2vec: Scalable feature learning for networks

    Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, 2016

    2016

  18. [26]

    GPT4Graph: Can large language models understand graph structured data ? an empirical evaluation and benchmarking

    Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. GPT4Graph: Can large language models understand graph structured data ? an empirical evaluation and benchmarking. Preprint arXiv:2305.15066, 2023

    2023 arXiv

  19. [27]

    Gutmann and Aapo Hyvärinen

    Michael U. Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. JMLT, 13(11):307–361, 2012

    2012

  20. [28]

    Hamilton, Rex Ying, and Jure Leskovec

    William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017

    2017

  21. [30]

    Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning

    Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning. arXiv preprint arXiv:2305.19523, 2023

    2023 arXiv

  22. [31]

    Unigraph: Learning a cross-domain graph foundation model from natural language

    Yufei He and Bryan Hooi. Unigraph: Learning a cross-domain graph foundation model from natural language. arXiv e-prints, pages arXiv–2402, 2024

    2024

  23. [32]

    Learning deep representations by mutual information estimation and maximization

    R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In ICLR, 2019

    2019

  24. [33]

    Rae, Oriol Vinyals, and Laurent Sifre

    Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osin...

    2022 arXiv

  25. [34]

    GraphMAE: Self-supervised masked graph autoencoders

    Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. GraphMAE: Self-supervised masked graph autoencoders. In KDD, 2022

    2022

  26. [35]

    Open graph benchmark: Datasets for machine learning on graphs

    Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Preprint arXiv:2005.00687, 2020

    2005 arXiv

  27. [36]

    Strategies for pre-training graph neural networks

    Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In ICLR, 2020

    2020

  28. [37]

    PRODIGY: Enabling in-context learning over graphs

    Qian Huang, Hongyu Ren, Peng Chen, Gregor Kržmanc, Daniel Zeng, Percy Liang, and Jure Leskovec. PRODIGY: Enabling in-context learning over graphs. In NeurIPS, 2023. 11

    2023

  29. [38]

    Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei

    Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. Preprint arXiv:2001.08361, 2020

    2001 arXiv

  30. [39]

    Bert: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of naacL-HLT, volume 1. Minneapolis, Minnesota, 2019

    2019

  31. [40]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017

    2017

  32. [41]

    Hamilton, Vincent Létourneau, and Prudencio Tossou

    Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In NeurIPS, 2021

    2021

  33. [42]

    What’s behind the mask: Understanding masked graph modeling for graph autoencoders

    Jintang Li, Ruofan Wu, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang. What’s behind the mask: Understanding masked graph modeling for graph autoencoders. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and...

    2023

  34. [43]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018

    2018

  35. [44]

    Gated graph sequence neural networks

    Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICLR, 2016

    2016

  36. [45]

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

    Hao Liu, Jiarui Feng, Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In ICLR, 2024

    2024

  37. [46]

    Towards graph foundation models: A survey and beyond

    Jiawei Liu, Cheng Yang, Zhiyuan Lu, Junze Chen, Yibo Li, Mengmei Zhang, Ting Bai, Yuan Fang, Lichao Sun, Philip S Yu, et al. Towards graph foundation models: A survey and beyond. arXiv preprint arXiv:2310.11829, 2023

    2023 arXiv

  38. [47]

    Generating Wikipedia by summarizing long sequences

    Peter J Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating Wikipedia by summarizing long sequences. Preprint arXiv:1801.10198, 2018

    2018 arXiv

  39. [48]

    Graphprompt: Unifying pre-training and downstream tasks for graph neural networks

    Zemin Liu, Xingtong Yu, Yuan Fang, and Xinming Zhang. Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. In Proceedings of the ACM Web Conference 2023, pages 417–428, 2023

    2023

  40. [49]

    Zheyuan Liu, Xiaoxin He, Yijun Tian, and Nitesh V . Chawla. Can we soft prompt llms for graph learning tasks? In WWW, 2024

    2024

  41. [50]

    Decoupled weight decay regularization

    I Loshchilov. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017

    2017 arXiv

  42. [51]

    Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim

    Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. In ICML, 2023

    2023

  43. [52]

    Position: Graph foundation models are already here

    Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. Position: Graph foundation models are already here. In ICML, 2024

    2024

  44. [53]

    Graph reconstruction via distance oracles

    Claire Mathieu and Hang Zhou. Graph reconstruction via distance oracles. In International Colloquium on Automata, Languages, and Programming, pages 733–744. Springer, 2013

    2013

  45. [54]

    Automating the construction of internet portals with machine learning

    Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127–163, 2000

    2000

  46. [55]

    Wiki-cs: A wikipedia-based benchmark for graph neural networks

    Péter Mernyei and C˘at˘alina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural networks. arXiv preprint arXiv:2007.02901, 2020

    2007 arXiv

  47. [56]

    Graph-to-graph transformer for transition- based dependency parsing

    Alireza Mohammadshahi and James Henderson. Graph-to-graph transformer for transition- based dependency parsing. arXiv preprint arXiv:1911.03561, 2019. 12

    1911 arXiv

  48. [57]

    Recursive non-autoregressive graph-to-graph transformer for dependency parsing with iterative refinement

    Alireza Mohammadshahi and James Henderson. Recursive non-autoregressive graph-to-graph transformer for dependency parsing with iterative refinement. Transactions of the Association for Computational Linguistics, 9:120–138, 2021

    2021

  49. [58]

    DeepWalk: Online learning of social representations

    Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. DeepWalk: Online learning of social representations. In KDD, 2014

    2014

  50. [59]

    Gcc: Graph contrastive coding for graph neural network pre-training

    Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gcc: Graph contrastive coding for graph neural network pre-training. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pag...

    2020

  51. [60]

    Improving language understanding by generative pre-training

    Alec Radford. Improving language understanding by generative pre-training. OpenAI, 2018

    2018

  52. [61]

    Recipe for a general, powerful, scalable graph transformer

    Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. In NeurIPS, 2022

    2022

  53. [62]

    Learning and verifying graphs using queries with a focus on edge counting

    Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In International Conference on Algorithmic Learning Theory, pages 285–297. Springer, 2007

    2007

  54. [63]

    DropEdge: Towards deep graph convolutional networks on node classification

    Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep graph convolutional networks on node classification. In ICLR, 2020

    2020

  55. [64]

    GPPT: Graph pre-training and prompt tuning to generalize graph neural networks

    Mingchen Sun, Kaixiong Zhou, Xin He, Ying Wang, and Xin Wang. GPPT: Graph pre-training and prompt tuning to generalize graph neural networks. In KDD, 2022

    2022

  56. [65]

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

    Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan. All in one: Multi-task prompting for graph neural networks. In KDD, 2023

    2023

  57. [66]

    Walklm: A uniform language model fine-tuning framework for attributed graph embedding

    Yanchao Tan, Zihao Zhou, Hang Lv, Weiming Liu, and Carl Yang. Walklm: A uniform language model fine-tuning framework for attributed graph embedding. Advances in neural information processing systems, 36:13308–13325, 2023

    2023

  58. [67]

    Graphgpt: Graph instruction tuning for large language models

    Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 4...

    2024

  59. [68]

    Dyer, Rémi Munos, Petar Veliˇckovi´c, and Michal Valko

    Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Veliˇckovi´c, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In ICLR, 2022

    2022

  60. [69]

    Chawla, and Panpan Xu

    Yijun Tian, Huan Song, Zichen Wang, Haozhu Wang, Ziqing Hu, Fang Wang, Nitesh V . Chawla, and Panpan Xu. Graph neural prompting with large language models. In AAAI, 2024

    2024

  61. [70]

    Llama 2: Open foundation and fine-tuned chat models

    Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023

    2023 arXiv

  62. [71]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, 2017

    2017

  63. [72]

    Graph attention networks

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018

    2018

  64. [73]

    Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm

    Petar Veliˇckovi´c, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019

    2019

  65. [74]

    Can language models solve graph problems in natural language? In NeurIPS, 2023

    Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In NeurIPS, 2023

    2023

  66. [75]

    GFT: Graph foundation model with transferable tree vocabulary

    Zehong Wang, Zheyuan Zhang, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. GFT: Graph foundation model with transferable tree vocabulary. In NeurIPS, 2024. 13

    2024

  67. [76]

    Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus

    Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus. Emergent abilities of large language models. I...

    2022

  68. [77]

    NodeFormer: A scalable graph structure learning transformer for node classification

    Qitian Wu, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. NodeFormer: A scalable graph structure learning transformer for node classification. In NeurIPS, 2022

    2022

  69. [78]

    Wright, Azalia Mirhoseini, Joseph E

    Zhanghao Wu, Paras Jain, Matthew A. Wright, Azalia Mirhoseini, Joseph E. Gonzalez, and Ion Stoica. Representing long-range context for graph neural networks with global attention. In NeurIPS, 2021

    2021

  70. [79]

    Moleculenet: a benchmark for molecular machine learning

    Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9(2):513–530, 2018

    2018

  71. [80]

    Opengraph: Towards open graph foundation models

    Lianghao Xia, Ben Kao, and Chao Huang. Opengraph: Towards open graph foundation models. arXiv preprint arXiv:2403.01121, 2024

    2024 arXiv

  72. [81]

    How powerful are graph neural networks? In ICLR, 2019

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019

    2019

  73. [82]

    Revisiting semi-supervised learning with graph embeddings

    Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40–48. PMLR, 2016

    2016

  74. [83]

    Do transformers really perform bad for graph representation? In NeurIPS, 2021

    Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform bad for graph representation? In NeurIPS, 2021

    2021

  75. [84]

    Graph contrastive learning with augmentations

    Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurIPS, 2020

    2020

  76. [85]

    Hierarchical graph transformer with adaptive node sampling

    Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. Hierarchical graph transformer with adaptive node sampling. In NeurIPS, 2022

    2022

  77. [86]

    All in one and one for all: A simple yet effective method towards cross-domain graph pretraining

    Haihong Zhao, Aochuan Chen, Xiangguo Sun, Hong Cheng, and Jia Li. All in one and one for all: A simple yet effective method towards cross-domain graph pretraining. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 4443–4454, 2024

    2024

  78. [87]

    Gophormer: Ego-graph transformer for node classification

    Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yan- fang Ye. Gophormer: Ego-graph transformer for node classification. Preprint arXiv:2110.13094, 2021

    2021 arXiv

  79. [88]

    Graphtext: Graph reasoning in text space

    Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoning in text space. arXiv preprint arXiv:2310.01089, 2023

    2023 arXiv

  80. [89]

    Hierarchical transformer for scalable graph learning

    Wenhao Zhu, Tianyu Wen, Guojie Song, Xiaojun Ma, and Liang Wang. Hierarchical transformer for scalable graph learning. In IJCAI, 2023

    2023

  81. [90]

    Deep graph contrastive representation learning

    Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. Preprint arXiv:2006.04131, 2020

    2006 arXiv

  82. [91]

    Graph contrastive learning with adaptive augmentation

    Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, 2021. 14 Contents 1 Introduction 1 2 Related work 3 3 Methodology 3 3.1 Random-walk representation of nodes . . . . . . . . . . . . . . . . . . . ...

    2021

  83. [92]

    and RNGTr [57] adapt Transformers to handle graph-structured input and output in dependency parsing tasks. Although not originally designed for general graphs, these models incorporate structure- aware mechanisms that capture local connectivity within sequential input, typical...

  84. [93]

    PAPER TITLE AND ABSTRACT:

    (20) Letpf = 1− 1/r by tuning the biased random walk. Then we have: E[nSP ]≈ 1 4(r + 1)2 = Θ(r2), (21) which leads to the conclusion given the assumptions. In practice,k can often be much smaller, particularly when the graph is sparse or far from complete. For instance, in a 2...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.