Graph Fourier Transformer with Structure-Frequency Information
Yonghui Zhai, Yang Zhang, Minghao Shang, Lihua Pang, Yaxin Ren · 2025
Read Graph Fourier Transformer with Structure-Frequency Information by Yonghui Zhai, Yang Zhang, Minghao Shang, Lihua Pang, Yaxin Ren (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19740.txt.
Introduction
Yonghui Zhai and co-authors add frequency sense to graph transformers in this 2025 paper. Graph transformers read networks by letting every node attend to others. Plain attention ignores patterns that graph veterans rely on, such as smooth trends versus sharp local breaks. Their model, Grafourierformer, mixes both kinds of information into the attention step.
A graph Fourier transform splits signals into low and high frequency parts. Masks built from the graph's own eigenvalues steer attention toward the right mix. Tests on graph and node sorting tasks beat both classic graph networks and other transformers. Removing parts of the design lowered scores, which supports each part's role. The code is public.
Catalog record
| CREATOR | Yonghui Zhai, Yang Zhang, Minghao Shang, Lihua Pang, Yaxin Ren |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19740
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Fourier Transformer with Structure-Frequency Information Yonghui Zhai, Yang Zhang, Minghao Shang, Lihua Pang, Yaxin Ren Abstract Graph Transformers (GTs) have shown advantages in numerous graph structure tasks but their self-attention mechanism ignores the generalization bias of graphs, with existing methods mainly compensating for this bias from aspects like position encoding, attention bias and relative distance yet still having sub-optimal performance and being insufficient by only considering the structural perspective of generalization bias. To address this, this paper proposes Grafourierformer, which innovatively combines GT with inductive bias containing Frequency-Structure information by applying Graph Fourier Transform to the Attention Matrix: specifically, eigenvalues from the Graph Laplacian matrix are used to construct an Eigenvalue matrix mask (reflecting node positions and structural relationships with neighboring nodes to enable consideration of node range structural characteristics and focus on local graph details), and inverse Fourier transform is employed to extract node high-frequency and low-frequency features, calculate low-frequency and high-frequency energy, and construct a node frequency-energy matrix to filter the eigenvalue matrix mask, allowing attention heads to incorporate both graph structural information and node frequency information optimization, adaptively distinguish global trends from local details, and effectively suppress redundant information interference. Extensive experiments on various benchmarks show Grafourierformer consistently outperforms GNN and GT-based models in graph classification and node classification tasks, with ablation experiments further validating the effectiveness and necessity of the method. Codes are available at https://github.com/Arichibald/Grafourierformer.git 1 Introduction Graph-structured data plays a pivotal role in modern machine learning, with applications spanning social networks, molecular biology, and recommender systems. Traditional Graph Neural Networks (GNNs) rely on message-passing mechanisms to aggregate local neighborhood information, but their limited receptive fields hinder their ability to capture complex global dependencies. Graph Transformers (GTs) ( Dwivedi and Bresson 2020 ) address this limitation through self-attention mechanisms, enabling direct interactions between any pair of nodes and facilitating global information aggregation. However, the uniform attention mechanism in standard GTs fails to account for the inherent inductive biases in graph data—namely, structural correlations and frequency characteristics among nodes—resulting in suboptimal performance in capturing local structural details and multi-scale features. Existing approaches attempt to mitigate this issue through two primary strategies: (1) positional encoding, where methods such as GT ( Dwivedi and Bresson 2020 ) and SAN Kreuzer et al. 2021 employ Laplacian eigenvectors to encode structural information, and (2) attention bias, where models like Gradformer ( Liu et al. 2024a ) adjust attention scores based on the shortest path distances between nodes. However, as illustrated in Figure 1 , these methods exhibit only marginal differences in attention patterns compared to standard GTs, suggesting insufficient optimization of the attention mechanism. Crucially, these approaches focus solely on structural inductive bias while neglecting the frequency-domain properties of graphs—where low-frequency signals correspond to global trends and high-frequency signals reflect local details ( Shuman et al. 2013 ) . This oversight renders existing models susceptible to redundant information interference, particularly in low-resource settings or complex graph structures, ultimately limiting their performance. To address these limitations, we propose Graph Fourier Transformer (Grafourierformer), a novel architecture that integrates graph Fourier transforms into the GT framework, enabling joint structure-frequency modeling for multi-dimensional inductive bias injection. Our key innovations include: 1) Laplacian Eigenvalue Mask: Leveraging the eigenvalues of the graph Laplacian matrix to construct a structure-sensitive attention mask, explicitly modeling local connectivity patterns and global structural correlations. 2) Node Frequency Energy Filter: Decomposing node features into low- and high-frequency components via inverse Fourier transform, then dynamically adjusting attention weights based on their energy distribution to enhance multi-scale feature extraction. This dual mechanism establishes a novel paradigm: "structural constraints guide attention range, while frequency optimization refines attention weights." Grafourierformer offers three key advantages: 1) Unified Modeling: The graph Fourier transform enables the first joint representation of structural and frequency-domain information, providing a more comprehensive inductive bias. 2) Adaptive Feature Separation: The frequency energy filter dynamically distinguishes between global trends and local details, effectively suppressing redundant information. 3) Hybrid Local-Global Learning: The combined structural-frequency mask preserves the local sensitivity while retaining the global modeling strength. Extensive experiments on eight benchmark datasets demonstrate that Grafourierformer outperforms 15 baseline models across most tasks, with particularly significant gains in low-resource scenarios. For instance, on the NCI1 dataset with only 5% training data, Grafourierformer achieves a 1.59% accuracy improvement over the best competitor. These results validate the efficacy of joint structure-frequency modeling. Contributions: 1.We propose the first GT framework integrating graph Fourier transforms, unifying structural and frequency-domain optimization. 2.We design Laplacian eigenvalue masks and frequency energy filters to inject multi-dimensional inductive biases into attention mechanisms. 3.We empirically demonstrate Grafourierformer’s superiority, particularly its robustness in low-resource settings. The remainder of this paper is organized as follows: section 2 details Grafourierformer’s methodology; section 3 presents experimental results and analysis; section 4 reviews related work; and section 5 concludes with future research directions. 2 Methodology 2.1 Preliminaries Let an undirected graph be denoted as G=(V,E) , consisting of nodes V and edges E . The graph G can be represented by an adjacency matrix A\in\{0,1\}^{n\times n} and a node feature matrix X\in\mathbb{R}^{n\times d} , where n is the number of nodes, d is the feature dimension, and A[i,j]=1 if there exists an edge between nodes v_{i} and v_{j} , otherwise A[i,j]=0 . Traditional Graph Transformers (GTs) employ parameter matrices W_{Q}^{l} , W_{K}^{l} , and W_{V}^{l}\in\mathbb{R}^{d_{l}\times d_{l+1}} to project node features into queries Q^{l} , keys K^{l} , and values V^{l} : Q^{l}=x_{\text{node}}^{l}W_{Q}^{l},\quad K^{l}=x_{\text{node}}^{l}W_{K}^{l},\quad V^{l}=x_{\text{node}}^{l}W_{V}^{l}, (1) where l denotes the layer index of the Transformer and d_{l} represents the hidden dimension at layer l . The attention mechanism computes dot products between queries and keys to generate attention maps, subsequently producing output node embeddings x_{\text{node}}^{l+1} : A^{l}=\frac{Q^{l}{K^{l}}^{T}}{\sqrt{d_{l}}},\quad x_{\text{node}}^{l+1}=\text{softmax}(A^{l})V^{l}, (2) where A^{l}\in\mathbb{R}^{n\times n\times d_{l+1}} represents the output attention map. This single-head self-attention module can be generalized to a multi-head self-attention (MHA) module through concatenation operations. 2.2 Proposed Method: Grafourierformer This subsection describes the Grafourierformer method. First, we describe the architecture of the Grafourierformer and the process of graph Fourier transform, focusing our attention on two modules: the Laplace matrix eigenvalue mask and the node frequency energy filter. We explore in detail how the Grafourierformer method optimizes the self-attention matrix. Architecture Figure 1: The structure of Grafourierformer is optimized by Structure-Frequency Mask on the attention matrix to achieve the fusion of graph structure information and node frequency information with attention. As shown in Figure 1 , Grafourierformer introduces Structure-Frequency Mask to optimize the self-attention matrix on the basis of GT, and injects the graph structure information and node frequency information into the self-attention matrix by using graph Fourier Transform, which introduces a more comprehensive inductive bias in self-attention learning. Graph Fourier Transform Consider an undirected graph G=(V,E) with adjacency matrix A\in\{0,1\}^{n\times n} , where V represents the set of nodes with |V|=N and E denotes the set of edges. The normalized graph Laplacian matrix is defined as: L=I_{n}-D^{-1/2}AD^{-1/2} (3) where D\in\mathbb{R}^{n\times n} is a diagonal degree matrix with elements D_{i,i}=\sum_{j}A_{i,j} , and I_{n} denotes the identity matrix. As L is a real symmetric matrix, it possesses a complete set of orthogonal eigenvectors {u_{l}}_{l=1}^{n}\in\mathbb{R}^{n} , each associated with a corresponding eigenvalue \lambda_{l}\in[0,2] ( Chung 1997 ) . Through eigendecomposition, we have: L=U\Lambda U^{T} , where \Lambda=\text{diag}([\lambda_{1},\lambda_{2},\dots,\lambda_{n}])