Cluster Attention for Graph Machine Learning

Oleg Platonov, Liudmila Prokhorenkova · 2026

Read Cluster Attention for Graph Machine Learning by Oleg Platonov, Liudmila Prokhorenkova (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-07492.txt.

Introduction

Platonov and Prokhorenkova propose cluster attention for graph machine learning, widening receptive fields without losing graph-structure biases. Message-passing nets are limited by layer count, while global-attention graph transformers ignore topology and its inductive biases. Cluster attention splits nodes into communities with standard detection methods and lets each node attend to all nodes in each cluster. The method keeps large receptive fields plus strong structural biases. Adding cluster attention to message-passing nets or graph transformers much improves scores across many graph datasets, including real-world GraphLand benchmarks.

Catalog record

CREATOROleg Platonov, Liudmila Prokhorenkova
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61205
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.07492

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cluster Attention for Graph Machine Learning Oleg Platonov, Liudmila Prokhorenkova 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. 1 Introduction Graphs are a natural way to represent data from different domains such as social networks (both real-life and virtual), computer networks, transportation networks, co-purchasing networks, molecules, connectomes, neural network architectures, various physical and biological systems, or even interconnected abstract concepts. Thus, machine learning on graph-structured data, henceforth referred to as Graph Machine Learning (GML), has attracted a lot of attention recently. In particular, Graph Neural Networks (GNNs) ( 16 ; 37 ; 26 ; 31 ) have become the most popular models for most GML tasks in the past decade. Most modern GNNs can be unified by the Message Passing Neural Networks (MPNNs) framework ( 26 ) . In this framework, within each neural network layer each node in the graph sends messages to its neighbors and aggregates incoming messages to form its new representation based on them. The graph-structure based relational inductive biases of MPNNs, which send messages along graph edges, turned out to be very effective for modeling many real-world networks ( 5 ) . However, in each MPNN layer, the model only exchanges information between neighboring nodes. Thus, the model’s receptive field, i.e., the maximum shortest path distance information can travel between nodes in the graph, is equal to the number of message passing layers. This has been argued to be a limitation of MPNNs as it prevents taking into account long-range interaction between nodes that might happen in some networks. Thus, Graph Transformers with global (all-to-all) attention have been proposed as an alternative neural model architecture for GML ( 38 ; 79 ; 77 ; 62 ) , inspired by the success of the Transformer architecture in the field of natural language processing ( 74 ) . However, all-to-all attention does not have any information about the graph structure, which is arguably very important for solving GML tasks, and thus this information has to be integrated into the model in some other ways (typically via positional encodings or MPNN-Transformer hybridization). It has been observed that many real-world networks exhibit community structure — presence of well-defined clusters of densely connected nodes with sparser connections between these clusters ( 27 ) . The problem of finding such clusters — graph clustering — has been extensively studied in network science and machine learning communities, and many methods for it have been proposed over the years ( 25 ) . Such algorithms can be used to divide graph nodes into clusters where nodes within the same cluster are strongly related, where the exact definition of this relation and thus the meaning of the obtained clusters can differ between different clustering algorithms. In this work, we argue that various partitions of a graph into node clusters provide very useful information about the graph structure and thus it can be beneficial to integrate these partitions into GML models. Specifically, we propose cluster attention (CLATT) — a graph-based attention mechanism in which nodes can attend to other nodes in the same cluster and thus exchange information with them. We view cluster attention as a middle ground between MPNNs in which only neighboring nodes can interact with each other and Graph Transformers in which all nodes can interact with each other. Cluster attention allows capturing longer-ranged dependencies than MPNNs while still providing strong graph-structure-based inductive biases which Graph Transformers lack. We argue that the graph-structure-based inductive biases of cluster attention are complementary to those of MPNNs and thus propose augmenting MPNNs with cluster attention. Similarly, Graph Transformers can be augmented with CLATT to provide these global attention models with stronger graph-structure-based inductive biases. In experiments on a diverse set of 12 real-world graph datasets, we demonstrate that cluster attention can significantly improve the performance of both MPNNs and Graph Transformers. The rest of this paper is structured as follows. Section 2 provides the necessary background on GML with neural networks and on graph node clustering. In Section 3 , we formally define cluster attention and discuss its implementation details. In Section 4 , we discuss our approach to selecting graph node clustering algorithms to use with cluster attention. Section 5 presents our experimental results. In Section 6 , we discuss the limitations of cluster attention. Section 7 provides concluding remarks. 2 Background and related work 2.1 Graph Neural Networks and Graph Transformers In recent years, Graph Neural Networks (GNNs), in particular Message Passing Neural Networks (MPNNs) ( 26 ) , have become the most dominant approach to graph machine learning tasks. In each message passing layer of an MPNN, each node aggregates representations from its neighbors in the graph (by receiving messages from them) and updates its own representation based on the aggregated information. Many GNN architectures falling under the MPNNs framework have been proposed ( 37 ; 31 ; 75 ; 78 ; 11 ) , mostly differing in their aggregation function. The receptive field of MPNNs, i.e., the maximum shortest path distance in the graph at which nodes can interact with each other, is equal to the number of message passing layers. This is often viewed as a limitation, since long-range dependencies can exist in some graph machine learning problems. While there have been some works attempting to increase the receptive field of MPNNs ( 1 ; 21 ) , a different and more radical approach has become more popular: replacing MPNNs with models with all-to-all Transformer-style attention ( 74 ) that has global receptive field. Such models became known as Graph Transformers (GTs) ( 38 ; 79 ; 77 ; 62 ) . However, global attention has no information about graph topology and thus this approach foregoes graph-structure-based inductive biases of MPNNs and essentially treats the graph nodes as a set rather than a graph. To inject graph information into GTs, various positional encoding (PEs) are typically added to node features or attention weights. Such PEs are often based on Laplacian eigenvectors ( 19 ) , graph distances ( 79 ) , or random walks ( 18 ) . However, despite the success of the Transformer architecture in other fields such as natural language processing, computer vision, and audio processing, and despite considerable research efforts to adapt Transformers to graph machine learning, recent benchmarking works show that GTs tend to not provide advantages

Read the complete text