Graph Neural Networks with Learnable and Optimal Polynomial Bases

Yuhe Guo, Zhewei Wei

Abstract

Polynomial filters, a kind of Graph Neural Networks, typically use a predetermined polynomial basis and learn the coefficients from the training data. It has been observed that the effectiveness of the model is highly dependent on the property of the polynomial basis. Consequently, two natural and fundamental questions arise: Can we learn a suitable polynomial basis from the training data? Can we determine the optimal polynomial basis for a given graph and node features? In this paper, we propose two spectral GNN models that provide positive answers to the questions posed above. First, inspired by Favard's Theorem, we propose the FavardGNN model, which learns a polynomial basis from the space of all possible orthonormal bases. Second, we examine the supposedly unsolvable definition of optimal polynomial basis from Wang&Zhang (2022) and propose a simple model, OptBasisGNN, which computes the optimal basis for a given graph structure and graph signal. Extensive experiments are conducted to demonstrate the effectiveness of our proposed models. Our code is available at https://github.com/yuziGuo/FarOptBasis.

Benchmark Results

Tested on 5 datasets 4 baseline values reported too low

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

OGB

ogbn-papers100M

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	SGC code ↗ GNN global	0.7910	Unifews: You Need Fewer Operations for Efficient Graph Neural Networks code ↗
2	GAMLP code ↗ GNN global	0.7036 ±0.0002	Learning on Large-scale Text-attributed Graphs via Variational Inference code ↗
3	GLEM-GNN code ↗ GNN global	0.7036 ±0.0002	Learning on Large-scale Text-attributed Graphs via Variational Inference code ↗
18	OptBasisGNN GNN baseline	0.6722 ±0.0015	This paper
21	ChebNetII GNN baseline	0.6718 ±0.0032	This paper
35	SAGE code ↗ GNN global	0.6644 ±0.0017	Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs code ↗
95	MLP code ↗ Trad global	0.4960 ±0.0030	Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group … code ↗

Heterophilic Graphs

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 ↗
4	FavardGNN Hyb ★ proposed	0.4305 ±0.0053	This paper
11	OptBasisGNN GNN baseline	0.4239 ±0.0052	This paper
21	BernNet GNN baseline actual #21 vs paper #22 1 place worse	0.4179 ±0.0101 best reported	actual #21 vs paper #22 1 place worse paper 0.4171 ±0.0112 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) best today: $P^2$GNN: Two Prototype Sets to boost GNN Performance (2026) Difference within reported uncertainty; not counted as underperformance. paper 0.4171 ±0.0112 Δ today 0.0008
22	ChebNetII GNN baseline	0.4175 ±0.0107	This paper
34	JacobiConv GNN baseline	0.4117 ±0.0064	This paper
41	APPNP GNN baseline actual #41 vs paper #54 13 places worse	0.4046 ±0.0064 best reported	actual #41 vs paper #54 13 places worse paper 0.3976 ±0.0049 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) best today: A Quasi-Wasserstein Loss for Learning Graph Neural Networks (WWW 2023) Difference within reported uncertainty; not counted as underperformance. paper 0.3976 ±0.0049 Δ today 0.0070
42	MLP Trad baseline actual #42 vs paper #43 1 place worse	0.4026 ±0.0108 best reported	actual #42 vs paper #43 1 place worse paper 0.4018 ±0.0055 best at pub: Heterophily-Aware Graph Attention Network (2023) Difference within reported uncertainty; not counted as underperformance. paper 0.4018 ±0.0055 Δ at pub 0.0008
53	GPR-GNN GNN baseline actual #53 vs paper #53	0.3992 ±0.0067 best reported	actual #53 vs paper #53 paper 0.3991 ±0.0062 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) best today: Piecewise Constant Spectral Graph Neural Network (TMLR 2025) Difference within reported uncertainty; not counted as underperformance. paper 0.3991 ±0.0062 Δ today 0.0001
68	GraphSAGE code ↗ GNN global	0.3899 ±0.0085	A Quasi-Wasserstein Loss for Learning Graph Neural Networks code ↗
88	ChebNet GNN baseline actual #88 vs paper #114 26 places worse	0.3802 ±0.0023 best reported	actual #88 vs paper #114 26 places worse paper 0.3742 ±0.0058 best at pub: Node-oriented Spectral Filtering for Graph Neural Networks (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.3742 ±0.0058 Δ at pub 0.0060
111	ARMA GNN baseline	0.3767 ±0.0054	This paper
135	GCN GNN baseline actual #135 vs paper #284 149 places worse	0.3690 best reported	actual #135 vs paper #284 149 places worse paper 0.3326 ±0.0115 best at pub: Beyond Low-frequency Information in Graph Convolutional Networks (AAAI 2021) paper 0.3326 ±0.0115 Δ at pub 0.0364

LINKX Benchmarks

Penn94

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DC-GNN GNN global	0.8669 ±0.0022	Differentiable Cluster Graph Neural Network
2	M2M-GNN code ↗ GNN global	0.8594 ±0.0040	Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs code ↗
3	GloGNN GNN global	0.8574 ±0.0042	Differentiable Cluster Graph Neural Network
6	FavardGNN Hyb ★ proposed	0.8492 ±0.0041	This paper
7	ChebNetII GNN baseline	0.8486 ±0.0033	This paper
8	OptBasisGNN GNN baseline	0.8485 ±0.0039	This paper
11	LINKX GNN baseline	0.8471 ±0.0052	This paper
17	MixHop GNN baseline actual #17 vs paper #20 3 places worse	0.8363 ±0.0054 best reported	actual #17 vs paper #20 3 places worse paper 0.8347 ±0.0071 best at pub: Uplifting Message Passing Neural Network with Graph Original Information (2022) Difference within reported uncertainty; not counted as underperformance. paper 0.8347 ±0.0071 Δ at pub 0.0016
20	GPR-GNN GNN baseline	0.8354 ±0.0032	This paper
23	BernNet GNN baseline	0.8326 ±0.0029	This paper
27	GCNII GNN baseline	0.8292 ±0.0059	This paper
29	GIN code ↗ GNN global	0.8268 ±0.0032	Mixture of Weak & Strong Experts on Graphs code ↗
31	GCN GNN baseline	0.8247 ±0.0027	This paper
40	LINK Hyb baseline	0.8079 ±0.0049	This paper
51	MLP Trad baseline actual #51 vs paper #57 6 places worse	0.7534 ±0.0064 best reported	actual #51 vs paper #57 6 places worse paper 0.7361 ±0.0040 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) best today: Clarify Confused Nodes via Separated Learning (2023) paper 0.7361 ±0.0040 Δ today 0.0173

Pokec

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	SAGE code ↗ GNN global	0.8597 ±0.0021	Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning code ↗
2	Polynormer code ↗ GT global	0.8595 ±0.0007	Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning code ↗
3	NID_SAGE code ↗ global	0.8563 ±0.0031	Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning code ↗
5	OptBasisGNN GNN baseline	0.8283 ±0.0004	This paper
6	ChebNetII GNN baseline	0.8233 ±0.0028	This paper
7	LINKX GNN baseline	0.8204 ±0.0007	This paper
9	BernNet GNN baseline	0.8167 ±0.0017	This paper
10	MixHop GNN baseline	0.8107 ±0.0016	This paper
13	GPR-GNN GNN baseline	0.8074 ±0.0022	This paper
14	LINK Hyb baseline	0.8054 ±0.0003	This paper
16	GCNII GNN baseline	0.7894 ±0.0011	This paper
23	GCN GNN baseline actual #23 vs paper #24 1 place worse	0.7601 ±0.0049 best reported	actual #23 vs paper #24 1 place worse paper 0.7545 ±0.0017 best at pub: Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited (NeurIPS 2022) best today: Mixture of Weak & Strong Experts on Graphs (ICLR 2023) paper 0.7545 ±0.0017 Δ today 0.0056
24	GraphSAGE code ↗ GNN global	0.7576 ±0.0004	Mixture of Weak & Strong Experts on Graphs code ↗
31	MLP Trad baseline actual #31 vs paper #39 8 places worse	0.7048 ±0.0077 best reported	actual #31 vs paper #39 8 places worse paper 0.6237 ±0.0002 best at pub: FMP: Toward Fair Graph Message Passing against Topology Bias (2022) paper 0.6237 ±0.0002 Δ at pub 0.0811

twitch-gamers

Global leaderboard →

#	Model	Accuracy ↑	Paper
1	DGT Hyb global	0.6609 ±0.0022	Deformable Graph Transformer
2	ICG_u-NN code ↗ Hyb global	0.6608 ±0.0074	on Large Graphs using Intersecting Communities code ↗
3	LINKX GNN baseline	0.6606 ±0.0019	This paper
6	MixHop GNN baseline actual #6 vs paper #6	0.6564 ±0.0027	actual #6 vs paper #6 paper 0.6564 ±0.0027 prev best: Deformable Graph Transformer (2022) paper 0.6564 ±0.0027 Δ at pub 0.0044
9	OptBasisGNN GNN baseline	0.6517 ±0.0016	This paper
11	ChebNetII GNN baseline	0.6503 ±0.0027	This paper
13	LINK Hyb baseline	0.6485 ±0.0021	This paper
14	GraphSAGE GNN global	0.6473 ±0.0011	Deformable Graph Transformer
16	GCN GNN baseline actual #16 vs paper #28 12 places worse	0.6434 ±0.0012 best reported	actual #16 vs paper #28 12 places worse paper 0.6218 ±0.0026 best at pub: Deformable Graph Transformer (2022) paper 0.6218 ±0.0026 Δ at pub 0.0216
18	BernNet GNN baseline	0.6427 ±0.0031	This paper
19	FavardGNN Hyb ★ proposed	0.6426 ±0.0012	This paper
23	GCNII GNN baseline	0.6339 ±0.0061	This paper
27	GPR-GNN GNN baseline	0.6259 ±0.0038	This paper
33	MLP Trad baseline actual #33 vs paper #37 4 places worse	0.6114 ±0.0006 best reported	actual #33 vs paper #37 4 places worse paper 0.6092 ±0.0007 best at pub: Deformable Graph Transformer (2022) paper 0.6092 ±0.0007 Δ at pub 0.0022

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 Best today — OK at publication; today's leaderboard best is elsewhere