Scalable Message Passing Neural Networks: no need for attention in large graph representation learning

Conference item

We propose Scalable Message Passing Neural Networks (SMPNNs) and demonstrate that, by integrating standard convolutional message passing into a Pre-Layer Normalization Transformer-style block instead of attention, we can produce highperforming deep message-passing-based Graph Neural Networks (GNNs). This modification yields results competitive with the state-of-the-art in large graph transductive learning, particularly outperforming the best Graph Transformers in the literature, without requiring the otherwise computationally and memoryexpensive attention mechanism. Our architecture not only scales to large graphs but also makes it possible to construct deep message-passing networks, unlike simple GNNs, which have traditionally been constrained to shallow architectures due to oversmoothing. Moreover, we provide a new theoretical analysis of oversmoothing based on universal approximation which we use to motivate SMPNNs. We show that in the context of graph convolutions, residual connections are necessary for maintaining the universal approximation properties of downstream learners and that removing them can lead to a loss of universality.

Authors: Sáez de Ocáriz Borde, H; Lukoianov, A; Kratsios, A; Bronstein, M; Dong, X

• Publication status: Published
• Peer review status: Peer reviewed
• Host title: International Conference on Learning Representations 2026
• Publication date: 2026-04-26
• Acceptance date: 2026-03-02
• Event title: Workshop on Geometry-grounded Representation Learning and Generative Modeling (GRaM Workshop @ ICLR 2026)
• Event location: Rio de Janeiro, Brazil
• Event website: https://iclr.cc/virtual/2026/workshop/10000809
• Event start date: 2026-04-26
• Event end date: 2026-04-26
• Language: English