Cluster Attention for Graph Machine Learning

Oleg Platonov; Liudmila Prokhorenkova

cs.LGApr 8, 2026

Cluster Attention for Graph Machine Learning

Authors: Oleg Platonov, Liudmila Prokhorenkova

Organizations: HSE University, Yandex Research · Yandex Research

Abstract

Message Passing Neural Networks have recently become the most popular approach to graph machine learning tasks; however, their receptive field is limited by the number of message passing layers. To increase the receptive field, Graph Transformers with global attention have been proposed; however, global attention does not take into account the graph topology and thus lacks graph-structure-based inductive biases, which are typically very important for graph machine learning tasks. In this work, we propose an alternative approach: cluster attention (CLATT). We divide graph nodes into clusters with off-the-shelf graph community detection algorithms and let each node attend to all other nodes in each cluster. CLATT provides large receptive fields while still having strong graph-structure-based inductive biases. We show that augmenting Message Passing Neural Networks or Graph Transformers with CLATT significantly improves their performance on a wide range of graph datasets including datasets from the recently introduced GraphLand benchmark representing real-world applications of graph machine learning.

Figures & tables

Panel of Figure 1 — Figure 1: Receptive fields of a single layer of different GML models. The blue node can interact with the red nodes. In an MPNN, the receptive field is based on the graph structure, but only neighboring nodes can interact with each other. GGT allows all nodes to interact with each other, but completely disregards the graph structure. CLATT allows nodes within the same cluster to interact, which provides longer-range interactions than in an MPNN, but still relies on the graph structure to disallow most possible pairwise interactions.

Figure 2: Similarities of clusterings produced by different node clustering algorithms on 4 different datasets: lastfm-asia , facebook , questions , amazon-ratings-5core . The Correlation Coefficient similarity measure is reported. LA is Leiden algorithm, BPP is Bayesian planted partition model, H1 is hierarchical statistical clustering (with the hierarchy level with the smallest non-trivial number of clusters being used), KM is k-means clustering of ResMLP node representations.

	node regression			node classification
	city-roads-M	city-roads-L	avazu-ctr	tolokers-2	city-reviews	hm-categories	pokec-regions	questions	lastfm-asia	facebook	amzn-r-5core	amzn-r-full
# nodes	$57.1$ K	$142.3$ K	$76.3$ K	$11.8$ K	$148.8$ K	$46.5$ K	$1.6$ M	$48.9$ K	$7.6$ K	$22.5$ K	$24.5$ K	$334.9$ K
# edges	$107.1$ K	$231.6$ K	$11.0$ M	$519.0$ K	$1.2$ M	$10.7$ M	$22.3$ M	$153.5$ K	$27.8$ K	$170.8$ K	$93.1$ K	$925.8$ K
avg degree	$3.75$	$3.26$	$288.04$	$88.28$	$15.66$	$460.92$	$27.32$	$6.28$	$7.29$	$15.20$	$7.60$	$5.53$
median degree	$4$	$3$	$71$	$30$	$4$	$45$	$13$	$1$	$4$	$7$	$5$	$4$
avg distance	$126.75$	$194.05$	$3.55$	$2.79$	$4.91$	$2.45$	$4.68$	$4.29$	$5.23$	$4.97$	$16.24$	$11.95$

Table 1: Characteristics of the considered graph datasets.

Table 2: Experimental results.

R^{2}

is reported for regression datasets, Average Precision is reported for binary classification datasets, Accuracy is reported for multiclass classification datasets. TL means time limit exceeded (24 hours for a single model run). For each pair consisting of a base model and its version augmented with CLATT, we highlight the best of the two results with bold and additionally underline it if the difference between the two results is statistically significant.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Distributions of average attention distances for different types of attention. Note that the unweighted average pairwise distance is $5.23$ for lastfm-asia and $2.79$ for tolokers-2 .

quantile $\rightarrow$	$0.05$	$0.25$	$0.50$	$0.75$	$0.95$	$0.05$	$0.25$	$0.50$	$0.75$	$0.95$
	lastfm-asia					tolokers-2
LGT (local attention)	$0.39$	$0.62$	$0.79$	$0.90$	$0.97$	$0.59$	$0.91$	$0.97$	$0.99$	$1.00$
LGT-CLATT (local attention)	$0.38$	$0.60$	$0.78$	$0.89$	$0.96$	$0.56$	$0.91$	$0.98$	$0.99$	$1.00$
LGT-CLATT (cluster attention)	$1.35$	$1.99$	$2.56$	$3.50$	$5.23$	$1.23$	$1.73$	$1.99$	$2.32$	$3.14$
GGT-DW (global attention)	$4.13$	$4.71$	$5.16$	$5.67$	$6.61$	$2.23$	$2.49$	$2.71$	$2.93$	$3.35$
GGT-DW-CLATT (global attention)	$4.10$	$4.69$	$5.13$	$5.65$	$6.60$	$2.26$	$2.52$	$2.73$	$2.94$	$3.36$

Appendix

Table 3: Quantiles of distributions of average attention distances for different types of attention. Note that the unweighted average pairwise distance is

5.23

for lastfm-asia and

2.79

for tolokers-2 .

clustering algorithm $\rightarrow$	LA	BPP	H1
city-roads-M	✓	✓
city-roads-L	✓	✓
avazu-ctr	✓
tolokers-2		✓
city-reviews			✓
hm-categories	✓

Appendix

Table 4: Clustering algorithms selected for each of the considered datasets. LA is Leiden algorithm, BPP is Bayesian planted partition model, H1 is hierarchical statistical clustering (with the hierarchy level with the smallest non-trivial number of clusters being used), KM is k-means clustering of ResMLP node representations.

Explore similar work

Gaussian Process Limit Reveals Structural Benefits of Graph Transformers
Mar 18, 2026Nil Ayday, Lingchu Yang, Debarghya GhoshdastidarGraph Neural Networks Graph Transformer
School of Computation, Information and Technology, Technical University of Munich · Graduate School of Information Science and Technology, The University of Tokyo
Robust Contrastive Graph Clustering with Adaptive Local-Global Integration
May 27, 2026Lei Zhang, Fubo Sun, Haipeng Yang +2Graph Representation Learning Multi-Scale Feature Fusion
School of Computer Science and Technology, Anhui University · College of Management and Economics, Tianjin University
Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning
Aug 27, 2026Jintang Li, Yuhong Chen, Ruofan Wu +4Graph Neural Networks Text-Attributed Graph Learning
School of Computer Science and Engineering of Central South University, Changsha 410000, China

Mar 18, 2026J/K move · Enter open · S save

Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

Nil Ayday, Lingchu Yang, Debarghya Ghoshdastidar

School of Computation, Information and Technology, Technical University of Munich · Graduate School of Information Science and Technology, The University of Tokyo

Graph Neural Networks Graph Transformer Node Classification

Open paper AskPDF arXiv

Graph transformers are the state-of-the-art for learning from graph-structured data and are empirically known to avoid several pitfalls of message-passing architectures. However, there is limited theoretical analysis on why these models perform well in practice. In this work, we prove that attention-based architectures have structural benefits over graph convolutional networks in the context of node-level prediction tasks. Specifically, we study the neural network gaussian process limits of graph transformers (GAT, Graphormer, Specformer) with infinite width and infinite heads, and derive the node-level and edge-level kernels across the layers. Our results characterise how the node features and the graph structure propagate through the graph attention layers. As a specific example, we prove that graph transformers structurally preserve community information and maintain discriminative node representations even in deep layers, thereby preventing oversmoothing. We provide empirical evidence on synthetic and real-world graphs that validate our theoretical insights, such as integrating informative priors and positional encoding can improve performance of deep graph transformers.

Abstract

Explore similar work

Gaussian Process Limit Reveals Structural Benefits of Graph Transformers

Robust Contrastive Graph Clustering with Adaptive Local-Global Integration

Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning