Higher-Order Graphon Neural Networks: Approximation and Cut Distance

We thank the reviewer for their insightful remarks and positive feedback on our work!

not being a product of a definitional choice that could be reworked and rather a facet of the true underlying problem

This is an excellent point! In the revision, we have clarified this and highlighted the close connection to $k$-WL. Please refer to the general comments for the full answer to this question.

short section, dedicated to showcasing some of the concepts you develop, perhaps in some experiments

Refer to general comments.

Is there any hope for an interesting bound in the distance regardless of discontinuity, or is the behavior fundamentally unworkable?

Thank you for raising this interesting question! Indeed, there is a strong indication that IWNs might be able to approximate sufficiently well-behaved functions on the entire space, and not just compact subsets (which are tiny compared to the entire graphon-signal space in the topology induced by $\delta_p$). Note that we can show such a result for signal-weighted homomorphism densities (Theorem 5.2), which are bounded continuous functions. Nevertheless, since the $\delta_p$-topologies are not compact, there might be unbounded continuous functions which can impossibly be approximated on the entire space by IWNs. A conjecture would be that all bounded $\delta_p$-continuous functions can be approximated arbitrarily well. While we have not checked this carefully, we agree this would also be an interesting further result.

toy examples of the model

Refer to general comments.

We thank the reviewer for their insightful remarks and positive feedback on our work!

It will be nice to substantiate this remark using empirical evidence, either through observation made in existing works using IGNs or original experiment studies.

Please refer to the general comments.

Definition of signal-weighted homomorphism densities (Defn 3.1) seems standard from the graphon literature.

We thank the reviewer for this comment. Indeed, the references [1] and [2] mentioned by the reviewer also define weighted graph homomorphism counts for node-featured graphs that would extend to our definition for graphons, which we were not fully aware of before the paper submission. Yet, to the best of our knowledge, there are currently no works that define and systematically analyze this concept for node-featured graphons, which can capture (a) weak isomorphism (Theorem 3.3) or (b) the k-WL test (Theorem 3.5) specifically under the topology that arises from the graphon-signal space [5]. We also note that there are numerous concepts of homomorphism counts used in the GNN literature, and, e.g., the definitions of [6] do not work for us as (a) not considering the signal moments only distinguishes graphs after twin reduction (e.g., signal values of zero can be removed), and (b) considering the same function for each node would result in the signal-weighted homomorphism densities not being closed under multiplication, which is essential for our proofs. As such, we see the task of defining a suitable concept as nontrivial. In the revision, we have made the connection to existing concepts clearer (cf. L219, L231-235).

Invariance under discretization

We are not entirely sure that we fully understand the reviewer’s question. Invariance under discretization, intuitively meaning that (higher-order) step kernels are again mapped to step kernels w.r.t. the same regular partition of $[0,1]$, is not a condition that we impose on the network, but rather a consequence of framing IWNs as bounded linear operators—which is a reasonable assumption for any decently well-behaved network on graphons for theoretical analyses. Could the reviewer kindly elaborate on their question if our response does not fully address their concern?

Nontrivial IWN in Proposition 5.1

In the mentioned proposition (now Proposition 5.5 in the revision), we precisely state that $W \mapsto \varrho(W)$ for any graphon $W$ is discontinuous in the cut norm, i.e., we do not consider an entire IWN, but only the pointwise application of the nonlinearity $\varrho$ (the integral of this would be a very simple IWN). If $\varrho$ is linear, this assignment is just a rescaling of $W$ and the addition of a constant, which is clearly cut distance continuous (as a homogenous function up to the additive constant). Even if one considers higher-order IWNs with a linear activation, one can derive that any parametrization (irrespective of the IWN’s order) will collapse to a function of the form $W \mapsto a (\int_{[0,1]^2} W \mathrm{d}\lambda^2) + b$, which is clearly cut distance continuous, but of trivial expressivity.

The effect of pooling

In our analysis, the pooling is implicitly defined by the last layer which maps to scalars, and, as such, is fixed to the mean (or integral for graphons). This is indeed crucial for our analysis, as other pooling operations such as $\mathrm{max}$ seem to not go well with the graphon space: One of the simplest such models would be essentially $W \mapsto \||W\||_\infty$, which is not continuous w.r.t. any of the $\delta_p$ distances, $p < \infty$. Therefore, we do not expect our analysis to extend to such a case. We kindly ask the reviewer to let us know should the question not be fully addressed.

References

[5] Ron Levie. A graphon-signal analysis of graph neural networks. Advances in Neural Information Processing Systems, 36:64482–64525, December 2023.

[6] Hoang Nguyen and Takanori Maehara. Graph Homomorphism Convolution. In Proceedings of the 37th International Conference on Machine Learning, pp. 7306–7316. PMLR, November 2020.

We thank the reviewer for elaborating on their question.

Indeed, the dimension of the space of layers from Theorem 4.2/Eq. 15 satisfying both permutation and discretization invariance (or $\delta_p$-continuity) is smaller than the original IGN layer dimension of $\mathrm{bell}(k+\ell)$. In general, when designing such higher-order GNNs, the goal is to have a small and easily parametrizable basis. As we show that the basis from Theorem 4.2 achieves the same expressivity via the $k$-WL hierarchy (which also holds for finite graphs), we do not see any reason to keep the basis larger than necessary. Also, keeping the basis larger (and, e.g., discarding invariance under discretization) would not have any positive effect on the continuity properties of an IWN, as the resulting hypothesis class would just become a strict superset, still containing the same cut distance discontinuous functions (simply by setting the parameters of the added basis elements to zero). Even worse, when adding other basis elements for which continuity/invariance under discretization is not fulfilled, as mentioned in the introduction (L74-77) and further hinted at in § 4.1 (L326-327, L347-349), the resulting functions would not even be well-defined on the graphon-signal space, and, as such, impossible to analyze (which is why Cai & Wang (2022) introduced the “partition norm” vector). We also want to emphasize that the cut distance discontinuity does not arise from the linear layers, but from the pointwise application of the nonlinearity (cf. Proposition 5.5 in the updated script).

Nevertheless, we agree that fixing the cut distance discontinuity and further examining its consequences would be an interesting avenue for further work (which we also mentioned in the conclusion, L535-537). This would entail developing a $k$-WL expressive architecture for which the edge weights are similarly processed as in the 1-WL, i.e., only acting through integral operators and not already being explicitly passed already in the first step of the test. With the IWN/IGN architecture, due to the pointwise application of nonlinearities, something like this is fundamentally unworkable (meaning that no further restriction of the basis would yield such a parametrization). As also mentioned in L536, Böker (2023) defines the simple $k$-WL test for this, which could potentially be used to design a higher-order cut distance continuous architecture (however, the parametrization would become slightly more complicated). Yet, in light of our result of the cut distance discontinuity’s fixability for transferability purposes, it is questionable if such a parametrization would yield meaningful benefits (what would be imaginable are better generalization guarantees, due to compactness of the graphon-signal space w.r.t. cut distance, as well as the possibility of extensions to sparse graph limits).

We thank the reviewer for their valuable suggestions and positive feedback on our work!

The paper does not provide numerical experiments.

We added some proof-of-concept experiments; please refer to the general comments.

Minor comments:

1. It is a standard fact that the cut norm can be bounded by the $\mathcal{L}^1$ norm, and the inequality for arbitrary $p$ indeed follows straightforwardly (specifically for $[0,1]$).
2. $\mathbb{G}(W, \mathbf{X})$ is the definition of the simple random graph obtained by sampling edges $e_{ij}$ further from $W(\mathbf{X})$ via $e_{ij} \sim \mathrm{Bernoulli}(W(X_i, X_j))$.
3. Thanks for spotting this!

Suggestions

1. We have attempted to make this a bit clearer, and added a reference which explains the concept in more detail.
2. Please see the general comments, § 5.2, and Figures 1-3.
3. We agree that this adds to the readability, and have changed the sentence accordingly.

We thank the reviewer for their helpful comments and suggestions, and we have addressed these points in the revision of the script.

We highly appreciate the reviewer’s thoughtful feedback and their positive remarks on our work. See below for detailed answers to the concerns and questions raised.

It's not clear what the consequences for ML on graphs are. […] Do you have an example where this property hinders size generalization?

Please refer to the general comments.

IWNs from Cai & Wang (2022) preserve convergence when sampling graphs from (sufficiently regular) graphon, but yours doesn't?

The IGNs as framed by Cai & Wang in [1] have similar convergence properties as IWNs: Cai & Wang show that IGNs applied to weighted graphs sampled from a graphon (”edge probability continuous model”) converge, but IGNs applied to unweighted graphs (”edge probability discrete model”, by [1] demonstrated through the model from Keriven et al. in [2]) do not. While the former only requires continuity of the model in $\delta_p$ distances, the latter would require continuity in the cut distance $\delta_\square$ (see, e.g., Eqs. (3) and (4)).

It appears that many results from Böker et al. (2023) and Levie (2023) were reproven using the same techniques for graphon-signal or IWNs.

While the results of Böker [3] and Levie [4] are indeed foundational to our work, we did not reprove any results and we are convinced that our technical contributions go far beyond a straightforward adaptation of their theory to graphon-signals. One of our technical contributions is the introduction of signal-weighted homomorphism densities in § 3: For finite node-featured graphs there are various notions of homomorphism counts, such as enforcing that homomorphisms are stable w.r.t. node features, or different forms of weighting—for graphon analyses, however, node features have been mostly ignored. The trivial approach does not extend to graphon-signals, which can have node features that just attain a single value on null sets. While proof techniques do overlap with [3] and [5], originally finding a notion of weighted homomorphism that can be used for graphon-signals to elegantly capture (a) weak isomorphism (Theorem 3.3) or (b) the k-WL test (Theorem 3.5) is not straightforward, and was also mentioned as a challenge for future analyses in [3]. Our treatment of IWNs and linear equivariant layers, specifically the definition for general measure spaces and the derivation of a canonical basis in section 4, has a priori little to do with the aforementioned works and makes use of very different techniques, such as the representation stability argument for Theorem 4.2.

It is not clear what the broader impact or significance is

Please refer to the general comments.

References

[1] Chen Cai and Yusu Wang. Convergence of Invariant Graph Networks. In Proceedings of the 39th International Conference on Machine Learning, pp. 2457–2484. PMLR, June 2022.

[2] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolutional networks on large random graphs. Advances in Neural Information Processing Systems, 33:21512–21523, 2020.

[3] Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, and Christopher Morris. Fine-grained Expressivity of Graph Neural Networks. Advances in Neural Information Processing Systems, 36:46658–46700, December 2023.

[4] Ron Levie. A graphon-signal analysis of graph neural networks. Advances in Neural Information Processing Systems, 36:64482–64525, December 2023.

[5] László Lovász. Large Networks and Graph Limits. American Mathematical Soc., 2012.

We thank the reviewer for their comments and positive feedback on our paper.

absence of empirical experiments and practical application scenarios

See general comments.

unclear whether the mathematical assumptions hold across diverse real-world datasets

Indeed, graphons are dense graph limits, while real-world datasets often exhibit sparser structures. Nevertheless, still any finite graph can be represented as a graphon, and our analyses do not impose any additional regularity assumptions on the graphon such as their continuity, which is much more restrictive.

computational overhead

IWNs can be applied to any finite graph and have the same asymptotic complexity as IGNs or higher-order GNNs for any given tensor order. Also, our construction is smaller than the full IGN basis (see § F).