Piecewise Constant Spectral Graph Neural Network

Vahan Martirosyan, Jhony H. Giraldo, Fragkiskos D. Malliaros

Abstract

Graph Neural Networks (GNNs) have achieved significant success across various domains by leveraging graph structures in data. Existing spectral GNNs, which use low-degree polynomial filters to capture graph spectral properties, may not fully identify the graph's spectral characteristics because of the polynomial's small degree. However, increasing the polynomial degree is computationally expensive and, beyond certain thresholds, leads to performance plateaus or degradation. In this paper, we introduce the Piecewise Constant Spectral Graph Neural Network (PieCoN) to address these challenges. PieCoN combines constant spectral filters with polynomial filters to provide a more flexible way to leverage the graph structure. By adaptively partitioning the spectrum into intervals, our approach increases the range of spectral properties that can be effectively learned. Experiments on nine benchmark datasets, including both homophilic and heterophilic graphs, demonstrate that PieCoN is particularly effective on heterophilic datasets, highlighting its potential for a wide range of applications. The implementation of PieCoN is available at.

Benchmark Results

Tested on 4 datasets 13 baseline values reported too low

Tables show presented results in global context (best 3 papers + GCN + MLP).

Classic

Amazon-Photo

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	GraphTARIF code ↗ Hyb global	0.9703 ±0.0019	Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification code ↗
2	GAT GNN baseline actual #2 vs paper #401 399 places worse	0.9669 ±0.0014 best reported	actual #2 vs paper #401 399 places worse paper 0.9094 ±0.0068 best at pub: SignGT: Signed Attention-based Graph Transformer for Graph Representation Learning (2023) best today: Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification (2026) paper 0.9094 ±0.0068 Δ at pub 0.0404 Δ today 0.0575
3	GAT+T code ↗ Hyb global	0.9660 ±0.0007	Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification code ↗
7	SAGE code ↗ GNN global	0.9643 ±0.0027	Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification code ↗
8	GCN GNN baseline actual #8 vs paper #502 494 places worse	0.9632 ±0.0008 best reported	actual #8 vs paper #502 494 places worse paper 0.8587 ±0.0083 best at pub: SignGT: Signed Attention-based Graph Transformer for Graph Representation Learning (2023) best today: Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification (2026) paper 0.8587 ±0.0083 Δ at pub 0.0889 Δ today 0.1045
18	Specformer GT baseline actual #18 vs paper #42 24 places worse	0.9580 ±0.0026 best reported	actual #18 vs paper #42 24 places worse paper 0.9529 ±0.0030 best at pub: NTFormer: A Composite Node Tokenized Graph Transformer for Node Classification (2024) paper 0.9529 ±0.0030 Δ at pub 0.0051
25	PieCoN Hyb ★ proposed	0.9565 ±0.0034	This paper
35	JacobiConv GNN baseline actual #35 vs paper #37 2 places worse	0.9543 ±0.0023 best reported	actual #35 vs paper #37 2 places worse paper 0.9536 ±0.0024 best at pub: LON-GNN: Spectral GNNs with Learnable Orthonormal Basis (2023) best today: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) Difference within reported uncertainty; not counted as underperformance. paper 0.9536 ±0.0024 Δ at pub 0.0007 Δ today 0.0007
55	PPGNN GNN baseline	0.9509 ±0.0031	This paper
61	UniFilter GNN baseline	0.9496 ±0.0074	This paper
62	ChebNetII GNN baseline actual #62 vs paper #62	0.9492 ±0.0033	actual #62 vs paper #62 paper 0.9492 ±0.0033 prev best: A Quasi-Wasserstein Loss for Learning Graph Neural Networks (WWW 2023) paper 0.9492 ±0.0033 Δ at pub 0.0142
63	DSF-Jacobi-R GNN baseline	0.9490 ±0.0031	This paper
70	OptBasisGNN GNN baseline	0.9471 ±0.0033	This paper
87	GCNII GNN baseline actual #87 vs paper #451 364 places worse	0.9430 ±0.0020 best reported	actual #87 vs paper #451 364 places worse paper 0.8994 ±0.0031 best at pub: Polynormer: Polynomial-Expressive Graph Transformer in Linear Time (ICLR 2024) paper 0.8994 ±0.0031 Δ at pub 0.0436
112	GPR-GNN GNN baseline	0.9385 ±0.0028	This paper
118	ChebyNet GNN baseline	0.9377 ±0.0032	This paper
127	BernNet GNN baseline actual #127 vs paper #129 2 places worse	0.9368 ±0.0028 best reported	actual #127 vs paper #129 2 places worse paper 0.9363 ±0.0035 best at pub: A Quasi-Wasserstein Loss for Learning Graph Neural Networks (WWW 2023) Difference within reported uncertainty; not counted as underperformance. paper 0.9363 ±0.0035 Δ at pub 0.0005
190	LanczosNet GNN baseline	0.9321 ±0.0085	This paper
218	H_2GCN GNN baseline	0.9302 ±0.0091	This paper
390	MLP code ↗ Trad global	0.9128 ±0.0063	Clarify Confused Nodes via Separated Learning code ↗
502	Free eigenvalues GNN baseline	0.8608 ±0.0081	This paper

Heterophilic Graphs

Texas

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	P^2GNN Hyb global	0.9672 ±0.0147	$P^2$GNN: Two Prototype Sets to boost GNN Performance
2	DoG code ↗ ext data GNN global	0.9660 ±0.0210	Diffusion on Graph: Augmentation of Graph Structure for Node Classification code ↗
3	GPF-plus code ↗ ext data GNN global	0.9583 ±0.0419	ProG: A Graph Prompt Learning Benchmark code ↗
20	OptBasisGNN GNN baseline actual #20 vs paper #100 80 places worse	0.9348 ±0.0168 best reported	actual #20 vs paper #100 80 places worse paper 0.8738 ±0.0279 best at pub: Simplified PCNet with Robustness (2024) paper 0.8738 ±0.0279 Δ at pub 0.0610
21	JacobiConv GNN baseline actual #21 vs paper #72 51 places worse	0.9344 ±0.0213 best reported	actual #21 vs paper #72 51 places worse paper 0.8902 ±0.0279 best at pub: Simplified PCNet with Robustness (2024) best today: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) paper 0.8902 ±0.0279 Δ at pub 0.0442 Δ today 0.0442
22	BernNet GNN baseline actual #22 vs paper #72 50 places worse	0.9328 ±0.0148 best reported	actual #22 vs paper #72 50 places worse paper 0.8902 ±0.0345 best at pub: A Quasi-Wasserstein Loss for Learning Graph Neural Networks (WWW 2023) Difference within reported uncertainty; not counted as underperformance. paper 0.8902 ±0.0345 Δ at pub 0.0426
23	ChebNetII GNN baseline actual #23 vs paper #72 49 places worse	0.9328 ±0.0147 best reported	actual #23 vs paper #72 49 places worse paper 0.8911 ±0.0343 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) best today: Simplified PCNet with Robustness (2024) Difference within reported uncertainty; not counted as underperformance. paper 0.8911 ±0.0343 Δ at pub 0.0417 Δ today 0.0417
30	GPR-GNN GNN baseline actual #30 vs paper #81 51 places worse	0.9291 ±0.0132 best reported	actual #30 vs paper #81 51 places worse paper 0.8853 ±0.0336 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8853 ±0.0336 Δ at pub 0.0438
34	MLP Trad global	0.9230 ±0.0070	Design your own universe: a physics-informed agnostic method for enhancing graph neural networks
40	H2GCN GNN baseline actual #40 vs paper #84 44 places worse	0.9189 ±0.0393 best reported	actual #40 vs paper #84 44 places worse paper 0.8836 ±0.0262 best at pub: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) Difference within reported uncertainty; not counted as underperformance. paper 0.8836 ±0.0262 Δ at pub 0.0353
53	GraphSAGE code ↗ GNN global	0.9000 ±0.0365	Graph Neural Networks Need Cluster-Normalize-Activate Modules code ↗
67	PieCoN Hyb ★ proposed	0.8934 ±0.0311	This paper
70	GCNII GNN baseline actual #70 vs paper #70	0.8918 ±0.0443	actual #70 vs paper #70 paper 0.8918 ±0.0443 prev best: Global-Local Graph Neural Networks for Node-Classification (2024) paper 0.8918 ±0.0443 Δ at pub 0.0761
71	DSF-Jacobi-R GNN baseline	0.8918 ±0.0344	This paper
87	Specformer GT baseline actual #87 vs paper #175 88 places worse	0.8823 ±0.0038 best reported	actual #87 vs paper #175 88 places worse paper 0.8360 ±0.0327 best at pub: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) Difference within reported uncertainty; not counted as underperformance. paper 0.8360 ±0.0327 Δ at pub 0.0463
88	Free eigenvalues GNN baseline	0.8820 ±0.0328	This paper
105	UniFilter GNN baseline	0.8672 ±0.0377	This paper
113	ChebyNet GNN baseline actual #113 vs paper #286 173 places worse	0.8622 ±0.0245 best reported	actual #113 vs paper #286 173 places worse paper 0.7721 ±0.0295 best at pub: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) paper 0.7721 ±0.0295 Δ at pub 0.0901
132	PPGNN GNN baseline	0.8557 ±0.0262	This paper
211	GAT GNN baseline actual #211 vs paper #280 69 places worse	0.8162 ±0.0645 best reported	actual #211 vs paper #280 69 places worse paper 0.7754 ±0.0098 best at pub: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) best today: Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (2025) paper 0.7754 ±0.0098 Δ at pub 0.0328 Δ today 0.0408
257	GCN GNN baseline actual #257 vs paper #266 9 places worse	0.7933 ±0.0447 best reported	actual #257 vs paper #266 9 places worse paper 0.7869 ±0.0180 best at pub: Graph Wave Networks (WWW 2025) Difference within reported uncertainty; not counted as underperformance. paper 0.7869 ±0.0180 Δ at pub 0.0064
299	LanczosNet GNN baseline	0.7639 ±0.0443	This paper

Actor

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DiGGR Hyb global	0.4535 ±0.0353	Disentangled Generative Graph Representation Learning
2	TRIGON code ↗ Hyb global	0.4402 ±0.0028	Dynamic Triangulation-Based Graph Rewiring for Graph Neural Networks code ↗
3	DoG code ↗ ext data GNN global	0.4320 ±0.0120	Diffusion on Graph: Augmentation of Graph Structure for Node Classification code ↗
11	OptBasisGNN GNN baseline	0.4239 ±0.0052	This paper
19	Specformer GT baseline actual #19 vs paper #26 7 places worse	0.4193 ±0.0104 best reported	actual #19 vs paper #26 7 places worse paper 0.4156 ±0.0125 best at pub: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) Difference within reported uncertainty; not counted as underperformance. paper 0.4156 ±0.0125 Δ at pub 0.0037
21	BernNet GNN baseline	0.4179 ±0.0101	This paper
22	ChebNetII GNN baseline	0.4175 ±0.0107	This paper
24	Free eigenvalues GNN baseline	0.4161 ±0.0063	This paper
34	JacobiConv GNN baseline actual #34 vs paper #41 7 places worse	0.4117 ±0.0064 best reported	actual #34 vs paper #41 7 places worse paper 0.4043 ±0.0081 best at pub: Graph Neural Networks with Learnable and Optimal Polynomial Bases (ICML 2023) best today: GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2024) Difference within reported uncertainty; not counted as underperformance. paper 0.4043 ±0.0081 Δ at pub 0.0074 Δ today 0.0074
38	GCNII GNN baseline actual #38 vs paper #136 98 places worse	0.4082 ±0.0179 best reported	actual #38 vs paper #136 98 places worse paper 0.3689 ±0.0095 best at pub: Feature Expansion for Graph Neural Networks (ICML 2023) best today: $P^2$GNN: Two Prototype Sets to boost GNN Performance (2026) paper 0.3689 ±0.0095 Δ at pub 0.0172 Δ today 0.0393
42	MLP Trad global	0.4026 ±0.0108	Heterophily-Aware Graph Attention Network
44	UniFilter GNN baseline	0.4011 ±0.0131	This paper
53	GPR-GNN GNN baseline actual #53 vs paper #53	0.3992 ±0.0067	actual #53 vs paper #53 paper 0.3992 ±0.0067 prev best: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) Improvement within reported uncertainty; not highlighted. paper 0.3992 ±0.0067 Δ at pub 0.0001
54	DSF-Jacobi-R GNN baseline	0.3989 ±0.0054	This paper
57	PPGNN GNN baseline	0.3965 ±0.0066	This paper
64	ChebyNet GNN baseline actual #64 vs paper #111 47 places worse	0.3917 ±0.0143 best reported	actual #64 vs paper #111 47 places worse paper 0.3761 ±0.0089 best at pub: Heterophily-Aware Graph Attention Network (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.3761 ±0.0089 Δ at pub 0.0156
68	GraphSAGE code ↗ GNN global	0.3899 ±0.0085	A Quasi-Wasserstein Loss for Learning Graph Neural Networks code ↗
71	H2GCN GNN baseline actual #71 vs paper #192 121 places worse	0.3885 ±0.0117 best reported	actual #71 vs paper #192 121 places worse paper 0.3586 ±0.0103 best at pub: ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting (2022) best today: $P^2$GNN: Two Prototype Sets to boost GNN Performance (2026) paper 0.3586 ±0.0103 Δ at pub 0.0254 Δ today 0.0299
84	LanczosNet GNN baseline	0.3816 ±0.0091	This paper
135	GCN GNN baseline actual #135 vs paper #246 111 places worse	0.3690 best reported	actual #135 vs paper #246 111 places worse paper 0.3465 ±0.0068 best at pub: Beyond Low-frequency Information in Graph Convolutional Networks (AAAI 2021) paper 0.3465 ±0.0068 Δ at pub 0.0225
182	GAT GNN baseline actual #182 vs paper #270 88 places worse	0.3605 ±0.0035 best reported	actual #182 vs paper #270 88 places worse paper 0.3393 ±0.0247 best at pub: Hierarchical Graph Transformer with Adaptive Node Sampling (NeurIPS 2022) Difference within reported uncertainty; not counted as underperformance. paper 0.3393 ±0.0247 Δ at pub 0.0212

Heterophily Benchmark

Amazon-ratings

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	UniGAP global	0.6375 ±0.0110	UniGAP: A Universal and Adaptive Graph Upsampling Approach to Mitigate Over-Smoothing in Node …
2	H2GCN + HalfHop GNN global	0.5961 ±0.0100	UniGAP: A Universal and Adaptive Graph Upsampling Approach to Mitigate Over-Smoothing in Node …
3	GraphSAGE + HalfHop GNN global	0.5897 ±0.0150	UniGAP: A Universal and Adaptive Graph Upsampling Approach to Mitigate Over-Smoothing in Node …
7	H2GCN GNN baseline actual #7 vs paper #120 113 places worse	0.5681 ±0.0090 best reported	actual #7 vs paper #120 113 places worse paper 0.4817 ±0.0052 best at pub: UniGAP: A Universal and Adaptive Graph Upsampling Approach to Mitigate Over-Smoothing in Node Classification Tasks (2024) paper 0.4817 ±0.0052 Δ at pub 0.0864
12	SAGE code ↗ GNN global	0.5569 ±0.0023	Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification code ↗
14	GAT GNN baseline actual #14 vs paper #85 71 places worse	0.5028 ±0.0055	actual #14 vs paper #85 71 places worse paper 0.5028 ±0.0055 prev best: Graph Neural Networks for Graphs with Heterophily: A Survey (2022) best today: Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification (2026) paper 0.5028 ±0.0055 Δ at pub 0.0119 Δ today 0.0531
24	GCN GNN baseline actual #24 vs paper #109 85 places worse	0.5411 ±0.0034 best reported	actual #24 vs paper #109 85 places worse paper 0.4880 ±0.0022 best at pub: UniGAP: A Universal and Adaptive Graph Upsampling Approach to Mitigate Over-Smoothing in Node Classification Tasks (2024) best today: Graph Transductive Sharpening: Leveraging Unlabeled Predictions in Node Classification (2026) paper 0.4880 ±0.0022 Δ at pub 0.0500 Δ today 0.0531
56	PieCoN Hyb ★ proposed	0.5237 ±0.0050	This paper
84	MLP Trad global	0.5058	Understanding Heterophily for Graph Neural Networks
87	ChebyNet GNN baseline	0.5020 ±0.0052	This paper
92	UniFilter GNN baseline	0.5002 ±0.0070	This paper
103	GPR-GNN GNN baseline actual #103 vs paper #103	0.4937 ±0.0071	actual #103 vs paper #103 paper 0.4937 ±0.0071 prev best: Evolving Computation Graphs (ICML 2023) paper 0.4937 ±0.0071 Δ at pub 0.0449
109	BernNet GNN baseline	0.4882 ±0.0020	This paper
110	OptBasisGNN GNN baseline	0.4880 ±0.0021	This paper
111	ChebNetII GNN baseline	0.4879 ±0.0021	This paper
112	DSF-Jacobi-R GNN baseline	0.4868 ±0.0034	This paper
114	JacobiConv GNN baseline actual #114 vs paper #114	0.4853 ±0.0096	actual #114 vs paper #114 paper 0.4853 ±0.0096 prev best: Evolving Computation Graphs (ICML 2023) paper 0.4853 ±0.0096 Δ at pub 0.0498
117	LanczosNet GNN baseline	0.4835 ±0.0040	This paper
122	PPGNN GNN baseline	0.4796 ±0.0089	This paper
135	GCNII GNN baseline	0.4660 ±0.0120	This paper
156	Free eigenvalues GNN baseline	0.4428 ±0.0113	This paper

SOTA performance (not significantly different from the best) Proposed method (this paper) Baseline / comparison (this paper) Global context (other papers) Best at pub — reported result worse than the best known when published (best reported in green) Best at pub — reported value improved over the best known when published Improved at pub — later paper surpassed this result