Rethinking Graph Transformers as Graph Signal Denoisers: The Role of Block-Diagonal Priors

By synergizing graph topology with the global expressive power of attention, Graph Transformers (GTs) have emerged as a powerful architecture for node classification. Existing GTs mainly focus on diverse topology injection paradigms, which fundamentally construct different propagation operators. However, a unified theoretical understanding of what constitutes a desirable propagation operator remains largely unexplored. To bridge this gap, this paper rethinks GTs from a graph signal denoising perspective, revealing that a block-diagonal structure is a desirable structural prior for graph denoising. To efficiently instantiate this prior, this paper introduces BDFormer, which imposes spectral block regularization on the affinity of a compact set of latent anchors. Furthermore, by introducing hard assignments between nodes and anchors, BDFormer establishes sparse, structured propagation that suppresses noisy cross-class propagation in linear time. Meanwhile, the learned global affinity guides the pruning of inter-class edges in the graph topology, enabling both global and local propagation to jointly adhere to the target block-diagonal structure. Extensive experiments on benchmark datasets demonstrate the superiority and scalability of BDFormer.