SimPlex-GT: Node-to-Cluster Attention for Graph Learning under Mixed Homophily and Heterophily

Real-world graphs frequently exhibit mixed homophily and heterophily, where local message passing and global attention provide complementary but often conflicting signals. Existing graph transformers (GTs) and GNN–GT hybrids combine these signals at a single level of abstraction, leading to interference and unstable training. We propose **SimPlex-GT**, which decouples the two by routing global reasoning through a small set of learned semantic prototypes rather than full node-to-node attention. Our **node-to-cluster (N2C) attention** computes prototypes per forward pass as a differentiable function of input features—distinguishing it from prior tokenization-based GTs that rely on free-parameter latents or codebook-style update rules—and replaces $\mathcal{O}(N^{2}d)$ pairwise attention with *exact* attention against $M\ll N$ prototypes at $\mathcal{O}(NMd)$ cost. A lightweight GCN branch supplies local inductive bias, and three regularizers stabilize the global branch: complementary filtering of input features, cluster smoothing over the coarse graph induced by soft assignments, and a teacher–student self-supervised objective that prevents prototype collapse. The model is pretrained without labels and evaluated with a frozen linear probe. Across 14 node-classification, 3 graph-classification, and 4 node-clustering benchmarks (17 datasets in total), SimPlex-GT improves over the strongest baseline in our comparison by **+5.95** points on Squirrel-filtered, **+0.69** points on Penn94, and **+2.45** points on Amazon-Ratings, matches or improves on homophilic Cora/CiteSeer/PubMed, and trains faster in total wall-clock time than NodeFormer (**2.3×**, from faster convergence at comparable per-epoch cost) and GREET (up to **8.5×**). Controlled ablations isolate the input-conditioned prototype construction: replacing it with freely learned prototype vectors costs 2.9–8.3 points across heterophilic, mixed, and homophilic graphs. The results suggest that the bottleneck in scalable graph attention is *what to attend to*, not how cheaply to approximate full attention.