GraFix++: A novel graph transformer based on a fixed multi-head structural attention mechanism

Graph neural networks (GNNs) have achieved strong performance on graph learning tasks, but their message-passing mechanism makes it difficult to capture long-range structural dependencies and may lead to over-smoothing in deeper architectures. Graph transformers offer a possible remedy, yet existing approaches typically rely on learnable attention or additional structural encodings, which increase the number of trainable parameters and computational cost while not always exploiting graph structure explicitly. Motivated by these limitations, we propose GraFix++, a graph transformer based on a fixed (non-learnable) multi-head structural attention mechanism derived from graph kernels. Multiple attention heads capture a range of structural similarities between substructures in the input graph, while a GNN is employed to improve the node features extraction. The resulting graph transformer showcases an excellent performance on standard graph classification benchmarks, matching or surpassing a wide range of alternative graph-based approaches. Furthermore, our model benefits from a reduced number of learnable parameters and competitive training runtime. In our experiments, we extensively evaluate the impact of various graph kernels, multiple attention heads, and GNN integration, demonstrating their collective contribution to the model's superior performance.