# Global Attention Improves Graph Networks Generalization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2020.

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

- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Equivariant Hypergraph Neural Networks](https://mlsanity.com/paper/2208.10428/) (2022)
- [On the approximation capability of GNNs in node classification/regression tasks](https://mlsanity.com/paper/2106.08992/) (2021)
- [Calibrated Dataset Condensation for Faster Hyperparameter Search](https://mlsanity.com/paper/2405.17535/) (2024)
- [Memory-Associated Differential Learning](https://mlsanity.com/paper/2102.05246/) (2021)
- [Universality and Approximation Rates of Graph Neural Networks with Random Features](https://mlsanity.com/paper/2607.26699/) (2026)
- [Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency](https://mlsanity.com/paper/2511.12838/) (2025)

## Abstract (arXiv)

This paper advocates incorporating a Low-Rank Global Attention (LRGA) module, a computation and memory efficient variant of the dot-product attention (Vaswani et al., 2017), to Graph Neural Networks (GNNs) for improving their generalization power. To theoretically quantify the generalization properties granted by adding the LRGA module to GNNs, we focus on a specific family of expressive GNNs and show that augmenting it with LRGA provides algorithmic alignment to a powerful graph isomorphism test, namely the 2-Folklore Weisfeiler-Lehman (2-FWL) algorithm. In more detail we: (i) consider the recent Random Graph Neural Network (RGNN) (Sato et al., 2020) framework and prove that it is universal in probability; (ii) show that RGNN augmented with LRGA aligns with 2-FWL update step via polynomial kernels; and (iii) bound the sample complexity of the kernel's feature map when learned with a randomly initialized two-layer MLP. From a practical point of view, augmenting existing GNN layers with LRGA produces state of the art results in current GNN benchmarks. Lastly, we observe that augmenting various GNN architectures with LRGA often closes the performance gap between different models.