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.

Graph Transformers are advanced machine learning models designed to analyze network data, such as social connections or scientific citations. However, real-world networks are inherently noisy, often containing irrelevant or misleading connections. When these models allow information to propagate indiscriminately across an entire network, they inadvertently mix useful signals with this noise, which degrades predictive accuracy and incurs massive computational costs. To address this, this paper proposes BDFormer, a model that views network learning through the lens of "noise filtering." Our key insight is that information should primarily flow within well-defined, coherent communities rather than crossing into unrelated groups. BDFormer achieves this by introducing a small set of "anchors" that help organize the network into a structured, block-by-block format. This design actively suppresses noisy, cross-community interactions and prunes irrelevant connections from the original network. Ultimately, BDFormer provides a principled way to filter out structural noise. It delivers highly accurate predictions while operating with exceptional computational efficiency, making it highly scalable for massive real-world networks.