# A Piece-wise Polynomial Filtering Approach for Graph Neural Networks

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 57 references that are in the map.
- First posted on arXiv 7 Dec 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [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)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [GRAND: Graph Neural Diffusion](https://mlsanity.com/paper/2106.10934/) (2021)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Dirichlet Energy Constrained Learning for Deep Graph Neural Networks](https://mlsanity.com/paper/2107.02392/) (2021)
- [Convolutional Neural Network Architectures for Signals Supported on Graphs](https://mlsanity.com/paper/1805.00165/) (2018)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [Graph Neural Networks Inspired by Classical Iterative Algorithms](https://mlsanity.com/paper/2103.06064/) (2021)
- [N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification](https://mlsanity.com/paper/1802.08888/) (2018)
- [How Framelets Enhance Graph Neural Networks](https://mlsanity.com/paper/2102.06986/) (2021)
- [AdaGNN: Graph Neural Networks with Adaptive Frequency Response Filter](https://mlsanity.com/paper/2104.12840/) (2021)
- [Tree Decomposed Graph Neural Network](https://mlsanity.com/paper/2108.11022/) (2021)

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

- [Non-convolutional Graph Neural Networks](https://mlsanity.com/paper/2408.00165/) (2024)
- [Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering](https://mlsanity.com/paper/2206.02386/) (2022)
- [Graph Neural Networks with Diverse Spectral Filtering](https://mlsanity.com/paper/2312.09041/) (2023)
- [FiGURe: Simple and Efficient Unsupervised Node Representations with Filter Augmentations](https://mlsanity.com/paper/2310.01892/) (2023)
- [Q-AGNN: Quantum-Enhanced Attentive Graph Neural Network for Intrusion Detection](https://mlsanity.com/paper/2603.22365/) (2026)
- [Piecewise Constant Spectral Graph Neural Network](https://mlsanity.com/paper/2505.04808/) (2025)
- [Interleaved Head Attention](https://mlsanity.com/paper/2602.21371/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) exploit signals from node features and the input graph topology to improve node classification task performance. However, these models tend to perform poorly on heterophilic graphs, where connected nodes have different labels. Recently proposed GNNs work across graphs having varying levels of homophily. Among these, models relying on polynomial graph filters have shown promise. We observe that solutions to these polynomial graph filter models are also solutions to an overdetermined system of equations. It suggests that in some instances, the model needs to learn a reasonably high order polynomial. On investigation, we find the proposed models ineffective at learning such polynomials due to their designs. To mitigate this issue, we perform an eigendecomposition of the graph and propose to learn multiple adaptive polynomial filters acting on different subsets of the spectrum. We theoretically and empirically show that our proposed model learns a better filter, thereby improving classification accuracy. We study various aspects of our proposed model including, dependency on the number of eigencomponents utilized, latent polynomial filters learned, and performance of the individual polynomials on the node classification task. We further show that our model is scalable by evaluating over large graphs. Our model achieves performance gains of up to 5% over the state-of-the-art models and outperforms existing polynomial filter-based approaches in general.