PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Message Passing: Neural Graph Pattern Machine

Zehong Wang, Zheyuan Zhang, Tianyi Ma, Nitesh V Chawla, Chuxu Zhang, Yanfang Ye

arXiv:2501.18739v2cs.LGcs.AIcs.SI

TL;DR

Graph-learning tasks depend on meaningful substructure patterns, but those patterns are not directly modeled by message passing. GPM samples, encodes, and prioritizes graph patterns, and is reported to outperform state-of-the-art baselines across several graph task levels.

  • Problem

    Graph-learning tasks rely on recurring substructures such as triadic closures and benzene rings, which encode meaningful inductive biases and graph semantics.

    Source: §1 · p. 1

  • Method

    GPM samples graph patterns with random walks, encodes semantic and anonymous paths, and uses a transformer to identify patterns relevant to downstream tasks.

    Source: §1 · p. 2, §3.1 · p. 4, §3.3 · p. 5

  • Results

    GPM outperforms state-of-the-art baselines across node-, link-, and graph-level tasks, with reported robustness, scalability, and interpretability.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GPM directly learns graph substructure patterns without message passing and is reported to offer greater expressiveness and capacity to capture long-range dependencies.

    Source: §5 · p. 9

    GPM's prediction performance depends heavily on sampled-pattern quality, and random sampling may increase training and hyperparameter-tuning resource consumption.

    Source: §5 · p. 9

Abstract

from arXiv · show

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.

1. Introduction

Graph-learning tasks rely on substructure patterns that encode meaningful inductive biases and semantics. Because message-passing GNNs aggregate neighborhoods rather than directly model such patterns, GPM learns from patterns instead.

1. Introduction

  • Graph patterns such as triadic closures and benzene rings encode meaningful inductive biases and are central to graph semantics and learning performance.Source: §1 · p. 1
  • Message-passing GNNs aggregate local neighborhoods rather than directly model substructures, limiting their ability to capture motifs such as triangles, stars, and k-cliques.The passage attributes this expressiveness limit to equivalence with the 1-WL test; proposed extensions remain tied to message passing and may bring interpretability, computational-cost, and inductive-bias challenges.Source: §1 · pp. 1–2
  • Graph-pattern methods still face tokenizer, encoder, and pattern-selection challenges, including task-specific tokenizers and uncertainty about performance on localized or mixed dependencies.Source: §1 · p. 2
  • GPM uses random walks to sample patterns, separately encodes semantic and anonymous paths, then applies a transformer to identify task-relevant patterns.The workflow is illustrated in Figure 1.Source: §1 · p. 2, Figure 1 · p. 2
  • GPM outperforms state-of-the-art baselines across node-, link-, and graph-level tasks, with reported robustness, scalability, and interpretability.Source: §1 · p. 2

2. Related Works

Related approaches extend message-passing expressiveness or tokenize graph patterns, but trade-offs in scalability, locality, and task coverage remain. GPM is presented as a direct pattern-learning alternative addressing those gaps.

2. Related Works

3. Neural Graph Pattern Machine

GPM represents graph instances with sampled patterns, separately encodes their semantic and topological structure, and uses a transformer to identify patterns relevant to downstream tasks.

3.1. Pattern Tokenizer

  • Random walks replace fixed-vocabulary pattern matching with sampled semantic paths and anonymous paths that encode graph topology.The tokenizer samples patterns for nodes, edge endpoints, or randomly selected graph nodes, depending on the task.Source: §3.1 · p. 4

3.2. Pattern Encoder

  • GPM encodes semantic paths with a transformer by default and anonymous paths through loop-based adjacency, then combines both embeddings.Optional positional embeddings augment node features; performance can remain competitive without them, and the preferred positional encoding depends on the dataset.Source: §3.2 · p. 5

3.3. Important Pattern Identifier

  • A transformer encoder learns the relative importance of sampled patterns, while an optional class token supports interpretation through its attention scores.The class token is intended primarily to improve interpretability, not performance.Source: §3.3 · p. 5

3.4. Training Strategies

  • Training uses m patterns and inference uses k ≫ m; multi-scale sampling varies walk lengths without changing the number of patterns.The defaults are m = 16, k = 128, and walk lengths [2, 4, 6, 8]; preprocessing pre-samples patterns to reduce sampling overhead.Source: §3.4 · pp. 5–6

3.5. How Does GPM Surpass Message Passing?

  • At task radius 7, GPM fits data perfectly while message-passing methods show over-squashing by radius 4; under stated assumptions, it also distinguishes all non-isomorphic graphs.The theorem assumes connected, unweighted, undirected graphs, sufficiently many patterns, and the reconstruction conjecture; a corollary gives examples beyond k-WL expressiveness.Source: §3.5 · p. 6

4. Experiments

Across node-, link-, and graph-level tasks, GPM performs strongly against existing methods; the experiments also examine its out-of-distribution robustness, scalability, component contributions, and pattern interpretation.

4.1. Applicability to Graph-based Tasks

  • GPM outperforms message-passing and random-walk GNNs across node-classification datasets, is best on the evaluated link-prediction datasets, and consistently leads graph classification and regression methods.Among node-classification graph transformers, GPM is superior on most datasets, with CoraFull the exception.Source: §4.1 · pp. 6–7, Table 1 · p. 7, Table 2 · p. 7

4.2. Out-of-Distribution Generalization

  • GPM outperforms existing OOD-specific methods in settings such as A →D and Twitch, and combining it with DANN or SSReg improves results across all settings, particularly D →A.The evaluation trains on a source graph and tests on a target graph; Twitch training uses DE and evaluation covers the other five graphs.Source: §4.2 · p. 7, Table 4 · p. 8

4.3. Scalability

  • GPM’s instance encoding has complexity O(k^2) and overall complexity O(n · k^2), enabling mini-batch scaling to large graphs; it achieves competitive results on Products, ogbl-Collab, and ZINC-Full.Here n ≫ k^2 denotes the number of instances.Source: §4.3 · p. 8
  • Increasing GPM parameters enhances performance on large-scale graphs, while GPM also achieves greater distributed-training efficiency than message-passing GNNs on PRODUCTS.The parameter-versus-accuracy comparison and GPU-count-versus-acceleration-ratio comparison are shown in Figure 4.Source: §4.3 · p. 8, Figure 4 · p. 8

4.4. Ablation Study

  • Anonymous paths contribute more than positional embeddings; a Transformer is the best semantic-path encoder because it models localized and long-range dependencies.Positional embeddings encode relative node positions, while anonymous paths characterize pattern structures.Source: §4.4 · p. 9, Table 5 · p. 9
  • Multi-scale training raises average accuracy from 70.72 to 72.34, while test-time augmentation reduces training cost with negligible performance drop, from 72.43 to 72.34.The augmentation uses fewer patterns during training, for example 16 at training versus 128 at inference.Source: §4.4 · p. 9
  • On PRODUCTS, unbiased random-walk sampling (p = 1, q = 1) performs best among the tested criteria, allowing GPM to balance localized and long-range dependencies.It is compared with localized (p = 0.1, q = 10) and long-range (p = 10, q = 0.1) sampling.Source: §4.4 · p. 9, Figure 5 · p. 9

4.5. Model Interpretation

  • On ZINC, GPM’s top-9 patterns include topologically significant stars and rings; on COMPUTERS, triangle structures are predominant.Figure 6 colors atoms by type; Figure 8 shows the COMPUTERS patterns.Source: §4.5 · p. 9, Figure 6 · p. 9

5. Conclusion

GPM learns graph substructure patterns directly without message passing, and experiments report robustness, scalability, and interpretability across graph tasks.

5. Conclusion

  • GPM’s prediction performance depends heavily on sampled-pattern quality, and random sampling may increase training and hyperparameter-tuning resource use.The paper identifies adaptive task-specific sampling or a unified pattern vocabulary as possible ways to mitigate this issue.Source: §5 · p. 9
  • GPM is currently limited to supervised tasks; proposed extensions include unsupervised learning, LLM integration, external knowledge, and complex graph types such as heterogeneous graphs.Source: §5 · p. 9

Impact Statement

The paper presents GPM as a way to address message-passing limitations and support interpretation of graph topology.

Impact Statement

  • GPM is intended to support topology-sensitive applications such as social network analysis and drug discovery, while misuse in surveillance or profiling and reinforcement of training-data biases are ethical concerns.Source: Impact Statement · p. 10

A. Limitations of Message Passing and Recent Advances

The discussion contrasts message-passing GNNs with expressive variants, random-walk methods, and graph transformers, noting their respective limits and trade-offs.

A. Limitations of Message Passing and Recent Advances

B.1. Environments

  • Experiments used Linux servers with four Nvidia A40 GPUs and PyTorch 2.4.0, PyTorch Geometric 2.6.1, PyTorch Cluster 1.6.3, CUDA 12.1, and Python 3.9.Source: §B.1 · p. 14

B.2. Training Details

  • Training used AdamW with weight decay, early stopping after 100 epochs, label smoothing of 0.05, gradient clipping at 1.0, and 100 warm-up steps by default.Experiments used five random seeds and a default batch size of 256.Source: §B.2 · p. 14

B.3. Model Configurations

  • The default model configuration uses hidden dimension 256, four attention heads, and one Transformer layer; hyperparameter searches cover learning rate, positional embedding dimension, dropout, weight decay, and λ.Pattern sampling defaults to p = 1, q = 1.Source: §B.3 · p. 15, Table 6 · p. 15

B.4. Architectures in Model Scaling Analysis

The appendix connects random-walk patterns to ego-graph structure, explains how GPM encodes semantic and topological information, and establishes a graph-distinguishing result under stated conditions.

B.4. Architectures in Model Scaling Analysis

  • Table 7 gives the model architectures and parameter counts used to compare GAT and GPM across model scales.The supplied passage identifies the table’s scope but does not provide its values.Source: §B.4 · p. 15, Table 7 · p. 15

C.1. Proof of Proposition 3.2

  • Anonymous-walk distributions can reconstruct a node’s k-hop ego-graph, so a set of l-length patterns can represent that neighborhood.The stated walk length is l = O(|E′|).Source: §C.1 · pp. 15–16

C.2. Proof of Proposition 3.3

  • GPM separately encodes semantic paths, which identify pattern nodes, and anonymous paths, which capture pattern structure, using bijective projections to preserve distinct paths.Both path representations are jointly required to encode a graph pattern comprehensively.Source: §C.2 · p. 16

C.3. Proof of Theorem 3.4

  • Under connected, unweighted, undirected graph assumptions and sufficient patterns, GPM can distinguish non-isomorphic graphs.The argument extends a simplified model using one sufficiently long walk, injective mappings, and a mean aggregator to GPM’s neural encoders and transformer; the result is stated up to the Reconstruction Conjecture.Source: §C.3 · pp. 16–17

C.4. Proof of Theorem 3.5

The appendix relates GPM’s pattern encodings to k-WL distinguishability and examines complexity, empirical expressiveness, long-range fitting, and distributed-training scope.

C.4. Proof of Theorem 3.5

  • If k-WL distinguishes two graphs, the simplified GPM can also distinguish them, but GPM may distinguish graphs that k-WL does not.This result is stated up to the Reconstruction Conjecture and under connected, unweighted, undirected graph assumptions with sufficiently many sampled patterns.Source: §C.4 · p. 17

D. Complexity

  • GPM’s node-level complexity is O(n · k2), compared with O(n2) for existing graph transformers; for graph classification, the respective complexities are O(m · k2) and O(m · n2).The passage states k2 ≪ n for node classification.Source: D. Complexity · p. 17

E.1. Empirical Effectiveness

  • GPM distinguishes all graphs in the CSL, EXP, and SR25 benchmarks, including SR25 graphs indistinguishable by the 3-WL test.The prose reports that many existing models fail on these tasks; Table 8 summarizes the results.Source: §E.1 · p. 18, Table 8 · p. 18

E.2. Tackling Over-Squashing

  • On TREENEIGHBORSMATCHING, GPM achieves perfect training accuracy at every radius, while message-passing GNNs and RUM fail to fit examples from r = 4.The reported accuracy is training accuracy; the proposed mechanism is direct learning of long-range patterns sampled by random walks.Source: §E.2 · pp. 18–19, Figure 7 · p. 18

F.1. Additional Discussion on Distribution Training

  • The distributed-training experiments use one machine with four Nvidia A40 GPUs, so they do not establish acceleration in multi-machine settings.The discussion nevertheless states advantages over message-passing GNNs particularly for scenarios with many devices.Source: §F.1 · p. 19

F.2. Model Component Ablation

The ablations examine topological inputs and semantic-path encoders, while the learning-strategy discussion considers pattern scales and test-time pattern counts.

F.2. Model Component Ablation

  • Adding positional embeddings and anonymous paths improves performance, with anonymous paths having a more pronounced effect than positional embeddings.Removing both components significantly reduces performance; Table 9 contains the full ablation results.Source: §F.2 · pp. 19–20, Table 9 · p. 19
  • The Transformer semantic-path encoder performs best on 11 of 14 datasets; GRU outperforms Mean on heterophilous graphs such as Deezer, Blog, and Flickr-S.The passage attributes the Transformer result to its ability to model localized and long-range dependencies, and suggests GRU’s recurrent structure as a reason for its heterophilous-graph result.Source: §F.2 · p. 20

F.3. Additional Discussion on Learning Strategies

  • Multi-scale training generally improves performance, except on the heterophilous Blog, Flickr, and Flickr-S datasets.The passage suggests smaller patterns may overemphasize localized structure on these graphs; Table 10 presents the comparisons.Source: §F.3 · p. 20, Table 10 · p. 20
  • Using 128 patterns for training and inference improves performance over 16 for both, but incurs substantial computational overhead; the default uses 16 for training and 128 for inference.The mixed-count variant sometimes outperforms using 128 patterns in both phases, possibly because fewer training patterns reduce overfitting; Tables 11 and 12 cover the comparisons and training time.Source: §F.3 · p. 20, Table 11 · p. 20, Table 12 · p. 21

G. GPM Automatically Learns Data Dependencies

Graph tasks can involve both localized and long-range dependencies, and GPM uses transformer-based pattern selection to learn which patterns matter for each task.

G. GPM Automatically Learns Data Dependencies

  • Rumor-spreader detection is an example of a task requiring long-range information because the origin may be disconnected from many affected nodes.The passage describes rumor information flowing through multiple intermediaries.Source: G. GPM Automatically Learns Data… · p. 21
  • GPM’s transformer identifies task-relevant localized or long-range patterns, reducing the need to tune hyperparameters for different dependency types.The passage also states that this capability enhances overall performance.Source: G. GPM Automatically Learns Data… · p. 21
  • On PRODUCTS, unbiased random walks that sample both localized and long-range patterns achieve the best performance among the tested sampling settings.The compared biased settings sample localized or long-range patterns; Figure 5 presents training loss and testing accuracy.Source: G. GPM Automatically Learns Data… · p. 21
  • The paper attributes localized-pattern underperformance to duplicated samples, while long-range patterns are less redundant but noisier; it hypothesizes unbiased sampling balances these effects.The passage reports that long-range patterns can outperform localized patterns even on graphs with high homophily ratios, but their noise still prevents optimal performance.Source: G. GPM Automatically Learns Data… · p. 21

H. Model Interpretation on COMPUTERS

Figure 8 presents the top 10 important patterns associated with certain nodes.

H. Model Interpretation on COMPUTERS

  • Figure 8 presents the top 10 important patterns associated with certain nodes.The caption does not identify the patterns or nodes.Source: Figure 8 · p. 22
Loading 2501.18739v2…