Depth, Width, and Locality of Message-Passing Representations on Sparse Graphs

Message-passing neural representations are usually analyzed on unrestricted graph families, although many graph domains are structurally sparse. We ask how sparsity changes the depth and width resources needed by Weisfeiler--Leman-style message passing. The answer is asymmetric. On rooted trees, rooted 1-WL has an exact depth characterization: height $h$ is sufficient and, in the worst case, necessary. Yet even treewidth one does not yield a constant-depth complete message-passing representation; bounded treewidth does not remove locality. In contrast, bounded degree compresses the finite structural type space seen by an $L$-layer representation: rooted types admit Johnson--Lindenstrauss compression in $O(\varepsilon^{-2}(\Delta^L+\log(1/\eta)))$ dimensions, with a matching finite-precision counting lower bound. Synthetic diagnostics reproduce the tree-depth transition and the predicted width scaling. Overall, sparse structure can reduce representation complexity, but depth and width respond differently, and locality remains fundamental.