Covered Forest: Fine-grained generalization analysis of graph neural networks

We thank the reviewer for their fair and constructive review.

the paper is very heavy and difficult to understand, and at times it lacks clarity in what it wants to achieve and how to prove it. It might be beneficial to add some more intuitive discussion between the various propositions. For example: an intuition of the behavior of \widebar{\gamma}^{\leftarrow} would help understand the results of Proposition 9 and its consequences an explanation on the choice of using the Tree distance rather than the Forest distance (see also questions)

We agree that the paper is relatively dense. We will use the additional page in the camera-ready version of the paper to add more intuition and guide the reader. For example, we will add intuitive explanations before a theorem/proposition.

the fact that an estimated Lipschitz constant (rather than an upper bound for the entire GNN class) is used in the results of Table 1 should be stated clearly, and not hidden in Section Q.

We will explicitly mention that we do not compute the uniform Lipschitz constant for our experiments but instead use an empirical Lipschitz constant.

Minor comments: In eq. 7, A(G) is never defined (only in the Appendix). Please double check that everything is defined properly. in lemma 2 the comma in the "only if" is misplaced the footnote 7 on the "technical reasons" should really be part of the Proposition.

Thank you for your comments. We will consider all minor comments.

Why do you use the Tree distance for unlabeled graphs and the Forest distance for labeled graphs? Could one not use always the Forest distance? This distinction should be clarified.

The decision to use both the tree distance and forest distance is motivated by:

(i) Computational complexity: The tree distance with the L2-norm can be computed in polynomial time (see our response to Reviewer e2Pe), and we will move this explanation to the main text.

(ii) The tree distance allows us to derive generalization bounds for graph classes without requiring bounded degree assumptions on graphs, which are necessary for the finiteness of the covering number using the forest distance.

I don't understand the relevance of the subsection on Otter trees, as this is an artificial setting with little practical relevance. Could you motivate your choice of inserting this in the main paper? I think that, e.g., the construction of Theorem 10 that allows you to obtain a cover of size m/(k+1) is much more interesting.

The motivation was to show that in this specific graph class, the covering number admits an upper bound that decreases exponentially with the radius. This shows that our framework yields significantly tighter generalization bounds to structurally more simple graphs.

Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.

We thank the reviewer for their detailed and constructive review.

One potential weakness is the computational complexity of computing pseudo-metrics at scale on large graphs. The authors do mention computational complexity but might elaborate more on possible approximations.

Thank you for highlighting computational complexity. Throughout the paper, we discuss two main distances: the tree distance (with either the cut norm or the l2-norm) and the forest distance.

As shown in Lemma 3, the forest distance is equivalent to the Tree Mover’s Distance (TMD) introduced by Chuang et al. This allows us to compute it efficiently using dynamic programming (as shown in the original paper) in time: $\mathcal{O}(t(n) + Lnt(q))$, where $q$ is the maximum degree of a node (in both graphs), $n$ the number of nodes, and $t(m) = O(m^3 log(m))$.

The tree distance with the L2-norm can be computed in polynomial time (more precisely, an $\varepsilon$-solution), as detailed in “Interior-Point Polynomial Algorithms in Convex Programming” (Section 6.3.3).

On the other hand, the cut norm poses a much more difficult combinatorial optimization problem. Its computation is indeed challenging. One of the most well-known approximation techniques is given in “Approximating the Cut-Norm via Grothendieck’s Inequality”. Additional relevant works will be added to the main paper (“Random Sampling and Approximation of MAX-CSP Problems”, Alon et al., “Quick Approximation to Matrices and Applications”, Frieze & Kannan.)

It is worth mentioning that for the theoretical results in our paper, either the tree distance with the cut norm or with the l2-norm can be used interchangeably, as they define the same topology—this is discussed in “Fine-Grained Generalization Analysis.”

The revised paper will add a detailed discussion regarding the pseudo-metrics computational complexity.

The paper’s experimental scope is somewhat narrow, focusing on a small set of molecules/graphs; the empirical portion might be strengthened by more extensive analysis, including for other graph topologies

This is a good point. However, we view our work as theoretical work. We will try our best to include experiments with other graph structures,

Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.

We thank the reviewer for their fair and constructive review.

Q1. We can expect the experiment's results from the definition of the covering number and WL-indistinguishability. Therefore, I have a question whether the observations from this experiment are new.

You are correct that, by definition, we expect the covering number to decrease with the radius and increase with the order. What is new in our work is that we derive explicit upper bounds on the covering number for different graph families (n-order graphs, otter trees, and an artificial graph class), capturing how it scales with radius and graph order.

Specifically:

i) Proposition 10 shows that for n-order graphs, the covering number is upper bounded by $m_n/(k+1)$, showing a linear decrease with the radius, and an $\mathcal{O}(m_n)$ increase with $n$.

ii) Proposition 12 establishes a stronger bound for Otter trees, showing exponential decay in the radius and again O(m_n) dependence on n.

iii) Appendix N introduces an artificial graph class where the covering number scales with m_n/n instead of m_n.

Hence, we empirically compute covering numbers in Figure 8 and observe trends that align with the theoretical bounds. These results help validate the tightness of our derived bounds. Indeed, for n-order graphs, the covering number can be bounded by a linear function on the radius, and for otter trees, it can be bounded by an exponential function on the radius.

However, the current phrasing of Q1 may not fully reflect this. We will revise it to “To what extent do the empirical covering numbers for different graph families match the theoretical upper bounds derived in Section 4?.”

Q3. The experiment shows that the generalization performance gap and theoretical upper bounds have the same scale. However, we cannot say the tightness of the bound from this observation.

Our goal in Q3 was not to claim that the bound is tight in the formal sense, but to show that the bound and the generalization gap are of the same scale in practice. We will clarify this point.

I checked Sections Q and R. Although $\mathcal{F}_n$ is referred to as a set of graphs, it is not defined in the main text or appendix. I suggest adding its definition.

Thank you for pointing this out. $\mathcal{F}_n$ is an artificial graph class defined in Appendix N. We will include its definition in the main text of the revised papers.

One of the weaknesses of this paper is the excessive appendix (37 pages), which reduces its clarity. For example, as this paper mainly focuses on generalization of MPNNs, the discussion on the mean forest distance seems to be different from its main scope. On the other hand, I am positive about adding explanations on the cut norm, graphon, and WL algorithm in the appendix because they allow readers unfamiliar with these concepts to understand the paper in a self-contained manner.

We acknowledge that the appendix is quite extensive. However, our goal was to ensure that all notations and definitions used in the proofs are rigorously defined and that the paper remains self-contained for readers with varying backgrounds. For that reason, we will provide some additional discussion on Appendices D, K, and C about the intuition behind cut-norm, graphons, and the WL algorithm, respectively.
We defined the mean forest distance to show that mean aggregation MPNNs satisfy the Lipschitz property for a coarser pseudo-metric (mean forest distance), leading to tighter generalization bounds. We will clarify this motivation in the main paper.

Overall, we will use the additional page to make the main part more self-contained.

this paper uses two terms (labeled and attributed) to describe a node with a feature. I want to clarify whether they are different concepts. l.400(right): Unless I am missing something, $\mathcal{F}_n$ is undefined. L.431(left): How are the Forest distance and MPNN outputs correlated? is better L.1652 : The above generalization bound: I could not identify the bound this sentence refers to. L.1696: Theorem 35 in the main paper: Theorem 35 is not in the main text but in the appendix.

Thank you for pointing this out.

1. The terms labeled and attributed refer to the same underlying concept, with a minor distinction noted in the background section: labeled typically refers to discrete labels drawn from a finite set, whereas attributed generally refers to continuous feature vectors in $\mathbb{R}^d$.

2.,5. Thank you. We will correct this in the camera-ready version.

3. Thank you for the suggestion.

4. Should have been “improved the generalization bound in \cref{robustness_bound}” referring to the one introduced by Xu & Manor. We will correct this in the camera-ready version.

Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.

We thank the reviewer for their detailed and constructive review.

Some part is not clear enough, and the main content is not self contained without looking at the appendix. For example, the equation in line 187 does not explain what is the definition of unr. Also, the Figure 4 referenced in line 211 are essential for understanding the > presented metric, I think the author should move it to the main paper. In the meantime, I think many claims and theorms can be improved with presentation, with simplifying notification and moving minor > bounds to appendix. This will make the reading and understanding much better. The section 4, while being the main section of the paper, lacks good structure. The author presents all findings and derivations >sequentially in a single flat level. I think this make the reading harder. The author should think about how to present this section much structured and simpler.

Thank you for pointing out these omissions. We will use an additional page in the camera-ready version to explain the unrolling trees in the main text and refer the reader to their definition in Appendix C.

Given the extra page available, we will include an introductory paragraph in Section 4 highlighting the main results and guiding the reader through the section's flow to improve readability.

I think the author can consider adding additional experiments to cover the influence of graph structure, aggregation, and loss function, which is claimed in theory and contribution but not empirically studied in the experiments.

Thank you for this suggestion, we will try our best to include these experiments to align theory and practice more.

Please consider updating your score if you are satisfied with our answer. We are happy to answer any remaining questions.