# Beyond Message Passing: Neural Graph Pattern Machine

arXiv: https://arxiv.org/abs/2501.18739 · HTML: https://mlsanity.com/paper/2501.18739/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 80 of its 103 references that are in the map.
- First posted on arXiv 30 Jan 2025.

## Builds on (most cited first, 30 of 80)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Domain-Adversarial Training of Neural Networks](https://mlsanity.com/paper/1505.07818/) (2015)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [CrossViT: Cross-Attention Multi-Scale Vision Transformer for Image Classification](https://mlsanity.com/paper/2103.14899/) (2021)
- [Florence: A New Foundation Model for Computer Vision](https://mlsanity.com/paper/2111.11432/) (2021)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)

## Built on by (most cited first, 17 of 17)

- [Graph is a Substrate Across Data Modalities](https://mlsanity.com/paper/2601.22384/) (2026)
- [Controllable Graph Generation with Diffusion Models via Inference-Time Tree Search Guidance](https://mlsanity.com/paper/2510.10402/) (2025)
- [Semantic Refinement with LLMs for Graph Representations](https://mlsanity.com/paper/2512.21106/) (2025)
- [Molecular Representations in Implicit Functional Space via Hyper-Networks](https://mlsanity.com/paper/2601.22327/) (2026)
- [W2T: LoRA Weights Already Know What They Can Do](https://mlsanity.com/paper/2603.15990/) (2026)
- [Temporal Graph Pattern Machine](https://mlsanity.com/paper/2601.22454/) (2026)
- [Policy4OOD: A Knowledge-Guided World Model for Policy Intervention Simulation against the Opioid Overdose Crisis](https://mlsanity.com/paper/2602.12373/) (2026)
- [Learning Graph Foundation Models on Riemannian Graph-of-Graphs](https://mlsanity.com/paper/2605.09993/) (2026)
- [Consistency Deep Equilibrium Models](https://mlsanity.com/paper/2602.03024/) (2026)
- [BHyGNN+: Unsupervised Representation Learning for Heterophilic Hypergraphs](https://mlsanity.com/paper/2602.14919/) (2026)
- [Generalizing GNNs with Tokenized Mixture of Experts](https://mlsanity.com/paper/2602.09258/) (2026)
- [OPBench: A Graph Benchmark to Combat the Opioid Crisis](https://mlsanity.com/paper/2602.14602/) (2026)
- [GRAVITY: A Controversial Graph Representation Learning for Vertex Classification](https://mlsanity.com/paper/2508.08954/) (2025)
- [Enhancing Graph Representations with Neighborhood-Contextualized Message-Passing](https://mlsanity.com/paper/2511.11046/) (2025)
- [On the Safety of Graph Representation Learning](https://mlsanity.com/paper/2605.06576/) (2026)
- [Hypergraph Pattern Machine: Compositional Tokenization for Higher-Order Interactions](https://mlsanity.com/paper/2605.16527/) (2026)
- [SupraBench: A Benchmark for Supramolecular Chemistry](https://mlsanity.com/paper/2606.13477/) (2026)

## Abstract (arXiv)

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.