Beyond Message Passing: Neural Graph Pattern Machine

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.

A detailed comparison to RUM.

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.

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.

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.

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.

Explicitly highlight the key differences between GPM and DeepWalk, GraphRNA, RAW-GNN.

We 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.

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.

Empirical Comparison: Based on the above limitations, GPM consistently outperforms these methods empirically. We show the comparison results on node classification in the following.

Theoretical clarification

Theorem 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.

Despite 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).

We 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.

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.

GPM has the potential to overcome over-smoothing. Need more experiments.

Absolutely — 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.

To 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.

Experiments on heterogeneous graphs

We 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].

We 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:

[1] Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks, KDD 21.

Experiment on large graphs, like OGB.

Thank 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.

Strongly recommend the author publicly disclose the code to facilitate reproducibility.

We 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.

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.

Related works on graph expressiveness

Thank 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.

Compared 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.

Empirically, GPM outperforms all three baselines on the ZINC regression benchmark, evaluated via MAE:

[1] Expectation-Complete Graph Representations with Homomorphisms

[2] Path Neural Networks: Expressive and Accurate Graph Neural Networks

[3] The Expressive Power of Path based Graph Neural Networks

Theoretical runtime

We 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:

• 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.
• 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.

Mathematical precision

We 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.

That 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.

Regarding 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.

To 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.

Other modifications and clarifications

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.

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.

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.

Discussion and comparison to related works.

We 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.

Regarding 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.

We 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:

[1] Learning Long Range Dependencies on Graphs via Random Walks. (ICLR’25)

[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks. (ICLR’21)

Elaborate on Proposition 3.3.

We 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.

This 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.

The Important Pattern Identifier is a straightforward application of Transformer interpretability.

We appreciate this feedback and would like to clarify the intent of this module.

This 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.

The missing numbers are not explicitly explained in the text.

Thank 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.

We prioritized reporting results for the most informative and representative baselines under a consistent evaluation protocol.