Beyond Message Passing: Neural Graph Pattern Machine
Authors: Zehong Wang
Zheyuan Zhang
Tianyi Ma
Nitesh V Chawla
Chuxu Zhang
Yanfang Ye
Venue: ICML 2025 poster (2025)
Keywords: Graph Learning
Supervised Learning
Substructures
Graph Pattern
Primary area: deep_learning->graph_neural_networks

Abstract: Graph learning tasks often hinge on identifying key substructure patterns---such as triadic closures in social networks or benzene rings in molecular graphs---that underpin downstream performance. However, most existing graph neural networks (GNNs) rely on message passing, which aggregates local neighborhood information iteratively and struggles to explicitly capture such fundamental motifs, like triangles, $k$-cliques, and rings. This limitation hinders both expressiveness and long-range dependency modeling. In this paper, we introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures. GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies. Empirical evaluations across four standard tasks---node classification, link prediction, graph classification, and graph regression---demonstrate that GPM outperforms state-of-the-art baselines. Further analysis reveals that GPM exhibits strong out-of-distribution generalization, desirable scalability, and enhanced interpretability. Code and datasets are available at: https://github.com/Zehong-Wang/GPM.

Beyond Message Passing:
Neural Graph Pattern Machine
Zehong Wang'
Zheyuan Zhang'
Tianyi Ma
Nitesh V Chawla' Chuxu Zhang? Yanfang Ye
Abstract
graph classification task, where atoms and bonds are rep- resented as nodes and edges, respectively (Hu et al., 2020). In e-commerce, predicting user preferences naturally trans- lates into link prediction on user-item interaction graphs (Ying et al., 2018). A key insight of these tasks is that the certain substructures encode meaningful inductive biases (Xu et al., 2019; Zhao et al., 2022), emerging as predictive patterns. For instance, triadic closure, where three nodes form a closed triangle, is ubiquitous in social, biological, and communication networks (Granovetter, 1973). It serves as an indicator of stable node relationships and is instrumen- tal in tasks like node classification (Jin et al., 2020) and link prediction (Huang et al., 2015). In molecular graphs, the benzene ring-a six-carbon cyclic structure-is canoni- cal example of a stable substructure with implications for chemical reactivity (Rong al., 2020). We refer to such recurring substructures, including triangles, rings, and other motifs, as substructure patterns or graph patterns. These patterns form the building blocks of graph semantics and are central to understanding and improving performance in graph-based learning tasks.
Graph learning tasks often hinge on identify- ing key substructure patterns-such as triadic closures in social networks or benzene rings in molecular graphs- that underpin downstream per- formance. However, most existing graph neu- ral networks (GNNs) rely on message passing, which aggregates local neighborhood informa- tion iteratively and struggles to explicitly cap- ture such fundamental motifs, like triangles, k- cliques, and rings. This limitation hinders both expressiveness and long-range dependency mod- cling. In this paper. we introduce the Neural Graph Pattern Machine (GPM), novel frame- work that bypasses message passing by learn- ing directly from graph substructures. GPM ef- ficiently extracts, encodes, and prioritizes task- relevant graph patterns, offering greater expres- sivity and improved ability to capture long-range dependencies. Empirical evaluations across four standard tasks node classification, link predic- tion, graph classification, and graph regression demonstrate that GPM outperforms state-of-the- art baselines. Further analysis reveals that GPM exhibits strong out-of- -fflo-f-bititutiinnn generalization. desirable scalability, and enhanced interpretabil- ity. Code and datasets are available at: https: //git com com//ehong Zehong Wang/GPM
Despite the critical role of substructure patterns in graph learning, most graph neural networks (GNNs) (Kipf & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018) operate under the message passing paradigm (Gilmer et al., 2017), which iteratively aggregates local neighborhood in- formation rather than directly modeling graph substructures. While message passing GNNs have demonstrated strong empirical performance on tasks such as node classification, link prediction, and graph classification, numerous stud- ies (Xu et al., 2019; Verma & Zhang, 2019; Garg al., 2020; Chen et al., 2020; Tang & Liu, 2023; Zhang et al., 2024a) highlight their inherent limitations in capturing ba- sic patterns like triangles, stars, and k-cliques, owing to their equivalence to the I-dimensional Weisfeiler-Leman (I-WL) test (Xu et al., 2019). To address these limitations, various enhancements have been proposed, including po- sitional encodings (Murphy et al., 2019; Loukas, 2020), graph transformers (Kreuzer et al., 2021; Rampasek et al., 2022), and higher-order GNNs (Morris et al., 2019; Zhao et al., 2022; Qian et al., 2024; Ma et al., 2025b), which ex- tend expressiveness beyond 1-WL. However, these methods remain fundamentally tied to message passing, and often suffer from challenges such limited interpretability, high
1. Introduction
Graphs serve as a fundamental abstraction for modeling complex systems across domains such as social networks, drug discovery, and recommender systems (Zhang et al., 2024c;d; Ma al., 2025a; Zhang et al., 2024b; Ma al., 2023; Fu al., 2023). Many real-world problems can be formulated as classification regression tasks graphs. For example, molecular property prediction can be cast as
University of Notre Dame Uniiversity of Connecticut. Corre- spondence to: Zehong Wang 2owaag43@nd.edoe Yanfang Ye <yye7 @oc7@nd edu>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Beyond Message Passing: Neural Graph Pattern Machine
Social Networks
Triangle
(Node)
Important Puttern Identifier
Wikipedia Networks (Link)
Pattem Sampler
Pattern Encoder
Connectivity
Molecule Graphs
Motif
(Graph)
Any Graph Data with Different Tasks
Sampling Patterns by Random Walks
Encoding Patterns by Sequenrial Models
Identifying Most Relevant Patterss via Self-Attenton
Potential Pattems Dominaring Certain Tasks
The workflow of Neural Graph Pattern Machine (GPM), Given a graph dataset, GPM utilizes random walk tokenizer to extract a set patterns representing the learning instances (nodes, edges, or graphs). These patterns are first encoded by a sequential model and then processed by transformer encoder, which identifies the dominant patterns relevant to downstream tasks.
Figure 1.
computational cost, and biased inductive assumptions.
matches a particular graph pattern (proved in Section 3.1). By leveraging this insight, we model graph patterns by sep- arately encoding the semantic paths and anonymous paths of the corresponding walks, thereby comprehensively cap- turing the preserved graph inductive biases. The encoded graph patterns are then fed into a transformer layer (Vaswani et al., 2017) that identifies the important patterns dominating downstream tasks. To provide deeper understanding the superiority of GPM over message passing, we demonstrate that GPM can distinguish non-isomorphic graphs that GNNs cannot identify and can model long-range dependencies that GNNs fail to capture. Furthermore, we conduct extensive experiments on node-, link-, and graph-level tasks to demon- strate that GPM is applicable various graph tasks and outperforms state-of-the-ar baselines. Our experimental results also show that GPM is robust to issues, and can be readily scaled to large graphs, large model sizes, and distributed training. In addition, the mechanism for identifying dominant substructures enables GPM to have desirable model interpretability.
To go beyond the message passing, recent research has be- gun exploring the use of graph patterns as discrete tokens to represent nodes, links, or entire graphs. While promising, this line of work is still its early stages and faces three key challenges. (1) Universal Graph Tokenizer: Extracting graph patterns requires tokenizer that can adapt to node-, link-, and graph-level tasks. Unlike sentences and images, which inherently have sequential structures, tokenizing graph instances is challenging due to their non- Euclliddn nature. Existing tokenizers tend to be task-specific, such as the Hop2token tokenizer (Chen et al., 2023) for node tasks and the METIS tokenizer (He et al., 2023) for graph tasks. (2) Effective Pattern Encoder: The model must ef- ficiently and comprehensively encode the extracted graph patterns. Current approaches often use message passing as a pattern encoder (Chen et al., 2022: He et al., 2023; Behrouz& & Hashemi, 2024) or auxiliary module (Behrouz & Hashemi, 2024) to provide graph inductive biases. However, the limited expressiveness of message passing in identifying basic substructures leads information loss in encoding graph patterns. (3) Important Pattern Identifier: As the sampled patterns may be duplicated or noisy, it is crucial to identify the most relevant patterns for downstream do- mains. For example, in social networks that favor localized patterns, the model should emphasize patterns that preserve local information. However, existing methods are gener- ally evaluated on benchmarks with long-range dependencies (Dwivedi et al., 2023; 2022; Platonov et al., 2023); their effectiveness graphs favoring localized or mixed depen- dencies remains unclear.
2. Related Works
Expressive Bottleneck of Message Passing. Traditional message passing GNNs (Kipf & Welling, 2017; Hamilton et al., 2017: Veličković et al., 2018) suffer from well-known issues, particularly on limited expressiveness. Their ex- pressiveness is fundamentally bounded by the 1-WL. test (Xu et al., 2019; Corso al., 2020), which restricts the ability to distinguish basic structures such as stars, cycles, and cliques (Chen et al., 2020; Garg et al., 2020; Zhang et al., 2024a; Qian et al., 2025). To address this limitation, three main research directions have emerged. First, expres- sive GNN variants enhance the message passing framework by incorporating higher-order structure encodings (Maron et al., 2019a; Bouritsas et al., 2022) and node positional embeddings (Murphy al., 2019; Loukas, 2020), but often suffer from scalability challenges (Azizian & mare lelarge, 2021). Second, random walk-based approaches (Zhang
To address these challenges, we introduce the Neural Graph Pattern Machine (GPM), where the workflow is illustrated in Figure We design random walk-based tokenizer to sample graph patterns, which is computationally efficient (Grover & Leskovec, 2016) and can be naturally adapted to various tasks. The key insight is that the combination of semantic path and anonymous path of a random walk
2

---

Beyond Message Passing: Neural Graph Pattern Machine
(a) Training GPM on graphs
(b) Tokenization via Random Walks
(exemplified by node classification)
Rundom Walks
Graph Pattern
Semantic Path
Predict Head
Predictions
Random
Conceptually Iquuals
Sampling
Anonymous Path
Transformer Encoder
[class] Token
(c) Pattern Encoding via Sequential Models
Node Feature
Edge Feature
D
Node PE (optional)
Loop-based Adjaceney
Pattern Encoder (e)
Semantic Path
Sequential Encoder
0
Anonymous Path
Eneader
Tokenization (b)
Figure 2. The overview framework of GPM.
al., 2019; Fan et al., 2022; Jin et al.. 2022; Wang & Cho, 2024) improve long-range modeling (Welke et al., 2023), but often sacrifice local pattern understanding (Tönshoff et al., 2023). Third, graph transformers (Kreuzer et al., 2021; Ying et al., 2021) utilize global attention to capture arbitrary node dependencies and exceed WL. expressiveness, but incur quadratic complexity, limiting scalability to large graphs (Wu et al., 2023). While these approaches extend message passing in expressiveness, they are often imple- mented as extensions complements the message pass- ing, failing directly and effectively model graph patterns. This observation motivates the need for fundamentally different approach, as pursued in this work. A more detailed discussion is provided in Appendix A.
(Zhao et al., 2022), and GraphMamba (Behrouz & Hashemi, 2024) propose task-agnostic tokenization methods. How- ever, these methods often rely message passing either as the pattern encoder or an auxiliary module, inheriting the limitations of message passing, While the aforementioned methods have shown empirical success, none fully meet our criteria: (1) a universal graph tokenizer, (2) an effective pattern encoder, and (3) the ability to identify important patterns relevant downstream tasks. Our proposed GPM overcomes these challenges.
3. Neural Graph Pattern Machine
Let G = (V, E, X, E) denote a graph, where V is the set of nodes with | = N, S V x V is the set of edges with [ = E, and X and represent the node and edge feature matrices, respectively. Each node feature vector x, Rd, and each edge E is associated with feature vector E Rdd (if applicable). We define graph patterns subgraphs that represent small, recurring substructures, such as triangles, stars, cycles, etc.
Early methods for leveraging graph patterns often relied on primitive training paradigms. For instance, DGK (Yanardag & Vishwanathan, 2015) uses graph kernels to measure relationships between (substruc- ture) patterns, while AWE (Ivanov & Burnaev, 2018) em- ploys anonymous random walks to encode pattern distribu- tions in graphs. More recent approaches tokenize graphs into sequences of substructures. Graph (He et al., 2023), for example, splits graph into multiple subgraphs using graph partitioning algorithms (Karypis, 1997), encodes each subgraph individually via message passing, and aggregates the resulting embeddings to represent the entire graph. Sim- ilarly, GMT (Baek et al., 2021) decomposes nodes into a multiset, with each set representing a specific graph pattern. However, these methods are limited to graph-level tasks. On the other hand, NAGphormer (Chen et al., 2023) and GC- Former (Chen al., 2024) utilize Hop2token and neighbor- hood sampling, respectively, to tokenize patterns represent- ing individual nodes; Yet, they are tailored for node-level tasks. To address this, SAT (Chen et al., 2022), GNN-AK
Graph Patterns as Tokens.
is associated with
3.1. Pattern Tokenizer
Tokenization is an essential step for converting a given in- stance into a sequence of patterns. Existing methods typ- ically rely on pre-defined strategics. For example, large language models (LLMs) employ pre-defined vocabularies (Brown et al., 2020) decompose sentence into se- quence of tokens, where each token represents concept entity. Similarly, vision transformers use patch tokenizers to partition an image into a sequence of grids (Dosovitskiy et al., 2021). However, universal tokenizer for graphs has yet to be established. straightforward approach is to construct a unified substructure vocabulary via efficient sub-
3

---

Beyond Message Passing: Neural Graph Pattern Machine
Target Graph
Random Walks
Anonymous Walks
walk "A-C-E-D-A" maps to the anonymous path "0-1-2-3-0," which represents a rectangle-shaped substructure. Note refer the original random walks semantic paths.
Same
Recent findings (Micali & Zhu, 2016; Ivanov & Burnaev, 2018) have demonstrated that the distribution of anonymous paths originating from a node v is sufficient to reconstruct the subgraphs induced by all nodes within a fixed distance from v. Consequently, we state the following proposition, establishing that anonymous paths encapsulate sufficient topological information to describe each node.
Different
Proposition 3.2. (Informal) Given node u E V, assume the task requires information from the k-hop ego-graph B( k)) = (V', E"), A sufficiently large set of patterns, sam- pled via l-length anonymous walks with 1 = O(EE') can provide distinguishable topological representations.
Figure 3. Examples of anonymous paths.
graph matching (Sun et al., 2012), and then use this vocabu- lary to describe patterns for each instance (e.g., node, edge, or graph). However, the vocabulary construction and pattern matching are obviously inefficient and cannot scale well to large graphs. To address this challenge, GPM bypasses the need for an explicit fixed vocabulary by approximating the pattern matching process via random sampling.
The proof is sketched in Appendix C.I. This proposition demonstrates that the distribution of anonymous paths start- ing from a node is sufficient to capture its topological proper- ties. Naturally, two nodes and v can be considered to share similar graph patterns their anonymous path distributions are similar. This proposition can be extended to links and graphs by treating them as combinations of nodes, with the corresponding distributions. Thus, for each random walk, we can derive both semantic path (capturing node features) and an anonymous path (capturing topological structures), where their combination conceptually represents a certain graph pattern. Then, we have the proposition.
The task now is sample patterns that effectively describe graph instances. Ideally, the sampling process should be efficient and produce diverse patterns to enable scalability for large graphs. To achieve this, we propose leveraging random walks for sampling graph patterns. An (unbiased) random walk w (length I.) is defined as node sequence w- = -vo, Ui...., UL), generated via a Markov chain:
Proposition 3.3. (Inorrmal) Jointly encoding semantic paths and anonymous paths via any bijective mappings pro- vides a comprehensive representation of the graph inductive biases encapsulated in the corresponding graph pattern.
P(u++1| | vo....,,y) m.) = [(( 1++1) E &)/D(u), (1)
where D(v)) represents the degree of node us Utilizing this landing probability, it becomes straightforward to generate sequence of random walks starting at node v.
This proposition, proved in Appendix C.2, implies that graph patterns can be effectively encoded by combining the individually encoded semantic and anonymous paths.
Next, we discuss why this basic strategy is effective for sampling graph patterns and demonstrate that each random walk inherently depicts a unique graph pattern. Before delving into this, we introduce the concept of anonymous walks (Ivanov& & Burnaev, 2018).
Applicability to Graph-based Tasks. The method is capa- ble of tokenizing nodes, edges, and graphs. For node-level tasks, the tokenizer samples & patterns for node v. For edge-level tasks, the tokenizer samples & patterns starting from the endpoints u and v of an edge (u, v). For graph- level tasks, the tokenizer samples k: patterns for each graph by randomly selecting starting nodes within the graph.
Definition 3.1 (Anonymous Walk (Ivanov & Burnaev, 2018)). Given random walk (vo, uI...., UL), its corresponding anonymous walk is defined as sequence of integers @ = =70. ......, YL), where % = min pos(w, et). The mapping from the random walk to its anonymous path represented by w + d.
3.2. Pattern Encoder
Anonymous walks encode random walks as sequences of relative positions, preserving anonymity by avoiding the explicit recording of specific nodes. Each anonymous walk thus captures unique graph topology pattern. For instance, as illustrated in Figure 3, the random walks "A-B-C-A-D" and "C-D-E-C-A" both correspond to the same anonymous path "0-1-2-0-3," representing a triangle-shaper substruc- ture with an additional connection, In addition, the random
As discussed above, any graph pattern can be represented as the combination of a semantic path and an anonymous path. Given a graph pattern, let the semantic path be w (Up,.... vn) and the anonymous path be & = (....... These paths are encoded separately using two distinct en- coders, which are combined to form the pattern embedding:
p = pa(w) + X Pa (a())
(2)
4

---

Beyond Message Passing: Neural Graph Pattern Machine
where p denotes the pattern embedding, Ps and Pe are the encoders for the semantic path and the anonymous path, respectively, and À is a weighting coefficient.
In this work, we adopt GRU as the default encoder due to its balance of expressiveness and computational efficiency.
3.3. Important Pattern Identifier
Semantic Path Encoder. To encode the semantic path, we construct a sequence of node features according to the semantic path as Bo.....,nnJ,. where nodes may appear multiple times. The encoder Ps can be any model capa- ble of processing sequential data. By default, we use the transformer encoder due to its superior expressiveness in capturing long-range dependencies. The alternatives can be mean aggregator or GRU (Chung et al., 2014). The encoding process is defined as:
For each graph instance, we use set of encoded patterns P = ................................ ... to describe its characteristics. Since the patterns are randomly sampled from the graph, it is essen- tial to identify the most relevant patterns for downstream tasks. To achieve this, we employ a transformer encoder to highlight the dominant patterns by learning their relative importance. The encoding process is defined as follows:
Q = P K= PPWK.
V =PW,,
(6)
(3) where- x = |x: || el represents the concatenation of node features a: and optional edge features e (if applicable). Note that in a path, the number of edges is one less than the num- ber of nodes. To address this mismatch, edge features are padded with a zero vector at the beginning of the sequence.
Ps (ww) = Po hnl), h = Wa, + b,,
(QK)
(P) = softmax
V E Buxdout
ddout
p' = FFN(P + Attn P)).
(8)
where WQ. WK. Wy are trainable parameter matrices, dout is the dimension of the query matrix Q. and FFN represents a two-layer MLP. We utilize multi-head attention, which has proven effective in practice by concatenating multiple attention mechanisms. Additionally, multiple trans- former layers can be stacked to further enhance the capacity.
Node Positional Embedding. To incorporate advanced topological information, it is optional to concatenate node positional embeddings (PEs) with the node features. This approach has been shown to be effective to enhance model expressiveness (Kreuzer et al., 2021; Rampasek et al., 2022; He et al., 2023; Chen et al., 2023). The augmented node features are represented as:
Let P' = ( P'm) denote the output of the final trans- former layer. These outputs are aggregated for downstream predictions using an additional prediction head:
[x e,1, || ax),
(4)
X72
ÿ Head
P
where æ, denotes the node features, 6,-1,5 represents op- tional edge features, and a, refers to the optional positional embedding. In this work, we utilize widely adopted PEs, in- cluding random-walk structural embeddings (RWSE) (Ram- pasek et al., 2022) and Laplacian eigenvector embeddings (Lap) (Kreuzer et al., 2021). Empirically, we observe that the choice of PE depends on the dataset. Notably, the model can still achieve competitive performance even without the positional embeddings.
m
where Head is a linear prediction layer. A mean readout function is applied over all pattern embeddings to compute the instance embedding, which is then used for prediction.
Class Token For improved interpretability, a class to- ken Pets can be appended to the sequence of pattern em- beddings before transformer encoding, such that P [peis: po...., Pmm) The downstream prediction is then based solely on the encoded class token, modifying Equation 9 as ÿ = Head(p'ate) This approach evaluates the signif- icance of individual graph patterns for downstream tasks based on the attention scores on the class token. Note that the primary purpose of using the class token to enhance interpretability rather than to improve model performance, although it may also serve as an efficient summarization of the entire pattern set (Dosovitskiy et al., 2021).
Anonymous Path Encoder. For anonymous path ő (70...., 7n), we adopt similar approach to encode the path as used for semantic paths, with key distinction: anony- mous nodes lack explicit features. Instead of employing one-hot encoding for each anonymous index, inspired by Tönshoff et al. (2023), we utilize an advanced method that encodes both anonymous indices and connectivity infor- mation. Specifically, for anonymous path of length k, each node 14 is assigned k-dimensional vector 2,, where Zi,- 177 75]- This encoding not only captures identity information but also encodes loop structures. We refer to this representation as loop-based adjacency. Consequently, any anonymous path can be expressed as Φ = [zo...., zn); which can then be processed using encoder Pa:
3.4. Training Strategies
Test-Time Augmentation. For single instance, we select k patterns to represent its characteristics, where empiri- cal evidence suggests that a larger k generally improves performance. However, increasing imposes additional computational costs, as the self-attention has quadratic
Pa (Ø) = Pa ((z0...... zn))-
(5)
5

---

Beyond Message Passing: Neural Graph Pattern Machine
time complexity with respect the input length, OA.²). In- spired by test-time scaling in LLMs (Snell al., 2024), we address this trade-off by training the model with yn patterns and using k patterns during inference, where k > m. By default, we set m = 16 and k = 128. To further reduce the computational overhead of pattern sampling, we pre-sample patterns during preprocessing and randomly select m pat- terns during training. The time consumption minimal, taking less than 10 seconds on most datasets. Even for the largest dataset used (~2,500,000 nodes), the sampling time remains under 2 minutes on an Nvidia A40 GPU.
rior capability in modeling long-range interactions. Follow- ing He et al. (2023), evaluate this capability using the TREENEIGHIBORSMACCIII
(Alon & Yahav, 2021). Our GPM perfectly fits the data with task radius up to 7, yet message passing methods exhibit over-squashing effects as early as task radius 4 (Appendix E.2).
4. Experiments
4.1. Applicability to Graph-based Tasks
To evaluate the effectiveness of our method on all graph predictive tasks (node, link, and graph), we conduct exten- sive experiments such as node classification, link prediction, graph classification, and graph regression.
Multi-Scale Learning. Recent studies have demonstrated the effectiveness of multi-scale learning across various do- mains (Liao et al., 2019; Chen et al., 2021). Inspired by the success of multi-scale learning in visual transformers (Chen et al., 2021), which process small and large patch tokens within single model, we propose sampling pat- terns of varying sizes. Specifically, during tokenization, we sample patterns with lengths (2. instead of using a fixed length I. By default, the multi-scale lengths are set to [2, 4, 6, 8). Note the number of patterns remains unchanged. Additional implementation details are in Appendix B.
Node Classification. We conduct experiments on bench- mark datasets of varying scales, with their statistics and ho- mophily ratios summarized in Table 1. The datasets include Products, Computer, Arxiv, WikiCS, CoraFull, Deezer, Blog, Flickr, and Flickr-S (Small). We adopt the dataset splits from Chen et al. (2023) and Chen et al. (2024); public splits for WikiCS, Flickr, Arxiv, and Products; 60/20/20 train/valltest split for CoraFull and Computer; 50/25/25 split for the remaining datasets. Accuracy used as the evaluation metric. The baselines include message passing GNNs (GCN, GAT, APPNP, GPR-GNN OrderedGNN), random walk-based GNNs (RAW-GNN, RUM), and graph transformers (GraphGPS, SAN, NodeFormer, GOAT, NAG- phormer, GraphMamba, VCR- VCR-Graphormer, and GCFormer). As presented in Table 1, our GPM consistently outperforms message passing GNNs and random walk-based GNNs across all datasets. When compared to graph transform- ers specifically designed for node classification, our method achieves superior performance most datasets, with the exception of CoraFull. Although NAGphormer slightly out- performs GPM on CoraFull, its Hop2Tokenn mechanism constraints the method on node-level tasks.
3.5. How Does GPM Surpass Message Passing?
Advancing Expressivity. Message passing frameworks can distinguish non-isomorphic graphs that are distinguish- able by the 1-WL isomorphism test (Xu et al., 2019). We demonstrate that GPM surpasses message passing in pressiveness under the following mild assumptions: (1) the graphs are connected, unweighted, and undirected, and (2) the number of sampled patterns is sufficiently large.
Theorem 3.4. Under the reconstruction conjecture assump- tion, GPM can distinguish all pairs of non non-isomorphic graphs given sufficient number of graph patterns.
The proof is sketched by first demonstrating the expressive power of simplified variant of GPM and then generalizing to the full model. The detailed proof is in Appendix C.3. Based on the theorem, it is readily to extend to the following corollary.
Link Prediction. We evaluate the link prediction perfor- mance on three datasets: Cora, Pubmed, and ogbl-Collab. Following Guo et al. (2023), we split the edges into 80/5/15 train/val/test sets and use Hits @ 20 for Cora and Pubmed, and Hits @ 50 for ogbl-Collab for evaluation. The baselines include GCN, LLP, RUM, NodeFormer, and NAGphormer.
Corollary 3.5. For k 2 1, there exist graphs that can be distinguished by GPM using walk length k but not by the k-WL isomorphism test.
The results, along with dataset statistics, are summarized in Table 2. Notably, graph transformer methods such as NodcFormer and NAGphormer do not achieve competitive performance and, in some cases, perform worse than mes- sage passing GNNs. This discrepancy may arise from the in- ductive bias provided by message passing, which iteratively updates node representations based on their neighborhoods and is inherently well-suited for modeling connectivity be- tween nodes. Our GPM achieves the best performance across all evaluated datasets. This superior performance is
The proof of this result is detailed in Appendix C.4. This corollary highlights that GPM at least as expressive as message passing frameworks and high-order GNNs. Empir- ically, GPM successfully distinguishes graphs that remain indistinguishable under the 3-WL test (Appendix E)
Tackling SquasSius Another limitation of message passing is their focus on localized information, which pre- vents them from effectively capturing long-range dependen- cies within graphs. In contrast, GPM demonstrates supe-
6

---

Beyond Message Passing: Neural Graph Pattern Machine
Table 1. Node classification results, where the best-performing model highlighted in bold, and the second-best method is underlined.
PRODUCTS
COMPUTER
ARXIV
WIKICS
CORAFULL
DEEZER
BLOG
FLICKR
FLICKR-S
# Nodes
2,449,029
13,752
169,343
11,701
19,793
28,281
5,196
89,250
7.575
# Edges
123,718,024
491,722
2,315,598
431,206
126,842
185,504
343,486
899,756
479,476
Homophily Ratio H(g)
0.81
0.78
0.65
0.65
0,57
0,53
0.40
0.32
0.24
GCN (Kipf& & Welling, 2017)
75. 64.a2
89.65.is:
71.74am0
77,47,23
61,76
62.70wam
50,90wu1
84.58am
GAT (VeliSkovid et al, 2018)
79.45
90.78.a11
72.01-ma
76,91-332
64.47
61,70
93,47
50.70wm
85. 1
APPNP (Gusteiger et al., 2019)
77.58
10,18
69.40anco
78,87a2m
65. 65.16
66.10uue
94.77am
50,36uuss
84, 84.66m31
GPRONN (Chien et al., 2021)
79.76
89.32wk2
71.10aaz
78. 12,322
67.12mm:
63.20uus
94,36
48.32x1.
85, aanc
OrderedGNN (Song et 2023)
22.03auu
29.0
69.21am
66.12
25.90wm
51,20
88 68
RAW-GNN UJn et al., 2022)
90.98uums
78,01a
68. 58.64
65.1
94,96wm
49.58
86.53aus
RUM (Wang Cho, 2024)
78.68 78.68.1-0
90.62w134
70.54.000
78.20.a3
70.42.tss
64.25
94.16
50.97
87 87.25
GraphGPS (Kampasek et 2022)
OOM
91. 19
70.97-mar
78, 78.66-3 is
35.76
60.56wae
94.35
45.15
63.61
SAN (Kreuzer et 2021)
89,83au
78, 48
59,01
64.29ass
90.21
0OM
O0M
NodeFormer (Wu et.,, 2022)
72. 15
86, 98
67.19
74.73.291
71.01=a31
666.40mm2
93,79
$1,23
88.30wam
GOAT (Kong et al., 2023)
62.000ees
90. 96.
72.41
77.00~am
68,55-1
66, 4a
94,40mm
48, 48
88.1 18.16
NAGphormer (Chen et al., 2023)
73.55
91. 21.22
70. 70.13auce 13ass
77.16.212
71.51am
65 65.54
94.42anss
49. 49.66u.29
86. 85
GraphMamba (Behrouz& Hashemi, 2024)
72.48.0o0
VCR- Gruphormer (Fu et al., 2024))
91. 91.04au2
77.694239
68.78ur2
65 65.28mmm
93.92mum
50.77am
86.23
GCFormer (Chen et al., 2024)
91.63uts
18.12
69. 69.70
65.16
96.03mm
50.28au
87.90 87.90s
GPM
82.624c3
92.28
72.89
80.19.
71.23am
67.26mm
96.71.m
52.22
89.41.um
contrast, our GPM eliminates the need for message passing, potentially enabling more effective substructure learning.
Table 2. Link prediction results.
CORA
PUBMED
OGBL--COLAA
Nodes
2,708
19,717
235,868
4.2. Out-of-Distribution Generalization
# Edges
10,556
88,648
2,570,930
GCN (Kipl Welling, 2017)
84, 14.10
85.06
44.75aum
We evaluate the model robustness under distribution shifts between training and testing sets. Under the setting, the model is trained on source graph and evaluated on a target graph, with a 20/80 val/test split. We conduct experiments on citation networks, ACM and DBLP (using accuracy as the metric), as well as social networks Twitch (using AUC as the metric). The Twitch dataset consists of six graphs (DE, EN, ES, FR, PT, RU), where the model is trained on DE and evaluated the remaining graphs. For baselines, in addition to the methods used in previous experiments, we include domain adaptation and OOD generalization base- lines such as DANN, SR-GNN, StruRW, and SSReg. The experimental results are summarized in Table 4. We observe that standard graph learning methods struggle in this setting, highlighting their limited robustness to OOD testing. In con- trast, our GPM outperforms existing OOD-specific methods in settings such as A + D and Twitch, demonstrating supe- rior robustness to OOD challenges. This can be attributed to GPM's pattern learning ability that potentially identifies shared patterns between source and target graphs, whereas message passing is sensitive to subtle structural changes (Wang et al., 2024c). Furthermore, the performance of GPM is enhanced when combined with OOD techniques such as DANN and SSReg, achieving significant improve- ments across all settings, particularly in D + A.
LLP (Gao et al., 2023)
89,95-tml
87.23
49. 10
RUM (Wang Cho, 2024)
88. 78.74.am
85.87
48. 19
NodeFormer (Wa ol., 2022)
80. 48
83.93-1
46. 56
NAGphomeer (Chen et al., 2023)
86.87
86.46.um
47.56,us:
GPM
42.85
88.29.s15
49.70-a.0
likely due to the effectiveness of the captured patterns in accurately reflecting the connectivity between nodes.
Graph Classification and Regression. We evaluate the model on six graph datasets: social networks (IMDB-B. BB, COLLAB, Reddit-M5K, Reddit-M12K) for classification and molccule graphs (ZINC and ZINC-Full) for regression. We use 80/10/10 train/val/test splits for social networks, and the public splits for molecule graphs. The baselines include message passing GNNs (GIN, PNA, GNN-AK), graph ker- nels (DGK), random walk-based methods (AWE, CRaWI, AgentNet, RUM), and graph transformers (GMT, SAN, Graphormer, GPS, SAT, DeepGraph, Graph ViT. GEANet). The results, along with dataset statistics, are presented in Table 3. We observe that graph transformers generally out- perform message passing GNNs, likely due to their superior capability in modeling long-range dependencies. Notably, our GPM consistently outperforms all other methods across datasets of varying scales, particularly outperforming meth- ods that also utilize graph patterns as tokens (c.g., GMT, SAT, ViT). This might because these methods still rely on message passing as the encoder for individual patterns, thereby inheriting the limitations of message passing. In
4.3. Scalability
Large Graphs. Each graph instance (e.g., node, edge, or graph) is represented by k patterns, with an encoding com-
7

---

Beyond Message Passing: Neural Graph Pattern Machine
Table 3. Graph classification and regression (i.e., ZINC and ZINC-Full) results.
IMDB-B B
COLLAB f REDDIT-MSK REDDIT-MI2K1 1
ZINC 4
ZINC-FULL
Graphs
1,000
5,000
4,999
11,929
12,000
249,456
Nodes (in average)
199.8
~/74.5
~508.5
~391.4
~2332
~/23.2
Edges (in average)
~119311
~v4914.4
~1189.77
~913.8
c.49.8
<v49.8
GIN (Xu et al., 2019)
73.26
80.59.am
45.88.076
39.37-140
0.52610011
0.088
DGK (Yanardag & Vishwanathan, 2015)
66.96
73.09-0as
41.27.a..8
32,22Hom
PNA (Corso et al., 2020)
12.31
74.73-1m
42.18 12..8
38.57+1.6
0. 40000
0.067-0000
GNN-AK+ (Zhao et al., 2022)
75.00.4.0
77.35-093
47.78+1.12
40.604a.9
4.080
0.034.0.00
AWE (Ivanov & Burnaev, 2018)
74.45asas
73.93.194
50,46s191
39.20s2.00
0.094
0 0.05 an.00s
CRaWI (Tönshoff et al., 2023)
73.69
77.17-078
48.81
40.72
0.085
0.036Gn.oo oor
AgentNet (Martinkus et ul., 2023)
75. 88
77.30=1
42.15
0. 14
RUM (Wang& & Cho, 2024)
81. 10a.su
75.50
48 48.66.976
41,66e015
GMT (Back et al., 2021)
73.48.006
78.94.044
49.96.121
40.63r0.4
SAN (Kreuzer et al., 2021)
76.00...0
74.45.2
50.761041
39.92...2
0.139 10.0e
Graphormer (Ying et al., 2021)
76.74 742
78,82=12
48.98
41.42e0.s
0. e.12200000
0.025
GPS (Rampasek et ul., 2022)
77. 76
=7.41
49. 09
41.55a001
0.070
SAT (Chen et ul., 2022)
78, 21
78.35
47 .2.02
42,14 142007
0.094
0.036
DeepGraph (Zhao al., 2023)
0,072e0.004
ViT al., 2023)
78.05.1.0
78.79.0
48.39
40.17
0.073
0.035.nom
GEANet (Liang et al., 2024)
0.193
GPM
82.67
80.70.a74
51.87.144
43.07
0.064
0.021
Products
Arxiv
Table Out-of-distribution (OOD) generalization results.
Accuracy (%)
73
A A-> D
> A
TWITCH
82
GNN
GNN
GCN (Kipf Welling. 2017)
59.02a1.4
54.26
56.68
GPM
72-
GPM
GAT (Veličković et al., 2018)
61.67-1m
58.98
56.86
80
APPNP (Gasteiger et al., 2019)
49.05.xs4
57.542432
54.26
RUM (Wang& & Cho, 2024)
60,38as.
52.95
58.59
-0.3M
-3M
-SM
-25M -100M
-0.3M
-3M
-5M
-25M
-100M
Parameters
# Parameeerss
NodeFormer (Wa ul., 2022)
65. 69
55,33
54,17
NAGphormer (Chen et al., 2023)
65.01as.
55,40
54.19
Acceleration (%)
Products
DANN (Ganin et al., 2016)
68.90 18.92.x.9
63.07
60.71
SR-GNN (Zhu et al., 2021)
68, 30.166
62,43atu
59.65
GNN
GPM
StruKW (Liu al., 2023)
10.19>2
65,07a19
61.46
24
SSReg (You 2023)
69.04-2as
65.9341m
60.43
GPM
74.91
59.57.2m
61.63
2
4
GPM + DANN
75.39us
63.03
62.98
# GPUs
GPM SSReg
75.66:344
67.30
62.77
Figure 4. Model scalability analysis. (Top) Number of Parameters vs. Accuracy. (Bottom) Number GPUs vs. Acceleration Ratio.
A and are aboreviation of ACM and DBLP. Twitch is averagod over 5 settings.
plexity of O(k²) and overall complexity of O(n k2) (see Appendix D), where >> 2²2 denotes the number of instances. This design enables GPM to efficiently scale to large graphs using mini-batch training. We evaluate GPM on large-scale graph datasets, e.g., Products, ogbl-Collab, and ZINC-Full (Tables 2, and 3). GPM achieves competitive performance across these large-scale benchmarks.
smoothing effect. The architectural details of large-scale GPM models are presented in Table 7 in Appendix.
Distributed Training. Transformers have demonstrated remarkable efficiency in distributed training due to the par- allelization of self-attention mechanism (Shoeybi et al., 2019). In contrast, message passing GNNs are less efficient for distributed training, as their iterative message passing introduces sequential dependencies and incurs significant communication overhead when computational nodes are distributed across machines. By leveraging a transformer- based architecture, GPM achieves superior efficiency in distributed training compared to message passing GNNs on PRODUCTS, as shown in Figure 4 (Bottom). Further details
Large Models. Leveraging the transformer architecture, GPM naturally scales to larger model sizes by stacking ad- ditional transformer layers, as illustrated in Figure 4 (Top). Empirically, increasing model parameters enhances perfor- mance on large-scale graphs. In contrast, message passing GNNs (GAT in this case) struggle to scale due to the over-
8

---

Beyond Message Passing: Neural Graph Pattern Machine
Table Model component ablation. "PE" denotes positional em- bedding, "AP" is anonymous path, and "SP" is semantic path.
PRODUCTS
ARXIV
OGBL-COLLAD
COLLAB
GPM
82.62am.
72.89uv
49,70am
80.70.am
Comp.
w/o w/o AP
82,47
72.59wam
49.59
78.00+
81.99uus
72.47ame
48.43mmo
78.33une
w/o PE & AP
80.74
71.40a
48, 48.24
75.40koss
SP Eine
Mean
80 80.42mia
72. 12.0s
47.83-1
76.27-a4
GRU
80.9 poss
72.23 22.23
12ace
74.00
(a) Graph Structure
(b) Top-9 Dominant Patterns
Transformer
82.62u..
72.89
49.70
80.70
Figure 6. Model interpretation on ZINC.
80
p=10, q=o.1
Accuracy
70-
p=t, q=1
p=t.1 q=10
60
4.5. Model Interpretation
50
200
Epoch
Epoch
GPM leverages self-attention to identify the most relevant patterns for downstream tasks by utilizing a class token to aggregate pattern information. As an illustrative example, Figure presents the 24-th molecule graph from ZINC (colors indicate different atom types) along with its top-9 key patterns, demonstrating that GPM effectively captures topologically significant structures such as stars and rings in molecules. Similarly, Figure 8 in Appendix visualizes the results on COMPUTERS, highlighting that triangle structures are predominant in e-commerce networks.
Figure 5. Training loss and model performance on PRODUCTS with varying sampling criteria.
and discussions are provided in Appendix F.1.
4.4. Ablation Study
Impact of Model Components. Table 5 presents the model component ablation study results. Both positional embed- dings (PE) and anonymous paths (AP) contribute captur- ing topological information, with PE encoding relative node positions and AP characterizing pattern structures. Empir- ically, AP has a greater impact than PE, suggesting that the model prioritizes understanding pattern structures over node locations. For the semantic path (SP) encoder, the Transformer achieves the best due its ability to adaptively model both localized and long-range dependencies. More results and discussions are provided in Appendix F.2.
5. Conclusion
We propose GPM, novel graph representation learning framework that directly learns from graph substructure pat- terns, eliminating the need for message passing. The archi- tecture comprises three key components: a pattern sampler, pattern encoder, and an important pattern identifier. Exten- sive experiments across node-, link-, and graph-level tasks demonstrate the effectiveness of GPM, showcasing its supe- rior robustness, scalability, and interpretability. Moreover, GPM offers enhanced model expressiveness and a greater capacity for capturing long-range dependencies.
Impact of Training Tricks. Both multi-scale training and test-time augmentation contribute to improved performance. Specifically, multi-scale training increases average accuracy from 70.72 to 72.34 by incorporating hierarchical substruc- ture knowledge. Test-time augmentation uses fewer sub- structure patterns during training (e.g., 16 at training vs. 128 at inference), which significantly reduces training cost with negligible performance drop (72.43 to 72.34). Full details are provided in Appendix F.3.
Limitations and Future Works. The prediction perfor- mance of GPM heavily depends on the quality of the sam- pled patterns. In this work, we adopt a random sampling strategy, aiming to sample many patterns as possible to construct a comprehensive pattern set. However, this ap- proach may increase resource consumption during model training and hyperparameter tuning. Developing an adaptive sampling strategy tailored to specific downstream tasks or designing unified pattern vocabulary (Wang et al., 2024a:b) could mitigate this issue. Furthermore, the current imple- mentation of GPM is limited to supervised tasks. Future extensions could include unsupervised learning (He et al., 2022), integration with LLMs (Yuan et al., 2021; Liu et al., 2024), incorporating external knowledge (Ni et al., 2025), or adaptations for complex graph types, such as heterogeneous graphs (Wang et al., 2023).
GPM Automatically Learns Data Dependencies. Lever- aging the transformer architecture, GPM automatically iden- tifies dominant patterns. Experiments on the PRODUCTS (Figure 5) demonstrate that unbiased random walk sampling (p = 1, = 1) achieves the best results, over localized (p = 0.1, g = 10) and long-range (p = 10, = 0.1) sam- pling, by allowing the model to autonomously balance lo- calized and long-range dependencies. Detailed discussions are provided in Appendix G.

---

Beyond Message Passing: Neural Graph Pattern Machine
Acknowledgments
Bodnar, C., Frasca, F,, Otter, N., Wang, Y., Lio, P., Montu-
far, G. R,, and Bronstein, M. Weisfeiler and lehman go cellular: Cw networks. In NeurlPS, 2021.
This work was partially supported by the NSF under grants IIS-2321504, IIS-2334193,
IIS-234 -S-2340346, IIS-2217239, CNS- 1N5-2426514, and CMMI-2146076, and Notre Dame Strategic Framework Research Grant (2025). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors,
Bouritsas, G., Frasca, F., Zafeiriou, S., and Bronstein, M. M. Improving graph neural network expressivity via sub- graph isomorphism counting. TPAMI, 2022.
Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv, 2017.
Impact Statement
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. In NeurlPS, 2020.
We introduce novel graph representation learning frame- work that goes beyond the traditional message passing. By design, our GPM addresses inherent challenges in mes- sage passing, such as restricted expressiveness and over- squashing. This capability enables our framework to better scale to complex tasks requiring large models or involving large graphs. Also, GPM provides an interface to enable model interpretation, facilitating the applications requiring clear insights on graph topology, such social network analysis and drug discovery. Potential ethical considerations include the misuse of the technology in sensitive domains, such as surveillance or profiling, and the reinforcement of biases present the training data.
Cai, Z., Yan, X., Wu, Y., Ma, K., Cheng, J., and Yu, F. Dgel: An efficient communication library for distributed gnn training. In EuroSys, 2021.
Chen, C.-F. R., Fan, Q. and Panda, R. Crossvit: Cross- attention multi-scale vision transformer for image classi- fication. In ICCV, 2021.
Chen, D., O'Bray, L., and Borgwardt, K. Structure-aware transformer for graph representation learning. In ICML, 2022.
References
Chen, D., Schulz, T. H., and Borgwardt, Learning long range dependencies on graphs via random walks. In ICLR, 2025.
Abboud, R., Ceylan, I., Grohe, M., and Lukasiewicz, T. The surprising power of graph neural networks with random node initialization. In IJCAI, 2021.
Chen, J., Gao, K., Li. G., and He, K. Nagphormer: A tokenized graph transformer for node classification in large graphs. In ICLR, 2023.
Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In ICLR, 2021.
Alsentzer, E., Finlayson, S., Li, M., and Zitnik, M. Subgraph neural networks. In NeurIPS, 2020.
Chen, J., Liu, H., Hoperoft, J. E., and He, K. Leveraging contrastive learning for enhanced node representations in tokenized graph transformers. In NeurlPS, 2024.
Azizian, W. and mare lelarge. Expressive power of invariant and equivariant graph neural networks. In ICLR, 2021.
Chen, Z., Villar, S., Chen, L., and Bruna, J. On the equiv- alence between graph isomorphism testing and function approximation with gnns. NeurIPS, 2019.
Back, J., Kang, M., and Hwang, S. J. Accurate learning of graph representations with graph multiset pooling. In ICLR, 2021.
Chen, Z., Chen, L.., Villar, S., and Bruna, J. Can graph neural networks count substructures? In NewrIPS, 2020.
Balcilar, M., Héroux, P., Gauzere, B., Vasseur, P., Adam, S., and Honeine, P. Breaking the limits of message passing graph neural networks. In ICML, 2021.
Chien, E., Peng. J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
Behrouz, A. and Hashemi, F. Graph mamba: Towards learning on graphs with state space models. In KDD, 2024.
Chung. J., Gulcehre, C., Cho, K., and Bengio, Y. Empirical evaluation of gated recurrent neural networks sequence modeling, arXiv, 2014.
Bian, T., Xiao, X., Xu, T., Zhao, P., Huang, W., Rong, Y., and Huang, J. Rumor detection on social media with bi-directional graph convolutional networks. In AAAI, 2020.
Corso, G., Cavalleri, L., Beaini, D., Liò, P., and Veličković, P. Principal neighbourhood aggregation for graph nets. NeurlPS, 2020.
10

---

Beyond Message Passing: Neural Graph Pattern Machine
Dosovitskiy, A., Beyer, L.,, Kolesnikov, A., Weissenborn,
Hamilton, W., Ying, Z., and Leskovec, J. Inductive repre- sentation learning large graphs. In NeurlPS, 2017.
D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
He, K., Chen, X., Xie, S., Li, Y., Dollár, P., and Girshick, R. Masked autoencoders are scalable vision learners. In CVPR, 2022.
Dwivedi, V. P. and Bresson, X. A generalization of trans- former networks to graphs, arXiv, 2020.
He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mlp-mixer to graphs. In ICML, 2023.
Dwivedi, V. P., Rampášek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph bench- mark. In NeurlPS, 2022.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. In ICLR, 2020.
Dwivedi, V. P., Joshi, K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. JMLR, 2023.
Huang, H., Tang, J., Liu, L., Luo, J., and Fu, X. Triadic closure pattern analysis and prediction social networks. TKDE, 2015.
Fan, Y.. Ju, M., Zhang, C., and Ye, Y. Heterogeneous temporal graph neural network. In SDM, 2022.
Ivanov, S. and Burnaev, E. Anonymous walk embeddings. In ICML, 2018
Fu, D., Hua, Z., Xie, Y., Fang, J., Zhang, S., Sancak, K., Wu, H., Malevich, A., He, J., and Long, B. VCR- -CR-graphormer: A mini-batch graph transformer via virtual connections. In ICLR, 2024.
Jin, D., Wang, R., Ge, M., He, D., Li, X., Lin, W., and Zhang, W. Raw-gnn: Random walk aggregation based graph neural network. In IJCAI, 2022.
Fu, X., Chen, C., Dong, Y., Vullikanti, A., Klein, E., Mad- den, G., and Li, J. Spatial-temporal networks for antibi- ogram pattern prediction. In ICHI, 2023.
Jin, Y., Song, G., and Shi, C. Gralsp: Graph neural networks with local structural patterns. In AAAI, 2020.
Karypis, G. Metis:
Unstructured graph partitioning and sparse matrix ordering system. Technical report, 1997.
Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., March, M., and Lempitsky, V. Domain- adversarial training of neural networks. JMLP, 2016.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Garg, V., Jegelka, S., and Jaakkola, T. Generalization and representational limits of graph neural networks. In /CML, 2020.
Kong, K., Chen, J., Kirchenbauer, J., Ni, R., Bruss, C. B., and Goldstein, T. Goat: A global transformer large- scale graphs. In ICML, 2023.
Gasteiger, J., Bojchevski, A., and Günnemann, S. Com- bining neural networks with personalized pagerank for classification on graphs. In ICLR, 2019.
Kreuzer, D., Beaini, D., Hamilton, W., Létourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. In NeurIPS, 2021.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In ICML, 2017.
Liang. J., Chen, M., and Liang. J. Graph external attention enhanced transformer. In ICML, 2024.
Granovetter, M. S. The strength of weak ties. American journal of sociology, 1973.
Liao, R., Zhao, Z., Urtasun, R., and Zemel, Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.
Graziani, C., Drucks, T., Jogl, F., Bianchini, M., Scarselli, F., Gartner, T., et The expressive power of path-based graph neural networks. PMLR, 2024.
Liben-Nowell, D. and Kleinberg, J. The link prediction problem for social networks. In CIKM, 2003.
Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In KDD, 2016.
Liu, S., Li, T., Feng, Y., Tran, N., Zhao, H., Qiu, Q., and Li, P. Structural re-weighting improves graph domain adaptation. In ICML, 2023.
Guo, Z. Shiao, W., Zhang, S., Liu, Y., Chawla, N. V., Shah, N., and Zhao, T. Linkless link prediction via relational distillation, In ICML., 2023.
Liu, Z., He, X., Tian, Y., and Chawla, N. V. Can we soft prompt Ilms for graph learning tasks? In WWW, 2024.

---

Beyond Message Passing: Neural Graph Pattern Machine
Loukas, A. What graph neural networks cannot learn: depth VS width. In ICLR, 2020.
Rampasek, L.,, Galkin, M., Dwivedi, V. P. Luu, A. T., Wolf, G., and Beaini, D. Recipe for general, powerful, scal- able graph transformer. In NeurIPS, 2022.
Ma, T., Qian, Y., Zhang, C., and Ye, Y. Hypergraph trastive learning for drug trafficking community detection. In ICDM, 2023.
Rong, Y., Bian, Y., Xu, T., Xie, W., Wei, Y., Huang, W., and Huang, J. Self-supervised graph transformer on large- scale molecular data. In NeurlPS, 2020.
Ma, T., Qian, Y.. Wang, Z., Zhang, Z., Zhang, C., and Ye, Y. Lim-empowered class imbalanced graph prompt learning for online drug trafficking detection. arXiv, 2025a.
Shoeybi, M., Patwary, M., Puri, R., LeGresley, P., Casper, J., and Catanzaro, B. Megatron-Im: Training multi- billion parameter language models using model paral- lelism. arXiv, 2019.
Ma, T.. Qian, Y., Zhang, S., Zhang, C., and Ye, Y. Adap- tive expansion for hypergraph learning. arXiv preprint arXiv:2502.15564, 2025b.
Snell, C., Lee, J., Xu, K., and Kumar, A. Sealing 11m test-time compute optimally can be effective than scaling model parameters. arXiv, 2024.
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. In NewrIPS, 2019a.
Song, Y., Zhou, C.,, Wang, X., and Lin, Z. Ordered GNN: Ordering message passing to deal with heterophily and over-smoothing. In ICLR,, 2023.
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y. In- variant and equivariant graph networks. In ICLR, 2019b.
Martinkus, K., Papp. P. A., Schesch, B., and Wattenhofer, R.
Sun, Z., Wang, H., Wang, H., Shao, B., and Li, J. Efficient subgraph matching on billion node graphs. In VLDB, 2012.
Agent-based graph neural networks. In ICIR, 2023.
Micali, S. and Zhu, Z. A. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 2016.
Tang, H. and Liu, Towards understanding generalization of graph neural networks. In ICML, 2023.
Michel, G., Nikolentzos, G., Lutzeyer, J. F., and Vazirgian- nis, M. Path neural networks: Expressive and accurate graph neural networks. In ICML, 2023.
Tönshoff, J., Ritzert, M., Wolf, H., and Grohe, M. Walking out of the weisfeiler leman hierarchy: Graph learning beyond message passing, TMLR, 2023.
Morris, C., Ritzert, M., Fey, M.. Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. Atten- tion is all you need. In NeurIPS, 2017.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
Murphy, R., Srinivasan, B., Rao, V., and Ribeiro, B. Rela- tional pooling for graph representations. In ICML, 2019.
Ni, B., Liu, Z., Wang, L., Lei, Y., Zhao, Y., Cheng, X., Zeng, Q.. Dong. L., Xia, Y., Kenthapadi, K., et al. Towards trust- worthy retricval augmented generation for large language models: A survey. arXiv, 2025.
Verma, S. and Zhang, Z.-L. Stability and generalization of graph convolutional neural networks. KDD, 2019.
Wang. Y. and Cho, K. Non-convolutional graph neural networks. In NeurIPS, 2024.
Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, I. A critical look the evaluation of GNNs under heterophily: Are really making progress? In ICLR, 2023.
Wang. Z., Li, Q., Yu, D., Han, X., Gao, X.ZZ., and Shen, S. Heterogeneous graph contrastive multi-view learning. In SDM, 2023.
Qian, Y., Ma, T., Zhang, C., and Ye, Y. Dual-level hy- pergraph contrastive learning with adaptive temperature enhancement, In www, 2024.
Wang. Z., Zhang, Z., Chawla, N. V., Zhang, C., and Ye, Y. GFT: Graph foundation model with transferable tree vocabulary. In NewrlPS, 2024a.
Qian, Y., Ma, T., Zhang, C., and Ye, Y. Adaptive graph en- hancement for imbalanced multi-relation graph learning. In CIKM, 2025.
Wang, Z., Zhang, Z., Ma, T., Chawla, N. V., Zhang, C., and Ye, Y. Learning cross-task generalities across graphs via task-trees. arXiv, 2024b.
12

---

Beyond Message Passing: Neural Graph Pattern Machine
Wang, Z. Zhang, Z., Zhang, C., and Ye, Y. Subgraph pooling: Tackling negative transfer graphs. In IJCAI, 2024c.
Zhang, Z., Wang, Z., Hou, S., Hall, E., Bachman, L., White, J., Galassi, V., Chawla, N. V., Zhang, C., and Ye, Y. Diet- odin: A novel framework for opioid misuse detection with interpretable dietary patterns. In KDD, 2024c.
Welke, P. Thiessen, M. Jogl, F,, and Gärtner, T. Expectation-compler graph representations with homo- morphisms. In ICML,, 2023.
Zhang, Z., Wang, Z., Ma, T., Taneja, V. Nelson, S., Le, H. L.,, Murugesan, K., Ju, M., Chawla, N. V., Zhang. C., et al. Mopi-hfis: A multi-ojeective personalized health- aware food recommendation system with lIm-enhanced interpretation. arXiv, 2024d.
Wu, Q.. Zhao, W., Li, Z., Wipf, D., and Yan, J. Nodeformer: A scalable graph structure learning transformer for node classification. In NeurIPS, 2022.
Zhao, H., Ma, S., Zhang, D., Deng, Z.-H., and Wei, F. Are more layers beneficial to graph transformers? In ICLR, 2023.
Wu, Q. Zhao, W. Yang, C.. Zhang, H., Nie. F., Jiang, H., Bian, Y., and Yan, J. Simplifying and empowering transformers for large-graph representations. In NeurlPS, 2023.
Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars subgraphs: Uplifting any GNN with local structure awareness. In ICLR, 2022.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019.
Zhu, Q., Ponomareva, N., Han, J., and Perozzi, B. Shift- robust gnns: Overcoming the limitations of localized graph training data, In NeurIPS, 2021.
Yan, Z., Zhou, J., Gao, L., Tang, Z., and Zhang, M. An effi- cient subgraph gnn with provable substructure counting power. In KDD, 2024.
Yanardag, P. and Vishwanathan, S. Deep graph kernels. In KDD, 2015.
Ying, C., Cai, T., Luo, S., Zheng, S., Ke. G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? In NeurIPS, 2021.
Ying, R., He, R., Chen, K., Eksombatchai,
P., Hamilton, W. L., and Leskovee, J. Graph convolutional neural net- works for web-scale recommender systems. In KDD, 2018.
You, Y., Chen, T., Wang, Z., and Shen, Y. Graph domain adaptation via theory- spectral regularization. In ICLR, 2023.
Yuan, L., Chen, D., Chen, Y.-L., Codella, N., Dai, X., Gao, J. Hu, H., Huang, X., Li, B., Li, C., et al. Florence: A new foundation model for computer vision. arXiv, 2021.
Zhang, B., Gai, J., Du, Y., Ye, Q.. He, D., and Wang, L. Beyond weisfeiler-lehman: A quantitative framework for gnn expressiveness. ICLR, 2024a.
Zhang, C., Song, D., Huang, C., Swami, A., and Chawla, N. V. Heterogeneous graph neural network. In KDD, 2019.
Zhang, Z., Li, Y., Le, Wang. Z., Ma, T., Galassi, V., Murugesan, K., Moniz, N., Geyer, W., Chawla, N. V., et al. Ngqa: A nutritional graph question answering benchmark for personalized health-aware nutritional rea- soning. arXiv, 2024b.
13

---

Beyond Message Passing: Neural Graph Pattern Machine
A. Limitations of Message Passing and Recent Advances
The message passing paradigm (Kipf& & Welling, 2017; Hamilton et al., 2017; Veličković et al., 2018) in GNNs has well- documented limitations, including restricted expressiveness, over-smoothing, over-squashing and an inability to effectively model long-range dependencies. Given our focus on learning graph patterns, this discussion emphasizes the issues of expressiveness and notable advancements. Pioneering work by Xu et al. (2019) revealed that the expressive power of GNNs is fundamentally bounded by the 1-WL isomorphism test. Building on this, Corso et al. (2020) demonstrated that no GNN employing a single aggregation function can achieve the expressiveness of the I-WL test when the neighborhood multiset has uncountable support. Consequently, this constraint renders GNNs incapable of identifying critical graph structures, such as stars, conjoint cycles, and k-cliques (Chen et al., 2020; Garg et al., 2020; Zhang et al., 2024a).
To address the expressiveness limitations of GNNs, three primary strategies have emerged. The first focuses on developing expressive GNNs that enhance the message passing framework to surpass the constraints of the 1-WL test. For instance, Maron et al. (2019b); Chen et al. (2019); Maron et al. (2019a) introduced k-order WL GNNs to emulate the k- (LWL test within GNN architectures. Similarly, Alsentzer et al. (2020); Bouritsas et al. (2022); Bodnar et al. (2021); Zhao et al. (2022) proposed advanced message passing mechanisms capable of detecting substructures in graphs, while Murphy et al. (2019); Loukas (2020) incorporated node positional embeddings to boost the representational power of message passing GNNs. Despite their increased expressiveness, these approaches often suffer from computational inefficiency (Azizian & mare lelarge, 2021).
An alternative approach leverages random walk kernels to guide the message passing process, constraining interactions limited range of nodes (Jin et al., 2022: Martinkus et al., 2023; Tönshoff' et al., 2023; Wang & Cho, 2024; Chen et al., 2025). Notably, Tönshoff et al. (2023) demonstrated that random walk-based methods can capture both small substructures and long-range dependencies, while Wang & Cho (2024) showed that sufficiently long random walks can distinguish non-isomorphic graphs. Moreover, these random walk approaches are theoretically more expressive than message passing (Zhang et al., 2019; Fan et al., 2022; Welke et al., 2023; Michel et al., 2023; Graziani et al., 2024). Despite their strengths, these methods tend to emphasize long-range dependencies at the expense of localized information (Tönshoff et al., 2023) and lack interpretability regarding the specific graph knowledge being learned.
Lastly, graph transformers (GTs) (Kreuzer et al., 2021; Ying et al., 2021; Dwivedi & Bresson, 2020; Rampasek et al., 2022; He et al., 2023; Chen et al., 2022) have emerged as a compelling alternative to traditional message passing GNNs. Leveraging a global attention mechanism, GTs can capture correlations between any pair of nodes, enabling effective modeling of long-range dependencies. Both theoretical and empirical studies (Kreuzer et al., 2021; Ying et al., 2021) demonstrate that, under mild assumptions, graph transformers surpass the expressive power of WL isomorphism tests. This represents fundamental advantage over message passing GNNs in terms of expressiveness. However, the quadratic complexity of all-pair node attention poses significant computational challenges, limiting the applicability of GTs to smaller graphs, such as molecular graphs (Wu al., 2023).
Crucially, the aforementioned methods primarily focus on developing advanced message passing frameworks rather than directly encoding graph patterns. As a result, they may still inherit the limitations associated with message passing.
B. Implementation Details
B.I. Environments
Most experiments are conducted on Linux servers equipped with four Nvidia A40 GPUs The models are implemented using Py PyTorch 2.4.0, PyTorch Geometric 2.6.1, and PyTorch Cluster 1.6.3, with CUDA 12.1 and Python 3.9.
B.2. Training Details
The training of transformers is highly sensitive regularization techniques. In our setup, use the AdamW optimizer with weight decay and apply early stopping after 100 epochs. Label smoothing is set 0.05, and gradient clipping is fixed at 1.0 to stabilize training. The learning rate follows a warm-up schedule with 100 warm-up steps by default.
All experiments are conducted five times with different random seeds. The batch size is set to 256 by default.
14

---

Beyond Message Passing: Neural Graph Pattern Machine
B.3. Model Configurations
We perform hyperparameter search over the following ranges: learning rate {le-2, 5e-3, 1e-3), positional embedding dimension {4, 8, 20), dropout {0.1, 0.3, 0.5). weight decay {1e-2,0) 0), and weighting coefficient À {0.1, 0.5, 1.0). For pattern sampling, set 1, 1 by default (see Appendix G for details). The model configuration includes hidden dimension of 256, 4 attention heads, and transformer layer. The selected hyperparameters are summarized in Table 6.
Table Hyper-paramert settings on predictive tasks.
PRODUCTS
COMPUTER
ARXIV
WIKICS Node
CORAFULL
DEEZER
BLOG
FLICKR Node
FLICKR-S
Node
Node
Node
Node
Node
Node
Learning Rate
0.01
0.01
0.001
0.005
Dropout
0.5
0.1
0.3
Decay
0.01
Batch Size
256
256
256
256
256
256
256
256
PE Type
Lup
Lap
Lup
Lup
Lup
Lup
Lap
Lap
Lup
PE Dim
8
8
8
16
16
8
4
AP Encoder
MEAN
GRU
GRU
GRU
GRU
GRU
GRU
MRAN
GRU
A
0.5
0.5
0.5
0.1
0.5
0.5
CORA Link
PUBMED Link
COLL-C
IMDB-B B
COLLAB
REDDIT-MSK
REDDIT-
ZINC Graph
ZINC-FULL
Task
Link
Gruph
Graph
Gruph
Gruph
Graph
Learning Rate
0.001
0.01
1101
0.001
0.01
0.001
0.005
0.01
0.01
Dropout
0.3
0,3
0.1
0.1
0.1
0.1
0.1
0.1
0.1
Decay
0
0.01
0
0
0.01
0
Batch Size
256
256
256
1024
1024
1024
256
1024
1024
PE Type
Lap
Lap
Lap
RW
RW
RW
RW
RW
RW
PE
8
8
8 GRU
Encoder
GRU
GRU
MEAN
MEAN
MEAN
GRU
GRU
0.1
B.4. Architectures in Model Scaling Analysis
In our scalability analysis (Section 4.3), we evaluate the performance of GAT and GPM across different model scales, The detailed model architectures and corresponding parameter counts are provided in Table
Table 7. Model architectures in model scaling analysis.
Architectures of GNN (GAT in this case)
# GNN Layers
2
2
3
Number Heads
24
48
112
# Hidden Dimension
512
1536
2048
3072
7168
ARXIV PRODUCTS
0.35M
2.63M
4.56M
19. 19.44M
104.07M
0.34M
2.6M
4.52M
19.37M
103. 103.92M
Architectures GPM
# Transformer Layers Number of Heads
1
3
8
16
# Hidden Dimension
64
256
256
512
1024
ARXIV
0.19M
2.94M
4.52M
20.04M
96.72M
PRODUCTS
0.21M
3.21M
4.79M
21.12M
100.96M
C. Proof
C.1. Proof of Proposition 3.2
We prove the proposition by introducing the following theorem first.
Theorem C.1 (Theorem 1 of (Micali & Zhu, 2016)). Given a graph g = (V,E), one can reconstruct B(u,k) = -V", E"). where n = [ m = [''), the ego-graph induced by node E with k radius, via an anonymous walk distribution Dj. where (m) starting at node v.
15

---

Beyond Message Passing: Neural Graph Pattern Machine
As stated in the theorem, let Di denote the distribution of anonymous walks sampled from node v. This distribution is sufficient to represent the complete k-hop ego-graph induced from v (u,,, k) = (V",'",, where = O In other words, if a set of patterns {01, Ø2.... J can approximate Di, this set can be used to reconstruct the corresponding ego-graph. Thus, for each node, set of I-length patterns is sufficient to reconstruct its respective k-hop ego-graph.
Next, we consider the scenario where a task requires information from the k-hop ego-graph (e, k). Given that the ego-graph distribution of each node can be reconstructed via anonymous walks, it becomes feasible to compare these distributions to assess whether node representations are distinguishable. In general, the k-hop ego-graph distributions of two nodes u and u are distinct unless they represent the same structural phenomena. Consequently, the corresponding pattern sets {øN, of og.... 3 and { ....... } are also distinct, ensuring that each node retains a unique and distinguishable topological representation.
C.2. Proof of Proposition 3.3
As discussed, any graph pattern can be represented as a combination of a semantic path, which captures semantic information (i.e., the specific nodes forming the pattern), and an anonymous path, which encodes topological structure (i.e., the overall pattern structure). To effectively extract both types of information, these two paths can be encoded separately, preserving semantic meaning and structural insight independently.
To ensure lossless compression, we employ bijective mappings to project these paths, guaranteeing that distinct paths maintain unique representations. Given semantic path w and its corresponding anonymous path Φ, we introduce two bijective projections: Ps : w + Ps for semantic encoding and Pa : 6 + Pa for structural encoding. Consequently, to comprehensively encode given graph pattern, both the semantic and anonymous paths must be jointly represented.
C.3. Proof of Theorem 3.4
We outline the proof by first (1) establishing the expressiveness of a simplified variant of GPM and (2) extending this result to the general case.
The learning process of GPM consists of three key steps: (1) Extracting n patterns using (-length random walks, where each pattern is uniquely defined by its semantic path w and anonymous path d. (2) Encoding the semantic and anonymous paths separately using neural networks and combining their representations. (3) Passing the encoded graph patterns through a transformer for final predictions.
To analyze expressiveness, we consider a simplified variant of GPM with the following modifications: (1) Setting n 1. (2) Replacing neural networks with universal and injective mappings Ps and pa. (3) Using a mean aggregator over encoded patterns instead of transformer.
Under this setting, the model is essentially trained on a single l-length path w. Additionally, we impose the following mild assumptions:
Assumption C.2. The graphs are connected, unweighted, and undirected. Assumption C.3. The walk length / is sufficiently large.
Given these assumptions, the simplified GPM can distinguish non-isomorppic graphs, as stated in the following theorem. Theorem C.4 (Theorem 4 of Wang & Cho (2024)). Up to the Reconstruction Conjecture, encoding the l-length random walks (combining semantic path and anonymous path) produces distinct embeddings for non-isomorphic graphs.
The key insight is that for any two non isomoophi graphs, the distributions of infinite-length random walks over these graphs are distinct, regardless of the starting points. Moreover, universal and injective mappings ensure that each unique random walk is projected into a unique point in the embedding space. Wang & Cho (2024) establishes this theorem by (1) proving it for the simplest case where the graph size is 3, and (2) using induction to extend the proof to graphs of size and n. Based on this theorem, it is straightforward to demonstrate that the simplified GPM can distinguish any non-isomorphic graphs, provided the reconstruction conjecture holds. Next, we generalize the simplified case to the proposed GPM framework.
(1) The simplified case assumes n = 1 with a sufficiently large walk length I, whereas GPM operates with n > 1. Since random walks can start from any node in the graph, an l-length random walk can be split into & segments (k is large enough), each of length l/k. Each sub-walk can be encoded individually and later combined to approximately form the final embedding. Note that We did not mean to suggest that long walks can be fully reconstructed from shorter ones, especially
16

---

Beyond Message Passing: Neural Graph Pattern Machine
since anonymous walks cannot preserve node identity across segments. Rather, we intended deseribe an approximate strategy, where long walks are segmented into shorter sub-walks, each encoded independently. This design allows the transformer to aggregate distributed long-range information across these sub-patterns, (2) GPM employs neural networks as encoders, which are inherently universal and injective, satisfying the requirements of the mappings Ps and Pa used in the simplified case. (3) Finally, while the simplified case uses a mean aggregator over encoded patterns, GPM adopts a transformer architecture for aggregation. The self-attention mechanism transformers generalizes the mean aggregator, which can be seen as a special case of the transformer.
By these generalizations, we establish that GPM can distinguish any connected, unweighted. and undirected non-isomorphic graphs, given sufficient number of graph patterns.
C.4. Proof of Theorem 3.5
The proof follows the same structure Theorem 3.4: (1) Defining simplified variant of GPM, (2) Proving the theorem this simplified model, and (3) Extending the results the general case.
To ensure the proof is self coff-oontaiee,, we reintroduce the design of the simplified variant and its extension to the full model.
The simplified variant of GPM includes the following modifications: (1) Replacing neural networks with universal and injective mappings P3 and Pa- (2) Using a mean aggregator over encoded patterns instead of a transformer.
Under the same assumptions as in Theorem 3.4, namely: (1) The graphs are connected, unweighted, and undirected, and (2) The number of sampled patterns is sufficiently large, we apply the following corollary directly prove Theorem 3.5 for the simplified case.
Theorem C.5 (Corollary 4. of Wang & Cho (2024)). Up to the Reconstruction Conjecture, two graphs G1, G2 labeled as non-isomorphic by the k-WL test is the necessary, but not sufficient condition that encoding the k-length random walks sampled from these two graphs produces the same embedding.
In other words, if the k-WL test distinguishes two graphs, then the simplified GPM variant can also distinguish them. However, the converse does not necessarily hold-if the simplified GPM distinguishes two graphs, the k- k-WL test may fail to do so.
To generalize from the simplified case to the full GPM model, we follow the same strategy as the proof of Theorem 3.4: (1) Replacing the universal and injective mappings with neural network encoders, and (2) Substituting the mean aggregator with transformer architecture.
D. Complexity
We analyze the time complexity of three key components: pattern sampling, pattern encoding, and transformer encoding. For a single instance, & random walks of length / are sampled, resulting in a sampling complexity of O 1), where 12 empirically. Pattern encoding involves three alternative encoders: the mean encoder with complexity 2 O(k), the GRU encoder with complexity 2 x O(k I), and the transformer encoder with complexity and anonymous paths should be encoded). The tranformer encoder over encoded graph patterns introduces an additional complexity of O(.2). Thus, the maximum total complexity per instance is
O 12) (note both semantic
0(k-1)+2x00 0(k -))-)++2x0(-+) +0
O(K))
We compare this complexity to that of existing graph transformers for both node-level and graph-level tasks. For node classification, GPM's time complexity for encoding all nodes in a graph is O(n k²), where n is the number of nodes, and 2 < n. In contrast, existing graph transformers incur O complexity, which scales quadratically with the number of nodes. For graph classification, GPM's complexity for encoding all graphs is O(m x²), where m is the number of graphs In comparison, existing graph transformers require O(m n²), where the average number of nodes per graph.
17

---

Beyond Message Passing: Neural Graph Pattern Machine
E. How Does GPM Surpass Message Passing?
E.1. Empirical Effectiveness
Beyond theoretical analysis, we provide an empirical evaluation on three benchmark datasets specifically designed to challenge graph isomorphism tests. The CSL dataset (Murphy al., 2019) comprises 150 4-regular graphs that are indistinguishable using the 1-WL test. The EXP dataset (Abboud al., 2021) includes 600 pairs of non-isomorphic graphs that cannot be distinguished by either the 1-WL 2-WI. tests. Lastly, the SR25 dataset (Balcilar al., 2021) contains 15 strongly regular graphs with 25 nodes each, which remain indistinguishable even under the 3-WL test. The experimental results, summarized in Table 8, demonstrate that GPM successfully distinguishes all graphs across these datasets, empirically surpassing the 3- test. In contrast, many existing models fail on these tasks.
Table 8. Empirical expressiveness analysis.
CSL
EXP
SR25
GCN (Kipf & Welling, 2017)
10
51.9
6.7
GatedGCN (Bresson & Laurent, 2017)
10
51.7
6.7
GraphTrans (Dwivedi & Bresson, 2020)
10
52.4
6.7
3-GNN (Morris et ul., 2019)
95.7
99.7
6.7
GIN-AK+ (Zhan et al., 2022)
100
6.7
GraphViT (He et al., 2023)
100
100
100
ESC-GNN (Yan al., 2024)
100
100
100
GPM
100
100
100
E.2. Tackling Over-Squashing
Another limitation of message passing is their focus on localized information, which prevents them from effectively capturing long-range dependencies within graphs. In contrast, GPM demonstrates superior capability in modeling long-range interactions. Following He et al. (2023), we evaluate this capability using the TREENEIGHBBOSSMTCHHIN benchmark introduced by Alon & Yahav (2021). This dataset comprises binary trees, with the objective being to classify the root node based on its degree. The degree information is maintained within the leaf nodes, and successful classification of the root node requires the model capture r-radius information, where is the depth of the tree.
As shown in Figure 7, we report the training accuracy following Alon & Yahav (2021) to evaluate the model's fitting ability. Notably, message passing GNNs and RUM (Wang & Cho, 2024) fail to perfectly fit the data, exhibiting over-squashing effects as early as r = 4. In other words, these models fail to distinguish between different training examples, even when these examples are observed multiple times. In contrast, GPM achieves perfect data fitiin across all problem radiuses. This attributed to its ability to directly learn long-range patterns sampled via random walks.
To provide clearer understanding, we present a brief example illustrating how GPM mitigates over-squashing in such scenarios. Recall that the correlation between node labels and degrees is encoded within the leaf nodes, where the features of the leaf nodes are a combination of their degrees and labels (for simplicity). Even the simplest variant of GPM (without anonymous path encoding or node positional embeddings) has the potential to solve this problem. Specifically, given a tree
1.0
Accuracy
0.5
GCN
GIN
GAT
RUM
GGNN
GPM
0.0
3
5
6
Problem Radius
Figure 7. Over-squashing analysis.
18

---

Beyond Message Passing: Neural Graph Pattern Machine
with radius r, we randomly sample k random walks of length and encode these walks using transformer. In the optimal (and empirically observed) case, the encoded pattern embeddings accurately capture the features of the leaf nodes, i.e., the combination of node features and labels. At this stage, the model effectively reduces the task to basic matching problem: given multiple sets of (node degree, label) pairs, it predicts the label of the root node based on its degree. This matching task is straightforwardly handled by neural networks, such as the transformer architecture employed in our work.
F. Additional Experimental Results and Discussions
E.1. Additional Discussion Distribution Training
We GraphSAGE the GNN baseline, fixing the batch size to 256 and the number of training epochs to 10. Distributed GNN training follows the graph partitioning without replication strategy (Cai et al., 2021), where the graph is divided into non-overlapping partitions using the METIS library (Karypis, 1997). Each GPU processes a single partition, and peer-to-peer communication is used to exchange learned node embeddings among GPUs.
Due to resource limitations, our experiments are conducted on a single machine equipped with four Nvidia A40 GPUs, which does not reflect acceleration performance multi-machine distributed settings. However, Shoeybi et al. (2019) demonstrated that the scalability of transformer architectures improves consistently with an increasing number of compu- tational devices. In contrast, Cai et al. (2021) showed that the graph partitioning without replication strategy introduces substantial communication overhead in GNNs the number of GPUs increases. Specifically, Cai et al. (2021) (Figure 2) reports that when scaling to 16 GPUs, the training becomes slower than with just 2 GPUs due to communication overhead dominating time consumption.
These findings highlight the advantages of GPM, which using tranformer as backbone, over message passing GNNs for distributed training, particularly scenarios with large number of devices.
F.2. Model Component Ablation
To verify the contribution of key components in GPM, we conduct several ablation studies, as summarized Table 9.
Impact of Positional Embeddings and Anonymous Paths. We investigate the role of positional embeddings and anonymous paths in GPM. While both provide topological insights, positional embeddings primarily capture node-level structural information (i.e., the relative position of node within the graph), whereas anonymous paths encode structural characteristics of patterns (i.e., the identity and structure of the pattern itself). As shown in Table 9, incorporating positional embeddings and anonymous paths improves model performance. However, the effect of positional embeddings is relatively
Table Full results on model component ablation.
PRODUCTS
COMPUTER Node
ARXIV Node
WIKICS Node
CORAFULL
DEEZER
BLOG
Task
Node
Node
Node
Node
GPM
82.62 # 0.39
92.28 = 0.39
72.89 + 0.68
80.19 = 0.41
71.23 + 0,51
67.26 + 0.22
96.71 + 0.59
Comp.
w/o PE
82.47 0.21
91.89 0.64
72.59 0.23
80.02 0.43
70.71 a 0.50
67.82 0.39
96.38 1: 0.60
w/o
81,99 + 0.68
91.83 a 0.55
72.47 0.40
79.56 + 0.43
70.42 1 0.36
66.90 0.17
92.10 + 1.72
w/o PE & AP
80.74 0.65
91.14 + 0.30
0.76
0.41
70.69 + 0.48
66,24 + 0.62
90.74 + 1.06
SP Ene
Mean
80.42 + 0.48
91.11 + 0.49
72.08 0.66
79.82 0.42
71.25 + 0.54
64.62 0.21
90.58 4 0.48
GRU
80.91 # 0.33
90.05 + 0.71
72.23 + 0.41
79.54 + 0.41
70.92 + 0.56
65.88 + 0.11
91.88 # 2.93
Transformer
82.62 0.39
92.28 = 0.39
72.89 # 0.68
80.19 0.41
71.23 + 0.51
67.26 0.22
96.71 + 0.59
FLICKR Node
FLICKR-S
OGBL-COLLAB Link
IMDB-B Graph
COLLAB Graph
REDDIT-MI2K REDDIT-MSK
Task
Node
Graph
Graph
GPM
52.22 + 0.19
89.41 = 0.47
49.70 0.59
82.67 0.47
80.70 + 0.74
51.87 1.04
43.07 + 0,29
Comp.
w/o PE
52.26 # 0.20
88.45 + 0.80
49.59 + 0.65
79.00 # 1.63
78.00 + 1.07
50.88 0.78
41.73 4 0.83
w/o AP
51.52 0.12
88.14 0.53
0.997
80.48 2.18
78.33 4 0.24
1.51 49.08
39.73 4 1.09
w/o PE AP
51.39 0.01
87.70 + 0.40
48.24
81.33 3.30
75.40 + 0.99
48.73 0.25
39.50 + 0.46
SP Ene
Mean
0.06
89.86 + 0.26
47.83 1.00
83.33 0.94
76.27 + 0.47
47.30 2.33
40.78 4 0.31
GRU
51.12 0.006
90.13 + 0.31
48. 1
82.00 2.83
74.00) + 1.57
47.12 + 1.44
42.44 + 0.83
Transformer
52.22 + 0.19
89.41 + 0.47
49.70 + 0.59
82.67 + 0.47
80.70 + 0.74
51.87 + 1.04
43.07 + 0.29
19

---

Beyond Message Passing: Neural Graph Pattern Machine
marginal, while the impact of anonymous paths is more pronounced. This diserepancy suggests that GPM, which learns from graph patterns rather than individual nodes, benefits more from understanding the structural composition of patterns than from knowing the specific locations of nodes within them. Notably, when both components are removed, model performance deteriorates significantly, highlighting the necessity of topological information for effective learning.
Impact of Semantic Path Encoders. We analyze the effect of different semantic path encoders, including Mean, GRU, and Transformer. The Transformer encoder achieves the best performance on 11 out of datasets, owing to its inherent ability model both localized and long-range dependencies. Comparing Mean and GRU, we observe that GRU outperforms Mean on heterophilous graphs ge.g.. Deezer, Blog, Flickr-S), likely due to its recurrent structure, which better captures long-range dependencies in the data.
F.3. Additional Discussion on Learning Strategies
Multi-Scale Learning. Table 10 presents the model performance with and without multi-scale training. The results demon- strate that multi-scale training generally enhances performance across various tasks, with the exception of heterophilous graphs (Blog. Flickr, Flickr-S). This suggests that sampling graph patterns of varying sizes effectively captures different levels of information dependencies. However, in heterophilous graphs, which inherently favor long-range dependencies, sampling smaller patterns may overemphasize localized structures, leading to performance degradation.
Table 10, Impact of multi scaling training.
PRODUCTS Node
COMPUTER Node
ARXIV Node
WIKICS Node
CORAFULL Node
DEEZER Node
BLOG Node
Task
GPM
82.62 0.39
92.28 0.39
72.89 + 0.68
80.19 0.41
71.23 0.51 62.55 + 0.52
67.26 0.22 64.56 4 0.16
96.71 0.59
w/o multi-scale
82.44 # 0.20
91.00 = 0.42
71.79 + 0.40
80.05 + 0.32
97.02 + 0.47
FLICKR Node
FLICKR-S Node
OGBL-COLLAB Link
IMDB-B BB
COLLAB Graph
REDDIT-M5K
REDDIT-MI2K Graph
Task
Graph
Graph
GPM
52.22 = 0.19 52.26 # 0.14
89.41 0.47
49.70 0.59
82.67 + 0.47
80.70 0.74
51.87 1.04
43.07 0.29
w/o multi-scale
90.68 # 0.79
48.30 + 0.39
82.33 # 1.89
77.73 # 0.90
47.87 # 0.98
41,46 # 0.40
Test-Time Augmentation. Table 11 presents the impact of test-time augmentation in GPM. We evaluate three variants: (1)
1r,in=16, 16, # infer=/28, where 16 patterns are used during training and 128 during inference (the default setting); (2)
Train=16, # Infer=16, which uses 16 patterns for both training and inference, serving as the lower bound of GPM; and (3) #
128, # Infer=128, where 128 patterns are used in both training and inference, representing the upper bound of GPM.
Comparing # Train=16, # Infer=16 with # Train= # Infer= 128, we observe that increasing the number of patterns significantly improves performance but also incurs substantial computational overhead (Table 12). To balance high performance with computational efficiency in training, we adopt # Train=16, # Infer=/28, where fewer patterns are used during training while maintaining a larger number during inference. Interestingly, in some cases, this variant even outperforms # 128, # Infer= 128, possibly due the reduced risk of overfitting of fewer patterns in training.
Table 11. Impact of test- time augmentation.
PRODUCTS
COMPUTER Node
ARXIV Node
WIKICS
CORAFULL Node
DEEZER Node
BLOG Node
Task
Node
Node
1rain=16 # Infer=128
82.62 0.39
92.28 0.39
72.89 0.68
80.19 0.41
71.23 0.51
67.26 2 0.22
96.71 0.59
Train=16 Infer=16
80.89 = 0.23
90.10 + 0.48
69.90 = 0.00
78.45 0.55
62.57 + 0.35
64.54 0.27
86.53 = 0.57
128 # Infer=128
82.39 = 0.50
92.54 = 0.74
72.42 + 0.00
80.83 = 0.50
71.24 : 0.06
67.71 0.09
96.48 = 0.24
FLICKR Node
FLICKR-S Node
OGBL-COLLAR
IMDB-B Graph
COLLAB Graph
REDDIT-MI2K REDDIT-M5K
Task
Link
Graph
Graph
1rain=16 # Infer=128
52.22 0.19
89.41 = 0.47
49.70 0.59
82.67 = 0.47
80.70 + 0.74
51.87 1.04
43,07 = 0.29
1rain=16 # Infer=16
50.07 = 0.08
81.15 + 1.42
47.30 + 0.69
81.33 = 1.25
76.27 # 0.38
44.53 # 0.81
39.12 0.62
12a # Infer=128
52.85 # 0.28
89.28 0.42
49,92 + 0.53
82.87 + 3.05
80,93 # 0.81
$1.27 & 0.93
43.27 + 0.04
20

---

Beyond Message Passing: Neural Graph Pattern Machine
Table 12. Training time (second per epoch) and acceleration of using less patterns.
PRODUCTS
COMPUTER
ARXIV
WIKICS
FLICKR
# Train = 128
682.07s
19.15s
179.78s
0.92s
83.36s
# Train 16
44.58s
1.22s
12.84s
0.08s
5,54s
Acceleration
x 15.30
x15.70
x x14.00
11.50
x5.05
G. GPM Automatically Learns Data Dependencies
Graph datasets often exhibit a mixture of localized and long-range dependencies. While social networks are commonly assessed to preserve localized dependencies (Granovetter, 1973; Liben-Nowell Kleinberg, 2003), certain tasks demand an understanding of long- -aaggr dependencies. For instance, detecting rumor spreaders involves tracing information flow across the network (Bian al., 2020), rumors propagate through multiple intermediaries, with the origin potentially disconnected from many affected nodes.
Leveraging the transformer architecture, GPM can automatically identify dominant patterns (no matter localized or long- range) relevant to downstream tasks. This capability allows the model to learn the underlying data dependencies within the graph. Such a property not only reduces the need for extensive hyperparameter tuning, where other models might require different hyperparameter settings to capture varying dependencies, but also enhances overall performance.
We conduct experiments on the PRODUCTS dataset. By leveraging biased random walks for pattern sampling, we control 1, 1), localized (p 0.1, q 10), long-range (p 10, 9 = 0.1) patterns. Figure 5 presents the training loss and testing accuracy under these settings. The results show that models using unbiased random walks (p- = 1, 1). which uniformly sample patterns with both localized and long-range dependencies, achieve the best performance. This validates that the model can autonomously determine the importance of different patterns. In contrast, when data dependencies are pre-determined (p = 0.1, 10 or p = 10, q 0.1), the model may fail to capture the most relevant patterns for each instance, leading to degraded performance.
the sampling bias to generate mixed
An intriguing and counterintuitive observation is that models utilizing long-range patterns outperform those relying on localized patterns, even on graphs with high homophily ratios. This phenomenon, consistently observed across other datasets, can be attributed to the large degree of duplication in sampled localized patterns, which arises from the long-tail degree distribution of nodes. Such duplications hinder the model to identify truly dominant patterns, impairing performance. In contrast, long-range patterns, while containing more noise, are less redundant and have a higher probability of including the dominant patterns. However, the noise inherent in long-range sampling still prevents optimal performance. Based on these observations, we hypothesize that unbiased sampling achieves balance between redundancy and noise, enabling the model learn more effectively.
H. Model Interpretation on COMPUTERS
See Figure 8.
21

---

Beyond Message Passing: Neural Graph Pattern Machine
6764
6762
7004
6762
0335
107
3322
1133
15331
13157
1131
2026
13356
6570
6292
6028
1704
1000
1003
6762
1003
3113
1434
1033
1237
123)
13723
(560
(a) Node index 1003
4859
2097
1150
9723
1053
11100
3058
1119
1108
7518
2023
1853
2018
5913
6222
1993
9607
2036
1056
6057
2047
11033
6735
2026
2028
33370
3028
2036
1022
557
13:00
6052
13101
(b) Node index 1056
12093
5355
5a05
5185
5033
8974
7063
1220
1992
6036
4074
1005
6764
2025
5422
4825
9313
4023
3390
9135
$245
6974
6143
3074
1013
12042
2513
263
$139
1633
1500
18339
12377
9250
12414
3103
10747
2314
(c) Node index 5885
Figure 8. The top- 10 important patterns associated to the certain nodes.
22


Reviews:
[{"review_id": "ynK6vK1I9m", "reviewer": "Reviewer_uZYz", "summary": "This paper introduces a framework for graph learning named Neural Graph Pattern Machine (GPM). It aims to directly capture substructure patterns instead of relying on message-passing mechanisms. The model leverages random walks to extract graph patterns, and then convert them into semantic paths and anonymous paths. These paths are encoded separately through a Transformer-based architecture to learn deep representations. Empirical evaluations are conducted across multiple tasks, including node classification, link prediction, and graph regression. The experimental results can demonstrate GPM’s superiority over baseline models including message-passing and other Transformer-based models. The paper also highlights its robustness to distribution shifts, scalability, and interoperability.\n\n## update after rebuttal\nThank you for the authors' rebuttal. I will keep my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their detailed and insightful feedback, as well as for recognizing our contributions in methodology, theoretical insights, and empirical performance. We particularly appreciate the constructive suggestions regarding theoretical clarity, experimental completeness, and related work comparisons, which have helped us significantly improve the manuscript.\n\n> Discussion and comparison to related works.\n> \n\nWe highlight several key differences between GPM and NeuralWalker: **(1) Task-adaptive tokenization**: NeuralWalker tokenizes graphs into random walks uniformly across all tasks. In contrast, GPM performs **task-specific pattern sampling**—for example, node-level tasks focus on patterns centered around each node, while graph-level tasks use global structures. This adaptivity is a central design of GPM. **(2)** **Representation granularity**: NeuralWalker encodes each node within a walk and updates node-level embeddings, resulting in multiple embeddings per walk. GPM, on the other hand, produces a **single representation per walk**, capturing the semantics of the entire pattern rather than individual nodes. **(3) Architecture paradigm**: GPM is a **fully message passing-free** architecture, whereas NeuralWalker still relies on message passing components to explicitly model local information.\n\nRegarding CAW, both CAW and GPM use anonymous paths as substructure patterns. However, their purposes and applications differ: **(1) Domain**: CAW is designed for **temporal graphs**, while GPM is intended for **attributed static graphs**. **(2) Tokenization**: Like NeuralWalker, CAW performs **uniform walk sampling**, regardless of the task. GPM introduces an **adaptive tokenizer** tailored to different downstream objectives. **(2) Task scope**: CAW primarily focuses on **link prediction**, while GPM supports **node, link, and graph-level tasks**.\n\nWe summarize the empirical comparison between GPM and NeuralWalker in the following table. Since CAW is designed for temporal graphs, it does not naturally apply to the datasets used in this paper:\n\n| **Task** | **Dataset** | **NeuralWalker [1]** | **CAW [2]** | **GPM (ours)** |\n| --- | --- | --- | --- | --- |\n| Node Classification | WikiCS | 78.55 | - | **80.19** |\n| Link Prediction | Cora | 87.50 | - | **92.85** |\n| Graph Regression | ZINC | **0.053** | - | 0.064 |\n\n[1] Learning Long Range Dependencies on Graphs via Random Walks. (ICLR’25)\n\n[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks. (ICLR’21)\n\n> Elaborate on Proposition 3.3.\n> \n\nWe apologize for the confusion and appreciate the opportunity to clarify. In Proposition 3.3, the term *\"comprehensive\"* refers to the ability to capture both **semantic (feature-level)** and **structural (topological)** information of a graph pattern by jointly modeling its **semantic path** and **anonymous path**. Specifically, a graph pattern can be decomposed into a semantic path (preserving node/edge attributes) and an anonymous path (preserving topology only). These paths, being sequential, can be bijectively projected into fixed-size embeddings without loss of information. Therefore, embedding a graph pattern can be obtained by combining the embeddings of its semantic and anonymous paths.\n\nThis proposition is intended to provide the intuition behind GPM’s dual encoding design and emphasizes the necessity of modeling both views to capture rich structural and semantic signals.\n\n> The Important Pattern Identifier is a straightforward application of Transformer interpretability.\n> \n\nWe appreciate this feedback and would like to clarify the intent of this module.\n\nThis component serves primarily as an **aggregation mechanism** over encoded graph patterns. We chose to use the Transformer for this role due to its proven effectiveness across domains, e.g., CV and NLP. While we acknowledge that Transformer attention is not novel per se, its **emergent interpretability**—i.e., its ability to highlight important substructures—was a valuable and interpretable byproduct. This insight supports GPM’s modular design, where effective aggregation and interpretability naturally align.\n\n> The missing numbers are not explicitly explained in the text.\n> \n\nThank you for pointing this out. We will update the text to clarify that missing values (denoted as “-”) correspond to baselines for which: **(1)** **Computational constraints** (e.g., tuning models such as VCR-Graphormer, GEANet) made training impractical, or **(2) Reproducibility issues** (e.g., unavailable official code for RAW-GNN, GraphMamba, GCFormer) prevented fair comparison.\n\nWe prioritized reporting results for the most informative and representative baselines under a consistent evaluation protocol.", "claims_and_evidence": "Strengths:\n1. The advantages of the proposed GPM are empirically supported by experimental results on node/edge/graph learning tasks. The method is computationally efficient compared to the naive GCN.\n2. The paper is well-structured and clearly written. The authors effectively explain their motivation, methodology, and results.", "methods_and_evaluation_criteria": "Strengths:\n1. The method is both conceptually sound and practically feasible\n2. The evaluation criteria follow common practices and make sense.", "theoretical_claims": "Strengths:\n1. The paper provides a comprehensive theoretical study. These theoretical insights help establish the foundations of the proposed method and its advantages over traditional message-passing GNNs.\n\nWeaknesses:\n1. The statement of proposition 3.3 “provide a comprehensive representation…” lacks rigor. The term “comprehensive” is a subjective description. Also, I didn’t understand how the proof in Appendix C.2 proves this claim.", "experimental_designs_or_analyses": "Strengths:\n1. The experimental evaluation is thorough, covering multiple tasks including node classification, link prediction, and graph regression. A wide range of baseline models are compared. \n2. The proposed GPM demonstrates strong empirical results across various datasets, outperforming or matching state-of-the-art models in benchmark tasks. These results suggest that the method is competitive and effective in real-world applications.\n\nWeaknesses:\n1. The missing numbers in Table 1 are not explicitly explained in the text.", "relation_to_broader_scientific_literature": "Strengths:\n1. A wide range of existing methods are discussed including both message-passing based and tokenization based models. \n\nWeaknesses:\n1. Extracting subgraph patterns with random walk and anonymous walk have been studied in previous papers [1, 2]. [1] was published on the recent ICLR’25 but was posted on arxiv on Jun, 2024. [2] studied anonymous walks for temporal networks which are based on GNNs. These papers should be discussed and compared as well since the main idea of GPM seems very relevant to them. \n2. The proposed Important Pattern Identifier is a straightforward application of Transformer interpretability. This part doesn’t show a significant technical contribution. \n\n[1] Learning Long Range Dependencies on Graphs via Random Walks. (ICLR’25)\n[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks. (ICLR’21)", "essential_references_not_discussed": "See above [1,2].", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please address the Weaknesses listed above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8ucsijoe7y", "reviewer": "Reviewer_M2he", "summary": "This paper proposes GPM, a graph transformer based on randomly sampling walks in the graph. GPM achieves strong empirical results across a variety of datasets and types of tasks. Furthermore, by sampling a large number of paths (or very long paths) GPM achieves high expressivity.\n\n## update after rebuttal\nThe authors did provide substantial explanations and additional experiments during the rebuttal. This has caused me to increase my score (see latest rebuttal comment).", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your recognition of the strengths of our method and experimental evaluation. While we take your concerns about the theoretical aspects seriously, we would like to emphasize that the primary contribution of our work lies in the **model design and empirical success**; the theoretical components are included to provide **insight into our design choices**, rather than to serve as the core contribution. We address each point in detail below and are committed to improving clarity and rigor in future revisions.\n\n> Related works on graph expressiveness\n> \n\nThank you for pointing out these relevant works. While GPM shares high-level similarities with [1], it differs significantly in approach: GPM is a **data-driven framework** that learns task-relevant patterns through sampling and optimization, whereas [1] takes a **theoretical route**, leveraging homomorphism counts to prove expectation-completeness using random subgraph probes.\n\nCompared to PathNN [2] and PAIN [3], which also rely on random walks, GPM distinguishes itself by using a **Transformer to aggregate pattern-level embeddings**, rather than encoding enumerated paths [2] or sampled paths [3]. This enables **pattern-centric reasoning** and contributes to improved **generalization** across tasks and graph scales.\n\nEmpirically, GPM outperforms all three baselines on the ZINC regression benchmark, evaluated via MAE: \n\n| **Dataset** | **GIN + hom + F [1]** | **PathNN-AP [2]** | **PAIN [3]** | **GPM (ours)** |\n| --- | --- | --- | --- | --- |\n| ZINC | 0.174 | 0.090 | 0.148 | **0.064** |\n\n[1] Expectation-Complete Graph Representations with Homomorphisms\n\n[2] Path Neural Networks: Expressive and Accurate Graph Neural Networks\n\n[3] The Expressive Power of Path based Graph Neural Networks\n\n> Theoretical runtime\n> \n\nWe appreciate the reviewer raising this point. Indeed, in the worst-case scenario (e.g., dense graphs), the number of paths within a k-hop neighborhood can grow exponentially with k, making full enumeration intractable. However, **GPM does not require exhaustive enumeration**. Instead, we perform **efficient random walk sampling** to approximate the distribution over substructures:\n\n- In practice, we sample a fixed number of paths per node (e.g., 128) of fixed length (e.g., 8), independent of the total k-hop neighborhood size. This provides predictable runtime and memory cost, even on large-scale graphs. Notably, sampling random walks on graphs with over **2.5 million nodes** in under two minutes.\n- Theoretical analysis in Proposition 3.2 assumes access to the full pattern space, but empirically we find that a **small number of walks (i.e., 128)** is sufficient for strong performance.\n\n> Mathematical precision\n> \n\nWe thank the reviewer for the detailed feedback. We agree that the current formulation of Propositions 3.2, 3.3, and Theorems 3.4 and 3.5 is informal and lacks full mathematical rigor. These results were intended to provide **conceptual insights** into the representational power of GPM, not to constitute formal theoretical contributions.\n\nThat said, we will: (1) **Revise Theorem 3.4** to state clearly that *GPM can distinguish all pairs of non-isomorphic graphs given a sufficiently rich set of patterns*. (2) **Demote Theorem 3.5** to a corollary or informal observation, as it logically follows from Theorem 3.4. (3) Explicitly **mention the reconstruction conjecture** and its role in the assumptions underlying these results.\n\nRegarding the proof of Theorem 3.4: we agree that our phrasing was misleading. We did **not mean to suggest** that long walks can be **fully reconstructed** from shorter ones, especially since anonymous walks cannot preserve node identity across segments. Rather, we intended to describe an **approximate strategy**, where **long walks are segmented into shorter sub-walks**, each encoded independently. This design allows the transformer to aggregate distributed long-range information across these sub-patterns. We will revise the wording in the appendix to reflect this more accurately and avoid overstating the implications.\n\nTo reiterate, our theoretical analysis is included to motivate and clarify design choices. We will clearly label these components as **heuristic or informal** in future revisions to avoid confusion.\n\n> Other modifications and clarifications\n> \n\n**Modifications**: We thank the reviewer for pointing this out. We will update the definition of a graph and the definition 3.1 in our future version. \n\n**Clarifications**: We appreciate the question about sampling consistency in the expressiveness analysis (Table 8). To clarify: GPM samples patterns **locally from each graph**, with the goal of capturing the **structural fingerprint** of each instance via its own distribution of substructures. **different patterns are not a source of trivial separability**, but rather a core mechanism for capturing graph-specific structure. Using a shared pattern set would **reduce discriminative power**.", "claims_and_evidence": "The experimental claims are solid, the evidence supporting theoretical claims could be improved (see below).", "methods_and_evaluation_criteria": "See below.", "theoretical_claims": "I have skimmed all proofs in the appendix. While they seem to hold, mathematical statements are often imprecise (see below).", "experimental_designs_or_analyses": "This paper very thoroughly evaluates their methods for different tasks and datasets. Overall, I think that the experiments are solid (see Strengths) except the question I raise in (Questions For Authors).", "relation_to_broader_scientific_literature": "I think the related work is mostly fine, but is missing a few references (see below).", "essential_references_not_discussed": "The expressivity of of GPM is based on randomly sampling graph patterns. It seems that (1) is essential related work, as (1) propose expressive GNNs based on randomly sampled patterns (homomorphisms). Furtherme, since the architecture is based on walks I believe that recent literature on path-based GNNs should also be discussed such as (2,3). \n\n(1) Welke at al., _Expectation-Complete Graph Representations with Homomorphisms_, ICML 2023  \n(2) Gaspard et al., _Path Neural Networks: Expressive and Accurate Graph Neural Networks_, ICML 2023  \n(3) Drucks et al.,  _The Expressive Power of Path based Graph Neural Networks_, ICML 2024", "other_strengths_and_weaknesses": "**Strengths:**\n- (S1). The (non mathematical) sections are well written and easy to follow.\n- (S2). The proposed method is conceptually elegant and the paper has many small, clever ideas. In particular, the test time augmentation (only sampling few paths during training to speed it up but sampling a lot of paths to achieve strong inference results) seems really interesting.\n- (S3). The experiments are more than solid. The authors select a wide range of different tasks (node predictions, link predictions, graph predictions, synthetic graph distinction) and achieve good results. All in all, I believe that the experimental part of this paper is excellent.\n\n**Weaknesses:**\n- (W1). Theoretical runtime. The proof of Proposition 3.2 requires sampling as many paths as the size of the $k$-hop neighborhood (for each node). Sampling this many paths for every node is computationally expensive (at least quadratic in the worst case).\n- (W2). Mathematical precision. Definitions are incomplete (see below), Propositions and Theorems are formulated descriptively but are not precise mathematical statements.  Some examples of this:\n\t- Proposition 3.2 and 3.3 are informal.\n\t- Theorem 3.4: \"GPM can distinguish non-isomorphic graphs given a sufficient number of graph patterns.\" This formulation is wrong: MPNNs are also able to distinguish non-isormophic graphs (just not all of them). I think what was meant is: \"GPM can distinguish all pairs of non-isomorphic graphs given a sufficient number of patterns\".\n\t- If my interpretation of Theorem 3.4 is correct, then Theorem 3.5 should be a simply corrollary of Theorem 3.4 instead of a theorem.\n\t- Theorem 3.4 and 3.5 rely on the reconstruction conjecture to be true which I believe is not mentioned in the main text.\n\t- Proof of Theorem 3.4: _\"The simplified case assumes $n = 1$ with a sufficiently large walk length $l$, whereas GPM operates with $n > 1$. Since random walks can start from any node in the graph, an $l$-length random walk can be split into $k$ segments ($k$ is large enough), each of length $l/k$. Each sub-walk can be encoded individually and later combined to form the final embedding\"_. I do not think long walks can simply be reconstructed from shorter walks as anonymous walks do not allow to match nodes between different walks.\n\n\n**Overall,** this is a difficult decision for me. The experimental side of this paper is strong and I wish all GNN papers would so thoroughly evaluate their architecture on different tasks. However, the mathematical / theoretical side needs extensive improvements. Thus, I am in favor of rejecting as I believe that the required changes are too large to be done in the process of the rebuttal. I hope the authors will re-write the problematic sections and look forward to seeing this paper at a future conference.", "other_comments_or_suggestions": "- A graph is defined as $G = (V, E)$, this should also include the node features. Since the paper also mentions edge feature, they should also be defined here.\n- Definition 3.1 seems incomplete as the $pos$ function is not defined", "questions_for_authors": "- For the \"Empirical expressiveness analysis\" (Tab 8 Appendix), did you ensure that the same patterns get sampled for pairs of graphs that you try to distinguish? If not, then your model would be trivially be able to distinguish 100% of all pairs.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LHHk9o6I5n", "reviewer": "Reviewer_Ynb7", "summary": "The paper introduces the Neural Graph Pattern Machine (GPM), a framework designed to enhance the expressiveness of graph learning models by directly learning from graph patterns. Traditional Graph Neural Networks (GNNs) rely on message passing to aggregate information from local neighborhoods, which can limit their ability to identify fundamental substructures, such as triangles. GPM addresses this limitation by efficiently extracting and encoding substructures, identifying the most relevant ones for downstream tasks. Empirical evaluations across various tasks, including node classification, link prediction, graph classification, and regression, demonstrate GPM's superiority over state-of-the-art baselines. The paper also highlights GPM's robustness, scalability, and interpretability, offering a comprehensive analysis of its performance. Overall, the paper is well-organized and clearly presented.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful and encouraging review. We’re glad the reviewer appreciated our contributions in expressiveness, scalability, and interpretability. We also appreciate the constructive suggestions regarding additional experiments, and we address each point in detail below.\n\n> GPM has the potential to overcome over-smoothing. Need more experiments.\n> \n\nAbsolutely — we also believe that GPM naturally mitigates the over-smoothing problem. In traditional message-passing GNNs, deeper networks tend to aggregate node features from increasingly distant neighbors, often leading to over-smoothing. In GPM, the analogous hyperparameter is the **random walk length**, which controls the receptive field of each pattern.\n\nTo investigate this, we conducted experiments on **WikiCS** (node classification) and **COLLAB** (graph classification), varying the random walk length in [4, 8, 16, 32, 64]. As shown in the table below, while standard models like GraphSAGE and GIN suffer significant performance degradation as depth increases, GPM maintains strong performance, with only a slight drop at extreme walk lengths. We attribute this to GPM's architecture, where a **Transformer processes each sampled walk independently**, effectively decomposing hop-level interactions, rather than stacking layers that prioritize low-order information.\n\n| **Model Layer / Walk Length** | **4** | **8** | **16** | **32** | **64** |\n| --- | --- | --- | --- | --- | --- |\n| **WikiCS (Node classification)** |  |  |  |  |  |\n| SAGE | 78.50 | 73.38 | 68.35 | 64.32 | 30.58 |\n| GPM (ours) | 79.64 | **80.19** | 80.52 | 78.98 | 77.31 |\n| **COLLAB  (Graph Classification)** |  |  |  |  |  |\n| GIN | 80.31 | 79.30 | 75.44 | 72.68 | 65.38 |\n| GPM (ours) | 80.45 | **80.70** | 80.66 | 79.53 | 77.39 |\n\n> Experiments on heterogeneous graphs\n> \n\nWe appreciate the suggestion and have conducted additional experiments on heterogeneous graphs. Specifically, we evaluated GPM on two widely used datasets: **ACM** and **DBLP**. To handle heterogeneity, we adopt a simple yet effective strategy: for each node type, we use a **type-specific Mapping** to project the features into a shared latent space, following the approach in [1].\n\nWe compare GPM with strong baselines including Metapath2vec, RGCN, HAN, HeCo, and HGT. Using the standard 20/40/40 split and Micro-F1 as the metric, GPM outperforms all baselines:\n\n| **Dataset** | **Metapath2vec** | **HAN** | **HeCo** | **HGT** | **GPM (ours)** |\n| --- | --- | --- | --- | --- | --- |\n| ACM | 82.96 | 90.45 | 91.23 | 91.12 | **93.27** |\n| DBLP | 89.02 | 92.60 | 93.24 | 92.55 | **94.29** |\n\n[1] Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks, KDD 21. \n\n> Experiment on large graphs, like OGB.\n> \n\nThank you for pointing this out. In fact, we already include experiments on large-scale **OGB benchmarks** in the main paper: **ogbn-arxiv (Arxiv)**, **ogbn-products (Products)**, and **ogbl-collab**. The **ogbn-products** dataset, for instance, includes **2,449,029 nodes** and **123,718,024 edges**. Despite the scale, GPM maintains high scalability and **consistently outperforms baselines** across these large benchmarks. For example, GPM achieves 82.62 in ogbn-products yet the best baseline just achieves 82.00. \n\n> Strongly recommend the author publicly disclose the code to facilitate reproducibility.\n> \n\nWe completely agree, and we are fully committed to open research. We have provided the code in the supplement. We will release the full source code and instructions upon publication.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "yes", "experimental_designs_or_analyses": "yes\nIn Section 4.3, the authors highlight that traditional message-passing Graph Neural Networks (GNNs), such as the Graph Attention Network (GAT), encounter scalability challenges due to the oversmoothing effect. This phenomenon occurs when node representations become indistinguishable as the number of GNN layers increases, ultimately diminishing model performance. To address this issue, the proposed Neural Graph Pattern Machine (GPM) takes a novel approach by learning directly from graph patterns instead of relying solely on message passing. By efficiently extracting and encoding substructures, GPM strives to preserve distinctive node representations. Therefore, it should have the potential to overcome the oversmoothing problem, (if my understanding is correct). However, further experiments are needed to substantiate this claim.", "relation_to_broader_scientific_literature": "The key contributions of this paper relate to the broader scientific literature as follows:\n\nNew Approach: The framework, GPM, overcomes the limitations of traditional GNNs like restricted expressiveness and oversquashing, echoing ongoing research efforts in addressing these issues.\n\nScalability: GPM scales better for complex tasks involving large models and graphs, contributing to the field's discussions on handling vast datasets.\n\nInterpretability: GPM provides a way to interpret models, which is crucial for applications like social network analysis and drug discovery. This aligns with the growing focus on the interpretability of GNNs in the literature.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The main shortcomings of this paper lie in its reliance on existing technology. However, the author has provided valuable insights into the rationale behind using this technology, supported by corresponding evidence, and conducted thorough experiments. Including experiments specifically aimed at overcoming the oversmoothing issue would further enhance the paper's contributions.", "other_comments_or_suggestions": "1. Strongly recommend the author publicly disclose the code to facilitate reproducibility.\n\n2. Suggest adding experiments on heterogeneous graphs. While the author mentions this in the limitations section, evaluating GPM's classification potential on heterogeneous graphs would be valuable.\n\n3. Recommend increasing experimental comparisons to address oversmoothing. For instance, increasing the number of network layers to evaluate model performance would be beneficial.\n\n4. How does the model perform on large datasets, such as OGB? Including an assessment of GPM's performance on big datasets would strengthen the paper.", "questions_for_authors": "How does the model perform on large datasets, such as OGB?\nHow does the model perform on the heterogeneous graph dataset?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NkzhMGzKh4", "reviewer": "Reviewer_ykrV", "summary": "## Update after rebuttal\nThe authors have solved most of my concerns. I decide to maintain my score.\n\nGraph neural networks struggle to capture essential substructures, such as triangles in social networks or benzene rings in molecular graphs, due to their reliance on message passing. To address this limitation, the Neural Graph Pattern Machine (GPM) is introduced as a framework that directly learns from graph patterns, efficiently extracting and encoding substructures while identifying those most relevant to downstream tasks. Theoretically, GPM surpasses message passing in expressivity and long-range information modeling.  The authours have conducted extensive experiments across multiple graph learning tasks to demonstrate its superiority over state-of-the-art baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We appreciate your constructive suggestions regarding related work and theoretical clarification, and we address each of these points in detail below.\n\n> A detailed comparison to RUM.\n> \n\n**Motivation**: RUM is designed to jointly address expressiveness, over-smoothing, and over-squashing within a message-passing-motivated framework (see below). In contrast, GPM is motivated by **bypassing message passing** and learning directly from **substructure patterns**.\n\n**Graph Inductive Bias**: While both RUM and GPM use **semantic paths** and **anonymous paths** to represent individual walks, their modeling approaches diverge significantly. RUM utilizes **RNNs (GRUs)** to encode these paths, following a philosophy aligned with message passing—where localized information dominates importance. GPM, however, leverages **Transformers** to encode semantic paths, allowing the model to **learn inductive biases directly from data**, particularly important in tasks requiring **long-range dependency modeling**.\n\n**Pattern Aggregator**: GPM employs a **Transformer-based aggregator** to combine learned graph pattern representations, whereas RUM uses a **mean aggregator**. This design choice brings several advantages: **(1) Scalability**: GPM scales effectively to large graphs and large model sizes (as demonstrated in Tables 1–3 and Figure 4). **(2)** **Effectiveness**: GPM samples 128 graph patterns per instance during inference (vs. 4 in RUM), and the Transformer allows the model to **attend to the most informative patterns**, yielding superior performance across benchmarks (Tables 1–4). **(3) Interpretability**: The attention mechanism in GPM’s Transformer provides **natural interpretability**, allowing us to identify key substructure patterns (e.g., via attention weights in Figure 5), a feature absent in RUM.\n\n**Empirical Comparison:** The distinctions above enables our GPM consistently outperforms RUM empirically (see Table 1,2,3,4). For example, in large-scale ogbn-product dataset (about 2.5 million nodes), GPM achieves 82.62% accuracy comparing to 78.68% of RUM. \n\n> Explicitly highlight the key differences between GPM and DeepWalk, GraphRNA, RAW-GNN.\n> \n\nWe thank the reviewer for this request and provide the following comparison. **DeepWalk and GraphRNA** follow the principle of representing an entire graph as a collection of random walks that capture **co-occurrence relationships among nodes**. Their differences mainly lie in how walks are generated and encoded. \n\n**GPM and RAW-GNN**, in contrast, adopt the philosophy that **random walks represent individual substructures** of graph instances (nodes, edges, or entire graphs). The key distinctions between GPM and RAW-GNN are (1) **Sampling Strategy**: GPM uses unbiased random walks, reducing inductive bias. RAW-GNN employs biased sampling, which may impose structural priors that limit generalizability. (2) **Structural Representation**: GPM explicitly **decouples topology and semantics** by representing each walk as semantic and anonymous paths. RAW-GNN does not separate structural and feature encoding in this way. (3) **Pattern Aggregation**: GPM uses a **single** Transformer to aggregate all patterns. RAW-GNN uses **separate** aggregators for low- and high-order patterns, which may prevent modeling interactions across different structural levels.\n\n**Empirical Comparison:** Based on the above limitations, GPM consistently outperforms these methods empirically. We show the comparison results on node classification in the following. \n\n| **Dataset** | **DeepWalk** | **GraphRNA** | **RAW-GNN** | **GPM (ours)** |\n| --- | --- | --- | --- | --- |\n| **Computers** | 88.56 | 91.06 | 92.03 | **92.28** |\n| **WikiCS** | 76.34 | 77.65 | 79.01 | **80.19** |\n| **Flickr** | 49.70 | 49.78 | 49.58 | **52.22** |\n\n> Theoretical clarification\n> \n\nTheorem 3.4 demonstrates the **existence** of a sufficient number of graph patterns such that GPM can distinguish any pair of non-isomorphic graphs under its pattern-based encoding. However, this is a **non-constructive** result—it does not provide an explicit bound on the required number of patterns. Establishing such a bound is challenging due to the **combinatorial nature** of graph structures and the fact that the number may depend on: (1) Graph size and topological complexity, (2) The specific classes of non-isomorphic graphs (e.g., regular vs. irregular), (3) The expressiveness of the semantic and anonymous path encoders. \n\nDespite the theoretical uncertainty, our empirical findings show that **sampling 128 random walks per graph** is often sufficient to achieve **perfect accuracy** in distinguishing non-isomorphic graphs (see Table 8). \n\nWe agree that deriving a **tight theoretical bound** on the number of necessary patterns is an important direction for future work, and we appreciate the reviewer for highlighting this.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, see the weakness.", "experimental_designs_or_analyses": "See the weakness.", "relation_to_broader_scientific_literature": "See the weakness.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\nRefer to the summary.\n\nWeaknesses:\n1. The fundamental framework of GPM appears similar to [1]. It is recommended that the authors provide a detailed comparison to clarify the distinctions between their approach and this prior work.\n\n2. Regarding the Pattern Encoder, numerous studies have explored the integration of Random Walk with GNNs/RNNs, including DeepWalk [2], GraphRNA [3], and RAW-GNN [4]. The authors should explicitly highlight the key differences between GPM and these existing methods.\n\n3. In Theorem 3.4, GPM is shown to distinguish non-isomorphic graphs given a sufficient number of graph patterns. However, how is this number determined? Are there theoretical bounds on the required number of patterns? Addressing this would be crucial, as it represents a trade-off between computational complexity and learning sufficiency.\n\n[1] Wang Y, Cho K. Non-convolutional graph neural networks[J]. arXiv preprint arXiv:2408.00165, 2024.\n[2] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 2014: 701-710.\n[3] Huang X, Song Q, Li Y, et al. Graph recurrent networks with attributed random walks[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 732-740.\n[4] Jin D, Wang R, Ge M, et al. Raw-gnn: Random walk aggregation based graph neural network[J]. arXiv preprint arXiv:2206.13953, 2022.", "other_comments_or_suggestions": "No.", "questions_for_authors": "See the weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates the problem of identifying fundamental substructures within graphs using graph learning models. To address this challenge, the authors propose Neural Graph Pattern Machine (GPM), a framework designed to learn directly from graph patterns. GPM efficiently extracts and encodes substructures, while identifying the most relevant ones for downstream tasks. Experiments on several datasets demonstrate the effectiveness of the proposed model.


Strengths:
1. The paper is well-structured and clearly written. The authors effectively explain the motivation, methodology, and results.
2. The proposed method is both conceptually sound and practically feasible.
3. The experiments are sufficiently comprehensive to demonstrate the effectiveness of the proposed model.


Weaknesses:
1. The theoretical runtime analysis may suggest a high computational cost, and the mathematical precision could be improved in some areas.
2. Several related studies should be discussed and potentially compared in the paper to provide a more complete context for the proposed work.



Overall, this paper presents a novel and interesting approach to identifying fundamental substructures in graphs, making valuable contributions to the research field. The paper is well-written, clear, and easy to follow, and the experiments are sufficient to demonstrate the effectiveness of the proposed model. However, the paper would benefit from a more precise explanation of certain mathematical statements to enhance clarity. Additionally, some related studies should be discussed and even compared to strengthen the paper's argument. I recommend that the authors address these issues in the camera-ready version to make the paper more convincing.
Decision: Accept (poster)