# Spectral GNN via Two-dimensional (2-D) Graph Convolution

arXiv: https://arxiv.org/abs/2404.04559 · HTML: https://mlsanity.com/paper/2404.04559/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 63 references that are in the map.
- First posted on arXiv 6 Apr 2024.

## Builds on (most cited first, 30 of 37)

- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Spectral Temporal Graph Neural Network for Multivariate Time-series Forecasting](https://mlsanity.com/paper/2103.07719/) (2021)
- [Rethinking Graph Neural Networks for Anomaly Detection](https://mlsanity.com/paper/2205.15508/) (2022)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Graph Wavelet Neural Network](https://mlsanity.com/paper/1904.07785/) (2019)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [PDE-GCN: Novel Architectures for Graph Neural Networks Motivated by Partial Differential Equations](https://mlsanity.com/paper/2108.01938/) (2021)
- [Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks](https://mlsanity.com/paper/1704.06803/) (2017)
- [Local Spectral Graph Convolution for Point Set Feature Learning](https://mlsanity.com/paper/1803.05827/) (2018)
- [Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks](https://mlsanity.com/paper/2003.03777/) (2020)
- [Killing Two Birds with One Stone:Efficient and Robust Training of Face Recognition CNNs by Partial FC](https://mlsanity.com/paper/2203.15565/) (2022)
- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [Equivalence of approximation by convolutional neural networks and fully-connected networks](https://mlsanity.com/paper/1809.00973/) (2018)
- [Spectral Temporal Graph Neural Network for Trajectory Prediction](https://mlsanity.com/paper/2106.02930/) (2021)

## Built on by (most cited first, 3 of 3)

- [ERGNN: Spectral Graph Neural Network With Explicitly-Optimized Rational Graph Filters](https://mlsanity.com/paper/2412.19106/) (2024)
- [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025)
- [Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach](https://mlsanity.com/paper/2404.15354/) (2024)

## Abstract (arXiv)

Spectral Graph Neural Networks (GNNs) have achieved tremendous success in graph learning. As an essential part of spectral GNNs, spectral graph convolution extracts crucial frequency information in graph data, leading to superior performance of spectral GNNs in downstream tasks. However, in this paper, we show that existing spectral GNNs remain critical drawbacks in performing the spectral graph convolution. Specifically, considering the spectral graph convolution as a construction operation towards target output, we prove that existing popular convolution paradigms cannot construct the target output with mild conditions on input graph signals, causing spectral GNNs to fall into suboptimal solutions. To address the issues, we rethink the spectral graph convolution from a more general two-dimensional (2-D) signal convolution perspective and propose a new convolution paradigm, named 2-D graph convolution. We prove that 2-D graph convolution unifies existing graph convolution paradigms, and is capable to construct arbitrary target output. Based on the proposed 2-D graph convolution, we further propose ChebNet2D, an efficient and effective GNN implementation of 2-D graph convolution through applying Chebyshev interpolation. Extensive experiments on benchmark datasets demonstrate both effectiveness and efficiency of the ChebNet2D.