Research map / Graph learning / GNN architectures
Relieving the Over-Aggregating Effect in Graph Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Identifies an over-aggregating phenomenon in linear graph attention and proposes Wideformer, a plug-and-play method that clusters source nodes into parallel aggregations and sorts/weights cluster outputs by attention to focus on informative messages.
Problem
Global graph attention, especially linear variants, aggregates messages from very many nodes into one representation, causing uniform attention (high entropy), dilution of key messages, and information loss on large graphs.
Approach
Divide the global aggregation into m parallel cluster-wise aggregations (cluster centers chosen from query features via K-Means++-style selection, sources assigned by key-center similarity), then sort and weight the cluster outputs per target node by cluster attention scores, keeping the global receptive field at O(nm) cost.
Key results
- Wideformer improves Polynormer on roman-empire from 91.83% to 92.16% and on questions from 78.66% to 79.00% (ROC-AUC) in the heterophilic setting.
- On CoauthorPhysics, SGFormer+Wideformer reaches 97.39% accuracy versus 96.87% for SGFormer alone.
- Wideformer consistently reduces attention entropy across GraphGPS, SGFormer and Polynormer, and the reported cluster count of around 3-5 is found to be optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add Wideformer to the backbone | GraphGPS, SGFormer, and Polynormer · 13 real-world graph datasets | accuracy or ROC-AUC | Helped |
| reduce the number of clusters to one (from multiple clusters) (ablation) | Wideformer backbones · all datasets | performance gain | Hurt |
| increase cluster count beyond 6 (ablation) | Wideformer backbones · all datasets | performance gain | Hurt |
| use iterative clustering for center selection instead of the non-iterative strategy (ablation) | Wideformer · reported center-selection comparison | performance | Helped |
| use parameterized centers instead of the non-iterative strategy (ablation) | Wideformer · reported center-selection comparison | performance | Helped |
| add attention guidance to divided aggregation (ablation) | Wideformer backbones · reported module ablation datasets | performance | Helped |
| remove attention guidance while retaining divided aggregation (ablation) | Wideformer backbones · reported module ablation datasets | attention entropy | Hurt |
| add cluster-attention entropy regularization (ablation) | Wideformer backbones · roman-empire | accuracy: 81.46 -> 82.23; 75.20 -> 77.83; 91.83 -> 92.36 | Helped |
| add cluster-attention entropy regularization (ablation) | Wideformer backbones · CoauthorCS | accuracy: 95.44 -> 96.14; 93.50 -> 94.16; 94.53 -> 95.42 | Helped |
| add whole-attention entropy regularization | linear graph-attention backbones · reported datasets | performance | Helped |
Surprising findings
- Directly regularizing attention entropy on the full attention matrix yields only marginal gains and runs out of memory on larger graphs.
- Polynormer shows the largest entropy reduction but smaller performance gains than the other two backbones.
Limitations
- Only a simple K-Means++-based division and cluster-weighting guide are explored; learnable division and adaptive weighting are left open.
- The simple attention-guiding strategy can fail to benefit backbones when fewer source nodes contain informative messages (e.g., some Polynormer settings).
- Optimal cluster number varies and too many clusters disperse information and raise attention entropy.
Experimental setup
Datasets: amazon-ratings minesweeper questions roman-empire tolokers twitch-gamer Cora CiteSeer CoauthorCS CoauthorPhysics AmazonComputers AmazonPhoto
Benchmarks: amazon-ratings minesweeper questions roman-empire tolokers twitch-gamer Cora CiteSeer CoauthorCS CoauthorPhysics AmazonComputers AmazonPhoto
Metrics: accuracy ROC-AUC attention entropy paired t-test p-value
Baselines: GCN GraphSAGE GAT GPRGNN NAGphormer NodeFormer DIFFormer GOAT Exphormer ENACT Entropy Regularization
Builds on: GraphGPS SGFormer Polynormer Performer K-Means++
Closest papers by meaning
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.90)
- Even Sparser Graph Transformers (NeurIPS 2024 · similarity 0.89)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.87)
- Multi-Track Message Passing: Tackling Oversmoothing and Oversquashing in Graph Learning via Preventing Heterophily Mixing (ICML 2024 · similarity 0.86)
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.86)
- A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.