A Survey on Spectral Graph Neural Networks
Graph neural networks (GNNs) have attracted considerable attention from the
research community. It is well established that GNNs are usually roughly
divided into spatial and spectral methods. Despite that spectral GNNs play an
important role in both graph signal processing and graph representation
learning, existing studies are biased toward spatial approaches, and there is
no comprehensive review on spectral GNNs so far. In this paper, we summarize
the recent development of spectral GNNs, including model, theory, and
application. Specifically, we first discuss the connection between spatial GNNs
and spectral GNNs, which shows that spectral GNNs can capture global
information and have better expressiveness and interpretability. Next, we
categorize existing spectral GNNs according to the spectrum information they
use, \ie, eigenvalues or eigenvectors. In addition, we review major theoretical
results and applications of spectral GNNs, followed by a quantitative
experiment to benchmark some popular spectral GNNs. Finally, we conclude the
paper with some future directions.
Deyu Bo, Xiao Wang, Yang Liu, Yuan Fang, Yawen Li, Chuan Shi
# A Survey on Spectral Graph Neural Networks

###### Abstract

Graph neural networks (GNNs) have attracted considerable attention from the research community. It is well established that GNNs are usually roughly divided into spatial and spectral methods. Despite that spectral GNNs play an important role in both graph signal processing and graph representation learning, existing studies are biased toward spatial approaches, and there is no comprehensive review on spectral GNNs so far. In this paper, we summarize the recent development of spectral GNNs, including model, theory, and application. Specifically, we first discuss the connection between spatial GNNs and spectral GNNs, which shows that spectral GNNs can capture global information and have better expressiveness and interpretability. Next, we categorize existing spectral GNNs according to the spectrum information they use, _i.e_., eigenvalues or eigenvectors. In addition, we review major theoretical results and applications of spectral GNNs, followed by a quantitative experiment to benchmark some popular spectral GNNs. Finally, we conclude the paper with some future directions.

## 1 Introduction

Graph neural networks (GNNs) have shown strong performance in graph-related tasks, including node classification [18, 17], link prediction [16], and graph classification [20]. In general, GNNs can be divided into spatial and spectral methods according to different definitions of graph convolution. Spatial methods, also known as message-passing neural networks (MPNNs) [14], perform graph convolutional in the vertical domain by aggregating the neighborhood information along graph structures. In contrast, spectral methods use spectral graph theory [15] to transform the convolutions into products of the frequency domain. Over the past few years, research on GNNs has focused on spatial methods because of their flexibility and scalability, [1]. On the contrary, research on spectral methods is somewhat under-explored.

Spectral GNNs have related but different views from spatial methods and play an important role in graph representation learning. First, **spatial and spectral GNNs capture different information**. Spatial GNNs aggregate node features layer by layer. Nodes can only capture information within a fixed distance, emphasizing local information. In contrast, spectral GNNs transform all node features into weighted sums of different eigenvectors via graph Fourier transform, which naturally captures global information. Second, **spatial and spectral GNNs use different design principles**. Spatial GNNs involve node-based updating, where the gradients flow between the connected nodes only and therefore have lower complexity, but their expressive power is bounded from above by the 1-Weisfeiler-Lehman (WL) test [21]. Spectral GNNs involve feature-based updating, where each feature is filtered by the fully-connected eigenspaces, and messages are passed among all nodes simultaneously. Although more complex, feature-based updating breaks the localized property and is thus more powerful than node-based updating [1]. Third, **spatial and spectral GNNs have different interpretability**. Spatial GNNs require a post-hoc interpretation strategy, which aims to find the most important graph structures related to a prediction, _e.g_., nodes, edges, or subgraphs [20]. Spectral GNNs are interpretable models in which the learned graph filters can directly state the most important frequency information associated with the labels, _e.g_., low-, medium-, and high-frequencies.

The above three points show that spectral GNNs are important in designing and explaining GNNs. However, little effort has been made to summarize the development of spectral methods. On the one hand, existing surveys of GNNs [20, 19] focus on spatial methods. On the other hand, spectral GNNs are close to graph signal processing (GSP). Ortega _et al_. [1] and Dong _et al_. [1] are two surveys on traditional GSP that formally define some fundamental concepts, such as filtering and sampling, but they do not explain the connection between spectral filtering and graph representation learning in detail. Besides, while both eigenvalues and eigenvectors play a role in the spectral domain, the latter has been largely ignored in previous literature.

In this paper, we provide a comprehensive and system
atic review of spectral GNNs. Specifically, we first analyze the differences between spatial and spectral GNNs and introduce the unique challenges of designing spectral methods. Then, we differentiate existing methods into two categories: eigenvalue-based and eigenvector-based, which correspond to the design of filters and basis functions in signal processing. Within each category, there are three subcategories, and we further analyze their strengths and weaknesses in terms of effectiveness and efficiency. Next, we introduce major theoretical results and important applications of spectral GNNs. We also make a quantitative experiment to test the performance and complexity of different graph filters on both homophilic and heterophilic benchmarks. Finally, we discuss a few promising future directions in spectral GNNs.

## 2 Challenges and Concepts

Spectral GNNs utilize neural networks to learn representations from spectral information. The design of spectral GNNs is not trivial, which poses the following three challenges:

* **Diversity of spectral information.** Spectral GNNs aim to learn node or graph representations from spectral information, which is informative but hard to explore. For example, eigenvalues and eigenvectors indicate the global and local structures [14], and the Fourier coefficients reflect the energy of signals on different harmonics. These spectral features with different meanings and tensor sizes pose the first challenge.
* **Complexity of graph data.** There are various types of graph data in real-world applications, such as dynamic graphs, heterogeneous graphs, hyper-graphs, etc. Most of them cannot be represented by a basic adjacency matrix. Therefore, how to extend the idea of spectral convolution to graph data other than undirected graphs is indispensable for spectral GNNs.
* **Scalability of methodology.** The complexity of the eigenvalue decomposition is the cube of the number of nodes. Besides, explicitly constructing the fully-connected eigenspaces also brings a quadratic time and space complexity. Both operations are important but expensive for spectral GNNs. How to make spectral GNNs scalable to large-scale graphs is a great challenge for spectral GNNs.

The reviews of spectral GNNs are shown in Section 3, where each approach solves at least one of these three challenges. Before that, we first introduce some important concepts to give a general understanding of spectral GNNs.

Assume that \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) is a graph, where \(\mathcal{V}\) is the node set with \(|\mathcal{V}|=N\) and \(\mathcal{E}\) is the edge set. Let \(\mathbf{A}\in\{0,1\}^{N\times N}\) be the adjacency matrix of \(\mathcal{G}\) and the normalized graph Laplacian matrix is defined as \(\mathbf{L}=\mathbf{I}_{N}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\), where \(\mathbf{D}\) is a diagonal degree matrix with \(D_{i,i}=\sum_{j}A_{i,j}\) and \(\mathbf{I}_{N}\) denotes the identity matrix.

Eigenvalue Decomposition (EVD).The graph Laplacian matrix can be decomposed as \(\mathbf{L}=\mathbf{U}\mathbf{A}\mathbf{U}^{\top}\), where \(\mathbf{\Lambda}=\text{diag}\{\lambda_{1},\cdots,\lambda_{N}\}\) is a diagonal matrix of eigenvalues and \(\mathbf{U}=[\mathbf{u}_{1},\cdots,\mathbf{u}_{N}]\) is the corresponding eigenvectors. If \(\mathbf{L}\) is symmetric, the eigenvalues are real and satisfy \(0\leq\lambda_{1}\leq\cdots\leq\lambda_{N}\leq 2\). Otherwise, both \(\mathbf{\Lambda}\) and \(\mathbf{U}\) will be complex. If no special emphasis, the graphs are undirected.

Graph Fourier Transform (GFT).Discrete Fourier transform (DFT) aims to decompose an input signal or function into a weighted sum of the orthogonal bases. Through SVD, we have \(\mathbf{L}\mathbf{u}_{i}=\lambda_{i}\mathbf{u}_{i}\) and \(\lambda_{i}=\mathbf{u}_{i}^{\top}\mathbf{L}\mathbf{u}_{i}\). Note that the eigenvalues reflect the frequency/smoothness of the corresponding eigenvectors. Since the eigenvectors are normalized and orthogonal, _i.e._\(||\mathbf{u}_{i}||=1\) and \(\mathbf{u}_{i}^{\top}\mathbf{u}_{i}=\delta_{ij}\), the eigenvectors can be used as the orthogonal bases. Given a graph signal \(\mathbf{x}\in\mathbb{R}^{N\times 1}\), its GFT and inverse GFT can be defined as:

\[\hat{\mathbf{x}}=\mathbf{U}^{\top}\mathbf{x},\;\mathbf{x}=\mathbf{U}\hat{ \mathbf{x}}, \tag{1}\]

where \(\hat{\mathbf{x}}\) is the Fourier coefficients of \(\mathbf{x}\).

Based on the eigenvalues and eigenvectors of graph Laplacian, we can define the convolutional in the Fourier domain.

Spectral Graph Convolution.The convolution between a filter \(f\) and a signal \(\mathbf{x}\) in the spatial domain is equal to their production in the spectral domain. Through GFT, the spectral graph convolutional is defined as

\[f*_{G}\mathbf{x}=\mathbf{U}\left(\left(\mathbf{U}^{\top}f\right)\odot\left( \mathbf{U}^{\top}\mathbf{x}\right)\right), \tag{2}\]

where \(f*_{G}x\) is the convolution and \(\odot\) is the production. Generally, spectral GNNs will parameterize \(\mathbf{U}^{\top}f\) with a learnable diagonal matrix \(\mathbf{G}=\text{diag}\{g_{1},\cdots,g_{N}\}\) as the spectral filter that can be optimized by gradient descent. We can rewrite the spectral graph convolutional as:

\[f*_{G}\mathbf{x}=\mathbf{U}\mathbf{G}\mathbf{U}^{\top}\mathbf{x}=(g_{1} \mathbf{u}_{1}\mathbf{u}_{1}^{\top}+\cdots+g_{N}\mathbf{u}_{N}\mathbf{u}_{N}^ {\top})\mathbf{x}, \tag{3}\]

where \(\mathbf{u}_{i}\mathbf{u}_{i}^{\top}\in\mathbb{R}^{N\times N}\) is the \(i\)-th fully-connected eigenspace.

## 3 Spectral Graph Neural Networks

In this section, we classify existing spectral GNNs into two categories: eigenvalue-based and eigenvector-based, according to the spectral information they used. Within each category, we will introduce three subcategory methods and explain their advantages and disadvantages as well as the connection in detail. Additionally, we present advances in theory and application, and benchmark existing methods on six datasets. The overall framework can be seen in Figure 1.

Figure 1: Framework of this survey.
### Eigenvalue-based Spectral GNNs

Eigenvalue-based spectral GNNs correspond to the design of filters in signal processing. Approaches belonging to this category aim to learn a good filter that captures the most important frequency information of input graph signals. In this section, we introduce three types of graph filters: advanced filters, polynomial filters, and linear filters, from which we can observe how the spectral GNNs evolve to reduce complexity and scale to large graphs, along with the declining of expressive power.

**Advanced Filters**

We refer to the spectral GNNs that explicitly take eigenvalues as the input of neural networks as advanced filters. Since the decomposition of graph Laplacian is time-consuming, advanced filters usually choose to truncate the graph spectrum, _i.e._, using the smallest-\(k\) eigenvalues and eigenvectors, to reduce the complexity. Although computationally intensive, such methods can capture the geometric information hidden in the eigenvalues. For example, the second-smallest eigenvalue indicates the algebraic connectivity of a graph.

SpectralCNN [14] is the first advanced graph filter, which treats the graph filter as the parameters of neural networks and directly optimizes it by gradient descent:

\[\mathbf{h}_{j}^{(l+1)}=\sigma(\mathbf{U}\sum_{i=1}^{d_{in}}\mathbf{G}_{ij}^{(l )}\mathbf{U}^{\top}\mathbf{h}_{i}^{(l)})\quad(j=1\cdots d_{out}), \tag{4}\]

where \(\sigma\) is the activation function and \(\mathbf{h}_{i}^{(l)}\in\mathbb{R}^{N\times 1}\) indicates the \(i\)-th dimension of the representations in \(l\)-th layer. SpectralCNN generalizes the design of convolutional neural networks (CNNs) to graphs and assigns each feature an independent graph filter, _i.e_. \(\mathbf{G}_{ij}^{(l-1)}\). Therefore, the total parameters of one convolution layer are \(\mathcal{O}(k^{2}d_{in}d_{out})\). More parameters enhance the fitting ability of SpectralCNN but also bring high time and space complexity. Additionally, the non-parametric graph filters make the model brittle. When there are multiple eigenvalues, SpectralCNN cannot handle the ambiguity of eigenvectors [15].

LanczosNet [11] uses spectral convolution to define a multi-scale graph representation learning framework. Spatial GNNs construct multi-scale representations by stacking multiple message-passing layers, _i.e_., calculating \(\mathbf{A},\mathbf{A}^{2},\cdots,\mathbf{A}^{K}\) recurrently, which is infeasible for large graphs. LanczosNet leverages the fact \(\mathbf{A}^{K}=\mathbf{U}\mathbf{A}^{K}\mathbf{U}^{\top}\) to reduce complexity and capture the long-range information in the spectral domain, which is more efficient. The long-range spectral filter is defined as:

\[L_{i}(\mathcal{I})=\sum_{t=1}^{k}f_{i}(\lambda_{t}^{\mathcal{I}_{1}},\lambda_{t }^{\mathcal{I}_{2}},\cdots,\lambda_{t}^{\mathcal{I}_{|\mathcal{I}|}})\mathbf{ u}_{t}\mathbf{u}_{t}^{\top}, \tag{5}\]

where \(f_{i}\) is an element-wise function, such as multilayer perceptron (MLP) and \(\mathcal{I}=\{10,20,\cdots,50\}\). For short-range information, LanczosNet directly uses spatial convolution. The overall framework is defined as:

\[\mathbf{h}^{(l+1)}=[\mathbf{A}\mathbf{h}^{(l)}\cdots\mathbf{A}^{K}\mathbf{h}^ {(l)},L_{1}(\mathcal{I})\mathbf{h}^{(l)}\cdots L_{T}(\mathcal{I})\mathbf{h}^{( l)}]\mathbf{W}. \tag{6}\]

It is worth noting that LanczosNet takes the eigenvalues as input and outputs the long-range graph filter. By leveraging the correspondence between eigenvalues and eigenvectors, LanczosNet learns invariant representations to the permutation of nodes and eigenvectors. The design of parameterizing eigenvalues as graph filters is first proposed by Defferrard _et al._ [13] and continued in subsequent work.

Specformer [1] is a recent work on advanced graph filters that considers the set relationships between eigenvalues, where rich geometric information is embedded. For example, the algebraic multiplicity of eigenvalue 0 reflects the number of connected components in the graph. But element-wise graph filters are not aware of such statistics. Therefore, Specformer uses Transformer [18] as a set-to-set graph filter to learn the set relationships between eigenvalues:

\[\mathbf{G}=\text{Transformer}(\rho(\mathbf{\Lambda})), \tag{7}\]

where \(\rho(\cdot)\) is a positional encoding function to vectorize the scalar eigenvalues. Theoretically, the set-to-set graph filter is a generalization of element-wise filters and, therefore, more expressive. However, the quadratic complexity of Transformer further increases the complexity of Specformer and makes it impossible to scale to large graphs.

**Summary.** The advanced filters are the first kind of spectral GNNs, which has great potential in graph representation learning. However, the explicit matrix factorization is time-consuming and prevents advanced filters from scaling to large graphs. Therefore, it is important to find suitable domains for advanced filters, such as molecular representation learning [1].

**Polynomial Filters**

The polynomial filters are special cases of advanced filters that simplify the neural networks into polynomial functions. The greatest advantage of the polynomial filters is that they avoid the explicit EVD but still preserve the arbitrary filtering ability. In addition to reducing the time complexity, ChebNet also learns a localized graph filter, _i.e_. only nodes within \(K\)-hops are connected. The localization property ensures that graph filters remain sparsely connected in space and reduce the cost of memory. Therefore, polynomial filters attract considerable attention in recent years.

The basic polynomial filter is the weighted sum of graph Laplacian of different orders, which can be defined as:

\[\mathbf{G} =\theta_{0}\mathbf{I}+\theta_{1}\mathbf{\Lambda}+\cdots+\theta_{K} \mathbf{\Lambda}^{K}, \tag{8}\] \[\mathbf{UGU}^{\top} =\theta_{0}\mathbf{I}+\theta_{1}\mathbf{L}+\cdots+\theta_{K} \mathbf{L}^{K},\]

where \(\{\theta_{0},\theta_{1},\cdots,\theta_{K}\}\) are the coefficients of polynomials. However, there are some disadvantages. For example, the polynomial terms \(\{\mathbf{L},\mathbf{L}^{2},\cdots,\mathbf{L}^{K}\}\) are non-orthogonal, which may affect the convergence of models. There are many works that try to improve the design of polynomial filters, most of which are based on the approximation theory, such as Chebyshev polynomial, Bernstein polynomial, etc.

ChebNet [1] uses Chebyshev expansion to construct a polynomial filter. Due to its orthogonality, ChebNet can be trained quickly to converge with a small
number of polynomial terms. The Chebyshev polynomial filter is defined as:

\[\mathbf{G}=\sum_{k=1}^{K}\theta_{k}\mathcal{T}_{k}(\tilde{\mathbf{A}}), \tag{9}\]

where \(\tilde{\mathbf{A}}=\frac{2\mathbf{A}}{\lambda_{max}}-\mathbf{I}_{N}\) that scales the eigenvalues in the range \([-1,1]\) and \(\mathcal{T}_{k}(x)=2x\mathcal{T}_{k-1}(x)-\mathcal{T}_{k-2}(x)\) with \(\mathcal{T}_{0}=1,\mathcal{T}_{1}=x\) constructs the orthogonal space. Although ChebNet has a good approximation ability, it may fail under certain boundary conditions, known as the Runge phenomenon (Eperson, 1987). ChebNetII (He _et al._, 2022) is then proposed to use Chebyshev interpolation to enhance the approximation of ChebNet and alleviate the over-fitting problem.

There are also other polynomial filters. For example, GPRGNN (Chien _et al._, 2021) considers the PageRank information, BernNet (He _et al._, 2021) uses Bernstein polynomial to keep the graph filter positive semidefinite, JacobiConv (Wang and Zhang, 2022) provides a more general orthogonal base through Jacobi polynomial, and DSGC (Li _et al._, 2021) designs polynomial filters on both node and attribute affinity graphs. Here we do not describe them in detail.

Another type of polynomial filter is the relational graph filter, which has a good approximation to the narrow bands, where there is a sharp change in the frequency response. The aforementioned polynomial filters need to increase their order to fit such narrow bands, which may result in numerical instability. Relational graph filters solve this problem by learning the ratio between two polynomials as the filtering, which can be formulated as:

\[\mathbf{G}=\left(\sum_{q=0}^{Q}\theta_{q}\mathbf{\Lambda}_{i}^{q}\right) \left(\mathbf{I}+\sum_{p=0}^{P}\theta_{p}\mathbf{\Lambda}_{i}^{p}\right)^{-1}, \tag{10}\]

where \(Q\) and \(P\) are the orders of the two polynomials. CayleyNets (Levie _et al._, 2019) and GraphARMA (Bianchi _et al._, 2022) are two traditional relational graph filters in the complex and real domains, respectively. Relational graph filters can fit the narrow bands with fewer orders. However, the calculation of the inverse of a matrix is time-consuming and unstable, which requires carefully designed constraints, _i.e._, \(1+\sum_{p=0}^{P}\theta_{p}\lambda_{i}\neq 0,\forall i\in N\).

**Summary.** Polynomial filters can approximate arbitrary filters, _e.g._, low-, medium-, and high-pass, and easily scale to large graphs, which are widely used in various applications. For example, multivariate time-series forecasting (Liu _et al._, 2022). However, the numerical instability needs to be carefully considered in designing polynomial filters, which is caused by calculating the \(K\)-th power of the Laplacian matrix. Spec-GN (Yang _et al._, 2022) provides a spectrum-shrinking method to increase the order of polynomial filters. One can also consider the trigonometric polynomial to avoid the potential numerical problem.

**Linear Filters**

Linear filters further simplify the polynomial filters to yield high scalability and inductive learning ability. But they lost the capability to approximate arbitrary graph filters. In general, linear filters can only scale the graph spectrum, but not change the response patterns.

GCN (Kipf and Welling, 2017) is one of the most important works in the field of GNNs, which is the first-order approximation of ChebNet and can be seen as a linear filter. GCN takes the first two terms of ChebNet, _i.e._, \(\theta_{0}\mathbf{I}\) and \(\theta_{1}(\mathbf{L}-\mathbf{I})\), and assumes that \(\theta=\theta_{0}=-\theta_{1}\). Then it has a linear filter:

\[\mathbf{UGU}^{\top}=\theta(2\mathbf{I}-\mathbf{L})=\theta(\mathbf{I}+ \mathbf{A})\approx\theta\tilde{\mathbf{A}}, \tag{11}\]

where \(\tilde{\mathbf{A}}\) is the renormalization trick of adjacency matrix. Here we can see that the graph filter \(\mathbf{G}\) is linear with the input graph structure \(\tilde{\mathbf{A}}\). This explains why GCN has the over-smoothing phenomenon (Li _et al._, 2018): The parameters of neural networks can only scale the graph spectrum of \(\tilde{\mathbf{A}}\) but do not change its inherent low-pass pattern (Wu _et al._, 2019). By continuously multiplying the graph filter, only the first trivial eigenspace \(\mathbf{u}_{1}=[\frac{1}{\sqrt{N}},\cdots,\frac{1}{\sqrt{N}}]^{\top}\) can preserve the amplitude 1 and others 0.

Although the linear property restricts the expressive power of GCN, it still inspires a series of subsequent works. PPNP (Klicpera _et al._, 2019) combines GCN with PageRank and adds a residual connection to the graph convolutional layers:

\[\mathbf{UGU}^{\top}=\theta((1-\alpha)\tilde{\mathbf{A}}+\alpha\mathbf{I}), \tag{12}\]

where \(\alpha\) is a hyperparameter to balance the low-pass filter \(\tilde{\mathbf{A}}\) and all-pass filter \(\mathbf{I}\). Compared with GCN, PPNP has a hyperparameter to control the response function of the graph filter. But PPNP still cannot approximate arbitrary filters. GNN-LF/HF (Zhu _et al._, 2021) further unifies all linear filters into an optimizing framework. It decomposes the design of graph convolution into two objectives: fitting and regularization. By setting different hyperparameters, the fitting term can make the model approximate different filters, _e.g._, low- and high-pass. However, such methods can only approximate predefined filters and cannot learn from data, which requires a lot of expert knowledge.

FAGCN (Bo _et al._, 2021) provides a solution to adaptively learn low- or high-pass filters from data but still preserves the linear property. The key idea is to use neural networks to combine some predefined graph filters.

\[\mathbf{UGU}^{\top}=\theta(\mathbf{I}-\mathbf{M}\odot\mathbf{A}), \tag{13}\]

where \(\mathbf{M}\in\mathbb{R}^{N\times N}\) is a sparse edge weight matrix learned by neural networks. When the elements in \(\mathbf{M}\) is larger than 0, FAGCN can act as a low-pass filter and otherwise a high-pass filter. There are also some similar methods. For example, AdaGNN (Dong _et al._, 2021), AKGNN (Ju _et al._, 2022) and ADA-UGNN (Ma _et al._, 2021). Through parameterizing the hyperparameters with neural networks, the linear filters can adaptively approximate different filters. But the expressive power is still not as good as the aforementioned two methods.

**Summary.** Generally, the linear filters are equal to the basic spatial GNNs. Taking GCN as an example, if we assign each feature an independent filter, then the spectral filter becomes:

\[\mathbf{h}_{j}^{(l+1)} =\sigma(\mathbf{U}\sum_{i=1}^{d_{in}}\theta_{ij}\tilde{\mathbf{A} }\mathbf{U}^{\top}\mathbf{h}_{i}^{(l)})=\sigma(\sum_{i=1}^{d_{in}}\theta_{ij} \mathbf{U}\tilde{\mathbf{A}}\mathbf{U}^{\top}\mathbf{h}_{i}^{(l)})\] \[=\sigma(\sum_{i=1}^{d_{in}}\theta_{ij}\tilde{\mathbf{A}}\mathbf{ h}_{i}^{(l)})=\sigma(\tilde{\mathbf{A}}\mathbf{h}^{(l)}\mathbf{\theta}_{j}), \tag{14}\]
where \(\mathbf{\theta}_{j}\in\mathbf{R}^{d_{in}\times 1}\) is the parameters of neural networks. Therefore, linear filters have good scalability, but the fitting ability is heavily restricted. Linear filters cannot directly capture global or high-order information because the predefined filters are usually designed for first-order information. It is a promising direction to combine linear filters with complicated filters to learn representations effectively and efficiently.

### Eigenvector-based Spectral GNNs

A graph signal can be decomposed into the weighted sum of bases, where the weights indicate the energy in different frequencies. Therefore, it is important to choose a set of bases that well reflect the distribution of graph signals. Eigenvector-based spectral GNNs aim to design bases to effectively represent the graph signals in the spectral domain. In this section, we introduce two important bases: Graph Wavelet and Hermitian Laplacian. In addition, we also mention the basis encoder, which takes the eigenvectors as input and generates positional encodings for nodes.

**Wavelet Basis**

The Fourier bases, _i.e_., eigenvectors, are the most commonly used basis function. However, there are two shortcomings of eigenvectors: First, eigenvectors are dense in space. If graph signals only exist in a subgraph, _e.g_., diffusion signals, GFT needs to use a large number of bases to approximate such signals. Second, eigenvectors are non-localized, which cannot reflect the spatial location of the graph signals. To represent graph signals more efficiently, graph wavelets [11] are proposed, which are sparse and localized in the vertex domain. The graph wavelets \(\mathbf{\psi}_{s}\) are defined as:

\[\mathbf{\psi}_{s}=[\mathbf{\psi}_{s1},\cdots,\mathbf{\psi}_{sN}]=\mathbf{U}\text{diag}(e^ {s\lambda_{1}},\cdots,e^{s\lambda_{N}})\mathbf{U}^{\top}, \tag{15}\]

where \(\mathbf{\psi}_{si}\) is a basis that represents a diffusion signal centered on node \(i\) with the scaling parameter \(s\). Generally, a smaller value \(s\) indicates a shorter diffusion, _i.e_., covering fewer neighbors. By using different scaling parameters, graph wavelets can construct a multi-scale representation of the graph signals. Graph wavelets not only reflect the energy distribution in the spectral domain but also indicate its location distribution in the vertex domain, which is a powerful spatial-spectral analysis tool. There are many spectral GNNs based on graph wavelets.

GWNN [20] proposes a non-parametric spectral GNNs based on the graph wavelet transform (GWT):

\[\mathbf{h}_{j}^{(l+1)}=\sigma(\mathbf{\psi}_{s}\sum_{i=1}^{d_{in}}\mathbf{G}_{ij}^ {(l)}\mathbf{\psi}_{s}^{-1}\mathbf{h}_{i}^{(l)})\quad(j=1\cdots d_{out}), \tag{16}\]

where \(\mathbf{\psi}_{s}^{-1}=\mathbf{U}\text{diag}(e^{-s\lambda_{1}},\cdots,e^{-s\lambda _{N}})\mathbf{U}^{\top}\). Since the calculation of \(\mathbf{\psi}_{s}\) and \(\mathbf{\psi}_{s}^{-1}\) are time-consuming, Hammond _et al._[11] uses Chebyshev polynomials to efficiently approximate the wavelet bases. Zheng _et al._[20] design orthogonal graph wavelets to provide a multi-resolution framework for graph signal analysis.

**Conjugate Basis**

A basic assumption for spectral GNNs is that the underlying graph structures are symmetric. The EVD of asymmetric graphs will generate complex eigenvalues and eigenvectors. However, existing graph filters do not support complex operations. Therefore, it is important to find a basis that can encode the direction information of edges and have real eigenvalues for graph filtering. Hermitian Laplacian is a generalization of graph Laplacian, which contains the real part and imaginary parts. The real part is a symmetric matrix, which represents the graph structures. The imaginary part is conjugate, which can be used to encode side information, _e.g_., edge direction. The EVD of Hermitian Laplacian has real eigenvalues and complex eigenvectors, which we call conjugate basis. Therefore, it can be directly incorporated with existing graph filters.

MagNet [14] uses the Hermitian Laplacian to design a spectral GNN for directed graphs. The normalized Hermitian Laplacian of a directed graph is defined as:

\[\mathbb{L}=\mathbf{I}-\mathbb{D}^{-\frac{1}{2}}\mathbb{A}\mathbb{D}^{-\frac{1}{ 2}}\odot\exp\left(\mathrm{i}\mathbf{\Theta}^{(q)}\right)\quad\mathrm{i}\cdot \mathrm{i}=-1, \tag{17}\]

where \(\mathbb{A}=\frac{1}{2}(\mathbf{A}+\mathbf{A}^{\top})\), \(\mathbb{D}\) is the degree matrix of \(\mathbb{A}\) and \(\mathbf{\Theta}^{(q)}=2\pi q(\mathbf{A}-\mathbf{A}^{\top})\) is the phase matrix, where the incoming and outgoing edges are set to 1 and -1, respectively. Therefore, they will have opposite values in the complex plane. The hyperparameter \(q\) represents the importance of structural information and direction information. A smaller value of \(q\) indicates that the structural information is more important. Based on the Hermitian Laplacian, MagNet defines a linear filter similar to GCN in the directed graph:

\[\mathbf{h}_{j}^{(l+1)}=\theta_{ij}\tilde{\mathbb{A}}\odot\exp\left(\mathrm{i} \mathbf{\Theta}^{(q)}\right)\mathbf{h}_{i}^{(l)}, \tag{18}\]

where \(\tilde{\mathbb{A}}\) is the renormalization of \(\mathbb{A}\). MagNet sheds light on how to combine graph filters with the side information of graphs. It is promising to extend graph filters to other types of graph data by using Hermitian Laplacian. For example, heterogeneous graphs that use different relations as the side information.

**Basis Encoder**

In addition to representing the energy of graph signals, the eigenvectors also reflect the global positions of nodes, which can be used as positional encodings to improve the expressive power of spatial GNNs and break the limitation of 1-WL test [15]. There are many attempts to learn data representation from the eigenvectors. For example, spectral clustering [21] aims to use the top-\(k\) eigenvectors to represent the manifold of data. Besides, graph embedding, which aims to embed nodes into a low-dimension space, can be seen as factorizing different graph matrices [22], where the eigenvectors are used as the node embeddings. However, such methods are two-stage approaches that cannot update representations through back-propagation.

Basis encoders aim to learn the position representations of nodes from the eigenvectors in an end-to-end manner. In addition, they also consider the sign and basis ambiguity of eigenvectors [13, 14] and design models to learn invariant representations. Although the basic encoders are not necessarily GNNs, there is a close relationship between them. Spectral GNNs aim to find the important eigenspaces, _i.e_. \(\mathbf{u}\mathbf{u}^{\top}\), and basis encoders are designed to find
the important eigenvectors that can well describe the node positions.

SAN [14] proposes to use Transformer to construct a permutation-equivariant basis encoder. Through the self-attention mechanism, SAN can learn the importance of different eigenvectors, which has a similar idea to spectral GNNs. SignNet [12] finds that the eigenspaces are invariant to the sign flips and basis symmetries of eigenvectors and uses invariant and equivariant GNNs to learn positional representations from the eigenspaces, which can be seen as a generalization of spectral GNNs. PEG [20] uses the Euclidean distance between eigenvectors to reweight the adjacency matrix, thus avoiding the ambiguity of eigenvectors. PEG encodes the positional information in edges and performs well on the link prediction task.

SummaryCompared with eigenvalues-based spectral GNNs, eigenvector-based methods are under-explored, possibly due to theoretical and computational limitations. A future direction is to combine the basis information with other tasks. For example, GCN-SVD [15] shows that the low-frequency bases are robust to graph perturbation.

### Theory

In this section, we mainly introduce the theoretical progress on spectral GNNs, including expressive power, robustness, and transferability, which may give a deeper understanding of spectral GNNs.

Expressive powerThe expressive power of MPNNs is proven to be restricted by 1-WL test [23]. But the expressive power of spectral GNNs remains under-determined. balcilar2021efficient proves that spectral graph convolution with nonlinear filtering can break the limit of the 1-WL test and is as powerful as the 3-WL model. wang2022efficient make a further attempt. They show that spectral filters are universal approximators when satisfying two conditions: no multiple eigenvalues and no missing frequency components. Since existing graph filters will map the multiple eigenvalues into the same scalar, this conclusion gives a future direction for designing spectral GNNs.

RobustnessIt has been proved that GCNs will have different predictions under structural perturbation [24], implying that spatial convolutions are vulnerable to attack. GCN-LFR [1] is the first to verify the vulnerability of graph filters through matrix perturbation theory. Their theoretical analysis shows that graph filters are more robust against structural perturbations when the eigenvalues fall into a specific interval. lei2022efficient find that even-order graph filters are more robust than full-order methods and propose EvenNet, which is a graph filter with only even-order terms and performs well on both homophilic and heterophilic datasets.

TransferabilityTransferabilityTransferability

Transferability reflects the generalization ability of graph filters across different graphs. Intuitively, if two graphs have similar spectrums, the graph filters should have representations on both graphs. levie2021efficient first proves that spectral filters are transferable on different graphs and can learn similar representations when there is a small perturbation between two graphs, which establishes the connections between transferability and robustness. kenlay2021efficient further proposes a stability bound to measure the stability and transferability of graph filters.

### Application

In this section, we review the latest applications and explain why they are suitable for spectral GNNs, including multivariate time-series forecasting, neuroscience, and computer vision.

Multivariate Time-series ForecastingMultivariate time-series forecasting task aims to predict multiple correlated time-series simultaneously, which needs to consider both intra-series and inter-series patterns. Learning a latent graph between different time-series can capture the inter-relations and significantly improve forecasting performance. stemGNN [1] uses Discrete Fourier Transform (DFT) and GFT to capture the intra- and inter-patterns in the spectral domain, respectively. TPGNN [13] further proposes a temporal polynomial filter to capture the dynamics between different time-series.

NeuroscienceNeuroscience studies the nervous system of human brains. Brain connectivity can be seen as a special brain graph, where nodes are different brain regions, and edges are their connections. bessadok2021efficient introduces how to apply GNNs for network neuroscience, and xu2019multilayer utilizes graph wavelets to construct a multi-scale analysis of brain networks. In general, neuroscience is a suitable application for spectral GNNs, as it does not require scalability and has a strong need for interpretability.

Computer VisionMany computer vision tasks can improve performance by introducing graph structures, such as detection, classification, recognition, etc. chen2022efficient provides a comprehensive summary of vision tasks involving GNNs, and we present two of them that make use of spectral GNNs.

Point clouds can be seen as special 3D graphs, where the nodes are points and edges are their nearest neighbors. It is natural to generalize the idea of graph filters to 3D graphs. hu2020efficient introduces the recent development of GSP in geometric data, and liu2022efficient reviews the attacks on point clouds from the perspective of the graph spectral domain. Point cloud tasks, such as segmentation, often need to learn the global structures of nodes. Compared to the layer-by-layer aggregation mechanism of spatial methods, spectral GNNs are better at learning global information through GFT.

Skeleton-based motion prediction is another task aimed at predicting human motions from sensor data, where sensors can be considered as the nodes in a graph, and edges are their spatial connections. li2021efficient proposes a graph scattering network to project the sensor signals into different graph spectrum bands to predict human motions. Through
decomposing the sensor signals, spectral GNNs can capture the potential relationship between human motions and basis functions and use it for classification.

### Benchmark

We benchmark existing spectral GNNs on six graph datasets, three of which (Cora, Citeseer, Pubmed) are homophilic graphs, while the other three (Chameleon, Squirrel, Actor) are heterophilic graphs. We implement these spectral GNNs based on our GAMMA-Spec 1 framework, which provides the implementation and visualization of different graph filters. We follow the setting of He _et al._ [2021] and randomly select 60% data for training, 20% for validation and 20% for testing. The results are shown in Table 1.

Footnote 1: [https://github.com/liuyang-tian/Spectral-GNN-Library](https://github.com/liuyang-tian/Spectral-GNN-Library)

We can see that the advanced filters outperform other filters in four datasets, confirming that the advanced filters have better approximation ability. However, due to the high complexity, there is less research on this type of filter. Polynomial filters take the runner-up spot but are more studied than advanced filters, probably because polynomial filters strike a good balance between effectiveness and efficiency. The performance of linear filters is worse than other filters. Due to the lack of nonlinear filtering, there is also less research on linear filters. Therefore, it is an important direction to empower linear filters with adaptive filtering capability.

## 4 Conclusion and Future Directions

In this paper, we introduced the development of spectral GNNs from the perspective of model, theory, and application. Although some progress has been made, spectral GNNs still lag behind spatial GNNs. To facilitate the development of spectral GNNs, we briefly discuss some promising future directions.

**Information intersection**

As mentioned in the challenges, the spectral information of graphs is informative, such as eigenvalues, eigenvectors, Fourier coefficients, etc. Therefore, it is important to exploit the connections between different spectral information and fuse them to learn better representations. Besides, spectral GNNs should not be limited to supervised or semi-supervised learning. Applying the rich spectral information to unsupervised or self-supervised learning is also a promising direction. For example, Liu _et al._ [2022b] connects graph spectrum and graph data augmentation to improve the performance of graph contrastive learning.

**Learning from signal processing**

Signal processing on Euclidean data, _e.g._, time series and images, has a long history. While non-Euclidean signal processing is still an emerging field. Therefore, spectral GNNs can borrow ideas from traditional signal processing methods. For example, Kalman filtering, Bessel filtering, etc. In addition, the spectrum of the Euclidean data can be divided into amplitude spectrum and phase spectrum, representing the shape and location information, respectively. However, in spectral GNNs, most graph spectrums are amplitude spectrums, and the phase spectrums are largely ignored, which motivates the discovery of phase information in spectral GNNs.

**Broader data and applications**

One of the most important advantages of spatial GNN is the flexibility to adapt to different graph data. The message-passing mechanism can be easily extended to heterogeneous graphs and hypergraphs. However, the idea of signal processing is hard to generalize to other graph data, which hinders the development of spectral GNN to some extent. Therefore, an important future direction is to extend spectral GNNs to broader graph data and find suitable applications, _e.g._, biomedical and neuroscience.

\begin{table}
\begin{tabular}{c|c|c c c c c} \hline \hline  & \multicolumn{2}{c}{Cora} & Citeseer & Pubmed & Chameleon & Squirrel & Actor \\ \hline \multirow{4}{*}{Advanced} & SpectralCNN & 83.17\(\pm\)0.87 & 71.06\(\pm\)1.93 & 83.76\(\pm\)0.51 & 55.73\(\pm\)2.66 & 44.79\(\pm\)2.58 & 28.87\(\pm\)3.77 \\  & LanczosNet & 88.03\(\pm\)1.70 & 80.55\(\pm\)1.19 & **90.13\(\pm\)0.49** & 60.96\(\pm\)3.32 & 45.14\(\pm\)1.44 & 36.07\(\pm\)1.38 \\  & Specformer & 88.57\(\pm\)1.01 & **81.49\(\pm\)0.94** & - & **74.72\(\pm\)1.29** & **64.64\(\pm\)0.81** & 41.93\(\pm\)1.04 \\ \hline \multirow{9}{*}{Polynomial} & ChebNet & 86.37\(\pm\)1.71 & 78.65\(\pm\)1.55 & 88.00\(\pm\)0.74 & 66.94\(\pm\)1.59 & 53.15\(\pm\)1.97 & 37.06\(\pm\)2.41 \\  & ChebNetII & 88.08\(\pm\)1.17 & 78.46\(\pm\)1.56 & 88.10\(\pm\)0.63 & 71.26\(\pm\)1.28 & 61.92\(\pm\)1.37 & 41.68\(\pm\)1.04 \\  & GPRGNN & **89.61\(\pm\)1.80** & 80.85\(\pm\)1.29 & 90.09\(\pm\)1.15 & 65.27\(\pm\)2.73 & 46.46\(\pm\)2.01 & 39.16\(\pm\)1.39 \\  & BernNet & 87.21\(\pm\)1.13 & 79.33\(\pm\)1.59 & 89.00\(\pm\)0.63 & 68.53\(\pm\)3.05 & 51.74\(\pm\)2.37 & 40.72\(\pm\)1.17 \\  & JacobiConv & 89.05\(\pm\)1.17 & 80.44\(\pm\)0.95 & 89.51\(\pm\)0.80 & 74.07\(\pm\)1.63 & 57.42\(\pm\)1.94 & 40.82\(\pm\)1.72 \\  & Spec-GN & 88.18\(\pm\)0.85 & 80.07\(\pm\)1.48 & 88.51\(\pm\)0.35 & 65.34\(\pm\)3.20 & 50.96\(\pm\)2.19 & 40.49\(\pm\)1.00 \\  & DSGC & 88.24\(\pm\)1.53 & 79.75\(\pm\)1.98 & 87.72\(\pm\)0.69 & 51.73\(\pm\)1.95 & 35.68\(\pm\)1.22 & **42.63\(\pm\)1.32** \\  & ARMA & 87.70\(\pm\)1.25 & 79.02\(\pm\)1.31 & 88.96\(\pm\)0.51 & 60.96\(\pm\)5.66 & 51.10\(\pm\)0.92 & 38.10\(\pm\)2.19 \\  & CayleyNet & 86.55\(\pm\)1.61 & 78.40\(\pm\)1.32 & - & 68.21\(\pm\)1.85 & 51.65\(\pm\)1.98 & 42.26\(\pm\)1.42 \\ \hline \multirow{4}{*}{Linear} & GCN & 87.23\(\pm\)0.82 & 79.82\(\pm\)0.74 & 86.43\(\pm\)0.57 & 59.73\(\pm\)1.75 & 46.55\(\pm\)1.02 & 34.01\(\pm\)1.57 \\  & FAGCN & 88.03\(\pm\)1.30 & 80.04\(\pm\)0.78 & 89.22\(\pm\)0.59 & 66.52\(\pm\)2.17 & 50.40\(\pm\)1.73 & 39.69\(\pm\)1.57 \\ \cline{1-1}  & AdaGNN & 87.32\(\pm\)1.10 & 78.69\(\pm\)1.50 & 88.72\(\pm\)0.47 & 60.85\(\pm\)2.44 & 49.88\(\pm\)1.85 & 37.16\(\pm\)0.93 \\ \cline{1-1}  & AKGNN & 88.28\(\pm\)1.52 & 81.06\(\pm\)0.84 & 88.96\(\pm\)0.50 & 68.53\(\pm\)0.69 & 46.82\(\pm\)0.75 & 35.70\(\pm\)1.20 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Node classification on real-world datasets, where bold and underline indicate the best and runner-up, respectively.