Walk Counts and the Depth of Graph Neural Networks

Message-passing neural networks distinguish vertices exactly as far as color refinement does, layer for layer, so on graphs whose stable coloring has $m$ classes they can need $m-1$ layers. Global filters, such as spectral, diffusion and Katz filters, let every layer see the whole graph, and how much of this depth they remove has been open. We prove that they halve it: with any filters that are polynomials in the adjacency matrix, arbitrary update functions and unbounded width, exactly $\lfloor m/2\rfloor$ layers are needed in the worst case. The layers that remain are spent on naming, since a linear filter can separate color classes without producing their indicator vectors and only a nonlinearity supplies them. The depth that full expressive power costs thus counts nonlinear layers, however far each layer sees.