Research map / Graph learning / Graph self-supervised learning
Cluster-wise Graph Transformer with Dual-granularity Kernelized Attention
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.
Proposes Cluster-GT, a graph transformer that keeps Metis clusters uncompressed and uses a linear-time Node-to-Cluster Attention (N2C-Attn) combining cluster- and node-level kernels via multiple kernel learning.
Problem
Node-clustering graph pooling methods coarsen each cluster into a single embedding, causing homogeneous cluster representations, loss of node-level information, and oversimplified cluster-to-cluster interactions.
Approach
Treat the graph as interconnected node sets without coarsening; build bi-level (cluster and node) queries and keys and combine their kernels via tensor product or convex sum (multiple kernel learning) inside kernelized attention, rewritten as linear-time cluster-wise message passing.
Key results
- On six TU datasets, Cluster-GT reports the best accuracy on IMDB-BINARY (75.10%), IMDB-MULTI (52.13%), MUTAG (87.11%), PROTEINS (76.48%) and D&D (79.15%), while COLLAB (80.43%) trails SEP-G (81.28%).
- Cluster-GT outperforms most existing graph transformers on ZINC and MolHIV, per the paper's claim (the specific numbers are not in the extracted text).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Cluster-GT instead of SEP-G | Graph classification · IMDB-BINARY | accuracy: 74.12 -> 75.10 | Helped |
| Use Cluster-GT instead of SEP-G | Graph classification · IMDB-MULTI | accuracy: 51.53 -> 52.13 | Helped |
| Use Cluster-GT instead of SEP-G | Graph classification · COLLAB | accuracy: 81.28 -> 80.43 | Hurt |
| Use Cluster-GT instead of SEP-G | Graph classification · MUTAG | accuracy: 85.56 -> 87.11 | Helped |
| Use Cluster-GT instead of SEP-G | Graph classification · PROTEINS | accuracy: 76.42 -> 76.48 | Helped |
| Use Cluster-GT instead of GMT | Graph classification · D&D | accuracy: 78.72 -> 79.15 | Helped |
| Use attention that combines node-level and cluster-level information instead of cluster-level-only attention (ablation) | Cluster-GT · Graph classification datasets in the attention ablation | performance | Helped |
| Use attention that combines node-level and cluster-level information instead of node-level-only attention (ablation) | Cluster-GT · Graph classification datasets in the attention ablation | performance | Helped |
| Use N2C-Attn-T instead of N2C-Attn-L (ablation) | Cluster-GT · Graph classification datasets in the attention ablation | performance | Helped |
| Use cluster aggregation instead of DeepSets to form cluster-level queries or keys (ablation) | Cluster-GT · Graph classification | performance | No clear effect |
| Make cluster-level and node-level queries identical (ablation) | Cluster-GT with different bi-level keys · Graph classification | performance | No clear effect |
Surprising findings
- Cluster-level-only and node-level-only attention variants both underperform the combined N2C-Attn variants, with the tensor-product variant leading marginally.
- Cluster-GT pays more weight to cluster-level kernels on social network datasets than on biology datasets, per the learned alpha in N2C-Attn-L.
Limitations
- Uses a simple, non-learnable Metis partitioning rather than learned or flexible partitioning.
- COLLAB accuracy is slightly below SEP-G, so the method does not win on every dataset.
Experimental setup
Datasets: IMDB-BINARY IMDB-MULTI COLLAB MUTAG PROTEINS D&D ZINC MolHIV
Benchmarks: IMDB-BINARY IMDB-MULTI COLLAB MUTAG PROTEINS D&D ZINC MolHIV
Metrics: accuracy MAE ROC-AUC
Baselines: GCN GIN DiffPool SAGPool TopKPool ASAP MinCutPool SEP Set2Set SortPool StructPool GMT
Builds on: Metis kernelized softmax (linear attention) Multiple Kernel Learning GraphViT GCN GIN
Closest papers by meaning
- DHAKR: Learning Deep Hierarchical Attention-Based Kernelized Representations for Graph Classification (AAAI 2025 · similarity 0.87)
- Less is More: on the Over-Globalizing Problem in Graph Transformers (ICML 2024 · similarity 0.86)
- Deep Multi-modal Graph Clustering via Graph Transformer Network (AAAI 2025 · similarity 0.86)
- VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections (ICLR 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)
- Towards Principled Graph Transformers (NeurIPS 2024 · 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.