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 C to ∣TS∣lnC, where ∣TS∣ 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.
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.Reviewer_jeGUOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary
This paper derives generalisation bounds for GNNs. The bounds compare the expected and empirical errors arising from the graph learning algorithm. The GNNs are assumed to have a special ACR (aggregate-combine-readout) structure with sum aggregation. Nodes and edges have feature vectors assigned. The architecture of the GNN is permutation-invariant regarding the nodes. Under Lipschitz assumptions, a bound on the covering number is obtained. The argument involves unrolling the graph and defining a pseudo-distance on the unrolled graphs.
Critical strengths
The paper provides a rigorous mathematical framework. It also introduces a family of pseudo-metrics. The results are generally well explained. They heavily rely on a key result from Xu and Mannor (2012).
Critical weaknesses
It is not clear to me that the bounds obtained are informative. In Corollary 13, a trivial bound on the distance is M_\ell, from the definition of the loss function. When is the factor multiplying M_\ell in the bound actually smaller than 1? The factor increases exponentially in n and M; the only small factor is division by k, the sample size. How large would the sample have to be for the bound to be informative?
A similar comment applies to the bound in Proposition 14.
It would be good to have some numerical examples which illustrate the usefulness of the results.
Questions for authors
Please address the critical issues raised above: are the bounds nontrivial in Corollary 13 and Proposition 14?
Could you provide a numerical example to illustrate the bounds?
Where does the difficulty enter when the graph is directed as opposed to undirected? For example the paper
Gholamali Aminian, Yixuan He, Gesine Reinert, Lukasz Szpruch, Generalization Error of Graph Neural Networks in the Mean-field Regime. Samuel N. Cohen Proceedings of the 41st International Conference on Machine Learning, PMLR 235:1359-1391, 2024
derives bounds for undirected input graphs; how does their approach fail in the directed case?
Thank you for your careful reading and the direct questions. For an overview of the changes, please see our general response. The weaknesses you pointed out are central ones, and we worked on them.
Are the bounds in Corollary 13 and Proposition 14 non-trivial?
Over the full feature cube they are not for realistic graph and sample sizes, and the revision states this explicitly (Section 4.3).
The bound of Corollary 13 (now Theorem 13(i) with Eq. (7)) requires k exponential in p=nd+n2d′.
For the data-dependent bound of Kawaguchi et al. (Proposition 14, now Proposition 25 and Theorem 13(ii)), Lemma 14 gives the exact condition k≥∣TS∣ln(2C/δ)/xτ. For molecular graphs with the parameters of QM9 (Section 4.3), even ∣TS∣=1 would require k greater than the dataset.
The new Section 4.4 shows how the bounds become informative: by exploiting the zero set of dL, which is coarser than isomorphism, and by covering only the support of the data (Theorem 15), with finite feature alphabets as a special case (Theorem 16). Proposition 17 shows that some assumption on the data is necessary for any algorithm-uniform bound.
Numerical examples
Section 4.5 evaluates the bounds on two examples.
Financial networks with continuous features (E1, Example 48). The generalization gap is at most 0.3 from k≈2.7⋅105 simulated scenarios for n=10 banks (Table 1).
Synthetic directed graphs (E2). The bound is non-vacuous from k≈2,700 and reaches Φ=0.094 at k=200,000 (Figure 1).
Directed vs. undirected graphs
There is no intrinsic difficulty between directed and undirected graphs in our setting. The choice decides which data the setting can capture: for financial networks directed edges are crucial, for chemical bonds less so. In our setting it determines the neighbourhoods and hence how graphs are unrolled. Undirected graphs are the special case of symmetric edge features, and since the bounds only require a cover of the support of the data (Theorem 15), they apply directly. The actual technical difficulties lie in the multi-dimensional edge features, which are matched jointly with both endpoint features, in the unnormalized sums, and in the global readout term.
As far as we understand, the approach of Aminian et al. (2024) does not use the symmetry of the adjacency matrix in its main results and might also be valid for directed graphs. What sets our work apart is the setting: multi-dimensional edge features, more general GNNs, and bounds that hold uniformly for every learning algorithm, whereas theirs hold for the minimizer of a KL-regularized empirical risk in the mean-field regime. We now discuss this paper in the related work.
If a specific step of a proof raises concerns regarding soundness, we would be grateful to know which one, so that we can address it.
Thank you for your thoughtful and valuable review. We truly appreciate the time and effort you have invested in assessing our work. We hope that our detailed responses have adequately addressed your remarks and provided additional clarity.
As the discussion period is approaching its conclusion, we would be grateful for any further comments or suggestions you might wish to share. We would be pleased to clarify any outstanding points and respond to any remaining concerns. Should you consider that our replies have sufficiently addressed the issues you identified, we would sincerely appreciate it if you would consider updating your overall assessment of the paper accordingly.
The paper derives generalization bounds for message-passing GNNs on directed graphs with multi-dimensional node and edge features, using a new family of pseudo-metrics based on unrolling trees. By combining Lipschitz continuity with existing robustness theory, the authors establish bounds for both single-layer and multi-layer GNNs and improve their dependence on covering numbers through a data-dependent analysis.
Critical strengths
The paper addresses a meaningful gap in GNN generalization theory by considering directed graphs with multi-dimensional node and edge features.
The theoretical analysis is well structured, covering both single-layer and multi-layer GNNs and providing improved data-dependent generalization bounds.
Critical weaknesses
The paper introduces a new pseudo-metric based on unrolling trees, but its necessity is not fully justified. A simpler alternative would be to align node permutations and directly measure differences in node and edge features. Since the covering number is ultimately bounded using the raw feature space, the authors should clarify what theoretical advantages the proposed pseudo-metric offers over this simpler approach.
Thank you for your careful reading and the constructive comments. For an overview of the changes, please see our general response. The weakness you pointed out is a central one, and we worked on it.
The alternative you suggest, aligning nodes by a single permutation and comparing features directly, is the graph-matching counterpart dLσ in the revised version (Definition 42, Proposition 6). Every network in our class is Lipschitz with respect to both pseudo-metrics, and dL≤dLσ. The bounds obtained by covering the full feature cube use the identity matching and therefore exploit neither pseudo-metric (Section 4.3). The pseudo-metric dL has three advantages:
(a) Computability. Computing dLσ is a quadratic assignment problem, and deciding dLσ=0 is the graph isomorphism problem. dL is an iterated assignment problem with O(Ln5) operations (Proposition 4).
(b) A coarser zero set.dL vanishes exactly on graphs that edge-aware colour refinement does not separate (Theorem 8), so non-isomorphic graphs can share a cell (Example 9).
(c) Smaller partitions. Covering only the support modulo dL can give much smaller partitions and non-vacuous bounds. For finite alphabets, the bound depends only on the occupied colour-refinement classes (Theorem 16). In E2 these are 2 classes for 200,000 graphs, whereas a subsample of 20,000 graphs contains 19,722 isomorphism classes, so cells based on alignment leave the bound vacuous.
The new Section 4.4 discusses when the bounds are informative, and Section 4.5 gives two instances (E1, E2).
Thank you for the detailed rebuttal and the additional theoretical analysis. The comparison with the permutation-based alternative clarifies the advantages of the proposed pseudo-metric and largely addresses my concern. I will maintain my positive rating.
This paper establishes generalization bounds for message-passing graph neural networks operating on directed graphs with multidimensional node and edge features. The considered architecture also allows global aggregation terms, extending beyond standard local message passing.
The authors introduce a family of pseudo-metrics based on graph unrolling trees and establish Lipschitz continuity of the considered GNNs with respect to these metrics. They then bound the covering numbers of the graph space and apply the robustness framework of Xu and Mannor (2012) to derive generalization bounds. Using the data-dependent results of Kawaguchi et al. (2022), they obtain refined bounds that depend on the number of covering cells occupied by the training samples rather than the total covering number directly.
The paper also analyzes how the bounds depend on graph size and network depth, and shows that the dependence on graph size in the Lipschitz constant can be eliminated for a restricted message-passing architecture.
The contributions are entirely theoretical, with proofs provided in the appendix. No empirical validation is presented.
Critical strengths
Extension to a more general class of GNNs. The paper establishes generalization bounds for message-passing GNNs on directed graphs with multidimensional edge features and global aggregation. This is a meaningful extension of existing theoretical results, which typically consider more restricted architectures.
A rigorous and general theoretical framework. The authors construct graph pseudo-metrics based on unrolling trees and establish explicit Lipschitz bounds for multilayer GNNs. These results are technically nontrivial and yield generalization guarantees for any learning algorithm returning a hypothesis from the considered class, without assumptions on the training procedure or a prior over network parameters.
Critical weaknesses
Limited novelty and insufficient discussion of closely related work. While the extension to directed graphs with multidimensional edge features is technically valuable, the overall approach largely follows existing generalization frameworks based on Lipschitz continuity, covering numbers, and algorithmic robustness. Moreover, relevant prior work on GNN generalization and graph metrics, including Rauchwerger and Levie (2025) [1] and Sverdlov et al. (NeurIPS 2026) [2], is not discussed. A more careful comparison is necessary to establish the precise novelty of the contributions.
Loose generalization bounds with unclear practical significance. The authors bound the covering number of the proposed graph pseudo-metric using that of the full Euclidean feature space, thereby losing much of the potential benefit of exploiting graph symmetries. Furthermore, the improved data-dependent bounds depend on the number of occupied covering cells, which can be comparable to the training sample size for continuous distributions. In such cases, the bounds may remain vacuous even as the sample size increases. The paper provides neither a tighter analysis exploiting the graph structure nor concrete examples demonstrating that the resulting bounds are informative.
References
[1] Levi Rauchwerger and Ron Levie. A Note on Graphon-Signal Analysis of Graph Neural Networks. arXiv:2508.18564, 2025. https://arxiv.org/abs/2508.18564
[2] Yonatan Sverdlov, Benjamin Friedman, Snir Hordan, and Nadav Dym. When and How to Canonize: A Generalization Perspective. Advances in Neural Information Processing Systems (NeurIPS), 2026. https://arxiv.org/abs/2605.11008
Questions for authors
1. An error in the covering-number argument (Corollary 13 and Remark 29).
The authors use the inequality N(Y,r)≤N([0,1],r) for Y⊆[0,1]. However, this is generally false under the definition of covering numbers adopted in Section 2, where covering centers must belong to the covered space.
For example, let Y={0,1/2,1} and r=0.3. Then N(Y,r)=3, whereas N([0,1],r)=2.
One possible correction is to use
N(Y,r)≤N([0,1],r/2),
which follows by selecting representatives from Y in the covering balls that intersect Y. This would modify the explicit constants.
Alternatively, and perhaps more simply, the authors could directly partition Y by intersecting it with intervals of length at most ε. Such a partition has at most ⌈1/ε⌉ cells, each of diameter at most ε, and therefore suffices for the robustness argument without changing the claimed asymptotic bounds or introducing the extra factor of two.
Could the authors correct the argument in Corollary 13 and Remark 29, and clarify the related "without loss of generality" step in the proof of Theorem 12?
2. Can the generalization bounds be obtained much more directly?
The main contribution is the construction of the pseudo-metrics dL and the establishment of Lipschitz continuity with respect to them. However, Proposition 9 gives
dL(G,H)≤2TLn3/2∥wG−wH∥2.
Combining this with Proposition 8 immediately yields a Lipschitz bound with respect to the ordinary Euclidean distance between the raw graph feature vectors.
Moreover, since n is fixed and all message-passing components are Lipschitz, it seems possible to derive such a bound directly through a layer-by-layer perturbation analysis, without introducing the unrolling-tree pseudo-metrics.
The authors subsequently bound N(Gn,dL,ε) using the covering number of the full Euclidean cube [−M,M]p, where p=nd+n2d′. Consequently, the final explicit generalization bounds do not appear to exploit the permutation symmetry that motivated the construction of dL.
What is the actual quantitative benefit of introducing these pseudo-metrics? Can the authors demonstrate a strictly better covering-number estimate, a better dependence on n, or another result that cannot be obtained comparably easily using a direct Euclidean analysis?
This question is particularly important for assessing the novelty and necessity of the proposed framework.
3. When are the improved generalization bounds non-vacuous?
The data-dependent bounds in Theorems 15 and 17 depend on the number ∣TS∣ of covering cells occupied by the training sample. Their leading statistical term is proportional to
k∣TS∣logC,
where k is the sample size and C is the covering number.
For continuous feature distributions in the regime k≪C, one generally expects ∣TS∣≈k. In this case, the term becomes approximately logC and does not decrease with k as long as the samples continue to occupy distinct cells.
Furthermore, the explicit estimate for logC depends on the full input dimension p=nd+n2d′, which may be extremely large even for moderately sized graphs.
Could the authors exhibit a concrete setting, preferably with continuous node and edge features, in which their bounds are non-vacuous? What assumptions on the underlying distribution would guarantee that ∣TS∣/k becomes sufficiently small?
Without such an example or sufficient conditions, it is unclear whether the proposed bounds provide meaningful generalization guarantees beyond formally valid but potentially vacuous estimates.
4. Technical issues concerning the Lipschitz assumptions.
On page 4, the authors suggest message functions of the form
ϕ(h,e,h′)=∥e∥σ(ϕˉ(h,e,h′))
as examples of Lipschitz functions vanishing on zero-edges, assuming that ϕˉ is Lipschitz and σ is bounded and Lipschitz.
However, these assumptions do not guarantee that ϕ is globally Lipschitz. For instance, ϕ(e,h)=∣e∣tanh(h) is not globally Lipschitz on R2.
One possible correction is to replace ∥e∥ with a bounded Lipschitz function vanishing at zero, such as min{∥e∥,R}. Alternatively, the authors could explicitly restrict the domain on which Lipschitz continuity is required.
Could the authors clarify the assumptions and correct this example?
Additionally, Proposition 14 defines ζ(AS) using a maximum over Z, although the label space Y⊆[0,1] is not required to be closed. Would using a supremum instead of a maximum be more appropriate?
5. Relation to closely related work and the precise novelty of the results.
The related-work discussion appears incomplete in several important respects.
First, Rauchwerger and Levie (2025) extend graphon-signal analysis to directed graphs with multidimensional node features and establish Lipschitz continuity and robustness-based generalization bounds. This is particularly relevant to the statement in Section 1 that graphon-based analyses are restricted to undirected graphs.
Second, Amran, Gilat, and Levie (ICML 2026) derive generalization results for GNNs on sparse graphs using a graph-metric framework that also accommodates varying graph sizes.
Third, Sverdlov et al. (NeurIPS 2026) investigate generalization through covering numbers in the presence of permutation symmetries, comparing invariant models, canonization, and non-invariant approaches. Their results are directly relevant to the potential improvement of covering-number estimates through symmetry.
Could the authors discuss these connections and clarify precisely which aspects of the proposed framework are new?
In particular, given that the final covering-number estimates are obtained from the full Euclidean feature space, it would be valuable to understand whether the proposed approach provides an advantage over existing methods that explicitly exploit the underlying permutation symmetry.
References
[1] L. Rauchwerger and R. Levie. A Note on Graphon-Signal Analysis of Graph Neural Networks. arXiv:2508.18564, 2025. https://arxiv.org/abs/2508.18564
[2] O. Amran, T. Gilat, and R. Levie. A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation. ICML, 2026. https://proceedings.mlr.press/v306/amran26a.html
[3] Y. Sverdlov, B. Friedman, S. Hordan, and N. Dym. When and How to Canonize: A Generalization Perspective. NeurIPS, 2026. https://arxiv.org/abs/2605.11008
Thank you for your careful reading and constructive comments. For an overview of the changes, please see our general response. We believe that the revised version addresses the weaknesses you pointed out. Our answers to your questions follow below.
Question 1
Thank you, this is indeed an error that we overlooked. We implemented your proposal of partitioning Y directly into intervals of length at most ε (Lemma 26, Theorem 13, Remark 36). This removes the unjustified "w.l.o.g." step and leaves the constants unchanged. If Y is known, the results also hold for more specific partitions, e.g. {0},{1} for binary classification with Y={0,1}.
Question 2
The bounds obtained by covering the full feature cube use the identity matching (Proposition 12) and therefore do not exploit dL, as we now state in Section 4.3. The benefits of dL appear in the refinements:
(a) Computability.dL is an iterated assignment problem with O(Ln5) operations (Proposition 4), whereas its permutation-minimized counterpart dLσ is a quadratic assignment problem (Proposition 6, Remark 7).
(b) A coarser quotient.dL vanishes exactly on graphs that edge-aware colour refinement does not separate (Theorem 8), which is strictly coarser than isomorphism (Example 9). Cells can be merged along it (Corollary 44), and for finite alphabets the bound depends only on the occupied classes, without Lipschitz constants or feature dimensions (Theorem 16). Together with covering only the support of the data (Theorem 15), this can yield much smaller partitions and non-vacuous bounds, e.g. 2 cells for 200,000 almost pairwise non-isomorphic graphs in E2.
Question 3
The new Section 4.4 is devoted to this question. Lemma 14 shows that the occupied cells must be heavily populated, and Proposition 17 that, without conditions on the distribution, no algorithm-uniform bound can be small at small sample sizes. Sufficient conditions are a support with small covering exponent (Theorem 15) or a finite feature alphabet (Theorem 16).
As an example with continuous node features, we consider financial networks (E1, Example 48, Proposition 49), where the bounds are informative for realistic Monte Carlo sample sizes (Table 1). The synthetic graphs of E2 are based on a finite alphabet, but small continuous perturbations (relative to the covering radius) would not change the result.
Question 4
Thank you for catching this. We had bounded edge features in mind: since edge features are never updated, ϕ and ψ only receive edge features in [−M,M]d′, so Lipschitz continuity is only needed on Rd(l−1)×[−M,M]d′×Rd(l−1), where the example is Lipschitz. We now state this explicitly (Section 2, Remark 29(iii)).
Your remark regarding the maximum is equally correct; we now use the supremum in ζ.
Question 5
Thank you for these references. We now discuss them, together with Aminian et al. (2024), in the related work, and we removed the incorrect statement that graphon-based analyses are restricted to undirected graphs.
Rauchwerger & Levie (2025) cover directed graphs and Amran et al. (2026) graphs of varying size, both with scalar edge weights. We add multi-dimensional edge features that enter the messages jointly with both endpoint features, and a global readout term in every layer, with explicit constants at fixed n.
Sverdlov et al. (2026) work with the quotient by a group action, whereas dL induces the coarser quotient of colour refinement.
Thank you to the authors for their detailed response and for addressing my technical concerns.
My main concern remains the limited novelty and significance of the contribution. In particular, the generalization bounds obtained by covering the full feature cube do not improve upon what can be derived directly using Euclidean distances, standard Lipschitz continuity arguments, and existing robustness-based generalization results. The improvements offered by the proposed pseudo-metrics become relevant only under additional structural or distributional assumptions, such as a small covering exponent of the data support or a finite feature alphabet. While the authors provide examples where these refinements yield non-vacuous bounds, I do not find these examples sufficiently convincing to establish the broader significance of the results.
More fundamentally, I consider the paper too incremental. The overall theoretical framework is well established, and the proposed extensions do not introduce a sufficiently novel or interesting conceptual contribution. Although the authors have addressed my technical comments, I remain unconvinced that the paper provides a meaningful advance in our understanding of GNN generalization.
Thank you for your reply and for confirming that our response addressed your technical concerns.
We agree that over the full feature cube our bounds do not improve on a direct Euclidean analysis, and the revision states this (Section 4.3). We would, however, like to point to one aspect for the overall assessment.
The need for structural or distributional assumptions is not specific to our approach: Proposition 17 shows that any bound holding uniformly over learning algorithms must be large at small sample sizes unless the data are restricted. The relevant question is therefore which assumptions make such bounds informative, and whether they can be checked. Here dL gives results that neither a Euclidean nor a permutation-based analysis provides. Its zero set is exactly colour-refinement equivalence (Theorem 8). For finite alphabets this yields a bound that depends only on the occupied classes, independently of Lipschitz constants and dimensions (Theorem 16). And because dL is computable in polynomial time (Proposition 4), these quantities can actually be evaluated, as in E2, where 200,000 almost pairwise non-isomorphic graphs occupy two cells.
We appreciate your time and the corrections you pointed out, which improved the paper.
The paper develops generalization guarantees for message-passing graph neural networks on directed graphs with vector-valued node and edge features. The analyzed architecture allows messages to depend on destination features, edge features, and source features, and optionally includes a global aggregation term. For graphs of fixed order, the authors construct permutation-invariant pseudo-metrics by matching unrolling trees, establish explicit Lipschitz stability bounds, and transfer covering estimates from the raw feature space to the graph domain. Robustness arguments then yield guarantees for any learning algorithm returning a model in the specified class. A data-dependent refinement replaces the square-root dependence on the total covering count with terms involving the number of occupied partition cells and the logarithm of that count. Appendix D also analyzes a restricted architecture with a graph-size-independent Lipschitz constant. The contribution is theoretical; no numerical evaluation of the bounds is provided.
Critical strengths
The analysis covers a substantive combination of graph structure and architectural features. The framework jointly accommodates directed edges, multidimensional edge attributes, sum aggregation, destination-dependent messages, and a global aggregation term (Sections 2–3). Extending the stability and robustness analysis to this combination is useful because these features change how information propagates through a graph. The resulting guarantees apply to the specified hypothesis class independently of the learning algorithm.
The paper provides an explicit and interpretable chain from graph geometry to generalization. The pseudo-metric construction, Lipschitz estimates, and covering-number arguments are connected clearly, with proofs in Appendices A–C. The comparison with the simplified class in Appendix D is particularly informative: removing global aggregation and destination dependence yields a Lipschitz constant independent of graph order, while the authors explicitly acknowledge that the covering-number contribution still depends on graph size. This distinction helps identify which parts of the analysis incur particular scaling costs.
Critical weaknesses
The quantitative usefulness of the guarantees remains unresolved. The covering estimate is based on the full feature cube of dimension p=nd+n^2d', and therefore does not directly exploit sparsity or a lower-dimensional graph distribution. Theorem 17 substantially improves the dependence on the covering count C, but still requires |T_S|\log(2C/\delta)/k to be small, where k is the sample size and |T_S| counts occupied graph–label partition cells. If |T_S| is comparable to k, this refinement need not provide a useful guarantee. Section 3.5 already explains this limitation, so the concern is the absence of a concrete informative regime, rather than an overlooked condition in the theorem. A worked example with explicit constants and an admissible partition would help establish the practical significance of the improvement.
The formal applicability is narrower than the breadth of the motivating applications. The results assume a fixed graph order, bounded features, uniformly controlled component Lipschitz constants, and message functions satisfying \phi(\cdot,0,\cdot)=\psi(\cdot,0,\cdot)=0 (Section 2, Eq. (3)). In particular, an existing edge with a zero-valued feature vector is indistinguishable from an absent edge in this formulation. These are legitimate assumptions, but they require checking for a concrete implementation and do not automatically cover arbitrary edge-conditioned networks or datasets with varying graph sizes. The conclusion discusses possible extensions to bounded graph order, including changing the readout, but does not establish them. This limits the immediate reach of an otherwise coherent theoretical contribution.
Questions for authors
Quantitative clarification: Can the authors give a concrete graph distribution and a partition fixed independently of the observed training sample for which Theorem 17 yields an informative risk bound at explicit values of graph order, depth, feature dimensions, Lipschitz constants, and sample size? An analytical or small synthetic example would suffice; the key issue is the joint behavior of C, |T_S|, and the robustness term as the covering radius changes.
Applicability clarification: For the architectures and datasets motivating the paper, how are the zero-edge condition and the uniform Lipschitz bounds enforced? For graphs of varying size, does padding preserve the computation with the normalized readout in Eq. (2), or are additional masking conditions or the readout modification proposed in Section 4 necessary? Clarifying this distinction would materially affect how broadly the guarantees can be interpreted.
Thank you for your careful reading and constructive comments. For an overview of the changes, please see our general response. Our answers to your questions follow below.
Critical Weakness 1 / Question 1
We provide two such instances, both with partitions fixed before the sample is drawn.
(a) Financial networks (E1, Example 48, Proposition 49). Interbank liabilities are fixed directed edge features, external assets are continuous node features driven by a common factor, and the label is the Eisenberg–Noe shortfall. The support is a one-dimensional curve, so it suffices to cut cells along the factor (Theorem 15). For L=1, ε=0.1 and δ=0.05, the generalization gap is at most 0.3 from k≈2.7⋅105 samples for n=10 and from k≈5.9⋅106 for n=50, both with K=1; Table 1 gives the values up to n=100 and K=2. In such applications, GNNs are trained on simulated scenarios, so these are realistic Monte Carlo budgets. The covering radius ε/(8K4) enters explicitly, so the number of cells grows like K4.
(b) Synthetic directed graphs (E2).n=10 nodes, edge features in {(1,0),(0,1),(1,1)}. All graphs with the same label are ∼L-equivalent, so ∣TS∣=2 under the ∼L partition, while a subsample of 20,000 graphs contains 19,722 isomorphism classes. Theorem 16 gives lnC=139, independently of L and K. The bound is non-vacuous from k≈2,700 and reaches Φ=0.094 at k=200,000. With grid cells, ∣TS∣=k and the bound stays vacuous.
Critical Weakness 2 / Question 2
The paragraphs following the definition of our GNN class (Section 2) now discuss this in more depth.
Zero-edge condition. It can be enforced for arbitrary message functions, e.g. by ϕ~(x,e,y)=ϕ(x,e,y)−ϕ(x,0,y), at most doubling the Lipschitz constant. Alternatively, networks that do not satisfy the condition at all can be embedded into our class: existing edges are encoded as e^i,j=(1,ei,j), absent edges as 0∈Rd′+1, and the message functions are masked by the first coordinate (Proposition 47). The embedded network computes the same output and only has a larger Lipschitz constant, which enters lnC logarithmically. This approach additionally separates an existing edge with feature 0 from an absent edge, which may be desirable depending on the data.
Uniform Lipschitz bounds. These can be enforced in practice by spectral normalization of the weight matrices or by weight clipping.
Graphs of bounded order. These are covered by padding smaller graphs with nmax−n isolated zero-feature nodes (Proposition 46). With the normalized readout (2), padding does not preserve the computation. The readout must then be the unnormalized sum, which multiplies the Lipschitz constants by nmax, and we additionally need α(0,0)=0 and ρ(0,0,⋅)=0, which can be imposed by the same subtraction trick.
Thank you for your thoughtful and valuable review. We truly appreciate the time and effort you have invested in assessing our work. We hope that our detailed responses have adequately addressed your remarks and provided additional clarity.
As the discussion period is approaching its conclusion, we would be grateful for any further comments or suggestions you might wish to share. We would be pleased to clarify any outstanding points and respond to any remaining concerns. Should you consider that our replies have sufficiently addressed the issues you identified, we would sincerely appreciate it if you would consider updating your overall assessment of the paper accordingly.
We thank all reviewers for their careful reading and constructive comments. Their feedback allowed us to include material we had been working on since the initial submission, and it raised further questions that we are happy to answer. Changes are marked in blue in the revised PDF (for the new Sections 3.2, 4.4 and 4.5 we only marked the title).
All reviews raise two central questions: what the pseudo-metric dL adds, given that the covering number is bounded via the full Euclidean feature cube, and whether the bounds can be informative. The revision is organized around these questions.
What dL adds. The revised version studies dL in much more depth.
It is computable as an iterated assignment problem with O(Ln5) operations (Proposition 4), whereas its graph-matching counterpart dLσ, which minimizes over a single node permutation, is a quadratic assignment problem (Proposition 6, Remark 7).
Its zero set is characterized by edge-aware colour refinement on the completed graph (Theorem 8), a quotient strictly coarser than isomorphism (Example 9).
When the bounds are informative. Covering the full feature cube does not exploit dL, and the resulting bounds are vacuous for realistic graph and sample sizes (Section 4.3). We prove that assumptions on the data are necessary: without them, no algorithm-uniform bound can be small at small sample sizes (Proposition 17). The new Section 4.4 provides the refinements through which our bounds become informative:
Lemma 14 gives the required sample size.
Partitions can exploit the zero set of dL (Corollary 44).
It suffices to cover only the support of the data, which may have a much smaller covering exponent than the full cube (Theorem 15).
For finite feature alphabets, the covering number is the number of colour-refinement classes, independently of Lipschitz constants and feature dimensions (Theorem 16).
Empirical results. Since dL is computable, we added experiments (Section 4.5). The bounds are informative for a financial network model with continuous features (E1, Table 1) and for synthetic directed graphs with two-dimensional edge features (E2), where colour refinement collapses 200,000 almost pairwise non-isomorphic graphs into two cells. Code is provided in the supplementary material, and a GitHub repository will be available after the double-blind review.
From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.
Thank you for your careful reading and the direct questions. For an overview of the changes, please see our general response. The weaknesses you pointed out are central ones, and we worked on them.
Are the bounds in Corollary 13 and Proposition 14 non-trivial?
Over the full feature cube they are not for realistic graph and sample sizes, and the revision states this explicitly (Section 4.3).
The new Section 4.4 shows how the bounds become informative: by exploiting the zero set of dL, which is coarser than isomorphism, and by covering only the support of the data (Theorem 15), with finite feature alphabets as a special case (Theorem 16). Proposition 17 shows that some assumption on the data is necessary for any algorithm-uniform bound.
Numerical examples
Section 4.5 evaluates the bounds on two examples.
Directed vs. undirected graphs
There is no intrinsic difficulty between directed and undirected graphs in our setting. The choice decides which data the setting can capture: for financial networks directed edges are crucial, for chemical bonds less so. In our setting it determines the neighbourhoods and hence how graphs are unrolled. Undirected graphs are the special case of symmetric edge features, and since the bounds only require a cover of the support of the data (Theorem 15), they apply directly. The actual technical difficulties lie in the multi-dimensional edge features, which are matched jointly with both endpoint features, in the unnormalized sums, and in the global readout term.
As far as we understand, the approach of Aminian et al. (2024) does not use the symmetry of the adjacency matrix in its main results and might also be valid for directed graphs. What sets our work apart is the setting: multi-dimensional edge features, more general GNNs, and bounds that hold uniformly for every learning algorithm, whereas theirs hold for the minimizer of a KL-regularized empirical risk in the mean-field regime. We now discuss this paper in the related work.
If a specific step of a proof raises concerns regarding soundness, we would be grateful to know which one, so that we can address it.