A Survey on Spectral Graph Neural Networks

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 (Bruna et al., 2014) is the first advanced graph filter, which treats the graph filter as the parameters of neural networks and directly optimizes it by gradient descent:

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 (Wang et al., 2022).

LanczosNet (Liao et al., 2019) 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}\bm{\Lambda}^{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:

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:

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. (2016) and continued in subsequent work.

Specformer (Bo et al., 2023) 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 (Vaswani et al., 2017) as a set-to-set graph filter to learn the set relationships between eigenvalues:

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.

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:

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 (Defferrard et al., 2016) 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:

where $\tilde{\mathbf{\Lambda}}=\frac{2\mathbf{\Lambda}}{\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 (Epperson, 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, GPR-GNN (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., 2021b) 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:

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$.

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:

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:

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.

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.

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 (Hammond et al., 2011) are proposed, which are sparse and localized in the vertex domain. The graph wavelets $\bm{\psi}_{s}$ are defined as:

where $\bm{\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 (Xu et al., 2019a) proposes a non-parametric spectral GNNs based on the graph wavelet transform (GWT):

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

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 (Zhang et al., 2021) uses the Hermitian Laplacian to design a spectral GNN for directed graphs. The normalized Hermitian Laplacian of a directed graph is defined as:

where $\mathbb{A}=\frac{1}{2}(\mathbf{A}+\mathbf{A}^{\top})$, $\mathbb{D}$ is the degree matrix of $\mathbb{A}$ and $\bm{\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 hyparparameter $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:

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.

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 (Dwivedi et al., 2022). There are many attempts to learn data representation from the eigenvectors. For example, spectral clustering (Ng et al., 2001) 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 (Qiu et al., 2018), 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 (Lim et al., 2022; Wang et al., 2022) 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 (Kreuzer et al., 2021) 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 (Lim et al., 2022) 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 (Wang et al., 2022) 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.

The expressive power of MPNNs is proven to be restricted by 1-WL test (Xu et al., 2019b). But the expressive power of spectral GNNs remains under-determined. Balcilar et al. (2021) 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. Wang and Zhang (2022) 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.

It has been proved that GCNs will have different predictions under structural perturbation (Zügner et al., 2018), implying that spatial convolutions are vulnerable to attack. GCN-LFR (Chang et al., 2021) 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. Lei et al. (2022) 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.

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. Levie et al. (2021) 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. Kenlay et al. (2021) further proposes a stability bound to measure the stability and transferability of graph filters.

Multivariate 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 (Cao et al., 2020) uses Discrete Fourier Transform (DFT) and GFT to capture the intra- and inter-patterns in the spectral domain, respectively. TPGNN (Liu et al., 2022c) further proposes a temporal polynomial filter to capture the dynamics between different time-series.

Neuroscience 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. Bessadok et al. (2021) introduces how to apply GNNs for network neuroscience, and Xu et al. (2019c) 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.

Many computer vision tasks can improve performance by introducing graph structures, such as detection, classification, recognition, etc. Chen et al. (2022) 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. Hu et al. (2020) introduces the recent development of GSP in geometric data, and Liu et al. (2022a) 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. Li et al. (2021a) 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.