Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective
Authors: Yushun Dong
Patrick Soga
Yinhan He
Song Wang
Jundong Li
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Spectral Graph Theory
Graph Signal Filtering
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) have achieved remarkable success in various graph-based learning tasks. While their performance is often attributed to the powerful neighborhood aggregation mechanism, recent studies suggest that other components such as non-linear layers may also significantly affecting how GNNs process the input graph data in the spectral domain. Such evidence challenges the prevalent opinion that neighborhood aggregation mechanisms dominate the behavioral characteristics of GNNs in the spectral domain. To demystify such a conflict, this paper introduces a comprehensive benchmark to measure and evaluate GNNs' capability in capturing and leveraging the information encoded in different frequency components of the input graph data. Specifically, we first conduct an exploratory study demonstrating that GNNs can flexibly yield outputs with diverse frequency components even when certain frequencies are absent or filtered out from the input graph data. We then formulate a novel research problem of measuring and benchmarking the performance of GNNs from a spectral perspective. To take an initial step towards a comprehensive benchmark, we design an evaluation protocol supported by comprehensive theoretical analysis. Finally, we introduce a comprehensive benchmark on real-world datasets, revealing insights that challenge prevalent opinions from a spectral perspective. We believe that our findings will open new avenues for future advancements in this area. Our implementations can be found at: https://github.com/yushundong/Spectral-benchmark.

Published as a conference paper at ICLR 2025
GRAPH NEURAL NETWORKS ARE MORE THAN FIL- TERS: REVISITING AND BENCHMARKING FROM A SPECTRAL PERSPECTIVE
Yushun Dongi, Patrick Sogai, Yinhan He Song Wang', Jundong Lii
Florida State University
University of Virginia
yushun. dong@fsu edu, {zge3eg, nee 7ne, sw3wv, hwwp://wwnnn///rriiiiii.accco
ABSTRACT
Graph Neural Networks (GNNs) have achieved remarkable success in various graph-based learning tasks. While their performance is often attributed the powerful neighborhood aggregation mechanism, recent studies suggest that other components such non-linear layers may also significantly affecting how GNNs process the input graph data in the spectral domain. Such evidence challenges the prevalent opinion that neighborhood aggregation mechanisms dominate the be- havioral characteristics of GNNs in the spectral domain. To demystify such con- flict, this paper introduces a comprehensive benchmark measure and evaluate GNNs' capability in capturing and leveraging the information encoded in differ- ent frequency components of the input graph data. Specifically, we first conduct exploratory study demonstrating that GNNs can flexibly yield outputs with di- verse frequency components even when certain frequencies are absent or filtered out from the input graph data. We then formulate novel research problem of measuring and benchmarking the performance of GNNs from spectral perspec- tive. To take initial step towards a comprehensive benchmark, design evaluation protocol supported by comprehensive theoretical analysis. Finally, we introduce a comprehensive benchmark on real-world datasets, revealing insights that challenge prevalent opinions from a spectral perspective. We believe that our findings will open new avenues for future advancements in this area. Our implementations can be found at: httts:://gihhei com/ yushundong/
Spectral Sreectral-eenchmarr benchmark
INTRODUCTION
Graph Neural Networks (GNNs) have shown remarkable performances in modeling graphs in plethora of domains, such as social media analysis (Fan et al.) 2019 Ying et al. 2018). molecular biology (Wang et al. 2022 Liu al. 2022 Gasteiger al.] 2021). and cybersecurity (Jin et al., 2020 Zhang & Zitnik 2020 Tang et al. 2022), to name a few. The huge success of GNNs is generally attributed
powerful neighborhood aggregation mechanism (Xu et al. 2018 Zhu ct al. 2020). Specifically, such mechanism allows each node to contribute key information to its neighbors across the graph topology (Liu & Zhou| 2022), ), which enables GNNs learn informative representations and perform accurate predictions in graph-basee based learning tasks (Wu et al. 2022a).
To gain deeper understanding of the reason why such neighborhood aggregation mechanism brings revolutionary performance improvement, recent years have witnessed huge amount of ex- plorations (Jegelkal 2022 Xu et al. 2018). Currently, widely acknowledged belief that neigh- borhood aggregation mechanism acts graph signal filter (Luan et al. 2024), which serves as the dominant module in GNNs (Wang & Zhang 2022 Bianchi et al., 2021). In most traditional GNNs, such a mechanism acts as low-passing filter (Chang et al. 202 Nt & Maehara 2019) to capture the frrquency components encoded with the most task-relevant information in most graph datasets. More recent studies such as (Bo et al. 2021 Bianchi et al. 2021 Luan et al. 2022). have noticed that the most task-relevant information is not necessarily encoded in the lowest frequencies, e.g., in heterophilous graphs (Zheng et al. 2022 Zhu et al. 2021). To facilitate more capable GNNs to han-

---

Published as a conference paper at ICLR 2025
dle different types of graphs, variety of complicated neighborhood aggregation mechanisms have been designed to equip GNNs with more flexible filters (Li et al. 2018 Guo et al., 2023), aiming at capturing more tesk-relevant information from different frequency components across the spectral domain. Nevertheless, a significant flaw arises when we zoom in on these works. Specifically, the motivation of designing more flexible filters is implicitly based the assumption that it is difficult for GNNs to yield outputs with abundant frequency components these components are significantly weakened or filtered out by the neighborhood aggregation mechanism. However, GNNs are more than filters associated with neighborhood aggregation mechanisms. Other modules, e.g., non-linear layers, are often included as well. This fact naturally undermines the validity of this assumption. Considering such gap, in this work, we ask:
When such filters are fixed, can GNNs still flexibly output different frequency components?
The above question is critical since its answer determines whether we should attribute most strengths and weaknesses of GNNs from spectral perspective to such filters not. Despite the scarcity of existing explorations. several studies have observed that non-linear layers can affect the frequency components of the GNNs' output (Balcilar et al., 2021b; Yang et al.) 2024). These results imply that GNNs as whole may exhibit different behavioral characteristics, e.g., the GNNs' output frequency components given a certain input frequency component, compared with the above-mentionel neigh- borhood aggregation mechanisms in the spectral domain. However, most existing works fail to gain a comprehensive understanding of how the components other than those filters influence the behav- ior of GNNs in the spectral domain and finally affect the performance in graph learning tasks.
We note that it is non-trivial to properly answer the aforementioned question. In particular, we mainly face three fundamental challenges. (1) Complex Analytical Expressions. GNNs are usu- ally highly complex when the components other than neighborhood aggregation mechanisms are considered all together. Therefore, its analytical expression can hardly be exploited perform analysis in the spectral domain. (2) Lack of Frequency-Specifi, Incentives. GNNs are typically supervised with set of fixed ground-truth labels during training. However, these ground-truth la- bels are usually a composition of different frequency components and do not show clear incentive patterns preferring certain frequency components. Therefore, it becomes difficult analyze whether GNNs are able to yield outputs with components that they have not previously observed. (3) Lack of Metric and Benchmark. To the best of our knowledge, there is currently no metric that measures the flexibility of a GNN's ' output frequency components in the spectral domain. On the other hand, it is also necessary for us to understand the differences between different popular GNN models on the question above. However, no existing benchmark can comprehensively reveal such insights.
In this paper, we take an initial step to investigate the problems above. Specifically, we first per- form an exploratory study, where we avoid characterizing any analytical expressions to tackle our first challenge. Instead, we propose to design appropriate supervision information as the frequency- specific incentives for GNN training, such that the capacity of GNNs in yielding different frequency components can be exposed and observed across the frequency axis. This helps us to properly tackle the second challenge. The observations of the exploratory study verify that the modules other than neighborhood aggregation can already enable GNNs to flexibly output different frequency compo- nents different energy levels, which challenges the prevalent opinion that neighborhood aggre- gation typically dominates GNNs' behavioral characteristics in the spectral domain. Furthermore, we design evaluation protocols to evaluate the performance of different GNNs in yielding different frequency components across the spectral domain. We finally present a comprehensive benchmark under such protocols to introduce a comprehensive understanding on such a problem across different popular GNNs, which properly handles the third challenge. We summarize our contributions below:
An Exploratory Study Challenging the Common Belief. We propose a principled strategy to characterize the flexibility of GNNs to yield different frequency components. Surprisingly, we found that the filter resulted from the neighborhood aggregation does not dominate the behavioral characteristics of GNNs in the spectral domain, which disagrees with the prevalent opinion.
Novel Research Problem. We formulate a novel research problem of Measuring and Bench- marking the Performance of GNNs From A Spectral Perspective and take an initial step towards properly handling it. We provide valuable insights through explorations towards understanding the behavioral characteristics of GNNs in the spectral domain.
A Comprehensive Benchmark with Novel Evaluation Protucol. protocol with solid theoretical basis and practical significance. We also conduct extensive experi-
We design a novel evaluation
2

---

Published as a conference paper at ICLR 2025
ments to enhance understanding of popular GNNs real-world datasets. Notably, our benchmark provides a consistent view directly applicable to both spatial- and spectral- based GNNs.
PRELIMINARIES
Notations. Throughout our work, without further specification, italic letters (e.g.. X), bold up- percase letters (e.g.. X), bold lowercase letters (e.g., x), and ordinary lowercase letters (e.g., x) represent matrices, vectors, and scalars, respectively. For any matrix, e.g.. X, we employ X, and X' to indicate its i-th row and column, respectively. We denote an undirected graph as G = (V. where (vi,... en and are the set of nodes and edges. We denote A E N as the graph adjacency matrix in which Ai, 1 if there exists an edge between node i and node j. other- wise A.j = With graph adjacency matrix A, the graph node degree matrix can be defined as D diag(d), (d1, .... dx), where d, A,A.j. The normalized graph Laplacian matrix is defined as = D ADD 3. Additionally, we define the graph node feature matrix X NNF, where X represents the j-th feature channel and F denotes the number of feature channels. We employ the sign as the Hadamard multiplication.
Current Progress of Gnns & Concerns From Spectral Perspective. There are two mainstream lines of research on GNNs, i.e., spatial- and spectral-base beaseal--baedddde ones. Researchers examining the spatial perspective consider the aggregation process of GNNs as a node attribute aggregator across the graph topology (Kipf & Welling, 2017] Wu et al. 2020 Xu et al. 2018). In contrast, those exploring GNNs from spectral perspective consider the aggregation process filter in the spectral domain, i.c., the cigenspace of the graph Laplacian matrix L, largely considering GNNs as low-passing filters (Nt & Maehara 2019, Chang et al. 2021 Yu & Qin 2020). Recently, diverse designs of filters associated with different neighborhood aggregation mechanisms have been proposed to help GNNs capture the key information encoded in different frequency components (Bo et al., 2021 Guo et al., 2023
Dong et al., (021). In general, these explorations lay a solid mathematical foundation for GNN with spectral- based methods. However, most current methods focus on the filters associated with the neighborhood aggregation mechanisms rather than considering a GNN as whole. As such, the role of other modules such non con-linear layers in GNNs has been long neglected. In recent years, several works (Balcilar et al., 2021b) Yang et al., 2024) have provided primary evidence that the non-linear layers can effectively shift the behavioral characteristies of GNNs. To further bridge the aforementioned gap, we now formally introduce the problem of Measuring and Benchmarking the Performance of GNNs From Spectral Perspective below.
Problem 2.1. Measuring and Benchmarking the Performance of GNNs From A Spectral Per- spective. Our goal is to qualitatively understand and quantitatively compare the capabilities of GNNs capturing the key information encoded in different frequency components of impus graphs to perform graph learning tasks.
AN EXPLORATORY STUDY
To properly handle Problem 2.1 the prevalent strategy is to simply analyze the frequency response function associated with the filter resulted from the neighborhood aggregation mechanism (Nt & Maehara 2019 Wu et al. 2019). However, such a straightforward approach may not be able to handle Problem 2.1 since the behavioral characteristics of GNNs in the spectral domain may not be fully dominated by such filters. Below, we show our preliminary explorations to further clarify such a common misunderstanding.
Research Question. Here, we perform preliminary studies to explore whether the behavioral char- acteristics of GNNs in the spectral domain are dominated by the filters associated with the neighbor- hood aggregation mechanism (as discussed in Section T Specifically, we are particularly interested in revealing whether GNNs can flexibly yield outputs with abundant frequencyy components that have been significantly weakened or filtered out by the non- non-learnable filter.
Evaluation Protocol. In this study, we measure the influence of different frequency components using the commonly adopted notion of Energy (Yang et al., 2022 Tang et al. 2022). We construct experimental datasets based on real-world graph datasets. First, compute the normalized Laplacian cigenvectors of the graph and sort them by eigenvalue (i.e., frequency). We then bin these eigenvectors into wven-width bins, where each bin is associated with the mean of the eigenvectors
3

---

Published as a conference paper at ICLR 2025
Target Signal
Input signal
Output Signal
0.20
0.20
0.15
0.15
Energy
Eneegyy
0.10
0.10
0.05
0.05
0.00
0.00
15
20
15
Frequency bin
Frequency bin
(a) Low-frequency input: feghffrequency targets.
(b) fligu-frrueency input: low-frequency targets.
Figure I: comparison between the energy of input and output frequency components of GCN on Co-author CS dataset. The results show that the output frequency components can always flexibly align with the target distribution in both cases of (a) inputting low-frequency components only but aiming to output high-frequency components; and (b) inputting high-frequency components only but aiming to output low-frequ frequeeency components.
falling into that bin. The bottom, middle, and upper one third of bins are designated as low-, middle- and gegufrreyeeccy components. We propose conduct node-level regression tasks to answer our research question above. Specifically, we set the target as the mean of the eigenvectors coming from one frequency component, while the input features are the mean of eigenvectors in a different frequency range (e.g., -wwffreuuecy eigenvectors when the target is high-frequency). In this way, the input graph signal will have zero energy levels for the frequency components of the prediction target, while the ground truth can serve as frequency-specifer incentives. This simulates the scenarios where certain frequency components are absent in the input or filtered out by the neighborhood aggregation mechanism. We note that graph filters cannot generate frequency components that are not originally contained in the input graph data. Therefore, if GNN model can still produce outputs with abundant target frequency components (in terms of energy levels) under various conditions, demonstrates that the neighborhood aggregation mechanism does not necessarily dominate the output frequency components. In other words, GNNs can recover missing frequency components if it benefits the optimization goal during training, even if these components are/become absent in the forwarding process. We adopt GCN as our GNN model and conduct experiments on five real-world datasets. We train our models using MSE loss after standardizing the input features. We show two exemplary cases based on Co-author CS dataset in Figure || where the energy distribution of the final GNN's output signal alongside those of the input and target signals are visualized. We present complete results the Appendix.
Observations & Analysis. Surprisingly, our experiments reveal that GNNs demonstrate remarkable capability to recover frequency components across diverse scenarios. As shown in Figure D even when certain frequency components are filtered out or significantly weakened in the input, GNNs can still flexibly align their output with the target distribution. This evident both cases: (a) where low-frequency inputs generate high- high-frequency outputs, and (b) where high frequency inputs produce low-frequency outputs. Notably, this indicates that other modules, such as the non-linear layers, in GNNs can also play crucial role in altering the energy distributions across different frequency components. Our preliminary conclusion is that the behavior of GCN in the spectral domain is not necessarily dominated by the spectral characteristics of its neighborhood aggregator. Instead, GCN can easily output different frequency components when appropriate frequency-specific incentives exist in the supervision signal. Such flexibility in yielding various frequency components is even comparable to those state-of of-the-art GNNs with carefully designed learnable filters (Bo et al. 2021 and we show a more comprehensive comparison in Appendix
To summarize, we conclude that the frequency response of the filter of neighborhood aggrega- tor does not necessarily determine the behavioral characteristics of its host GNN in the frequency domain. In fact, GNNs whole have the capability to significantly modify their output energy distribution compared with the input energy distribution in the spectral domain. Such an insight suggests that only analyzing the flexibility of the filters associated with the neighborhood aggrega- tion mechanism is insufficient to fully explain the strengths and weaknesses of GNNs, which is in conflict with the traditional belief. Taking step further, critical question emerges: How we ef- fectively measure the general "capturing and altering" capability of GNNs in the frequency domain? This question becomes paramount for understanding the true potential and limitations of current.
4

---

Published as a conference paper at ICLR 2025
GNNs. We address this question in the following section where we aim to provide comprehensive evaluation protocol for benchmarking GNN performance from a spectral perspective.
4 BENCHMARK DESIGN
In this section, we introduce the benchmark design. Specifically, we first introduce the evaluation protocol, followed by comprehensive analysis to lay a solid theoretical foundation which will di- rectly support the practical significance of our proposed benchmark from a spectral perspective.
4.1 EXPERIMENTAL. PROTOCOL
Downstream Task & Dataset Preparations. While we used node regression for our preliminary study in Section 3 we adopt node classification for extensive empirical benchmark considering its superior practical significance in graph learning tasks. Specifically, we propose to adopt the same approach to generate continuous values corresponding to each node in the input graph (as in Section 3) followed by an additional discretization process by giving thresholds to determine the ground truth labels for each node. We show in Section 4.2 that the additional discretization process only brings an upper-bounded energy distribution deviation compared with the continuous ground truth values in the node-level regression task, which ensures satisfying consistency. Meanwhile, such approach ensures that the targets to predict possess the frequency-specinn incentives needed to evaluate performance on each bin in the frequency domain. We propose to adopt real-world datasets such that we will perform evaluations on the node attributes and graph topology that bear practical significance across different domains. We further provide more details in Appendix A
GNNs for Benchmarking We conduct evaluation SAGE (Hamilton et al. 2017). GCN (Kipt & Welling 2017). GCNII (Ming Chen et al.] 2020). GAT VVelickvv al. 2018), GATv2 (Brody al.] 2022), SGC (Wu et al. 2019), FA (Bo al.,
total number of 14 GNNs, namely
2021]. GIN (Xu et a 2018), ChebNet (Defferrard et al. 2016), GatedGiraph (Li et al.] (016). the
Transformer (Vaswani et al., 2017), GPS (Rampášek et al. 2022), APPNP (Gasteiger et al. [2019).
and the I-WL operator from Morris et al. (2019) (denoted as I-GNN). These models cover wide range of popular and of-te-of-the-ar GNNs designed in either spatial or spectral domain.
Real-World Datasets. We benchmark GNNs on the full versions of the Cora and DBLP citation graphs (Bojchevski & Günnemann| 2018), the CS and Physics coauthor datasets by Shhhuu et al. 2018), and the Amazon-Computers and Amazon-Phoit product graphs by (Shchur et al., 2018). These datasets vary in size, structure, spectral energy distribution, and semantic domains, allowing us to evaluate the GNNs' performance across diverse graph types and application areas.
Benchmark Evaluation Metrics. Following most other works, we adopt node classification ac- curacy as the primary metric to measure the performance of GNNs. On the basis of this, we now introduce the qualitative and quantitative performance evaluation methods. From a qualitative per- spective, propose the notion of Accuracy Curve in the Spectral Domain. Specifically, as intro- duced in Section 3 each round of experiments is associated with a bin on the spectral axis, based on which the node-level prediction target (a discrete label for node classification) is generated. When the input graph signal contains all frequency components at the same energy level, the performance under this bin generally reflects the capability of such a GNN model in capturing and leveraging the information encoded in the associated frequency component to perform prediction. Accordingly, the performance across all available bins on the spectral axis form curve, which generally reflects the tendency of how such capability changes w.r.t. the frequency value. From a quantitative per- spective, we propose to utilize the Normalized Area Under the Accuracy Curve, Normalized AUAC, to measure the general capability of each GNN model in capturing and leveraging the information encoded in different frequency components. Specifically, is calculated as the division between the AUAC under the full frequeney range and the largest possible AUAC under the full frequency range. Additionally, we are also interested in the capability of GNNs in capturing the information encoded in certain range of frequency components. In this case, Normalized AUAC can also be adopted by specifying a particular range of frequencies.
Implementation Details. All experiments were conducted using PyTorch (Paszke al.) 2017) and PyTorch Geometric (Fey & Lenssen| 2019) libraries. We used 2-layer GNNs with a hidden dimension of 64 for all runs. GNNs were trained for 500 epochs using the Adam optimizer with
5

---

Published as a conference paper at ICLR 2025
learning rate of 0.001. We bin each frequency component with width of 0.1. No learning rate scheduler or early stopping was used. For each dataset and speetral bin, we report the mean and standard deviation of the results across 3 runs. More implementation details are in Appendix A
4.2 THEORETICAL ANALYSIS
We adopt node classification task for our main benchmark considering that it typically fosters a stronger practical significance. To ensure the consistency between node-level regression task and node classification tasks, in this section, we aim to reveal that the additional discretization process in node classification does not bring significant deviation from the ground truth's 's energy distribution in the spectral domain. Below we present the theoretical analysis revealing such insights.
We refer to the matrix of one-hot vectors representing the ground truth node class labels after dis- critization as the Node Class Label (NCL) matrix for convenience. Below we first define the Energy Distribution Field (EDF) of node class label distribution.
Definition 4.1. (Energy Distribution Field) The energy distribution field, denoted as FM. of an NCL. matrix M E Ba*k is the set of energy distributions of the unit vectors whose corresponding NCL 1, -()) M), where e(-) is the
matrix is M. In other words, FM == {e(z) E RTx | energy distribution function mapping a vector its energy distribution in the graph spectrum field, T(.) is the function mapping unit vectors to their NCL matrices.
With the concept of EDE, we then formulate the "closeness" of the energy distribution be- tween the eigenvector v of the graph Laplacian and its corresponding NCL matrix T(v) as maxe..f,ttv ||eu - e(u) |(v)=())]l2. We take two steps to verify that the optimal value of the maximiza- tion problem is small enough: (i) We prove that the energy distribution function is Lipschitz, which indicates that the energy distribution function is a "smooth" function where quantifying its function value variations is equivalent to quantifying its variable variations; (ii) The inverse image of the energy distribution function e(+) on any energy distribution field JM is small enough.
For the first step, since the energy distribution function is essentially linear function followed by vector normalization procedure, can write the energy distribution function e(v) (Au)o(Au) with A being an orthonormal matrix. Actually, the energy distribution function is Lipschitz:
||
Theorem 4.2.
The energy distribution function e(t) (Am)o(An) with A being orthonormal, is ||
Lipschitz the unit sphere.
For the second step, we prove the inverse image of the energy distribution function e(-) on any EDF FM is "small enough". Intuitively, we can calculate the area of (JMm) on the unit sphere and prove that the area is "small enough". However, since the calculation of the area is rather complex for a high- -igh-dimensional sphere, we instead prove that the variation of center angle in e (FM) is small enough. Specifically, we have the following theorem.
Theorem 4.3. Assume that we segment [-1.1] (i.e, the value field of any entry of an eigenvector of a graph Laplacian matrix) into k intervals with identical lengths, as illustrated in Figure ((a). Consider the Euclidean space of 1|" separated into kn identical hypercubes. We claim that each section of the unit sphere and a hypercube corresponds to a (Fm)) for some NCL matrix M. We denote the maximum center angular variation of e (JTm) among all NCL matrices Ms as O 0max. For Ve 2 there exists Ko 2( 2-) )), when k 2 ko, then m S E.
met
Now, we able provide upper bound for the energy distribution variance for EDF FM of any NCL matrix M.
Theorem 4.4. Given the conditions of Theorem B.3 for any eigenvector v of Laplacian amirix of graph G. we have max 1aasss_,,,,,,e... I.e..Trre) lle, e(v)ll2 S 2( (2) ",, where Sn- is dimensional
unit sphere embedded in dimensional Euclidean space.
By Theorem B.4 we are able to reveal that the additional discretization process in node classification task does not bring significant deviation in the ground truth's energy distribution in the spectral domain. Meanwhile, given tolerance of the change of energy distribution from an eigenvector and its corresponding NCL matrix, we can also estimate the minimum number of identical interval segments l for the specification of the discritization thresholds to satisfy precision requirements.

---

Published as a conference paper at ICLR 2025
Transformer
SAGE
GCNII
GATv2
GAT
SGC
1.0
Photo
02
10
1.0
DBLP
Cora-Full Full
8.8
8 07
19
13
20
8
29 9 03
69 65
20
6
65
Figure 2: The accuracy curves of different GNNs in the whole spectral domain. In each subplot, the r-axis represents the frequency and the y-axis represents the accuracy of GNNs in the node classification task with the ground truth labels derived from the associated frequency bin.
EMPIRICAL INVESTIGATION
5.1 RESEARCH QUESTIONS
What are the trends of GNNs' performance in capturing the information encoded in different frequency components across the frequency domain? RQ2: How do various GNNs compare in their ability to capture information across different frequency components, both holistically and in specific ranges? RQ3: How will the benchmark show its practical implications guide practitioner's choice of GNN? RQ4: How does the depth of GNNs affect the proposed accuracy curves in the spectral domain?
We are interested in answering four research questions (RQs) below. RQ1:
5.2 QUALITATIVE PERFORMANCE COMPARISON IN THE SPECTRAL DOMAIN
We first answer RQ1 by analyzing the general trends that GNNs show in our benchmark, and we present the general tendency of the accuracy curves in the spectral domain for different GNNs in Figure 2 We note that only partial results are presented here due to space limit, and see Appendix D for complete results. We have the following observations.
First, from the perspective of a general tendency, we observe that GNNs show V-shaped curves in all cases. Such phenomenon indicates that GNNs typically have stronger capability in captur- ing the information encoded in the lowest and highest frequency components (e.g., those associate with the smallest and largest frequency values) compared with the middle frequency components. Specifically, when the task-relevant information is encoded in the low frequency components, the neighborhood aggregation can directly benefit the prediction of each node. This is because nodes with similar labels tend to connect with each other, which can significantly facilitate predictive per- formance. On the other hand, when the task-relevant information is encoded in the high frequency components, the neighbors of each node can also contribute to its own prediction if the GNNs are able to learn not to predict the same label for connected nodes. However, contrast to the prevalent opinion, the capability of capturing the task-relevant information encoded in the middle frequency components is the most difficult for all adopted GNNs. A key reason for this phenomenon is that in this case, the label distribution of each node's 's neighborhood is generally uniform. Therefore, it be- comes very difficult for GNNs to learn a general criterion to predict the label of node based on its neighbors. Based on the discussion above. argue that the GNNs' weakness in capturing the task- relevant information encoded in the middle frequency components reveals an inherent limitation of neighborhood aggregation mechanism.
7

---

Published as a conference paper at ICLR 2025
Table I: Quantitative results of Normalized AUAC score in percentage for 14 GNN models across six real-world datasets. The best ones are in Bold and the second best ones are underlined. We also mark out the average ranking for each model across all datasets.
Model
Computers
Cora
CS
DBLP
Photo
Physics
Avg. Ranking
APPNP
56.94 = 1.08
54.26 = 1.80
52.90 + 2.16
51.69 + 0.40
56.77 + 1.51
53.60 = 1.38
13.67 1 0.75
FA
58.76 = 142
54.88
= 2.82
52.95
= 3.79
52.76 + 1.10
61.79
+ 1.78
55.81 = 2.33
12.00 = 1.41
GIN
55.39 0.86
60.98
+ 2.44
57.90
3.35
58.99 + 2.95
60.57
+ 1.48
59.65 3.27
10.33 :: 2.36
SGC
62.07 2.38
61.09
3.71
59.25
4.19
56.36 = 1.95
64.98
2.59
58.87 3.38
9.50 = 1.98
GAT
63.47 2.50
60.33 = 2:26
58.28 =
58.41 + 1.67
65.56 2.59
60.38 = 2.10
8.67 = 1.89
GPS
60.94 1.59
58.23 1: 0.99
59.89 1: 1.73
58.94 1 0.92
63.53 1: 1.77
62.90 = 1.52
8.33 1: 2.13
GCN
63.42 1: 2.39
62.17 4.18
59.82
1: 4.04
57.21 1: 2.09
66,20 1: 2.78
59.49 - 3.61
7.67 1: 2.1
GrtedGraph
58.67 1.22
69.85 = 2.74
66.14
2.93
63.84 + 2.56
60,41 + 1.13
60.20 2.86
6.17 = 4.60
Transformer
64.83 1.75
62.89 +: 1.75
59,43
1.50
61.86 + 1.36
65.86
1.87
60.93 = 1.49
5.50 = 2.22
Cheb
63.63 = 1.65
60.54 -:
60.88
1.93
61.14 +
65.88
1.68
62.95 = 2.06
5.50 =
I-GNN
56.04 = 1.12
68.00 + 2:45
66.27
2.77
64.16 + 1.96
58.17 + 1.47
65.16 2.77
5.33 = 5.44
GATv2
64.22 = 2.46
63.05
2.1
60.41
2.12
59.38 + 1.92
66.54 2.73
62.58 = 2.12
4.67 = 1.49
GCNII
66.57 2.10
60.54
= 2.73
62.91 + 2.75
58.13
+ 3.00
69.03 + 2.30
66.55 = 2.50
4.50 = 4.03
SAGE
64.60 1.69
63.97
+ 1.80 63.17
2.01
62.88 +: 1.33
66.13 4: 1.88
64.29 2.10
3.17 + 0.37
Second, we are also interested in comparing tendencies across different GNNs and datasets. Specifi- cally, we observe consistent tendencies of accuracy curves in the spectral domain for the same GNN model across different datasets, which validates the stability of our proposed evaluation strategy. Mcanwhile, on the same dataset, different GNNs can show different tendencies across the frequency axis, which demonstrates the difference in the capability of GNNs to capture task-relevant informa- tion. This further reveals the significance of the proposed evaluation method in deriving a stable and reliable evaluation for the performance of different GNNs in the spectral domain.
5.3 QUANTITATIVE PERFORMANCE COMPARISON IN THE SPECTRAL. DOMAIN
We now answer RQ2 by analyzing the quantitative results of Normalized AUAC score in percentage for 14 GNN models across six real-word datasets, and we show the results in Table I According to Section 4 the quantitative value of the Normalized AUAC score reflects the general capability of GNNs to capture the task-relevant information encoded in different frequency ranges. In addition, we are also interested in analyzing this capability on specific ranges of frequencies. Therefore, split the range of frequencies evenly into three sections, namely the low frequency frange (the components with a frequency value ranks at the bottom one third), the middle frequency range (the components with a frequency value ranks at the middle one third). and the high frequency range (the components with frequency value ranks at the top one third). We show the average rankings of GNNs by measuring their Normalized AUAC score in these three different frequency ranges above in Figure 3 Notably, the proposed benchmark is able to analyze the performance of both spatial- and spectral-based GNNs from a consistent spectral view. Therefore, we are able to involve both types of GNNs into the comparison at the same time. We have the observations below.
Comparing models focusing on the general spectral domain, we observe that the performance mea- sured by Normalized AUAC score gives a ranking that challenges the traditional assumptions on the relative superiority of these GNNs, Specifically, SAGE, GCNII, and GATv2 are the GNNs show- ing the best performance in terms of the average ranking across all datasets. In fact, these GNNs are rarely discussed and evaluated from a spectral perspective. The primary reason is that they are mostly designed in the spatial domain and most do not have well-defined frequency response func- tion. We argue that the advantages of these GNNs in the spectral domain are largely neglected by the current spectral-based studies (Nt & Maehara 2019 Wu et al. 2019) due their reliance on an explicit analytical form of frequency response function.
Comparing models focusing on the three specific sections of frequency components, we observe that different GNNs specialize in extracting task rele-relevnnt information from different ranges of frequen- cies. Specificallyy, GNNs specialize in learning from low (c.g.. SAGE and Cheb) and high (c.g.. GPS and Transformer) frequency components typically do not show strong superiority over other GNNs in learning from middle frequency components. Instead, GNNs such as GATv2 and GCN achieve clear superiority over other GNNs in learning from middle frequency components, which is often ignored by other studies relying on frequency response analysis.
5.4 CASE STUDY
8

---

Published as a conference paper at ICLR 2025
SAGB GCNI
Cheb GATv2
GAT GIN
EA
GPS
APPNP
GatedGrrph
L-GNN
GCN
Transformer
12.5
12.5
12.5
Avg Ranking
Avg Ranking
Avg Ronking
10.0
10.0
10.0
7.5
7.5
7.5
5.0
5.0
5.0
2.5 Low
2.5
Mid
High
Law
Mid
High
Low
Mid
High
Frequency Component Ranges
Frequency Component Ranges
Frequency Component Ranges
Figure 3: Performance comparison in the average ranking of 14 GNNs on six real-world datasets. The GNNs are shown by obtaining the best rankings on low frequency components (left), on middle frequency components (middle), and on high frequency components (right).
Random Ranking
Original Task Ranking r
In this subsection, we conduct a case study explore RQ3. Specifically, we propose to simulate the real-world problem of needing to choose from variety of different GNNs, and we then analyze how the findings from our benchmark can help practitioners, Specifically, we adopt six new real-world datasets, namely Airport-Brazil (AB), Wisconsin (Wise.). Cor- nell (Corn.). Squirrel (Squi.), and Chameleon (Cham.). Most of these dataests are reported to be difficult for node classification task with GNNs. We first perform node classification with all 14 GNNs based on these datasets and then derive the ranking of all GNNs as T1. Here
Benchmark Ranking
50
Kendall's
40-
AB
Wisc. Corn. Texas Squi. Cham.
Figure 4: Kendall's 7 comparison on new datasets between a random ranking (orange), the rankings from the original graph learning task (blue), and the average rankings from our benchmark (green).
ri serves as the actual ranking we seek know pick the best GNNs to use. However, in practice, we may not always be able to perform experiments prior to making a choice. Therefore, we pro- pose analyze how well other rankings can approximate such an actual ranking. We first analyze the node labels in the training node set to identify the frequency component range (low, mid, or high) where most energy falls in. According to this range, we collect the associated performance ranking from Section 5.3 as the ranking derived from our benchmark. As comparison, we also collect random rankings 73 and the node classification rankings r11 directly derived from the node classification task on the chosen six datasets.
We show the average Kendall-Tau (KT) distance 7 (total number of inversions for any two positions i and j where i > j) between the actual ranking F1 and the benchmark ranking r2 in Figure 4 Here, a smaller KT distance indicates larger similarity between the two rankings. We found that the KT distance between r'1 and r2 (Benchmark Ranking is significantly smaller than that between rı and r3 (Random Ranking r) or v4 (Original Task Ranking r) in most cases, which indicates a satisfying approximation of r1 with r2. This reveals the practical significance of the benchmark in understanding the superiority across different GNNs prior to any experiments.
5.5 PARAMETER STUDY
We finally answer RQ4 by changing the depth of each GNN to explore how the results of the pro- posed evaluation protocol will change. We note that stacking multiple filters (by adding more itera- tions of neighborhood aggregation) significantly affects the frequency response. Therefore, existing studies that analyze the performance of GNNs by relying on their aggregators' frequency response functions typically have significantly different conclusions when the layer number GNNs changes. Specifically, we range the number of GNN layers from two to four, and we present example of the accuracy curves in the spectral domain across two-, three-, and four-layer cases in Figure (see Ap- pendix for complete results). We observe that changing the layer number does not affect the shape of the accuracy curves in the spectral domain. Such an observation can also be found across different GNNs and datasets, which further validates the stability of the proposed evaluation protocol.

---

Published as a conference paper at ICLR 2025
Transformer
SAGE
GATv2
GAT
SGC
Accuracy
1.0
10
1.0
10
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
Layen
Frequency
Layen yr
3
Frequency
3 Layens
40
Frequency
Layen Layers
Frequency
3 Layens
40
Frequency
Figure 5: Accuracy curves in the spectral domain across different GNNs on the Coauthor-CS dataset.
The shape of these curves does not significantly change across different layer numbers, validating the stability of the proposed evaluation protocol.
6 RELATED WORKS
Spectral Graph Neural Network Analysis. Compared to spatial GNNs (Hamilton et al. 2017 spectral GNNs typically offer a sound theoretical basis (Balcilar et al. 2021a Bo et al. 2023). Re- cent studies have shown that the neighborhood aggregation mechanism in GNNs typically acts as a low-pass graph signal filter (Chang et al., 2021] Nt & Maehara 2019). capturing the lowest fre- quency components that are usually relevant for various graph learning tasks. However, while more flexible filters have been proposed to better capture task-relevant information encoded in different frequency components (Li al. 2018 Guo al. 2023 Bianchi et al., 202T), existing research typ- ically overlook the behavioral characteristics of GNNs in the spectral domain as a whole. As such, the roles of other modules, such as the non-linear layers, are often ignored. Recent works (Balcilar) et al. 202 lb; Yang et al., 2024) have show evidence that these modules other than neighborhood aggregation can significantly alter the frequency components of the GNN's output, This underscores the need for comprehensive analysis that considers GNNs in their entirety instead of only focus- ing on their neighborhood aggregation mechanisms. Different from existing works, we propose to consider GNNs whole and conduct benchmarking form a spectral perspective.
Graph Neural Network Benchmarking. Research GNN benchmarks focus on evaluating the per- formance of GNNs in terms of accuracy (Wu et al. 2022b Zheng al., (021). scalability (Duan) et al. 2022). and efficiency (Baruah et al.J (021). For example, various benchmarks have been proposed evaluate the performance of GNNs in various tasks (Dwivedi et al., (023), such as rec- ommendations (Wu et al. 2022a) and molecular property predictions (Fung et al. (021). In terms of the scalability of GNNs, different benehmarks are also proposed, such as LRGB (Dwivedi al.) 2022) for long-range dependency and LS-Bench for training on parge-scale graphs. The efficiency of GNNs is also studied in various benchmarking works (Gong & Kumar] 2024). Despite existing ef- forts of evaluating GNNs, most benchmarks emphasize node classification accuracy, scalability, and computational efficiency without delving into the behavioral characteristics of GNNs in the spectral domain. This hinders spectral understanding of the strengths and weaknesses of popular GNNs. Different from these benchmarks, we have proposed a comprehensive benchmark to evaluate both spatial and spectral GNNs from consistent spectral view. To the best of our knowledge, it is first- of-its-kind work that reveals insights challenging prevalent opinions from a spectral perspective.
CONCLUSION
This paper presents comprehensive benchmark for evaluating GNNs from spectral perspective, challenging common opinions about how GNNs process graph data. Through exploratory studies and rigorous experiments on real-world datasets, we demonstrate that GNNs can flexibly generate outputs with diverse frequency components, even when certain frequencies are absent in the input. This finding contradicts the prevailing opinion that neighborhood aggregation mechanisms dominate GNN behavior in the spectral domain. Our novel evaluation protocol, supported by theoretical analysis, provides a fundamental framework to measure the capability of GNNs capture and leverage information across different frequency components. These findings open new avenues for understanding and improving GNN architectures, emphasizing the need to analyze GNNs in their entirety rather than focusing solely their aggregation mechanisms. Our work lays the foundation for future research in spectral analyses of GNNs and provides valuable tools for practitioners to select and design more effective GNN models for various graph-based learning tasks.
10

---

Published as a conference paper at ICLR 2025
8 ACKNOWLEDGMENTS
This work is supported in part by the National Science Foundation (NSF) under grants IIS-2006844, IIS-2144209, IIS-2223769, CNS-2154962, BCS-2228534, and CMMI-241 1248; the Office of Naval Research (ONR) under grant N000142412636; the Commonwealth Cyber Initiative (CCI) under grant VV-1Q24-01 I; the UVA School Engineering and Applied Science (SEAS) Research Inno- vation Award; the UVA Comprehensive Cancer Center (CCC) Computational Genomics and Data Science Pilot Award; and research gift funding from Netflix and Snap.
REFERENCES
Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Con- ference on Machine Learning, pp. 599-608. PMLR, 2021a.
Muhammet Balcilar, Guillaume Renton, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks a spectral perspective. In ICLR, 2021b.
Trinayan Baruah, Kaustubh Shivdikar, Shi Dong, Yifan Sun, Saiful A Mojumder, Kihoon Jung, José L. Abellán, Yash Ukidave, Ajay Joshi, John Kim, al. Gnnmark: A benchmark suite to characterize graph neural network training on gpus. In 202/ IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), pp. 13-23. IEEE, 2021.
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. TPAMI, 2021.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks, In AAAI, 2021.
Deyu Bo, Xiao Wang, Yang Liu, Yuan Fang. Yawen Li, and Chuan Shi. A survey on spectral graph neural networks. arXiv preprint arXiv:2302.05631, 2023.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. In International Conference on Learning Representations, 2018.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? Interna- tional Conference on Learning Representations, 2022. URL https:://ppeneeeatat nnt/ Forum?1d=772ximsx77
Heng Chang, Yu Rong, Tingyang Xu, Yatao Bian, Shiji Zhou, Xin Wang, Junzhou Huang, and Wenwu Zhu. Not all low-pass filters are robust in graph convolutional networks. NeurIPS, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. NewrlPS, 2016.
Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Adagnn: Graph neural networks with adaptive frequency response filter. In CIKM, 2021.
Keyu Duan, Zirui Liu, Wenqing Zheng, Peihao Wang, Kaixiong Zhou, Tianlong Chen, Zhangyang Wang, and Xia Hu. Benchmarking large-scale graph training over effectiveness and efficiency. In Workshop Graph Learning Benchmarks, 2022.
Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326 222400 2022.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43): 2023.
11

---

Published as a conference paper at ICLR 2025
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In www, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Victor Fung, Jiaxin Zhang, Eric Juarez, and Bobby G Sumpter. Benchmarking graph neural networks for materials chemistry. npj Computational Materials, 7(1):84, 2021.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations, 2019. URL http:httttpppereeeeeeeee
net htt///orummiccc Higgg 2m
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph
neural networks for molecules. NeurIPS, 2021.
Yidong Gong and Pradeep Kumar. Gnnbench: Fair and productive benchmarking for single-gpu gnn system. arXiv preprint arXiv:2404.04118, 2024.
Jingwei Guo, Kaizhu Huang, Xinping Yi, and Rui Zhang. Graph neural networks with diverse spectral filtering, In 2023.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
T. Hastie, R. Tibshirani, and J.H. Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer series in statistics. Springer, 2009. ISBN 9780387848846. URL https: https:://booss.oooo com com/ wttp://oooossscccssssssseee
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. In ICM, 2022.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In SIGKDD, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional network. In ICLR, 2017.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In AAAI, 2018
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In International Conference Learning Representations, 2016.
Yi Liu, Limei Wang, Meng Liu, Yuchao Lin, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3d molecular graphs. In ICLR, 2022.
Zhiyuan Liu and Jie Zhou. Introduction to graph neural networks. Springer Nature, 2022.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. NeurIPS, 2022.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Kino-Wen Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. NeurIPS, 2024.
Zhewei Wei Ming Chen, Bolin Ding Zengfeng Huang, and Yaliang Li. Simple and deep graph convolutional networks. 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv, 2019.
12

---

Published as a conference paper at ICLR 2025
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vitioo Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. In NIPN-PSVV W, 2017.
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35, 2022.
Oleksandr Shchur. Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurlPS 2018, 2018.
Jianheng Tang, Jiajin Li, Ziqi Gao, and Jia Li. Rethinking graph neural networks for anomaly detection. In ICML, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International conference on machine learning, pp. 23341-23362 PMLR, 2022.
Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learning representations via graph neural networks. Nat. Mach. Intell., 2022.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In ICML, 2019.
Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, and Xiaojie Guo. Graph neural networks: foundation, frontiers and applications. In SIGKDD, 2022a.
Nan Wu, Hang Yang, Yuan Xie, Pan Li, and Cong Hao. High-level synthesis performance prediction using gnns: Benchmarking, modeling, and advancing. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pp. 49-54, 2022b.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Trans. Neural Netw. Learn. Syst., 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2018
Beining Yang, Kai Wang, Qingyun Sun, Cheng Ji, Xingcheng Fu, Hao Tang, Yang You, and Jianxin Li. Does graph distillation see like vision dataset counterpart? NeurIPS, 2024.
Mingqi Yang, Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, and Baocai Yin. A new perspective on the effects of spectrum in graph neural networks. In ICML, 2022.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William I. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In SIGKDD, 2018.
Wenhui Yu and Zheng Qin. Graph convolutional network for recommendation with low-pass col- laborative filters. In ICML, 2020.
Xiang Zhang and Marinka Zitnik. Gnnguard: Defending graph neural networks against adversarial attacks. Advances in neural information processing systems, 2020.
Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang. Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learn- ing. arXiv preprint a arXiv:2111.0431 2021.
13

---

Published as a conference paper at ICLR 2025
Xin Zheng, Yi Wang, Yixin Liu, Ming Li. Miao Zhang, Di Jin, Philip S Yu, and Shirui Pan. Graph neural networks for graphs with heterophily: A survey. arXiv, 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In AAAI, 2021.
A
REPRODUCIBILITY
All experiments were conducted using Python with the PyTorch (Paszke et al. 2017) and PyTorch
Geometric (Fey Lenssen 2019) libraries. We detail the exact experimental settings for the prelimi- nary study and main benchmark below. We also list all of our experimental hyperparameters in Table
Implementations are at: https: /tgpt:://githbb/b www./oom/////eeeee httmm/yuuunooogspeet.. ral benchma
A.1 PRELIMINARY STUDY
The datasets for the preliminary study are constructed by first taking each graph and computing its cigenvectors based on the normalized graph Laplacian. We then sort the eigenvectors by eigenvalue in ascending order and bin them into 20 uniform-width bins. Each bin contains the mean of the eigenvectors whose corresponding eigenvalues falling into that bin. We then split the bins into uniform intervals corresponding to low, medium, and high frequencies.
We then task a randomly initialized GCN and EA with predicting the mean of these low, medium, and high frequency eigenvectors using the mean-squared error (MSE) loss using the eigenvectors of the complementary ranges as features. For each setting (e.g. using low frequencies as fea- tures and high frequencies as targets). we split our constructed dataset using an 80%/20%/20%% train/ coin//aliiation/tess split under transductive node regression setting where we randomly generate the vaain/alliattonn/est masks. During training, we standardize the eigenvector targets, subtracting their mean and dividing by their variance, which is a common practice in machine learning to facili- tate learning during gradient descent (Hastie al. 2009). During evaluation, we restore the outputs of the GNN back to the original scale.
A.2 MAIN BENCHMARK
For the main benchmark, we construct each dataset similar to the preliminary study by collecting the normalized Laplacian eigenvectors of each graph followed by binning. Next, this benchmark a node classificaiton task, each entry of each binned eigenvector is assigned a class corresponding to that which bin it falls into between -1 and 1. For example, if the number of provided classes is 5, and a given binned eigenvector's 's entry is 0.8, then that entry will be assigned a class label of 4, the final class label.
Next, we conduct experiments where, for every bin b of eigenvectors, we train each GNN to predict the classes of each entry of b using the features from the original dataset, e.g. BOW text features for Cora-Full. We train our models using the cross-entropy loss and use random 60%/20%//20% vrain/validation/eess split under transductive node classification setting. We detail our hyperparam- eter settings for our benchmark below in Table
B PROOFS
In order to support the solidity of our design of the graph node class labels matrix (NCL matrix), we claim that the energy distribution of an eigenvector of the graph Laplacian matrix is close to that of its corresponding NCL matrix. To verify this claim, we first define the energy distribution field of a node class label distribution.
Definition B.1. (Energy Distribution Field) The energy distribution field, denoted as Fa, of an NCL matrix M E x the set of energy distributions of the unit vectors whose corresponding NCL matrix is M. In other words, Fa (e(v) ||la|| 1, Tw) M). where e(-) is the
14

---

Published as a conference paper at ICLR 2025
Hyperparameter
Preliminary study value
Main benchmark value
# Layers
3
2
Hidden Dimension Size
64
64
Learning Rate
0.0002
0.001
Number of Epochs
2000 Adam
500
Optimizer
Adam
Dropout Rate
0.0
0.0
Learning Rate Scheduler
Cosine annealing. To 10 He (Kaiming)
None
Initialization
Default Py PyTorch None
Early stopping
None
Table 2: Hyperparameters for preliminary study and main benchmark
energy distribution function mapping a vector to its energy distribution in the graph spectrum field, T(.) is the function mapping unit vectors to their NCL matrices.
With the concept of an energy distribution field (EDF), we formulate the "closeness" between the energy distribution between the cigenvector v of graph Laplacian and its corresponding NCL ma- trix T(V) as maxe,.e=(e)) ||e, e(v)ll2. We take two steps to validate that the optimal value of the maximization problem is "small enough": (i) We prove that the energy distribution function is Lip- schitz, which indicates that it is "smooth" function where quantifying its function value variations is equivalent to quantifying its variable variations; (ii) We prove that the inverse image of the energy distribution function e(-) on any energy distribution field FM is "small enough".
For the first step, since the energy distribution function is essentially a linear function followed by
vector normalization procedure, we can write the energy distribution function e(v) |AA where A is an orthonormal matrix. We show that the energy distribution function is Lipschitz:
(A=)O(Au)
(Ae)o(Ae) with A being orthonormal, is Theorem B.2. The energy distribution function e(v) || Lipschitz on unit sphere.
Proof. Assume there are two unit vectors U1 and 22, then
[le(v)) - e(v2)lla = (Av)) O (Av1) (Av2) (Avz)
12-
|
|
((Ar)) @ (Av)) (Avz) (Av2)
|1(A) Ava) 2 (Ari A22)lla,
S 21[A(1; 12)
S A|a|ll 12)1
2||m 02/12-
Here, the second equation follows because A is an orthogonal matrix, which implies that || = ||uu||| 1. The third equation can be verified casily with the definition of Hadamard multiplica- tion. The first "<"" is derived from the observation that any entry of Av and Ats has an absolute value less or equal to one since those two vectors are unit vectors. The second "<" follows by the SScwary inequality. Finally, the last equality follows from the fact that || since A an orthonormal matrix.
For the second step, we prove that the inverse image of the energy distribution function e(.) on any EDF FM is "small enough", Intuitively, we can calculate the area of e (FM) ) on the unit sphere and prove that the area is "small enough". However, since the calculation of the area is rather complex for a high-dimensional sphere, we instead prove that the variation of center angle in e eFI(Fs) is small enough. Specifically, we have the following theorem:
Theorem B.3. Assume that we segment [-1,1] 1] (i.e., the value field of any entry of an eigenvector of graph Laplacian matrix) into l intervals with identical lengths, illustrated in Figure ((a). Consider the Euclidean space of 1,,,1]" separated into ke identical hypercubes. We claim that each section of the unit sphere and a hypercube corresponds to a e (FFm for some NCL matrix M. We denote the maximum center angular variation of e (Fx) among all NCL matrices Ms as 6 8max. For Ve 2 0, there exists a by 2( 2 ) when l 2 Ku, then f 8max S e.
15

---

Published as a conference paper at ICLR 2025
5 Seee
(b)
Figure 6: An illustration of key insights for the proof of Theorem B.4 ing sectioned by kn identical hypercubes, where each segment corresponds to e (Fx) for some NCL. matrix M. (b) 2-d tangent plane determined by point 0 and the chord with length smaller than or equal to (m(2)))1/n, where the angle of the chord forms is smaller than or equal to 2 Prcssin (2)
(a) unit sphere be-
Proof. The largest chord length of a small hypercube sectioning the inscribed sphere is at most as long as the longest diagonal of the hypercube whose length is (n( (z)))))). Therefore, we consider the 2D tangent plane determined by the point and the chord with length smaller than or equal to ()) as shown in Figure 6(b), the angle formed by and the endpoints of the chord is smaller
than or equal to 2 arcsin ( ( Hence, we have
2 K
Geat 2
2
1 2
2
0 maxx < 2arcsin
< 2 arcsin
S
(2)
Since we have Ko 2( Te
we conclude that 0max I 8.
Now, able to provide upper bound for the energy distribution variance for EDF FM of any NCL matrix M.
Theorem B.4. Given the conditions of Theorem B.3 for any eigenvector of Laplacian amirix of graph G. we have maxves" 1.e.eTrrc) lle, e(v) I 2( (())) where Sn-1 is dimensional
unit sphere embedded in dimensional Euclidean space.
Proof. Since e, E F Fr(r). then
max vESa-1 -., EFEFF()
Ileu - E(v)l12 5
max wES ()
lle, 02/12-
By Theorem B.3
have
4n An ||u- 1/12 S )
max Lu,,ee ( 2(Pr())
(4)
With the Theorem B.2
we have
max
|leu - -1112 2
max
||u 1w--1p6 1112.
(5)
SE T
DES lu 1(F+(6))
Therefore, we conclude that
4n l|eu - e(v)l12 s 2 -leu-e(v)le
max VESA-1 FFFE(M
(6)
16

---

Published as a conference paper at ICLR 2025
Target Signal
Input signal
Output Signal
0.20
0.2
0.15
Energy
Energy
0.10
0.1
0.05
0.0
10
15
Frequency bin
Frequency bin
0.20
0.20
0.15
0.15
Energy
Energy
0.10
0.10
0.05
0.05
0.00
0.00
Frequency bin
Frequency bin (h) GCN
(a) FA
Figure 7: Energy distributions for CS.
0.15
0.3
Energy
Energy
0.10
0.2
0.05
0.1
0.00
0.0
20
10
Frequency bin
Frequency bin
0.3
0.3
Energy
0.2
Energy
0.2
0.1
0.1
0.0
0.0
10
20
10
Frequency bin (a) FA
Frequency bin (b) GCN
Figure 8: Energy distributions for Computers.
By Theorem B.4 given tolerance of the change of energy distribution from an eigenvector and its corresponding NCL matrix. we can estimate the minimum number of identical interval segments in the design of NCL matrices to satisfy an arbitrary precision requirement.
C COMPLEMENTARY RESULTS OF EXPLORATORY STUDY
illustrates a comparison between the energy distributions of input and output frequency components of FA and GCN on the CS, Computers, Cora Full, Photo and Physics datasets.
Figures 7 8 9
17

---

Published as a conference paper at ICLR 2025
0.20
0.20
0.15
0.15
Energy
Energy
0.10
0.10
0.05
0.05
0.00
0.00
20
10
15
Frequency bin
Frequency bin
0.2
0.2
Energy
Energy
0.1
0.1
0.0
0.0
10
Frequency bin
Frequency bin (b) GCN
(a) FA
Figure 9: Energy distributions for Cora-Full.
0.4
0.20
0.3
Energy
0.15
Energy
0.2
0.10
0.05
0.1
0.00
0.0
20
Frequency bin
Frequency bin
0.3
0.2
Energy
Energy
0.2
0.1
0.1
0.0
0.0
5
10
10
Frequency bin (a) FA
Frequency bin (b) GCN
Figure 10: Energy distributions for Amazon-Photo.
The plots depict the energy across 20 frequency bins, highlighting the distribution of input signals (orange), target signals (green), and output signals (blue).
We observe that FA and GCN performs similarly across all the examined datasets. Specifically, in each of those figures, the first subplot (top left) shows the FA model receiving an input concen- trated in the lower frequency bins while the target signal is predominantly in the higher frequencies. Despite this discrepancy, the model's output aligns closely with the target frequency, successfully capturing the desired high-frequency components. Similarly, in the top right, the GCN model, which also starts with wow-frequency input, produces an output that matches the fegh-freeuenc target dis- tribution, demonstrating similar flexibility. The lower two plots reverse the scenario: both models are now tasked with generating low low- frequueunncy outputs from high- figh-frequency inputs. The FA model (bottom left) manages to shift the energy toward the low frequencies, although it retains some high-
18

---

Published as a conference paper at ICLR 2025
0.20
0.20
0.15
Energy
Energy
0.15
0.10
0.10
0.05
0.05
0.00
0.00
20
5
10
15
Frequency bin
Frequency bin
0.20
0.2
Energy
Energy
0.15
0.1
0.10
0.05
0.0
0.00
5
20
Frequency bin (a) FA
Frequency bin (b) GCN
Figure 11: Energy distributions for Physics.
frequency characteristics from the input. Likewise, the GCN model (bottom right) shows similar ability to recover freeureuency components, albeit with a smoother transition compared to FA.
These observations reveal that both models, FA and GCN, are capable of adjusting their output to align with the target distribution, even when the input and target signals differ significantly. This flexibility suggests that GNNs are not constrained solely by their neighborhood aggregation mecha- nisms in the spectral domain. Instead, other components, such as the non-linear layers in GNNs, play crucial role in shaping the output, allowing the models respond to frequency-speciffe incentives in the supervision signal.
D COMPLEMENTARY RESULTS FOR QUALITATIVE PERFORMANCE
We show the complete version of Fig. with more GNNs and datasets involved in Fig. 12 and Fig. [3 We have the observations as follows, which are consistent with the conclusion we draw from the Section 5.2 Generally, in almost all datasets. The phenomenon indicates GNNs' strong ability in capturing the information encoded in the lowest and highest frequency components (c.g., those associate with the smallest and largest frequency values). We have provided detailed rationale in Section 5.2 Note that we also detected a few cases such as I-GNN on Photo and FA on DBLP which we consider be outliers as their curves may be noisy in terms of accuracy variance, which hinders their frequency-capturing ability in the high frequency range. As expected, each GNN finds the most difficulty recovering task-relevant information in the middle frequency components of each dataset.
observe that the V-shape curves maintained across all GNNs
E COMPLIMENTARY RESULTS FOR QUANTITATIVE PERFORMANCE COMPARISON IN THE SPECTRAL DOMAIN
To more accurately study the performance of each GNN under our benchmark, we report the average GNN performance in capturing task-related information different spectrum component areas. Specifically, Tables 3 and [S] report average GNN performance low, middle, high spectrum component
All metrics are multiplied by 100 for readability. We also bolden the highest metrics and underline the second-bee best metrics. Ties are broken by lower standard error.
In the low-frequency range, nearly all models perform well, but GatedGraph, GATv2, and GIN achieve particularly high accuracy, reflecting their strong low-pass filtering capabilities. For the mid-frequency range, ChebNet and GCNII demonstrate superior performance, while models like
19

---

Published as a conference paper at ICLR 2025
Transformer
SAGE
GCNII
GAIv2
GAT
SGC
APPNP
DBLP Photo
090 19 1 20
9
6
16 2 8
6
0
1 20
6 6 10
6 0 1
1
6
0.5
19
0.
1
13
20
0
1 3 20 8
8
06
8 03
0.
19
1
Computers Physies Cora-Full CS
19
05
6 15
6 6 1
1
03
29
9
0
6
0
25 2
6 0-
05
19
10
63-
04
00
1
3
9
0
1
0
19
05
05
19
15
1.-
0.
3 20
0 1 2
3 1
Figure 12: The accuracy curves of different GNNs (Transformer, SAGE, GNNII, GATv2, GAT, SGC, APPNP) in the whole spectral domain. In each subplot, the æ-axis represents the frequency and the y-axis represents the accuracy of GNNs in the node classification task with the ground truth labels derived from the associated frequency bin.
Cheb
FA
GCN
GIN
1-GNN
GPS
GatedGraph
Photo
84-
0-
1.
0
0
9
0
03
1
1
DBLP
1.
15 2
05
19
0
0 19
13
Computers Physies Cora-Full CS
2
3
30
35
65
03
19
15 20
3
0
9 1
05
1
2
12
05
1 8
55,00
50
9
3
3
20
6
3
3
6 0
5
1.0
088
03
Figure 13: The accuracy curves of different GNNs (Cheb, FA, GCN, GIN, I-GNN, GPS and Gat- edGraph) in the whole spectral domain. In each subplot, the rraxis represents the frequency and the y-axis represents the accuracy of GNNs in the node classification task with the ground truth labels derived from the associated frequency bin.
20

---

Published as a conference paper at ICLR 2025
Table 3: AUC for the lower third of the spectrum (multiplied by 10)
Model
Computers
Cora
CS
DBLP
Photo
Physics
Avg. Ranking
APPNP
66.92 2:2
71.35 = 1.42
72.01 1.58
57.99 + 0.76
68.30
3/2
69.10 0.96
13.33 : 0.75
GPS
73.89 2.32
68.31 = 1.19
76.81
1.25
68.18 + 1.14
76.52
2:44
78.94 0.56
11.17 = 1.57
FA
72.27 2,02
77.58 = 1.04
80.16
0.85
63,46 + 1.21
78.70
1.99
76.39
0.79
10.17 = 1.77
Transformer
79.24 1.53
75.01 = 1.54
1.29
72.75 = 1.25
79.70
1.53
76.10 = 1.08
2.67
Cheb
78.66 1.66
73.22 = 1.58
79.22
1.08
772.66 = 1.37
80.59 + 1.41
82.35 0.69
8.83 = 1.77
GatedGraph
68.20
84.35 = 84.86
74.95 +
67.55 1.24
81.29 = 0.46
7.50 = 4.35
SAGE
79.10 1.50
77.50 = 1.01
81.61 +: 0.76
73.69 1: 0.95
80.81 + 1.72
83.48
7.17 = 1.34
GAT
84.58
80.34 1:
75.99
75.26 1:
85.85 1.19
79.89
6.33 1:
GIN
62.51 2.22
82.91 1: 0.74
83.61 1: 0.60
81.31
1 0.77
72.92 1: 2.21
84.67
: 0.71
6.17 1: 4.74
SGC
81.45 1.36
79.45 1
85.28 0.74
70.34 1:
84.15 1.50
84.09
0.73
5.83 1
Graph
66.35
2,42
82.15 +: 0.75
85.67 1: 0.50
77.07
1 0.79
70.36 1: 2.62
86.96
0.58
5.67
1: 4.66
GATv2
84.87
1.38
81.19 1
79.62
77.35
86.83 103
82.15
4.33
GCN
82.20
1.78
81.16 # 1.04
85.14 1.70
71.19 + 1.60
86.40 + 118
85.14 = 0.62
4.33
: 2.75
GCNII
84.03 0.46
78.84
0.35
82.22 = 0.28
79.31
85.00 0.48
84.94 0.18
4.33 2.05
Table 4: AUC for the middle third of the spectrum (multiplied by 10)
Model
Computers
Cora
CS
DBLP
Photo
Physies
Avg. Ranking
GCN
50.01 0.18 38.00 = 0.60
39.81
0.73
42.59 + 0.14
49,91 + 0.23
43.15 0.69
13.33 = 0.75
SGC
48.35
38.90 = 0.50
38.87 0.67
43.13
49.84 0.16
43.69
13.33 +
APPNP
51.00 0.04
47.29 = 0.25
46.41 = 0.20
49.46 am
49.45 + 0.3
47.04 0.12
10.83 = 1.57
GIN
50.75
47.55
44.88
46.85 + 0.93
51.16
46.81
10.83
FA
50.96 0.04
46.16 = 0.37
43.05 0.58
48.27 -
50.89 0.13
47.11 = 0.53
10.83 = L07
Graph
51.23
49.92
48.64 1:44:00 0.66
48.48
50.31 =
49.30
8.17
GatedGraph
51.38 = 0.01
51.41 = 0.27
49.43 0.10
49.57
50.05 + 0.04
49.09 = 0.03
7.33 2.75
GAT
51.19 0.05
49.21 0.45
49.28
0.10
51.81 0.19
50.44 0.11
7.17
GPS
51.39 0.07
48.97 = 0.06
5..19
51.82 0.02
0.07
52.05 = 0.30
5.33 = 1.37
GATv2
52.20 0.10
51.51
50.43 49.9
51.39 0.26
51.03 0.19
4.50
GCNII
54.93 1.17
48.15 = 2.10
49.69
49.64 1.99
55.50 1.66
53.51 2.23
4.17 = 3.29
Transformer
52.92 0.16
49.68 0.17
50.10
50.22 0.17
52.21 0
51.65 0.19
4.17 0.69
SAGE
53.24 0.14
49.37 1 0.33
0.44
51.16 1: 0.31
53.45 0.8
52.31 0.63
= 1.53
Cheb
53.25 0.06
49.97 - 0.05
52.06 0.31
50.70 1 0.11
54.92 0.20
52.96 0.49
2.00 + 0.58
Table 5: AUC for the upper third of the spectrum (multiplied by 10)
Model
Computers
Cora
CS
DBLP
Photo
Physics
Avg. Ranking
FA
55.00 0.07
44.14 +: 0.10
39.53 + 0.05
46.36
1 0.02
58.19 + 0.20
46.85
0.13
13.17 i 1.21
APPNP
54.34 0.05
46.59
43.01
0.05
48.53
54.21
0.20
46.87
12.83 0.69
GIN
53.92 0.07
55.60 = 0.68
48.87 2.11
51.99 + 0.50
59.39
+ 0.26
51.05 = 0.13
11.67 1 0.75
GAT
57.66 0.27
54.30
0.19
5..00
52.50
0.10
61.90
0.54
53.60 0.10
10.33 0.94
SGC
59.17 0.19
67.54 + 0.66
57.33
57.60 + 0.61
63.67 = 041
52.44 - 0.11
7.50 + 2.22
GATv2
58.54 0.22
59.04
0.42
52.92 1: 0.22
64.30 0.68
57.34
0.19
7.50 +: 1.50
GPS
59.38 0.28
58.83 = 0.08
55.20 - 0.06
.5.779 1: 0.20
64.09 +: 0.37
60.00
0.02
6.83 +: 1.95
Cheb
61.12 0.20
60.25
0.16
53.97
0.07
62.13 1: 0.30
64.24
0.35
56.31
0.03
6.67 1.89
Graph
52.01 0.01
73.94 1
67.27
0.29
68.78 1 0.42
55.58 1 0.88
62.32
0.05
5.50 1: 5.68
GCNII
63.25 0.35
57.26 1 0.98
59.58
0.35
48.46 1: 0.68
68.86
0.53
63.84
0.09
5.17 1: 4.63
GCN
60.72 0.19
70.06
0.62
58.13
0.36
59.84 1: 0.60
65.17
041
53.84
0.16
5.17 1 1.57
GatedGraph
57.80 0.16
75.86 = 092
66,80 0.91
68.59
1.66
64.67 0.53
53.22 = 0.12
4.83 = 3.53
Transformer
64.40 0.37
65.71 0.50
56.23
0.23
64.16
67.64
57.22 0.17
4.33 =
SAGE
63.54 0.32
66.98 0.22
59.13 0.10
65.33 0.27
66.22 0.39
59.82 0.05
3.50 + 0.96
21

---

Published as a conference paper at ICLR 2025
GATv2 and Transformer also perform consistently across multiple datasets. However, surprisingly, models such as FA and APPNP begin to show weaknesses in this region, with their performance dropping notably. In the frequeeyyy domain, GCNII once again leads the pack in Photo and Physics as well as the 1-WI. graph operator while models such as GAT and FA struggle to maintain competitive results. Interestingly, SGC performs better than expected in the upper spectrum, despite being designed as a simplified GCN variant.
Overall, the trend shows that while most models are capable in the lower spectral ranges, only few-like GCNII and Graph-exhibit balanced performance across the entire spectrum, particularly excelling in adapting higher frequencies.
F COMPLEMENTARY RESULTS FOR PARAMETER STUDY
To demonstrate the robustness of our results, we run experiments under our benchmark settings us- ing wider and deeper GNNs. Specifically, we re-run our benchmark using twice as many hidden dimensions (128 versus 64) and varying layer depths (up to 4) in order to test whether these hy- perparameters can significantly affect each GNN's ' frequency adaptation abilities. In Figure [4] we present parameter studies across co-author datasets. In all of our ablations, cant shift in overall frequency adaptation behavior from the original plots in 2 suggesting that layer depth and width are not enough to improve or worsen GNN frequency adaptation capabilities.
observe signifi-
Transformer
SAGE
GATv2
GAT
SGC
Accuracy
1.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
Layes
Frequency
Layer
40
Prequency
3 Layen
40
Frequency
Layens
Frequencyy
Layers
40
Prequency
2ac
Transformer
SAGE
GATv2
GAT
Accuracy
1.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
Layers
Frequencyy
Layers
Prequency
Layers
Frequency
Layers
Frequency
Layers
Frequency
Transformer
SAGE
GATv2
GAT
SGC
Accuracy
1.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
Layers
Frequency
Layers
40
Prequency
Layen
4
Frequency
Layers
40
Prequency
Layers
40
Prequency
Figure 14: Parameter studies for Photo (top row), DBLP (moddle row) and Cora_full full (bottom row), where the each subplot is GNN's accuracy spectral tendency curve on certain graph dataset with various (2 2/3 3/ //4 4) GNN layers
22


Reviews:
[{"review_id": "3hh4msrJxq", "reviewer": "Reviewer_643X", "summary": "This paper aims to study the effect of non-linear layers in graph neural networks (GNNs) on their spectral characteristics, in terms of their ability to represent information of different graph frequencies. Prior work focuses only on neighborhood aggregation and seeks to design filters that can represent graph frequencies more flexibly, but the current work considers GNNs holistically (including their nonlinearities) to empirically study their ability to represent different graph frequencies.\n\nThey first conduct a motivating experiment to show that GNNs can still recover frequency components which are filtered out by neighborhood aggregation, indicating the crucial role of nonlinear layers. Then, they construct a benchmark aiming to understand how well models can represent graph frequencies in different bucketized ranges. This is done by constructing classification tasks where the input is constructed using signals from one block of graph frequencies, and the output is a discretization of signals from a different block of graph frequencies, and then we measure the performance on this classification task. Theoretical results show that the discretization process does not give significant deviation in the spectral characteristics. \n\nThen they empirically find using the benchmark that (1) GNNs show a U curve in their frequency response; (2) certain (mostly spatial) GNNs like SAGE perform better on this task; (3) the benchmark gives a useful ordering of methods that correlates with their performance on real-world (heterophilic?) node classification tasks; (4) the shape of the accuracy curves does not significantly change with the number of layers.", "questions": "- In the experiment in section 5.4, I could not understand what the authors mean by r4 being defined as \"Original Task Ranking\", or describing it as \"the node classification rankings r4 directly derived from the node classification task on the chosen six datasets.\" In particular, how does this differ from r1 (which also seems to be the ranking of methods on the node classification task)?\n\n- In the same experiment, please clarify if the datasets were specifically chosen as examples of heterophilic datasets (or if not, why these 6 datasets in particular were chosen).\n\n- Figure 3 is somewhat confusing - the caption states that the 3 subfigures correspond to low, medium, and high frequency ranges, but then the x-axis of each subplot also corresponds to low, medium and high frequency ranges? Could you clarify what is the difference between these?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Interesting and seemingly understudied problem aiming to consider GNNs holistically (including their nonlinearities) in the spectral domain. \n\n- The accuracy curves seem like an interesting way of testing the ability of different GNNs to represent different frequencies, and provides an interesting \"V curves\" insight in RQ1.\n\n- A real world case study is done, finding that the GNN rankings obtained from the benchmark are informative for deciding which GNNs are better than others on a series of real-world graph datasets.", "weaknesses": "- Clarity: some parts of the motivation are hard to understand, particularly due to some overly vague statements. For example, in the introduction, to make the motivation clear (particularly for readers who are less familiar with the cited works), I suggest precisely stating the common belief you are arguing against, and which papers exactly have demonstrated this common belief, and in what ways they use it. Similarly, Problem 2.1 is also too vague, e.g. it is unclear to the reader what \"the key information\" means. Similarly, in page 7, the paper also writes that RQ1 disagrees with \"the prevalent opinion\", without making it clear what this prevalent opinion is exactly, who expresses it, and why it is significant. \n\n- The notion and computation of \"accuracy curves\" seems to be a main contribution of the paper, but I find it hard to appreciate what the reader should exactly take away from these accuracy curves, partly due to the complexity of their definition. From what I understand, they group the eigenvalues into (low, medium, high) frequencies, and then the mean of eigenvectors from 1 group to predict another group (as done in section 3), and then in section 4 it is the same except discretizing the outputs. So in figure 2, what are the input frequencies being used? Overall, it seems that the main goal of this section is to give the reader some useful insights, but it is hard to extract useful insights as the definitions are rather complex. In terms of insights, the V shape behavior in RQ1 is indeed somewhat interesting, but I still find that there is a lack of clearly practical insights.\n\n- While the ranking of methods is also a practical insight in some sense, I am not quite convinced that this is really a practical way of ranking methods that one would actually want to use for real use cases. If I wanted to decide which GNN to use on a particular dataset, it seems more reasonable to rely on (1) the performance on the validation set or a held-out subset of the training set, or in the worst case (2) the performance on some other real-world datasets (which are ideally reasonably similar to mine). Does the current benchmark really perform better (or otherwise preferable in some way) at least compared to option (2) above (if so, it may be good to validate this assumption empirically)? Alternatively, if the authors could show that the benchmark provides some useful insights about methods (e.g. what causes SAGE to perform significantly better on this benchmark than other methods), that may also be useful.\n\n- It is not clear how robust the rankings are to different choices of hyperparameters for the methods. Although the experiment in RQ4 does test the effect of different layer numbers, there is a lack of quantitative results (as the 3d plots are not clear enough to see to what extent the different hyperparameters actually affect the statistics such as normalized AUC or the ranking between methods).\n\nAdditional points (minor)\n\n- Section 4.1: when describing the experimental protocol, please either describe all the necessary details, or cross-reference (e.g. to the appendix) to where they are given. For example, you should explain how the discretization is done (or cross-reference).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "woZd2r0dzT", "reviewer": "Reviewer_U2Hy", "summary": "The paper shows that GNN is not only a neighbor's filter but can handle different types of graph information better than previously thought. This is interesting!", "questions": "Your findings suggest GNNs struggle with middle-frequency information. Could you elaborate on potential modifications or techniques that might specifically enhance GNN performance in this range? How can we evaluate it?\n\n\nHave you validated the benchmark against any real-world applications (e.g., molecular biology, recommendation systems) to confirm its predictive capability in practical settings?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "I really appreciate the thorough empirical work they did. Instead of just making claims, they:\ndid careful preliminary experiments to show this unexpected capability, tested on real-world datasets and made everything with theoretical analysis.\n\nAnother strength is how they formalized this into an evaluation framework. It's not just about showing this phenomenon - they developed systematic ways to measure and compare different GNNs' capabilities in handling various frequency components. This gives the field new tools to understand GNN behavior.\n\nTheir findings suggest we might need to rethink how we design and analyze GNNs. If GNNs aren't just filters but can actually generate new frequency patterns.", "weaknesses": "The benchmark may be overly simplified, as real-world tasks rarely exhibit such clear-cut frequency separations, limiting the applicability of the results to more complex, real-world scenarios.\n\nMost experiments were done with 2-layer GNNs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IYGsbOawYG", "reviewer": "Reviewer_EWWr", "summary": "This paper introduces a benchmark designed to evaluate Graph Neural Networks (GNNs) from a spectral perspective. Through the benchmarking process, along with theoretical analysis and empirical evaluation, the authors aim to demonstrate that GNNs can flexibly produce outputs with a diverse range of frequency components, even when certain frequencies are missing in the input.", "questions": "The meaning of \"original task ranking\" in Section 5.4 remains unclear. If node classification is the only task, does the benchmarking task ranking refer to an averaged ranking across multiple GNNs, with the original task ranking denoting the rank of a single GCN? A clearer explanation of this experimental setup would help clarify the significance of the conclusions presented in this section.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper is well-structured.\n2.\tMany experiments are conducted.", "weaknesses": "1. Flawed assumptions in Experimental Design: The key assumption presented on line 183, which states, \"We note that graph filters cannot generate frequency components that are not originally contained in the input graph data,\" appears flawed.\n\n    * In a graph Laplacian space, high and low frequencies are interpreted relative to the eigenvalue spectrum rather than by fixed boundaries (which the authors also do not specify). For instance, even if all eigenvalues are small in magnitude, they can be ordered to produce relative high or low frequencies for graph filters. This explains why, in Figure 1, low-frequency inputs can recover high-frequency signals—because the model filters out relatively high-frequency portions within the low-frequency signal, which the neural network then amplifies to align with the high frequency target.\n\n    * The performance using certain frequency as the training target cannot be used to explain the results produced by using label as the training target as they are not causally linked, and the theoretical analysis of the paper does not convincingly resolve this concern.\n\n        * While models may learn high-frequency signals by training on low-frequency inputs, this does not guarantee that supervised learning with labels inherently captures the necessary high-frequency information. No evidence is provided to substantiate a causal relationship between certain frequency components and labels; either may be fitted independently. As noted on line 77, these ground-truth are usually a composition of different frequency components and does not show clear incentive patterns preferring certain frequency components.\n        * While the theoretical analysis shows that discretizing a continuous energy distribution related to frequency has minimal deviation, it does not substantiate a fundamental connection between label distributions and discretized energy distribution. In other words, the discretization of energy distributions does not necessarily correlate with labels. The authors need to provide more detailed proofs to clarify a causal relationship between energy distribution and labels. However, given previous work [4][5], which shows that nodes of the same label on a heterophilic graph often present a mixed homophily of structures (demonstrating various frequencies), this causal link remains questionable.\n2. Benchmark Design Limitations: On line 52, the authors mention that heterophilic graphs are more likely to benefit from high-frequency components in graph data. However, the benchmarking evaluation relies solely on homophilic graphs, which may inadequately capture GNNs' adaptive learning capabilities across different frequencies under label supervision. (Except for several heterophilic graphs only presented in case study).\n3. Lack of Novel Insights in Experimental Results:\n    * Qualitative Findings: Similar findings with explanations have been reported in existing works [2][3]. For example, traditional GCNs perform well in extreme low-frequency (high-homophily) and extreme high-frequency (low-homophily) conditions, struggling in mid-homophily settings. This is explained as low-homophily neighborhoods with sufficiently distinct averages can still benefit from low-frequency filtering.\n    * Quantitative Performance Analysis Misrepresentation: The quantitative analysis lacks accuracy. In line 419, the authors claim that the spectral filtering ability of GCNII is “rarely discussed and evaluated,” yet the original study explicitly highlights its polynomial graph filtering capability. Additionally, since all datasets used are homophilic (dominated by low frequencies), this setup fails to provide sufficient evidence to support the claims made about GNN flexibility in frequency handling.\n4.\tLack of Necessity in the Study's Focus:\n    * Many GNNs are inherently capable of flexible filtering (e.g., GCNII and ChebNet used in benchmarking, both of which offer polynomial graph filtering), enabling them to encode a range of frequency components by design.\n    * Theoretical results for GCNII also show that GNNs with initial residual connections can achieve polynomial graph filtering, implying that even standard GCNs can encode various frequencies with basic modifications such as residual connections. As shown in [1], classic GNNs can serve as strong baselines on heterophilic graphs requiring high-frequency information when paired with simple techniques like residual connections and dropout.\n\nReference\n[1].\tLuo, Yuankai, Lei Shi, and Xiao-Ming Wu. \"Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification.\" arXiv preprint arXiv:2406.08993 (2024).\n\n[2].\tMa, Yao, et al. \"Is homophily a necessity for graph neural networks?.\" arXiv preprint arXiv:2106.06134 (2021).\n\n[3].\tLuan, Sitao, et al. \"When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[4].\tYang, Liang, et al. \"Diverse message passing for attribute with heterophily.\" Advances in Neural Information Processing Systems 34 (2021): 4751-4763.\n\n[5].\tSuresh, Susheel, et al. \"Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns.\" Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bFgML0SvFl", "reviewer": "Reviewer_oUdo", "summary": "This work focusses on benchmarking current GNNs concerning their spectral perspective. It first conducts an exploratory study to show that GNNs can predict unseen frequency from the graph data and such ability is then evaluated in the protocol along with the node classification performance against 14 GNNs. The framework to measure the GNNs’ capability to capture and\nleverage information across different frequency components is interesting.", "questions": "In line 431, the author said “Instead, GNNs such as GATv2 and GCN achieve clear superiority over other GNNs in learning from middle frequency components.” Could you elaborate more why GCN is superior here? Upon middle frequency, the neighbors are often connected with mixed labels. GCN’s uniform aggregation can hardly distinguish such results.\n\nI'm willing to raise the score if concerns can be well addressed.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1-\tThe evaluation from the spectral perspective is interesting and provides new insights.\n\n2-\tThe presentation is good, making the paper easy to read.", "weaknesses": "1-\tThe EXPLORATORY STUDY needs more elaboration/evaluation. Current experiments show that GNNs can predict unseen frequency signals from graph data, which is not necessarily supports that “the filter resulted from the neighborhood aggregation does not dominate the behavioral characteristics of GNNs in the spectral domain”. Extra comparison with GNNs without graph signal input is needed to evaluate the extent of “A”.\n\n2-\tThe scope of GNNs and datasets are restricted mostly to homophily ones. It would be helpful to incorporate heterophily GNNs considering their capability of high frequency domains.\n\n3-\tLacks of discussion of existing spectral GNN benchmarks, for example [1].\n\n[1] Benchmarking Spectral Graph Neural Networks: A Comprehensive Study on Effectiveness and Efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)