Beyond Message Passing: Neural Graph Pattern Machine

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

REVIEW 4 major objections 5 minor 1 cited by

Beyond Message Passing: Neural Graph Pattern Machine

T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read A graph learning model that replaces message passing with random-walk pattern sampling and transformer-based pattern selection can distinguish graphs that stump 3-WL tests, capture long-range dependencies without over-squashing, and…

desk verdict Strong, broad empirical package for pattern-based graph learning; the universal expressiveness proof has an acknowledged gap that should stop the overclaim. read the letter →

arxiv 2501.18739 v2 pith:ACOIXPA7 submitted 2025-01-30 cs.LG cs.AIcs.SI

Zehong Wang , Zheyuan Zhang , Tianyi Ma , Nitesh V Chawla , Chuxu Zhang , Yanfang Ye This is my paper · ORCID

classification cs.LGcs.AIcs.SI

keywords graphpatternlearningmessagepassinganonymouswalksrandomwalksamplingtransformersexpressivenessWeisfeiler-Lemantestlong-rangedependencies

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that the standard message-passing paradigm for graph neural networks is a bottleneck: it cannot directly capture repeated substructures like triangles, rings, or cliques, and it loses information when dependencies are long-range. To get around this, the authors propose the Neural Graph Pattern Machine (GPM), a model that never passes messages. Instead, it samples random walks from each node, edge, or graph, encodes each walk twice — once for its node attributes (the semantic path) and once for its bare topology (the anonymous path) — and feeds the resulting pattern embeddings into a transformer that picks out the patterns most relevant to the prediction task. The paper claims that this design distinguishes graphs that the Weisfeiler-Leman hierarchy cannot distinguish, handles long-range dependencies without over-squashing, and beats state-of-the-art baselines on node, link, and graph-level benchmarks. If true, pattern-based non-message-passing models would be a viable general-purpose replacement for GNNs rather than a niche alternative.

What carries the argument

The key machinery is the pattern tokenizer built on random walks. A walk of length $L$ is split into a semantic path (the sequence of node and edge features along the walk) and an anonymous path (the sequence of integers marking when each node is first visited, e.g., $0$-$1$-$2$-$0$-$3$ for a triangle with an extra appendage). The anonymous path is turned into loop-based adjacency vectors — a $k$-dimensional indicator vector per position recording which earlier positions it revisits — and encoded separately from the semantic path by sequential models, giving a pattern embedding $p = \rho_s(w) + \lambda\,\rho_a(\phi)$. A transformer then treats the sampled pattern embeddings as tokens and learns which patterns dominate the downstream task, optionally using a class token for interpretability. This replaces neighborhood aggregation with pattern selection.

What would settle it

Run GPM on two non-isomorphic graphs that have identical distributions of anonymous walks of every length GPM samples (the multi-scale lengths 2, 4, 6, 8); if GPM produces the same embedding for both, the universal-expressiveness claim collapses. A practical proxy: if any pair from the SR25 set becomes tangled under different sampling seeds, the theorem's empirical support is put in doubt.

Watch

Extended reading notes

Core claim

The central discovery is that a graph pattern can be represented as the joint encoding of a semantic path and an anonymous path obtained from a random walk, and that this representation captures enough structure to support learning without any message passing. The paper proves (under the reconstruction conjecture and a simplified-model reduction) that GPM can distinguish any pair of non-isomorphic connected, unweighted, undirected graphs given enough sampled patterns, and that GPM with walk length k can distinguish graphs that the k-WL test cannot. Empirically, the authors demonstrate that GPM achieves perfect accuracy on CSL, EXP, and SR25 datasets — sets containing graphs that are indistinguishable by 1-WL, 2-WL, and 3-WL tests respectively — and that it fits the Tree Neighbors Matching task perfectly up to radius 7, where message-passing models fail by radius 4. Across node classification, link prediction, graph classification, and graph regression benchmarks, GPM reports the best accuracy among the compared models, including graph transformers and random-walk-based GNNs.

Load-bearing premise

The proof that GPM can distinguish every pair of non-isomorphic graphs depends on a famous unsolved conjecture about graphs being determined by their smaller pieces, and on the assumption that encoding short walk segments separately preserves the power of encoding whole walks.

Editorial extensions

If this is right

GPM distinguishes all graphs in the CSL, EXP, and SR25 benchmarks, including strongly regular graphs that elude the 3-WL test, so pattern-based models can exceed the expressiveness of message-passing GNNs and higher-order GNNs.
GPM matches the Tree Neighbors Matching task perfectly to radius 7, showing the architecture does not suffer from over-squashing and can capture dependencies that message-passing models lose.
GPM reports state-of-the-art accuracy on node classification (e.g., 82.62 on Products, 72.89 on Arxiv), link prediction (Hits@20 of 92.85 on Cora), and graph classification/regression (MAE 0.064 on ZINC), outperforming graph transformers and random-walk GNNs on the same splits.
GPM scales to large graphs (2.4M-node Products), larger model sizes (up to ~100M parameters), and distributed training with better scaling than message-passing GNNs, because each instance is represented by a small set of k=128 patterns rather than by the full adjacency structure.
The class-token attention weights make the dominant patterns inspectable, giving a direct view of the substructures (e.g., benzene rings, triangles) that drive predictions.

Reading between the lines

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

If pattern-based tokenization proves robust across tasks, one could extend GPM to a general-purpose graph tokenizer for foundation models, where pre-sampled pattern vocabularies replace task-specific heuristics; the paper hints at this but does not develop it.
The theoretical dependence on the reconstruction conjecture suggests that testing GPM on the small known candidates for reconstruction-counterexample graphs (if any exist) would directly probe the universality claim, rather than relying only on the SR25 benchmark.
Because anonymous paths encode topological structure independently of node identities, GPM's pattern embeddings might transfer across different graphs with shared motifs — this could explain the reported OOD gains on ACM→DBLP and Twitch, but the paper does not isolate the mechanism.
A natural stress test is to replace the random-walk sampler with a motif-aware sampler (e.g., biased toward triangles or cycles) and see whether the transformer identifier can still learn to down-weight irrelevant patterns; the paper reports biased-walk experiments only on Products.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The one thing to know: the empirical core is real and worth engaging with, but the theoretical framing oversells what is proven. GPM does something genuinely useful—it samples random walks, encodes semantic and anonymous paths separately, and lets a transformer pick the task-relevant patterns. That combination, with multi-scale sampling and test-time augmentation, is new relative to RUM and the other baselines. The paper also ships code and runs a wide, credible evaluation: node, link, graph classification, graph regression, OOD, scalability, and interpretability, with error bars and ablations. Credit where due: the authors are honest about components and include a code link. That alone makes this a serious empirical contribution to the non-message-passing line of work.

The soft spot is the expressiveness theorem, and it is load-bearing because the abstract and Section 3.5 use it to claim GPM surpasses message passing universally. Theorem 3.4 rests on the reconstruction conjecture—that is fine as a conditional claim—but the proof only establishes the result for a simplified variant: one long walk, injective encoders, mean pooling. The generalization to the actual model is argued in Appendix C.3, where the authors explicitly say they do not mean to suggest long walks can be fully reconstructed from shorter segments and call it an 'approximate strategy.' That is an honest admission, but it means the universal guarantee does not transfer to the architecture being evaluated. The CSL/EXP/SR25 results are credible measurements on the full model and they stand on their own, but they are finite benchmarks, not a proof. Corollary 3.5 inherits the same gap. So the right fix is to soften the claim: present the universal expressiveness result as conditional and provisional, and make the approximate step prominent rather than buried in an appendix.

Two smaller issues. The abstract says GPM outperforms state-of-the-art baselines, but Table 1 shows NAGphormer slightly ahead on CoraFull; the text admits this, so the abstract should be qualified. Also, the Twitch OOD column in Table 4 has no error bars, unlike the rest of the table. Minor, but easy to clean up.

Who is this for? Anyone working on graph transformers, random-walk graph learning, or models that claim to bypass message passing. It is a useful benchmark-heavy paper even if the theory is weaker than advertised. If this landed on my desk, I would send it to peer review rather than desk reject—the empirical work deserves referee time—and I would ask for the theory framing to be corrected and the OOD numbers completed before acceptance.

Referee Report

4 major / 5 minor

Summary. The paper proposes the Neural Graph Pattern Machine (GPM), a graph representation learning framework that abandons message passing entirely. GPM tokenizes each node, edge, or graph into a set of random-walk patterns, encodes each pattern by separately encoding its semantic path (node/edge features) and its anonymous path (topological structure), and then uses a transformer to identify the most task-relevant patterns. The authors argue that this design yields higher expressiveness than message passing (Theorem 3.4, Corollary 3.5), better long-range dependency modeling, and state-of-the-art empirical performance across node classification, link prediction, graph classification, and graph regression, plus OOD generalization, scalability, and interpretability. The paper includes ablations, complexity analysis, and releases code.

Significance. If the theoretical claims were fully established, GPM would be a significant contribution to the growing line of non-message-passing graph models: it offers a unified tokenizer for node/link/graph tasks, a message-passing-free pattern encoder, and a scalable transformer-based pattern selector. The empirical study is a strength: it covers many datasets and tasks, reports standard deviations, includes ablations of the main components, provides honest discussion of component contributions, and releases code. The expressiveness experiments on CSL, EXP, and SR25 are meaningful measurements. However, the paper's central theoretical guarantee currently rests on two gaps: the proof that the simplified model extends to the full architecture is explicitly acknowledged as approximate, and the proof relies on assumptions about injectivity of neural encoders that are not met by the implemented model. These gaps are load-bearing because the abstract and Section 3.5 use the universal expressiveness claim as the main justification for going beyond message passing.

major comments (4)

[Appendix C.3 and Section 3.5] Theorem 3.4's proof does not bridge the simplified variant to the full GPM model. The simplification uses n=1, a single sufficiently long walk, injective encoders, and mean aggregation; the generalization to many shorter walks, learned encoders, and transformer pooling is argued by splitting a long walk into segments. The authors themselves write that this is an 'approximate strategy' and that 'anonymous walks cannot preserve node identity across segments,' so the set of short walks does not determine the original long walk. Therefore the proof establishes expressiveness only for a simplified, different model, not for the architecture actually evaluated. Since the abstract and Section 3.5 use the universal distinguishability claim as a central selling point, this gap must be repaired (or the claim must be downgraded to a conjecture with empirical support).
[Proposition 3.3 and Eq. (2)] Proposition 3.3 states that jointly encoding semantic and anonymous paths via any bijective mappings gives a comprehensive representation, but the actual pattern embedding in Eq. (2) is p = ρs(w) + λ·ρa(φ), a sum of two encoded vectors. Addition is not a bijective mapping from the pair (w, φ) to the embedding space; collisions are possible. The proof in Appendix C.2 argues from bijective projections, which do not apply to the implemented encoder. Moreover, ρs and ρa are learned GRU/transformer networks, which are not guaranteed to be injective. Thus the 'key insight' of Section 3.1 that the combined encoding matches a unique graph pattern is not justified for the architecture used.
[Appendix C.3, generalization step (2)] The proof states that 'neural networks are inherently universal and injective,' but this is incorrect as a general statement: standard neural architectures (GRUs, transformers with finite precision) are universal approximators but not injective, and many used in GPM (mean aggregation, GRU) are explicitly non-injective. This assumption is not stated in Theorem 3.4 or its hypotheses, and it is needed to transfer the simplified-model result to the full model. Without injectivity, the argument that distinct walks yield distinct embeddings fails, so the theorem's conclusion is not established for the actual model.
[Corollary 3.5 and Appendix C.4] Corollary 3.5 is stated for 'walk length k' and claims distinguishability beyond k-WL, but the implemented GPM uses multiple walk lengths (default [2,4,6,8]) and a variable number of patterns m during training and k during inference. The proof in Appendix C.4 reuses the same approximate reduction from Appendix C.3, so the corollary inherits the gap described above. The statement also does not specify how 'walk length k' relates to the multi-scale sampling used in the experiments, making the formal claim hard to interpret with respect to the actual architecture.

minor comments (5)

[Appendix C.4] The appendix heading reads 'Proof of Theorem 3.5' but the theorem is numbered Corollary 3.5; the numbering should be aligned.
[Appendix C.3] The sentence 'We did not mean to suggest that long walks can be fully reconstructed from shorter ones...' is written in a conversational, self-referential style that is out of place in a proof appendix; it should be replaced by a formal statement of what is and is not proven.
[Appendix F.1] The phrase 'distribution training' in the heading appears to be a typo for 'distributed training,' and 'tranformer' in the same section is misspelled.
[Table 8] The CSL, EXP, and SR25 accuracies are reported without standard deviations, unlike the other tables; adding deviations (or stating they are single runs) would improve consistency.
[Section 4.1] The claim that GPM 'outperforms state-of-the-art baselines' is too broad: on CoraFull, NAGphormer is slightly better, and for several graph-level datasets the gap to some baselines (e.g., RUM on IMDB-B) is within one standard deviation. The conclusion would be more precise if such exceptions were acknowledged in the text.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: GPM's expressiveness theorem is inherited from external work (Wang & Cho 2024) plus the reconstruction conjecture, and the acknowledged approximate-transfer step in Appendix C.3 is a proof gap rather than a reduction to the paper's own fitting inputs.

full rationale

The paper's central claim that GPM surpasses message passing rests on Theorem 3.4, whose proof is delegated to Theorem 4 of Wang & Cho (2024) and Theorem C.1 of Micali & Zhu (2016), with the reconstruction conjecture stated explicitly as an assumption. These are external results, not self-citations, and the stated assumptions do not include the conclusion that GPM is optimal; the theorem is conditional on an open conjecture. The generalization from the simplified variant (n=1, injective encoders, mean pooling) to the full model (n>1, neural encoders, transformer pooling) is not circular by the paper's own admission: Appendix C.3 says that long walks are segmented into sub-walks only as an 'approximate strategy' because 'anonymous walks cannot preserve node identity across segments.' That is an acknowledged proof gap, which weakens the universality claim, but it is not a fitted parameter renamed as a prediction and not a result defined into existence. The only near-tautological element is Proposition 3.3, where jointly encoding semantic and anonymous paths via bijective mappings is lossless by the definition of bijectivity; this step is explanatory rather than load-bearing for the main theorem. Empirical evaluations compare GPM against published baselines on standard datasets, and the expressiveness measurements on CSL, EXP, and SR25 are direct accuracy measurements, not quantities manufactured by GPM's own equations. Self-citations appear in related-work, motivation, and future-work contexts and do not carry the proof. No load-bearing reduction to the paper's inputs is exhibited.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard model hyperparameters and on external theorems (Micali-Zhu, RUM) plus the unproved reconstruction conjecture. No new physical or ontological entities are introduced. The main epistemic debt is the conditional nature of the expressiveness theorem and the approximate reduction from the simplified variant to the full model.

free parameters (5)

lambda (semantic-anonymous path weighting) = 0.1 to 1.0, dataset-specific (Table 6)
Controls the balance between semantic path and anonymous path embeddings in Equation 2; tuned per dataset and affects final accuracy.
m (training patterns per instance) = 16 (default)
Number of random walk patterns sampled during training; ablation shows #Train=16 vs 128 changes accuracy by several points.
k (inference patterns per instance) = 128 (default)
Number of patterns used at inference under test-time augmentation; large k adds compute but improves accuracy.
multi-scale walk lengths = [2, 4, 6, 8] (default)
Pattern lengths sampled at multiple scales; ablation shows multi-scale training improves accuracy on most datasets.
positional embedding type and dimension = Lap or RW, dim 4-20 per dataset (Table 6)
Optional PE concatenated to node features; choice depends on dataset, e.g., Lap for node tasks, RW for graph tasks.

assumptions (6)

domain assumption Graph reconstruction conjecture (the original graph is determined by its vertex-deleted subgraphs)
Invoked in the proof of Theorem 3.4 and Corollary 3.5 via Theorem 4 and Corollary 4.1 of Wang & Cho (2024); see Appendix C.3. The conjecture is unproved, so the expressiveness guarantees are conditional.
standard math Theorem 4 and Corollary 4.1 of Wang & Cho (2024) (random walk embeddings distinguish non-isomorphic graphs up to the reconstruction conjecture)
Used as the foundation of Theorem 3.4 and Corollary 3.5; the present paper adds a reduction from its simplified variant to the full GPM.
standard math Theorem 1 of Micali & Zhu (2016) (anonymous walk distributions reconstruct ego-graphs)
Used in Proposition 3.2 proof (Appendix C.1) to justify that anonymous walk patterns capture local topology.
domain assumption Assumption C.2: graphs are connected, unweighted, and undirected
Restricts the expressiveness theorem to this graph class; real datasets often violate these conditions.
domain assumption Assumption C.3: sufficiently large walk length
The expressiveness guarantee requires sufficiently long or sufficiently many walks; the implemented model uses finite lengths [2,4,6,8] and at most 128 patterns.
ad hoc to paper Neural encoders are universal and injective (used in the proof reduction)
In Appendix C.3 the proof replaces neural networks with universal injective maps and asserts neural networks satisfy this; with finite training data this is not guaranteed in practice.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Beyond Message Passing: Neural Graph Pattern Machine." pith.science (2026). https://pith.science/paper/ACOIXPA7

@misc{pith2026250118739,
  author       = {Pith},
  title        = {Pith review of: Beyond Message Passing: Neural Graph Pattern Machine},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ACOIXPA7}},
  note         = {Machine review of arXiv:2501.18739}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2501.18739 by the authors.

**Figure 1.** The workflow of Neural Graph Pattern Machine (GPM). Given a graph dataset, GPM utilizes a random walk tokenizer to extract a set of patterns representing the learning instances (nodes, edges, or graphs). These patterns are first encoded by a sequential model and then processed by a transformer encoder, which identifies the dominant patterns relevant to downstream tasks. computational cost, and biased inductive assum… view at source ↗

**Figure 2.** The overview framework of GPM. et 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 (Tonshoff ¨ 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, l… view at source ↗

**Figure 3.** Examples of anonymous paths. graph matching (Sun et al., 2012), and then use this vocabulary 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 r… view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: Model scalability analysis. (Top) Number of Parameters vs. Accuracy. (Bottom) Number of GPUs vs. Acceleration Ratio. smoothing effect. The architectural details of large-scale GPM models are presented in [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 6.** Figure 6: Model interpretation on ZINC. 4.5. Model Interpretation 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, [PITH_FULL_IMAGE:figures/full_fig_…

**Figure 5.** 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 [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

**Figure 7.** Figure 7: Over-squashing analysis. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

**Figure 8.** Figure 8: The top-10 important patterns associated to the certain nodes. 22 [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Consistency Deep Equilibrium Models
cs.LG 2026-02 conditional novelty 6.0 of 10

C-DEQ trains a consistency model to map intermediate solver states directly to the DEQ equilibrium, enabling accurate one-to-few-step inference for deep equilibrium models.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages · cited by 1 Pith paper

[1]

(3) Using a mean aggregator over encoded patterns instead of a transformer

(2) Replacing neural networks with universal and injective mappings ρs and ρa. (3) Using a mean aggregator over encoded patterns instead of a 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 undire...

work page 2024
[4]

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

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

work page 2021
[6]

This represents a fundamental advantage over message passing GNNs in terms of expressiveness

demonstrate that, under mild assumptions, graph transformers surpass the expressive power of WL isomorphism tests. This represents a 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 smalle...

work page 2023
[7]

Model architectures in model scaling analysis. Architectures of GNN (GAT in this case) # GNN Layers 2 2 2 3 3 # Number of Heads 8 24 32 48 112 # Hidden Dimension 512 1536 2048 3072 7168 ARXIV 0.35M 2.63M 4.56M 19.44M 104.07M PRODUCTS 0.34M 2.6M 4.52M 19.37M 103.92M Architectures of GPM # Transformer Layers 1 1 3 3 3 # Number of Heads 4 4 4 8 16 # Hidden D...

work page 2016
[8]

21 Beyond Message Passing: Neural Graph Pattern Machine 1003 31136335 3704 7077 7131 1003 3113 3704 6335 6762 7131 13157 2026 1003 3113 6762 3704 8392 3322 6766 13721 13358 1003 6762 3113 3704 6335 7131 8568 5895 1003 6762 6335 3113 13331 6670 1003 6335 3113 6762 3704 1430 1003 3704 3113 6335 6762 1003 3113 3704 71313030 6223 1003 3113 6762 3704 7454 1120...

work page 2026
[10]

Each GPU processes a single partition, and peer-to-peer communication is used to exchange learned node embeddings among GPUs

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

work page 2019
[11]

Impact of test-time augmentation. PRODUCTS COMPUTER ARXIV WIKICS C ORAFULL DEEZER BLOG Task Node Node Node Node Node Node Node # Train=16 # Infer=12882.62 ± 0.3992.28 ± 0.39 72.89 ± 0.68 80.19 ± 0.41 71.23 ± 0.51 67.26 ± 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 # Tra...

work page 1989
[12]

Training time (second per epoch) and acceleration of using less patterns. PRODUCTS COMPUTER ARXIV WIKICS F LICKR # 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 ×15.30 ×15.70 ×14.00 ×11.50 ×15.05 G. GPM Automatically Learns Data Dependencies Graph datasets often exhibit a mixture of localized and...

work page 1973

Show all 13 references

[2018]

Given our focus on learning graph patterns, this discussion emphasizes the issues of expressiveness and notable advancements

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

2019
[2021]

Limitations of Message Passing and Recent Advances The message passing paradigm (Kipf & Welling, 2017; Hamilton et al., 2017; Veliˇckovi´c et al.,

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ˇckovi´c et al.,

2017
[2022]

Leveraging a global attention mechanism, GTs can capture correlations between any pair of nodes, enabling effective modeling of long-range dependencies

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 (Kreuze...

2021
[2023]

Llm-empowered class imbalanced graph prompt learning for online drug trafficking detection

Ma, T., Qian, Y ., Wang, Z., Zhang, Z., Zhang, C., and Ye, Y . Llm-empowered class imbalanced graph prompt learning for online drug trafficking detection. arXiv, 2025a. Ma, T., Qian, Y ., Zhang, S., Zhang, C., and Ye, Y . Adap- tive expansion for hypergraph learning. arXiv pre...

arXiv
[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 mo...

2023

Pith tools

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

[1] [1]

(3) Using a mean aggregator over encoded patterns instead of a transformer

(2) Replacing neural networks with universal and injective mappings ρs and ρa. (3) Using a mean aggregator over encoded patterns instead of a 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 undire...

work page 2024

[2] [4]

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

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

work page 2021

[3] [6]

This represents a fundamental advantage over message passing GNNs in terms of expressiveness

demonstrate that, under mild assumptions, graph transformers surpass the expressive power of WL isomorphism tests. This represents a 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 smalle...

work page 2023

[4] [7]

Model architectures in model scaling analysis. Architectures of GNN (GAT in this case) # GNN Layers 2 2 2 3 3 # Number of Heads 8 24 32 48 112 # Hidden Dimension 512 1536 2048 3072 7168 ARXIV 0.35M 2.63M 4.56M 19.44M 104.07M PRODUCTS 0.34M 2.6M 4.52M 19.37M 103.92M Architectures of GPM # Transformer Layers 1 1 3 3 3 # Number of Heads 4 4 4 8 16 # Hidden D...

work page 2016

[5] [8]

21 Beyond Message Passing: Neural Graph Pattern Machine 1003 31136335 3704 7077 7131 1003 3113 3704 6335 6762 7131 13157 2026 1003 3113 6762 3704 8392 3322 6766 13721 13358 1003 6762 3113 3704 6335 7131 8568 5895 1003 6762 6335 3113 13331 6670 1003 6335 3113 6762 3704 1430 1003 3704 3113 6335 6762 1003 3113 3704 71313030 6223 1003 3113 6762 3704 7454 1120...

work page 2026

[6] [10]

Each GPU processes a single partition, and peer-to-peer communication is used to exchange learned node embeddings among GPUs

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

work page 2019

[7] [11]

Impact of test-time augmentation. PRODUCTS COMPUTER ARXIV WIKICS C ORAFULL DEEZER BLOG Task Node Node Node Node Node Node Node # Train=16 # Infer=12882.62 ± 0.3992.28 ± 0.39 72.89 ± 0.68 80.19 ± 0.41 71.23 ± 0.51 67.26 ± 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 # Tra...

work page 1989

[8] [12]

Training time (second per epoch) and acceleration of using less patterns. PRODUCTS COMPUTER ARXIV WIKICS F LICKR # 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 ×15.30 ×15.70 ×14.00 ×11.50 ×15.05 G. GPM Automatically Learns Data Dependencies Graph datasets often exhibit a mixture of localized and...

work page 1973