Generalization Bounds for Message-Passing GNNs on Directed Graphs with Edge Features

We establish generalization bounds for message-passing graph neural networks on directed graphs with multi-dimensional node and edge features, a setting that, to our knowledge, is not covered by existing generalization analyses. Messages are computed by Lipschitz functions of the triple (destination feature, edge feature, source feature), and each layer may include a global readout term enabling long-range interaction. We introduce a family of pseudo-metrics on graphs of fixed order $n$, defined by matching unrolling trees and vanishing on permutations by construction. Every network in our class is Lipschitz with respect to these metrics with an explicit constant, and bounding the covering number yields generalization bounds via the robustness framework of Xu & Mannor (2012). The bounds hold for any learning algorithm returning a hypothesis in the class and require no prior over model parameters. Using the data-dependent theorem of Kawaguchi et al. (2022), the dependence on the covering number $C$ improves from $\sqrt{C}$ to $\sqrt{|{\mathcal{T}}_{\mathcal{S}}|\ln C}$, where $|{\mathcal{T}}_{\mathcal{S}}|$ counts only the covering classes occupied by the training sample. For the general architecture, the Lipschitz constant grows with $n$ and with depth; for a simplified subclass without global aggregation or destination-dependent messages, it becomes independent of $n$.