# Self-Attention in Colors: Another Take on Encoding Graph Structure in Transformers

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 42 references that are in the map.
- First posted on arXiv 21 Apr 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Residual Gated Graph ConvNets](https://mlsanity.com/paper/1711.07553/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs](https://mlsanity.com/paper/2103.09430/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Long Range Graph Benchmark](https://mlsanity.com/paper/2206.08164/) (2022)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [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)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [GraphiT: Encoding Graph Structure in Transformers](https://mlsanity.com/paper/2106.05667/) (2021)

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

- [An end-to-end attention-based approach for learning on graphs](https://mlsanity.com/paper/2402.10793/) (2024)
- [Graph Transformers without Positional Encodings](https://mlsanity.com/paper/2401.17791/) (2024)
- [Simple Path Structural Encoding for Graph Transformers](https://mlsanity.com/paper/2502.09365/) (2025)
- [Hybrid Focal and Full-Range Attention Based Graph Transformers](https://mlsanity.com/paper/2311.04653/) (2023)
- [Differential Encoding for Improved Representation Learning over Graphs](https://mlsanity.com/paper/2407.02758/) (2024)
- [Range-aware Positional Encoding via High-order Pretraining: Theory and Practice](https://mlsanity.com/paper/2409.19117/) (2024)
- [Challenges in Non-Polymeric Crystal Structure Prediction: Why a Geometric, Permutation-Invariant Loss is Needed](https://mlsanity.com/paper/2509.00832/) (2025)

## Abstract (arXiv)

We introduce a novel self-attention mechanism, which we call CSA (Chromatic Self-Attention), which extends the notion of attention scores to attention _filters_, independently modulating the feature channels. We showcase CSA in a fully-attentional graph Transformer CGT (Chromatic Graph Transformer) which integrates both graph structural information and edge features, completely bypassing the need for local message-passing components. Our method flexibly encodes graph structure through node-node interactions, by enriching the original edge features with a relative positional encoding scheme. We propose a new scheme based on random walks that encodes both structural and positional information, and show how to incorporate higher-order topological information, such as rings in molecular graphs. Our approach achieves state-of-the-art results on the ZINC benchmark dataset, while providing a flexible framework for encoding graph structure and incorporating higher-order topology.