Sharp Bounds for Poly-GNNs and the Effect of Graph Noise
This work addresses the theoretical understanding of GNN performance for researchers, showing incremental insights into depth limitations and noise effects in graph-based learning.
The paper tackles the problem of semi-supervised node classification using graph neural networks with polynomial features (poly-GNNs) under a contextual stochastic block model, finding that deeper networks do not achieve faster separation between classes, with the rate being the same for depth k>1 as for k=1, and quantifying how graph noise dominates signal in deep GNNs.
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.