# Sharp Bounds for Poly-GNNs and the Effect of Graph Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 28 Jul 2024.

## Builds on (most cited first, 12 of 12)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Network Regression with Graph Laplacians](https://mlsanity.com/paper/2109.02981/) (2021)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Simple GNNs with Low Rank Non-parametric Aggregators](https://mlsanity.com/paper/2310.05250/) (2023)

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

- [Understanding the Effect of GCN Convolutions in Regression Tasks](https://mlsanity.com/paper/2410.20068/) (2024)

## Abstract (arXiv)

We investigate the classification performance of graph neural networks with graph-polynomial features, poly-GNNs, on the problem of semi-supervised node classification. We analyze poly-GNNs under a general contextual stochastic block model (CSBM) by providing a sharp characterization of the rate of separation between classes in their output node representations. A question of interest is whether this rate depends on the depth of the network k, i.e., whether deeper networks can achieve a faster separation? We provide a negative answer to this question: for a sufficiently large graph, a depth k > 1 poly-GNN exhibits the same rate of separation as a depth k=1 counterpart. Our analysis highlights and quantifies the impact of ``graph noise'' in deep GNNs and shows how noise in the graph structure can dominate other sources of signal in the graph, negating any benefit further aggregation provides. Our analysis also reveals subtle differences between even and odd-layered GNNs in how the feature noise propagates.