# PatchGT: Transformer over Non-trainable Clusters for Learning Graph Representations

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 44 references that are in the map.
- First posted on arXiv 26 Nov 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Graph Transformer Networks](https://mlsanity.com/paper/1911.06455/) (2019)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Patches Are All You Need?](https://mlsanity.com/paper/2201.09792/) (2022)
- [Representing Long-Range Context for Graph Neural Networks with Global Attention](https://mlsanity.com/paper/2201.08821/) (2022)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [AMMUS : A Survey of Transformer-based Pretrained Models in Natural Language Processing](https://mlsanity.com/paper/2108.05542/) (2021)
- [Accurate Learning of Graph Representations with Graph Multiset Pooling](https://mlsanity.com/paper/2102.11533/) (2021)
- [Dive into Deep Learning](https://mlsanity.com/paper/2106.11342/) (2021)
- [Graph Convolutional Networks with EigenPooling](https://mlsanity.com/paper/1904.13107/) (2019)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Memory-Based Graph Networks](https://mlsanity.com/paper/2002.09518/) (2020)
- [Universal Graph Transformer Self-Attention Networks](https://mlsanity.com/paper/1909.11855/) (2019)

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

- [Graph Transformers: A Survey](https://mlsanity.com/paper/2407.09777/) (2024)
- [Efficient Large-Scale Traffic Forecasting with Transformers: A Spatial Data Management Perspective](https://mlsanity.com/paper/2412.09972/) (2024)
- [Enhancing Graph Transformers with Hierarchical Distance Structural Encoding](https://mlsanity.com/paper/2308.11129/) (2023)
- [AGFormer: Efficient Graph Representation with Anchor-Graph Transformer](https://mlsanity.com/paper/2305.07521/) (2023)
- [Are Graph Transformers Necessary? Efficient Long-Range Message Passing with Fractal Nodes in MPNNs](https://mlsanity.com/paper/2511.13010/) (2025)
- [URLOST: Unsupervised Representation Learning without Stationarity or Topology](https://mlsanity.com/paper/2310.04496/) (2023)
- [Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Lehman Go Indifferent](https://mlsanity.com/paper/2311.01205/) (2023)
- [Neighbour-level Message Interaction Encoding for Improved Representation Learning on Graphs](https://mlsanity.com/paper/2404.09809/) (2024)

## Abstract (arXiv)

Recently the Transformer structure has shown good performances in graph learning tasks. However, these Transformer models directly work on graph nodes and may have difficulties learning high-level information. Inspired by the vision transformer, which applies to image patches, we propose a new Transformer-based graph neural network: Patch Graph Transformer (PatchGT). Unlike previous transformer-based models for learning graph representations, PatchGT learns from non-trainable graph patches, not from nodes directly. It can help save computation and improve the model performance. The key idea is to segment a graph into patches based on spectral clustering without any trainable parameters, with which the model can first use GNN layers to learn patch-level representations and then use Transformer to obtain graph-level representations. The architecture leverages the spectral information of graphs and combines the strengths of GNNs and Transformers. Further, we show the limitations of previous hierarchical trainable clusters theoretically and empirically. We also prove the proposed non-trainable spectral clustering method is permutation invariant and can help address the information bottlenecks in the graph. PatchGT achieves higher expressiveness than 1-WL-type GNNs, and the empirical study shows that PatchGT achieves competitive performances on benchmark datasets and provides interpretability to its predictions. The implementation of our algorithm is released at our Github repo: https://github.com/tufts-ml/PatchGT.