  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.
