# Benchmarking Spectral Graph Neural Networks:
A Comprehensive Study on Effectiveness and Efficiency

Ningyi Liao1, Haoyu Liu1, Zulun Zhu1, Siqiang Luo1, Laks V.S. Lakshmanan2
1 Nanyang Technological University
2 The University of British Columbia
<EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

With the recent advancements in graph neural networks (GNNs), spectral GNNs
have received increasing popularity by virtue of their specialty in capturing
graph signals in the frequency domain, demonstrating promising capability in
specific tasks. However, few systematic studies have been conducted to assess
their spectral characteristics. This emerging family of models also varies in
terms of design and settings, leading to difficulties in comparing their
performance and deciding on the suitable model for specific scenarios,
especially for large-scale tasks. In this work, we extensively benchmark
spectral GNNs with a focus on the frequency perspective. We analyze and
categorize over 30 GNNs with 27 corresponding filters. Then, we implement
these spectral models within a unified framework with dedicated graph
computations and efficient training schemes. Thorough experiments are
conducted on the spectral models with inclusive metrics on effectiveness and
efficiency, offering practical guidelines on evaluating and selecting spectral
GNNs with desirable performance. Our implementation enables application on
larger graphs with comparable performance and less overhead, which is
available at: https://github.com/gdmnl/Spectral-GNN-Benchmark.

##  1 Introduction

Graph neural networks (GNNs) have emerged as powerful tools in a wide range of
graph understanding tasks. Spectral GNNs denote a specialized set of GNN
designs that are based on spectral graph theory and apply graph signal filters
in the spectral domain [1, 2, 3, 4]. Benefiting from diverse and adaptive
spectral expressions, these models have garnered exceptional utility under
both homophily and heterophily [5, 6], and in real-world scenarios such as
multivariate time-series forecasting [7, 8] and point cloud processing [9,
10]. Particularly, spectral operations are feasible with a denser parameter
space and less computational overhead while preserving expressiveness and
efficacy, alleviating the conventional bottleneck of GNNs and rendering these
models ideal for large-scale tasks. Figure 1 illustrates the basic concept of
fitting spectral filters to different GNN training pipelines.

Figure 1: The spectral filter remains the same between (a) full-batch
learning, which is the common setting of GNN training, and (b) mini-batch
learning, which is specialized for spectral GNNs. The invariability enables
unified spectral filter implementation and evaluation across different model
architectures and learning schemes possessing varying efficiency and
scalability performance.

#### Existing Evaluations of Spectral GNNs.

The spectral domain of graphs has long been incorporated into graph learning
tasks [11, 12]. We present a detailed review of related GNN surveys and
benchmarks in Appendix C. Although a handful of classic spectral models have
been included in previous benchmarks [13, 14], most of them lack specificity
in considering and assessing characteristics from a spectral perspective. With
the bloom of spectral GNNs in the last few years, we find that existing
evaluations are particularly limited compared to recent research progress in
various aspects.:

  * •

Advance in Spectral Interpretation: Latest studies have revealed the general
relationship between spectral and spatial operations, where many classic and
popular GNN designs have been shown to have corresponding spectral formations
[15, 16, 17]. This new equivalence calls for interpreting and evaluating these
models in the spectral domain.

  * •

Varied Implementations and Evaluations: Existing spectral GNNs vary greatly in
non-spectral designs such as data processing, graph computation, and network
architecture. These ancillary properties are less relevant to their spectral
expressiveness. However, their diverse implementations affect the model
performance and complicate the fair comparison of different spectral filters.

  * •

Limited Efficient Computation: As depicted in Figure 1, spectral GNNs are
known for achieving favorable expressiveness with efficient and scalable
designs. A line of recent works proposes dedicated algorithms for spectral
computation [18, 19, 20, 21]. While other spectral filters are conceptually
applicable to such enhancements, they are never implemented nor evaluated.

#### Our Contribution.

In this study, we are hence motivated to benchmark GNNs specifically in the
spectral domain, presenting theoretical and empirical view of spectral filters
within a unified framework. The scope of our evaluation covers a wide range of
GNNs with spectral interpretations. By deriving and classifying proposed
filters, we show that the majority of existing spectral models can be divided
into three categories, exhibiting distinct capabilities and performance.

We offer dedicated implementation of these filters under the same framework,
integrated with advanced data processing, network architecture, and scalable
computation techniques. Based on our taxonomy and implementation, we conduct
experimental comparison on performance including expressiveness, efficacy,
efficiency, and scalability. Compared to previous GNN evaluations, we
highlight the following specialties of this work:

  * •

Unified Framework: We offer an open-source, plug-and-play collection for
spectral models and filters. The framework realizes unified and efficient
implementations covering a variety of spectral GNN designs. Reproducible
pipelines are included for training and evaluating the provided models.

  * •

Spectral-oriented Design: Our spectral framework is designed in a spectral-
oriented manner independent to spatial operations. Such implementation ensures
that most filters are easily adaptable to a wide range of model-level options
on transformation, architecture, and learning schemes. In this way, spectral
GNNs can be constructed on-demand from various choices of modules and
configurations offering different precision, speed, and memory performances.

  * •

Comprehensive and Fair Evaluation: We provide extensive study on the
effectiveness and efficiency of spectral filters across various model
architectures and learning schemes under our framework. Particularly, most
filters are applicable to graphs beyond million-scale, which has never been
achieved before. We analyze the spectral properties of the filters and
conclude practical guidelines for designing and utilizing spectral models as
well as open questions for future research.

The key takeaways of our benchmark study characterizing effectiveness and
efficiency of diverse types of spectral GNNs are summarized as follows:

  * •

All three types of filters are able to achieve satisfactory performance on
homophilous graphs, while variable filters and filter bank models excel under
heterophily. As there is no optimal single solution for all cases,
comprehensive consideration of model capability and expense is required when
choosing a suitable filter for learning distinct graph signals.

  * •

Filters with fixed parameters are the most efficient design for both full-
batch and mini-batch training schemes. Variable feature transformation and
additional graph propagation increase memory overhead and model learning time,
respectively. The trade-off between efficacy and efficiency is critical for
model applications, especially on large graphs.

  * •

Spectral models exhibit dissimilar effectiveness on nodes of high and low
degrees under different graph conditions, which extends the presumption in
previous studies. The bias also affects overall model prediction and may
motivate dedicated filter designs to further enhance accuracy.

##  2 Formulations for Spectral GNN Paradigms

In this section, we first provide the general notations of spectral GNNs
highlighting the polynomial approximation for the consideration of its
predominant utility in real-world graph learning. Based on the formulation, we
categorize polynomial filters into three types according to their
parameterization schemes, which are summarized in Table 1 and introduced in
respective subsections. A detailed list of filters and models is presented in
Table 5 with analysis in Appendix B.

#### Graph Notation.

An undirected graph is denoted as
$\mathcal{G}=\langle\mathcal{V},\mathcal{E}\rangle$ with $n=|\mathcal{V}|$
nodes and $m=|\mathcal{E}|$ edges. The adjacency matrix without and with self-
loops are $\boldsymbol{\mathbf{A}}$ and
$\bar{\boldsymbol{\mathbf{A}}}=\boldsymbol{\mathbf{A}}+\boldsymbol{\mathbf{I}}$,
respectively. The normalized adjacency matrix is
$\tilde{\boldsymbol{\mathbf{A}}}=\bar{\boldsymbol{\mathbf{D}}}^{\rho-1}\bar{\boldsymbol{\mathbf{A}}}\bar{\boldsymbol{\mathbf{D}}}^{-\rho}$,
where $\bar{\boldsymbol{\mathbf{D}}}$ is the self-looped diagonal degree
matrix and $\rho\in[0,1]$ is the normalization coefficient [18, 22]. The
Laplacian matrix is defined as
$\boldsymbol{\mathbf{L}}=\boldsymbol{\mathbf{D}}-\boldsymbol{\mathbf{A}}$,
while its normalized counterpart is
$\tilde{\boldsymbol{\mathbf{L}}}=\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{A}}}$.
The attributed graph is associated with a node attribute matrix
$\boldsymbol{\mathbf{X}}\in\mathbb{R}^{n\times F}$, carrying an
$F$-dimensional attribute vector for each node. Summary of primary symbols and
notations used in the paper can be found in Table 4.

#### Spatial Graph Convolution.

The spatial interpretation understands GNN message-passing procedure as two
stages, namely propagation and transformation. Propagation describes the
process of applying graph matrix to the node representation
$\boldsymbol{\mathbf{H}}$ as
$\boldsymbol{\mathbf{P}}=f(\tilde{\boldsymbol{\mathbf{A}}})\cdot\boldsymbol{\mathbf{H}}$,
inside which the aggregation operator $f:\mathbb{R}^{n\times
n}\rightarrow\mathbb{R}^{n\times n}$ characterizes the process of aggregating
graph information. The other stage of transformation
$\varphi:\mathbb{R}^{n\times F}\rightarrow\mathbb{R}^{n\times F}$ updates the
representation with learnable weights.

From the view of network architecture, iterative GNNs incorporate the two
stages in an alternative fashion:
$\boldsymbol{\mathbf{H}}^{(j+1)}=\varphi(f(\tilde{\boldsymbol{\mathbf{A}}})\cdot\boldsymbol{\mathbf{H}}^{(j)})$
and $\boldsymbol{\mathbf{H}}^{(0)}=\boldsymbol{\mathbf{X}}$. Applying such
spatial convolution of $J$ iterations leads to a receptive field of $J$ hops
on the graph. In contrast, decoupled models possess separated stages and can
be formulated by
$\boldsymbol{\mathbf{H}}=\varphi_{1}(f(\tilde{\boldsymbol{\mathbf{A}}})\cdot\varphi_{0}(\boldsymbol{\mathbf{X}}))$,
where $\varphi_{0},\varphi_{1}$ are pre- and post-transformations performed by
learnable weights, respectively.

#### Spectral Graph Convolution.

Graph spectral theory looks into the the eigen-decomposition of Laplacian
$\tilde{\boldsymbol{\mathbf{L}}}=\boldsymbol{\mathbf{U}}\boldsymbol{\mathbf{\Lambda}}\boldsymbol{\mathbf{U}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$,
where graph spectrum
$\boldsymbol{\mathbf{\Lambda}}=\operatorname{diag}(\lambda_{1},\cdots,\lambda_{n})$
is the diagonal matrix of eigenvalues
$0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}\leq 2$, and
$\boldsymbol{\mathbf{U}}$ is the matrix consisting of eigenvectors. For
simplicity, here we present by considering the $F=1$ attribute vector
$\boldsymbol{\mathbf{x}}$ as the input graph signal. GNNs adopting spectral
convolution can be generally expressed as:

$\hat{g}\ast\boldsymbol{\mathbf{x}}=\boldsymbol{\mathbf{U}}\hat{g}(\boldsymbol{\mathbf{\Lambda}})\boldsymbol{\mathbf{U}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\boldsymbol{\mathbf{x}}=\sum_{i=0}^{n}\hat{g}(\lambda_{i})\boldsymbol{\mathbf{u}}_{i}\boldsymbol{\mathbf{u}}_{i}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\boldsymbol{\mathbf{x}},\quad\hat{g}(\boldsymbol{\mathbf{\Lambda}})=\operatorname{diag}\big{(}\hat{g}(\lambda_{1}),\cdots,\hat{g}(\lambda_{n})\big{)},$
(1)

where $\hat{g}:[0,2]\rightarrow\mathbb{R}$ is the frequency response, i.e.,
spectral filter, and $\hat{g}(\boldsymbol{\mathbf{\Lambda}})$ denotes the
diagonal matrix when applied to the graph spectrum. Eq. 1 can be understood by
three consecutive stages: the Fourier transform upon the input signal
$\boldsymbol{\mathbf{y}}_{1}=\boldsymbol{\mathbf{U}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\boldsymbol{\mathbf{x}}$,
the modulation based on graph information
$\boldsymbol{\mathbf{y}}_{2}=\hat{g}(\boldsymbol{\mathbf{\Lambda}})\boldsymbol{\mathbf{y}}_{1}$,
and lastly the inverse Fourier transform to the output
$\boldsymbol{\mathbf{x}}^{\star}=\boldsymbol{\mathbf{U}}\boldsymbol{\mathbf{y}}_{2}$.

In practice, directly acquiring eigen-decomposition is prohibitive for graph-
scale matrices. Hence, it is common to utilize reduction in the form of
$K$-order polynomial approximation with regard to
$\tilde{\boldsymbol{\mathbf{L}}}$ as an approximate filter
$g(\tilde{\boldsymbol{\mathbf{L}}})$. Such polynomial estimation is
satisfactory for arbitrary smooth signals, while more complicated filters such
as rational functions are required under signal discontinuity [23, 24].
Nonetheless, computing graph-scale matrix inverse for rational filters is
impractical, which also leads to polynomial reduction in realistic
implementations as elaborated in Appendix B.

#### Relation between spatial and spectral convolutions.

We examine the general case where the $K$-order filter
$g(\tilde{\boldsymbol{\mathbf{L}}})$ is derived from an arbitrary polynomial
basis $T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$. Each term is parameterized
by $\theta_{k}$, which can either be a scalar or a matrix. Now the spectral
convolution Eq. 1 is approximated by the polynomial filter with respect to
basis $T(\tilde{\boldsymbol{\mathbf{L}}})$:

$\hat{g}\ast\boldsymbol{\mathbf{x}}\approx
g(\tilde{\boldsymbol{\mathbf{L}}})\cdot\boldsymbol{\mathbf{x}},\quad
g(\tilde{\boldsymbol{\mathbf{L}}})=\sum_{k=0}^{K}\theta_{k}\,T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}).$
(2)

A line of studies have revealed the relationship between spatial and spectral
convolutions in the context of GNN learning [2, 25, 16, 17]. Without loss of
generality, the spectral filter defined in Eq. 2 can be written as a
polynomial based on $\tilde{\boldsymbol{\mathbf{A}}}$ as
$\sum_{j=0}^{J}\xi_{j}\,\tilde{\boldsymbol{\mathbf{A}}}^{j}$ by expanding
$T(\tilde{\boldsymbol{\mathbf{L}}})$ and substituting
$\tilde{\boldsymbol{\mathbf{L}}}=\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{A}}}$,
which corresponds to the spatial convolution
$f(\tilde{\boldsymbol{\mathbf{A}}})$. In other words, the polynomial spectral
filters can be achieved by a series of recurrent graph propagations. When the
spatial and spectral orders align with each other, we have $J=K$. We further
discuss the architectural difference and respective complexity in Appendix A.

Table 1: Brief taxonomy of spectral GNNs analyzed in this paper. A complete list is in Table 5. Category |  Models
---|---
Fixed Filter |  GCN [2], SGC [26], gfNN [27], GZoom [28], S2GC [29], GLP [30], APPNP [31], GCNII [32], GDC [33], DGC [34], AGP [18], GRAND+ [19]
Variable Filter |  GIN [35], AKGNN [36], DAGNN [37], GPRGNN [25], ARMAGNN [38], ChebNet [4], ChebNetII [20], HornerGCN/ClenshawGCN [39], BernNet [40], LegendreNet [41], JacobiConv [5], FavardGNN/OptBasisGNN [42]
Filter Bank |  AdaGNN [43], FBGNN(I/II) [44], ACMGNN(I/II) [45], FAGCN [46], G2CN [47], GNN-LF/HF [48], FiGURe [49]

###  2.1 Fixed Filter GNN

For spectral GNNs with polynomial filters in Eq. 2, the basis
$T(\tilde{\boldsymbol{\mathbf{L}}})$ and the parameter $\theta$ jointly
determine the actual response to graph signals, and consequently dominate the
model performance [5]. It is pivotal for designing spectral GNNs to choose the
basis and parameter that are suitable for the task. We thereby categorize
polynomial spectral GNNs based on the acquisition schemes of bases and
parameters into three types, as respectively introduced in the following
subsections.

For the first type of spectral GNNs, the basis and parameters are both
constant during learning, resulting in fixed filters
$g(\tilde{\boldsymbol{\mathbf{L}}})$. In practice, these filters are usually
predefined simple schemes such as monomial or PPR summation. Below we give an
example of the classic APPNP model and its filter:

#### Personalized PageRank (PPR).

The APPNP [31] model is computed by iteratively applying graph propagation to
approximate the PPR calculation:
$f(\tilde{\boldsymbol{\mathbf{A}}})=\sum_{j=0}^{J}\alpha(1-\alpha)^{j}\tilde{\boldsymbol{\mathbf{A}}}^{j}$,
where $\alpha\in[0,1]$ denotes the decay coefficient. By selecting the basis
$T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$,
we name the spectral interpretation of APPNP as the PPR filter:

$g(\tilde{\boldsymbol{\mathbf{L}}})=\sum_{k=0}^{K}\alpha(1-\alpha)^{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{k}=\alpha(1-\alpha)^{k}.$

###  2.2 Variable Filter GNN

The second type of spectral GNN in our taxonomy also features a predetermined
basis $T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$ in Eq. 2. The series of
parameters $\theta_{k}$ is variable, usually acquired through gradient descent
during model training, leading to a variable filter
$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)$. Compared to spectral GNNs with
fixed filters, these models enjoy better capability, especially for fitting
high-frequency signals and capturing non-local graph information. The choice
of basis is the primary factor of the model performance on practical tasks [5,
42]. Below we present the representative Chebyshev filter.

#### Chebyshev.

ChebNet [4] utilizes the Chebyshev polynomial as basis. Each term
$T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$ in the polynomial is expressed in
the recursive form based on the computation results
$T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})$ and
$T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}})$ of previous hops. The Chebyshev
spectral filter can be computed by:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=2\tilde{\boldsymbol{\mathbf{L}}}T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}}),\,T^{(1)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}},\,T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{I}}.$

###  2.3 Filter Bank GNN

Some studies argue that a single filter is limited in leveraging complex graph
signals. Hence, spectral GNNs with filter bank arise as an advantageous
approach to provide abundant information for learning. These models typically
adopt multiple fixed or variable filters
$g_{q}(\tilde{\boldsymbol{\mathbf{L}}};\theta)$, each assigned with a filter
weight parameter $\gamma_{q}$. When the number of filters is $\mathit{Q}$,
their combination can be expressed as:

$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma,\theta)=\bigoplus_{q=1}^{\mathit{Q}}\gamma_{q}\cdot
g_{q}(\tilde{\boldsymbol{\mathbf{L}}};\theta),\quad
g_{q}(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{q,k}\,T_{q}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),$
(3)

where $\bigoplus$ denotes an arbitrary fusion function such as summation or
concatenation. By this means, the filter bank is able to cover different
channels, i.e., ranges of frequencies, to generate more comprehensive
embeddings of the graph. The filter parameter $\gamma$ can be either learned
separately or along with GNN training, depending on the specific model
implementation.

#### FiGURe.

FiGURe [49] is an exemplar filter bank GNN following exactly Eq. 3 with
summation fusion
$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma,\theta)=\sum_{q=1}^{\mathit{Q}}\gamma_{q}\cdot
g_{q}(\tilde{\boldsymbol{\mathbf{L}}};\theta)$, where filter-level parameters
$\gamma_{q}$ are learned to control the channel strength. Common variable
filters including monomial, Chebyshev, and Bernstein bases are utilized to
compose the filter bank.

##  3 Benchmark Design

#### Framework Implementation.

Based on the paradigm of spectral GNNs, we develop a unified framework
oriented towards the invariable spectral filters in particular. As specified
Section D.1, our implementation embraces the modular design principle,
offering plug-and-play filter modules that can be seamlessly integrated into
mainstream graph learning toolkits. It is also easily extendable to new filter
designs, as only the spectral formulation described in Section 2 needs to be
implemented. Then the filter enjoys a wide range of off-the-shelf blocks for
building a complete GNN.

#### Tasks and Metrics.

We focus on the semi-supervised learning for node-classification task on a
single graph, as it is the mainstream task for spectral GNNs. In particular,
this task features some of the largest datasets available for graph learning,
which is ideal for assessing the scalability of spectral models. We follow the
dataset settings for using efficacy metrics including accuracy and ROC AUC.
Efficiency with respect to both running speed and CPU/GPU memory usage is
measured for each learning stage, including training, inference, and
precomputation.

#### Datasets.

We comprehensively involve 22 representative datasets that are widely used in
spectral GNN evaluation. We mainly categorize them from two aspects. In
efficacy evaluations, we distinguish them into homophilous and heterophilous
datasets, since performance under heterophily is the design motivation of many
spectral filters. For experiments on efficiency, we separately investigate
small-, medium-, and large-scale graphs, and focus on larger ones where the
scalability issue of GNN models is more critical. Details of the benchmark
datasets can be found in Section D.2.

#### Learning Schemes.

Figure 1 indicates that the spectral filter is invariable across different
training schemes. Full-batch training loads all input data onto the GPU, which
is the de facto scheme for most GNN models. In contrast, mini-batch scheme
performs graph-related operations in a precomputation stage on CPU. Then, only
the intermediate representations are loaded onto the GPU in batches during
training, which prevents the memory footprint to be coupled with the graph
size and enjoys better scalability. Our novel implementation enables the
application of most filters to both schemes for fair and comprehensive
comparison.

#### Model Architectures and Hyperparameters.

We unify the non-spectral aspects of architectures for all models in our
evaluation, as an approach to provide comparable performance while enhancing
scalability to larger graphs. This includes the same transformation
operations, network depth and width, propagation hops, batch size, and
training epochs among all models in the main experiment. For other
hyperparameters not affecting efficiency, we perform individual
hyperparameters tuning for each model and dataset. More elaboration and
comparison among different architectural designs can be found in Section A.1,
while details of hyperparameter search are elaborated in Section D.3.

##  4 Experimental Results

In this section, we present primary observations on the performance comparison
among a total of 27 filters in three types. We also include our novel
observations on the efficacy bias concerning nodes of different degrees.
Complete experimental results are supplemented in Appendix E, while Appendix F
and Appendix G present additional explorations on the spectral and degree-
specific properties.

Table 2: Effectiveness results (%) and standard deviations of spectral filters
with full-batch training on selected datasets. Corresponding full results can
be found in Section E.1. For each dataset, highlighted results are filters
with average scores ranked first, second, and third.

Type Filter cora citeseer pubmed flickr squirrel chameleon actor roman Fixed
Identity 75.60±1.08 72.92±1.34 87.31±0.48 35.95±1.27 32.08±3.86 24.37±5.59
35.95±1.27 66.23±0.74 Linear 86.62±1.69 76.00±1.23 84.52±0.49 26.22±1.09
33.93±3.30 36.62±2.64 25.08±0.46 30.92±0.82 Impulse 86.21±1.53 74.79±1.03
83.02±0.74 26.48±0.83 34.21±3.71 35.23±2.20 27.00±1.30 27.90±0.59 Monomial
80.91±3.37 76.26±1.67 89.22±0.93 32.36±2.81 37.64±3.56 33.91±1.31 35.53±1.40
60.71±1.37 PPR 88.61±0.95 77.25±1.29 89.01±0.38 35.55±1.04 32.81±3.57
33.58±1.59 35.17±1.01 62.26±2.34 HK 88.06±0.99 77.10±0.89 89.11±0.63
37.33±1.48 32.64±4.06 34.28±1.50 37.53±1.25 65.60±0.92 Gaussian 86.37±2.12
76.92±1.16 89.06±0.76 35.62±0.87 33.54±4.02 37.18±1.82 36.44±1.25 66.47±0.94
Variable Linear 87.08±1.46 76.00±1.14 85.04±0.75 27.49±1.12 36.39±4.25
37.32±1.85 25.56±1.22 40.05±6.02 Monomial 87.56±1.00 76.72±1.25 88.18±0.76
35.42±1.89 39.33±2.90 40.65±1.67 32.13±3.47 64.76±0.66 Horner 86.14±1.82
76.72±1.61 89.59±0.45 36.74±0.88 37.92±3.41 34.57±1.35 37.65±1.10 61.52±0.88
Chebyshev 86.67±1.09 76.37±1.62 89.68±0.49 36.09±1.30 29.83±4.04 38.86±3.36
32.68±1.29 62.64±1.79 Clenshaw 80.33±3.72 74.14±1.48 86.35±2.12 31.16±2.42
31.40±3.08 34.26±1.41 27.03±5.10 68.03±1.51 ChebInterp 86.57±1.14 72.52±6.76
89.28±0.45 34.67±1.64 30.62±5.36 34.30±1.72 32.27±2.89 70.54±1.64 Bernstein
69.76±2.10 61.97±1.20 84.61±0.61 33.47±1.01 36.18±3.06 36.01±2.29 33.07±1.30
57.24±1.97 Legendre 86.56±1.12 77.15±0.86 89.83±0.40 35.70±1.40 35.51±6.95
35.52±1.50 35.63±1.01 57.04±5.64 Jacobi 81.40±3.05 74.67±1.15 89.56±0.38
35.30±1.51 31.69±3.93 36.87±1.60 36.10±1.47 63.25±1.66 Favard 82.74±4.59
74.16±2.94 89.44±0.43 30.89±2.58 30.56±4.02 37.05±2.49 36.37±1.13 62.19±1.41
OptBasis 82.20±2.22 73.59±2.04 88.16±1.92 33.76±2.12 33.76±3.81 33.76±1.91
34.26±1.09 64.46±1.60 Bank AdaGNN 85.91±0.81 74.96±0.98 89.97±0.50 36.28±1.44
35.00±4.35 35.32±1.57 36.49±1.21 66.13±1.35 FBGNNI 86.84±0.95 75.02±1.03
88.98±0.38 33.54±0.93 35.96±2.21 37.88±2.77 33.88±0.42 67.26±1.78 FBGNNII
87.91±1.56 72.21±1.92 88.87±0.53 34.21±0.67 37.53±5.29 33.87±1.47 35.30±0.75
72.61±1.68 ACMGNNI 87.25±1.27 76.00±1.20 88.84±0.66 33.38±1.27 33.37±3.50
30.68±3.18 33.59±1.20 64.19±1.65 ACMGNNII 81.89±3.59 74.60±0.60 89.07±0.38
34.14±0.60 34.05±3.70 27.43±3.33 33.49±1.31 73.40±1.30 FAGNN 86.60±1.43
75.95±1.52 85.06±0.42 24.89±1.38 31.29±5.22 35.61±2.35 27.82±1.21 28.20±1.39
G2CN 87.99±1.25 76.64±1.18 88.33±0.48 33.21±1.35 38.03±2.97 35.72±2.28
33.72±0.99 58.08±1.49 GNN-LF/HF 85.93±1.40 76.98±0.89 88.53±1.82 37.22±1.27
35.84±2.91 34.12±1.63 36.49±1.55 64.02±1.23 FiGURe 87.45±1.98 76.32±1.37
87.75±0.34 31.71±3.06 40.34±3.19 36.94±2.36 31.76±4.50 60.13±0.96

###  4.1 Overall Effectiveness and Efficiency Performance

Both effectiveness and efficiency are important for GNN applications in
practice. Our benchmark study aims to offer a comprehensive view considering
both factors. Tables 2 and 3, along with Tables 8, 9, 10 and 11, include the
results with regard to model efficacy and efficiency for full- and mini-batch
training. Observations are based on the complete evaluation on all datasets.

Obs.#1: Filter effectiveness varies under conditions of heterophily and is
relevant to different types of spectral designs.  Graph heterophily affects
the prediction performance of different filter types in distinctive manners,
and no filter achieves dominant efficacy across all scenarios. On homophilous
graphs, the accuracy gap among the three types is relatively marginal and
mostly within the error interval. With proper settings, even conventional
fixed filters can achieve superior performance, such as PPR and HK on cora and
citeseer. However, fixed filters typically fail under heterophily, while more
variable and complex designs retain higher performance, confirming their
utility in addressing the heterophily issue of canonical GNNs. In most cases,
full-batch and mini-batch training schemes do not diversify the model
efficacy.

We associate the difference in performance with the design of filter
parameterization. Models with fixed parameters are constrained to exploit low-
frequency graph signals, which is shown to be beneficial only under homophily.
In contrast, variable parameters offer a more flexible approach in
approximating a wider range of the graph spectrum. This allows for dynamically
learning filter weights based on the graph pattern, which is preferable for
capturing and leveraging useful information in the frequency domain to produce
a more comprehensive understanding of the graph.

Table 3: Time and memory efficiency of mini-batch training on large-scale
datasets. Corresponding full results can be found in Section E.2. “Pre.” and
“Train” respectively refer to precomputation and training time ($\mathrm{s}$),
while “Infer” refers to inference time ($\mathrm{m}\mathrm{s}$). “RAM” and
“GPU” respectively refer to peak RAM and GPU memory throughout the whole
learning process ($\mathrm{G}\mathrm{B}$). For each column, highlighted ones
are results ranked first, second, and third within the error interval.

Type Filter pokec products snap wiki Pre. Train Infer RAM GPU Pre. Train Infer
RAM GPU Pre. Train Infer RAM GPU Pre. Train Infer RAM GPU Fixed Linear 8.45
6.52 6.23 6.61 0.48 19.5 1.56 10.3 21.6 1.75 27.3 10.5 8.30 20.8 0.63 206.5
11.4 6.80 57.5 0.94 Impulse 5.36 7.30 6.37 6.58 0.48 15.0 1.57 10.3 21.6 1.74
21.0 10.7 8.37 18.1 0.63 164.1 10.9 7.40 57.5 0.94 Monomial 5.22 7.24 6.53
6.59 0.48 15.5 1.55 10.4 21.6 1.76 21.9 11.1 8.70 18.0 0.61 172.6 11.5 6.40
57.4 0.93 PPR 5.68 6.86 6.33 6.60 0.45 15.8 1.55 10.6 21.6 1.35 20.3 10.4 8.43
18.1 0.61 166.6 11.1 5.97 57.4 0.94 HK 5.21 7.08 6.30 6.62 0.48 14.8 1.54 11.1
21.6 1.49 18.8 11.1 8.37 18.1 0.63 165.6 10.4 5.80 57.4 0.94 Gaussian 5.24
6.78 7.67 6.61 0.48 14.7 1.51 9.77 21.6 1.63 19.7 11.3 9.97 18.1 0.63 156.1
10.2 6.10 57.5 0.94 Variable Linear 5.66 12.5 15.6 11.8 1.19 16.6 2.31 16.2
25.9 2.06 26.5 17.0 22.4 70.3 4.87 175.4 15.8 17.1 109.0 10.8 Monomial 6.04
15.3 14.6 11.8 1.19 15.3 2.63 15.4 25.9 1.92 25.0 18.1 17.0 70.3 4.87 166.9
16.6 11.8 109.1 10.8 Horner 6.21 13.4 17.8 11.8 1.19 20.9 3.40 25.5 25.9 2.18
23.5 17.7 24.7 70.3 4.87 203.7 18.3 23.8 109.1 10.8 Chebyshev 7.12 13.6 12.0
12.3 1.19 24.1 3.21 17.6 27.3 2.19 26.3 16.1 15.4 70.5 4.87 198.6 16.9 16.2
114.5 10.8 Clenshaw 7.74 14.2 19.1 11.8 1.19 28.4 3.14 23.9 25.9 2.33 35.1
21.9 31.6 70.3 4.87 234.1 18.8 23.8 109.1 10.8 ChebInterp 7.34 125.6 77.0 12.3
1.19 23.5 35.2 102.1 27.3 2.26 35.2 461.2 108.6 70.5 4.87 239.9 628.5 78.2
114.5 10.8 Bernstein 26.4 15.5 15.2 13.4 1.59 99.7 3.27 20.6 30.7 2.42 100.0
22.4 44.3 71.0 5.25 1268.6 18.2 14.5 125.5 11.7 Legendre 7.50 15.6 12.9 11.8
1.19 22.5 2.97 15.0 25.9 2.04 32.1 19.1 15.9 70.3 4.87 205.8 16.7 11.0 109.1
10.8 Jacobi 8.99 15.3 14.4 11.8 1.19 23.3 3.03 15.7 25.9 2.15 42.8 18.7 19.8
70.3 4.87 203.6 16.5 12.8 109.1 10.8 OptBasis 35.1 14.1 13.9 11.9 1.19 87.2
3.15 17.9 25.9 2.41 269.1 21.3 18.7 70.5 4.87 477.9 16.1 11.3 109.1 10.8 Bank
FAGNN 15.3 9.08 7.73 6.56 0.57 46.9 2.11 11.8 21.6 1.14 68.9 16.0 13.8 23.6
1.03 438.8 13.2 7.17 57.2 1.96 G2CN 28.2 8.63 6.57 6.57 0.57 81.9 2.08 11.0
21.5 0.92 91.0 14.0 10.1 23.6 1.03 827.7 14.6 8.00 57.2 1.96 GNN-LF/HF 12.5
8.33 6.83 7.36 0.57 38.0 2.02 11.3 23.8 1.36 52.7 14.8 11.0 21.8 1.03 385.5
13.2 7.33 59.7 1.96 FiGURe 46.6 26.4 26.6 37.1 3.52 145.2 5.69 35.6 84.6 5.71
175.1 39.7 40.4 230.8 14.5 1458.7 55.3 47.0 358.4 20.1

Obs.#2: Fixed filters achieve top-tier efficiency and scalability.  For both
full- and mini-batch training schemes, fixed-filter GNNs share similar and the
best runtime and memory efficiency. Filter bank models consisting of fixed
filters also exhibit comparable performance when the graph scale is small.
Figure 2 illustrates a more in-depth breakdown of the time and memory
footprints. We mainly observe two design factors that increase the model
overhead. Firstly, variable transformations and subsequent operations come at
the price of more computational resources. In the full-batch scheme, this
leads to lower speed and higher GPU memory demand. Specifically, those with
complex representation computations, including Favard, OptBasis, FBGNN, and
ACMGNN, are among the models with prolonged training time and the worst memory
scalability, incurring out-of-memory errors on large graphs. For mini-batch
training, the cost is indicated by the increased RAM usage, since the model
needs to store $O(KnF)$ precomputation results compared to $O(nF)$ for fixed
filters. Similarly, a filter bank design with $Q$ filters demands up to $Q$
times larger memory.

On the other hand, the second factor of additional propagations slows down
learning but barely affects memory scalability. This can be inferred from
ChebINterp and Bernstein filters, which possess more graph propagations than
others. The design demonstrates significantly longer runtime, especially on
larger graphs, where the graph-scale propagation becomes the speed bottleneck.
However, their memory footprint is on par with fellow variable filters.

Obs.#3: An ideal spectral GNN necessitates comprehensive consideration of the
efficacy-efficiency trade-off.  Combining Sections 4.1 and 4.1, there is an
evident trade-off between efficacy and efficiency among spectral models, where
more challenging scenarios call for sophisticated designs but come with longer
running times and higher memory requirements. We suggest the following
practice as an effort to balance effectiveness and efficiency: when learning
on simple and homophilous graphs, one can stick to fixed filters such as PPR
for the best efficiency and comparable superb precision; for tasks under
heterophily, it is recommended to carefully choose the suitable model for
fitting the graph data and producing satisfying performance, while ensuring
the time and memory overhead remain feasible in the given environment.

In terms of learning schemes, mini-batch training showcases preferable time
and memory scalability compared to the full-batch scheme. As displayed in
Figure 2, on medium-sized graphs, both schemes present the same level of
overall running speed for most filters. However, on large datasets such as
pokec, mini-batch learning is $10-50\times$ faster, as it saves the expensive
graph propagation operation from iterative training. Moreover, it transfers
the majority of memory load from GPU to RAM, which enables the employment of
filters exceeding the GPU memory limit in the full-batch scheme. The GPU
memory complexity independent from the graph scale is favorable for deploying
spectral GNNs in a wider range of environments.

margin=2em,0em,skip=3pt margin=1.5em,-2em,skip=-1pt
margin=2em,0em,skip=3pt margin=1.5em,-2em,skip=-1pt

(a) Full-batch, penn94

(b) Mini-batch, penn94

(c) Full-batch, penn94

(d) Mini-batch, penn94

(e) Full-batch, pokec

(f) Mini-batch, pokec

(g) Full-batch, pokec

(h) Mini-batch, pokec

Figure 2: Comparison of filter time and memory efficiency under full- and
mini-batch training on the medium-scale dataset penn94 ((a)-(d)) and the
large-scale pokec ((e)-(h)). Empty bars are models with OOM error exceeding
$24$\mathrm{G}\mathrm{B}$$ GPU memory.

###  4.2 Degree-specific Effectiveness

Recent works reveal the node-wise performance difference of vanilla GNNs with
respect to nodes of varying degree levels [50, 51, 52, 53, 54]. In this
benchmark, we are motivated to offer preliminary investigation regarding the
degree-specific performance of spectral GNNs, including the causing factors
and impacts of the phenomenon. Corresponding evaluations are in Figure 3 and
Appendix G.

Obs.#4: Degree-wise effectiveness varies under conditions of homophily and
heterophily.  Unlike previous investigations assuming homophily, Figure 3
displays the difference between prediction accuracy on high- and low-degree
nodes extending to heterophilous datasets. It can be observed that most
filters behave distinctively under these two conditions. On homophilous
graphs, performance of high-degree nodes is generally on par with or higher
than low-degree ones, which echoes earlier studies. From the spectral domain
view, high-degree nodes are commonly located in clusters, which is more
related to low frequency in graph spectrum and is favorable for homophilous
GNNs.

Contrarily, the accuracy of high-degree nodes is usually significantly lower
under heterophily. In this case, the hypothesis that higher degrees are
naturally favored by GNNs no longer holds true. Although these nodes aggregate
more information from the neighborhood, it is not essentially beneficial, and
heterophilous connections may carry destructive bias and hinder the
prediction. As a more precise amendment for the conclusion in prior works, we
state that the degree-wise bias is more sensitive, but not necessarily
beneficial, to high-degree nodes with regard to varying graph conditions.

margin=1em,0em,skip=2pt margin=2em,-2em

(a) Accuracy gap on homophilous/heterophilous graphs.

(b) Respective accuracy on roman.

Figure 3: (a) Accuracy gap between high- and low-degree nodes on homophilous
(upper four) and heterophilous (bottom four) graphs. Color of each data point
indicates the difference value, while size of the circle represents the
relative overall accuracy among all filters in each dataset. (b) Respective
accuracy with standard deviation of high- and low-degree nodes on roman.

Obs.#5: Degree-wise bias is relevant to the overall effectiveness of filters.
It is also notable in Figure 3 that the degree-specific difference is
correlated with the test accuracy of models within each dataset. Filters
adhering to Section 4.2 with greater bias achieve relatively better
performance on roman. In comparison, filters such as Linear and Impulse fail
to distinguish high- and low-degree nodes, and the test accuracy is lower. The
observation suggests that GNNs tend to recognize and adapt to the majority of
low-degree nodes in order to achieve higher performance on heterophilous
graphs, although such a strategy sacrifices the performance of high-degree
nodes.

##  5 Discussion and Open Question

In this study, we conduct extensive evaluations for spectral GNNs regarding
both effectiveness and efficiency. We first provide thorough analysis of the
spectral kernels in existing GNNs and categorize them by spectral designs.
These filters are then implemented under a unified framework with plug-and-
play modules and highly-efficient schemes. Comprehensive experiments are
conducted to assess the model performance, with discussions covering
heterophily, graph scales, spectral properties, and degree-wise bias. We
highlight the large-scale experiments thanks to our scalable implementation.
Our benchmark observations also identify several open questions worth further
discussion and study towards better spectral GNNs:

  * •

How to improve spectral filters by balancing efficacy and efficiency? As
demonstrated in Sections 4.1, 4.1 and 4.1, the most efficient fixed-filter
models are only effective in a limited range of graphs, while more powerful
variable and composed filters are far from optimized efficiency. As the
scalability issue is notorious for GNNs in realistic applications, it is of
practical interest to pursue designs enjoying both efficacy and efficiency.
Our study is helpful in uncovering impact factors and bottlenecks of large-
scale deployment, and underscores the potential of spectral GNNs for more
scalable schemes.

  * •

How to address the degree-specific bias and enhance overall effectiveness? In
Sections 4.2 and 4.2, we discover that the degree-wise difference is related
with graph heterophily and affects model precision. As current endeavors
mitigating the GNN bias largely assume homophily, it is promising to search
for specialized schemes with accuracy improvement of both low- and high-degree
nodes considering various graph conditions, which also benefits overall model
performance.

## References

  * [1] Bruna, J., W. Zaremba, A. Szlam, et al.  Spectral networks and locally connected networks on graphs.  In _2nd International Conference on Learning Representations_. 2014.
  * [2] Kipf, T. N., M. Welling.  Semi-supervised classification with graph convolutional networks.  In _International Conference on Learning Representations_. 2017.
  * [3] Atwood, J., D. Towsley.  Diffusion-convolutional neural networks.  In _29th Advances in Neural Information Processing Systems_ , pages 2001–2009. 2016.
  * [4] Defferrard, M., X. Bresson, P. Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ , 29, 2016.
  * [5] Wang, X., M. Zhang.  How powerful are spectral graph neural networks.  In _Proceedings of the 39th International Conference on Machine Learning_ , vol. 162, pages 23341–23362. PMLR, 2022.
  * [6] Gong, C., Y. Cheng, X. Li, et al.  Towards learning from graphs with heterophily: Progress and future.  arXiv:2401.09769, 2024.
  * [7] Cao, D., Y. Wang, J. Duan, et al.  Spectral temporal graph neural network for multivariate time-series forecasting.  In _Advances in neural information processing systems_ , vol. 33, pages 17766–17778. 2020.
  * [8] Liu, Y., Q. Liu, J.-W. Zhang, et al.  Multivariate time-series forecasting with temporal polynomial graph neural networks.  In _Advances in neural information processing systems_ , vol. 35, pages 19414–19426. 2022.
  * [9] Li, Y., H. Chen, Z. Cui, et al.  Towards efficient graph convolutional networks for point cloud handling.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 3752–3762. 2021.
  * [10] Hu, W., J. Pang, X. Liu, et al.  Graph signal processing for geometric data and beyond: Theory and applications.  _IEEE Transactions on Multimedia_ , 24:3961–3977, 2021.
  * [11] Ortega, A., P. Frossard, J. Kovačević, et al.  Graph signal processing: Overview, challenges, and applications.  _Proceedings of the IEEE_ , 106(5):808–828, 2018.
  * [12] Dong, X., D. Thanou, L. Toni, et al.  Graph signal processing for machine learning: A review and new perspectives.  _IEEE Signal processing magazine_ , 37(6):117–127, 2020.
  * [13] Maekawa, S., K. Noda, Y. Sasaki, et al.  Beyond real-world benchmark datasets: An empirical study of node classification with gnns.  _Advances in Neural Information Processing Systems_ , 35:5562–5574, 2022.
  * [14] Duan, K., Z. Liu, P. Wang, et al.  A comprehensive study on large-scale graph training: Benchmarking and rethinking.  _Advances in Neural Information Processing Systems_ , 35:5376–5389, 2022.
  * [15] Balcilar, M., R. Guillaume, P. Héroux, et al.  Analyzing the expressive power of graph neural networks in a spectral perspective.  In _9th International Conference on Learning Representations_. 2021.
  * [16] Chen, Z., F. Chen, L. Zhang, et al.  Bridging the gap between spatial and spectral domains: A unified framework for graph neural networks.  _ACM Computing Surveys_ , page 3627816, 2023.
  * [17] Bo, D., X. Wang, Y. Liu, et al.  A survey on spectral graph neural networks.  arXiv:2302.05631, 2023.
  * [18] Wang, H., M. He, Z. Wei, et al.  Approximate graph propagation.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 1686–1696. ACM, 2021.
  * [19] Feng, W., Y. Dong, T. Huang, et al.  GRAND+: Scalable graph random neural networks.  In _Proceedings of the ACM Web Conference 2022_ , pages 3248–3258. ACM, Virtual Event, Lyon France, 2022.
  * [20] He, M., Z. Wei, J.-R. Wen.  Convolutional neural networks on graphs with chebyshev approximation, revisited.  In _35th Advances in Neural Information Processing Systems_. 2022.
  * [21] Liao, N., S. Luo, X. Li, et al.  LD2: Scalable heterophilous graph neural network with decoupled embeddings.  In _Advances in neural information processing systems,_ , vol. 36, pages 10197–10209. 2023.
  * [22] Yang, M., Y. Shen, R. Li, et al.  A new perspective on the effects of spectrum in graph neural networks.  In _Proceedings of the 39th International Conference on Machine Learning_ , pages 25261–25279. PMLR, 2022.
  * [23] Shuman, D. I., S. K. Narang, P. Frossard, et al.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  _IEEE signal processing magazine_ , 30(3):83–98, 2013.
  * [24] Chen, Z., F. Chen, R. Lai, et al.  Rational neural networks for approximating graph convolution operator on jump discontinuities.  In _2018 IEEE International Conference on Data Mining (ICDM)_ , pages 59–68. 2018.
  * [25] Chien, E., J. Peng, P. Li, et al.  Adaptive universal generalized pagerank graph neural network.  In _9th International Conference on Learning Representations_. 2021.
  * [26] Wu, F., A. Souza, T. Zhang, et al.  Simplifying graph convolutional networks.  In K. Chaudhuri, R. Salakhutdinov, eds., _Proceedings of the 36th International Conference on Machine Learning_ , vol. 97, pages 6861–6871. 2019.
  * [27] Nt, H., T. Maehara.  Revisiting graph neural networks: All we have is low-pass filters.  arXiv:1905.09550, 2019.
  * [28] Deng, C., Z. Zhao, Y. Wang, et al.  Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding.  In _8th International Conference on Learning Representations_. 2020.
  * [29] Zhu, H., P. Koniusz.  Simple spectral graph convolution.  In _9th International Conference on Learning Representations_. 2021.
  * [30] Li, Q., X.-M. Wu, H. Liu, et al.  Label efficient semi-supervised learning via graph filtering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 9574–9583. IEEE, Long Beach, CA, USA, 2019.
  * [31] Klicpera, J., A. Bojchevski, S. Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  _7th International Conference on Learning Representations_ , pages 1–15, 2019.
  * [32] Ming, C., Z. Wei, Z. Huang, et al.  Simple and deep graph convolutional networks.  In _37th International Conference on Machine Learning_ , vol. 119, pages 1703–1713. PMLR, 2020.
  * [33] Gasteiger, J., S. Weißenberger, S. Günnemann.  Diffusion improves graph learning.  In _32nd Advances in Neural Information Processing Systems_. 2019.
  * [34] Wang, Y., Y. Wang, J. Yang, et al.  Dissecting the diffusion process in linear graph convolutional networks.  In _Advances in Neural Information Processing Systems_ , vol. 34, pages 5758–5769. 2021.
  * [35] Xu, K., S. Jegelka, W. Hu, et al.  How powerful are graph neural networks?  In _7th International Conference on Learning Representations_ , pages 1–17. 2019.
  * [36] Ju, M., S. Hou, Y. Fan, et al.  Adaptive kernel graph neural network.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 36, pages 7051–7058. 2022.
  * [37] Liu, M., H. Gao, S. Ji.  Towards deeper graph neural networks.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 338–348. ACM, Virtual Event CA USA, 2020.
  * [38] Bianchi, F. M., D. Grattarola, L. Livi, et al.  Graph neural networks with convolutional arma filters.  _IEEE transactions on pattern analysis and machine intelligence_ , 44(7):3496–3507, 2021.
  * [39] Guo, Y., Z. Wei.  Clenshaw graph neural networks.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’23, pages 614–625. Association for Computing Machinery, New York, NY, USA, 2023.
  * [40] He, M., Z. Wei, Z. Huang, et al.  Bernnet: Learning arbitrary graph spectral filters via bernstein approximation.  In _34th Advances in Neural Information Processing Systems_. 2021.
  * [41] Chen, J., L. Xu.  Improved modeling and generalization capabilities of graph neural networks with legendre polynomials.  _IEEE Access_ , 11:63442–63450, 2023.
  * [42] Guo, Y., Z. Wei.  Graph neural networks with learnable and optimal polynomial bases.  In _40th International Conference on Machine Learning_ , vol. 202. PMLR, Honolulu, Hawaii, USA, 2023.
  * [43] Dong, Y., K. Ding, B. Jalaian, et al.  Adagnn: Graph neural networks with adaptive frequency response filter.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, pages 392–401. ACM, Virtual Event Queensland Australia, 2021.
  * [44] Luan, S., M. Zhao, C. Hua, et al.  Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks.  In _NeurIPS 2022 Workshop: New Frontiers in Graph Learning_. 2022.
  * [45] Luan, S., C. Hua, Q. Lu, et al.  Revisiting heterophily for graph neural networks.  In _36th Advances in Neural Information Processing Systems_. 2022.
  * [46] Bo, D., X. Wang, C. Shi, et al.  Beyond low-frequency information in graph convolutional networks.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(5):3950–3957, 2021.
  * [47] Li, M., X. Guo, Y. Wang, et al.  G2CN: Graph Gaussian convolution networks with concentrated graph filters.  In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, S. Sabato, eds., _39th International Conference on Machine Learning_ , vol. 162 of _Proceedings of Machine Learning Research_ , pages 12782–12796. PMLR, 2022.
  * [48] Zhu, M., X. Wang, C. Shi, et al.  Interpreting and unifying graph neural networks with an optimization framework.  In _Proceedings of the Web Conference 2021_ , pages 1215–1226. ACM, 2021.
  * [49] Ekbote, C., A. P. Deshpande, A. Iyer, et al.  FiGURe: Simple and efficient unsupervised node representations with filter augmentations.  In _36th Advances in Neural Information Processing Systems_. 2023.
  * [50] Tang, X., H. Yao, Y. Sun, et al.  Investigating and mitigating degree-related biases in graph convoltuional networks.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, page 1435–1444. 2020.
  * [51] Yan, Y., M. Hashemi, K. Swersky, et al.  Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks.  In _22nd IEEE International Conference on Data Mining_. 2022.
  * [52] Chen, Z., T. Xiao, K. Kuang.  Ba-gnn: On learning bias-aware graph neural network.  In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_ , pages 3012–3024. 2022.
  * [53] Liao, J., J. Li, L. Chen, et al.  Sailor: Structural augmentation based tail node representation learning.  In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management_ , page 1389–1399. 2023.
  * [54] Li, X., J. Ma, Z. Wu, et al.  Rethinking node-wise propagation for large-scale graph learning.  In _Proceedings of the ACM Web Conference 2024_. 2024.
  * [55] Xu, K., C. Li, Y. Tian, et al.  Representation learning on graphs with jumping knowledge networks.  In _35th International Conference on Machine Learning_ , vol. 80. PMLR, 2018.
  * [56] Maurya, S. K., X. Liu, T. Murata.  Simplifying approach to node classification in graph neural networks.  _Journal of Computational Science_ , 62:101695, 2022.
  * [57] Chanpuriya, S., C. Musco.  Simplified graph convolution with heterophily.  In _35th Advances in Neural Information Processing Systems_ , pages 27184–27197. Curran Associates, Inc., 2022.
  * [58] Bojchevski, A., J. Klicpera, B. Perozzi, et al.  Scaling graph neural networks with approximate pagerank.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2464–2473. ACM, 2020.
  * [59] Chen, M., Z. Wei, B. Ding, et al.  Scalable graph neural networks via bidirectional propagation.  _33rd Advances in Neural Information Processing Systems_ , 2020.
  * [60] Liao, N., D. Mo, S. Luo, et al.  Scalable decoupling graph neural networks with feature-oriented optimization.  _The VLDB Journal_ , 33, 2024.
  * [61] Feng, J., Y. Chen, F. Li, et al.  How powerful are k-hop message passing graph neural networks.  In _36th Advances in Neural Information Processing Systems_. 2022.
  * [62] Tremblay, N., P. Gonçalves, P. Borgnat.  Design of graph filters and filterbanks.  In _Cooperative and Graph Signal Processing_ , pages 299–324. Elsevier, 2018.
  * [63] Page, L., S. Brin, R. Motwani, et al.  The pagerank citation ranking: Bringing order to the web.  Tech. rep., 1999.
  * [64] Chung, F.  The heat kernel as the pagerank of a graph.  _Proceedings of the National Academy of Sciences_ , 104(50):19735–19740, 2007.
  * [65] Calcaterra, C., A. Boldt.  Approximating with gaussians.  _arXiv e-prints_ , (arXiv:0805.3795), 2008.
  * [66] Li, P., I. Chien, O. Milenkovic.  Optimizing generalized pagerank methods for seed-expansion community detection.  In _Advances in Neural Information Processing Systems_ , vol. 32. Curran Associates, Inc., 2019.
  * [67] Shuman, D. I., P. Vandergheynst, P. Frossard.  Chebyshev polynomial approximation for distributed signal processing.  In _2011 International Conference on Distributed Computing in Sensor Systems and Workshops (DCOSS)_ , pages 1–8. IEEE, 2011.
  * [68] Hammond, D. K., P. Vandergheynst, R. Gribonval.  Wavelets on graphs via spectral graph theory.  _Applied and Computational Harmonic Analysis_ , 30(2):129–150, 2011.
  * [69] Gil, A., J. Segura, N. M. Temme.  _Numerical methods for special functions_.  SIAM, 2007.
  * [70] Farouki, R. T.  The bernstein polynomial basis: A centennial retrospective.  _Computer Aided Geometric Design_ , 29(6):379–419, 2012.
  * [71] —.  Legendre–bernstein basis transformations.  _Journal of Computational and Applied Mathematics_ , 119(1):145–160, 2000.
  * [72] Gautschi, W.  _Orthogonal polynomials: computation and approximation_.  OUP Oxford, 2004.
  * [73] Liao, N., D. Mo, S. Luo, et al.  SCARA: Scalable graph neural networks with feature-oriented optimization.  _Proceedings of the VLDB Endowment_ , 15(11):3240–3248, 2022.
  * [74] Liao, R., Z. Zhao, R. Urtasun, et al.  Lanczosnet: Multi-scale deep graph convolutional networks.  In _International Conference on Learning Representations_. 2019.
  * [75] Levie, R., F. Monti, X. Bresson, et al.  Cayleynets: Graph convolutional neural networks with complex rational spectral filters.  _IEEE Transactions on Signal Processing_ , 67(1):97–109, 2018.
  * [76] Lim, D., J. D. Robinson, L. Zhao, et al.  Sign and basis invariant networks for spectral graph representation learning.  In _International Conference on Learning Representations_. 2023.
  * [77] Bo, D., C. Shi, L. Wang, et al.  Specformer: Spectral graph neural networks meet transformers.  In _11th International Conference on Learning Representations_. 2023.
  * [78] Xu, B., H. Shen, Q. Cao, et al.  Graph wavelet neural network.  In _7th International Conference on Learning Representations_. 2019.
  * [79] Zheng, X., B. Zhou, J. Gao, et al.  How framelets enhance graph neural networks.  In _38th International Conference on Machine Learning_ , vol. 139. PMLR, 2021.
  * [80] Geng, H., C. Chen, Y. He, et al.  Pyramid graph neural network: A graph sampling and filtering approach for multi-scale disentangled representations.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , KDD ’23, page 518–530. Association for Computing Machinery, New York, NY, USA, 2023.
  * [81] Gao, Y., X. Wang, X. He, et al.  Addressing heterophily in graph anomaly detection: A perspective of graph spectrum.  In _Proceedings of the ACM Web Conference 2023_ , pages 1528–1538. ACM, Austin TX USA, 2023.
  * [82] Verma, S., Z.-L. Zhang.  Stability and generalization of graph convolutional neural networks.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 1539–1548. 2019.
  * [83] Yang, M., Y. Shen, R. Li, et al.  A new perspective on the effects of spectrum in graph neural networks.  In _International Conference on Machine Learning_ , pages 25261–25279. PMLR, 2022.
  * [84] Li, Q., X. Zhang, H. Liu, et al.  Dimensionwise separable 2-d graph convolution for unsupervised and semi-supervised learning on graphs.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 953–963. 2021.
  * [85] Zhang, Z., P. Cui, W. Zhu.  Deep learning on graphs: A survey.  _IEEE Transactions on Knowledge and Data Engineering_ , 14(8), 2020.
  * [86] Zhou, J., G. Cui, S. Hu, et al.  Graph neural networks: A review of methods and applications.  _AI Open_ , 1:57–81, 2020.
  * [87] Wu, Z., S. Pan, F. Chen, et al.  A comprehensive survey on graph neural networks.  _IEEE Transactions on Neural Networks and Learning Systems_ , 32(1), 2021.
  * [88] Abadal, S., A. Jain, R. Guirado, et al.  Computing graph neural networks: A survey from algorithms to accelerators.  _ACM Computing Surveys_ , 54(9):1–38, 2022.
  * [89] Liu, X., M. Yan, L. Deng, et al.  Survey on graph neural network acceleration: An algorithmic perspective.  In _Proceedings of the 31st International Joint Conference on Artificial Intelligence_. 2022.
  * [90] Zhang, S., A. Sohrabizadeh, C. Wan, et al.  A survey on graph neural network acceleration: Algorithms, systems, and customized hardware.  (arXiv:2306.14052), 2023.
  * [91] Ma, L., Z. Sheng, X. Li, et al.  Acceleration algorithms in gnns: A survey.  (arXiv:2405.04114), 2024.
  * [92] Zheng, X., Y. Liu, S. Pan, et al.  Graph neural networks for graphs with heterophily: A survey.  arXiv:2202.07082, 2022.
  * [93] Dwivedi, V. P., C. K. Joshi, A. T. Luu, et al.  Benchmarking graph neural networks.  _Journal of Machine Learning Research_ , 23:1–48, 2022.
  * [94] Li, J., H. Shomer, H. Mao, et al.  Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking.  In _36th Advances in Neural Information Processing Systems_. 2023.
  * [95] Fey, M., J. E. Lenssen.  Fast graph representation learning with PyTorch Geometric.  In _ICLR Workshop on Representation Learning on Graphs and Manifolds_. 2019.
  * [96] Sen, P., G. Namata, M. Bilgic, et al.  Collective classification in network data.  _AI Magazine_ , 29(3):93, 2008.
  * [97] Zeng, H., H. Zhou, A. Srivastava, et al.  Graphsaint: Graph sampling based learning method.  In _International Conference on Learning Representations_. 2019.
  * [98] Pei, H., B. Wei, K. C.-C. Chang, et al.  Geom-gcn: Geometric graph convolutional networks.  _International Conference on Learning Representations_ , 2020.
  * [99] Oleg Platonov, Denis Kuznedelev, Michael Diskin, et al.  A critical look at evaluation of gnns under heterophily: Are we really making progress?  In _11th International Conference on Learning Representations_. 2023.
  * [100] Hu, W., M. Fey, M. Zitnik, et al.  Open Graph Benchmark: Datasets for Machine Learning on Graphs.  _33rd Advances in Neural Information Processing Systems_ , 2020.
  * [101] Lim, D., F. Hohne, X. Li, et al.  Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.  In _34th Advances in Neural Information Processing Systems_. 2021.
  * [102] Zhang, W., M. Yang, Z. Sheng, et al.  Node dependent local smoothing for scalable graph learning.  In _34th Advances in Neural Information Processing Systems_ , pages 20321–20332. 2021.
  * [103] Qin, Y., Z. Zhang, X. Wang, et al.  Nas-bench-graph: Benchmarking graph neural architecture search.  _Advances in Neural Information Processing Systems_ , 35:54–69, 2022.
  * [104] Park, N., R. Rossi, X. Wang, et al.  Glemos: Benchmark for instantaneous graph learning model selection.  In _36th Advances in Neural Information Processing Systems_. 2023.

##  Appendix A Preliminary

###  A.1 Iterative and Decoupled GNN Architecture

Model architecture is a critical perspective that affects model accuracy and
efficiency, even if the models share the same spectral expressiveness. We
distinguish iterative and decoupled architectures based on their approach of
integrating the propagation and transformation stages, i.e., how the graph-
scale propagation is integrated into the forward passing.

Iterative architecture implies that each hop of propagation is associated with
an explicit transformation computation $\varphi$, usually implemented by
multiplying a learnable weight matrix
$\boldsymbol{\mathbf{W}}\in\mathbb{R}^{F\times F}$ and applying non-linear
activation. For simplicity, here we assume the dimension of input and output
features to be constant across all layers. In the common case, the layer
representation $\boldsymbol{\mathbf{H}}^{(j+1)}$ is dependent on its
predecessor $\boldsymbol{\mathbf{H}}^{(j)}$. When the $j$-th propagation is
$f^{(j)}$, the model is computed in the recursive or iterative form:
$\boldsymbol{\mathbf{H}}^{(j+1)}=\varphi(f^{(j)}(\tilde{\boldsymbol{\mathbf{A}}})\cdot\boldsymbol{\mathbf{H}}^{(j)})$.
More complex schemes such as jumping knowledge [55] and concatenation [56, 57,
21] have also been proposed, which are orthogonal to this study since these
spatial transformations do not affect the spectral expressiveness.

Decoupled designs perform all hops of graph-related propagation together
without invoking weight tensors, which implies that the parameters
$\theta_{k}$ in Eq. 2 are all scalars. Note that this does not change the
spectral expressiveness of the filtering process. The separated propagation
stage enjoys the benefit of isolated computation, which can be accelerated
with dedicated algorithms [58, 59, 34, 18, 19, 21, 60]. The transformation
stage is also more scalable for adopting minibatch training and saving GPU
memory. A general spatial formulation for the network pipeline is
$\boldsymbol{\mathbf{H}}=\varphi_{1}(f(\tilde{\boldsymbol{\mathbf{A}}})\cdot\varphi_{0}(\boldsymbol{\mathbf{X}}))$,
where $f(\tilde{\boldsymbol{\mathbf{A}}})$ contains all $J$-hop propagations,
and $\varphi_{0},\varphi_{1}$ are pre- and post-transformations, usually
implemented as MLPs. Its spectral function is explicitly written as
$g(\tilde{\boldsymbol{\mathbf{L}}})$ of order $K$.

Table 4: Summary of primary symbols and notations in this work. Notation | Description
---|---
$\mathcal{G},\mathcal{V},\mathcal{E}$ | Graph, node set, and edge set
$\mathcal{N}(u)$ | Neighboring node set of node $u$
$f,\varphi$ | Spatial propagation and transformation
$\hat{g},g$ | Full and truncated spectral convolution
$n,m,F$ | Node number, edge number, and feature number
$J,K,Q$ | Spatial propagation hops, spectral filter order, number of filters
$\rho$ | General graph normalization coefficient
$\xi_{j}$ | Spatial propagation parameter of hop $j$ with regard to $\tilde{\boldsymbol{\mathbf{A}}}$
$\theta_{k}$ | Spectral filter parameter of order $k$ with regard to polynomial $T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\gamma_{q}$ | Weight parameter of filter $q$
$\boldsymbol{\mathbf{A}},\,\bar{\boldsymbol{\mathbf{A}}},\,\tilde{\boldsymbol{\mathbf{A}}}$ | Raw, self-looped, and normalized adjacency matrix of graph $\mathcal{G}$
${\boldsymbol{\mathbf{L}}},\,\tilde{\boldsymbol{\mathbf{L}}}$ | Raw and normalized Laplacian matrix of graph $\mathcal{G}$
$\boldsymbol{\mathbf{D}},\,\bar{\boldsymbol{\mathbf{D}}}$ | Raw and self-looped diagonal degree matrix
$\boldsymbol{\mathbf{H}},\boldsymbol{\mathbf{W}}$ | Network representation, weight matrix
$\boldsymbol{\mathbf{X}},\,\boldsymbol{\mathbf{x}}$ | Node attribute matrix and feature-wise vector
$\boldsymbol{\mathbf{\Lambda}},\,\lambda_{i}$ | Diagonal eigenvalue matrix, $i$-th eigenvalue of graph Laplacian

When deriving corresponding spectral filters, the transformation operation is
usually ignored, i.e., assuming
$\boldsymbol{\mathbf{W}}=\boldsymbol{\mathbf{I}}$ and utilizing identity
mapping as linear activation [26, 16]. Without loss of generality, if for the
$k$-th layer, the single-layer filter in spectral domain is $g^{(k)}$, then
the overall spectral filter is as expressive as $g=g^{(k)}\ast
g^{(k-1)}\ast\cdots\ast g^{(0)}$ [61, 5]. Conversely, if the explicit
polynomial is known, the model can be calculated in the iterative form by
recursively multiply the diffusion matrix (or matrices) to acquire the
$k$-order basis, and adding to the result with respective weight parameter.
Consequently, we use iterative or explicit formulas interchangeably in our
filter analysis, depending on the specific formulation. For iterative forms
with complicated or non-intuitive explicit formulas, we consider spectral
filters representing a single layer.

Table 5: Taxonomy of spectral GNN filters with notable corresponding models
included in this paper. “$\mathbb{I}$” and “$\mathbb{D}$” in the “Model”
column respectively refer to Iterative and Decoupled architectures.

Type Filter Name Filter Function $g(\tilde{\boldsymbol{\mathbf{L}}})$ Model
Identity $\boldsymbol{\mathbf{I}}$ MLP Linear
$2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}$ $\mathbb{I}$: GCN
Impulse $(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{K}$
$\mathbb{D}$: SGC, gfNN, GZoom, GRAND+ Monomial
$\frac{1}{K+1}\sum_{k=0}^{K}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{D}$: S2GC, AGP, GRAND+ PPR
$\sum_{k=0}^{K}\alpha(1-\alpha)^{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{I}$: GLP, GCNII; $\mathbb{D}$: APPNP, GDC, AGP, GRAND+ HK
$\sum_{k=0}^{K}\frac{e^{-\alpha}\alpha^{k}}{k!}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{D}$: GDC, AGP, DGC Fixed Filter Gaussian
$\sum_{k=0}^{K}\frac{\alpha^{k}}{k!}(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{D}$: G2CN Linear
$(1+\theta)\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}$
$\mathbb{I}$: GIN, AKGNN Monomial
$\sum_{k=0}^{K}\theta_{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{D}$: DAGNN, GPRGNN Horner
$\sum_{k=0}^{K}\theta_{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{I}$: ARMAGNN, HornerGCN Chebyshev
$\sum_{k=0}^{K}\theta_{k}T_{\text{Cheb}}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{I}$: ChebNet; $\mathbb{D}$: ChebBase ChebInterp
$\frac{2}{K+1}\sum_{k=0}^{K}\sum_{\kappa=0}^{K}\theta_{\kappa}T_{\text{Cheb}}^{(k)}(x_{\kappa})T_{\text{Cheb}}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: ChebNetII Clenshaw
$\sum_{k=0}^{K}\theta_{k}T_{\text{Cheb2}}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{I}$: ClenshawGCN Bernstein
$\sum_{k=0}^{K}\frac{\theta_{k}}{2^{K}}\bigl{(}\begin{smallmatrix}{K}\\\
{k}\end{smallmatrix}\bigr{)}(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{K-k}\tilde{\boldsymbol{\mathbf{L}}}^{k}$
$\mathbb{D}$: BernNet Legendre
$\sum_{k=0}^{K}\theta_{k}\frac{(-1)^{k}}{k!\bigl{(}\begin{smallmatrix}{2k}\\\
{k}\end{smallmatrix}\bigr{)}}\,(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}\tilde{\boldsymbol{\mathbf{L}}}^{k}$
$\mathbb{D}$: LegendreNet Jacobi
$\sum_{k=0}^{K}\theta_{k}T_{\text{Jacobi}}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: JacobiConv Favard
$\sum_{k=0}^{K}\theta_{k}T_{\text{Favard}}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: FavardGNN Variable Filter OptBasis
$\sum_{k=0}^{K}\theta_{k}T_{\text{OptBasis}}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: OptBasisGNN Linear
$\bigparallel_{q=1}^{Q}(\boldsymbol{\mathbf{I}}-\gamma_{q}\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: AdaGNN Linear (LP, HP)
$\gamma_{1}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})+\gamma_{2}\tilde{\boldsymbol{\mathbf{L}}}$
$\mathbb{I}$: FBGCN Linear (LP, HP, ID)
$\gamma_{1}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})+\gamma_{2}\tilde{\boldsymbol{\mathbf{L}}}+\gamma_{3}\boldsymbol{\mathbf{I}}$
$\mathbb{I}$: ACMGNN Linear (LP, HP)
$\gamma_{1}((\beta+1)\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})+\gamma_{2}((\beta-1)\boldsymbol{\mathbf{I}}+\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: FAGNN Gaussian (LP, HP) $\sum_{q=1}^{Q}\sum_{k=0}^{\lfloor
K/2\rfloor}\frac{\alpha_{q}^{k}}{k!}((1+\beta_{q})\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{2k}$
$\mathbb{D}$: G2CN PPR (LP, HP)
$\sum_{q=1}^{Q}\sum_{k=0}^{K}\alpha_{q}(1-\alpha_{q})^{k}(\boldsymbol{\mathbf{I}}+\beta_{q}\tilde{\boldsymbol{\mathbf{L}}})(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
$\mathbb{D}$: GNN-LF/HF Filter Bank Mono, Cheb, Bern, ID
$\sum_{q=1}^{\mathit{Q}}\sum_{k=0}^{K}\gamma_{q}\theta_{q,k}T_{q}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\mathbb{D}$: FiGURe

###  A.2 Time and Memory Complexity

Here we separately examine the theoretical computational complexity of graph
propagation and feature transformation. With regard to the relative order
between propagation and transformation, both iterative and decoupled
architectures usually conduct propagation first by multiplying the sparse
graph matrix with the dense representation, then perform corresponding feature
transformation afterwards. This implementation allows for maintaining a
constant diffusion matrix and preventing frequent modification of the graph
data.

For each propagation hop multiplying a graph matrix $\boldsymbol{\mathbf{A}}$,
or similarly, a matrix derived from $\boldsymbol{\mathbf{A}}$, upon
representation $\boldsymbol{\mathbf{H}}$, the time complexity is $O(mF)$.
Performing $K$-hop propagation leads to a time complexity of $O(KmF)$. Under
the above propagation-first scheme, the memory space for maintaining one graph
matrix throughout propagation hops is $O(m)$. Models such as BernNet utilize
more than one diffusion matrices, demanding more space for storing graph
matrices.

The time complexity of transformation by applying $\boldsymbol{\mathbf{W}}$ to
$\boldsymbol{\mathbf{H}}$ is $O(nF^{2})$. Stacking $J$ layers increases it by
$J$ times. For the simplest case, employing a representation matrix to be
iteratively updated for all nodes throughout learning consumes $O(nF)$ memory
space, while performing the computation in minibatches reduces it to be linear
with batch size $n_{b}$ instead of $n$. Specifically, architectures beyond the
vanilla recursive formation such as residual connection, jumping knowledge,
and concatenation also cause time and memory expense to rise in accordance.

##  Appendix B Details on Spectral GNN Paradigms

###  B.1 Fixed Filter

#### Linear.

A layer of GCN [2] propagation
$f(\tilde{\boldsymbol{\mathbf{A}}})=\boldsymbol{\mathbf{I}}+\tilde{\boldsymbol{\mathbf{A}}}$
is equivalent to a single-hop of spectral convolution. Recall that
$\tilde{\boldsymbol{\mathbf{L}}}=\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{A}}}$,
the filter can be expressed as:

$g(\tilde{\boldsymbol{\mathbf{L}}})=2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}.$

#### Impulse.

SGC [26] and gfNN [27] adopt a pre-propagation decoupled architecture, while
GZoom [28] applies post-propagation to achieve expansion of the closed-form
filter $(\boldsymbol{\mathbf{I}}+\tilde{\boldsymbol{\mathbf{L}}})^{-1}$. All
these models result in a $J$-hop spatial diffusion operation as
$f(\boldsymbol{\mathbf{A}})=\tilde{\boldsymbol{\mathbf{A}}}^{J}$. By
respectively examining bases
$T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}$
and
$T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}}^{k}$,
we have two equivalent formulations of the filter:

$\displaystyle g(\tilde{\boldsymbol{\mathbf{L}}})$
$\displaystyle=(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{K},\quad$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\;$
$\displaystyle\theta_{0}=\theta_{1}=\cdots=\theta_{K-1}=0,\;\theta_{K}=1;$
$\displaystyle g(\tilde{\boldsymbol{\mathbf{L}}})$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}\,\tilde{\boldsymbol{\mathbf{L}}}^{k},\quad$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}}^{k},\;$
$\displaystyle\theta_{k}=\binom{K}{k}(-1)^{k},$

where $\bigl{(}\begin{smallmatrix}{K}\\\ {k}\end{smallmatrix}\bigr{)}$ is the
binomial coefficient.

#### Monomial.

S2GC [29] summarizes $K$-hop propagation results with uniform weights in
decouple precomputation, which is classifies as the monomial propagation
$f(\boldsymbol{\mathbf{A}})=\sum_{j=1}^{J}\xi_{j}\tilde{\boldsymbol{\mathbf{A}}}^{j}$,
where $\xi_{j}=1/(J+1)$. Similarly, there are two commonly used spectral
interpretations based on two bases:

$\displaystyle g(\tilde{\boldsymbol{\mathbf{L}}})$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}\,(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\;$
$\displaystyle\theta_{0}=\cdots=\theta_{K}=\frac{1}{K+1};$ $\displaystyle
g(\tilde{\boldsymbol{\mathbf{L}}})$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}\,\tilde{\boldsymbol{\mathbf{L}}}^{k},\quad$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}}^{k},\;$
$\displaystyle\theta_{k}=\frac{1}{K+1}\sum_{j=k}^{J}\binom{j}{k}(-1)^{k},$

#### Personalized PageRank (PPR).

GLP [30] derives a closed-form
$\hat{f}(\boldsymbol{\mathbf{A}})=(\boldsymbol{\mathbf{I}}+\alpha\boldsymbol{\mathbf{L}})^{-1}$
from the auto regressive (AR) filter [62], while PPNP [31] solves PPR [63] as
$\hat{f}(\tilde{\boldsymbol{\mathbf{A}}})=\alpha\big{(}\boldsymbol{\mathbf{I}}+(1-\alpha)\tilde{\boldsymbol{\mathbf{A}}}\big{)}^{-1}$.
These two graph processing techniques are equivalent in essence.
$\alpha\in[0,1]$ is the coefficient for balancing the strength of neighbor
propagation, that a larger $\alpha$ results in stronger node identity and
weaker neighboring impact, and vice versa. In both works, the filter is
approximated by a recursive calculation
$\boldsymbol{\mathbf{H}}^{(j+1)}=\varphi((1-\alpha)\tilde{\boldsymbol{\mathbf{A}}}\boldsymbol{\mathbf{H}}^{(j)}+\alpha\boldsymbol{\mathbf{H}}^{(0)})$,
which is widely accepted in later studies such as GCNII [32]. The explicit
spatial and spectral interpretations of the polynomial approximation are
respectively:

$f(\tilde{\boldsymbol{\mathbf{A}}})=\sum_{j=0}^{J}\alpha(1-\alpha)^{j}\tilde{\boldsymbol{\mathbf{A}}}^{j};\quad
g(\tilde{\boldsymbol{\mathbf{L}}})=\sum_{k=0}^{K}\theta_{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{k}=\alpha(1-\alpha)^{k}.$

#### Heat Kernel (HK).

GDC [33] inspects the heat kernel PageRank (HKPR) [64] replacing the PPR
calculation by an exponential parameter. Let $\alpha>0$ be the temperature
coefficient, the filter
$\hat{f}(\tilde{\boldsymbol{\mathbf{A}}})=e^{-\alpha\tilde{\boldsymbol{\mathbf{L}}}}$
is expanded in spatial and spectral forms as:

$f(\tilde{\boldsymbol{\mathbf{A}}})=\sum_{j=0}^{J}\frac{e^{-\alpha}\alpha^{j}}{j!}\tilde{\boldsymbol{\mathbf{A}}}^{j};\quad
g(\tilde{\boldsymbol{\mathbf{L}}})=\sum_{k=0}^{K}\theta_{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{k}=\frac{e^{-\alpha}\alpha^{k}}{k!}.$

#### Gaussian.

G2CN [47] uses the Gaussian filter [65] for better flexibility on capturing
local information. When concentrating on low frequency, the closed-form
propagation is
$\hat{f}(\tilde{\boldsymbol{\mathbf{A}}})=e^{-\alpha(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})}$.
Invoking Taylor expansion for the filter leads to:

$f^{(j)}(\tilde{\boldsymbol{\mathbf{A}}})=\boldsymbol{\mathbf{I}}-\frac{\alpha}{J}(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}});\quad
g(\tilde{\boldsymbol{\mathbf{L}}})=\sum_{k=0}^{K}\theta_{k}(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{k}=\frac{\alpha^{k}}{k!}.$

###  B.2 Variable Filter

#### Linear.

GIN [35] alters the iterative ridged adjacency propagation with a learnable
scaling parameter $\theta>0$ controlling the strength of self loops, i.e.,
skip connections. It proves that its propagation
$f(\tilde{\boldsymbol{\mathbf{A}}})=(1+\xi)\boldsymbol{\mathbf{I}}+\tilde{\boldsymbol{\mathbf{A}}}$
is more expressive with regard to the Weisfeiler-Lehman (WL) test. AKGNN [36]
elaborates the expression in spectral domain, that the scaling parameter
adaptively balances the threshold between high and low frequency. We thereby
obtain the linear spectral function for each layer as:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=(1+\theta)\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}.$

#### Monomial.

DAGNN [37] studies the scheme of assigning learnable parameters to each hop of
the propagation, but implements a costly concatenation-based scheme. GPRGNN
[25] considers the iterative generalized PageRank computation [66] under
heterophily, which also produces the same variable monomial spectral filter
formulated as
$f(\boldsymbol{\mathbf{A}})=\sum_{j=0}^{J}\xi_{j}\tilde{\boldsymbol{\mathbf{A}}}^{j}$.
We present two bases and corresponding relationship between spatial and
spectral parameters when $J=K$:

$\displaystyle g(\tilde{\boldsymbol{\mathbf{L}}};\theta)$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}\,(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\;$
$\displaystyle\theta_{k}=\xi_{j};$ $\displaystyle
g(\tilde{\boldsymbol{\mathbf{L}}};\theta)$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}\,\tilde{\boldsymbol{\mathbf{L}}}^{k},\quad$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}}^{k},\;$
$\displaystyle\theta_{k}=\sum_{j=k}^{J}\binom{j}{k}(-1)^{k}\xi_{j}.$

[25] also inspects the effect of initialization of the parameters
$\xi_{j},\theta_{k}$ on fitting heterophilous graph signals.

#### Horner.

Horner’s method is a recursive algorithm to compute the summation of monomial
bases with residual connections. Consider adding a residual term in the layer-
wise propagation corresponding to the monomial filter
$\boldsymbol{\mathbf{H}}^{(j+1)}=\varphi(\tilde{\boldsymbol{\mathbf{A}}}\boldsymbol{\mathbf{H}}^{(j)}+\xi_{j}\boldsymbol{\mathbf{H}}^{(0)})$.
When the balancing parameter is fixed $\xi_{j}=\alpha/(1-\alpha)$, it is
equivalent to the PPR computation in Section B.1. When $\xi_{j}$ is variable,
the model is regarded as HornerGCN which is introduced by [39]. Alternatively,
ARMAGNN [38] utilizes the Auto Regressive Moving Average (ARMA) filter
$\hat{f}(\boldsymbol{\mathbf{A}})=\beta(\boldsymbol{\mathbf{I}}-\alpha\tilde{\boldsymbol{\mathbf{A}}})^{-1}$
[62] as an approach to describe the residual connection learned by respective
weights in iterative architecture. Their spectral filter is:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}\,(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{k}=\xi_{K-k}.$

Although it shares an identical spectral interpretation with the monomial
filter, the explicit residual connection proves beneficial in guiding the
learnable parameters to recognize node identity and alleviate over-smoothing
throughout propagation.

#### Chebyshev.

The Chebyshev basis is widely accepted for graph signal processing, which is
powerful in producing a minimax polynomial approximation for the analytic
functions [67, 68]. ChebNet [4] utilizes it to replace the adjacency
propagation in iterative network architecture so that
$f^{(j)}(\tilde{\boldsymbol{\mathbf{A}}})=T^{(j)}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{A}}})$.
To adapt the basis to decoupled propagation with explicit variable parameters,
[20] proposes ChebBase. The spectral expressiveness of these two models are
the same, and the filter is:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=2\tilde{\boldsymbol{\mathbf{L}}}T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}}),\,T^{(1)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}},\,T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{I}}.$

The Chebyshev polynomial is expressed in the three-term recurrence relation,
which is favorable for the GNN iterative propagation. One can also write the
Chebyshev basis of the first kind as the closed-form expression
$T^{(k)}(\lambda)=\cos(k\arccos{\lambda})$.

#### Chebyshev Interpolation (ChebInterp).

ChebNetII [20] utilizes Chebyshev interpolation [69] to modify the Chebyshev
filter parameter for better approximation with generally decaying weights. For
each Chebyshev basis $T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$, it appends
the basis with $K$-order interpolation:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\frac{2}{K+1}\sum_{k=0}^{K}\sum_{\kappa=0}^{K}\theta_{\kappa}T^{(k)}(x_{\kappa})\,T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad
x_{\kappa}=\cos\left(\frac{\kappa+1/2}{K+1}\pi\right),$

where $T^{(k)}(x_{\kappa}),T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$ follow
the Chebyshev basis, and $x_{\kappa}$ are the Chebyshev nodes of $T^{(K+1)}$.

#### Clenshaw.

Similar to Horner’s method, ClenshawGCN [39] applies Clenshaw algorithm on top
of Chebyshev polynomials to incorporate explicit residual connections. Its
spatial convolution is obtained as
$\boldsymbol{\mathbf{H}}^{(j+1)}=\varphi\big{(}2\tilde{\boldsymbol{\mathbf{A}}}\boldsymbol{\mathbf{H}}^{(j)}-\boldsymbol{\mathbf{H}}^{(j-1)}+\xi_{j}\boldsymbol{\mathbf{H}}^{(0)}\big{)},\boldsymbol{\mathbf{H}}^{(-1)}=\boldsymbol{\mathbf{H}}^{(-2)}=\boldsymbol{\mathbf{O}}$.
The form of spectral filter is related with Chebyshev polynomials of the
second kind:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=2\tilde{\boldsymbol{\mathbf{L}}}T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}}),\,T^{(1)}(\tilde{\boldsymbol{\mathbf{L}}})=2\tilde{\boldsymbol{\mathbf{L}}},\,T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{I}}.$

Alternatively, the closed-form definition of the Chebyshev basis of the second
kind is $T^{(k)}(\cos\lambda)=\frac{\sin((k+1)\lambda)}{\sin{\lambda}}$. The
relation to spatial parameters is $\theta_{k}=\xi_{K-k}$.

#### Bernstein.

BernNet [40] pursues more interpretable spectral filters by by Bernstein
polynomial approximation [70] and invokes constraints form prior knowledge to
avoid ill-posed variable parameters. The spatial propagation is special as it
applies two graph matrices instead of one. The filter with regard to Bernstein
basis $T^{(k)}$ is:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\frac{\theta_{k}}{2^{K}}\,T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\binom{K}{k}(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{K-k}\,\tilde{\boldsymbol{\mathbf{L}}}^{k},$

where learnable parameters are initialized as $\theta_{k}=T^{(k)}(k/K)$.

#### Legendre.

LegendreNet [41] exploits the Legendre polynomials in an accumulation form of
calculation similar to BernNet:

$g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\frac{(-1)^{k}}{k!\bigl{(}\begin{smallmatrix}{2k}\\\
{k}\end{smallmatrix}\bigr{)}}\,(2\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k}\,\tilde{\boldsymbol{\mathbf{L}}}^{k}.$

Based on the relation of Bernstein bases and Legendre polynomials [71], we can
also express it in the recurrence form:

$\displaystyle
g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\quad$
$\displaystyle
T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{I}},\;T^{(1)}(\tilde{\boldsymbol{\mathbf{L}}})=\tilde{\boldsymbol{\mathbf{L}}},$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\frac{2k-1}{k}\tilde{\boldsymbol{\mathbf{L}}}T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-\frac{k-1}{k}T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}}).$

#### Jacobi.

JacobiConv [5] utilizes the more general Jacobi basis, whereas Chebyshev and
Legendre polynomials can be regarded as special cases. Intuitively, it
provides more flexible weight functions with two hyperparameters
$\alpha,\beta$ to adapt to different signals of the spectral graphs. Each
polynomial term of JacobiConv can be formulated by the three-term recurrence
as following:

$\displaystyle
g(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\;$
$\displaystyle
T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{I}},\;T^{(1)}(\tilde{\boldsymbol{\mathbf{L}}})=\frac{\alpha-\beta}{2}\boldsymbol{\mathbf{I}}+\frac{\alpha+\beta+2}{2}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}),$
$\displaystyle
T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})=\delta_{k}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})+\delta_{k}^{\prime}\,T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-\delta_{k}^{\prime\prime}\,T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}}),$

where

$\displaystyle\delta_{k}=\frac{(2k+\alpha+\beta)(2k+\alpha+\beta-1)}{2k(k+\alpha+\beta)},\,\delta_{k}^{\prime}=\frac{(2k+\alpha+\beta-1)(\alpha^{2}-\beta^{2})}{2k(k+\alpha+\beta)(2k+\alpha+\beta-2)},$
$\displaystyle\delta_{k}^{\prime\prime}=\frac{(k+\alpha-1)(k+\beta-1)(2k+\alpha+\beta)}{k(k+\alpha+\beta)(2k+\alpha+\beta-2)}\,\text{
for }k\geq 2.$

#### Favard.

FavardGNN [42] exploits the Favard’s Theorem [72] to learn the polynomial
basis from available space and ensure orthonormality. It is achieved by a
three-term recurrence form with multiple series of hop-dependent variable
parameters $\theta,\alpha,\beta$:

$\displaystyle g(\tilde{\boldsymbol{\mathbf{L}}};\theta)$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\;T^{(-1)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{O}},\;T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\frac{1}{\sqrt{\alpha_{0}}}\boldsymbol{\mathbf{I}},$
$\displaystyle T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\displaystyle=\frac{1}{\sqrt{\alpha_{k}}}\left((\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-\beta_{k}T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-\sqrt{\alpha_{k-1}}\,T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}}).\right)$

#### OptBasis.

OptBasisGNN [42] considers a basis to be optimal with regard to convergence
rate in the graph signal denoising problem. By replacing the learnable
parameters in FavardGNN with parameters derived from the current input signal
$\boldsymbol{\mathbf{h}}^{(k)}$, it can approach the optimal basis without
occurring additional overhead.

$\displaystyle g(\tilde{\boldsymbol{\mathbf{L}}};\theta)$
$\displaystyle=\sum_{k=0}^{K}\theta_{k}T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),\;T^{(-1)}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{O}},\;T^{(0)}(\tilde{\boldsymbol{\mathbf{L}}})=\frac{1}{\|\boldsymbol{\mathbf{h}}^{(0)}\|}\boldsymbol{\mathbf{I}},$
$\displaystyle T^{(k)}(\tilde{\boldsymbol{\mathbf{L}}})$
$\displaystyle=\frac{1}{\|\boldsymbol{\mathbf{h}}^{(k)}\|}\left((\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-\beta_{k-1}T^{(k-1)}(\tilde{\boldsymbol{\mathbf{L}}})-\|\boldsymbol{\mathbf{h}}^{(k-1)}\|T^{(k-2)}(\tilde{\boldsymbol{\mathbf{L}}})\right),$
$\displaystyle\beta_{k-1}$
$\displaystyle=\langle(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})\boldsymbol{\mathbf{h}}^{(k-1)},\boldsymbol{\mathbf{h}}^{(k-1)}\rangle.$

###  B.3 Filter Bank

#### AdaGNN.

AdaGNN [43] designs $Q=F$ adaptive filters by assigning feature-specific
parameters to the linear basis
$g_{q}(\tilde{\boldsymbol{\mathbf{L}}})=\boldsymbol{\mathbf{I}}-\gamma_{q}\tilde{\boldsymbol{\mathbf{L}}},1\leq
q\leq F$. The representation update is performed in an iterative manner as
$\boldsymbol{\mathbf{H}}^{(j+1)}={\boldsymbol{\mathbf{H}}}^{(j)}-\tilde{\boldsymbol{\mathbf{L}}}{\boldsymbol{\mathbf{H}}}^{(j)}\boldsymbol{\mathbf{\Gamma}}^{(j)}$,
where
$\boldsymbol{\mathbf{\Gamma}}^{(j)}=\operatorname{diag}(\gamma_{1}^{(j)},...,\gamma_{F}^{(j)})$
containing the learnable feature-wise parameter for the $j$-th layer. Hence,
considering a single layer, the corresponding aggregated filter in spectral
domain is:

$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma)=\bigparallel_{q=1}^{F}(\boldsymbol{\mathbf{I}}-\gamma_{q}\tilde{\boldsymbol{\mathbf{L}}}),$

where each filter $g_{q}(\tilde{\boldsymbol{\mathbf{L}}})$ is only applied to
the $q$-th feature, and $\bigparallel$ is the concatenation operator that
combines filtering result tensors among all features.

#### FBGNN.

FBGNN [44] introduces the concept of filter bank for combining multiple
filters in spectral GNN under the context of graph heterophily. It designs a
two-channel scheme using graph adjacency
$T_{1}=\tilde{\boldsymbol{\mathbf{A}}}$ as linear low-pass filter (LP) and
Laplacian $T_{2}=\tilde{\boldsymbol{\mathbf{L}}}$ for linear high-pass filter
(HP) to learn the smooth and non-smooth components together. FBGNN adopts an
iterative form with scalar parameters $\gamma_{1},\gamma_{2}\in[0,1]$ for
weighted sum. By omitting components including transformation weights and non-
linear activation functions, we give the equivalent spectral function for each
layer as:

$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma)=\gamma_{1}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})+\gamma_{2}\tilde{\boldsymbol{\mathbf{L}}}.$

#### ACMGNN.

ACMGNN [45] extends FBGNN to three filters with the additional identity (ID)
diffusion matrix $T_{3}=\boldsymbol{\mathbf{I}}$, which corresponds to an all-
pass filter maintaining node identity throughout propagation. It has two
variants of applying different relative order between transformation and
propagation, which are denoted as ACMGNN-I and ACMGNN-II. Both of their
single-layer spectral expressions can be simplified as:

$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma)=\gamma_{1}(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})+\gamma_{2}\tilde{\boldsymbol{\mathbf{L}}}+\gamma_{3}\boldsymbol{\mathbf{I}}.$

#### FAGCN.

FAGCN [46] combines two linear filters with bias for capturing low- and high-
frequency signals as
$T_{1}=(\beta+1)\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}$ and
$T_{2}=(\beta-1)\boldsymbol{\mathbf{I}}+\tilde{\boldsymbol{\mathbf{L}}}$,
where $\beta\in[0,1]$ is the scaling coefficient. Since both filters are
linear to $\tilde{\boldsymbol{\mathbf{L}}}$, the fused representation of each
layer can be computed using only one propagation by employing attention
mechanism. We generally write the channel-wise parameters as
$\gamma_{1},\gamma_{2}\in[0,1]$ and $\gamma_{1}+\gamma_{2}=1$. Then the
spectral expression for one layer is:

$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma)=\gamma_{1}((\beta+1)\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})+\gamma_{2}((\beta-1)\boldsymbol{\mathbf{I}}+\tilde{\boldsymbol{\mathbf{L}}}).$

#### G2CN.

G2CN [47] derives the Gaussian filters for high- and low-frequency
concentration centers. Specifically, it adopts 2-hop propagation in each
layer. Utilizing the decay coefficient $\alpha\in[0,1]$ and the scaling
coefficient $\beta\in[0,1]$, we rewrite the layer-wise propagation as
$f^{(j)}(\tilde{\boldsymbol{\mathbf{A}}})=\boldsymbol{\mathbf{I}}-{\alpha}((1\pm\beta)\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{2}/{J}$.
The model integrates the $Q=2$ channels after the decoupled propagation,
hence:

$\displaystyle\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma)=\gamma_{1}\sum_{k=0}^{\lfloor
K/2\rfloor}\theta_{1,k}\,T_{1}^{(k)}+\gamma_{2}\sum_{k=0}^{\lfloor
K/2\rfloor}\theta_{2,k}\,T_{2}^{(k)},\quad$

$\displaystyle
T_{1}^{(k)}=((1+\beta_{1})\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{2k},\quad\theta_{1,k}=\frac{\alpha_{1}^{k}}{k!},$
$\displaystyle
T_{2}^{(k)}=((1-\beta_{2})\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{2k},\quad\theta_{2,k}=\frac{\alpha_{2}^{k}}{k!}.$

#### GNN-LF/HF.

[48] proposes a pair of generalized GNN propagations based on low- and high-
passing filtering (LF/HF) on top of its unified optimization framework
depicting a range of GNN designs. Intuitively, its filter formulation is
similar to the PPR scheme, except a
$(\boldsymbol{\mathbf{I}}\pm\beta\tilde{\boldsymbol{\mathbf{L}}})$ factor
applying to the input signal for distinguishing low- and high-frequency
components. We transform the original dual filters into one model with $Q=2$
channels by learning the balancing coefficients
$\gamma_{1},\gamma_{2}\in[0,1]$ which adjust the relative strength between
node identity and low/high frequency features. Consequently, the channels can
be implemented in a shared adjacency-based propagation. We formulate the
filter bank version of GNN-LF/HF as:

$\displaystyle\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma)=\gamma_{1}\sum_{k=0}^{K}\theta_{1,k}\,T_{1}^{(k)}+\gamma_{2}\sum_{k=0}^{K}\theta_{2,k}\,T_{2}^{(k)},\quad$

$\displaystyle
T_{1}^{(k)}=(\boldsymbol{\mathbf{I}}-\beta_{1}\tilde{\boldsymbol{\mathbf{L}}})(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{1,k}=\alpha_{1}(1-\alpha_{1})^{k},$
$\displaystyle
T_{2}^{(k)}=(\boldsymbol{\mathbf{I}}+\beta_{2}\tilde{\boldsymbol{\mathbf{L}}})(\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}})^{k},\quad\theta_{2,k}=\alpha_{2}(1-\alpha_{2})^{k},$

where there are
$\alpha_{1},\alpha_{2}\in[0,1],\beta_{1}\in[0,1/2],\beta_{2}\in(0,+\infty)$
according to the optimization objective.

#### FiGURe.

FiGURe [49] suggests using filter bank to adapt the unsupervised settings
where the graph information can assist filter formation. It considers up to
$Q=4$ filters, i.e., identity $\boldsymbol{\mathbf{I}}$, monomial
$\boldsymbol{\mathbf{I}}-\tilde{\boldsymbol{\mathbf{L}}}$, Chebyshev, and
Bernstein bases for the filter bank. In the first unsupervised stage, an
embedding function $\gamma_{q}:\mathbb{R}^{n\times
F}\rightarrow\mathbb{R}^{n\times F}$ is learned for each filter by maximizing
the mutual information across all channels. The second stage of supervised
graph representation learning fine-tunes another scalar weight
$\gamma_{q}^{\prime}$ to tailor for the downstream task, along with other
trainable model parameters. Formulation of the eventual FiGURe filter can be
written as:

$\mathscr{g}(\tilde{\boldsymbol{\mathbf{L}}};\gamma,\theta)=\sum_{q=1}^{\mathit{Q}}\gamma_{q}^{\prime}\gamma_{q}\cdot
g_{q}(\tilde{\boldsymbol{\mathbf{L}}};\theta),\quad
g_{q}(\tilde{\boldsymbol{\mathbf{L}}};\theta)=\sum_{k=0}^{K}\theta_{q,k}\,T_{q}^{(k)}(\tilde{\boldsymbol{\mathbf{L}}}),$

###  B.4 Other Relevant GNN Models

#### Efficient Computation.

There is a line of studies focusing on the efficient and scalable computation
of spectral filters, particularly fixed ones, rather than proposing novel
filters, including: PPRGo [58] (PPR), GBP [59] (PPR), SCARA [73, 60] (PPR),
DGC [34] (HK), AGP [18] (PPR, HK, monomial), GRAND+ [19] (impulse, PPR,
monomial). We omit them in above analysis for clearer representation, while it
is noteworthy that some efficient computation and data augmentation techniques
from them have been incorporated into our implementation and evaluation of
spectral GNNs.

#### Spectral Decomposition.

Unlike polynomial filters, conventional spectral GNNs perform explicit eigen-
decomposition to acquire graph spectrum
$\tilde{\boldsymbol{\mathbf{L}}}=\boldsymbol{\mathbf{U}}\boldsymbol{\mathbf{\Lambda}}\boldsymbol{\mathbf{U}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$
and apply graph convolution $\hat{g}(\boldsymbol{\mathbf{\Lambda}})$
accordingly. Representative works include SpectralCNN [1], LanczosNet [74],
CayleyNet [75], and SIGN [76], which all leverage spectral operations
depending on the full spectrum. Alternatively, Specformer [77] exploits a
transformer model to establish expressive spectral filtering.

Nonetheless, we note that the full eigen-decomposition is largely prohibitive,
resulting in weaker applicability of these models, especially on large graphs.
Hence, we do not include them in our benchmark evaluation, while comparison
for these models can be found in [17] and [16].

#### Alternative Spectral Transforms.

Beside graph Fourier transform, recent research introduce other techniques
from signal processing. GWNN [78] utilizes graph wavelet transforms for better
locality, which is extended by UFG [79] to framelets. PyGNN [80] employs
pyramid transforms with a down-sampling, filtering, and up-sampling pipeline.
These models are excluded in our evaluation as they also rely on complex
spectral operations involving matrix decomposition, and no implementation to
large datasets is available. We refer interested readers to [62] for graph
transformation and filter computation beyond polynomial approximation.

#### Task-Specific Models.

These methods set the stage for adapting the spectral properties or filtering
pipelines to particular tasks, instead of focusing on novel filter designs.
GHRN [81] explores the heterophily in the spatial domain and the frequency in
the spectral domain, which efficiently addresses the heterophily issue for
graph anomaly detection. StableGCNN [82] provides a theoretical spectral
perspective of existing GNN models which aims to analyze their stability and
establish their generalization guarantees. SpecGN [83] applies a smoothing
function on the graph spectrum to alleviate correlation among signals. DSGC
[84] explores the utility of the spectrum of both node and attribute affinity
graphs.

##  Appendix C Related GNN Surveys and Benchmarks

A line of surveys develop the fundamental taxonomy of GNN models based on
architectural selections, categorizing convolutional and sequential designs
[85, 86, 87]. Although some classic spectral models such as ChebNet are
included in these surveys, they are not distinguished from other spatial
models. [88, 89, 90, 91] focus on the efficient computational designs of GNNs
and cover techniques such as sampling, sparsification, and quantization.
However, most of these algorithms only have spatial interpretations, which are
orthogonal to the spectral perspective in our work. [92, 6] are surveys with
heterophily-oriented reviews and analysis.

Two recent surveys specifically target spectral GNNs: [16] derives the general
connection between common spatial and spectral operators, rendering three
levels of operators, i.e., linear, polynomial, and rational ones. Our spectral
analysis of models is primarily based on the theory in this work. As
elaborated in respective filter analysis before, we mainly highlight the
polynomial formulation since rational filters are usually reduced to it in
practice, and the linear filter is simply a special case. [17] reviews over 10
spectral models theoretically and empirically. However, their framework relies
on the eigen-decomposition of the full spectrum, which is constrained to small
graphs. In Appendix E, we ensure that our efficacy evaluation result is on par
with theirs, while we extend to large-scale datasets with efficiency
comparison.

On the practical side, [93] is a preliminary work for benchmarking about 10
GNN models in different tasks, while [13] and [94] respectively address
pitfalls of GNN evaluation in synthetic data and link prediction tasks. [14,
91] both offer large-scale GNN learning frameworks with collections of spatial
acceleration techniques. Overall, we note that there is a lack of reviews
comprehensively covering the up-to-date spectral models, especially those
featuring spectral-oriented evaluation and scalable implementation, which
highlight the contribution of this benchmark study.

##  Appendix D Experiment Settings

###  D.1 Implementation Design

Our framework design is based on the popular graph learning library PyTorch
Geometric (PyG) [95] with the same arrangement of components. We list the
following highlights of our framework compared to PyTorch Geometric and
similar works [14, 91]:

  * •

Plug-and-play modules: The model and layer implementation in our framework
follows the same design as PyTorch Geometric, implying that they can be
seamlessly integrated into PyG-based programs. Our rich collection of spectral
models and filters greatly extends the PyG model zoo.

  * •

Separated spectral kernels: We decouple non-spectral designs and feature the
pivotal spectral filters being consistent throughout different settings. Most
of the filters are thence applicable to be combined with various network
architectures, learning schemes, and other toolkits, including those provided
by PyG and PyG-based frameworks.

  * •

High scalability: As spectral GNNs are inherently suitable for large-scale
learning, our framework is feasible to common scalable learning schemes and
acceleration techniques. Several spectral-oriented approximation algorithms
are also supported.

We further elaborate on our code structure in Figure 4 by comparing
corresponding components in PyG:

  * •

We implement the spectral filters as nn.conv modules, which are pivotal and
basic blocks for building spectral GNNs. This is similar to the implementation
of spatial layers in PyG.

  * •

On the model level, common architectures formulated in Appendix A are included
in nn.models. Since these models are built in PyG style, they can seamlessly
access other utility interfaces offered by PyG and PyG-based toolkits.

  * •

Regarding the underlying backend for sparse matrix multiplication in graph
propagation, we support PyTorch-based computations inherited from PyG, as well
as extendable interfaces for scalable C++-based algorithms specialized for
spectral filtering.

  * •

Additionally, we include our reproducible benchmark pipeline for training and
evaluating the models, with a particular focus on spectral analysis as well as
scalable mini-batch training.

Figure 4: Code structure of our framework and relation to PyG.

Evaluation are conducted on a single machine with 32 Intel Xeon CPUs (2.4GHz),
an Nvidia A30 (24GB memory) GPU, and 512GB RAM.

Table 6: Dataset statistics. $d$, $F$, $N_{c}$, and $\mathcal{H}$ are average
degree, input attribute dimension, number of label classed, and node homophily
score.

Scale Hetero. Dataset Nodes $n$ Edges $m$ $d$ $F$ $N_{c}$ $\mathcal{H}$ Metric
Small Homo. cora [96] 2,708 10,556 3.898 1,433 7 0.825 Accuracy citeseer [96]
3,327 9,104 2.736 3,703 6 0.717 Accuracy pubmed [96] 19,717 88,648 4.496 500 3
0.792 Accuracy flickr [97] 7,600 30,019 3.950 932 5 0.221 Accuracy Hetero.
actor [98] 7,600 30,019 3.950 932 5 0.221 Accuracy chameleon [98] 890 17,708
19.897 2,325 5 0.244 Accuracy squirrel [98] 2,223 93,996 42.283 2,089 5 0.190
Accuracy roman-empire [99] 22,662 65,854 2.906 300 18 0.046 Accuracy
minesweeper [99] 10,000 78,804 7.880 7 2 0.683 ROC AUC amazon-ratings [99]
24,492 186,100 7.598 300 5 0.376 Accuracy questions [99] 48,921 307,080 6.277
301 2 0.898 ROC AUC tolokers [99] 11,758 1,038,000 88.280 10 2 0.634 ROC AUC
Medium Homo. ogbn-arxiv [100] 169,343 1,166,243 6.887 128 40 0.632 Accuracy
ogbn-mag [100] 736,389 5,416,271 7.355 128 349 0.315 Accuracy Hetero. arxiv-
year [101] 169,343 1,166,243 6.887 128 5 0.310 Accuracy penn94 [101] 41,554
2,724,458 65.564 4,814 2 0.483 Accuracy genius [101] 421,961 984,979 2.334 12
2 0.830 ROC AUC twitch-gamer [101] 168,114 6,797,557 40.434 7 2 0.973 ROC AUC
Large Homo. ogbn-products [100] 2,449,029 123,718,280 50.517 100 47 0.833
Accuracy Hetero. pokec [101] 1,632,803 30,622,564 18.755 65 2 0.448 Accuracy
snap-patents [101] 2,923,922 13,972,555 4.779 269 5 0.266 Accuracy wiki [101]
1,925,342 303,434,860 157.600 600 5 0.283 Accuracy

###  D.2 Datasets Statistics

#### Data Processing.

Our benchmark experiment include 22 node classification datasets in total.
Details of the datasets are listed in Table 6. In the table, we incorporate
self-loop edges and count undirected edges twice to better reflect the
propagation overhead. Specifically, chameleon and squirrel are processed based
on the new protocol [99], and ogbn-mag is tailored to its homogeneous portion.
Directed edges are only considered in arxiv-year and snap-patents as per
[101], while all other graphs are transformed to undirected ones.

#### Heterophily Evaluation.

Note that although we divide the datasets into homophilous and heterophilous
ones, graph heterophily should be considered as a continuous property measured
by metrics such as heterophily score. Hence, we utilize the node homophily
score $\mathcal{H}$ [98] to further measure graph homophily/heterophily as a
reference. A homophily score closer to $0$ indicates higher heterophily, and
vice versa.

#### Graph Scales.

We consider three levels of dataset scales for clearer presentation in
experiments. The criteria is mainly as follows:

  * •

Small-scale datasets: This set of datasets are mainly utilized for efficacy
evaluation of all models and schemes. Since the graph sizes are relatively
small, results regarding efficiency are omitted in this study, while they can
be similarly produced using the published codebase.

  * •

Medium-scale datasets: Experiments on these datasets share the same settings
with small-scale ones. However, we include the efficiency study to provide
comparable results across different models and training schemes.

  * •

Large-scale datasets: This category of graphs is mainly only applicable to the
mini-batch scheme, as most full-batch models occur out-of-memory error. Some
hyperparameters are also separated to ensure efficient learning performance.

#### Data Splits.

The train/validation/test sets are randomly generated with 60%/20%/20% split
for each run by default, following the majority settings in spectral GNN
research. OGBN and LINKX graphs maintain their original splits. We conduct 10,
10, and 5 runs with different random seeds for small-, medium-, and large-
scale evaluations in the main experiment, respectively, and report the average
metrics on test split with standard deviation.

###  D.3 Model Setup

#### Model Architecture.

We utilize a unified architecture for all models in our evaluation, which is
scalable to larger graphs while maintaining efficacy. This mainly incorporates
the decoupled design, i.e., having fixed or learnable scalars $\theta_{k}$ as
parameters. In the spatial interpretation, the decoupled architecture implies
performing all graph propagations successively, and transformations conducted
by learnable weight matrices are only performed before or after all
propagation operations.

#### Hyperparameter Search.

In order to ensure a fair comparison of both effectiveness and efficiency, we
employ a two-step hyperparameter tuning scheme:

  * •

First, we search for hyperparameters possessing significant impacts on the
model efficiency, including the number of hops $K$ and hidden dimension $F$.
To ensure comparable total running times, the epoch number is kept constant at
500.

  * •

Then, we utilize a fixed choice of these critical hyperparameters for
experiments across all models and datasets, and perform specific search on
other hyperparameters for each respective experiment.

The hyperparameters in each stage, search ranges, and used values are listed
in Table 7. Configuration files are also available in our online repository.

Table 7: Hyperparameter search scheme. Hyperparameters are explored based on the combination of listed ranges, and underlined values in Stage 1 are the universal settings used across main experiments.  Stage 1 | Full-batch | Mini-batch | Mini-batch
---|---|---|---
Small/medium-scale | Small/medium-scale | Large-scale
Propagation hop $K$ | 2, 4, $\cdots$, 10, $\cdots$, 30 | 2, 4, $\cdots$, 10, $\cdots$, 30 | 2, 4, $\cdots$, 10, $\cdots$, 30
Hidden width $F$ | 16, 32, 64, 128, 256 | 16, 32, 64, 128, 256 | 16, 32, 64, 128, 256
Linear layer of $\phi_{0}$ |  1, 2, 3 | 0 | 0
Linear layer of $\phi_{1}$ |  1, 2, 3 | 1, 2, 3 | 1, 2, 3
Batch size | – | 4,096 | 200,000
Stage 2 |  |  |
Graph normalization $\rho$ | $[0,1]$ | $[0,1]$ | $[0,1]$
Learning rate of $\phi_{0},\phi_{1}$ | $[10^{-5},0.5]$ | $[10^{-5},0.5]$ | $[10^{-5},0.5]$
Learning rate of $\theta,\gamma$ | $[10^{-5},0.5]$ | $[10^{-5},0.5]$ | $[10^{-5},0.5]$
Weight decay of $\phi_{0},\phi_{1}$ | $[10^{-7},10^{-3}]$ | $[10^{-7},10^{-3}]$ | $[10^{-7},10^{-3}]$
Weight decay of $\theta,\gamma$ | $[10^{-7},10^{-3}]$ | $[10^{-7},10^{-3}]$ | $[10^{-7},10^{-3}]$

##  Appendix E Full Experiment Results

###  E.1 Full-batch Learning

The efficacy results for full-batch filters with their respective metrics on
datasets other than Table 2 are presented in Table 8. “OOM” in the table means
the out-of-memory error on a single $24$\mathrm{G}\mathrm{B}$$ GPU. For
datasets larger than pokec, most models incur the OOM issue with full-batch
training, hence results are not included. Results in Tables 2 and 8 are
aligned with previous evaluations containing spectral filters such as [101,
99, 17] and are mostly comparable with their original papers.

Efficiency evaluation of all full-batch models is shown in Table 9. Note that
obgn-arxiv and arxiv-year share the same underlying graph structure, so we
only present the efficiency performance on obgn-arxiv. Specifically, it can be
observed that simple variable filters (Mono, Cheb) and filter banks composing
fixed filters (G2CN, GNN-LF/HF) sometimes achieve comparable efficiency with
fixed filters. The RAM overhead is mostly constant since the training is
mainly performed on the GPU.

Table 8: Effectiveness results (%) and standard deviations of spectral filters
with full-batch training on remaining datasets. For each dataset, highlighted
results are filters with average scores ranked first, second, and third.

Filter arxiv mag ratings mine. tolokers questions penn94 year genius twitch
pokec Identity 54.63±0.36 25.79±0.32 37.87±1.16 50.98±2.14 73.48±0.60
71.05±1.44 75.28±0.47 35.32±0.46 86.07±0.22 99.90±0.03 62.19±0.14 Linear
52.32±5.86 30.21±0.89 40.12±1.27 68.55±1.68 76.11±1.74 56.81±4.45 65.10±4.36
43.59±0.57 76.06±0.87 82.37±3.98 52.13±0.93 Impulse 58.31±5.01 29.66±1.17
42.45±0.72 64.15±1.92 69.03±4.93 73.91±1.46 55.03±3.90 37.51±1.27 73.01±0.62
78.30±1.66 53.06±0.91 Monomial 57.94±0.75 30.01±0.65 44.10±1.74 69.43±1.51
79.02±0.97 74.31±6.21 73.91±2.48 46.81±0.36 88.35±0.17 99.65±0.06 60.31±0.58
PPR 61.63±0.85 29.65±0.50 42.32±2.08 69.28±1.77 77.55±0.82 58.61±4.98
74.63±0.89 44.89±0.92 87.63±0.33 99.74±0.08 61.03±0.69 HK 61.62±1.04
26.26±0.59 41.69±1.11 73.44±2.36 78.33±0.90 62.17±5.89 74.60±0.46 45.88±2.03
87.60±0.63 97.84±2.39 58.99±2.43 Gaussian 61.69±0.94 26.80±0.78 43.92±1.76
73.26±2.20 78.43±0.86 72.01±3.83 75.36±0.35 43.87±0.93 86.72±0.54 99.97±0.01
60.83±0.75 Linear 63.10±1.82 33.13±0.42 44.40±1.55 72.43±1.64 73.44±3.54
65.85±4.95 67.26±5.46 35.92±4.09 86.11±0.55 70.63±9.64 (OOM) Monomial
68.18±0.61 32.62±0.70 40.76±2.12 89.29±0.48 78.77±0.74 64.63±4.18 84.08±1.47
35.66±5.66 87.28±1.31 97.59±2.38 59.67±0.96 Horner 61.19±1.41 31.71±0.55
39.60±1.05 89.27±0.53 77.81±0.79 62.10±6.48 84.94±0.33 40.21±1.39 87.46±0.51
97.89±3.06 77.14±1.20 Chebyshev 60.33±2.74 28.17±1.71 41.66±1.14 89.95±0.48
78.35±1.80 67.09±5.56 82.62±0.60 37.34±1.87 86.53±2.07 99.72±0.12 77.55±0.16
Clenshaw 52.84±4.84 30.24±1.31 42.33±1.19 89.79±0.50 78.59±1.28 64.51±2.04
69.72±14.91 42.14±2.36 87.60±0.66 90.64±1.45 74.69±2.18 ChebInterp 50.89±6.19
26.07±0.85 39.18±3.04 89.47±0.53 77.63±1.92 60.19±7.43 81.96±0.90 36.44±1.81
87.20±1.84 92.26±7.25 77.45±0.74 Bernstein 49.71±1.01 16.89±0.46 35.86±1.34
82.21±1.49 78.12±1.21 54.36±3.61 76.26±3.29 38.96±1.46 77.96±1.40 98.28±1.23
73.07±0.07 Legendre 63.01±2.55 30.82±0.60 39.42±1.08 89.73±0.69 79.68±0.81
64.74±1.60 82.49±1.60 41.79±4.87 85.22±0.27 90.83±6.24 56.34±4.18 Jacobi
61.14±2.66 29.33±0.79 42.70±0.90 89.76±0.44 79.13±0.90 65.56±4.80 82.59±1.40
42.44±5.39 88.07±1.29 97.97±3.12 51.09±0.64 Favard 68.05±1.03 34.07±0.25
39.80±0.97 89.96±0.47 79.68±2.04 55.19±4.53 84.15±0.51 41.16±6.56 85.30±0.23
99.66±0.17 (OOM) OptBasis 44.63±7.28 (OOM) 36.66±0.90 89.58±0.69 61.65±4.78
64.17±5.71 82.41±2.98 42.40±1.85 73.85±7.55 82.74±2.45 (OOM) AdaGNN 52.44±0.23
29.26±0.76 38.88±1.03 85.89±2.06 72.14±3.13 68.85±4.07 75.12±0.62 48.30±0.40
77.25±3.21 98.08±4.54 73.76±0.08 FBGNNI 69.11±0.70 (OOM) 43.53±1.26 89.05±0.94
79.21±1.21 52.16±2.20 74.04±1.35 45.66±4.18 85.36±0.42 97.96±0.64 (OOM)
FBGNNII 71.29±0.42 (OOM) 39.78±1.22 84.33±4.05 76.12±0.91 67.22±5.24
74.14±0.84 48.91±0.41 87.54±0.86 99.65±0.21 (OOM) ACMGNNI 69.64±0.41 (OOM)
43.79±1.77 88.13±1.29 77.55±0.64 63.86±3.70 73.91±1.25 48.91±0.63 86.14±3.94
98.88±0.27 (OOM) ACMGNNII 69.87±0.49 (OOM) 43.87±1.46 87.30±3.18 83.79±0.89
66.05±1.59 75.04±0.72 47.20±1.06 87.73±0.32 98.71±0.52 (OOM) FAGNN 62.21±5.17
31.73±0.87 41.54±1.43 68.91±1.61 73.26±2.90 68.28±2.31 56.36±3.60 43.31±0.37
75.28±0.93 82.96±2.13 51.15±0.78 G2CN 56.63±1.83 32.79±0.29 40.22±1.26
68.85±1.42 77.95±0.71 63.90±4.08 77.35±6.21 44.93±0.50 86.62±1.08 99.87±0.03
67.62±0.35 GNN-LF/HF 63.47±2.00 31.58±1.28 37.13±1.47 77.66±1.43 77.95±1.15
66.33±7.36 75.62±0.91 46.05±0.43 88.45±0.48 97.13±1.47 60.38±0.99 FiGURe
61.93±1.50 31.49±0.56 40.08±0.98 89.38±0.72 77.96±0.84 62.38±4.43 81.13±0.84
35.94±5.27 88.00±1.13 90.67±2.84 (OOM)

Table 9: Time and memory efficiency of full-batch training on medium-scale
datasets. “Train” and “Infer” respectively refer to average training time per
epoch and inference time ($\mathrm{m}\mathrm{s}$), while “RAM”, and “GPU”
respectively refer to peak RAM and GPU memory ($\mathrm{G}\mathrm{B}$). For
each column, highlighted ones are results ranked first, second, and third
within the error interval. .

Filter arxiv mag penn94 Train Infer RAM GPU Train Infer RAM GPU Train Infer
RAM GPU Linear 96.2±0.6 7.2±0.1 1.7±0.2 0.9±0.0 509.6±0.6 10.8±0.7 3.0±0.2
7.3±0.0 67.0±0.5 4.9±0.1 3.6±0.3 1.1±0.0 Impulse 79.1±0.6 7.0±0.5 1.7±0.2
0.8±0.0 435.2±0.7 10.5±0.3 3.0±0.2 7.3±0.0 59.3±0.5 5.0±0.0 3.6±0.2 1.1±0.0
Monomial 79.7±0.7 7.7±2.5 1.7±0.2 0.9±0.0 436.0±0.8 10.8±1.1 3.0±0.2 7.3±0.0
59.3±0.5 5.0±0.1 3.6±0.2 1.1±0.0 PPR 79.9±0.5 7.2±0.6 1.7±0.2 0.9±0.0
435.5±0.6 11.0±1.2 3.0±0.2 7.3±0.0 59.4±0.5 5.1±0.1 3.6±0.3 1.1±0.0 HK
79.4±0.7 6.9±0.5 1.7±0.2 0.8±0.0 435.6±1.5 10.8±0.7 3.0±0.2 7.2±0.0 58.8±0.7
5.2±0.1 3.6±0.2 1.1±0.0 Gaussian 79.2±0.6 7.0±0.3 1.7±0.2 0.8±0.0 437.0±1.1
13.9±7.5 3.0±0.2 7.3±0.0 58.7±0.6 5.1±0.0 3.6±0.2 1.1±0.0 Var-Lin 106.8±0.7
7.7±1.9 1.7±0.2 2.4±0.0 552.9±1.5 11.0±1.0 3.0±0.2 15.0±0.0 70.5±1.0 8.2±0.8
3.6±0.2 1.5±0.0 Var-Mono 85.2±0.7 6.9±0.2 1.8±0.2 1.5±0.0 453.5±0.8 10.4±0.3
3.0±0.2 11.2±0.0 60.8±0.3 7.4±0.5 3.7±0.2 1.3±0.0 Horner 109.9±0.8 10.0±1.9
1.7±0.2 1.9±0.0 560.6±1.0 13.2±0.8 3.0±0.2 11.5±0.0 67.9±1.0 11.5±6.5 3.7±0.2
1.3±0.0 Chebyshev 92.5±0.7 8.7±1.6 1.7±0.2 1.6±0.0 477.3±1.0 11.9±0.7 3.0±0.2
10.0±0.0 63.3±1.2 8.9±0.5 3.7±0.2 1.3±0.0 Clenshaw 123.4±0.6 10.9±0.5 1.7±0.2
1.8±0.0 623.0±0.7 14.3±1.5 3.0±0.2 11.5±0.0 71.7±1.4 10.8±0.6 3.6±0.2 1.3±0.0
ChebInterp 115.2±0.8 14.6±2.0 1.7±0.2 1.6±0.0 515.5±0.8 17.2±1.2 3.0±0.2
11.3±0.0 81.9±1.0 11.4±1.1 3.7±0.2 1.3±0.0 Bernstein 178.8±0.7 9.5±0.8 1.7±0.2
1.8±0.0 973.1±1.1 14.7±2.5 3.0±0.2 11.4±0.0 121.9±0.6 10.6±1.1 3.7±0.2 1.3±0.0
Legendre 100.4±0.8 9.2±0.2 1.7±0.2 1.6±0.0 514.1±1.3 12.9±0.3 3.0±0.2 9.9±0.0
64.8±0.9 10.0±0.3 3.7±0.2 1.3±0.0 Jacobi 110.5±0.6 9.2±0.3 1.7±0.2 1.7±0.0
568.3±2.5 12.8±0.6 3.0±0.2 11.2±0.0 67.8±0.7 9.8±1.2 3.7±0.2 1.3±0.0 Favard
135.8±1.0 10.2±0.5 1.7±0.2 2.6±0.0 664.7±1.3 14.8±3.6 3.0±0.2 14.1±0.0
74.8±1.3 11.6±2.2 3.6±0.2 1.5±0.0 OptBasis 348.5±0.8 13.8±0.8 1.8±0.2 4.2±0.0
(OOM) 112.1±0.8 13.4±1.6 3.6±0.2 1.9±0.0 AdaGNN 87.8±0.8 5.8±0.2 1.7±0.2
1.6±0.0 453.0±0.8 9.4±0.3 3.0±0.2 9.7±0.0 61.6±0.5 6.7±0.3 3.6±0.2 1.3±0.0
FBGNNI 372.4±2.6 14.9±3.1 1.7±0.2 7.1±0.0 (OOM) 186.6±5.1 16.5±2.7 3.6±0.3
2.6±0.0 FBGNNII 363.8±2.8 13.5±0.4 1.7±0.2 8.8±0.0 (OOM) 182.4±0.9 14.4±2.2
3.6±0.3 3.1±0.0 ACMGNNI 365.3±0.8 18.7±4.8 1.7±0.2 7.1±0.0 (OOM) 183.0±1.5
14.5±2.1 3.6±0.3 2.6±0.0 ACMGNNII 370.1±1.2 16.2±7.3 1.7±0.2 8.8±0.0 (OOM)
182.3±1.4 15.3±2.2 3.6±0.3 3.1±0.0 FAGNN 186.1±0.8 9.6±0.2 1.7±0.2 0.9±0.0
936.2±1.3 13.7±1.8 3.0±0.2 7.7±0.0 127.4±0.9 5.2±0.1 3.6±0.2 1.1±0.0 G2CN
94.5±1.4 7.6±0.1 1.7±0.2 1.0±0.0 503.3±1.5 10.9±0.5 3.0±0.2 7.7±0.0 69.9±0.9
4.9±0.1 3.6±0.2 1.1±0.0 GNN-LF/HF 171.9±1.8 9.1±2.0 1.7±0.2 0.9±0.0 864.5±2.3
11.9±0.6 3.1±0.2 7.9±0.0 124.0±0.6 6.2±0.2 3.6±0.2 1.1±0.0 FiGURe 352.7±8.9
13.2±1.7 1.7±0.2 3.6±0.0 1768.7±1.3 136.3±9.9 3.0±0.2 19.7±0.0 234.3±1.0
13.1±1.2 3.6±0.2 1.8±0.0 Filter genius twitch pokec Linear 134.2±0.5 7.0±0.4
1.6±0.1 1.7±0.0 310.8±1.0 7.3±0.2 2.5±0.2 1.4±0.0 1402.2±0.7 8.5±0.4 6.8±0.2
8.4±0.0 Impulse 103.2±0.5 6.9±0.3 1.6±0.1 2.0±0.0 273.2±0.6 6.8±0.5 2.5±0.2
1.4±0.0 1195.7±1.0 9.9±4.2 6.8±0.2 8.4±0.0 Monomial 103.0±0.4 6.9±0.1 1.6±0.1
2.0±0.0 272.4±0.9 6.9±0.4 2.5±0.2 1.4±0.0 1196.1±1.0 8.7±0.2 6.8±0.2 8.4±0.0
PPR 102.3±0.5 8.0±3.1 1.6±0.1 1.7±0.0 272.5±1.1 7.8±3.0 2.5±0.2 1.4±0.0
1187.1±1.0 8.5±0.3 6.8±0.2 8.4±0.0 HK 120.7±5.3 9.1±2.9 1.6±0.1 2.0±0.0
272.9±0.7 6.8±0.3 2.5±0.2 1.4±0.0 1189.8±1.0 10.1±5.8 6.8±0.2 7.4±0.0 Gaussian
107.2±6.6 7.9±1.5 1.6±0.1 1.5±0.0 272.7±1.2 7.6±1.9 2.5±0.2 1.4±0.0 1193.1±0.4
8.7±0.3 6.8±0.2 8.4±0.0 Var-Lin 159.0±0.7 7.3±0.7 1.6±0.1 5.8±0.0 320.4±1.2
7.9±1.8 2.5±0.2 3.0±0.0 (OOM) Var-Mono 114.3±1.0 6.9±0.4 1.6±0.1 3.6±0.0
277.7±1.3 7.6±1.8 2.5±0.2 2.2±0.0 1233.6±1.2 8.9±0.5 6.5±0.4 14.9±0.0 Horner
174.6±0.8 9.6±0.6 1.6±0.1 4.4±0.0 302.9±0.6 10.8±2.5 2.5±0.2 2.2±0.0
1474.1±1.0 30.8±7.4 6.6±0.4 17.7±0.0 Chebyshev 135.2±4.1 9.1±1.3 1.6±0.1
3.7±0.0 285.6±0.8 8.2±0.5 2.5±0.2 2.4±0.0 1313.7±1.6 9.6±0.5 6.6±0.4 16.2±0.0
Clenshaw 207.9±0.9 10.9±0.7 1.6±0.1 4.6±0.0 321.6±1.1 11.3±0.5 2.5±0.2 2.3±0.0
1619.5±1.0 88.4±4.4 6.6±0.4 18.5±0.0 ChebInterp 155.1±1.9 17.4±6.9 1.6±0.1
3.7±0.0 321.1±1.2 15.8±2.1 2.5±0.2 2.4±0.0 1410.6±0.6 16.6±1.4 6.6±0.4
16.2±0.0 Bernstein 242.5±1.2 10.4±1.8 1.6±0.1 4.3±0.0 627.5±1.8 10.1±1.2
2.5±0.2 2.5±0.0 2963.6±2.6 42.3±2.0 6.7±0.4 18.0±0.0 Legendre 153.0±1.6
10.1±1.0 1.6±0.1 3.8±0.0 294.0±1.3 10.3±2.2 2.5±0.2 2.2±0.0 1389.2±3.9
26.2±26.5 6.6±0.4 15.8±0.0 Jacobi 180.4±1.9 10.2±0.5 1.6±0.1 3.8±0.0 302.5±0.8
9.3±0.4 2.5±0.2 2.3±0.0 1488.2±1.9 39.7±19.3 6.6±0.4 16.6±0.0 Favard 239.8±1.2
11.6±3.0 1.6±0.1 6.2±0.0 332.1±2.0 11.0±3.2 2.5±0.2 3.2±0.0 (OOM) OptBasis
957.3±0.7 13.2±0.4 1.6±0.1 10.0±0.0 546.3±1.4 13.1±0.6 2.6±0.2 4.6±0.0 (OOM)
AdaGNN 119.1±0.7 6.6±2.7 1.6±0.1 3.6±0.0 280.9±1.3 6.8±2.1 2.5±0.2 2.2±0.0
1249.7±2.0 7.3±0.5 6.7±0.3 14.6±0.0 FBGNNI 694.3±1.0 17.6±1.3 1.6±0.2 17.3±0.0
826.7±5.5 43.8±20.0 2.5±0.3 7.7±0.0 (OOM) FBGNNII 693.5±3.4 14.7±2.5 1.6±0.2
21.7±0.0 822.2±6.7 23.5±15.4 2.5±0.3 9.5±0.0 (OOM) ACMGNNI 692.7±1.7 13.6±0.2
1.6±0.2 17.3±0.0 824.2±14.1 19.5±7.5 2.5±0.3 7.7±0.0 (OOM) ACMGNNII 694.6±2.1
18.0±8.9 1.6±0.2 21.7±0.0 822.5±3.2 16.4±5.3 2.5±0.3 9.5±0.0 (OOM) FAGNN
263.2±1.1 10.4±3.9 1.6±0.1 2.2±0.0 631.1±2.7 9.3±0.6 2.5±0.2 1.5±0.0
2840.0±0.7 11.3±0.2 6.6±0.4 9.1±0.0 G2CN 120.7±1.0 7.9±0.6 1.6±0.1 1.9±0.0
325.8±1.4 7.7±0.4 2.5±0.2 1.4±0.0 1431.4±0.5 22.1±12.9 6.6±0.4 9.1±0.0 GNN-
LF/HF 222.2±1.6 9.1±2.0 1.6±0.1 2.2±0.0 616.4±1.0 8.4±0.9 2.5±0.2 1.8±0.0
2685.1±1.3 10.1±1.2 6.6±0.4 10.2±0.0 FiGURe 481.5±1.4 12.4±0.3 1.7±0.1 8.7±0.0
1216.3±3.6 14.7±5.2 2.5±0.2 4.5±0.0 (OOM)

###  E.2 Mini-batch Learning

Table 10 displays the efficacy results of applicable spectral filters under
mini-batch training across all datasets. Compared to Tables 2 and 8, most
filters achieve similar performance. In particular, the highest accuracy on
each dataset is on par with the one under full-batch learning. The differences
in certain models may be caused by the difficulty in convergence, given that
the simple transformation model is relatively sensitive to the extreme values
in inputs.

Mini-batch training efficiency is shown in Table 11 with the separated
precomputation process. In terms of memory, the precomputation and training
stages share a similar RAM overhead mainly for maintaining intermediate
representations. Hence, we only show the maximum memory in the table.

Table 10: Effectiveness results (%) and standard deviations of spectral
filters with mini-batch training on all datasets. For each dataset,
highlighted results are filters with average scores ranked first, second, and
third.

Filter cora citeseer pubmed flickr products chameleon squirrel actor roman
snap wiki Identity 66.54±2.35 67.10±1.79 87.48±0.56 35.37±1.21 26.62±0.04
29.10±5.13 24.98±2.41 34.86±1.46 66.21±0.54 30.39±0.03 35.21±0.13 Linear
85.29±1.27 74.66±1.11 84.96±0.50 25.04±1.10 26.59±0.01 38.09±3.13 38.33±2.46
25.99±1.07 38.26±0.43 45.33±0.19 37.69±0.42 Impulse 86.04±1.76 74.14±1.04
84.03±0.51 24.45±0.95 26.16±0.75 39.83±2.21 38.94±1.78 24.32±1.60 31.52±0.45
53.56±0.18 32.88±1.47 Monomial 86.30±1.54 74.66±1.88 89.46±0.47 32.60±1.54
26.59±0.00 37.70±2.16 34.91±0.89 32.64±1.41 71.64±0.67 42.83±1.12 23.07±2.46
PPR 87.19±1.72 75.53±1.50 88.73±0.46 32.18±0.90 26.91±0.44 40.73±2.78
34.89±1.29 32.49±1.22 73.21±0.66 47.83±3.67 22.40±2.00 HK 86.60±1.39
74.76±0.96 89.39±0.41 32.82±1.51 26.61±0.76 41.63±3.14 36.37±1.94 32.88±1.39
72.43±0.79 50.99±0.16 43.06±0.30 Gaussian 67.86±1.81 74.44±1.23 88.70±0.55
32.89±0.88 26.59±0.00 39.08±2.93 35.32±1.60 32.84±1.28 70.91±0.71 52.58±0.04
42.81±0.45 Var-Linear 76.36±0.79 71.79±1.40 87.60±0.47 35.29±1.31 26.49±0.23
37.36±3.17 34.93±1.94 35.72±0.88 65.42±0.61 30.47±0.34 38.98±0.51 Var-Monomial
87.41±1.24 76.26±1.35 89.83±0.53 34.11±1.46 26.82±0.42 33.99±3.79 35.07±2.04
34.81±1.34 65.55±2.65 50.35±0.07 31.34±0.48 Horner 86.64±1.63 75.33±0.80
84.17±0.46 23.78±2.09 26.59±0.00 36.40±2.74 36.62±1.69 25.49±1.47 22.08±1.44
38.73±1.71 31.42±0.37 Chebyshev 87.89±0.87 75.71±1.63 90.06±0.33 30.92±1.47
26.58±0.01 34.27±3.39 34.23±1.21 29.89±1.82 71.09±2.54 42.83±0.96 24.26±2.39
Clenshaw 80.83±2.22 72.60±0.96 75.75±1.07 24.82±1.62 26.59±0.00 35.06±2.57
35.18±0.97 23.93±0.55 22.37±0.56 47.18±0.20 31.25±0.10 ChebInterp 84.70±3.59
74.73±1.89 89.28±0.43 30.27±1.08 28.11±1.17 28.37±3.09 34.62±1.98 30.36±1.22
50.69±7.82 45.77±0.56 23.85±1.84 Bernstein 82.05±1.46 69.18±1.83 85.46±0.45
33.55±1.11 26.59±0.17 39.61±3.21 35.68±2.35 30.68±1.05 63.54±2.98 48.67±0.28
24.54±1.95 Legendre 87.43±1.00 76.17±1.02 89.84±0.29 33.95±1.37 27.10±0.36
38.70±2.49 36.15±2.02 33.05±1.45 69.74±0.72 42.94±0.54 31.16±0.40 Jacobi
87.17±1.50 75.34±1.26 89.75±0.33 34.20±1.27 24.37±3.14 38.54±3.73 35.86±1.80
33.32±2.14 71.99±0.83 53.37±2.23 33.25±3.10 OptBasis 82.20±2.46 73.11±1.23
88.23±1.10 30.97±1.54 26.56±0.06 38.09±2.54 35.00±1.62 29.34±1.61 72.93±1.11
57.49±2.42 30.87±3.11 FAGNN 86.95±1.13 75.07±1.05 85.25±0.28 25.16±1.95
25.34±1.44 39.66±2.47 37.91±2.05 28.23±1.78 26.61±0.84 39.29±0.66 31.23±0.55
G2CN 86.51±1.79 75.05±1.11 84.42±0.51 25.14±1.46 26.59±0.00 40.79±3.47
39.08±2.93 21.47±0.88 24.54±1.19 26.85±0.02 38.66±0.10 GNN-LF/HF 87.36±1.02
75.95±1.35 89.76±0.39 33.57±1.36 25.80±0.91 40.66±2.14 34.75±1.98 33.91±1.61
69.97±1.09 44.82±1.81 35.97±1.65 FiGURe 87.21±1.13 76.67±1.33 89.73±0.49
31.82±1.65 26.24±1.03 39.33±4.26 38.21±2.33 33.45±2.07 61.19±3.92 41.76±0.66
38.57±0.76 Filter arxiv mag ratings mine. tolokers questions penn94 year
genius twitch pokec Identity 55.03±0.29 8.20±1.97 44.49±1.27 50.45±1.78
73.17±1.09 69.52±1.39 72.27±0.49 36.90±0.24 86.25±0.12 99.98±0.01 61.71±0.08
Linear 70.43±0.27 13.06±0.92 34.69±2.49 53.61±9.53 72.82±3.38 63.31±3.08
72.38±0.34 47.23±0.40 79.23±0.57 72.77±2.62 54.98±0.38 Impulse 68.27±0.24
22.42±1.69 35.81±2.37 62.88±2.16 65.15±4.34 71.23±1.49 60.52±0.49 44.93±0.27
72.90±1.06 77.50±0.67 57.84±0.11 Monomial 67.24±0.40 32.79±0.84 43.83±0.89
72.75±1.56 77.05±0.80 62.85±3.11 75.03±0.32 46.00±0.54 88.87±0.17 94.36±6.64
63.82±0.10 PPR 64.93±0.43 17.02±3.99 39.72±1.00 76.48±1.40 77.15±1.14
69.60±1.47 75.03±0.36 48.38±0.22 86.53±0.13 97.34±0.32 62.18±0.04 HK
68.87±0.54 25.72±0.67 36.66±1.16 54.39±5.38 79.02±1.03 65.76±2.21 72.77±0.76
48.70±0.25 89.96±0.16 97.79±1.10 62.04±0.08 Gaussian 70.42±0.23 25.70±0.70
34.76±2.36 54.39±5.38 59.81±4.86 61.36±2.69 73.93±0.45 49.60±0.27 87.98±0.35
99.32±0.10 62.20±0.05 Var-Linear 55.22±0.20 26.44±0.84 36.27±0.83 50.79±1.42
67.51±5.05 55.93±5.08 74.63±0.67 36.78±0.47 85.95±0.24 89.90±5.42 62.21±0.16
Var-Monomial 65.18±1.97 33.11±0.37 30.84±4.82 57.90±9.72 68.98±4.45 63.57±2.48
82.63±0.54 48.19±0.43 82.52±7.95 81.87±6.42 78.11±0.70 Horner 68.59±1.10
30.04±0.47 30.91±4.71 63.17±2.01 70.07±1.88 59.84±2.80 47.09±0.65 46.31±0.38
70.17±0.83 77.82±0.67 62.87±0.25 Chebyshev 60.55±1.74 19.54±5.50 37.15±2.22
53.86±3.20 80.79±0.72 61.03±1.77 83.40±0.40 45.66±0.10 89.53±0.71 99.92±0.05
78.95±0.13 Clenshaw 34.57±3.20 29.74±0.94 45.63±1.05 50.88±1.90 70.51±1.40
65.42±1.83 48.39±2.59 46.09±0.20 73.34±3.00 74.34±4.28 52.79±2.66 ChebInterp
69.61±0.09 28.26±0.84 35.58±2.22 55.43±3.27 70.63±2.87 61.32±1.41 63.59±0.70
45.67±0.84 86.87±2.00 99.71±0.45 78.60±0.68 Bernstein 47.18±0.80 16.07±0.32
31.24±2.14 74.51±2.61 67.44±3.20 58.06±4.64 79.72±0.34 35.78±0.86 83.06±4.56
97.43±0.55 73.61±0.02 Legendre 65.26±0.32 34.74±0.45 39.94±1.27 66.63±10.82
78.29±0.99 58.18±1.14 76.88±0.41 49.99±0.46 87.91±1.87 97.32±4.52 72.60±1.49
Jacobi 71.59±0.37 32.96±0.23 37.06±1.47 87.30±3.36 78.51±0.86 60.51±3.34
84.06±0.43 45.31±0.13 89.11±0.34 98.61±2.03 73.05±2.02 OptBasis 47.12±2.71
31.29±1.68 42.15±1.08 54.96±1.39 80.01±1.23 69.30±2.53 81.81±0.99 49.25±1.75
88.47±0.82 86.13±0.50 78.67±0.11 FAGNN 68.71±0.35 35.55±0.37 41.44±0.75
74.53±0.89 77.47±0.91 64.40±2.33 68.49±0.88 46.97±1.61 77.96±2.07 79.92±1.70
62.60±0.12 G2CN 59.27±1.02 29.68±0.27 33.84±1.18 61.71±1.69 71.82±1.58
64.32±2.09 80.55±0.45 44.81±1.91 71.76±0.11 78.72±1.21 50.69±0.05 GNN-LF/HF
68.22±0.56 29.41±0.22 38.04±1.84 85.12±0.84 79.75±1.27 60.90±6.86 75.72±0.44
50.15±0.21 89.03±0.21 99.91±0.07 62.95±0.65 FiGURe 70.06±0.29 34.43±1.13
39.09±1.17 90.13±0.50 82.02±0.61 64.63±2.14 83.70±0.38 48.09±0.49 87.33±1.33
71.26±3.64 73.58±2.53

Table 11: Time and memory efficiency of mini-batch training on medium- and
large-scale datasets. “Pre.” refers to precomputation time ($\mathrm{s}$),
“Train” and “Infer” respectively refer to average training time per epoch and
inference time ($\mathrm{m}\mathrm{s}$), while “RAM”, and “GPU” respectively
refer to peak RAM and GPU memory ($\mathrm{G}\mathrm{B}$). For each column,
highlighted ones are results ranked first, second, and third within the error
interval. .

Filter arxiv mag penn94 Pre. Train Infer RAM GPU Pre. Train Infer RAM GPU Pre.
Train Infer RAM GPU Linear 1.38±0.30 48.7±1.0 15.8±3.0 2.04±0.22 0.10±0.02
4.69±0.63 11.5±1.1 5.47±0.99 3.83±0.41 3.99±1.68 16.0±0.7 17.1±0.9 5.34±0.68
6.60±0.21 0.18±0.00 Impulse 0.85±0.19 46.9±1.5 16.2±2.3 1.88±0.20 0.10±0.02
3.86±0.24 11.4±0.5 5.27±0.50 3.38±0.31 3.96±1.66 12.0±0.4 16.0±0.5 4.95±0.87
5.86±0.21 0.18±0.00 Monomial 0.68±0.17 44.4±1.1 13.9±1.6 2.03±0.25 0.10±0.02
4.05±0.04 12.1±0.2 4.70±0.35 3.38±0.32 4.03±1.72 12.9±0.5 16.5±0.9 5.29±0.52
5.87±0.22 0.18±0.00 PPR 0.67±0.15 45.1±1.1 14.2±3.6 1.94±0.22 0.10±0.02
4.01±0.11 11.4±0.6 5.40±1.05 3.37±0.31 3.89±1.98 12.4±0.4 16.6±0.8 4.72±0.85
5.82±0.19 0.18±0.00 HK 0.63±0.14 46.6±1.1 14.5±3.2 1.98±0.24 0.10±0.02
3.92±0.19 12.1±1.1 4.80±0.10 3.38±0.31 4.04±1.72 12.3±0.6 16.3±1.1 5.33±0.39