Graph neural networks (GNNs) employing message passing for graph classification are inherently limited by the expressive power of the Weisfeiler-Lehman (WL) test for graph isomorphism. Node individualization schemes, which assign unique identifiers to nodes (e.g., by adding random noise to features), are a common approach for achieving universal expressiveness. However, the ability of GNNs endowed with individualization schemes to generalize beyond the training data is still an open question. To address this question, this paper presents a theoretical analysis of the sample complexity of such GNNs from a statistical learning perspective, employing Vapnik–Chervonenkis dimension and covering number bounds. We demonstrate that node individualization schemes that are permutation-equivariant and robust to minor input perturbations result in lower sample complexity, and design novel individualization schemes that exploit these results. Finally, our theoretical findings are validated experimentally on both synthetic and real-world datasets.