Generative Graph Pattern Machine
Authors: Zehong Wang
Zheyuan Zhang
Tianyi Ma
Chuxu Zhang
Yanfang Ye
Venue: NeurIPS 2025 poster ()
Keywords: Generative Pre-Training
Graph Transformer
Substructure
Scalability
Primary area: deep_learning
TL;DR: We treat substructures as graph tokens to enable the scale transformer pre-training on graphs.

Abstract: Graph neural networks (GNNs) have been predominantly driven by message-passing, where node representations are iteratively updated via local neighborhood aggregation. Despite their success, message-passing suffers from fundamental limitations---including constrained expressiveness, over-smoothing, over-squashing, and limited capacity to model long-range dependencies. These issues hinder scalability: increasing data size or model size often fails to yield improved performance. To this end, we explore pathways beyond message-passing and introduce Generative Graph Pattern Machine (G$^2$PM), a generative Transformer pre-training framework for graphs. G$^2$PM represents graph instances (nodes, edges, or entire graphs) as sequences of substructures, and employs generative pre-training over the sequences to learn generalizable and transferable representations. Empirically, G$^2$PM demonstrates strong scalability: on the ogbn-arxiv benchmark, it continues to improve with model sizes up to 60M parameters, outperforming prior generative approaches that plateau at significantly smaller scales (e.g., 3M). In addition, we systematically analyze the model design space, highlighting key architectural choices that contribute to its scalability and generalization. Across diverse tasks---including node/link/graph classification, transfer learning, and cross-graph pretraining---G$^2$PM consistently outperforms strong baselines, establishing a compelling foundation for scalable graph learning. The code and dataset are available at https://github.com/Zehong-Wang/G2PM.

Generative Graph Pattern Machine
Zehong Wang', Zheyuan Zhang', Tianyi Ma', Chuxu Zhang?, Yanfang Ye "University of Notre Dame, UUiiversity Connecticut *Corresponding Author
<zwang43, yye7>dnd.eee .dd
Abstract
Graph neural networks (GNNs) have been predominantly driven by message- passing, where node representations are iteratively updated via local neighbor- hood aggregation. Despite their success, message-passingg suffers from funda- mental iinitiooon--nnudiinn constrained expressiveness, over-smoothing over- squashing, and limited capacity model long-range dependencies. These issues hinder scalability: increasing data size or model size often fails to yield improved performance. To this end, explore pathways beyond message-passinn passing and introduce Generative Graph Pattern Machine (G²PM), a generative Transformer pre-training framework for graphs. G7PM represents graph instances (nodes, edges, or entire graphs) as sequences substructures, and employs generative pre-training over the sequences learn generalizable and transferable representations. Em- pirically, G2PM demonstrates strong scalability: on the ogbn arxiv benchmark, it continues improve with model sizes up 60M parameters, outperforming prior generative approaches that plateau at significantly smaller scales (c.g., 3M). addition, we systematically analyze the model design space, highlighting key architectural choices that contribute to its scalability and generalization. Across diverse tasks including node/link/graph classification, transfer learning, and cross- graph pretraining GM consistently outperforms strong baselines, establishing a compelling foundation for scalable graph learning. The code and dataset are available at https:::/// // thub. com www. /ee////Zoonngggggege Daaan/G2P!!
(a) Textual Generative Modeling via Word Sequence
(c) Graph Generative Modeling Substructure Sequence (Ours)
The
dog
set
The dog sat the mat.
mat
Transformer (GPT, BERT, LLaMA, etc.)
(b) Visual Generative Modeling via Patch Sequence
Graph Pattern Transformer (GPPM)
Substructure
Visual Transformer (VIT, VOGAN, etc.)
Tokenizer
Figure 1: Generative Transformer pre-training across modalities. (a) Textual modeling tokenizes
language into word sequences and generates next tokens masked tokens. (b) Visual modeling slices images into patches and models generation raster order. (c) Graph modeling (ours) tokenizes graph instances into substructure sequences using random walk-based substructure tokenizer, and leams to generate via masked substructure modeling, going beyond message- message-passing.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Arxiv (# Nodes 169,343)
Products
Arxiv (# (oNee 169,343)
(# Nodes 2,449,029)
OURS
SOTA Generative Graph Pretraining Method
Accuracy (%)
CCN
GraphMAF
80
Accuracy (%)
DGI
71
70
Node2ves
BGRL
79
VGAE
--- Ourr
- Ours
GraphMAE BGRL
GraphMAB
0.5M
30M
60M
BGRL
Million
1%
5%
10%
50%
100%
1%
5%
10% 50% 100%
Number of Parameters
Pretraining Data Ratio
Figure 2: Model scaling behavior on the ogbn-arxiv with linear probing. G con- sistently improves as model parameters increase, achieving 72.31% accuracy with 60M parame- ters ters- surpassing the current SOTA generative graph pre-training method [23]. In contrast,
Figure 3: Data scaling behavior on the ogbn-arxiv and ogbn-products with linear probing. GPPM demonstrates robust improve- ments with more pre-training data, reflecting su- perior scalability. In contrast, GraphMAE [22] and BGRL (53) peak at small data ratios and degrade with more data, suggesting overfitting, poor regularization, inefficient data utilization.
GraphMAE [22] and BGRL [53] exhibit perfor-
mance degradation, indicating limited scalability.
1 Introduction
Transformer architectures 559 have emerged as the cornerstone of modern foundation models 73 (57) Enabled by generative pre-training on massive unlabeled corpora 1722), Transformers learn transferable representations that can be efficiently adapted to diverse downstream tasks. This paradigm shift has redefined the landscape of machine learning, powering state-of-the-art systems in natural language processing and computer vision. Prominent examples include large language models (LLMs) 2 15 and Vision Transformers (ViTs) [3] which showcase the scalability and generalization strength of this approach.
Despite the transformative success of generative Transformer pre-training in text and vision domains, this paradigm has yet to bring comparable breakthroughs in the graph domain, posing a significant barrier the development of graph foundation models [40 65 [7]. Most existing approaches to
graph pre-training remain grounded in message-passing graph neural networks (MPNNs) 33 60 16
18 39 which known suffer from fundamental limitations: constrained expressive power (77).
over-smoothing [49]. over-squashing [56), and poor capacity for modeling long-range dependencies
47]. These challenges significantly limit the scalability of MPNNs [43] where increasing the size of the model or training data does not reliably lead to improved performance. As a result, the emergence of scaling laws in graph learning critical property in the success of foundation models 2 elusive. Moreover, current graph pre- pre-training techniques are predominantly based on contrastive learning 46
75 76
38 which has been shown be less capable
of learning generalizable semantic representations compared to generative objectives (20 12 54 5
This reliance further compounds the scalability bottleneck of graph neural networks (GNNs).
In this work, we aim to extend the success of Transformer-based generative pre-training to the graph domain, with the goal of enabling scalable graph representation learning. We consider the effectiveness of Transformers stems from a common principle: Transformer-based models represent instances using sequences of high-level semantic tokens, and apply generative objectives for pre-training. To realize this paradigm for graphs, we begin by identifying three fundamental challenges that distinguish graph-structured data from Euclidean modalities such text and images. (1) Absence of Sequence Structure: Unlike text or images, which naturally possess ordered or grid-like sequences compatible with Transformer training, graphs lack sequence (no matter ordered or unordered) for nodes, edges, or subgraphs. This complicates the adaptation of Transformer. (2) Semantic Granularity: Graph elements
as nodes or edges-typically encode low-level semantics, while tokens in language (i.e., words) or vision (i.e., patches) often correspond to higher-level concepts. is unclear whether Transformers can effectively learn from such low-level representations in a generative fashion. (3) Scalability Bottlenecks: Existing Graph Transformers

---

(GTs) [3, 9 14] often treat individual nodes tokens and focus on pairwise relationships, leading to sequence lengths that scale with the number of nodes. Due the quadratic time complexity of Transformers [29] this design choice limits scalability to large graphs, confining GT's primarily to small graphs such as molecular graphs
These challenges naturally raise a central question: how can we define sequences of high-level semantic tokens that meaningfully represent a graph instance-whether a node, an edge, or an entire graph? To answer this, we revisit the core objective of graph learning: understanding key substructures that are predictive of downstream tasks. In many domains, such substructures are inherently semantic. For instance, motifs like triangles in social networks capture stable interpersonal relationships, while benzene rings in molecular graphs encode chemical stability- both serving as informative building blocks for reasoning. Motivated by this intuition, we propose to represent graph instances as sequences of meaningful substructures (Figure and introduce the Generative Graph Pattern Machine (G²PM), Transformer- heasedede----d generative pre-training framework for graphs. G tokenizes graphs into sequences of substructures via random walks, and learns representations by reconstructing masked substructures from context. This approach enables the design of pure Transformer models for graphs-free from pastangg-asing---- woisl while unlocking scalability through increased model capacity and data volume (Figures 2 and 3p. We highlight our contributions:
We propose G2PM, generative Transformer vre-training framework that models graph instances as sequences of substructures, entirely eliminating the need for message passing.
We introduce a random baske tokenizer that efficiently extracts semantic substructure patterns, and pair it with masked substructure prediction task enable self-supervised learning.
We conduct a comprehensive design space exploration, offering actionable insights into model architecture and scalability.
We demonstrate that G2PM scales effectively: increasing data model size yields consistent performance gains, echoing the scaling behaviors observed in other domains.
We validate G across multiple benchmarks, showing state-of-the-art performance on node/link/graph-level tasks, along with strong generalization in cross-graph transfer tasks.
Outlook. While Transformers have redefined learning paradigms in many domains, their influence on graph learning remains nascent. We hope this work sparks further exploration into non-message- passing architectures, especially Transformers, as a new foundation for graph representation learning.
2 Generative Graph Pattern Machine
Let G = (V,E, X, E) denote graph, where V is the set of nodes with \V] = N, & V is the set of edges with [ = E, and X and represent the node and edge feature matrices, respectively.
Each node v E V is associated with a feature vector x, E R and each edge e E E is associated with feature vector Rd (when applicable). As illustrated in Figure G2PM is pre-trained using a masked substructure modeling (MSM) objective in fully self supervisedd fashion.
2.1 Graph Representations
Our core idea to represent any graph instance (node, link, or graph) as a sequence of substructures. In natural language, sequences are constructed using predefined vocabulary of words subwords; in vision, raster-scan tokenizers divide images into patch sequences. However, extending this notion of tokenization to graphs poses two key challenges. First, it is non-trivial to define universal vocabulary of graph substructures, as the semantic relevance of patterns is highly domain-specifii For example, triangle motifs prominent in social networks, whereas ring structures are more meaningful molecular graphs. Second, tokenizing graphs by substructure matching incurs high computational cost: subgraph isomorphism is NP-complete [15], rendering it impractical for large- scale
when compared to the linear-time tokenization of text and images [51 [3].
Tokenizer. To overcome these challenges, we adopt random walk-based tokenizer that samples substructure patterns on the fly, bypassing the need for a predefined vocabulary. This strategy offers an efficient and scalable tokenization mechanism 688 81]. As illustrated in Figure 4b.. random
3

---

(a) Pre- rre-Trainin Generative Graph Pattern Machine (GPPM)
Tokenizing Substructures via Random Walks
Target
EMA Encoder
Subsimeture Embedding
Substructure Patierns
Reconstruct
Sequential Model (Transformer, RNN, etc)
Tokenize
(b)
GPPM Decoder
Equals
Graph
htu
hg
Concat
Add Mask Token
Masking
[4]
Randem Mask
ltg
Extract
2
Masked Putten
[M]
Mask Token
GPPM Encoder
Randon
Hidden State
Flatten
Node Feanure
Reconstruction
[M]
Visible Tokens
Ddge Fearure
Figure 4: Overview of G2PM pre-training. (a) Given a graph instance, we first apply a random walk-based tokenizer to extract substructure patterns. Some patterns are randomly masked and the visible patterns are fed into a G2PM encoder. The encoder outputs are concatenated with special mask tokens and passed substructures by performing random walks over the graph, where each walk represents a substructure, which is proved to be effective 68 The substructure embeddings modeled via Transformer.
G2PM decoder to reconstruct the masked substructures. (b) We tokenize
walk such as [1, 1, 4, 3) corresponds to diamond Saamnd-shapped substructure. Formally, we define an unbiased random walk of fixed length L sequence sampled from Markov chain:
v.) = 1[(0,, u(41) E E
P(u+41 v.,...,,y)
(I)
D(m))
where ((v;) denotes the degree of node v,. This transition probability enables efficient generation of node sequences from arbitrary starting points.
For each graph instance, sample k random walks to serve substructure patterns. To balance lo- cality and global context, we leverage unbiased sampling strategies [44] 68]. Rather than constructing
explieit subgraphs from these walks, treat each as node sequence and directly encode it using Transformer, which has been shown to effectively capture structural inductive biases in graphs [68].
Given node sequence w [x1, (i..... Xm.. we compute its embedding via Transformer encoder f:
p = f(w) f(h hm)); h; = Wx; + b,
where p is the substructure embedding, and x; = [x:||e]] is the concatenation of node feature and (optionally) edge feature c,.
Eliminating Message-Passing Bottlenecks. Our tokenizer is entirely message-passing-fes allowing GPPM to bypass key limitations of traditional GNNs. Notably, the random walk-based representations
in G effectively capture long-range dependencies 68 27). exceed the expressiveness of 1-WI.
tests 55 69 42).
and mitigate over-smoothing and over-squashing effects [61].
No Positional Embeddings. Unlike standard Transformers, which depend on positional encodings, we find that adding position information to node sequences offers no consistent benefit (Table [b] and incurs cubic time complexity 34 We thus omit positional embeddings entirely, simplifying the architecture without compromising performance.
Task-Ag Tokenization. Our tokenizer is applicable across graph-based tasks. For node-level tasks, random walks originate from the target node; for edge-level tasks, from the endpoints of target edge; and for graph-level tasks, from randomly sampled nodes in the graph. This task-agnostic design enables G PM to adapt seamlessly without requiring specialized modifications.

---

2.2 PM Backbone
We adopt the standard Transformer architecture [59] as the backbone for both G2PM encoder and de- coder. The input to the Transformer is a sequence of graph substructure tokens P = [pI. P2...... pal where each P, denotes the embedding a sampled substructure. A single Transformer layer operates via a combination of self-attention and feed-forward networks, formally defined as:
QQK
P' FFN (P + Attn(P)), APt softmax
V E Ruxd,
(3)
V
Q = PWQ. K PWK. V
(4)
where Wo. WK. Wv are learnable projection matrices and dout denotes the dimensionality of the output embeddings. The FFN is implemented as a two-layer multilayer perceptron with non-linearity, Following standard practice, we employ multi-head sell-attention [59], where multiple attention mechanisms are applied in parallel and their outputs concatenated. We stack multiple Transformer layers to enhance model capacity. We denote the output of the final (L-th) Transformer layer as representing the learned contextualized embeddings of graph substructures.
p'. = Ip'.P2
2.3 Pre-Training G2P Masked Substructure Modeling
To pre-train the G2PM model, we introduce a generative Transformer objective masked substructure modeling (MSM). Given sequence of substructures extracted from graph, we randomly mask subset and train the model to reconstruct the masked substructures conditioned on the visible ones. This process follows the conditional factorization principle used in masked language modeling [12
p(11, ,2....,,,, xn) = p(z/M) II p(z, I/M),
(5)
TEM
where z/Ms denotes the set of visible tokens and M indicates the masked positions.
The key intuition that meaningful graph substructures exhibit strong interdependencies- such as hicrarchical relationships, functional reinforcement, or functional exclusion (Appendix allloooinng certain substructures to predictive of others. Concretely, given tokenized substructure sequence P = Pp..... p. we randomly retain k visible tokens to form P Pvis. while masking the remaining n 1 tokens. The visible sequence Pvis is passed through the GPPM encoder to produce contextual embeddings H We then insert learnable mask tokens at the masked positions to recover the full- length sequence, and feed the sequence into the G decoder for reconstruction R [ri,..., rn]]:
R- Decoder(H), H Addpa (Huis); H Encoder(P) Pris).
(6)
To define the reconstruction targets, we leverage the high-level semantics of substructures. Instead of reconstructing low-level node features or adjacency matrices, we employ an online encoder fEMA. an exponential moving average (EMA) version of the substructure encoder, to generate target embeddings p.- = SEMA (w;) for each substructure walk wy. This yields the training objective:
1 Σ is masked(p:). ||r:- sglp.112. ps = (w:),
L
where is (-_nasked(()) is an indicator function for masked positions, and sg|-] denotes the stop-gradien operator, ensuring that targets are fixed during training.
Adapting to Downstream Task. For downstream tasks, discard the decoder and append linear prediction head to the G2PM encoder. Each graph instance is tokenized into a sequence of substructure embeddings P = [pi, P2,.... .h.....P... Pu). which is processed by the L--ayer encoder to produce contextual representations p4 = [pf,....,p. [.]. We then apply mean pooling followed by the task head for final prediction & = Head (1 E.E1P!) p
Augmenting Substructure Patterns. To improve robustness and representation quality, we adopt mixed augmentation strategy inspired by corruttion-annosticc pre-training (20] 71). We define four augmentations in two categories: Feature-level (1) feature masking (zeroing subset of features) and (2) node masking (masking entire nodes); and Structure-level (3) substructure corruption (dropping nodes within walk) and (4) substructure injection (replacing walk nodes with random nodes). During training, we apply one feature-level and one structure-level augmentation per instance to promote generalization across diverse perturbations.
5

---

Dim
Params
Arxiv
HIV
Encoder
Arxiv
HIV
[(ask]
Arxiv
HIV
64
~0.4M
68.2
69.7
Learnabee
72.3
78.7
128
~1.5M
70.5
GRL
63.4
72.3
Fixed
71.8
76.9
256
~62M
71.2
74.1
GIN
71.0
73.2
Random
67.6
71.6
512
~26.6M
72.1
76.4
168
6615M
72.3
78.7
Node PE
72.4
78.6
Sampling
67.1
74.0
(a) Model dimension. G²PM hibits strong scalability with in- creased hidden dimension sizes.
(b) Tokenization. Transformer is the most expressive encoder for modeling substructures.
(c) Mask token. Using learnable mask token Icads to higher accu- racy compared to other tokens.
Aug.
Case
Arsiv
HIV
Update Every
Arsdv
EMA Finb.
72.3
78.7
Feature 0.2
Feat. (mess)
71.4
73.5
0.99
Node
Feol. (cuncal)
71.2
64.0
Subsimacure comupp 0u
71.3
74.4
0.99
5
72.2
78.1
Substracture inject 0.8
72.1
72.4
12
72.3
0.99
20
72.3
76.6
Nove
70.5
739
Topo. Recon.
we EMA Uparee
25.2
69.1
(d) Data augmentation. Mixed augmentation significantly im- proves downstream performance.
(c) Reconstruction target. High- level target is more effective than feature-level reconstruction.
(I) Online encoder. Maintaining an EMA-updated online encoder is crucial in generating targets.
Table 1: GM ablation experiments on ogbn-arxiv and HIV. We report linear probe accuracy (%) and use gray to indicate default settings. The detailed pypee-parameters are Appendix
Dec.
3 Design Spaces and Insights
MAE
7..IM
~7.M
71.1
75.9
MAE
~14.2M
~7.1
72.2
77.6
MAF
~21
~7.M
72.3
78.7
We conduct comprehensive ablation study to provide more insights about the model design.
MAE
~21.
~14.2M
72.0
71.9
SimMIM
~21.3M
-06
71.1
74.7
SimMIM
-21.M
(a) Model architecture. Our G2PM design (MAE-style
3.1 Model Architecture
20 outperforms SimMIM-style 71 pre-training.
Model Dimension. We set the default hidden dimension to 768, with a 3-layer encoder and a I-layer decoder. As shown in Table Ta in- creasing model size consistently improves per- formance, mirroring scaling trends observed in language and vision domains 7 13.. Unlike message-passing models that often plateau with scale, GPPM continues benefit from increased parameterization.
72
Accuracy
Masking Ratio
20%
40%
100%
(b) Masking ratio. A large masking ratio leads to better performance with challenging tasks.
Figure 5: More PM ablation experiments.
5a shows that deeper encoders enhance performance, while increasing decoder capacity provides limited or negative returns, particularly under the MAE-style masked modeling framework. We attribute this to the simplicity of substructure reconstruction, where expressive decoders can lead to overfitting. Replacing the MAE-style design [20] with a SimMIM-style variant [71] further degrades performance. This suggests that MAE-style sparsity encourages the encoder to learn stronger context-aware representations, which better align with the inductive bias of graph data.
Model Layer. Table 5a
3.2 Reconstruction Target
Target. By default, GPPM reconstructs the semantic embedding of each masked substructure generated by an EMA-updated encoder. As shown in Table Te this choice consistently yields the strongest performance, supporting our hypothesis that substructures encode transferable semantic information. We compare this approach to two low-level alternatives. Specifically, we represent cach substructure node sequence = [zi...., J. where each node and optional edge features. We experiment with (I) mean-pooling the node features over the exeerimmon
l is the concatenation of
walk, and (2) concatenating them directly. Both approaches underperform the semantic embedding target, suggesting that low-level supervision lacks the abstraction necessary for graph generalization.
Loss. We also evaluate the impact of loss functions. Replacing & loss with & leads to a notable drop graph classification accuracy, suggesting that outlier-sensitive objectives better capture nuanced substructure semantics. Additionally, we incorporate anonymous walks (24) following Wang et al. 688, using a parallel head to reconstruct topological patterns. This auxiliary objective consistently boosts performance, reinforcing the utility of substructures fundamental modeling units.

---

Online Encoder. We ablate the momentum and update the frequency of the EMA encoder (Table Our default setting (a 0.99, update every 10 steps) performs best. Lower momentum values degrade performance, with a 0 (i.e., no EMA) leading to divergence and collapse, highlighting the importance of stable, slowly evolving targets during training.
3.3 Tokenization
Substructure Encoder. To embed substructure sequences (e.g., random walks), adopt a Trans- former encoder, which models global dependencies among all nodes in the sequence. As shown in Table Transformer outperforms alternatives such mean pooling, GRU [[]] and GIN [73]. We attribute this to several factors: (1) mean pooling is a restricted, less expressive form of attention in Transformer; (2) GRUs suffer from optimization instability due to vanishing or exploding gradients [8] and (3) using GIN requires converting walks into subgraphs, reintroducing message- message-passing and its known limitations.
Positional Embedding. We also explore adding positional embeddings (PEs) to node features using Laplacian PE ogbn-arxiv and random walk PE ogbg-HIV [47). However, we observe no consistent performance gain. This may be due to the tokenization scheme: since each token represents an entire substructure, global node positions are less relevant. Moreover, computing PEs incurs cubic time complexity in the node number [34), making them impractical for large-scale graphs.
3.4 Augmentation
Table Id reports the impact of various augmentation strategies. In general, augmentation improves performance, with the mixed strategy yielding the best results, highlighting the value of combin- ing perturbations from different perspectives. We further analyze individual augmentation types. Among feature-level augmentations, node masking outperforms feature masking, likely because re- constructing full-node semantics from context is more challenging- thus more informative- recovering masked dimensions. For structure-level perturbations. substructure corruption performs better on graph-level tasks (e.g.. molecular graphs), while substructure injection is more effective on node-level tasks (e.g., academic networks). This distinction stems from how each augmentation impacts semantics: corruption distorts but retains the original context, whereas injection alters sub- structure identity, which may hurt graph-level tasks where substructure semantics are functionally meaningful. Notably, using only a single augmentation type yields limited improvements, reinforcing the importance of diversity in corruption strategies for generalizable representation learning.
3.5 Masking
Masking Ratio. Figure 5b shows that high masking ratio consistently improves performance, echoing trends observed in vision (20). This is likely because random walks often produce redundant or noisy substructures. High masking reduces such redundancy, resulting in a more challenging and informative learning signal that encourages the model to capture high-level semantics.
The choice of masking token significantly affects performance (Table Ic). By default, we use a single learnable mask token, which outperforms alternatives. Fixed tokens degrade performance due to their inflexibility, while random tokens sampled embeddings from other substructures introduce noise that confuses the model. These findings suggest that a consistent, learnalle mask token provides the strongest and cleanest supervision signal during reconstruction.
Masking Token.
Comparisons to State-of-The-Art Models
Node Classification on homophily graphs. We evaluate GPPM on suite of homophily graphs of varying scales, including Pubmed, Photo, Computers, WikiCS, Flickr, ogbn-arxiv, and egbn-product (see Table [ for dataset statistics). Pre-training conducted on the full graph. We adopt linear probe setup: node embeddings are frozen after pre-training and used to train a separate classifier, where we take 10/10/80 random split for Pubmed, Photo, and Computers, and the official split for the remaining datasets. Accuracy is used as the evaluation metric. We compare GPPM to supervised
GAT 60) non-message-pastee GPM (8]. contrastive methods (GCA BGRL
53, CCA-SSG
78 and generative methods (GraphMAE [22. GraphMAE 23 S2GAE [52] Bandana (82).
7

---

Table Node classification results on homophily graphs. Boldface and underline indicate the best and sub-best self- supervuper methods, and A.R. is the average ranking.
Pubmed
Photo
Computers
WikiCS
Flickr
Arxiv
Products
A.R.
Nodes Edges
19,717
7,650
13.752
11,701
89,250
169,343
2,449.029
88,648
238,162
491,722
431,206
899,756
2,315,598
123.718,024
Supervised
GAT 60
83.1 0.3
87.9
76,9
50.7 +
72.10 0.13
79.45 +
5.7
GPM 68
= 0.1
0.3
90.0 0.4
5 8.4
0.2
72.89 a 0.68
82.62 a 0.39
1.3
GCA 84
83.3 0.5
0.2 22
4.1 1,1
71.23
0.09
0.00
6.9
Contrastive
BGRL 53
8.3
02
8.2
492 0.8
70.51 + 0.03
18.59
5.7
CCA-S3G 78
818
0.6
0.3
75.3 0.8
71.24 4.2
0.20
15.27
8.6
GraphMAF
8..0=055
9.3
77.1 0.5
71,35 0.1
+
GraphMAB
22
01
9.24
8.9
0.
0.1
71.89 + 0.03
0.003
5,4
Generative
S2GAF 52
80.1=005
9..4+001
0.1
0.8
48.1 0.8
67.77 + 0.36
76.70+0.000
10.3
Bandana
0.5
0.7
87.7
0.2
0.3
4.6
71.09 + 0.24
77.
0.05
8.1
GMPM wio Pretrain
0.2
92.8 0.2
0.3
78.5
50.7
69.64 = 0.08
76.90 0.16
6.0
PPM
8..3
92.9 0.2
88.8 0.3
51.0 0.4
0.0
72.31 + 0.07
80.56 0.01
2.0
Chameleon
Actor
Pokec
(# Nodes = 2,277)
(# Nodes 7.600)
(# Nodes = 1,632,803)
34
76
Accurscy
73
Accuracy
32
72
74
Finctuning pretesined model
GraphMAE
GraphMAE
GaptiMA
71
Training from the sentch
50
Ours
72
500
1000
Epochs
Receptive Field Size
Figure 6: Convergence curves under fully finetuning on Arxiv dataset. We compare training from scratch versus fine-tuning the pre-trained model.
Figure 7: Node classification results on heterophily graphs under varying receptive field sizes. For GraphMAE, the receptive field is controlled by the number of model layers: in our method, it is controlled by the random walk length, where model layer of size k corresponds to walk length of 2
As shown in Table 2 G2PM outperforms all self-supervisee baselines and ranks second overall- only behind the supervised GPM-achieving an average rank of 2.0. Notably, on the large-scale ogbn-products dataset, GPPM achieves substantial performance gain (80.56 vs. 79.33), highlighting its scalability. Ablation shows that on small graphs (s 100K nodes), the model performs well even without pre-training, likely due to its sufficient capacity. However, on larger datasets like ogbn-arxiv and ogbn- products, pre-training proves crucial for capturing fine-grained structural patterns.
Node Classification on Heterophily Graphs. We evaluate GM on heterophily graphs: Chameleon, Actor, and Pokec (over IM nodes). Results are shown Figure 7 We compare against GraphMAE. varying the receptive field via the number of GNN layers (for GraphMAE) and random walk length (for GPPM) ). G consistently outperforms GraphMAE across datasets and benefits from increased receptive field size, demonstrating its ability to capture non-local information critical for heterophilous settings. On Actor, however, performance shows no clear correlation with receptive field, suggesting that key signals in this collaboration network are primarily localized.
Link Prediction. To further demonstrate the ef- fectiveness of our pretraining approach, we fol- low Wang et al. [68 show the link prediction results. We use three datasets, including Cora, Pubmed, and ogbl-collab, and follow a standard 80/5/15 split for training, validation, and test sets. For evaluation, we report H0 on Cora and Pubmed, and @it@ 50 on ogbl-collab. The results are summarized in Table 3] where we compare our method G2PM with a basic super- vised GCN 33 and a widely used graph pretraining method, GraphMAE (2]. As shown, GraphMAE significantly outperforms GCN, benefiting from its ability to utilize un unlabeled data during pretraining. Notably, G2PM achieves the best performance across all datasets, likely due to its capacity to model substructures that capture latent connectivity patterns between nodes.
Table Link prediction results on three widely- used benchmarks.
Cora
Pubmed
ogbl-Collab
# Nodes Edges Metric
2,708
19,717
235 2558868
10,556
88,648
2.570,930
Hit@20
H0
50
GCN [3
84.1 #
85,1 + +.8
44,8
GraphMAE 22 GPPM
87.6
87.1 3.1
46.5 0.9
90.4 4 0.8
88.0 4 3.8
47.1 0.6
8

---

Table 4: Graph classification results on molecular and social networks. Boldface and underline indicate the best and sub-best self supervise methods, and A.R. is the average ranking.
HIV
PCBA
Sider
MUV
ClinTox
IMDB-R
REDDIT-MI2K A.R.
Graphs Nodes Edges
41,127
437,929
1,427
93,087
1,478
1,000.
11,929
--25.5
~26.0
1336
~24.2
~26.1
~19.8
~331.4
-27.5
~28.1
~00.
~52.6
~55.5
-193.1
~9138
Supervised
GIN 773
75.8 0.8
70.3 0.3
57.7 0.8
74.4
0.9
83.4
73.3
3
6.3
GPM 68
0.9
75.1
0.3
5.0
74.6 1.4
82.4
0.3
82.7 + 0.5
4.3
3.0
GraphCL
0.3
2.14
579
82.9 2.6
71.1
37.9
Contrastive
10A0 76
0.3
1..4
58.5 0.5
72.3 L0
82.2
70.2 0.7
0.
6.0
MVGRL 19
7.14 7.77
0.6
71.5 1.2
03.
InteGCL
72
2..
2.77
58.7 0.7
73.4 1.0
75.1 8.7
39.3 0.5
5,4
GraphMAF
223
73.2 0..
03.7 6.06+00
75.5 0
37.6 2.5
4.1
Generative
S2GAE 52
75.6
72.9
58.0 0.9
71.6
80.6 2 0.4
75.8
37.9 1.8
7.0
GMPM w/o Pretruin
69.8
68.4
58.8 0.3
66.3 1.4
80.0 1.8
80.0 0.8
37.5
8.3
PM
78.7 2 0.1
75.6 2. 0.1
61.2 a 0.2
75.7 a 0.4
86.6 = 0.8
83.0
41.8 0.3
1.0
Table 5: Cross-domain transferability perfor- mance across diverse source and target datasets. Parentheses indicate the performance gap com- pared to training from scratch on the target graph.
Table 6: Cross-domain pre-training results on text-attributed graphs processed by (37], where node features are aligned via textual encoder.
Pretrain
Ardv FB15K237 ChemBI
Source
Arái
III
Downstream
Aráiv (Academia)
FB15K237 (Knowledge Graphi
HIV (Molecule
Target
Products
HTV
Ardiv
PCBA
GNN 60 [3]
78.3 13
70.1 (5.7
(1.6 f) (1.00.))
BGRL
86
68.5 1.6
GPM 68
82.0
74.3 (2.7
7140.5)
76.4 (1.3
GraphMAE
2.3
6..
BGRL 53
78.8 (0.2 1)
(3.
72.9 68.6(19.))
ORA 37 GFT A5
71.4
84.7
72.0 1.6
GrapiMAE
(3.1
79.2 69...19))
71.9
8.2
7.33+
81.3 1)
(1.9)
72.6(0.377)
(2.3
88.9
1.3
Convergence Curves. Figure 6 compares the training dynamics of models trained from scratch versus those finetuned from a pre-trained G2PM checkpoint on ogbn-arxiv. Pre-training leads to consistently better performance, indicating that structural knowledge acquired during pre-training accelerates convergence and improves generalization. As expected, accuracy improves with additional training epochs in both settings.
Graph Classification. We evaluate G2PM on seven datasets: five molecular graphs (HIV, PCBA, SIDER, MUV, ClinTox) and two social networks (IMDB-B, Reddit-M12K). Dataset statistics and results are summarized in Table We use public splits for molecular graphs and 80/10/10 random splits for social networks, following linear probe protocol. Baselines include supervised GAT (60, non-message-passte GPM [68]] contrastive methods (GraphCL. 775). JOAO [76), MVGRL. [19].
InfoGCL (72), and generative models (GraphMAE (22). S2GAE (52)) G2PM consistently achieves
the best performance across all datasets. In contrast, the model without pre-training performs worst
on average, highlighting the importance of capturing domain-specific substructure distributions to support discriminative generalization.
5 Cross-Domain Graph Learning
Cross-Domain Transfer. We evaluate the cross-domain transferability of G2PM in Table mea- suring generalization under distribution shifts across domains and tasks. In this setting, the model is pre-trained on source graph and fully fine-tuned on target graph. Since feature spaces differ across graphs, we introduce Icarnable linear projection layer before the pre-trained encoder, which is jointly finetuned during transfer. Basclines include GNNs (GAT (60] for ogbu-arxiv and GIN 773 for HIV), as well as GPM [68], BGRL [53] and GraphMAE [22] GPPM achieves the best transfer results, showing positive gains in 3 out of setups. In contrast, message-passing methods only transfer well across closely related domains (e.g.. HIV - PCBA). We attribute this to the ability to learn transferable structural patterns, enabling generalization (e.g., Arxiv > HIV), while message-passing remains sensitive to subtle structural shifts [66].
across domain and task boundaries
Cross-Domain Pre- Fre-Training. Table 6 presents results on cross-domain pre-training using three diverse graph types: Arxiv (academic network), FB FB15K237 (knowledge graph), and HIV (molecular graph) 37.. All graphs are text-attributed;
shared textual encoder to project node descriptions

---

into a unified embedding space, enabling a single model to operate across domains. We compare PM pre-training baselines (BGRL [53], GraphMAE (22)) and graph foundation models (OFA GFT 65 GMPM achieves the best or second-best performance across all datasets, highlighting its superior ability to learn transferable substructure representations, even under significant domain
37
shifts where sarange-pasiing--oe based methods often struggle.
6
Related Works
Graph Transformers. Inspired by the success of Transformers in vision and language 12
57 20
[3], several works have extended this architecture to graphs [34] 47 21 graph Transformers treat nodes as tokens and apply self-attention over all pairs. However, the quadratic complexity of node attention limits their scalability, making them impractical for large graphs [70]. To address this, recent works propose tokenizing graphs via substructures such as random walks or motifs 774 (24), enabling sequence-basee modeling 688
79 80] Typically,
21 30). For example, GPM [68 applies a ViT-style architecture over substructure sequences, Building on this idea, our work explores generative pretraining using a Transformer over substructures, entirely removing message passing.
Generative Pretraining. Generative pretraining has driven major advances in vision and language. These methods predict masked content from visible context, enabling learning from large-scale unlabeled data and powering modern foundation models [57]. This paradigm has extended to other domains (e.g., video, audio, biology), but its impact on graphs remains limited. More recent works apply generative approaches to graphs (e.g., VGAE (32). GraphMAE (22), GraphMAE2 (23], MaskGAE [ G2PT (T],, but focus reconstructing low-level signals such nodes or links, and typically rely on message-passing passing GNNs, limiting their expressiveness and scalability. In contrast, caassageppssiing -ree framework that models high-level semantic substructures, unlocking better scalability and generalization.
GMPM introduces fully Transformer-bastt
Random Walks Graphs. Random walks have been widely used to represent substructures, from early unsupervised embeddings
74 24 to recent deep models [68 81 27
41 55 26
25 31.
These methods have been shown to break key limitations of message passing, improving expressiveness [69] 42) modeling long-range dependencies [5], and mitigating over-smoothing
and over-squashing 662 However, these random walk-based methods often focus on global patterns
while overlooking localized structures [55]. G²PM uses random walks to sample substructures and design the MSM task automatically balance the contributions between localized and globalized substructures.
7 Conclusion
We introduce G2PM, a Transformer-based generative pretraining framework for graphs that operates entirely without message passing. Unlike traditional GNNs, G scales effectively with both data and model size, and consistently improves performance across tasks. Through extensive ablations and experiments, demonstrate its expressiveness, transfcrability, and potential as scalable backbone for graph representation learning. While G2PM PM leverages unordered substructure sequences- -suitnee -effiction-extediinng it to ordered sequences may enable next-token prediction, further improving scalability. Additionally, our use random walks as an online tokenizer opens up future directions in designing learnable and adaptive substructure tokenizers for graphs.
for masked-toker
Acknowledgement
The work was partially supported by the NSF under grants IIS-2533550, IIS LIS-2225544, IIS-2340346, IIS-2217239, IIS- 115-2528540, CNS-2426514 14, and CMM1-2146076, ND-IBM Tech Ethics Lab Program, Notre Dame Strategic Framework Research Grant (2025), and Notre Dame Poverty Research Package (2025). Any expressed opinions, findings, and conclusions or recommendations are those of the authors and do not necessarily reflect the views of the sponsors.
10

---

References
[1] Muad Abu-Ata and Feodor F Dragan. Metric tree-like structures in real-world networks: an empirical study. Networks, 2016.
[2] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv, 2023.
[3] Alex Arenas, Alberto Fernandez, Santo Fortunato, and Sergio Gomez. Motif-based communities in complex networks. Journal of Physies A: Mathematical and Theoretical, 2008.
[4] Aili Asikainen. Gerardo lñiguez, Javier Ureña-Carrión, Kimmo Kaski, and Mikko Kivelä. Cumulative effects of triadic closure and homophily in social networks. Science Advances, 2020.
[5] Hangbo Bao. Li Dong, Songhao Piao, and Furu Wei. Beit: Bert pre-training of image trans- formers. arXiv, 2021.
[6] Ginestra Bianconi, Richard K Darst, Jacopo lacovacci, and Santo Fortunato. Triadic closure as basic generating mechanism of communities in complex networks. Physical Review 2014.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In NeurIPS, 2020.
[8] Dexiong Chen, Leslie O' Brayy, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In ICMI,, 2022.
[9] Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: tokenized graph transformer for node classification in large graphs. In ICLR, 2023.
[10] Xiaohui Chen, Yinkai Wang. Jiaxing He, Yuanqi Du Soha Hassoun, Xiaolin Xu, and Liping Liu. Graph generative pre-trained transformer. In ICML, 2025.
[11] Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv, 2014.
[12] Jacob Devlin, Ming- deep bidirectional transformers for language understanding. In NAACL, 2019.
Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of
[13] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
[14] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv, 2020.
[15] Michael R Garey and David S Johnson. Computers and intractability, volume 29, wh freeman New York, 2002.
[16] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
[17] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks, In KDD, 2016.
[18] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
[19] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In JCML, 2020.
[20] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In CVPR, 2022.

---

[21] Xiaoxin He. Bryan Hooi, Thomas Laurent, Adam Perold, Yann LeCun, and Xavier Bresson. A generalization of vit/mlp-mixer to graphs. In ICML, 2023.
[22] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang. Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In KDD, 2022.
[23] Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A decoding-enhanced masked self-supervised graph learner. In wwW, 2023.
[24] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In ICML, 2018.
[25] Yunhui Jang, Dongwoo Kim, and Sungsoo Ahn, Graph generation with Sk^25-trees. In ICLR,, 2024.
[26] Yunhui Jang, Seul Lee, and Sungsoo Ahn. A simple and scalable representation for graph generation. In ICLR, 2024.
[27] Di Jin, Rui Wang, Meng Ge, Dongxiao He, Xiang Li, Wei Lin, and Weixiong Zhang. Raw-gnn: Random walk aggregation based graph neural network. In IJCAI, 2022.
[28] 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. arXiv,, 2020.
[29] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In ICML, 2020.
[30] Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. NeurIPS, 2022.
[31] Jinwoo Kim, Olga Zaghen, Ayhan Suleymanzade, Youngmin Ryou, and Seunghoon Hong. Revisiting random walks for learning on graphs. In ICLR, 2025.
[32] Thomas N Kipf and Max Welling. Variational graph auto-encoders. In NeurIPS Workshop, 2016.
[33] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[34] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. NeurIPS, 2021.
[35] 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 KDD, 2023.
[36] Xiaodong Li, Reynold Cheng, Kevin Chen-Chuan Chang, Caihua Shan, Chenhao Ma, and Hongtai Cao. On analyzing graphs with motif-paths VLDB, 2021.
[37] 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. ICLR, 2024.
[38] Tianyi Ma, Yiyue Qian, Chuxu Zhang, and Yanfang Ye. Hypergraph contrastive learning for drug trafficking community detection. In ICDM, 2023.
[39] Tianyi Ma, Yiyue Qian, Shinan Zhang, Chuxu Zhang, and Yanfang Ye. Adaptive expansion for hypergraph learning. arXiv preprint arXiv:2502. /5564, 2025.
[40] Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Michael Galkin, and Jiliang Tang. Graph foundation models. In ICML., 2024.
[41] Karolis Martinkus, Pál András Papp, Benedikt Schesch, and Roger Wattenhofer. Agent-based graph neural networks. In ICLR, 2023.
12

---

[42] Gaspard Michel, Giannis Nikolentzos, Johannes F Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. In ICML, 2023.
[43] Christopher Morris, Fabrizio Frasca, Nadav Dym. Haggai Maron, Ismail Ilkan Ceylan, Ron Levie, Derek Lim, Michael M. Bronstein, Martin Grohe, and Stefanie Jegelka. Position: Future directions in the theory of graph machine learning. In ICML, 2024.
[44] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In KDD, 2014.
[45] Yiyue Qian, Tianyi Ma, Chuxu Zhang, and Yanfang Ye. Dual-level hypergraph contrastive learning with adaptive temperature enhancement. In WWW, 2024.
[46] Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gec: Graph contrastive coding for graph neural network pre-training. In KDD, 2020.
[47] Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. In NeurlPS, 2022.
[48] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro, Graphon neural networks and the transfer- ability of graph neural networks. In NeurlPS, 2020.
[49] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv, 2023.
[50] Alice Schwarze and Mason A Porter. Motifs for processes on networks. SIAM Journal on Applied Dynamical Systems, 2021.
[51] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. arXiv, 2015.
[52] Qiaoyu Tan, Ninghao Liu, Xiao Huang, Soo-Hyun Choi, Li Li, Rui Chen, and Xia Hu. S2gae: Self-supervised graph autoencoders are generalizable learners with graph masking, In WSDM, 2023.
[53] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In ICLR, 2022.
[54] Keyu Tian, Yi Jiang, Zehuan Yuan, Bingyue Peng, and Liwei Wang. Visual autoregressive modeling: Scalable image generation via next-scale prediction. NeurIPS, 2024.
[55] Jan Tönshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing. TMLR, 2023.
[56) Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv,, 2021.
[57] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv, 2023.
(58) Charalampos E Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. In WWW, 2017.
[59] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez,
E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, 2017.
[60] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
13

---

[61]
Yuanqing Wang and Kyunghyun Cho. Non-convolutional graph neural networks. In NeurIPS, 2024.
[62] Yuanqing Wang and Kyunghyun Cho. Non-convolutional graph neural networks. In NeurlPS, 2024.
[63] Zehong Wang. Qi Li, Donghua Yu, Xiaolong Han, Xiao-Zhi Gao, and Shigen Shen. Heteroge- neous graph contrastive multi-view learning. In SDM, 2023.
[64] Zehong Wang, Donghua Yu, Shigen Shen, Shichao Zhang, Huawen Liu, Shuang Yao, and Maozu Guo. Select your own counterparts: Self-supervised graph contrastive learning with positive sampling. TNNLS, 2024.
[65] Zehong Wang, Zheyuan Zhang, Nitesh Chawla, Chuxu Zhang, and Yanfang Ye. GFT: Graph foundation model with transferable tree vocabulary. In NeurlPS, 2024.
[66] Zehong Wang, Zheyuan Zhang, Chuxu Zhang, and Yanfang Ye. Subgraph pooling: Tackling negative transfer on graphs. IJCAI, 2024.
[67] Zehong Wang, Zheyuan Zhang, Tianyi Ma, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. Towards graph foundation models: Learning generalities across graphs via task-trees. In ICML. 2025.
[68] Zehong Wang, Zheyuan Zhang, Tianyi Ma. Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. Neural graph pattern machine. In ICML, 2025.
[69] Pascal Welke, Maximilian Thiessen, Fabian Jogl, and Thomas Gärtner. Expectation-ccmplete graph representations with homomorphisms. In ICML, 2023.
[70] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for large-graph representations, In NeurlPS, 2023.
[71] Zhenda Xie, Zheng Zhang, Yue Cao, Yutong Lin, Jianmin Bao, Zhuliang Yao, Qi Dai, and Han Hu. Simmim: simple framework for masked image modeling. In CVPR, 2022.
[72] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information-awaat graph contrastive learning. NeurIPS, 2021.
[73] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[74] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In KDD, 2015.
[75] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. NeurIPS, 2020.
[76] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In ICML, 2021.
[77] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for gnn expressiveness. In ICLR, 2024.
[78] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. NewrlPS, 2021.
[79] Zheyuan Zhang, Zehong Wang, Shifu Hou, Evan Hall, Landon Bachman, Jasmine White, Vincent Galassi, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. Diet-odin: A novel framework for opioid misuse detection with interpretable dietary patterns. In KDD, 2024.
[80] Zheyuan Zhang, Zehong Wang, Tianyi Ma, Varun Sameer Taneja, Soñaa Nelson, Nhi Ha Lan Le, Keerthiram Murugesan, Mingxuan Ju, Nitesh V Chawla, Chuxu Zhang, et al. Mopi-hfrs: multi-objective personalized health-aware food recommendation system with Ilm-enhanced interpretation. In KDD, 2025.
14

---

[81] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In ICLR, 2022.
[82]
Ziwen Zhao, Yuhua Li, Yixiong Zou, Jiliang Tang, and Ruixuan Li. Masked graph autoencoder with non-discrete bandwidths. In WwW, 2024.
[83] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. In ICML Workshop, 2020.
[84] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW, 2021.
[85] Nicolas Zucchet and Antonio Orvieto. Recurrent neural networks: vanishing and exploding gradients are not the end of the story. NeurlPS, 2024.
15

---

A From the Perspective of Substructure Dependencies
To understand how PM work, take functional correlations among substructures inform both model design and training strategies.
Hierarchical Dependencies. Substructures often compose one another hierarchically. For example, a triangle (3-cycle) may serve as fundamental building block for larger cliques, while a square (4-cycle) can be part of more complex motifs such diamonds. This compositionality implies that the presence of smaller motifs potentially offer predictive signals for larger structures and vice versa. From modeling perspective, this hierarchical property allows the model to infer partially masked substructures based on their visible tokens.
Functional Reinforcement. Certain substructures statistically co-occur due to the generative pro- cesses underlying different graph types 488. For instance, in social and citation networks, a high density of triangles often correlates with the existence of higher-order cliques 6 4) Similarly, the
frequent appearance of short chains may indicate the potential for longer cycle [3, 50]. We refer to this pattern functional reinforcement, where the presence of one motif increases the likelihood of encountering another. This mutual reinforcement reflects domain structural priors and can be leveraged during pre-training to build predictive inductive bias across motifs.
Conversely, some substructures exhibit negative correlations. reflecting competition for structural space within the graph. We term this phenomenon example, node embedded within multiple triangle-like motifs likely part of densely connected community, making it less probable to support hub-like star patterns 3 58). Likewise, graphs with
Functional Exclusion.
corieeooonffncioonnn functional exclusion. For
tree-like branches typically lack the density required to support large cliques [. Understanding such exclusion enables the model to refine its prediction space: it can down-weight structurally incompatible or redundant patterns during reconstruction.
These inter-substructure dependencies serve dual purposes. On one hand, they enrich the predictive landscape by offering complementary structural cues: on the other hand, they enable the model to disambiguate noisy or redundant substructure tokens by reasoning over motif co-occurrence patterns. By explicitly modeling these dependencies, we endow the system with the capacity generalize from partial observations and regularize against overfitting to spurious or dataset-specific artifacts.
B Implementation Details
B.1 Environments
Most experiments are conducted on Linux servers equipped with four Nvidia A40 GPUs. The models implemented using PyTorch 2.4.0, PyTorch Geometric 2.6.1, and Py PyTorch Cluster 1.6.3, with CUDA 12.1 and Python 3.9.
B.2
Training Details
Table 7: Default syper-parameter settings.
Hyper-parament
Value
Hyper-parameter
Value
Batch Size
256
Gradient Clip
Hidden Dimension
768
Optimizer Beta
0.9
Number of Heads
12
Optimizer Beta 2
0.005
Number Encoder Layers
3
Min LR
le-07
Number of Decoder Layers
1
Warmup LR
le-07
EMA Momumtum
0.99
Scheduler
Cosine
EMA Update Every
10
Warmup Epochs
Dropout Weight Decay
0.3
Linear Probe LR
0.01
0.05
Linear Probe Weight Decay
0.001
In our setup, we use the Adam W optimizer with weight decay and set the number of epochs as 100. All experiments are conducted five times with different random seeds. The batch size is set to 256 by default. We present detailed default setup in Table
16

---

B.3 Model Configurations
We perform hyperparameter tuning over the following ranges:
learning rate (le-3, ve 1e-4, 7 5, 1e-5), pattern size {4,8, 16), feature
augmentation ratio Pteat [0.0, 0.9], and substructure augmentation ratio Psub [000, 0.9]. The final
selected hyper-parameters are reported in Table g
Table 8: Dataset-specift hyper- parameerr settings.
Pubmed
Photo
Computers
WikiCS
Flickr
Arxiv
Products
LR
3e-5
le-5
7e-5
le-5
5e-5
3e-4
3e-4
Peature Aug. Pfeat
0,6
0.2
0.0
0.0
Substructure Aug. Potruct
0.8
0.3
0.8
0.8
Pattern Size
8
HIV
PCBA
Sider
MUV
ClinTox
IMDB-B
REDDIT-MI2K
T.R
3e-5
le-5
le-4
5e-5
5e-5
5e-4
3e-4
Feature Aug. Pfeat
0.1
0.0
0.0
0.0
0.0
0.3
0.0
Substructure Aug. Patruet
0.3
0.8
0.7
0.2
0.0
0.3
0.6
Pattern Size
16
8
8
8
17

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main contribution is about the scalability, which has been clearly stated in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
18

---

Justification:
As discussed in the conclusion, we discuss the limitations and the potential
improvements.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
No theoretical part the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide essential reproducibility resources in the appendix. And we definitely will release the code upon acceptance.
Guidelines:
19

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
See attachment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
Cow.ooeeeeSomiiiiooooooooieeeeee for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips.cc/publi///guu
Codeeuumiiii wettsbbmmssiiioi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
20

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provide comprehensive training setup in the experiments and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide it on the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
21

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///waaaap..coppoooo.ccccaaa
Answer:
[Yes]
Justification:
We strictly follow the NeurIPS guidance.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our method is a pure machine learning model without using large language models. There are no societal concerns from the technical perspective.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has socictal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Not available.
Guidelines:
22

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We have cited all of essential tools and papers.
Guidelines:
The answer NA means that the paper does
existing assets. The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
23

---

Justification:
No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not relevant to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [Yes]
Justification:
The role of LLMs in this paper is only related to polish.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy htte::///aarrpppccc////feerrrerp for what should or should not be described.
24


Reviews:
[{"review_id": "BYSWk1TuCl", "reviewer": "Reviewer_P8WG", "summary": "The authors claim that existing pretrain graph representation methods suffer from fundamental limitations due to MPNNs: constrained expressive power, over smoothing, over-squashing, and poor capacity for modeling long-range dependencies. Therefore, this paper aims to extend the success of Transformer-based generative pre-training to the graph domain, with the goal of enabling scalable graph representation learning. The authors propose G^{2}PM, which first applies random walk to extract node sequence for each node, and then obtain the nodes’ representation via a transformer. Finally, based on constructed substructures sequence, mask-prediction self-supervised loss is used to learn node representations. Experimental results on multiple datasets seem to validate the effectiveness of the pre-training.", "questions": "See the weaknesses.", "limitations": "The authors claim in the limitation section that the current method is merely a masked-token prediction paradigm, and its effectiveness and scalability for next-token prediction remain unknown. Exploring next-token prediction is particularly important, as autoregressive methods have shown greater potential than autoencoding methods in the fields of NLP and CV for building foundation models.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is easy to read and understand.\n2. The experiment evolve node classification from 7 datasets and graph classification from 7 datasets.\n3. The proposed G^{2}PM seems to have somewhat scalability from Figures 2 and 3, which is attractive.\n4. The paper conducts lots of experimental analysis about model architecture design in Section 3.\nWeakness:\n1. The proposed method is not a novelty. According to my understanding, the proposed G²PM obtains the substructure sequence of each node through random walks and then computes the node representation using sequence modeling methods (i.e., Transformer, RNN). Based on the constructed node representations and the sampled sequences, G²PM further learns the node representations using a general mask prediction method. Thus, the main innovation of the method is tokenizing substructures via random walks, which is simple and straightforward.\n2. In the scalability experiment of Figure 2, 60M is not a large model size. If the model size continues to increase, can the performance of the method still improve consistently?\n3. In the experiment of Model architecture, the author claims that deeper encoders enhance performance while increasing decoder capacity provides limited or negative returns. I personally think that the selected range of encoder and decoder layers is too small to support the argument. Moreover, which dataset is used for the experimental results in Figure 5(b)?\n4. To demonstrate the pretrain effectiveness, it is necessary to experiment with a link prediction task.\n5.“Model Layer. Table 5a shows” in line 181 has a linking error.", "was_revised": true, "final_justification": "The authors have addressed my concerns, so I decide to increase my score.", "rebuttal": "Dear reviewer, \n\nWe sincerely thank the reviewer for the thoughtful and detailed feedback. We appreciate the recognition of the paper’s clarity, the comprehensive experimental analysis, and the promising scalability of our proposed method. We aim to clarify our contributions, provide additional experimental evidence, and address the limitations discussed to better convey the value and potential of G²PM.\n\n> Q1: The method is simple and straightforward.\n> \n\nThank you for your valuable feedback. We appreciate the opportunity to clarify the novelty of our method and address your concerns.\n\n1. **A New Perspective on Graph Pretraining:**\n    \n    Our primary contribution lies in introducing a new and promising *generative modeling perspective* over substructures for graph pretraining, which enables substantial scalability. While the connection between Transformer-based pretraining and scalability has been extensively explored in other domains such as NLP and CV, this direction remains underexplored in the context of graph learning. To the best of our knowledge, **no prior work has successfully demonstrated such scalability in graph pretraining**.\n    \n2. **Simple Yet Effective Design:**\n    \n    Our method proposes a simple yet effective implementation of this generative framework. While the use of random walks for substructure sampling is straightforward, our results demonstrate that even such a **simple tokenization can yield strong performance** when combined with a generative modeling approach. Importantly, this simplicity does not limit extensibility. As evidenced in Tables 1(b) and 1(e), incorporating advanced components such as positional encodings and topological reconstruction can further boost performance, indicating that G²PM offers a strong and adaptable foundation.\n    \n3. **Scalability Advantage:**\n    \n    Despite its conceptual simplicity, G²PM achieves compelling scalability with respect to both model capacity and data volume. In contrast to existing message-passing-based pretraining methods, which often involve complex architectural designs yet struggle to scale, G²PM supports model scaling up to 60M parameters. However, GraphMAE, a widely adopted method, saturates at around 3M parameters, **highlighting a significant (~20x) scalability advantage of G²PM**.\n    \n\nIn summary, we believe that G²PM not only offers a novel and scalable approach to graph pretraining, but also serves as a potential backbone for the next generation of graph representation learning, moving beyond the limitations of traditional message passing.\n\n> Q2: In the scalability experiment of Figure 2, 60M is not a large model size. If the model size continues to increase, can the performance of the method still improve consistently?\n> \n\n**1. Model Size in Graph Learning:**\n\nWhile 60M parameters may not appear large compared to models in the LLM era, where even the smallest models typically exceed 1B parameters, it is **indeed a substantial size in graph neural networks**. Graph models generally operate at a much smaller scale. For example, GraphMAE, a representative graph pretraining method, has approximately 3M parameters under its default configuration. Even among larger graph foundation models, parameter counts rarely exceed 30M unless they explicitly incorporate LLMs (see Table 8 in [1]). Therefore, achieving 60M parameters in a standalone graph model is already a significant step forward in scalability for this domain.\n\n**2. Performance Scaling with Model Size:**\n\nThe impact of increasing model size on performance depends heavily on the scale of the dataset. On smaller or medium-sized datasets such as *ogbn-arxiv* (~170K nodes), increasing the parameter count beyond a certain point leads to saturation or even slight performance drops due to overparameterization. For example, as shown in the table below, performance peaks around 60M and then declines slightly with further increases.\n\nHowever, on large-scale datasets like *ogbn-products* (~2M nodes), **increasing model size continues to yield consistent improvements**. As the table shows, **G²PM scales up to 160M parameters and continues to improve in performance**. We emphasize that this does **not** imply that G²PM has reached its performance ceiling; we have not tested models beyond 160M due to the time constraints of the rebuttal period.\n\n| **Dataset** | **~60M** | **~120M** | **~160M** |\n| --- | --- | --- | --- |\n| **ogbn-arxiv** | 72.31±0.07 | 71.42±0.09 | 71.41±0.14 |\n| **ogbn-products** | 80.56±0.01 | 80.98±0.02 | 81.31±0.01 |\n\n[1] GFT: Graph Foundation Model with Transferable Tree Vocabulary, NeurIPS 24. \n\n> Q3: In the experiment of Model architecture, the author claims that deeper encoders enhance performance while increasing decoder capacity provides limited or negative returns. I personally think that the selected range of encoder and decoder layers is too small to support the argument.\n> \n\nAs previously mentioned, model performance on **ogbn-arxiv** tends to saturate beyond 60M parameters. Therefore, to better investigate the effect of encoder and decoder depth, we conducted additional experiments on the larger **ogbn-products** dataset, where model scaling exhibits clearer trends.\n\nFrom these results, we observe a **consistent pattern**: increasing the encoder depth leads to improved performance, while increasing decoder depth beyond a certain point yields diminishing or even negative results. Specifically, a shallow decoder (e.g., 1 layer) paired with a deeper encoder results in the strongest performance. **This supports our original statement regarding the asymmetric benefit of deeper encoders versus decoders**.\n\nDue to computational constraints, we extended encoder depth up to 6 layers and decoder depth up to 3 layers. We would be happy to include additional results if required.\n\n| **Enc. Layers** | **Dec. Layers** | **ogbn-products** |\n| --- | --- | --- |\n| 1 | 1 | 78.39±0.04 |\n| 2 | 1 | 79.61±0.02 |\n| 3 | 1 | 80.56±0.01 |\n| 6 | 1 | 81.04±0.01 |\n| 6 | 2 | 80.67±0.03 |\n| 6 | 3 | 80.13±0.01 |\n\n> Q4: Link Prediction\n> \n\nThank you for the suggestion. To further demonstrate the effectiveness of our pretraining approach, we provide link prediction results on three datasets: *Cora* (2,708 nodes, 10,556 edges), *Pubmed* (19,717 nodes, 88,648 edges), and *ogbl-collab* (235,868 nodes, 2,570,930 edges). We follow a standard 80/5/15 split for training, validation, and test sets. For evaluation, we report *Hit@20* on Cora and Pubmed, and *Hit@50* on ogbl-collab. The results are summarized in the table below, where we compare our method (G²PM) with a basic supervised GCN and a widely used graph pretraining method, GraphMAE. As shown, GraphMAE significantly outperforms GCN, benefiting from its ability to utilize unlabeled data during pretraining. Notably, G²PM achieves the best performance across all datasets, likely due to its capacity to model substructures that capture latent connectivity patterns between nodes.\n\n| **Method** | **Cora (Hit@20)** | **Pubmed (Hit@20)** | **ogbl-collab (Hit@50)** |\n| --- | --- | --- | --- |\n| **GCN** | 84.14±1.19 | 85.06±3.79 | 44.75±1.07 |\n| **GraphMAE** | 87.64±1.44 | 87.12±3.15 | 46.53±0.89 |\n| **G2PM** | **90.42±0.78** | **88.01±3.79** | **47.10±0.57** |\n\n> Q5: Can we replace masked-token prediction with next-token prediction?\n> \n1. **Next-token prediction may not necessarily outperform masked-token prediction in G²PM:**\n    \n    While autoregressive (next-token) prediction has shown strong performance in sequential domains like text, its advantages may not directly transfer to graph-structured data. For example, in image generation, many autoregressive methods underperform compared to denoising-based approaches like diffusion models. **This is because images—and similarly, graphs—often contain high levels of redundancy or noise.** Denoising methods like masked-token prediction can learn to identify and reconstruct informative regions, discarding unimportant patterns.\n    \n    In our setting, G²PM benefits from this principle. For instance, in social networks, detecting key substructures such as triangles may suffice for node classification, while other sampled patterns may act as noise. From this perspective, masked-token prediction is a natural fit for our model, and next-token prediction may not offer clear benefits in terms of scalability or effectiveness.\n    \n2. **Extending G²PM to next-token prediction is feasible and worth exploring:**\n    \n    We agree that exploring next-token prediction is important, particularly for advancing generative graph modeling. The main challenge lies in defining a meaningful order over graph substructures, which is non-trivial due to the non-Euclidean nature of graphs. Nevertheless, there are several promising directions: (1) **Pattern size**: use the number of unique nodes in a substructure to define an order (e.g., predict larger patterns from smaller ones). (2) **Graph edit distance**: order substructures based on how dissimilar they are from one another. (3) **Spectral properties**: use eigenvalue-based metrics to define substructure complexity and ordering. We acknowledge this as a valuable direction for future work and appreciate the reviewer’s suggestion in pointing it out.\n    \n\n> Q6: Minor points\n> \n\nQ6.1: which dataset is used for the experimental results in Figure 5(b)?\n\nA6.1: The dataset used in Figure 5(b) is **ogbn-arxiv**. Thank you for pointing this out—we will clarify this explicitly in the revised manuscript.\n\nQ6.2: “Model Layer. Table 5a shows” in line 181 has a linking error.\n\nA6.2: Thank you for catching this. We will correct the linking error in the updated version of the paper."}, {"review_id": "ghz5xDYjpd", "reviewer": "Reviewer_CueM", "summary": "The authors propose a Transformer-based pre-training framework for graphs based on masked subgraph prediction. Subgraphs are generated through random walk tokenization and the model is shown to perform well across a range of scaling and ablation experiments.", "questions": "As well as addressing the two points in weaknesses, I have a couple of minor questions.\n\n[Line 128] How do you decide the ordering of the graph substructure tokens? Does this matter?\n\nDo the substructures from random walks significantly differ across datasets? Would this effect cross-domain adaption?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 1, "strengths_and_weaknesses": "Strengths \n\n- The authors undertake a comprehensive set of ablations and experiments. These clearly highlight the benefits of using subgraphs generated from their tokenization with a transformer encoder across a range of tasks. \n\n- The cross-domain transfer experiments are very compelling and show how the approach could make sense as a form of foundation model when compare to standard message-passing based approaches. \n\n- The paper is well-written and clearly motivated. \n\nWeaknesses \n\n- the technical development is limited in that the model is based on GPM and the innovation comes from the masked modeling component which in itself is well established. This lack of innovation is further highlighted by the fact that the performance improvement over GPM is negligible across a lot of tasks and can reduce performance. Given that the paper mainly adapts standard self-supervised learning techniques to GPM and doesn't see a huge performance boost, the scope of the paper could appear limited.\n\n- The self-supervised step can introduce a lot of additional computational time. Having some idea of the tradeoff between this and the performance improvement could be helpful to practitioners.", "was_revised": true, "final_justification": "The authors have satisfactorily addressed my concerns in their rebuttal.", "rebuttal": "Dear reviewer, \n\nWe sincerely thank the reviewer for the thoughtful and constructive feedback. We are pleased to hear that the paper is considered well-written, clearly motivated, and supported by a comprehensive set of experiments and cross-domain transfer evaluations. We appreciate the recognition of G²PM’s potential as a foundation model alternative to message-passing-based approaches. We aim to address your concerns by clarifying the contributions beyond prior work, discussing the practical trade-offs of our method, and providing insights into the ordering and variability of substructure tokenization across datasets.\n\n> Q1: The technical development is limited. The improvements over GPM is limited.\n> \n\nThank you for your thoughtful feedback. We believe there may be a misalignment in understanding, and we would like to clarify our contributions on two fronts: (1) the novelty and significance of the G²PM framework, and (2) the performance improvement of G²PM over GPM.\n\n**1. Clarifying the Novelty and Contribution of G²PM:**\n\n- **Scalable Transformer-based Graph Pretraining:** G²PM explores the underexplored territory of scalability in graph representation learning using Transformer-based generative pretraining. While Transformer scalability has been extensively studied in NLP and CV, there is limited work demonstrating effective and scalable Transformer architectures for graphs. Our method is, **to the best of our knowledge, the first to achieve such scalability**, scaling up to 60M parameters, whereas representative graph pretraining methods like GraphMAE saturate around 3M parameters, showing a **~20× benefit**.\n- **Simple yet Effective:** G²PM achieves strong performance with a minimal and straightforward design, **avoiding unnecessary architectural complexity while still being extensible**. As shown in our ablation studies, adding components such as positional encodings or topology-aware reconstruction further improves performance, indicating the method’s robustness and flexibility.\n- **Design Insights for Scalable Graph Models:** We conduct an extensive design space exploration, **offering practical insights into building scalable graph foundation models**. G²PM shows promise as a potential backbone model due to (1) its ability to learn from diverse graphs at scale, and (2) its substructure-based tokenization, which enables effective cross-domain transfer by capturing reusable graph motifs.\n\n**2. Clarifying Performance Improvements over GPM:**\n\nWe also want to address the concern regarding the seemingly marginal performance gain of G²PM over GPM. This is primarily due to the difference in training paradigms:\n\n- **GPM** is a fully supervised model, trained end-to-end with label supervision, allowing all parameters to be updated during training.\n- **G²PM**, on the other hand, is trained in a self-supervised fashion using masked substructure prediction. In our reported setup, we freeze the pretrained model and only train a **linear classifier** on top of the learned representations.\n\nThis discrepancy in training protocols naturally leads to a performance gap. However, when we **fine-tune the entire G²PM model** on downstream tasks (rather than only training the classifier), we observe **significant performance gains**, surpassing GPM across both node and graph classification tasks, as shown below. These results indicate that G²PM offers more than marginal gains—it can outperform strong supervised baselines when properly fine-tuned. We will clarify this more explicitly in the final version of the paper.\n\n| **Method** | **Arxiv** | **Products** | **PCBA** | **REDDIT-M12K** |\n| --- | --- | --- | --- | --- |\n| **Graph Type** | Citation | E-Commerce | Molecule | Social |\n| **# Graphs** | 1 | 1 | 437,929 | 11,929 |\n| **# Nodes** | 169,343 | 2,449,029 | ∼26.0 | ∼391.4 |\n| **# Edges** | 2,315,598 | 123,718,024 | ~28.1 | ∼913.8 |\n| **GPM** | 72.9±0.7 | 82.6±0.4 | 75.1±0.3 | 43.1±0.3 |\n| **G2PM - Linear Classifier (as reported)** | 72.3±0.1 | 80.6±0.0 | 75.6±0.1 | 41.8±0.3 |\n| **G2PM - Full Fine-Tuning** | **73.5±0.4** | **83.1±0.3** | **76.8±0.2** | **43.8±0.3** |\n\n> Q2: The self-supervised step can introduce a lot of additional computational time. Having some idea of the tradeoff between this and the performance improvement could be helpful to practitioners.\n> \n\nThank you for raising this practical concern. We agree that self-supervised learning introduces additional computational cost. However, we would like to emphasize that in real-world applications, this cost is typically incurred during an **offline pretraining phase**. Once the model is pretrained, it can be deployed for downstream tasks with **no additional overhead**, as the learned node or graph embeddings can be directly used during inference. Therefore, training efficiency is less of a concern in many industrial settings where inference-time speed is prioritized.\n\nThat said, we also provide empirical data to help practitioners understand the trade-off between computation time and performance gain. As shown in the table below, pretraining with G²PM results in **substantial improvements** across all datasets. Even on large-scale graphs with over 2 million nodes (e.g., ogbn-products), the total pretraining time is **less than 24 hours** on a single NVIDIA A40 GPU—an acceptable cost for many production environments given the performance benefits.\n\n| Dataset | **# Nodes / Graphs** | **G²PM (w/o Pretrain)** | **G²PM (with Pretrain)** | Imp. (%) | **Pretrain Time (s)** | **Inference Time (s)** |\n| --- | --- | --- | --- | --- | --- | --- |\n| **Arxiv** | 169,343 nodes | 69.6±0.1 | 72.3±0.1 | **3.88** | ~8,000 | ~190 |\n| **Products** | 2,449,029 nodes | 76.9±0.2 | 80.6±0.0 | **4.81** | ~60,000 | ~5,300 |\n| **PCBA** | 437,929 graphs | 68.4±0.0 | 75.6±0.1 | **10.53** | ~45,000 | ~8,700 |\n| **REDDIT-M12K** | 11,929 graphs | 37.5±0.3 | 41.8±0.3 | **11.47** | ~1,000 | ~60 |\n\n> Q3: How do you decide the ordering of the graph substructure tokens? Does this matter?\n> \n\nIn our current approach, we do **not** explicitly define an order for the substructure tokens. Since we adopt a **masked-token prediction** strategy for pretraining, the method is inherently **order-invariant**—the learning objective and model architecture are not sensitive to the order of tokens.\n\nHowever, we acknowledge that token ordering becomes important in **next-token prediction** frameworks, which we plan to explore in future work. In such cases, defining a meaningful and consistent order over graph substructures will be essential. One intuitive approach could be to use the **pattern size** (e.g., the number of unique nodes) as an ordering heuristic—predicting larger patterns from smaller ones. Alternatively, other indicators such as **graph edit distance** or **spectral properties** could be employed to define a semantically meaningful order.\n\nWe appreciate the reviewer bringing attention to this point, which is an important direction for future research.\n\n> Q4: Do the substructures from random walks significantly differ across datasets? Would this effect cross-domain adaption?\n> \n\nYes, the substructures generated via random walks can differ across datasets, and this difference can indeed impact cross-domain adaptation performance. The effectiveness of transfer learning largely depends on the model's ability to **capture invariant and semantically meaningful substructures** that are shared across domains.\n\nFor example, certain patterns, like high-degree nodes, may carry similar semantic meanings in both social and citation networks (e.g., representing influential users or highly cited papers). These shared substructures facilitate successful adaptation. However, when the source and target graphs come from very different domains, they are **less likely to share similar substructures**, which reduces the overlap in learned representations and can lead to diminished transfer performance.\n\n**Despite this challenge, our method shows promising results in cross-domain settings**, suggesting that some level of generalizable substructure information is still being captured. Further improving the alignment of substructure semantics across domains remains an exciting direction for future research."}, {"review_id": "Qm3iE4N0ow", "reviewer": "Reviewer_XK3h", "summary": "This paper introduces G²PM, a generative pre-training framework for graph representation learning based on Transformers. The key idea is to model graphs as sequences of substructures and apply Masked Substructure Modeling (MSM), where masked substructures are reconstructed conditionally on visible ones. The proposed approach enables the application of autoregressive transformer models to graph data by leveraging substructure-aware sequential representations.", "questions": "**Scope of downstream tasks**: The current architecture removes the decoder and adds a linear prediction head to the encoder. This setup supports node-level and graph-level prediction but not generation. Is it possible to extend this framework to graph generation tasks?", "limitations": "The paper only discusses the future direction and does not include any potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "[Strenghts]\n\n- **Clear and well-motivated contribution**: The paper is grounded in a well-defined need—the incorporation of semantic granularity into graph representations—to improve the effectiveness of Transformer-based models on graphs. The integration of substructures into a sequential modeling framework is conceptually novel.\n- **Thorough experimentation**: The authors provide comprehensive empirical results across various benchmarks, demonstrating the effectiveness of the proposed method.\n\n[Weaknesses]\n\n- **Missing prior work on graph-to-sequence representations**: The manuscript overlooks several prior works [1–5] that represent graphs as sequences suitable for Transformer-style training. Notably, the random walk approach employed in this paper closely resembles the method proposed in [5]. While the scope of this work focuses on pre-training, these related methods should still be acknowledged in the “Graph Transformers” and “Random Walks on Graphs” sections of the Related Work.\n- **Representation invariance and completeness**: The sequential representation is based on sampling and random walks. It is unclear whether the resulting representation is lossless. Specifically, how does the model capture the attachment points between substructures? A discussion on the limitations or assumptions of the representation would improve transparency.\n- **Limited benefit of cross-domain pretraining**: Although the paper aims to establish a graph pre-training framework, cross-domain pre-training occasionally degrades performance. For example, in Table 5, the performance on the HIV dataset is worse than in Table 3. The authors should elaborate on potential causes (e.g., domain mismatch or lack of generalization) and whether this highlights a limitation of their pre-training framework.", "was_revised": true, "final_justification": "The rebuttal solved my minor concerns and I keep my positive scores.", "rebuttal": "Dear reviewer, \n\nWe sincerely thank the reviewer for the thoughtful and constructive feedback. We are pleased that the core contributions of G²PM—particularly the integration of substructure-aware sequential modeling for Transformer-based graph pretraining—were found to be clear, well-motivated, and empirically validated. We appreciate the recognition of the novelty in using substructures for masked modeling, as well as the thoroughness of our experimental evaluation. At the same time, we acknowledge the helpful suggestions regarding missing related work on graph-to-sequence representations, the need for more discussion on representation completeness and attachment semantics, and clarification on the cross-domain transfer results. In this rebuttal, we aim to address these concerns and further clarify the scope, assumptions, and extensibility of our framework.\n\n> Q1: Missing prior work on graph-to-sequence representations\n> \n\nThank you for pointing this out. We apologize for the oversight and appreciate the reminder to more thoroughly position our work within the graph-to-sequence literature. While the reviewer did not specify the references, we will make a dedicated effort to identify and cite relevant works [1-5] that model graphs as sequences, particularly those leveraging **random walks or sequential encoding for Transformer-style models**. We will ensure these are properly discussed in the **“Graph Transformers”** and **“Random Walks on Graphs”** sections of the Related Work in the revised version of the paper.\n\nAdditionally, we will clarify how **G²PM fundamentally differs from prior sequence-based methods**. While we acknowledge that there are works exploring graph-to-sequence representations, most of these methods are **task-specific** and do not focus on building **scalable, general-purpose pretraining frameworks**. For example, many existing approaches (i) rely on node-level tokenization, which limits their capacity to capture rich substructure semantics, or (ii) are primarily designed for small-scale or domain-specific tasks (e.g., molecule generation) without addressing scalability to large graphs and datasets.\n\nIn contrast, our focus is on **masked substructure modeling** as a **generative pretraining paradigm** that scales effectively with both **model size (up to 60M parameters)** and **data volume**, as well as enables strong cross-domain performance. Unlike prior sequence-based methods that often lack scalability or fail to fully leverage substructure-level granularity, G²PM introduces a **substructure-as-token design** that allows Transformers to learn transferable representations across diverse graph types. We will make these distinctions explicit in the revised Related Work section to better highlight the unique contributions of our approach.\n\n[1] Graph Generative Pre-trained Transformer, ICML 25\n\n[2] GraphGPT: Generative Pre-trained Graph Eulerian Transformer, ICML 25\n\n[3] Graph-Mamba: Towards Long-Range Graph Sequence Modeling with Selective State Spaces, arXiv 24\n\n[4] Graph Mamba: Towards Learning on Graphs with State Space Models, KDD 24\n\n[5] Supercharging Graph Transformers with Advective Diffusion, ICML 25\n\n> Q2: Representation invariance and completeness\n> \n\nThank you for raising this important point. Our current design does not aim to achieve strict **invariance** or **completeness** in the traditional sense. Instead, we intentionally rely on **randomized sampling** to allow the model to learn which patterns are important and which are not. The randomness ensures **diverse and comprehensive substructure coverage**, avoiding reliance on predefined heuristics or structural assumptions that may introduce inductive bias and limit generalization.\n\nThat said, our method can be readily extended to incorporate sequential consistency and potentially improve completeness. For example, instead of independently sampling 50 random walks of length 8, one could generate a **single long walk of length 400** and split it into 50 segments. This approach would naturally preserve **sequential continuity** between substructures and could help retain attachment context across sampled patterns.\n\nWe acknowledge that our current approach may not fully capture all attachment relationships between substructures, and we will include a discussion of this limitation—and possible extensions—in the revised **Limitations** section of the paper.\n\n> Q3: Limited benefit of cross-domain pretraining\n> \n\nThank you for raising this concern. We believe there may be a misunderstanding regarding the datasets referenced in Table 3 and Table 5. Although both refer to **HIV**, they are **different versions** of the dataset.\n\n- In **Table 3**, the HIV dataset is the **standard version** that includes **atom properties as features**.\n- In **Table 5**, the HIV dataset includes **textual node attributes**, where nodes are annotated with **textual descriptions** and features are derived from a **text encoder**.\n\nTherefore, there is naturally a performance gap between these two tables. For a fair comparison, we adopt the dataset used in Table 5 to evaluate whether the cross-domain pretraining can enhance model performance. In particular, we pretrain G²PM using **only the HIV dataset** and the model achieves **72.1 AUC**. In contrast, when we apply **cross-domain pretraining** using three datasets (in Table 5), the performance improves to **74.1 AUC**. This clearly demonstrates that cross-domain pretraining **does enhance model performance**, even under domain shift. We will clarify this distinction in the paper to avoid confusion.\n\n> Q4: Is it possible to extend this framework to graph generation tasks?\n> \n\nYes, our framework can be naturally extended to support graph generation, and we envision two promising directions:\n\n1. **Autoencoder-style generation:** G²PM can serve as a powerful **feature encoder** within a standard graph generation pipeline, such as graph autoencoders or diffusion-based models. A straightforward approach is to feed a graph into G²PM to obtain a latent graph representation, and then use a **decoder module** (e.g., GNN or MLP) to reconstruct the graph structure.\n2. **Autoregressive generation:** A more exciting extension is to adapt G²PM for **autoregressive generation**. Instead of using random walks, we could apply traversal strategies like **DFS or BFS** to generate a long sequence of nodes, which is then split into substructure segments. The model is trained to **predict the next segment** conditioned on the previous ones, effectively learning to reconstruct the original traversal sequence. Since traversal sequences (e.g., DFS/BFS) contain sufficient structural information to reconstruct the original graph, this approach allows G²PM to be naturally adapted for **graph generation tasks**.\n\nBoth directions align well with the substructure-based design of G²PM and open the door for future work on generative modeling. We appreciate the reviewer for suggesting this valuable extension."}, {"review_id": "0x5DwjgxZI", "reviewer": "Reviewer_85SU", "summary": "This paper introduces G²PM (Generative Graph Pattern Machine), a Transformer-based framework for graph representation learning that bypasses traditional message-passing GNNs. G²PM tokenizes graphs into sequences of substructures (via random walks) and employs masked substructure modeling (MSM) for generative pre-training. The method demonstrates scalability, outperforming existing approaches on tasks like node classification, graph classification, and cross-domain transfer.", "questions": "1- You use a fixed tokenizer based on random walks. Would a learnable tokenizer—such as one trained via reinforcement learning or self-supervision—further improve performance?\n\n2- For billion-edge graphs, what modifications would make G²PM practical (e.g., graph sampling, attention approximations)?\n\n3- The paper relies on random walks for substructure extraction, which have known limitations in capturing certain graph properties. How does G²PM address scenarios where key higher-order patterns (like large cliques or complex cycles) aren't sufficiently captured by walk-based sampling?\n\n4- Could you provide more insight into why positional embeddings show no benefit in your framework?", "limitations": "---", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n\n1- The study presents a comprehensive experimental evaluation, encompassing:\n    - node classification benchmarks, including large-scale datasets like OGBN-ArXiv\n    - graph classification tasks spanning molecular and social networks\n    - Cross-domain transfer experiments\n    - In-depth ablation studies\n\n2- The results demonstrate consistent performance improvements with model scaling, achieving gains up to 60 million parameters—supporting the paper’s core hypothesis.\n\n\nWeaknesses:\n\n1- Theoretical Foundations: Although the empirical results are compelling, the theoretical underpinnings could be strengthened through: \n   - formal examination of the expressive power of substructure sequences \n   - theoretical analysis comparing the approach to message-passing methods\n\n2- Computational Efficiency: Several key aspects related to scalability are not thoroughly addressed: \n   - The memory consumption when applied to large graphs \n   - The computational overhead compared to message-passing baselines \n   - How the length of walks affects overall computational cost\n\n3- The Related Work section lacks a clear and explicit discussion of how G²PM fundamentally differs from and advances beyond previous substructure-based approaches in a way that highlights its unique contributions.", "was_revised": true, "final_justification": "My questions and concerns were resolved.", "rebuttal": "Dear reviewer, \n\nWe sincerely thank the reviewer for the detailed and thoughtful evaluation of our work. We appreciate the recognition of G²PM’s comprehensive experimental validation, its consistent scalability, and its strong performance across node classification, graph classification, and cross-domain transfer tasks. We aim to clarify our contributions, address the scalability and expressiveness of G²PM in more detail, and respond to specific questions around tokenizer design, walk limitations, positional embeddings, and deployment at billion-edge scale.\n\n> Q1: The theoretical underpinnings could be strengthened through: (1) formal examination of the expressive power of substructure sequences; (2) theoretical analysis comparing the approach to message-passing methods\n> \n\nThank you for highlighting this important point. Our primary goal in this work is to develop a simple yet effective GNN approach, with a focus on empirical analysis to demonstrate scalability across model sizes and data volumes. **This design philosophy follows a trend seen in NLP and CV, where the scalability of GPT and ViT is primarily established through empirical performance rather than theoretical guarantees**. That said, we appreciate the reviewer’s suggestion and agree that incorporating additional theoretical analysis could further strengthen our work. Fortunately, both of the reviewer’s questions can be addressed through a shared lens: by examining the expressive power of random-walk-based representations.\n\nThere is already a rich body of theoretical work showing that **random walk-based methods can be more expressive than message-passing neural networks (MPNNs)** under mild assumptions. For example, the GPM [1] (see Theorem 3.4) demonstrates that, under the *reconstruction conjecture*, random walk-based approaches can distinguish all pairs of non-isomorphic graphs, provided a sufficient number of walks are sampled. In essence, random walks capture enough structural information to uniquely characterize a graph, enabling discrimination between graphs that message-passing methods may fail to distinguish. Furthermore, Corollary 3.5 in GPM [1] shows that for any k ≥ 1, there exist graphs that can be distinguished by random walks of length k, but not by the **k-WL isomorphism test**, which bounds the expressive power of many MPNN variants. \n\nOur G²PM framework, which operates on substructures extracted via random walks, can thus inherit this theoretical advantage, **assuming a sufficient number of substructures are sampled**. We believe that these established theoretical frameworks can be directly extended to G²PM with relatively mild assumptions, further emphasizing the expressiveness advantage of G²PM over MPNN. \n\n[1] Beyond Message Passing: Neural Graph Pattern Machine, ICML 25. \n\n> Q2: Several key aspects related to scalability are not thoroughly addressed\n> \n\nThank you for raising these important points. Before addressing them individually, we would like to clarify that our use of the term **scalability** primarily refers to *scaling laws,* i.e., the ability of the model to benefit from larger datasets and model sizes, as demonstrated in our experiments. Nonetheless, we agree that discussing computational efficiency is important for practical understanding, and we address each sub-question below:\n\n**Q2.1: Memory consumption when applied to large graphs**\n\n**A2.1:** Memory usage is well-managed in G²PM through the use of **mini-batching**, which allows training on large-scale graphs. For instance, given a graph with 2,000 nodes and a mini-batch size of 100, we process only 100 nodes per batch, sampling substructures, encoding them, and computing losses independently. This approach scales efficiently: in our experiments, G²PM handles graphs with over **2 million nodes and 100 million edges** using a single **NVIDIA A40 GPU (48GB)**. We also verified that training can be conducted on a **NVIDIA 3090 (24GB)** by reducing the batch size.\n\n**Q2.2: Computational overhead compared to message-passing baselines**\n\n**A2.2:** We acknowledge that G²PM, being Transformer-based, is computationally more intensive than traditional message-passing methods. For example, on the **ogbn-arxiv** dataset, G²PM with 60M parameters takes approximately **8,000 seconds** for pretraining, while **GraphMAE** (with 3M parameters) takes about **2,000 seconds**. \n\nHowever, this additional cost is incurred only during the **offline pretraining phase**, which is performed once. In many real-world scenarios, the **learned embeddings are directly reused** for downstream tasks without requiring further inference through the model, making the computational overhead largely irrelevant in practice.\n\n**Q2.3: Impact of walk length on computational cost**\n\n**A2.3:** Walk length directly affects both the **size of substructures** and the computational load. Longer walks generate larger substructures, which increase both memory and compute requirements. However, longer walks do not always yield better performance—excessively long walks may introduce noise and reduce accuracy. The table below shows that **walk length = 8** offers a good trade-off between performance and efficiency.\n\n| **ogbn-arxiv** | **Length=4** | **Length=8** | **Length=16** |\n| --- | --- | --- | --- |\n| **Pretrain Time (s)** | ~6,000 | ~8,000 | ~12,000 |\n| **Accuracy** | 71.4±0.2 | **72.3±0.1** | 72.1±0.2 |\n\n> Q3: How G²PM fundamentally differs from other substructure-based approaches.\n> \n\nIn short, G²PM is not just another substructure-based method. It represents a shift in paradigm from enhancing local expressiveness to enabling scalable, generative pretraining over graphs. We provide detailed discussions as follows. \n\n- **A New Perspective:** G²PM introduces a *generative modeling framework* over substructures for graph pretraining, aiming to achieve **scalability in both model size and data volume**. While Transformer-based pretraining and scaling laws are well studied in NLP and CV, this direction remains underexplored in graph learning. In contrast, prior substructure-based methods primarily focus on enhancing model **expressiveness**, specifically addressing the limitations of message-passing in encoding complex substructures. Our approach is orthogonal: it leverages substructures not just for expressiveness but as the foundation for scalable, generative representation learning.\n- **Simple Yet Effective Design:** G²PM offers a simple yet effective implementation of the generative modeling concept. It demonstrates that **strong scalability can be achieved without introducing overly complex architectural components**, in contrast to many prior works relying on complicated model design that fail to achieve scalability.  \n- **Scalability in Practice:** Despite its conceptual simplicity, G²PM demonstrates **remarkable scalability**. It successfully scales up to **60M parameters**, significantly outperforming substructure-based or message-passing-based methods like GraphMAE, which tend to saturate at ~3M parameters. This ~20× parameter gap illustrates the practical limitations of existing approaches when applied to larger models and datasets, an area where G²PM excels.\n\n> Q4: Why is the tokenizer fixed in the model? Would a learnable tokenizer further improve performance?\n> \n\nThe primary motivation for using a fixed tokenizer is to maintain a **simple yet effective** model design. Despite being fixed, our tokenizer still offers a degree of **adaptability**. The random walk-based substructures are encoded by a Transformer, which can internally learn to focus on informative regions within each walk. In this sense, the model can implicitly identify **sub-substructures** within each sampled sequence, enabling meaningful representation learning even without a learnable tokenizer.\n\nThat said, we agree that **learnable or adaptive tokenizers** represent a promising direction for future improvement. Such approaches could tailor the substructure sampling process to better suit different graph domains. For example, one could employ **reinforcement learning** to adapt the p and q parameters of the random walk strategy based on the graph type—favoring short, localized walks (small p, large q) for social networks, and longer-range walks (large p, small q) for molecular graphs.\n\n> Q5: What make G²PM practical on billion-edge graphs?\n> \n\nIn short, we use mini-batching to enable the model to scale to billion-edge graphs. Due to the space limitation, please refer to Q2.1 for details.\n\n> Q6: How does G²PM address scenarios where key higher-order patterns aren't sufficiently captured by walk-based sampling?\n> \n\n\nG²PM addresses this by **increasing the walk length**, which improves the likelihood of covering complex patterns. For instance, on the PCBA molecular dataset, using a walk length of 16, G²PM achieves **75.6 AUC**, outperforming the best generative baseline (73.2 AUC), indicating its ability to approximate higher-order structures.\n\nThat said, random walks cannot guarantee full coverage of complex patterns. While using a **predefined vocabulary** of substructures could improve coverage, it introduces high computational cost and requires domain expertise. In contrast, our random walk-based approach is **efficient, domain-agnostic**, and scalable, offering a practical trade-off between expressiveness and efficiency.\n\n> Q7: Could you provide more insight into why positional embeddings show no benefit in your framework?\n> \n\nG²PM treats substructures, not individual nodes, as tokens. The model’s goal is to identify and learn from informative patterns, rather than relying on the exact positions of nodes in the graph. In this setting, global node positions become less relevant, as the focus shifts to the semantic contribution of substructures. As a result, incorporating node-level positional embeddings has minimal impact on performance within our framework."}]

Author rebuttal:

Meta-review: Summary:
This paper addresses the challenge of scalable graph generative modeling by introducing the Generative Graph Pattern Machine, a pre-training framework that adapts the Transformer architecture for graphs. This approach represents graph instances—including nodes, edges, and entire graphs—as sequences of substructures, then uses generative pre-training over these sequences to learn transferable, generalizable representations. Experiments on multiple datasets demonstrate the effectiveness of the proposed model.

Strengths:
1. The paper is well-structured and easy to follow.
2. The authors conduct a comprehensive set of ablations and experiments.
3. The work is grounded in a clear need to improve the effectiveness of Transformer-based models on graphs. The integration of substructures into a sequential modeling framework is a conceptually novel idea.


Weaknesses:
1. Some experimental aspects could be improved. For instance, the scalability experiment in Figure 2 would benefit from evaluating larger model sizes. Including a link prediction task would also be valuable, as it is a widely considered task.
2. The paper should discuss the trade-off between the cost of the self-supervised pre-training step and the resulting performance improvements.
3. A more thorough discussion of prior work on graph-to-sequence representations is required to strengthen the related work section.


In summury, this paper propose a novel pretraining framework on graph learning, which is different from the most utilized message-passing paradigm. New paradigms are driving force to the graph learing area. The experiments also show the effectiveness of the proposed model. I recommend the authors to address the minor issues in the camera ready version.
Decision: Accept (poster)