Graph Fourier Transformer with Structure-Frequency Information

• URL: http://arxiv.org/abs/2504.19740v1
• Date: Mon, 28 Apr 2025 12:38:02 GMT
• Title: Graph Fourier Transformer with Structure-Frequency Information
• Authors: Yonghui Zhai, Yang Zhang, Minghao Shang, Lihua Pang, Yaxin Ren,
• Abstract summary: This paper proposes Grafourierformer, which innovatively combines GT with inductive bias containing Frequency-Structure information.<n>Experiments on various benchmarks show Grafourierformer consistently outperforms GNN and GT-based models in graph classification and node classification tasks.
• Score: 2.7852431537059426
• License: http://creativecommons.org/licenses/by/4.0/
• 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

Related papers

• Dual-Frequency Filtering Self-aware Graph Neural Networks for Homophilic and Heterophilic Graphs [60.82508765185161]
  We propose Dual-Frequency Filtering Self-aware Graph Neural Networks (DFGNN) DFGNN integrates low-pass and high-pass filters to extract smooth and detailed topological features. It dynamically adjusts filtering ratios to accommodate both homophilic and heterophilic graphs.
  arXiv  Detail & Related papers  (2024-11-18T04:57:05Z)
• GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
  Graph State Space Network (GrassNet) is a novel graph neural network with theoretical support that provides a simple yet effective scheme for designing arbitrary graph spectral filters. To the best of our knowledge, our work is the first to employ SSMs for the design of graph GNN spectral filters. Extensive experiments on nine public benchmarks reveal that GrassNet achieves superior performance in real-world graph modeling tasks.
  arXiv  Detail & Related papers  (2024-08-16T07:33:58Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Gradformer: Graph Transformer with Exponential Decay [69.50738015412189]
  Self-attention mechanism in Graph Transformers (GTs) overlooks the graph's inductive biases, particularly biases related to structure. This paper presents Gradformer, a method innovatively integrating GT with the intrinsic inductive bias. Gradformer consistently outperforms the Graph Neural Network and GT baseline models in various graph classification and regression tasks.
  arXiv  Detail & Related papers  (2024-04-24T08:37:13Z)
• UniG-Encoder: A Universal Feature Encoder for Graph and Hypergraph Node Classification [6.977634174845066]
  A universal feature encoder for both graph and hypergraph representation learning is designed, called UniG-Encoder. The architecture starts with a forward transformation of the topological relationships of connected nodes into edge or hyperedge features. The encoded node embeddings are then derived from the reversed transformation, described by the transpose of the projection matrix.
  arXiv  Detail & Related papers  (2023-08-03T09:32:50Z)
• Graph Kernel Neural Networks [53.91024360329517]
  We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
  arXiv  Detail & Related papers  (2021-12-14T14:48:08Z)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  Spectral graph convolutional networks (SGCNs) have been attracting increasing attention in graph representation learning. We propose a novel class of spectral graph convolutional networks that implement graph convolutions with adaptive graph wavelets.
  arXiv  Detail & Related papers  (2021-08-03T17:57:53Z)
• GraphiT: Encoding Graph Structure in Transformers [37.33808493548781]
  We show that viewing graphs as sets of node features and structural and positional information is able to outperform representations learned with classical graph neural networks (GNNs) Our model, GraphiT, encodes such information by (i) leveraging relative positional encoding strategies in self-attention scores based on positive definite kernels on graphs, and (ii) enumerating and encoding local sub-structures such as paths of short length.
  arXiv  Detail & Related papers  (2021-06-10T11:36:22Z)
• Rethinking Graph Transformers with Spectral Attention [13.068288784805901]
  We present the $textitSpectral Attention Network$ (SAN), which uses a learned positional encoding (LPE) to learn the position of each node in a given graph. By leveraging the full spectrum of the Laplacian, our model is theoretically powerful in distinguishing graphs, and can better detect similar sub-structures from their resonance. Our model performs on par or better than state-of-the-art GNNs, and outperforms any attention-based model by a wide margin.
  arXiv  Detail & Related papers  (2021-06-07T18:11:11Z)
• A Generalization of Transformer Networks to Graphs [5.736353542430439]
  We introduce a graph transformer with four new properties compared to the standard model. The architecture is extended to edge feature representation, which can be critical to tasks s.a. chemistry (bond type) or link prediction (entity relationship in knowledge graphs)
  arXiv  Detail & Related papers  (2020-12-17T16:11:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.