Rethinking Graph Transformers as Graph Signal Denoisers: The Role of Block-Diagonal Priors
Lists
Only you see this
Abstract
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.
BibTeX
@inproceedings{zhuo2026rethinking,
author = {Jiaming Zhuo and Ziyi Ma and Kun Fu and Di Jin and Chuan Wang and Zhen Wang and Xiaochun Cao and Huazhu Fu and Liang Yang},
title = {{Rethinking Graph Transformers as Graph Signal Denoisers: The Role of Block-Diagonal Priors}},
booktitle = {International Conference on Machine Learning},
year = {2026},
url = {https://openreview.net/forum?id=EgfItWD8J8},
}Loading related content...