Higher-Order Graphon Neural Networks: Approximation and Cut Distance
Authors: Daniel Herbst
Stefanie Jegelka
Venue: ICLR 2025 Spotlight (2025)
Keywords: Graph neural networks
invariant graph networks
universal approximation
graph limits
graphons
transferability
homomorphism densities
machine learning theory.
Primary area: learning on graphs and other geometries & topologies
TL;DR: We extend higher-order GNNs to the graphon space and investigate their continuity, expressivity, and transferability.

Abstract: Graph limit models, like *graphons* for limits of dense graphs, have recently been used to study size transferability of graph neural networks (GNNs). While most literature focuses on message passing GNNs (MPNNs), in this work we attend to the more powerful *higher-order* GNNs. First, we extend the $k$-WL test for graphons (Böker, 2023) to the graphon-signal space and introduce *signal-weighted homomorphism densities* as a key tool. As an exemplary focus, we generalize *Invariant Graph Networks* (IGNs) to graphons, proposing *Invariant Graphon Networks* (IWNs) defined via a subset of the IGN basis corresponding to bounded linear operators. Even with this restricted basis, we show that IWNs of order $k$ are at least as powerful as the $k$-WL test, and we establish universal approximation results for graphon-signals in $L^p$ distances. This significantly extends the prior work of Cai & Wang (2022), showing that IWNs—a subset of their *IGN-small*—retain effectively the same expressivity as the full IGN basis in the limit. In contrast to their approach, our blueprint of IWNs also aligns better with the geometry of graphon space, for example facilitating comparability to MPNNs. We highlight that, while typical higher-order GNNs are discontinuous w.r.t. cut distance—which causes their lack of convergence and is inherently tied to the definition of $k$-WL—transferability remains achievable.

Published as a conference paper at ICLR 2025
HIGHER-ORDER GRAPHON NEURAL NETWORKS: APPROXIMATION AND CUT DISTANCE
Daniel Herbst' and Stefanie Jegelka 12,3
'TUM, School of CIT "TUM MCML and MDSI 'MIT. Department of EECS and CSAIL {daniel herbst, stefanie. jege 1 0t de
ABSTRACT
Graph limit models, like graphons for limits of dense graphs, have recently been used to study size transferability of graph neural networks (GNNs). While most literature focuses on message passing GNNs (MPNNs), in this work we at- tend to the more powerful higher-order GNNs. First, we extend the k-Wl. test for graphons (Böker, 2023) to the graphon-signal space and introduce signal- weighted homomorphism densities generalize Invariant Graph Networks (IGNs) to graphons, proposing Invariant Graphon Networks (IWNs) defined via subset of the IGN basis corresponding to bounded linear operators. Even with this restricted basis, we show that IWNs of order are least as powerful the k- test, and we establish universal approximation results for graphon-signals in I,P distances. This significantly ex- tends the prior work of Cai & Wang (2022), showing that IWNs- a subset of their IGN-small-retain effectively the same expressivity the full IGN basis in the limit. contrast to their approach, our blueprint IWNs also aligns better with the geometry of graphon space, for example facilitating comparability to MPNNs. We highlight that, while typical higher-order GNNs are discontinuous w.r.t. cut distance which whhnh causes their lack of convergence and is inherently tied to the definition of -W.-ttranferabbllii remains achievable.
key tool. As exemplary focus, we
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as a powerful tool for machine learning on complex graph-structured data, driving advances in fields like social network analysis (Fan et al., 2019), weather prediction (Lam et al., 2023) or materials discovery (Merchant et al., 2023). Message Passing GNNs (MPNNs) (Gilmer et al., 2017; Kipf & Welling, 2017; Veličković et al., 2018; Xu et al., 2019), which update node features by neighborhood aggregations, are a popular paradigm.
MPNN generalizes to larger graphs than those in the training set-has recently gained attention. Unlike extrapolation (Xu et al., 2021: Ychudai al., 2021; Jegelka, 2022), where generalization arbitrary graph topologies is considered, size transferability typically assumes structural similarities between the training and evaluation graphs, such them being sampled from the same random graph model (Keriven et al., 2020), topological space (Levie et al., 2021), or graph limit model (Ruiz et al., 2020; 2023; 2021b; Maskey et al., 2024; Le & Jegelka, 2023). For limits of dense graphs, graphons (Lovász & Szegedy, 2006; Lovász, 2012), which extend graphs to node sets on the unit interval and have been used to study extremal graph theory with analytic techniques, have also become popular choice for studying transferability. In contrast to sparse graph limits (Lovász, 2012; Backhausz. & Szegedy, 2022), they offer an established framework with powerful tools, such as embedding the set of all graphs into a compact space and having favorable spectral properties (Ruiz et al., 2021a). In such transferability analyses, GNN is extended to a function of graphons, and regularity properties of the GNN are then used to bound the difference between outputs of the GNN applied samples of different sizes from a graphon.
The question of size transferablity-whheeeee
Existing works on transferability have been almost exclusively limited to MPNNs. However, their expressive power is constrained by the 1-dimensional Weisfeiler-Leman graph isomorphism test (1- WL), also known as the color refinement algorithm (Xu et al., 2019; Morris et al., 2019). Hence, standard MPNNs even fail at straightforward tasks such counting simple patterns like cycles.

---

Published as a conference paper at ICLR 2025
This motivates extending generalization analyses to more powerful architectures. Most prominent among these are higher-order extensions of MPNNs that are as powerful as the k-WL test, k > 1, which iteratively colors k-tuples of nodes (Morris et al., 2019). Invariant and Equivariant Graph Networks (IGNs/EGNs) (Maron et al., 2019b), which serve as an exemplary focus in this work, are popular architectural choice, in which adjacency matrices and node signals are processed through higher-order tensor operations that maintain permutation equivariance. IGNs/EGNs universally ap- proximate any permutation in-/equivariant graph function, and are as powerful as k-WL with orders S k (Maron et al., 2019c; Keriven & Peyré, 2019; Maehara & NT, 2019; Azizian & Lelarge, 2021).
The expressive power of a GNN can also be judged via its homomorphism expressiviny, i.e., its ability to count the number of homomorphisms from fixed graphs into the input graph. E.g. 1-WL corresponds to counting homomorphisms w.r.t. trees, and its higher-order extensions are related to counting homomorphisms w.r.t. graphs of bounded treewidth (Dvořák, 2010; Dell et al., 2018). In the graphon case, similar results exist for homomorphism densities (Böker et al., 2023; Böker, 2023).
In this work, we study expressivity, continuity, and transferability properties of higher-order GNN extensions to graphons. Maehara & NT (2019) note that their IGN/EGN universality proof-using a to graphons. They re- gard the use of graphons for such analyses as promising. Keriven et al. (2021) study the convergence of universal class of GNNs based node IDs and identify the analysis of higher-order GNNs as an open direction. The closest related work by Cai & Wang (2022) investigates the convergence of IGNs to limit graphon via partition norm-a vector of norms over all diagonals of graphon. They observe that IGNs on traphon-samples graphs do not always converge. They propose a re- duced model class IGN-small, which enables convergence after estimating edge probabilities under certain regularity conditions. They also show that IGN-small retains sufficient expressiveness to approximate spectral GNNs. We argue that considering diagonals of graphons (which would lead to a limit object of self- graphs) is somewhat nonstandard in the larger body of work in graphon theory, limiting its applicability to their version of IGN limits. Furthermore, the expressivity analysis of IGN-small is rather limited, given that IGNs are typically universal GNN architectures.
parametrization relying on explicit simple homomorphism densities-
Contributions. A first focus of this work is to extend the k- test (Böker, 2023) and homo- morphism densities from graphons to graphon-signals (Levie, 2023), i.e., node-attributed graphons. For the extension of homomorphism densities, we introduce signal weighting and show that signal- weighted homomorphism densities inherit most topological properties from their graphon equivalent.
We generalize IGNs to suuphon-signale introducing Invariant Graphon Networks (IWNs). In con- trast to Cai & Wang (2022), we restrict linear equivariant layers to bounded operators, and, thus, our IWNs can be analyzed using LP and cut distances, enhancing comparability to the existing graphon literature. Using only this reduced basis, we show that IWNs of order up to h are as powerful as the k-WL test for graphon-signale and we establish universal approximation results in L distances. As IWNs are a subset of IGN-small, this significantly extends the work of Cai & Wang (2022), resolving the open questions posed in their conclusion: We show that the restriction to IGN-small comes at no cost in terms of expressivity, We carry out expressivity analyses using our notion of homomorphism expressivity via signal- weighted homomorphism densities. IWNs are discontinuous w.r.t. the cut distance and only continuous in the finer topologies induced by T.P distances, which do not represent our intuitive notion of graph similarity (Levie, 2023). This discontinuity is not unique to IWNs, but inherently tied to the way in which k-WL processes edge weights, and results in a large class of higher-order GNNs defined via color refinement exhibiting an absence of convergence under sampling simple graphs. Yet, despite this discontinuity, transferability is still possible.
To the best of our knowledge, this work is the first to extend higher-order GNNs to graphons in way that facilitates a systematic study of continuity, expressivity, and transferability in comparison to MPNNs, addressing the aforementioned challenges of Cai & Wang (2022) while building on the foundational work of Böker (2023). In summary, we make the following contributions:
We define signal-weighted homomorphism densities, link them to a natural extension of the k-WL test to graphon-signals, and show how they capture graphon-signal topology.
We introduce Invariant Graphon Networks (/WNs), restricting linear equivariant layers to bounded operators. We show that IWNs of order k are at least as powerful as &-WL for graphon-signale and establish universal approximation, extending Cai & Wang (2022). We point out the cut distance discontinuity of typical higher-order GNNs and demonstrate that such models are still transferable despite not converging to their graphon limit.
2

---

Published as a conference paper at ICLR 2025
2 BACKGROUND
In this section, we provide background on graphon theory, homomorphism expressivity, and the k- WL. test for graphons, as well as on how to extend graphons to incorporate node signals. Contents of $ 2.1 and $ 2.2 are mostly drawn from Lovász (2012); Janson (2013); Zhao (2023), while in $ 2.2 we also refer to Böker (2023). In 2.3 we summarize key results of Levie (2023).
For n N. write [n]] == (l....,..) n.. Unless stated otherwise, a graph always refers to a simple graph, meaning an undirected graph G = (V, with finite node set V(G) V and edge [E())) We will also consider multigraphs, for which the edges are a multiset. Write X for the k-dimensional Lebesgue measure; A : X See $ A for a table of notation and B.1 for background on topology and measure theory.
set F(G) E (K) Define also v(G) == [V[ e(G)
2.1 GENERAL BACKGROUND ON GRAPHON THEORY
Graphons. Informally, a graphon can be seen as a graph with node set [0, 1], and the adjacency
matrix being represented by function on the unit square. Intuitively, graphons can be obtained by taking the limit of adjacency matrices of dense graph sequences as the number of nodes grows. Formally, we first define a kernel as bounded symmetric measurable function W [0, 1]2 - R. A graphon is a kernel mapping to [0, 1]. Write W for the space of kernels; Wo for graphons. Define the cut norm of a kernel as
1/ Wdx? S, SxT
| = sup
(1)
where S, are tacitly assumed measurable. Let S(o,1] be the set of measure preserving maps yp [o, 1] + [0. 1] that are bijective almost everywhere; that is, for every measurable A S [0. 1]. we have (A)) = X(A). Write S(,.1] for the set of all measure preserving functions and define (z y) == (xx(x)) (p))) for & E S
1]- Since the specific ordering of the graphon values does not matter, we work with the cut distance (Lovász, 2012, $ 8.2) between two graphons, defined as
8D(W, V) == inf (E.
| Vo
min | - V
(2)
p..)
where the infimum is only guaranteed to be attained in the latter expression. Analogously, we can define distances 6, on graphons based on L norms, p E [1, Note that on I 51 (which follows from moving |- into the integral in (1)) and 8p <6 for p S q. on and {6p]p. p. p co, vanish simultaneously. However, the topology induced by 8 is strictly coarser than that induced by (6p) pe(l.c) (all of which coincide), which is in turn coarser than the topology induced by 8 The most commonly used among pp is 51, which corresponds (up to an absolute constant; (2012, $ 9)) to the edit distance on graphs. We identify weakly isomorphic graphons of distance O to form the space Wo of unlabeled graphons. The stricter concept of (strong) isomorphism, namely that the minimum over Sjo.1] in (2) is attained and zero, is less practical. The usefulness of & over any 6p lies in the fact that (Wy, 8m) forms compact space (Lovász, 2012, Theorem 9.23).
Lovász
Discretization and sampling. Any labeled graph G with adjacency A E Raxn can be identified with its induced step graphon Wg := Σi= Σx=1 A for regular partition { 1 of the unit interval, and finite graphs are dense in the graphon space (Zhao, 2023, Theorem 4.2.8). Graphons can also be seen as random graph models: Draw X ~ (0, 1)", and let W(X) be a graph with edge weights W,; = (X,,, X2). If eij Bernoulli(,,)) is further sampled, we obtain an unweighted graph G(W,X) X). Write (W) and (W) for the respective distributions. We have on(HH, (W), W) < 6, (H., (W), W) + 0 (Zhao, 2023, Lemma 4.9.4). Also on (G, W) - 0 (Lovász, 2012, Proposition 1 11.32), but this does not hold for 6;: Take, e.g., W = 1/2, then 6, G. G., (W)) 1/2 for all n E N.
Homomorphism densities. Let (F.(F. denote the number of homomorphisms from a graph F into graph G. The corresponding homomorphism density is defined ((F, G) hom F, ()))(G)(FF) i.e., the proportion of homomorphisms among all maps V(F) + V(G). We define the homomorphism density of a (multi)graph F with ((F) = [b]] to a graphon W by
((F, W) == /
II 10.11 ((S)EE(F)
W() dx (x)).
33)
3

---

Published as a conference paper at ICLR 2025
where factors may appear multiple times for multigraph. This generalizes the discrete concept in the sense that t(F. G) = =((F, Wc). For a sequence (W,)n of graphons, (W W) - iff t(F, W,, + t(F, W) for all simple graphs F, and thus two graphons W, V are weakly isomorphic iff ((F = i(F, V) for all simple graphs F. Hence, homomorphism densities can be seen as a counterpart of moments of a real random variable for W-random graphs, as they fix the distribution G. (W) similarly as the moments would for well-behaved real random variable (Zhao, 2023).
2.2 LL AND HOMOMORPHISM EXPRESSIVITY
In the discrete setting, the I I-dimensional Weisfeiler- (1-WL) graph isomorphism test (or color refinement algorithm) and its multidimensional extensions are widely used to judge the expressive power of a GNN model. Alteraatielyy, the model's 's homomorphism expressivity, i.e., its ability to count the number of homomorphisms from smaller graphs, called patterns, into the input graph, can be considered. Through homomorphic images (Lovász, 2012, $ 6.1), this also relates to subgraph counting (Chen et al., 2020; Tahmasebi al., 2023; Jin al., 2024). 1-WL expressivity corresponds precisely to distinguishing graphs for which the values of hom differ if T are trees. More gen- erally, k- GI can be precisely characterized as being able to compute (hom [. [F,))].. r. with F ranging over all simple graphs of treewidth bounded by k (Dvořák, 2010; Dell et al., 2018). See also $ B.4 for more information on treewidth and the tree decomposition of graph. A finer characterization for various GNN architectural choices was recently shown by Zhang et al. (2024).
The 1-WL test has been extended to graphons by Grebík Rocha (2022) through the concept of iterated degree measures (IDMs). These serve as the continuous counterpart of the color space used in the color refinement algorithm for graphons and are represented by sequences (an)n of colors after refinement rounds. The distribution of such colors, akin to the multiset of all assigned colors per node, represents the result of the isomorphism test. As in the discrete case, two graphons 1- indistinguishable iff their tree homomorphism densities match.
Recently, Böker (2023) developed a &- test for graphons using distributions of k- WL measures. Intuitively, for given graphon W, the mapping City C. assigns color to every k-tuple of nodes in [0, 1] these colors elements of topological space M called k- W- measures. The resulting k-WL distribution, defined as the pushforward V 1-WL == (CW:LL).X X E P(M)), is Borel proba-
bility measure on M² that captures the test's output. Notably, the homomorphism characterization of this natural k-WL test is given in terms of mulligraph homomorphism densities w.r.t. patterns of bounded treewidth (rather than simple graphs as for I-WL). See also & D. Note that in this work, k- &-WL always refers to the oblivious k-WL instead of the Folklore k- k-WL test, which also processes k-tuples but is (k + 1)-WL expressive (Cai et al., 1992; Grohe & Otto, 2015; Jegelka, 2022).
2.3 EXTENSION TO GRAPHON-SIGNAL
Most common GNNs take a graph-signal (G, as inputs, i.e., a graph G with node set [x] == (1...., ... n) and a signal f RR with l being the number of features. Levie (2023) extends this definition to graphons with mi-ddmmenioonal node signals. They fix r > 0, consider signals in L [0, 1] = (f [0, 1] Il S r}. and set Ilf == supsg [ss dx| with S measur- able. Note that this is equivalent to the signal L' norm. They then let WS, := Wy x [0, 1] and define the norm [[W,f)ll, == || + If Define on and 6p. step graphon-signals and sampling from graphon-signals analogously to the standard case. F.g., write G, G, (W,J) f) for the dis- tribution of (G(W, X), f(X)) X U(D,1)* 1)" Also, identify weakly isomorphic graphon-signals of cut distance zero to obtain the space WS, of unlabeled graphon-signals. Central to their con- tribution, Levie (2023) establishes the compactness of (WS,,. 65) and bounds its covering number (cf. B.5). They also derive a sampling lemma: For r > 1, (W,f) E WS,, and large n E N.
E [6 (W, < 15 (logn)-1/2,
(4)
3 SIGNAL-WEIGHTEE HOMOMORPHISM DENSITIES
is important to note that Böker et al. (2023); Böker (2023) focus exclusively on graphons and do not consider graphon-signals, and Levie (2023) does not introduce notion of homomorphism den-
4

---

Published as a conference paper at ICLR 2025
sities for graphon-signals either. However, since most GNN architectures in the literature operate on node-featured graphs, we need a concept of homomorphism densities that reflects the properties of the graphon-signt space well. This could then, e.g.. be applied to characterize the homomorphism expressivity of GNN models on graphon-signals, similar to the approach for graphons outlined in $ 2.2. As in Lovász (2012, $ 5.2) for finite graphs, we introduce weighting by signals.
Definition 3.1 (Signal-weighted homomorphism density). Let F be multigraph with V(F) = [k].. d Ni. and let (W, f) E WS,. We set
t((F, d), (W. = [ 10.11
III II iEV(F)
s(x:)))
II
(x),,z)) dd* (x).
(5)
(())E((F)
calling the functions (((F.d)..) signal-weighted hamomorphism densities.
Note that setting d = 0 E NO recovers the graphon homomorphism densities t((F, 0), ()) = t(F, W'. d * O will allow viewed as a multiset of nodes, similarly to homomorphism densities of multigraphs. This enables us capture the distribution of the signal, coupled with the graph structure, which will be crucial for (5) to separate non- oon-weakly isomorphic graphon-signals. In contrast to common approaches in the GNN literature, only considering d does not suffice in our case, as this only distinguishes graphs under twin reduction. Restricting the exponents to be the same across all nodes as in Nguyen & Maehara (2020) results in {+((F, d).-) F). not being closed under multiplication, which would later pose challenges. The finite-graph approach of enforcing homomorphisms to respect signal values does not extend to graphon-signals the level sets { = /} may all have measure zero, making homomorphism densities degenerate. A possible workaround is incorporating "similarity kernels" in (5) for approximate matches, but this also appears to be less practical.
consider moments of the signal, which could alternatively be
The definition of signal weighting assumes a scalar-valued signal f. with integer node features d acting via x + zd., This could be straightforwardly extended to signals mapping into a compact space K, where we define signal-weighted homomorphism densities by replacing pattern node fea- tures with continuous functions w E ((K))((F) applied pointwise to (x;). To uniquely determine a graphon-signal, it suffices to use dense subset of the continuous functions C(K). such as poly- nomials for K = [-r, r]. which form algebras and enable the use of the Stone-Weierstre Weierstrass theorem.
As a first step, we derive counting lemma (cf. & C.I) similar to the standard graphon case (Lovász, 2012, Lemma 10.23), which shows that signal-weighted homomorphism densities from simple graphs into a graphon-signal are Lipschitz continuous w.r.t. cut distance. A similar statement can also be shown for all multigraphs using 61. However, the main justification for Definition 3.1 is The- orem 3.2 (akin to Theorem 8.10 from Janson (2013)), as well as Corollary 3.3, demonstrating how signal-weighted homomorphism densities capture weak isomorphism and the topological structure of the graphon-signal space in a similar way as do homomorphism densities for graphons:
Theorem 3.2 (Characterizationss of weak isomorphism for graphon-signaly, Fix r >> 1 and let (W, (V, E WS,. Then, the following statements are equivalent:
(1) JV, = 0 0.for any p (1);;);
(2) (W,,,)) =0; 0;
(3) (((F,d), (W) = t((F, d), (V,g)) for all multigraphs F, d E Ny
(4) d((F,d), (W. = =((FF, d), (V,g)) for all simple graphs F, E ny)
(5) (W, 2 (V. for all ie E N;
(6) (W, 2 Gx for all k E N.
See $ C.3 for the proof. The equivalence (1) + (2) in Theorem 3.2, which we show in $ C.2 by ex- tending the argument of Lovász (2012, Theorem 8. 8.13), reveals that any (6p]pe[l.sc) distance could be alternatively used to define weak isomorphism of two graphon-signals. Thus, any 5p can also be seen as a metric on the space of unlabeled graphon-signals. The other equivalences show that weak isomorphism of two graphon-signals can be alternatively characterized by them having the same signal- weighted homomorphism densities, and the same random graph distributions. Specifically, {t( (F, d).))). >)) fixes the distribution of (W, f -rando graphs similarly as do homomorphism den- sities for W -random graphs or moments for real- valued random variables. We also remark that the condition > stems from the fact that we use the graphon-signal sampling lemma (Levie, 2023,
5

---

Published as a conference paper at ICLR 2025
Theorem 3.7). The following corollary shows that signal-weighter homomorphism densities of sim- ple graphs precisely characterize cut distance convergence (refer to Š C.4 for the proof):
Corollary 3.3 (Convergence in graphon- signal space). For (Wn, fo)m (W, E WS, and r > 1,
8 (WWn: fr); (W, +0
t((F, d), fw)) t((F.))) (W,)) YF NO(F) (6)
as n + oc, with ranging over all simple graphs.
Finally, we show that hignal-weighte homomorphism densities also make sense on the granularity level of the k-WL hierarchy, in the way that their indistinguishabiliyy is equivalent to the equality of a natural generalization of k- WL distributions as defined Böker (2023) to graphon-signals.
Theorem 3.4 (k- (L-WL for graphon-signals. signals, informal). Two graphon-signals (W. f) and (V.g) are k-WL indistingguishable if and only (fF((FF d), (W, f)) t((F, d), (V,9)) for all multigraphs F of treewidth < 1, d E ENO (2F
Due to their technical nature, all details, including the formal definition of the k-WL color space for graphon-signals as well as a formal statement of Theorem 3.4, are deferred to $ D.
INVARIANT GRAPHON NETWORKS
In this section, we introduce Invariant Graphon Networks (ZWNs) as an exemplary higher-order architecture on the graphon-signal space. The key components of IWNs are the linear equivariant layers, which we extend from the original framework of Maron et al. (2019b) spaces. We also determine the dimension of these layers and establish a canonical basis. We then proceed to define multilayer IWNs, highlight connections to the work of Cai & Wang (2022), and analyze the expressivity of IWNs.
arbitrary measure
4.1 LINEAR EQUIVARIANT LAYERS
We start with generalizing the building blocks of CEINs-namely, the linear equivariant layers. For IGNs, these are linear functions T RR" -> Rp=" such that is equivariant w.r.t. all permutations acting on the n coordinates. We now extend this notion from the set [n] to arbitrary measure spaces. The suitable generalization permutations will measure preserving maps:
Definition 4.1 (Linear equivariant layer). Let (X, p)) be measure space, simply denoted X, and let Sx be the set of measure-pree prensrripreseriing functions yp X + X. Let k, l E No. Write X for (x* A8k k 2²8h) and note that L (x) @k (²(xx)). Define the linear equivariant layers
LE (T C(L (x*))) Vip E Sx T(U*) TUU)² a.e.}
(7)
as the space of all bounded linear operators that are equivariant w.rf. all measure preserving func- and L(:,))
tions on X, iee, all relabelings of X. Here, UP (rI...., = denotes bounded linear operators.
For X == [n]] with a uniform probability measure (or counting measure), we obtain L2((n)) _ R." - and LE k- can be identified with the space of linear permutation equivariant functions R" - Rn as measure preserving functions [n] + [n] are just the permutations Sn. This yields precisely the linear equivariant layers that are building blocks of IGNs, which were studied by Maron et al. (2019b). One of their results is that dim LE("]
bell(k + (), with bell(m) denoting the number of partitions I m. of [m], independent of n. There exists canonical basis in which every basis element 2r(a) LE(" k corresponds to a partition 7 E I'+G, with basis elements being simple operations such extracting diagonals, summing/averaging over axes, and replication (see $ B.2).
interested in LE L as building blocks of IWNs, where [0, 1] is equipped with its Borel o-algebra and Lebesgue measure. The immediate question is how this space
For graphons,
compares to LE(n] - i.e., what its dimension is and if there exists canonical basis parameterize IWNs later on. It turns out that this space can be seen as just implementing a subset of the possibilities in the discrete setting, which is essentially consequence of [0. being atomless.
use to

---

Published as a conference paper at ICLR 2025
Theorem 4.2. Let & E No. Then, LEx-1 is a f mnite-dimeesional vector space of dimension
min (k
(
dim LEx-18 =
Σ
S bell(k: + +E).
(8)
The proof can be found in E.1. Central to the argument is the observation that can consider the action of any T E LEx->z on step functions, and apply the characterization from Maron et al. (2019b) sequence of nested subspaces, which fixes the operator the entire space [2 1] In fact, (8) is precisely the dimension of the Rook subalgebra of the partition algebra (see, e.g., Grood (2006); Halverson & Jacobson (2020)).
A canonical basis of LE The proof of Theorem 4.2 also provides insight into constructing a canonical basis of LE which is indexed by the following subset of the partitions Tate of [k [k+0) E]:
I' = {7 T'te VAET: 7: |An [&] S 1, IAn (K+ + (0] [0)
For a partition E TR.e, suppose that contains s sets of size 2 (1..1 fi,, with 21.....k ..g E [k], Ji.....JJ. E + [e], and let a (ii...... ..).. b (J.....,ss). Then, we can
write the corresponding basis element T, E LE
/ Jo.11-- U ap dx (((
TV(1) = [0. [0.1]
(10)
In comparison to the basis of Maron et al. (2019b), this corresponds precisely to the basis elements for which diagonals of the input are selected, and the output is always replicated space. We also note that the choice p 2 in Definition 4. is somewhat arbitrary, and T, can indeed be seen as operator L" + L for any p [1), with [[T,] p-p 1 (see $ E.2). We also briefly analyze the asymptotic dimension of LE compared to the discrete case in $ E.3.
the entire
4.2 DEFINITION OF INVARIANT GRAPHON NETWORKS
Using LEx- building blocks, we extend the definitions of IGNs from Maron al. (2019b) to graphons. This also corresponds to the definition used by Cai & Wang (2022), with the restriction that linear equivariant layers are limited to LE
Definition 4.3 (In- and equivariant graphon networks). Let o - RR be an activation. Let S E N, and for each E (O...., S), let k2 E No, d, E. Set (do, Ko) == (2, An Equivariant Graphon Network (EWN) is function that maps graphon-signal (W, E WS, to
NEWS (W.)) = 0.....0....... (30))000...000))) 00. (W,S),
(11)
where for each s E [S].
(U) with T(s) E (LEx..1-X..) di b(() E (LEo-+x.) and (U); == Σj (U,) for i EE [dg]. Here, the addition of the bias terms b(s) and application of e are understood elementwise. (W, is identified with [(x. + (W(x,,) (x) [xx)] in the first layer. An Invariant Graphon Network (IWN) is an EWN with (ds, ks) = (1, i.e., mapping to scalars.
I(t): (L310, (1310,116--)) 1//--1)aa do-1 + 11 U U (U) + b60)
(12)
We call max k. the order of EWN, and k; the orders of the individual layers. For notational convenience, we defined the individual biases as elements of LEo (noting that the input space of such function is a singleton). In the discrete setting, individual weights are assigned biases that are constant over the entire tensor and all its diagonals. Here, however, this issue does not arise because dim LE is always so the bias is merely scalar. Note that any IWN can be seen as function N /INN WS, + R, as it is invariant w.r.t. all +p E 3 by the definition LE
We also immediately observe that IWNs yield a parametrization that is closely related to IGN-small proposed by Cai & Wang (2022), a subset of IGNs with more favorable convergence properties under regularity assumptions on the graphon; their work, they define IGN- small as continuous IGNs (i.c., defined on graphons with signals) for which grid-sampling commutes with application of the discrete/continuous version of the IGN.
Cai & Wang (2022, Theorem 4) and B.3. In

---

Published as a conference paper at ICLR 2025
Proposition 4.4. Any IWN from (11) is instance of IGN-small (Cai & Wang. 2022).
The proof of Proposition 4.4 (see E.4) is a direct application of invariance under discretization (Lemma E.2) and representation stability of the basis elements. While the IGN-small constraint ap- plies to the entire multilayer network, we impose our boundedness condition on each linear equivari- ant layer individually. Consequently, it does not follow that every linear equivariant layer used in an IGN-small model must lie -Ex->e. The crux this discrepancy is that a graphon can, for exam- ple, be mapped into higher-dimensionn output by integrating over that diagonal. Although this overall procedure meets the IGN-small con- sisteney requirement, each single layer involved may fail to be bounded linear operator. Moreover, while IWNs only utilize a subset of the basis employed by IGNs, the following section will show that IWNs can still attain strong expressivity on par with the discrete setting. By Proposition 4.4, these expressivity results extend to IGN-small as well.
diagonal, from which the network might then compute its
4.3 EXPRESSIVITY OF INVARIANT GRAPHON NETWORKS
We prove expressivity results for IWNs, namely that IWNs up to order it are at least as powerful as k- k-WL for graphon-signale and that they act as universal approximators in the óp distances on any compact subset of graphon-signals. The analysis relies on the weinal-weighted homomorphism expressivity of IWNs ($ 3). Clearly, IWNs are continuous in all 6, distances (see & E.5 for a proof):
Lemma 4.5. Let Nrwx WS, + R be IWN with Lipschitz continuous nonlinearity g. Then, ArWN is Lipschitz continuous w.r.t. 6, for each p E oo).
As first step towards analyzing expressivity, we show that IWNs can approximate signal-weighted homomorphism densities w.r.t. graphs of size up to their order. Inspired by Keriven & Peyré (2019) 9), we explicitly model the product in the homomorphism densities and track the employed linear equiv- ariant layers. Finally, the result follows via a tree decomposition of the graph:
Theorem 4.6 (Approximation of signal- weighted homomorphism densities). Letr > 0. < N, @ + Lipschitz continuous and non-polyme non-polynomial, and be multigraph of treewidth k 1, d E NP(P) Fix e > 0. Then there exists an IWN NoW of order ls such that for all (W,J) f) E WS,
[M([F, d), (W, f)) NAwS (W S 6.
(13)
The proof (see $ E.6) is by induction on the tree decomposition of a graph. As we traverse the tree, we introduce IWN layers that add new nodes and marginalize over processed ones. We write Tht for the set of all IWNs w.r.t. nonlinearity o, and 8h-twN for the restriction to IWNs of order up to k. Note that an immediate consequence of Theorem 4.6 (refer to E.7):
that IWNs are k- k-WL-expressive
Corollary 4.7 (k-WL. expressivity). s S-h-ww is least as expressive the k-WL test at distinguish- ing graphon-signals.
As know from Theorem 3.2 that two graphon-signals are weakly isomorphic if and only if {t((F, d), F)r agree for all simple graphs or multigraphs F, Theorem 4.6 gives us an immedi- ate way prove universal approximation when not restricting the tensor order.
Corollary 4.8 (6,- -iyierrrrslllty of IWNs). Let r > 1, p E [1, o: IR + R Lipschitz continuous
and non-polynomial. For any compact K C (WSr,, 8p), R!wN is dense in the continuous functions C(K) w.r.f I1-
The proof (see $ E.8) straightforward application of the Stone- Weierstrass theorem: The span of the signal- separating. This result also crucially implies that IWNs can distinguish any two graphon-signale that are not weakly isomorphic. We also want to mention that while IWNs are continuous w.r.t. 8 the proof of Theorem 3.2 does not extend to this case as || is not a smooth norm on [0, 1|2.
homomorphism densities forms a subalgebra that, by Theorem 3.2, is point
CUT DISTANCE AND TRANSFERABILITY OF HIGHER-ORDER WNNS
In this section, discuss the relation of IWNs and more general higher-order graphon neural networks (referred to as "WNNs") to the cut distance and their transferability. One example besides IWNs are refinementbbaeed networks that emulate the k-WI. test, such as the ones define in $ F.
8

---

Published as a conference paper at ICLR 2025
5.1 CUT DISTANCE DISCONTINUITY AND CONVERGENCE
We first note that all nontrivial IWNs are discontinuous w.r.t. cut distance, in the following sense: Proposition 5.1. Let e : [0,1] + R. Then, the assignment Wo ô W + e(W) W, where is applied pointwise, is continuous w.r.t. Illla if and only if o is linear.
See $ G.1 for proof. This is evident in that node-featured graphs obtained from sampling do not converge to their underlying graphon-signal a phenomenon first observed by Cai & Wang (2022) in a related setting. This discontinuity is inherent to k-WL (Böker, 2023) because it uses multigraph homomorphism densities, which are discontinuous in the cut distance. As such, any k-WI. ex- pressive function defined graphon-signals would exhibit this discontinuity. The consideration of multigraphs arises from a fundamental difference in how k-WL and I-WL handle edges. For 1-WL, weighted edges are treated simply weights, i.e., function values of graphon only act through its shift operator and, thus, carry precisely the meaning of edge probabilities. For intuition, note that most operator norms of the shift operator topologically equivalent to the cut norm (Janson, 2013, Lemma E. In contrast, typical k- k-WL expressive models capture the full distribution of these edge weights, rather regarding them edge features. For IWNs ($ 4), this manifests through pointwise application of the nonlinearity on the graphon-signal. Although the parametrization of Maehara & NT (2019) as a linear combination of simple homomorphism densities is cut distance continuous, its purely conceptual formulation provides no clear guideline for selecting pattern graphs.
Note that, a priori, this might constitute disadvantage of such higher-order models compared to MPNNs. In particular, while the space (WS,,, 6n) is compact-allowiin for the direct application of the Weieesssssss theorem and the derivation of generalization bounds as in Levie (2023)- no similar results hold for (WS,, with p [1, oo). Although one can of course restrict the domain to compact subsets, as done for Corollary 4.8, it is doubtful if real-world distributions of node-featured graphs (or graphon-signals) would be confined to these. One example of subsets that are indeed compact w.r.t. 6, distances though of limited utility, particularly in the context of graph limits- is the set of regular step graphons bounded by some maximum size. This is somewhat similar to the restriction of Keriven & Peyré (2019) in their universality proof for IGNs/EGNs.
5.2 TRANSFERABILITY
Often, one may analyze the convergence of a graph ML model / to an underlying limit to study the question of its transferability, i.e., if
(( & (G fm)
(14)
holds when (G.: fn): (Gm, fm) ~ G, G,, as n.m E N grow. In the theory of graph limits, the convergence (14) for any graph parameter N is also known as extimability (Lovász, 2012, $ 15). For the continuous MPNNs converging under their respective graph limits, transferability is usually shown simply by invoking the triangle inequality (see, c.g., Ruiz et al. (2023); Le & Jegelka (2023)), which is not possible for typical higher-order models pointed out in $ 5.1. Even worse, it is not even guaranteed that random graphs sampled from a graphon-signal become close in the 6, distances as they grow in size: For example, take G(1) G((2) to be independent Erdōs-Rényi graphs of size n E N. By Lavrov (2023) and Lovász (2012, Theorem 9,30),
G(P) Z 1 lim inf E (. 20000
(15)
T2
(note that the expectation in (15) would tend to zero in ôn). As, for example, we have seen in Corollary 4.8 that IWNs are universal on compact subsets w.r.t. 81, one might expect there to be an "adversarial" IWN which does not converge to the same value for all such random graphs. However, it turns out that this discontinuity can be "fixed" for large class of functions:
Theorem 5.2 (Transferability). Let > 1. Let N WS, + R such that N is contained in the closure of
span (t((F, d) F multiggrah, dENg(r) dieterpppphdpNp.
S Co(WS,, 81)
(16)
Then, for any (W, E WS, and (Gn, fn), (Gm, fmm w.E.t. uniform convergence. (,, G,, (W,
E [ fn) - ((Gmmfmm) - 0, n, m. > 0o.
(17)

---

Published as a conference paper at ICLR 2025
The proof (see G.2) is immediate and consists of replacing multigraph F in any ((F,, d).-) -) by its corresponding simple graph Fsimple, resulting in a function of (W, f) E WS, which is cut distance continuous. We can further that the assumptions of Theorem 5.2 fulfilled for IWNs, well as more general functions which factorize over the color space of the k- WL test (see also & G.3): Corollary 5.3 (Transferability of higher-order WNNs). The assumption of Theorem 5.2 holds for (1) any IWN with continuous nonlinearity P.
W., ) for continuous N P(M)) + R. (2) any N: WS, - IR for which NW. = N (w(W)))
Note that, while Theorem 5.2 guarantees convergence, it does not make any statement about the rate. For this, one could show that N restricted to finite graph-signals extends to a 6p-Liischitz continuous function on WS,. The challenge here is that a simple and general closed form is not immediate for this extension. Yet, the following can be shown about a subclass of IWNs:
Theorem 5.4 (Quantitative transferability of IWNs, informal). Let > 1. For any N in universal class of 2-layer IWNs with -nalyiic nonlinearity there exists constant MA >> 0 such that for (W, f) WS, and (Gn, fn), (Gms fm) G, f), (W, f) for large n. m,
E | TWN
(G.: GG. fn) - -N fm)l I My (logn) -1/2 + (log m)) m/)3
(18)
See $ G.4 for more details. Note that the rate (logn)-1// in (18) comes from the sampling lemma, and can be substantially better under additional assumptions or different discretization techniques.
SBM
1.00
1.02
1.00
1.00
Aby, aree
0.75
Abs, croor
M0.75
50.75
0.50
g0.50
20.50
Triangular Narrow
0.25
1.00
0.25
0.55
200
H modes
1000
200
nodes
1000
200
nodes
1000
200
nodes
1000
(a) MPNN
(b) 2-IWN
(a) MPNN
(b) 2-IWN
Figure Example
Figure 2: Absolute output er- rors (WW) vs. (W).
Figure 3: 90% pred. interval widths of N (G,(())
graphons W.
We also validate our theoretical findings for IWNs with proof-of-concept experiment on the graphons from Figure 1. For continuity/commrrenncc we plot the absolute errors of the model out- puts for the sampled simple graphs in comparison to their graphon limits in Figure 2. Due to the on-continuity of MPNNs, their errors decrease as the graph size grows. For the IWN, however, this does not hold. Yet, the errors for the IWN stabilize with increasing sizes, suggesting that the out- puts converge (just not to their graphon limit). For transferability, we further plot prediction interval widths of the output distributions on simple graphs for each of the sizes in Figure 3. Here, the widths contract for both models and there are only minor differences visible between the MPNN and the IWN. This validates Theorem 5.2 and suggests that IWNs can indeed have similar transferability properties as MPNNs. For more details, see $ H.
CONCLUSION
In this work, we study the expressivity, continuity, and transferability of graphon- based higher-order GNNs on the graphon-signal space (Levie, 2023) via signal-weighted homomorphism densities. We introduce Invariant Graphon Networks (IWNs) and analyze them through L. and cut distances on graphons. Significantly extending Cai & Wang (2022), we demonstrate that IWNs, as a subset of their IGN-small, retain the same expressive power as their discrete counterparts. Unlike MPNNs, IWNs are discontinuous w.r.t. cut distance, so standard transferability arguments (e.g., Ruiz et al. (2023); Levie (2023); Le & Jegelka (2023) do not generalize. This stems from k-WI. (Böker, 2023), so many k- WL expressive models graphons would have the same limitations. Yet, show that this discontinuity can be overcome in the sense that higher-order GNNs are still transferable.
One potential direction for future research could be derive general, explicit, and tight bounds for Theorem 5.2, beyond the restricted setting of Theorem 5.4. Furthermore, one could analyze expressive spectral methods (Lim et al., 2023b;a; Huang al., 2024). More broadly, future work could consider sparse graph limits (Le & Jegelka, 2023; Ruiz et al., 2024) or inductive biases through training, data distribution, or the specifie task.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The authors would like thank Thien Le, Manish Krishan Lal, Dominik Fuchsgruber, and Levi Rauchwerger for insightful discussions at various stages of this work, and Andreas Bergmeister and Eduardo Santos Escriche for careful proofreading. This research was funded by an Alexander von Humboldt professorship.
REPRODUCIBILITY STATEMENT
We provide rigorous proofs of all our statements in the appendix, along with detailed explanations and the underlying assumptions. A comprehensive overview of our notation is listed in A. Details for the toy experiment are provided in H.
REFERENCES
Romain Abraham, Sean-Françeue Delmas, and Julien Weibel. sibbbbilitygrrphhn. Limits of large dense weighted graphs, December 2023. arXiv:2312.1599 [cs].
Waiss Azizian and Marc Lelarge. Expressive Power of Invariant and Equivariant Graph Neural Networks. In The Ninth International Conference on Learning Representations (ICLR), 2021.
Ágnes Backhausz and Balázs Szegedy. Action convergence of operators and graphs. Canadian Journal of Mathematics, 74(1):72-121, February 2022.
Jan Böker. Weisfeiler-Leman Indistinguishability of Graphons. The Electronic Journal of Combi- natorics, 30(4):P4.35, December 2023.
Jan Böker, Ron Levie, Ningyuan Huang, Soledad Villar, and Christopher Morri.. Fine-grained Expressivity of Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pp. 46658 46700, 2023.
Chen Cai and Yusu Wang. Convergence of Invariant Graph Networks. In Proceedings of the 39th International Conference on Machine Learning (ICML), pp. 2457-2484. PMLR, 2022.
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, December 1992.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 10383-10395, 2020.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász Meets Weisfeiler and Leman. loannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella (eds.), 45th Interna- tional Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings Informatics (LIPIcs), pp. 40:1-40:14 Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2018.
Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 2017.
Zdeněk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 2010.
Jürgen Elstrodt. Maß- und Integrationstheorie. Springer, 2018.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph Neural Networks for Social Recommendation. In The World Wide Web Conference, WWW '19, pp. 417-426, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. Proceedings of the 34th International Conference Machine Learning (ICMI), pp. 1263-1272, PMLR, 2017.

---

Published as a conference paper at ICLR 2025
Jan Grebík and Israel Rocha. Fractional Isomorphism of Graphons. Combinatorica, 42(3):365 404, June 2022.
Martin Grohe and Martin Otto. Pebble Games and Linear Equations. The Journal of Symbolic Logic, 8033)797-844, 2015.
Cheryl Grood, The rook partition algebra. Journal of Combinatorial Theory, Series A, 113(2): 325-351, February 2006.
Jerzy Grunwald and Grzegorz Serafin. Explicit bounds for Bell numbers and their ratios. Journal of Mathematical Analysis and Applications, (49(2))129522) September 2025.
Tom Halverson and Theodore N. Jacobson. Set-partition tableaux and representations of diagram algebras. Algebraic Combinatorics, 3(2):509-533) 2020.
Ningyuan Huang and Soledad Villar. A Short Tutorial on The Weisfeiler-Lehman Test And Vari- ants. In IEEE International Conference on Acouslics, Speech and Signal Processing (ICASSP), 2021.
pp.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the Stability of Expressive Positional Encodings for Graphs. In The Twelfth International Conference on Learning Representations (ICLR), 2024.
Svante Janson. Graphons, cut norm and distance, couplings and rearrangements. NYJM Mono- graphs, (4), 2013. arXiv:1009.253: 2376 [math].
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. In The Interna- fional Congress of Mathematicions, 2022.
Emily Jin, Michael M. Bronstein, Ismail Ilkan Ceylan, and Matthias Lanzinger. Homomorphism Counts for Graph Neural Networks: All About That Basis. In Proceedings of the 41st Interna- tional Conference on Machine Learning (ICML), pp. 22075-22098. PMLR, 2024.
Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and stability of graph convolu- tional networks on large random graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 21512-21523, 2020.
Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. On the Universality of Graph Neural Networks on Large Random Graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pp. 6960-6971, 2021.
Thomas N. Kipf and Max Welling. Superviie Classification with Graph Convolutional Net- works. In The Fifth International Conference Learning Representations (ICLR), 2017.
Ton Kloks. Treewidth: 1994.
Computations and Approximations. In Springer Science & Business Media,
Olga Klopp and Nicolas Verzelen. Optimal graphon estimation in cut distance. Probability Theory and Related Fields, 174(3): 1033- August 2019.
Donald F. Knuth. The art of computer programming, volume (3rd ed.): fundamental algorithms. Addison Wesley Longman Publishing Co., Inc., USA, 1997.
Remi Lam, Alvaro Sanchez-Gonzan Gonzalez, Matthew Willson, Peter Wirnsberger, Meire Fortunato, Fer- ran Alet, Suman Ravuri, Timo Ewalds, Zach Eaton-Rosen, Weihua Hu, Alexander Merose, Stephan Hoyer, George Holland, Oriol Vinyals, Jacklynn Stott, Alexander Pritzel, Shakir Mo- hamed, and Peter Battaglia. GraphCast: Learning skillful medium-range global weather forecast- ing. Science, August 2023.
Misha Lavrov. Expected graph edit distance between two random graphs, 2023. URL https: // /mathh stackexchange, com/ ////////// 4824292 (versi 2023-12222222
12

---

Published as a conference paper at ICLR 2025
Thien Le and Stefanie Jegelka. Limits, approximation and size transferability for GNNs sparse graphs via graphops. In Advances in Neural Information Processing Systems (NeurIPS), vol- ume 36, pp. 41305-41342 2023.
Ron Levie. A graphon-signn analysis of graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, pp. 14482-64525, 2023.
Ron Levie, Wei Huang, Lorenzo Bucci, Michael M. Bronstein, and Gitta Kutyniok. Transferability of Specttal Graph Convolutional Neural Networks. Journal of Machine Learning Research, (22): 1-59, June 2021.
Derek Lim, Joshua Robinson, Stefanie Jegelka, and Haggai Maron. Expressive Sign Equivariant Networks for Spectral Geometric Learning. In Advances in Neural Information Processing Sys- tems (NeurIPS), volume 36, pp. 16426-16455, 2023a.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning- In The Eleventh International Conference on Learning Representations (ICLR), 2023b.
László Lovász. Large Networks and Graph Limits. American Mathematical Soc., 2012. ISBN 978-0-8218-9085-1.
László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933-95) November 2006.
Takanori Machara and Hoang NT. A Simple Proof of the Universality of Invariann/Equiivaran Graph Neural Networks, October 2019. arXiv:1910.03802 [cs].
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In The Seventh International Conference Learning Representations (ICLR), 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 4363-4371. PMLR, 2019c.
Sohir Maskey, Gitta Kutyniok, and Ron Levie. Generalization Bounds for Message Passing Net- works on Mixture of Graphons. SIAM Journal on Mathematics of Data Science (SIMODS), April 2024.
Amil Merchant, Simon Batzner, Samuel S. Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for materials discovery. Nature, 624(7990):80-88) December 2023.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019.
Hoang Nguyen and Takanori Maehara. Graph Homomorphism Convolution. In Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 7306-7316. PMLR, 2020.
Sewoong Oh, Soumik Pal, Raghav Somani, and Raghavendra Tripathi. Gradient Flows on Graphons: Existence, Convergence, Continuity Equations. Journal of Theoretical Probability. 37(2):1469- 1522, June 2024.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 8: 143-195, January 1999. ISSN 1474-0508, 0962-4929.
Levi Rauchwerger and Ron Levie. A Note on Graphon-Signal Analysis of Graph Neural Networks. arXiv preprint, 2025.
13

---

Published as a conference paper at ICLR 2025
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon Neural Networks and the Transfer- ability of Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 1702-1712, 2020.
Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Graphon Signal Processing. IEEE Trans- actions on Signal Processing, 69:4961-4976, 2021a.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Graph Neural Networks: Architectures, Sta- bility and Transferability. Proceedings of the IEEE, 109(5);660-66) 682, 2021b.
Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Transfcrability Properties of Graph Neural Networks. IEEE Transactions on Signal Processing, 71:3474-3489 2023.
Luana Ruiz, Ningyuan Teresa Huang, and Soledad Villar. A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 9936-9940, 2024.
Konrad Schmüdgen. The Moment Problem, volume 277 of Graduate Texts in Mathematics. Springer International Publishing, Cham, 2017.
Barry Simon. Real Analysis. American Mathematical Soc., November 2015. ISBN 978- 978-1-4704- 1099-5.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The Power of Recursion in Graph Neural Networks for Counting Substructures. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1102--11042. PMLR, April 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In The Sixth International Conference on Learning Repre- sentations (ICLR), 2018.
Eric W. Weisstein. Bell Number. URL https://mathworldd: wol fram, com/
Bell Nelbeu html. Wolfram Research, Inc.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In The Seventh International Conference on Learning Representations (ICLR), 2019.
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks. In The Ninth International Conference on Learning Representations (ICLR), 2021.
Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From Local Struc- tures to Size Generalization in Graph Neural Networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 11975-11988 PMLR, 2021.
Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond Weisfeiler- Lehman: A Quantitative Framework for GNN Expressiveness. In The Twelfth International Con- ference on Learning Representations (ICLR), 2024.
Yufei Zhao. Graph Theory and Additive Combinatories: Exploring Structure and Randomness. Cambridge University Press, 2023. ISBN 978-1-00-9931994-9
14

---

Published as a conference paper at ICLR 2025
APPENDICES
A Notation
16
Extended Background
18
B.1
Topology and Measure Theory
18
B.2
Characterization of the IGN Basis
20
B.3
IGN-small (Cai & Wang, 2022)
20
B.4 Tree Decomposition and Treewidth
21
B.5 Sraphon-Signal Space (Levie, 2023)
21
Signal-Weighted Homomorphism Densities
23
C.1 A Counting Lemma for Graphon-Signals..
23
C.2 Smooth and Invariant Norms for Graphon 
24
C33 Proof of Theorem 3.2
25
C,4 Proof of Corollary 3.3
26
k- for Graphon-Signals
28
D.1
Tri-Labeled Graphs and Graphon-Signal Operators
28
D.2
Weisfeiler-Leman Measures
................................
D.3
Color Refinement for Graphon-Signals
32
Invariant Graphon Networks
33
E.1
Proof of Theorem 4.2
E.2
Continuity of Linear Equivariant Layers
................................
35
E.3 Asymptotic Dimension of Linear Equivariant Layers
................................
E,4
Proof of Proposition 4.4
................................
E.5
Proof of Lemma 4.5
................................
37
E.6
Proof of Theorem 4.6
................................
E.7 Proof of Corollary 4.7
................................
E.8
Proof of Corollary 4.8
42
Refinement-Bars Graphon Neural Networks and &-WL
43
F.1 Definition of Graphon Neural Networks
43
F.2
Formulation on W- Measures
43
G Cut Distance and Transferability of Higher-Order WNNs
46
G.1 Proof of Proposition 5.1
................................
46
G.2 Proof of Theorem 5.2
46
G.3 Proof of Corollary 5.3
47
G.4 Quantitative Transferability Results
47
G.5 Additional Remarks
50
H Experiment Details
52
H.I Setup
52
H.2 Pseudocode of Models
53
15

---

Published as a conference paper at ICLR 2025
A
NOTATION
Table 1: We list the most important symbols used in this work.
N: No: Q: IR
Natural, non-negative integer, rational, real numbers. Set (1,..., n for n. E N.
m
IA
Indicator function in set A.
(.)
Explicit list of elements in set.
Explicit list of elements Empty set and empty tuple.
multiset.
V(G); v()
Node set graph; number of nodes of graph G.
E(G); (G)
Edge (multi)set of (multi)graph; number of edges of a (multi)graph G.
deg(u)
Degree of node u graph.
0()
"Big-O" notation for asymptotic growth of function. "Little-o" notation, indicating that one function is dominated by another. Generic variable for neural network (MLP or GNN).
o()
N
Generic variable for a function class of neural networks.
(F(F)
Treewidth of a (multi)graph F.
Nom(F,C G)
Number of homomorphisms from graph F to G. Closure of a subset of a topological space X' Borel r-algebra of topological space X.
B(X)
o()
Generated alalebbra.
Probability measure.
Expected value.
x
I-dimensional Lebesgue measure; k-dimensional Lebesgue measure. Space of p-integrable functions measure space X', for oo).
TP(())
(2)
Space of p-integrable functions, with norm bounded by r.
In
Cut norm.
I|,1,
L norm of functions on a measure space, for E [1, oo].
L norm, with emphasis on the underlying measure space X..
Lipschitz norm of continuous function on a metric space. Space of bounded linear operators from normed vector space V1 V22 Operator norm of T Space of continuous functions from compact topological space K into F. with uniform norm ||-I|--
C(V1, 12)
ITTI
(Q))).
C(K)
C&(K)
Space of bounded continuous functions from topological space K into R. with uniform norm ||=
W
Space of kernels.
Wo
Space of graphons.
WS,
Space of graphon-signals Wo x [0, 1].
Wo
Space of unlabeled graphons.
WS,
Space of unlabeled graphon-signals.
Tw
Shift operator of graphon W.
Sjo.)
Measure preserving (almost) bijections [0, 1].
5x
Measure preserving functions - X', for measure space X' Cut distance.
6p
(Unlabeled) LP distance for graphons/kernels. (Unlabeled) distance w.r.t. smooth invariant norms N NN).
"
Weak convergence of probability measures.
f.p
Pushforward of measure y under f.
We
Step graphon of a graph G.
H&(W); (W,
Distribution of weighted graphs/graph-signals of size it sampled from graphon W/g W/graphon-sieee Distribution of unweighted graphhlgraph-siinnals of size k sampled from graphon W/graphon-sigee
(W. f).
G&(W); GW(,.J)
(W
U(O,1)
Uniform distribution on the interval [0, 1].
((FW)) W)
Homomorphism density from (multigrraph F' into graphon W.
16

---

Published as a conference paper at ICLR 2025
((F,d), (W,
Siinal-weighted homomorphism density from (multi)graph F, d E Ng(F), into graphon-signal (W, f).
F a, b,d)
Tri-labeled graph.
MR.e
Set of all tri-labeled graphs with k input, & output vertices. Composition of tri-labeled graphs.
F o
F2
F F2
Schur product of tri-labeled graphs.
FR
Set of atomic tri-labeled graphs.
(F)
Set of F-terms.
[F]
Evaluation of a term IF E (F))
h(F)
Height of term F.
TF (W.(W.f)
Graphon-signa operator associated with tri-labeled graph F. Space of k-WL colors up to step 8.
M
M
Space of k-WL colors,
Prssi Poo-
Canonical projections M; + M M + M...
pk
Space of k-WL refinements.
FP
Realizing functions on M of term F.
Realizing function on P a term F.
(s))..(s)
k-WL measure of (W, f) WS,.
(W.
&AWL
k-WL distribution of (W; f) WS,.
(WC) ()
LE
Linear equivariant layers measure space X. Linear equivariant layers on [0, 1].
LE
F
Regular step functions in I.2 [0, 1] resolution
T
Set of partitions of [m]. m E Ny-
bell(m
[m |, i.c., number of partitions of [m]] Set of partitions of [k: that index basis of LE
TR.6
T
Linear operator w.r.t. E T
17

---

Published as a conference paper at ICLR 2025
B EXTENDED BACKGROUND
B.1 TOPOLOGY AND MEASURE THEORY
We briefly recall fundamental definitions and results from topology, measure theory, and the theory of measures on Polish spaces that are used in this work. See, for example, Simon (2015) or Elstrodt (2018) for comprehensive primers.
B.1.1 TOPOLOGY
A topologiaal space is a pair (Z, O), where is a set and the topology O C 2 is a collection satisfying that X, Ø E O, User E O for any family {U. of Of E O, and U₁ n- n Un E O for any Ui...., Un E O. Le., a topology is closed under arbitrary unions and finite intersections. A set U E O is called open, and set A 2x is closed if its complement AA= : X' \ A is open. The closure A of set A S X' is the smallest closed set containing A. A subset A C X is dense if its closure A = X. A topoloiiall space is separable it has a countable dense subset. A neighborhood of x E X is set A E X such that there is an open set U with U A. If the topology is clear from context, it is often left implicit.
A metric space is pair (X,d) d) with metric d: X x X [0, o0) satisfying positive definite- ness d(x,, y) = 0 iff æ y, symmetry d(x, y) d(y, x), and the triangle inequality d(a, S d(xr; y) + d(y, (here, I,, v. E X). A pseudometric is a function d that satisfies all of the previ- ous requirements except positive definiteness. A metric d on X' induces a topology by choosing the coarsest topology on X' under which all balls (z) == {y E X' X(d(z, y) < $} for x E X, & > O, are open. A topological space is metrizable if its topology can be induced by metric. A topological space Hausdorff if for any two points x * y there exists a pair of disjoint neighborhoods. Metric spaces are trivially Hausdorff by positive definiteness. A metric space is complete if every Cauchy sequence it converges to a point in the space. Note that this is a property of the metric itself and not of the induced topology. Spaces like R or R" are typically considered with their standard topology, i.e. the one induced by the Euclidean norm/distance (which is the same for all norms).
A function f: X + Y' between topological spaces (X, Ox) and (V, Oy) is continuous if for every open set E Oy. one has f (V) E Ox. For metric spaces with their induced topology, this is equivalent to the standard definitions of continuity (via 6-8 or sequences).
An open cover of a topological space X' is a family of open sets whose union is all of X. A topo- logical space X' is compact if every open cover of X' has finite subcover, in metric spaces this is equivalent to every sequence in A' having a convergent subsequence.
The product topology on IL.z X, is the coarsest topology making all projections py: Ihe X, X, continuous, and if A C X,, the subspace topology on A is IU n A A open in X). The con- vergence a sequence in a topological product space is equivalent to convergence components, i.e., images under the projections p.. A subset A C X' is relatively compact if its closure is compact. By the Heine-Borel theorem, subsets of IR"" are compact iff they are closed and bounded (in any norm).
all of its
A closed subset of a compact space is compact w.r.t. the subspace topology. The converse also holds if the space is Hausdorff. Tychonoff's theorem states that any product IL, X, of compact topo- logical spaces is again compact (regardless of the cardinality of I). A topological space is normal if any two disjoint closed subsets have disjoint open neighborhoods (i.e., open sets containing them). Every metrizable space is normal. The Tietze extension theorem states that if X' is normal and A C X' is closed, then any continuous function f: A E can be extended continuous function F: X + IR.
Let K be a compact Hausdorff space. Write C(K, R) for the space of all continuous functions on K (which are all bounded), equipped with the topology of uniform convergence, i.e., I1-1lso- With pointwise addition and multiplication, this space becomes algebra. The theorem states that if A C C(K, R) is a subalgebra that separates points in K and contains the constant functions, then A is dense in C(K, RR).
18

---

Published as a conference paper at ICLR 2025
B.1.2 MEASURE THEORY
A measurable space (X, is a pair where X' is an underlying set, and A C 2* is o-algebra, which fulfills Ø E A, and stable under complements as well as countable unions. Note that this also implies stability under countable intersections. A measure space (K,A, μ) is tuple, where (A) is measurable space and j is a measure, i.e., function from A to [0. oo] which satisfies n=(2)= = O, and o-additivity U(UneN A,) Enen H (A)))) ) for any disjoint {An)n S A. If the o-algebra and/or measure is clear from context, we omit it. For any g C X. define its generated o-algebra (G) as the smallest o-algebra containing G (this is well-defined as is simply the intersection of all g-algebras containing 9). A property of X holds almost everywhere (a.e.)
the set N E A which this property does not hold is null set, Le., ((N) 0. A probability space AA, is a measure space with P(X)= = 1.
The Borel o-algebra B(x)) a topological space X' is the o-algebra generated by its open sets. Any continuous function on such a space is also measurable. The Lebesgue measure À on IR the unique measure on ((R) assigning intervals its length. Analogously, A on B(R²) is the unique measure assigning n--dimensional cuboids to its volume. These assignments determine the Lebesgue measure uniquely under translation invariance and regularity conditions. Often, the Lebesgue measure is considered on the Lebesgue o-algebra, which is the completion of the Borel o-algebra, containing all subsets of null sets. For this work, the distinction between both is not important, and we will work just with Borel sets. The counting measure on a set X' is defined by mapping each subsets to its cardinality. Similarly to topologies, we can define subspace and product o-algebras.
between two measurable spaces is measurable if (A) E Ax for every A E Ay. The Lebesgue integral of a measurable function f: (X' A. + (R, B(R)) is denoted by fx f dj,, and is defined via taking a.e. limits of indicator and step functions.
A function f: Ax)
linear operator T: (V, I|-llv) + (W, I:llw) between two normed spaces is bounded iff T is continuous w.r.t their induced metrics, which is equivalent to [[T|lv- == supl-l|ly= [Tullw < 0o. For measure space (X,A, (4) and < < oo, its L space is defined as (P(X) (s: X R| f is measurable, |lp = (fx [S| d/ < oo). (x)) is defined via the essential supremum, || ess f == MM 2 0l [f()) s M a.e.}. Functions that agree a.e. are identified.
In L" spaces, the following inequalities hold: Minkowski's inequality states that |lf+ - 1If [|allp- Jensen's 's inequality states that in probability space X' and for a convex function 6: R - I,
$ (fx f du) S Sx f(f) dp. Hölder's inequality states that for dual coefficients p, 4 E [1, oo] with 1/p + 1/q- = 1, we have fx Ifal du S l|llll
If f X + +Y is measurable and p is a measure on X. the pushforward measure fap on y is defined by f.m(A) = ((f for all measurable A C Y. If g y - R is measurable, then fygdf-u - [x go du holds for the Lebesgue integral. A measure preserving function between two measure spaces (X',)) and ()²,) v) is measurable function & X + ) such that P.,j v. Two measure spaces X' and y are isomorphic if there exists a measure preserving bijection between them whose inverse is also measure preserving. The spaces are almost isomorphic if the former holds for some subsets of full measure of X,
1.1 MEASURES ON POLISH SPACES
A Polish space X' is a topological space that is separable and completely metrizable, meaning that its topology is induced by metric d w.r.t. which (X, is complete. We typically consider a Polish space with its Borel alagebrr.. A standard Borel probability space is probability space defined on the Borel olalgebra of Polish space. Notably, by the isomorphism theorem, every nonatomic standard Borel probability space (meaning there are no points of positive measure) is almost isomorphic to the unit interval ((0, 1), [(0, 1]); A). By renormalization, similar result holds for all finite measures.
Let P(x') be the set of all Borel probability measures on a Polish space X. We equip this set with a topology as well: The weak topology of P(x') is the coarsest topology making all the maps y + fxx du continuous, where f E Co(2²) is considered over the bounded continuous functions
19

---

Published as a conference paper at ICLR 2025
on X. This corresponds to the weak- on the dual Cs(x)", (((X)),iie i..., bounded linear functionals on (Z)( ol A sequence (Ja), of probability measures on X' is said to converge weakly to (denoted He, 4 pt) if fx dun, + fx f du for every f E C,()).
The Portmanteau theorem gives several equivalent formulations of weak convergence (for exam- ple, convergence of the measures evaluated on continuity sets, or convergence of the integrals only for a dense subset of (x)). On X R. this precisely convergence of random variables in distribution. Notably, if X' is Polish, then so is P(2). and if X' is metrizable and compact, this also carries over to (()).
By Prokhorov's theorem, family of probability measures Polish space X' is relatively com- pact (with respect to the weak topology) iff is tight, meaning that the total probability mass can be approximated arbitrarily well by compact subsets Kg S X uniformly on the family of measures.
B.2 CHARACTERIZATION OF THE IGN BASIS
We restate the characterization of the IGN basis introduced by Cai & Wang (2022). As described bell(k: + E), i.e., the number of partitions Ta+e of the set [k + E). In the basis of Cai & Wang (2022), each basis element L (n) associated with partition
by Maron al. (2019b), dim LE
? E TK+e can characterized as a sequence of basic operations.
Given 7 E Tk+e, divide into 3 subsets == {A E 7 A S [b]]. 72 = (A [{], 73 := > (7)) Here, the numbers 1, ...... lt are associated with the input axes and k+ ............ k+b with the output axes respectively.
(Selection: H + H,). In first step, we specify which part of the input tensor H E R is under consideration. Take 7 == ( n [k:] A E 7, A n [M]] # Ø0 and construct a new Imn + ha/ = 11 | ttessor H., by selecting the diagonal of the k-tensor H corresponding with the partition 7 7118-
(Reduction: H,, + rear We average H., over the axes 71 S Salpp resulting in a tensor
Hed of order hnsl, indexed by 73 [4]]
(Alignment: Herred + a,,giig.). We align H.rred with I7a Italstessor alggi indexed by Palk+ter sending for A 73 the axis A n [B:] to A n [4]
(Replication: Hagalggn + rpp) Replicate the has Itel-tensor Hlyali indexed by 73 [+[[]] along the axes in 72. Note that if 1a/x+te U12 contains non-singleton sets, the output tensor is supported on some diagonal.
Aggregations in this procedure can either be normalized (as described here) or simple sums. The basis element T.()) R=* Rn can now be described by the assignment T:(") ( (H) == H yepp and
LE k = span (m 7 M r
(19)
B.3 IGN-SMALL (CAT& & WANG, 2022)
Cai Wang (2022) study the convergence of discrete IGNs applied to graphs sampled from a graphon continuous version of the IGN defined graphons. For this, they use the full IGN basis and a partition norm, which is for U E [ 1]ah a deimek))di vector consisting of L norms of U on all possible diagonals. While they show that convergence of discrete IGN on weighted graphs sampled from graphon to its continuous counterpart holds, they also demonstrate that this is not the case for unweighted graphs with {0, 1 -valued adjacency matrix.
As a remedy. Cai & Wang (2022) constrain the IGN space to IGN-small, which consists of IGNs for which applying the discrete version grid-sampled step graphon yields the same output as applying the continuous version and grid-sampling afterwards. In the following definition, we will formalize this. Here, F(()) denotes the regular k-dimensional step kernels [0, 1). t No-
20

---

Published as a conference paper at ICLR 2025
Definition B.1 small (Cai & Wang, 2022)). Let N be defined as in Definition 4.3, with the only difference that LE is replaced by the full IGN basis, where averaging steps should be understood integration. Cai & Wang (2022) call such N a continuous IGN. For any basis element T., Y E Tk+6. denote its discrete version at resolution n E N by T and the network obtained by discretizing all equivariant linear layers by N(6), Let
s(m) R10.11 xd + Rnnxxd U (U(i/n.j/m)).
(20)
be the srapllan operator. Then, N is contained in IGN-small if (8(m) (W,, = (A1)) o St.)
(21)
for any (W, E WS, such that W E Fl f F("). In this case, the input to such an IGN is [(x, v) + (W (z, v). f()))
Cai & Wang (2022) show that convergence of IGN-small can be achieved in model where a {0, 1)- valued adjacency matrix is sampled from the graphon, provided that certain assumptions on the graphon and the signal-such as Lipschitz continuity- satisfied (see Theorem 4). It is important to note, however, that assuming the graphon is contin- uous is a rather strong condition, as it implies a topological structure on the node set corresponding to the unit interval. In contrast, similarly to Levie (2023), treat [0, 1] solely as a measure space, which, being almost isomorphic to any nonatomic standard Borel probability space, is much more general. Regarding the expressivity of IGN-small,, Cai & Wang (2022) establish that this model class can approximate spectral GNNs with arbitrary precision (cf. Theorem 5).
a prior estimation of an edge probability
B.4 TREE DECOMPOSITION AND TREEWIDTHI
In this section, we will recall the tree decomposition of graph and the related notion of treewidth, which essentially captures how "far" a graph is from being a tree. See for example Diestel (2017, 12.3) for a more in-depth discussion of this fundamental graph theoretic concept. We use the specific notation of Böker (2023).
Definition B.2 (Tree Decomposition of a Graph). Let G be a graph. tree decomposition of G is a pair (T, 3). where T a tree and 3 VT) + 2V such that
(1) for every v E (G),, the set {t | E 3(t) is nonempty and connected T, (2) for every e E(G), there is node t (T) such that C Bt)).
For L E V(T), the sets B(I) C V(G) are commonly referred to as bags of the tree decomposition. Note that every graph G has a trivial tree decomposition, given by a tree consisting of one node, with the bag being the entire node set (GG). However, we generally interested in finding tree decompositions with smaller bags. This leads us to the concept of treewidth:
Definition B.3 (Treewidth of Graph). Let G be graph. For any tree decomposition (T, G. define its width
max ((x())(t) |t V(T)- 11
(22)
The treewidth of graph G is then the minimum width of all tree decompositions of G.
Note that, the edge graph of tree G can be seen as a tree decomposition of G, with each edge being bag. Hence, the treewidth of a tree is 1. It can also be shown that, e.g., the treewidth of circle of size at least 3 is 2. The definition can be extended to multigraphs by simply ignoring the edge multiplicities, i.e., considering the set of edges instead of the multiset.
B.5 GRAPHION-SIGNAL SPACE (LEVIE, 2023)
Without reintroducing the graphon-signal space (see $ 2.3 for the basic definitions), we formally restate two of the main results of Levie (2023) relevant this work. Central to their contribution, space and provides a bound on its covering
Levie (2023) proves compactness of the graphon- number. Note that something similar does not hold for any of the 6, distances.
21

---

Published as a conference paper at ICLR 2025
Theorem B.4 (Levie (2023), Theorem 3.6). The space (WS,, 6-i) is compact. Moreover, given r > and c > 1, for every sufficiently small ε > 0, the space can be covered by 2 balls of radius d6
where k = [
The proof follows an approach analogous to that used for establishing the compactness the space of unlabeled graphons and relies graphon-signal adaptation of the weak regularity lemma (Levie, 2023, Theorem B.6). The graphon-signal weak regularity lemma can also be used to de- rive sampling lemma:
Theorem B.5 (Levie (2023), Theorem 3.7). Let > 1. There exists constant No > O depending on r, such that for every n No and (W, E &S,, we have
15
E [6n f). G. fW)
(23)
Vlog n
Although the above results were obtained for one mne-dimensionl signals, they readily extend to d- dimensional signals taking values in compact sets K R² (say, hypercube [-r,r] based on multidimensional version of the signal cut norm normalized by d (see also Rauchwerger & Levie (2025)). this case, the exact statements of Theorem B.4 and Theorem B.5 can recovered. By norm equivalence, qualitative statements of the theorems remain valid when using the T,¹ norm I| as signal norm. The same reasoning extends to any L norm defined from a vector norm ||-||R: that is, if one sets
|I :- S
[f(z)ll=dd(()
(24)
[0.1]
as well as to other LP norms of f: If for all signals f. x + (x) is uniformly bounded by on [0, 1]. then
f |0.11 (
1/2 (1on (1(0)))))())))
rlo-1)/D (1 (1F(o)lld
1/p
11
(25)
where we used Jensen's inequality for the first part.
22

---

Published as a conference paper at ICLR 2025
C SIGNAL-WEIGHTN HOMOMORPHISM DENSITIES
C.I. A COUNTING LEMMA FOR TRAPHON-SIGNALE
We derive counting lemma similar the standard graphon case (Lovász, 2012, Lemma 10.23),
which shows that signal-weighen homomorphism densities from simple graphs into a graphon- signal are Lipschitz continuous w.r.t. distance.
Proposition C.1 (Counting lemma for graphon-signals). Let (W, E WS, and F be simple graph, d E No(P) Then, writing D == Diev(ry de
[((EE, d), (W) ((F,)) (V.9)) < P-1 2r e(F)
Vlla + +DI sala). (26)
As ((FF, .). -) is clearly invariant w.r.t. measure preserving functions acting on the graphon-signal, the bound of (26) can be easily extended to d The proof is relatively straightforward, with only detail requiring little extra consideration being that the signals take negative values and interact with the graphon. A similar statement can be shown for all multigraphs F using II-
Proof. We split the L.hss., bounding the difference of the graphons and the signals separately: d),
|((F, d), f)) (V, I
(27)
II fax))a
II (1.)EE(()
II (LF)EE(P)
(28)
(EV(F)
II V(n,,,))
II f(x.) IEV(F)
II g(x,) " dx*(x))
(29)
((L))E((P)
iEV(F)
For term D we set D D==E: E, di and observe that for all E [0,
II (1x) E [-1,1
(30)
DD
iEV(F)
and hence similarly to the proof of the classical counting lemma (see, e.g., Zhao (2023)) bound Vlln S Ar"e(F) IIW Vlln.
1 5 Pe(F)
I
(31)
In comparison to the standard proof, the usage |1-I|m, an alternative definition of the cut norm, stems from the fact that function values appearing in the integral in ① (renormalizing by rD)) are not necessarily in [0. 1], but [-,, See also equations (4.3), (4.4) in Janson (2013). For ② we bound the L difference of the terms involving ʃ and g:
II V(I (1.)EE(P)
II f(z,) - II 9 d)*(z)) (EV(F)
(32)
LEV(F)
StOrF 0.11
II ((n))
II ((x))d
II g(a))d dx*
(33)
(A.)ER(()
(EV(F)
SEV(P)
Σ
[((.)a g(z:)4.
II f(zz)4 I d2
(34)
10.11=
(EV(F)
jai
Σ Eszch dh /
-f(=:)) d)(x)
(35)
10.11
(FV(P)
Σ Es 11 11f-lgll ggll D-1 -1l1 S D-I |lf gllo
(36)
(EV(F)
23

---

Published as a conference paper at ICLR 2025
where (*) uses olf - and hence the Lipschitz constant of x: H 2: is bounded by the
maximum of its derivative d -1 and the last inequality uses 11-111 I 2 Il-11a in one dimension.
Combining the two bounds for 1 from (31) and 2 from (36), we obtain
|t((F, d), (W,f)) t(( d), (V.9)) < 4r e(F) IW Vlla + 2- allo. (37)
which yields the claim.
C.2 SMOOTH AND INVARIANT NORMS FOR GRAPHON-SIGNALS.
In this work, we consider not only the cut norm, but also L norms (and distances) of graphon- signals. The purpose of this section to show that all the derived unlabeled distances we consider on the graphon-signa space yield the same notion of weak isomorphism, i.e., vanish simultaneously. This can be shown for smooth invariant norms on the graphon-signa space (cf. Lovász (2012, 8.2.5)):
Definition C.2 (Smooth and invariant norms). Two norms N = (N1, where N1 is a norm on - [0, and N2 on W, are called smooth if the two conditions
(1) Wr + W. fo + f 10 1] almost everywhere, (2) suPneN Ww S oo, suPnEN 11 S 00,
10,
imply that
Ni(A)) + NiO, N2(W,) N2(W).
(38)
They are invariant if
N1(ft)= Ni(f), N2(W") N2W) Vp S
(39)
where (W, E W - 1] and f*(x) f(p(=)) for E (0, 1]. We may sometimes also write (W, f) = f%)
The conditions clearly apply II-Ilo and 1| for p o0) (acting either N1 and N2), but do not hold for p = oo (take for example W, = 10.]////2 fr. = 10.1nn) For any smooth and invariant N, we can obtain derived unlabeled distance as done for the cut distance:
Definition C.3 (Derived unlabeled distance). Let N (N1, N2) be smooth and invariant norms. Define its derived unlabeled distance on the graphon-signal space as
S).
inf (N2 V*) Ni -g)). (ES
(40)
Just in the standard graphon case, for all such smooth and invariant norms, the infimum in (40) is attained when minimizing over all measure preserving functions. This turns out to generaliza- tion of Lovász (2012, Theorem 8.13):
Theorem C.4 (Minima vs. infima for smooth invariant norms). Let N be smooth invariant norm on W and 1 [o, 1). Then, we have the following alternate expressions for dn:
8 ((W,)) (V.
inf (N2(W- - -V9) + +Ni(f 9)
(41)
sESpal
min (N2(WV- vo) N 9))
(42)
Sketch of proof. We follow the proof of Theorem 8.13 by Lovász (2012), briefly highlighting the necessary adjustments to the argument. To establish the first equality, approximations by step graphons that converge a.e. are considered, and the crucial point is that any & E S can be realized by a suitable 인 E Spo.1) for such step graphons. For graphon-signals, the argument can be transferred if one simply considers partitions respecting each step graphon and step signal simulta- neously when constructing the corresponding ş E S p),,1)- For the second equality, which proven in greater generality with coupling measures over [0, 1] by Lovász (2012), note that the lower semi- continuity in (8.24) is just shown for kernels (i.e., - [0, 1)2), but the argument extends verbatim to L [0, 1), and the sum of two lower semicontinuous functions still lower semicontinuous. The rest of the argument applies without modification.
24

---

Published as a conference paper at ICLR 2025
Note that our definition of åي coincides with the one by Levie (2023), they also considered measure preserving bijections co-null sets in [0, 1] (writing So.1j for this set). As an immediate corollary, we can obtain a simple characterization weak isomorphism for graphon-signals:
Corollary C.5 (Weak isomorphism). Two graphon-signals (W, (),), (V.g) E WS, are weakly iso- morphic, i.e., 5v ((W, f); (V) for any smooth and invariant norm N N2), if and only if there are yp, v 10 such that W v and f g almost surely.
Here, Theorem C.4 ensures that this does not depend the specific N. Similar to standard graphons, we identify weakly isomorphic graphon-signals to obtain the space of unlabeled graphon- signals WS,. We mainly work with the cut distance d as well as the Le distances 6p for p E [1, oo) (where we choose N = (II-Ipp- ps Il-llp)). Among these, of special interest are typically ô1 this cor- responds to the edit distance on graphs, as well as 8g, which gives rise to geodesic space in the standard graphon case (Oh et al., 2024).
C.3 PROOF OF THEOREM 3.2
Theorem 3.2 (Characterizations of weak isomorphism for graphon- graphon-signals) signals). Fix 1 and let fW, (V, E WS,. Then, the following statements are equivalent:
(1) (,,((.)). (V.g) 0 for any p [1):
(2) (VW)). = 0;
(3) (((F,d),
t((F, d), (V,g)) for all multigraphs F, d No(r)
(4) ((F,,),(W; = (((F, d), (V,g)) for all simple graphs F, E (p)
(5) f), 2 (V.g)) all k E N;
(6) f)( 2 Gv g) for all k E N.
The following elementary lemma will be useful several occasions when comparing probabil- ity distributions.
Lemma C.6 (Moments of Random Vectors). Let m E N and let X Y be m- m-dimennional random vectors which almost surely bounded, iee. there is some R O such that X| & R)
P(I & R) = 1, for any norm [|-]| on Th. Suppose that for all d E No the moments of X, Y agree:
E
x
E
(43)
Then, X and Y are identically distributed, i.e.,
X Y.
Proof. In the case of more general random variables/vectors. this is known in the literature as the moment problem (see, e.g., Schmüdgen (2017)). Under boundedness, however, this trivial and can for example be proven via the characteristic functions of the random vectors.
We are now ready to prove Theorem 3.2, To this end, we will show the implications in Figure 4.
(3) [t(F, d, )r multignph same
(4) (t(F, d. )) simple same
(1) 8, =0 Vp
+
(2) du =
(5) Hx same
(6) G.(() same
Figure 4: Equivalence chain for the proof of Theorem 3.2.
25

---

Published as a conference paper at ICLR 2025
Proof of Theorem 3.2.
(1) (2): Theorem C.4 implies that for any p E (c)
o (WW, (V,9)) = 0 + 3p; v E Soo1 (W, = (V,g)* e (VW(),) = 0, (44)
where equality in the middle holds in an -ae. sense.
(2) = (4): This follows immediately from the Siiphon-signal counting lemma ($ C.I).
(4) (6): Let f) (V.g) WS, such that t((F, d), (W. t((F,d), (V. for all simple
graphs F, d E No Fix some e N. Clearly, the distribution of GxW. f) is uniquely determined by
P(o.n)BA.W.)) (G (G F),
(45)
P(c.)) (f E F)
(46)
i.e, the discrete distribution of the (labeled) random graph G and the conditional distribution of the node features given the graph structure, for every simple graph of size k. For (45), we remark that the standard homomorphism densities w.r.t. just the graphons W, V can be recovered by taking celluson-exclusion exclusion argument from the proof of Theorem 4.9.1 in (Zhao, 2023) can be used verbatim to reconstruct the probabilities from (45). With similar inclusion-exclusion argument, we see that for any F
= O. Thus, the inclusion
1 (W)
E F'P
2 F
(47)
and therefore
Emgr(-1)e(P)-4 ((F' ..',d, (W,
E ((G.)))G,(W.))
II f G=P (EV(F)
(48)
(w.
as long the denominator is positive (otherwise, the corresponding conditional distribution is arbitrary). Since (fIG = F') is bounded random vector (fffl < r a.s.), its distribution is
uniquely determined by its multidimensional moments, i.e., precisely the expressions from (48) (see
Lemma C.6). Thus,
conclude Gx (W, 2 Gv for all k e N.
(6) + (2): This implication follows from applying the graphon-signal sampling lemma (Levie (2023, Theorem 3.7) and Theorem B.5): If (6) holds, we can bound
(V, - (W,,((W, (WW,, f)) + EB GwW, (W. GWW,
(49)
(V)
0
(50)
as 1: >>
(1) + (3): With a technique as in $ C.I, bounding the individual graphon terms in a similar way as the signal terms, it is straightforward to show that the ((FF.)) from any multigraph F is also Lipschitz continuous w.r.t. őj. Thus, statement (3) follows immediately.
homomorphism density
E WS, such that t((F, d), (W,)) (((F, d), (V,9)) for all multi- graphs F. NP(P) Fix te E N. Then, HHT (W, f) and & (V, be seen (k22 dimeensooao random vectors which are clearly bounded, since all graphon entries are in [0, 1] and all signal en- tries in r.. We observe that (t((F, d), (W,f))}r and {+((F, d), g)) F.a- with F ranging over multigraphs of size k, are precisely the multidimensional moments of these random vectors. Lemma C.6 yields statement (5).
(3) = (5): Let
(5) + (6): This is immediate, as G+(-) is a function of (-).
C.4 PROOF OF COROLLARY 3.3
Corollary 3.3 (Convergence in graphon-sight signal space). For (Wn. fa)m. (W,f) E WS, and 1, d= ((W,; n; fn), ()) 0 i((F, d,), (n)) - I((F, d), (W, VF,d N²(F) (6)
as n. oc, with F ranging over all simple graphs.
26

---

Published as a conference paper at ICLR 2025
Proof. The proof idea is essentially the same as in the classical graphon case (for example, see 4.9 in Zhao (2023)): An application of Theorem 3.2 that uses compactness the graphon- signal space. For the sake of completeness, we restate the argument.
"=" follows immediately from the counting lemma ($ C.I). For "=", let (Wn. fn)n be a sequence of graphon-signals that left-converges to (W, f) E WS,. By compactness (Levie, 2023, Theorem 3.6), there exists a subsequence (W.,, fn)); converging to some limit (V,g) in cut distance. But then also all signal-weighted homomorphism densities of the subsequence converge, and hence
t(F, d, (W, t(F, (V.)) VF, No
(51)
Theorem 3.2 yields 6 (W, = 0, i.e., also (Wn, fa) - (W,J) in cut distance.
27

---

Published as a conference paper at ICLR 2025
D &- FOR GRAPHON-SIGNALS
In this section, we demonstrate that signal-weighted homomorphism densities also make sense on the granularity level of the k-WL hierarchy. Specifically, we show that their indistinguishability aligns with a natural formulation of the k-WL test for graphon-signal::
Theorem 3.4 (k-WL for graphon-signals. informal). Two graphon-signals (W.f) f) and (V.g) are k-WL indistinguishable if and only if (fF( d), (W, t((F, d), (V,g)) for all multigraphs F of treewidth < k L, d E (2(
Recently, Böker (2023) established a characterization of the k-WL test for graphons, linking it to multigraph homomorphism densities w.r.f. patterns of bounded treewidth. Building this, we intro- duce a natural generalization of the k-WL measure and distribution by Böker (2023) to graphon- signals and highlight that their homomorphism expressivity can be captured through signal-weighted homomorphism densities. This serves as the final step in demonstrating the suitability of this ex- tension for our analyses. Since, compared to the discrete case, the formulation for graphons and graphon-signals is significantly more technical, we directly state the graphon-signal versions of the concepts. Our goal this section is not a fully detailed exposition, but rather to give intuition and highlight the key modifications required in the definitions and arguments of Böker (2023) to make them work for graphon-signals.
D.I TRI-LABELED GRAPHS AND GRAPHON-SIGNAL OPERATORS
To relate the k-WL measure to homomorphism densities on standard graphons, Böker (2023, $ 3.1) introduces bi-labeled graphs to define a set of operators that generalize the single shift operator Tw used by Grebík & Rocha (2022) for I-WL. Using bi-labeled graphs, they define operations that generate all multigraphs of treewidth < k 1 by taking the closure of set of alomic graphs under these operations. Intuitively, decomposing a bi-labeled graph into atomic parts corresponds to a tree decomposition with a certain special structure. This effectively allows one to express homomorphism densities via elementary operators associated with atomic graphs. This concept can be generalized to tri-labeled graphs for signal- homomorphism densities:
Definition D.1 (Tri-labeled graphs). A tri-labeled graph is tuple G = (G, a, d), where G is multigraph, a E V(G)*, E VGG with k. l 2 O, and d E Ng(G) Here, the entries of a, b each must be pairwise distinct. (G, d) is called the underlying graph of G, and a, b its input and output vertices. Write k for the set of all such graphs.
One can define some elementary operations with tri-labeled graphs: For F; -Fi, a1, bj, di)
M and F2 = (F2, a2 b2, d2) E M define the composition of Fi and F2 as
F2 = (F, b2, + d2) E M F
(52)
where F is obtained from F1 F2 by identifying the vertices the tuples b and a₂ (whose dimen- sions we required to be aligned). and the sum d1 + d2 should be seen w.r.t. this identification. This identification also potentially introduces multiedges. The Schur product of F, (Fi, an, 20,d1) and F2- = (F2, a22 Ø3 d2) E AM*0 is defined as
F. (F 2, d1 + d2) E M
(53)
where we abuse notation by writing for the empty tuple, and F' Fi L F2, with the nodes in a and a₂ identified. Now, also consider some atomic labeled graphs which can be glued together using the above operations:
Definition D.2 (cf. Böker (2023, Definition 12)). Let l 2 1. Define the following specific tri-labeled graphs:
Adjacency graph: A
((g) = ((k), (i,))) (1...., A.....,,)... (1) 0) E MRC f i j.
Introduce graph: r = ((()) 2), (1, ... k), (1, :....:.. -1, 0)
0) E MRih-1 Forget graph: F (R) ((()), Ø), (1, (1...., 1, + 11,++1..... 1,..., k), (1,...,,) 0) 1
Neighbor graph: N (k)
= 1(()) m/(h) M
28

---

Published as a conference paper at ICLR 2025
Signal graph: S = (((A), Ø), (I,..., (1,...,A),dd) Mahk for NO.
All-one graph: 1(k) = ((M)) Ø0, (1,....,),,.. 2,) E MM
Define the set of all atomic tri-labeled graphs as
F = ( (K) (RJ)
+ [ [+]] u (N j [1] u { de deNt c C.A...
(54)
These atomic graphs can now be joined by the elementary operations composition and Schur product to terms (Böker, 2023, Definition 13): For k 2 1 and F S -MRK, the set (F) of F-terms is the smallest set of expressions such that
1 (8) (F),
(55)
Fo E (F)
FF E (F).
(56)
F1 Fi.F2C E (F)
(57)
For such a term F, write [F] E M for its evaluation. Notably, Böker (2023, Definition 13) shows that the underlying graphs when evaluating the terms in their version of (F+) are precisely the multigraphs of treewidth bounded by 1. In our case, we obtain
Theorem D.3 (cf. Böker (2023, Theorem 14)). The underlying graphs of the tri-labeled graphs obtained by evaluating the terms in (F*) are precisely the node-featured multigraphs (F, d) with tw(F) S k 1, up to isolated vertices.
We omit the proof here; it is elementary and relies the existence of certain nice tree decompo- sitions (Kloks, 1994; Böker, 2023). In these (rooted) tree decompositions, roughly speaking, each edge where the bag changes corresponds to the addition removal of a single node in bag, and each bag has at most two children. Consequently, the tree can be traversed so that every edge is associated with one of the operations from Definition D.2.
Hi
S CAL MEJO
(ul, ug. MS
(KL
(M) Mg. Mag
(1
US
A000
A A (uap (ouds
Figure 5: A nice tree decomposition for a node-featured graph of treewidth 2, along with corresponding atomic tri-labeled graphs.
Consider, for example, the tri-labeled graph F (F, a, 2, 2,d) M330 from Figure 5 (the input vertices are highlighted), as well as a corresponding nice tree decomposition. F can be seen as the evaluation of the following term in F3:
F
S(3) (d..0.0 o ((A (1.2) (
A
(3)
A
(3)
S
d4) 1(
33)
(58)
(1.3)
(2.3)
(Ai1.3) (
A (3)
A (3)
S
ds) (()).
3)
(59)
[1,2)
[2,3]
To later connect these terms in (Fk) the k- test, Böker (2023) defines the concept of height h(F) for a term F. Intuitively, this means that the homomorphism density w.r.t. the underlying graph of [F] can be computed after ((F)) rounds of color refinement.
Definition D.4 (Height of a term). We define the height i(FF) of a term F E (Fk) inductively by setting h1 (a)) = O, h(N F) == h(F) + 1 for any neighbor graph N, h(A o F) := h(F) and ((S F) == ((F) for any adjacency and signal graphs A and S respectively, and i(F, F2) =
max (F.,., (.
We can define graphon-signal operators using tri-labeled graphs. Let F (FF,,bb b, d) E M be tri-labeled graph. Let r > 0. Define the associated F- Fooperator of (W,f) WS, as T TF
29

---

Published as a conference paper at ICLR 2025
1] - - 112, (Tr-(w,s) (xa)
which acts on U E L² 1] as
X
= -Jappee
II far))at (EV(F)
II 2z)) U(zs) dxx(F) ((v(F)))))))))))))))) (60)
(BJ)EE(F)
Importantly, composition (52) and Schur product (53) of tri-labeled graphs correspond to the com- position and pointwise product of their associated operators, i.e.,
T FF.FL-(WW.)) TF-((W,)) o TFL-(W.)) AA E MMR. F2 E EMM k, k,,, 2 0,
(61)
FW..F--(W.J) -w.)(W.)) -F,-((W))
VF,, F2 M k 0.
(62)
This allows gradually build up the operator [F]-(W.J) for any term F (F*) from the operators w.r.t. its atomic graphs. It is also straightforward to see that just integrating over the output of such an operator applied to constant function recovers the signal-weighted homomorphism densities, Formally, for any (W, f) WS, and F = (F, a, b, d) E M we have
J 10.1j= (F-ww so dx t((F, dW,
(63)
D.2 WEISFEILER-LEMA MEASURES
One can now define the space of colors used by the k- for praphon-signals, In the discrete case at least as long as node labels come from countable alphabet- thib space is countable and can be left implicit. However, for graphons and graphon-signals, the situation more nuanced as the color space requires careful consideration of its topology, i.e., a suitable notion of conver- gence/distance.
Definition D.5 (Weisfeiler-Leman Measure, ef. Böker (2023, Definition 26)). Let k 2 and fix r > 0. Let
Pe [0, ()
[-r,,]*
(64)
be the space of initial colors. Inductively define
M
P
Pk s+1 == P(M)))*
(65)
iS.
for every 8 E N, where we consider Ph with its standard topology, and P(-) denotes the set of all Borel probability measures, equipped with the weak topology. Let M == ILLE Ps (equipped with the product topology) and define Pt-ss Mb M& be the natural projection for Set
Pk = {a E M (ast1)) = (0.+2)) for all [k], EN,
(66)
where (po-sst)). denotes the pushforward of measures.
We tacitly equip all spaces in Definition D.5 with their Borel o-algebra. Intuitively, one can think of p as the space of all colors (potentially) used by the k-WL test, where for E Ip each entry ag. 8 E N. is a refinement of the previous one. For any a E Tp and j E [k.. there is unique measure 11 E P(M)) such that
(Poo-sa)-11f (c).+)) vs N,
(67)
by the Kolmogorov consistency theorem. A few basic statements about the topology of the spaces R and Ipk are collected in the following lemma:
Lemma D.6 (cf. Böker (2023, p. 32 and Lemma 27)). Consider M and pk as in Definition D.5.
The following holds:
(1) The space k is metrizable and compact, and Ipk C M closed.
(2) The set
C(M(t) Poc-se C. C(M))) seNo
U
(68)
is dense.
30

---

Published as a conference paper at ICLR 2025
(3) For any j E [k], the assignment P a H9 P(M)) is continuous.
Proof. Statement (I) follows immediately: Pg is clearly metrizable and compact, and we can in- ductively conclude the same for P 8 E N, as this is preserved by P(-) and finite products. Also, as countable product of metrizable and compact spaces, M is compact (by Tychonoff's ' theorem) as well as metrizable. Now, let (x E ph such that a² - E M.. Clearly, for any N, E [k), we have (a(41)) - (cxs41); by the definition of product topology, and for any J E CCM))
(n) J /d(a.f1) May
[ [opst1->s JeL
S
f fd(asti)s Jasl
sopsti-s
(69)
by the definition of the pushforward, and as a!n) E Pt This implies also (o (a and, thus. (a.-1); = (P==1-))) (as P(M)) is metrizable and, hence, Hausdorff). We conclude a E 1pt, and Ipt is closed. Particularly, this means that 1 is compact as well. For (2), note that the set an algebra, clearly contains a constant function, and separates points of M* (again, by the definition of product topology). The Stone-Weiersee Weierstrass theorem yields the claim. Statement (3) follows similarly easily from (2).
One can now define a set of "simple" functions on M which will turn out to be related to homo- morphism densities. For a term F (F*) of height h(F) I 8, define of realizing functions F from M to R inductively as the smallest one fulfilling
F
Amy,
(70)
Fg
aa + ((a))) t(a)]
Vt E F. i $ [k],
E
(71)
5 of
F.s
e
a + II ((ao)2). t(a)
Vt E F., d E No.
(72)
sE[K]
F. N
f id(asta)}
+
E F. j E [K]
(73)
JMs
FF
e t l/
44 E F. ,26 E 133
(74)
F e I Pa-st
WL 8 MFF).
(75)
Also, set
p
UUUE SENo ACT)S$
F o Poo-ss S (M*).
(76)
One can check that each E F is continuous. By the consistency requirement on Tpk the restriction of Fd to this subspace collapses to singleton. Abusing notation, define this realizing function of term F E (FF6) as
E = F F*I C(IPA).
(77)
This leads to the following result:
Theorem D.7. The sets
span UFC FE(FE)
F FFCMM C(MM)
and span (t (FIFFF)) C(PA)
(78)
are dense w.r.t. 11.
The proof for M is tedious but conceptually simple, and relies on an inductive application of the Stone-Weiersten theorem M. for N. Via Lemma D.6, (68), one then arrive at MI (this works, again, by a basic property of the product topology). The reader is referred to Böker (2023, Lemma 44) for the detailed argument. The statement for pp follows immediately by its compactness.
31

---

Published as a conference paper at ICLR 2025
D.3 COLOR REFINEMENT FOR GRAPHON- -SIGNLSS
One can now define the equivalent of the color refinement for specific graphon-signal. Observe the close resemblance of the following definition discrete k-WL test (ef. Huang & Villar (2021)).
Definition D.8 (k-WL, cf. Böker (2023, Definition 29)). Let k 1. O, and let (W, f) WS,.
Define el (0). [0, 1 + Mi by
fW.f)
(O (m) == (w.f)
((W())))))) (1)))(()))))) (L.)))) ((()))))))(((()))))))))()))))))( (f(zz)) (((H)
(79)
for every x E [0, 1]8. We then inductively define (W.f)
WL,
8+1 by
( (x) = (CWwhh (c% (z)), ((etwih o 20l-/5l) >) SE(N))
(W.))
(80)
for every [0, 1 where X is the Lebesgue measure and 2: x(-/j] == (..., "
[0, 1).. Let gk-LL
(W.)) [0, 1) + MP such that (C(W.))s = (C( for all E N. Call
k-WL (W.))
((w.)) ), X E P(M**
(81)
the k-dimensional Weisfeiler-Leman distribution of the graphon-signal (W, f).
Intuitively, this corresponds with the multiset of colors that is obtained by the k- test for graphs. Consequentially, we call two graphon-signals k W-WL-indisinggussaabe if and only if their k-WL distributions coincide. It is straightforward to show that k-WL (W.() (Pk) = 1, i.e., k-WL-distributions of graphon-signal indeed define color refinements in the sense of (66). Skipping all the technical details, we get directly to the homomorphism expressivity of this k-WL test. Notably, the realizing functions 1st of terms F E (Fk) can be elegantly related to -eiihtewe homomorphism densities via the terms from (77):
Proposition D.9 (cf. Böker (2023, Corollary 43)). Let k. 2 (W, WS,, and F e (Fh) with [F] =
Ø, d) E MM.0 Then, we have
S.a. du (W.))
t((F, d), (W.
(82)
This leads the following result, which generalizes Böker (2023, Theorem (1) 4> (2)):
Theorem D.10 (k-WL for graphon-signals, formal). Let > 0 and WW,)),VV E WS, be two sraphon-signate Then, w.- only if
(W.f) = (V.g)) i.e. the graphon sighnalssss are k- WL indistinguishable if and
k-WL,
((F,d), f)) (((F,d), (V.g))
(83)
for all multigraphs F of treewidth < k - 1 and d E No
The arguments of Böker (2023) transfer almost verbatim to this setting. The crux is that in the k- WL test, both the distribution of the graphon values W and the signal are captured already in the first step (79) and, therefore, higher-order moments need to be considered.
32

---

Published as a conference paper at ICLR 2025
E
INVARIANT GRAPHON NETWORKS
E PROOF OF THEOREM 4.2
Theorem 4.2. Let k, E No. Then, LEx is a finite-dimenniindl vector space of dimension
min(k,()
(
dim LEx-+ =
Σ
bell + +)).
(8)
We will need some more preparations for the proof, in which we consider any T E LEx-> only on step functions using regular intervals first, which will allow us use the existing results for the discrete case.
Lemma E.1 (Fixed points of measure preserving functions), If k E No and E L 1] such that U U for all ip E Soo.), then U is constant. All involved equalities are meant X -almost everywhere.
Although the proof is somewhat tedious, it is based on elementary measure theory. The aspect that warrants closer attention, however, is that yo acts uniformly across all coordinates.
Proof. Let U E [0 1| such that U is invariant under all measure preserving functions, and suppose that U is not constant -lalmoost everywhere. Then, there exist a < b such that A = ((-o0_ al). B == ((b, oo)) have positive Lebesgue measure X (*), X+B 0. Seeing U as random variable on the probability space ([O, 1]k, X²), the conditional distributions
P(-U aa) (²(-A))
and P(IUU 2 b)
(84)
(²)
(²(B)
are well-defined. For n E N, let 17 = ا-م 4 for j E m 13 and [(() == 1=
n-1 be
partition of [0, 1] into regular intervals, and set Pk(") = (1 x... (1) 1i,,..., in E (I....,..]. n}
First, note that we have
P(QUU Sa) # P(QUU 20) 2))
(85)
for some m E N and Q E ((m) Otherwise, equality in (85) would also hold for all hyperrectangles
k
with rational endpoints, which is a O-stable generator of the Borel o-algebra B[00, 1 Conse- quently, equality would hold for all sets in (( 1]*) and thus. 1 P(AU < a) PP (P 2 b)
X (B)) 0, which is a contradiction. W.L.o.g,, assume P(Q S a) > P(Q 2 b) in (85). As
Σ
PUSIU Sa)
Σ P(SU 2) = =, SEP!"))
(86)
SEP(m)
there must be another E
p((m) such that P( S a) < P(RIU 2 b). Set
4 = (a [0, ( xxHl < k),
A (n) c
= {Q E p(()) (QnA Ø)
(87)
to be the union of all diagonals on [0, 1]* and the elements of P (1) overlapping with A₂ respectively
for n E N. As x² (UQEA!")
(n) Q) X (Ax) 0 + do, there must exist m 2 m E N such that
there are Q 2 Q² p(m"
(m=)
A
(m²)
R R R
p(m")) A
(m")
satisfying
PUQ'UU S a) > PU 6), PU S a) < P(R 2 b).
(88)
Since Q" and R' do not overlap with any diagonal, we can now construct & E Spo1 such that p which clearly defines measure preserving function from [o, 11ah to itself, sends Q" to R By invariance of U under all measure preserving functions, we get
(R A) = x ((10 n A)) = x²(Q" nA), * n B) = A (( BB) = X²(Q" nB),
(89)
(90)
which contradicts (88). Hence, U must be -aae. constant.
n
33

---

Published as a conference paper at ICLR 2025
Let ki E No and n N. Let 170h 1-="" 1 for {1, fI...., 1} and T(() 1"
be a partition of [0, 1] into regular intervals. Let An == a (14 (m) ( denote the o-algebra generated by this partition and let
F - E E 12 11 is -mm--ssurablle):
(91)
define F-(") similarly. Intuitively, this is just the of regular k-dimensional L step kernels. Lemma E.2 (Invariance under discretization). Any T E LEg-t is invariant under discretization, which means that for any N. T(F S F.m), where the inclusion should be understood up to sets of measure zero.
Proof. Let LEx+4 and let U F Then, if pp E 3/o.1] such that
)
(92)
for any j E {I,...,,., n]. we have U = U and hence also T(U)* = T(U) Xaalmost everywhere. Take any hypercube Q 7(1) x...x (()) with -ie E
[I,...,n] and any measure-preserving function : [0, 1/n) [0, 1/)). We replicate yp the unit interval
(x) == x div 1/n + to (x mod 1/n),
(93)
which clearly satisfies (92), and thus T(U)0= = =T(U) almost everywhere. Since now
T(U) = T(U))* -(T(U))))
(94)
where we identify to with (0125-0) (which define measure preserving functions on 1,")),, we can use translation invariance and scale equivariance of the Lebesgue measure to conclude by Lemma E. that T(U) Q is constant X -ammost everywhere. As Q was chosen arbitrarily, this implies the state- ment of the lemma.
Equipped with Lemma E.2, we are now ready to show that the dimension of linear equivariant layers in [0, 1] is finite. Central to the argument is the observation that we can consider the action of any E LE on step functions, and apply the characterization from Maron al. (2019b) to sequence of nested subspaces, which fixes the operator on the entire space [, 1)
Proof of Theorem 4.2. Let n E N and T E LE By Lemma F.2, we know that T(F(") S F(")
Since F(") = (R t Ra* we can regard T v( F(()) F(")) as a linear operator R
TR." Taking for any E Sn measure-preserving transformation PP Sto.1) with -o- = lo)) that T y(()) is also permutation equivariant, and we can use the characterization of the basis elements from Cai & Wang (2022) (see $ B.2).
Note that for any n. E N we have F(") F( and the canonical basis elements {Tyheere-e under the identification F(m) R= (m) er Rm" are compatible in the sense that
T())).
(95)
Hence, the coefficients of T (()) w.r.t. the canonical basis (T heTtese do not depend on the specific n e N. W.L.ogg, assume that T restricted some F(") canonical basis function T (where 7 l'kte does not depend on n).
We now take a closer look at the partition 7" and its induced function T.(") described by the steps Selection, Reduction, Alignment, and Replication. Partition 7" into the 3 subsets qÎ : {A
7" A C [k]]. 7 == {A E > |4 C l + [[], 7% == > \ (of U 7g). For the constant U = E F(O)
(1) C (2 k} (()) (U) * 0 must also be constant a.e. by compatibility with discretization, so
34

---

Published as a conference paper at ICLR 2025
the partition > cannot correspond to basis function whose images are supported diagonal. This is precisely equivalent to |An (k + [4]] $ 1 for all A E y² Now suppose that the input only depends diagonal. Denoting the restriction of the constant U 1 to the diagonal under discretization of [0, 1] into n pieces by U,(
(U = T.. - (U) +
(96)
is constant, but ||U](- 12 + for n + oo, which contradicts boundedness (i.e., continuity) of the operator T E C(L (0. 118, _, Hence, >" must correspond to basis function for which the selection step 1 is trivial, i.c., |An n [k]] S 1 for all A E 7
This leaves us with only the partitions 7 E I' T whose sets A ? contain at most one element from [k] and [+[(] respectively. In the following Lemma E.3 we will check that for all of these partitions, the Reduction/ Satpiin/Aiiiimeee/eeeiaattte eeppcccation-proeduure (with averaging in the sense of integration over [0, 1)) indeed yields a valid operator T, E [0, 1]R, 1, 119) which agrees with TT()) on F(
If we can now show that UneN F. C [00 1] dense w.r.t. |1-112- we can conclude that T Tyy as I" is continuous and agrees with T,, on dense subset. However, this follows by a simple application of the martingale convergence theorem: Considering [0. 11 with Lebesgue measure A as a probability space and U e L2 11 as a random variable, we have EIU A E FA Also, (UnEN A [[00, 1]m) is the entire Borel a A-lgebra as A,, contains all intervals with rational endpoints, so B|U LA @ - EU [[[O, 1] = in 1
Define now
F'. = {r Ta+e VAA E E | [K]| S + 1J.
(97)
It straightforward to show that
min(k,e)
Fu. = Σ ==0
(98)
which can be seen as follows: Any partition on the l.s.s. can contain E {O..... min {} sets of size 2. Fixing some s, any of these sets can only contain one element from [k] and one from k + [d]. For the elements occuring in sets of size there are (2) options, and there are s! ways match the s selected elements in [k] with the s elements in + [e]. leaving us with the formula on the right. This concludes the proof.
Note the resemblance of the basis elements T., (10) to the definition of graphon- signall operators from D.1. Loosely speaking, all operators T, are variants of (60), where the roles of and b are switched, w.r.t. an empty graph
E.2 CONTINUITY OF LINEAR EQUIVARIANT LAYERS
We note that the choice p- 2 in Definition 4. I is somewhat arbitrary, and T,, can indeed be seen as an operator L + LP for any p E oo), with [[T,llp-p = 1. The case case p = 2 is technically still needed to complete the proof of Theorem 4.2.
Lemma E.3 (Continuity of Linear Equivariant Layers w.r.t. I1-lp))- Fix Fick, No. Let T E LE and p E [1, Then, T can also be regarded as bounded linear operator [P 11 + LP 1)s. Furthermore, all of the canonical basis elements from the proof of Theorem 4.2 have operator norm |T
Proof. If suffices to show boundedness, of all canonical basis elements. Just as in (10), take 7 E Tr. containing s sets of size (i.jj....... jes with ig...., ig E [k], J1. + [0]. and set = (ii..... 1e), b = (ji....,Je) J.). Write T, as
TU(U) = 10. 11f 3 y + /
Jo.j-- UlEa, 2(s)a)))))))))))))))))))) dx (
(99)
#b=k
35

---

Published as a conference paper at ICLR 2025
Consider at first
Clearly, (99) is also well-defined for U L" 1] and
|0,(0))13 So Jour Ul 2(b)aa) dx "
()
(100)
Bo=yb-k
f 10.11 J (U (Maaa) dxa (app\\a)
dX
(101)
JoAN I p..1-- (llaa, d ( (x = ||
(102)
with Jemsen's 's incquality being applied in the second step. Note that equality holds, c.g., for U = so [TTyll->p 1. For p = oo, we also see
1,
[1, (U))oo
ess sup ve[o.1]e 10.1)
Uw tlkiaaa ) dd (x{1))a))
(103)
/
U mلjiaal dla (x(()(a)) ve[0.1] [0.1]=-a
css sup
(104)
<l acc
2a yo-k
S 1oooo
(105)
again with equality for =
E.3 ASYMPTOTIC DIMENSION OF LINEAR EQUIVARIANT LAYERS
We briefly analyze the asymptotic differences in dimension between LE(") the linear equivariant layer space of discrete IGNs, and LE = k
U.1]
of IWNs. Recall that
dim LEIn k-t
bell + E), min(kke)
(106)
dim LE [0.1] [o.1.
Σ
k
(
(107)
For a comparison of the dimensions for the first few pairs (ks, E). see Table 2.
Table 2: Dimensions of LE LE
k-yz and LE 0.11
k
dim LE ir]
2
dim LE [0 4
1
2
3
k-
k-
2
15
1
1
1
1
2
5
15
52
2
3
4
5
15
52
203
3
7
13
3
5
15
52
203
877
4
13
34
73
203
877
4140
5
21
73
209
The case of bounded or f. Immediately visible from Table 2 the vastly different behavior of the expressions long one of the variables is bounded: In the discrete case, whenever k + 3o or é + oc, we have bell(k + E) + oo superexponentially. However, for the case of [0, 1], suppose w.l.o.g. that only A + and O(1) remains constant. Then, the corresponding dimension growth is bounded by
dim LE 0.1 k-4 = dim LE 1 = O(K))
(108)
(107) is dominated by (b) in this case.
36

---

Published as a conference paper at ICLR 2025
The of k ~ &. We will now consider the worst case, i.e., when is grows roughly as fast as l. For simplicity, assume k = E, and thus
dim LE m1
bell(2k)), dim LE
k-
[0.1]
h
(109)
s=0
The bell numbers grow superexponentially. be by of its asymptotic formulas (e.g.. refer to Weisstein, Equation 19):
bell(n)
π Vn ((n))
n+1/2
n
- -1),
(110)
((n)
where W denotes the Lambert W-function, i.e., the inverse of + I exp(2)), simpler charac- terization due to Grunwald & Serafin (2025, Proposition 4.7), which is not strictly asymptotically tight but suffices in our case:
1
72
< bell(n)
3 n2
(111)
log
4
log
as long as n 2 2. Therefore, the dimension of linear equivariant layers in the discrete case can be bounded as
dim
LE in
2k
2
(112)
R
log 2
We will now provide bounds the dimension in the continuous considering the last addend,
First note that by only
dim LE
k! bell(k)
(113)
still grows superexponentially well-known bound on the factorial (see, e.g., Knuth (1997, $ 1.2.5, Ex. 24)) is
2
h+1
(114)
1-1
for n E N. For a rough upper bound on the dimension, we consider just an even tensor order k:
k 2
dim LE 0.1]
Σ
(115)
k-t
h13
(k: + 1)k!
=(k =(++))
(116)
k/22
(k/2)114
(114)
33++3 22h-4
4
< (k + 1)
= - (k + 1)k-3
(117)
33hh 3 (k/2)22
which still grows significantly slower than (112).
E.4 PROOF PROPOSITION 4.4
Proposition 4.4. Any IWN from (11) is instance of IGN-small (Cai & Wang. 2022).
Proof. Let WIW be an IWN as in Definition 4.3. By invariance under discretization (Lemma E.2), we can see that any linear equivariant layer in 1/W fulfills a basis representation stability condition, and under the identification F(() e R= which is captured by grid-sampling, this directly implies that grid-sampling commutes with application of the IWN and its discrete equivalent.
E.5 PROOF OF LEMMA 4.5
Lemma 4.5. Let Arwn, WS, + be an IWN with Lipschitz continuous nonlinearity g. Then, N is Lipschitz contimuous w.E.I. o, for each p E (1)
37

---

Published as a conference paper at ICLR 2025
Proof of Lemma 4.5. Let
N =
(118)
be an IWN as in Definition 4.3. By Lemma E.3, each T E LE is Lipschitz continuous w.r.t
Il-llp on the respective imput and output space, and this immediately carries over to all I()) s S [S]. Hence, it suffices to check that the pointwise application of the nonlinearity, i.c. L 1 U +
o(U), is Lipschitz continuous for every h E No. where & is applied elementwise. If Ce is the Lipschitz constant of g. we have
(le(U) - e = / u.111
lo(U)) di* & SULN C6 w/p dx# = -blllU WIp.
(119)
for p < 00, and the claim follows similarly for I1-
E.6 PROOF OF THEOREM 4.6
We show that IWNs can approximate sggnal-eighted homomorphism densities w.r.t. graphs of size up to their order. For this, we model the product in the homomorphism densities explicitly while tracking which linear equivariant layers are being used by the IWN. The final result then follows by using a tree decomposition.
Theorem 4.6 (Aprroximation of geighte homomorphism densities), Letr > 0, < k E N, 0 + Lipschitz continuous and non-polynomial, and be multigraph of treewidth k- 1, d E N F > O. Then there exists an IWN Niww of order ls such that for all (W, E WS,
|t((F, d), (W, f)) - -N (W. E.
(13)
To establish this result, we first show that IWNs can approximate signal-weighted homomorphism densities for graphs of size up their order. To facilitate the final step of combining these ap- proximations via a tree decomposition, we refrain from integrating over all nodes of the pattern graph immediately. Instead, we keep some labeled nodes to serve connection points paint--akin the construction of signal-weighter
homomorphism densities from tri-labeled graphs in D.1.
Lemma E.4. Let > O, R > O, Q: TR - R Lipschitz continuous and non-polynomial, and > 1. Let F = (F, a,,,ab.dl d) M be tri-labeled graph with ((F) [K] and E I k. Write in for the function that embeds any U E L²²00,17 11mm for m S k as k-tensor ux(U) == [10, 1] e x + U ,.m..,,,,mm),. Consider now the map OF that implements
(W) (R(
(W) w() TULOTT-AWNN
OF (2210,1,11)) + 11
(120)
for any (W E WSy and U E 1210, 112h (technically, this is only partially specified in the first two coordinates). Then, extending notation informally, for any s >> O, there exists a k-order EWN TEWN with nonlinearity such that uniformly on (W,J) f) E WS, and U E 10 1]
|| p (W. f.))
-N -N NEWN (W,f, UWl,, S.
(121)
For the proof, we model the product in the graphon- signal operators explicitly while tracking which linear equivariant layers are being used by the EWN.
We start with a few further preparations for the proofs. Namely, our first goal will be to show that if an EWN of a fixed order can approximate a set of functions, it can also approximate their product (Lemma E.6). First, we show how we can approximate the identity with an EWN:
Lemma E.5. Let lo > and R > 0. Let e R - R be differentiable at least at one point with nonzero derivative. For any > O, there exist T(1, T(2) E LE such that for Arews
(T() go (1) we huve
[ - U 10,01, S
(122)
uniformly for all U E &. 10, 1
38

---

Published as a conference paper at ICLR 2025
Proof. We simply approximate the identity function using the nonlinearity 2. Let Zy R be point at which g is differentiable with g' (xo) * 0. Fix E > 0. There exists some constant > 0 such that |xc| S 8 implies
le(20 + x) - e(xo) (x(o)))) S & |z]|-
(123)
Set
idg(z) = (00
R
1o +
R²= e(xo)
(124)
Then, for any I-R, R8. 1 and hence
R
lid,(x) - x| =
(oo)
20
+
R
Φ - e(xo) e'(x0) πt"
(125)
R
R
<
S
8.
(126)
8g'
R
[e(x)))
We can now simply set NEWN == idg. acting on the function values of an input independently. Hence, for any U E L [0, 118, we get
R
[[ ~lll))_ lg'(x0)
[0.1j
(127)
directly by (126). Since the r.h.s. can be made arbitrarily small, the proof is complete.
Lemma E.6. Let k and O. Let NEW ..... NEWN be E EWNs of order k E and Lipschitz continuous nonlinearity 9, each with constant orders of ks the same input dimension d, and output dimension of I, i.e., returning function [0. 1] -> IR. Fix O. Then, there exists an EWN
m
N NEWN of order k, such that for all U E (LR 1
II (U) -VEEN (U)
SE.
(128)
00,
The proof is partially analogous to Keriven & Peyré (2019), A crucial difference is that we do not rely on modeling multiplication by increasing the tensor orders.
Proof. We will exploit property of cos that allows express products sums. Namely, it is well-known that for ft,... Fm E R we have
m II coS(
m Σ j=1
Σ
cos
Tjoj
(129)
2m
0E{+1)m
Fix >> 0. At first, we will describe how to approximate any NEWN using cos as a nonlinearity. By the classical universal approximation theorem (see for example Pinkus (1999, Theorem 3.1)), can approximate g R R on compact sets arbitrarily well by a feedforward neural network lcos with hidden layer, using the cosine function nonlinearity. For all é E [m]] the set of values of all intermediate computations in the evaluation of NNWW (U) for U E (I [0, 1 d is bounded, and we define Mj E [0, oo) be the supremum of this set. Note that this means that ø only ever evaluated on the compact set [-M M1] in {AEEw) Je. We can see that replacing each occurence of g in A JEWN by îcos and absorbing the linear factors into the linear equivariant layers again yields valid EWNs. Call these EWNs N = 1,..., m. The underlying feedforward neural network Goos can now be chosen such that for all l E [m], U (L 1/
N (U) - .1 FEWN (U) [0)]ll..,o..1- S E.
(130)
Note that each NOWN might have different numbers of layers. Hence, we invoke Lemma E.5 to equalize the number of layers, and add one more layer of the identity. We obtain EWNs WWNN..eEw (,coe
Aeew such
that
ideos (ACEWN (U)) NEWN (U)
10.10.11 S
(131)
39

---

Published as a conference paper at ICLR 2025
for all U (L [0. 1 Using (129) and setting idcos(2) cos(ax + b) + for some a, b, c, d E R, we can now write
172
ideos N, (U))
II
cos(a-
Agrn (U) b) + +d)
(132)
Σ
clAl d
II
cos(a 2,000 (U) + +b)
(133)
Ag
EEA
cl dn
Σ
cos
Σ
NeW (U) + +b]
(134)
2|
Aglm]
OE{+1]4
VEA
which can represented by an EWN of order and one layer more compared to (, es stacking the expressions from (+), applying the nonlinearity cos and aggregating the outputs determined by the weighted sum. Let
M2 == max sup || (U))(((U),,,
(135)
éE(m) U
Since for any E (L (0, 1
idooa
E,0os (U))
N EWN (U)
(136)
oc,10,11=
m
>
ideas (Nixw (U))
II (U)
(ideas (NVENN (U)) - -NEEN(
t=1
i<8
20.10.114
(137)
7
<
NWWN idso (N
(U))
II
N
rEWN (U)
idens N. (U)) - -VEW((U)
Leoo
10.10.11
i<8
(0.10.1
(138)
M2 + 2 22, 1=1
(139)
and since (139) goes to zero O. this shows the claim for cos. Another application of the universal approximation theorem yields the claim for g.
The proof Lemma E.4 now boils down to an application of Lemma E.6.
Proof of Lemma E.4. Fix a tri-labeled graph F = (F, a, b, d) with V(F) = [b], and b & and k-tuples over [k] respectively. Let (W, f) WS, and U E L (0, 11 Define
fi [0, 11th + R, W(n =00, 11th + R, x x W(x;
f(x)
for E (VF),
(140)
for {i.j} E(F).
(141)
Clearly, [1x (W)) + ft. (W),
+ W(..). and [w,(W) (x)))(()))) (f), UJ +
Ub = x + ('xx)] can be exactly represented by EWNs of order i with one layer (i.e., no application of the nonlinearity all). By Lemma E.6, the product
La (W)
)
6 (
II
Woss Ub
(142)
U
(EV(F)
can be approximated by an EWN of order & arbitrarily well in Il However, setting = E, di,
)
TF-(W.)U = SaNj-
=
II (EV(F))
(I W(n))
Ubdi Lg 00 0,1 (143)
(1J)EE(F))
40

---

Published as a conference paper at ICLR 2025
and combined with applying Lemma E.5 again on W and f, one concludes that
Ls (W)
(W)
(
(f)
(144)
U
LIR TF-
can be approximated arbitrarily well by an EWN for f) ws, and U E 10,1
With these preparations in place, are ready prove Theorem 4.6. The proof proceeds by constructing a signal-weighted homomorphism density step by step using F of tri-laheled graphs, as outlined in D.1.
Proof of Theorem 4.6. We first consider the operators 4 Fatom from Lemma E.4 for the atomic graphs F Fatom from Definition D.2. The restriction we imposed on the tri-labeled graphs F (F, a, b, d)
M to have ((F) = [k]] is straightforwardly fulfilled by the adjacency graphs A A and signal
(i.j)
graphs ) Any neighborhood graph be implemented by such operators Φr, where only the labels in the introduce graph have to be permuted to account for the trailing dimension caused by our use of the k-order embedding lg. In total, this means that $ Fatom for all atomic tri-labeled graphs in jk can be written as the composition of at most two of the functions in Lemma E.4. By precisely this lemma, we know that $ Fattom can be approximated by some EWN AVENN Futom up to arbitrary precision ||-1oco and on some restriction on the values of the input tensor U. Note that the composition of such functions can again be trivially approximated by an EWN (where the first and last linear equivariant layers can be merged). bounded and that any EWN as well as &F is I, -Liisshcc
crucial here that the set of all tensor values
Now, for any term F (F*), ), possible to approximate "tn with arbitrary precision by an EWN. (W. f) := [W+( ), 4 (f), 1 1o which can clearly be implemented To start, simply take P,
by EWN. As already mentioned, the composition of two approximable & can be clearly also approximated by an EWN, and the product in the third "register" acting on U as well by Lemma E.6. By the definition of (Fk) and (61 (662,, this implies that 11 can indeed be approximated up arbitrary precision for any -term F. Letting [F]] (F, a, 2, d) E M we get by (63) that
(W)
1 + 1/
11
(W.f)
(f)
10.11 (r)- = ((...),, f)), (145)
(RI-(W.)
and the mapping on the l.h.s. can be collapsed to an IWN A [J] Hence, the r.h.s. in (145) can also be approximated uniformly by an IWN. The claim of Theorem 4.6 follows, as ==*tterms parametrize all weighl- homomorphism densities up to treewidth k- - 1 by Theorem D.3.
E.7 PROOF OF COROLLARY 4.7
Having shown Theorem 4.6, k-WL expressivity can be obtained effectively by definition. Corollary 4.7 (L-WL expressivitt B--JwN at least as expressive as the k- WL test at distinguish- ing graphon-signals.
Proof. Let (W, (V.g) e WS, be distinguishable by k-WL. By Theorem D.10, this means that there exists multigraph F of treewidth at most k --1 and d Ne(F) for which
{((F, d). (W, * t((F, d), (V. Let = |t((F, d), d), (W. - t((F, d), (V.g)) > 0. By Theorem 4.6, take k-order IWN I/w such that
(146)
sup (U.)eES
W (U. (U, se/3.
(147)
We obtain
W WWWN(W - -AIIN)
(148)
2 |(((F, d), (W, - ((FF, ()[,,d),(C d), (V,g))
(149)
- -WWnN (W.J) - (t(,f))((FFdal) d), ((((F))))))))))))))))))))())())( (V.9)) -VIIN(V.g)
c- e/3 e/3>
(150)
41

---

Published as a conference paper at ICLR 2025
which yields the claim.
E.8 PROOF OF COROLLARY 4.8
Note that Theorem 4.6 tells us that IWNs of arbitrary order can approximate any signal-weighted homomorphism density. As these separate points in WS, by Theorem 3.2, it is straightforward to obtain universality on any which is compact w.r.t. a distance on WS, under which the signal- weighted homomorphism densities are continuous.
0 0 R - R Lipschitz continuous Corollary 4.8 (6p- Fy-Universality of IWNs). Let <> 1, (1, and non-polyno.ial. For any compact K C. (WS,,6p) 3 is dense in the continuous functions C(K) w.E. ||-1|s0
Proof. We show this statement by applying the Stone-Weierstue Weierstrass theorem. In essence, the main part of the proof already lies in establishing the approximation of the signal-weighted homomorphism densities (Theorem 4.6). Fix a compact subset K c (WS,, 6p). Consider the space
span([((F, d) multigraph, d Ny(P) S C)
(151)
Clearly, D is linear subspace, and contains non-zero constant function as can take homomorphism density of a graph F with no edges and d = 0. Also, it is straightforward to see that D is subalgebra, as for any multigraphs F1, F2, di (N(F)) d2 E (Ps)s)
((Fi, d)), (((F2, d2)..) (((F) U F2, d d2).) E
(152)
i.., the product of homomorphism densities w.r.t. two simple graphs can be rewritten as the homo- morphism density w.r.t. their disjoint union. By Theorem 3.2, D also separates points, and we can apply Stone- Weierstrass (note that K is a metric space and, thus, particularly Hausdorff) to conclude that D S C(K, R) is dense. However, by Theorem 4.6, any element of D be approximated with arbitrary precision by BD"K, and thus
C(K,R) = D S NIWN C C)K,R).
(153)
This concludes the proof.
42

---

Published as a conference paper at ICLR 2025
F REHINEMENT-BASED GRAPHON NEURAL NETWORKS AND k- WL
In this section, we extend the notion of k-order GNN to the graphon-signal setting. In analogy to IWNs, call such networks higher-order graphon neural networks (WNNs). Moreover, show that-similarly as weggal-weighted homomorphism densities in (82)-such WNNs can also be written continuous functions the space of k-WL measures, and related back to their original formulation via the seophon-signall k- WL distribution (see D.3). In the following, we will make this precise.
F.1 DEFINITION OF GRAPHION NEURAL NETWORKS
In the following, we extend higher-order graph neural networks that mimic the k- WL test ($ D) to graphon-signals.
Definition F.1 (k-order graphon neural network). k > An S-layer o-order graphon neural network (WNN) is function N WS,, - I2 that uses the atomic types from Definition D.8
as initialization and updates its embeddings ht) [0, 11th Rd, iteratively for input (W, e WS, and x E [0, 1)ah as
h (0) (x))= = (W z5)) (15) (1)) (f(=)))((((())))) sER1))
(154)
h (x)))()),, ( ( (..,, 2341. )).....))))))))) cd(z)
(0) (x) == N
jE(N]
(155)
and
AWk.WN((W.I) = NRREADOUT (LONE 125) h(s))an)))
(156)
Here, do = (0)+
+ k, and N1.)) Rdd-- - RR,, N : Rdd x (RZ.)R - Rdd+1, N NREADOUT
Rds + R are implemented by MLPs.
Under suitable assumptions on the MLPs, (Lipschitz) continuity of the nonlinearity, is straight- forward to show that such a WNN is (Lipschitz) continuous in any LT" norm. By invariance w.rt. measure preserving maps, this extends easily to continuity in the 5p distances (cf. C.2). It imme- diately apparent that this mirrors the discrete version (Morris et al., 2019) and aligns with the k-WL distribution (Definition D.8).
F.2 FORMULATION ON k- WL MEASURES
In the following, we show how the WNNs from Definition F.1 can be factorized as a function of the k-WL for graphon-signal (W (S D.3). Effectively, this will allow to regard k-WL measure (W.J)
N CK- not as a function on the uncontrollable spaces (WS,, 5,), but as functions on the compact space P(M+) of probability measures over the colors produced by the k-WL test. In the discrete case, it is clear that any graph parameter which is at most k-WI. expressive, could alternatively be seen as a function on the k-WL colors. our setting, however, additional care needed to ensure that the defined functions well-defined and continuous w.r.t. the considered topologies. The idea of considering GNN outputs on the space of WL colors was already introduced by Böker et al. (2023) for MPNNs.
Definition F22 (k-order graphon neural network on W- measure). Let l: > and fix N. Take the MLPs N3 .N NREADOUT precisely from Definition F.1. Define the following embeddings (x) Mt + dRd on the space of k-WL measures (to be exact, their first coordinates) as follows:
(0) (a) = =
(157)
h h (frz ~af00 h ho
h (0)) (a) = Adla
Vs E [S].
JENN
(158)
43

---

Published as a conference paper at ICLR 2025
Finally, for any VE P(M"), set N == REAADOU (Be h (8) P de
(159)
M
Measurability of all involved functions can be checked easily. We will demonstrate that Nk-wwN is indeed continuous w.r.t the weak topology on P(
Lemma E.3 (Continuity of k-WNN). Let NRtWWNN : -P(M)) - R be a WNN from Definition F.2. Suppose all involved MLPs are continuous. Then, h)() E C(M TRdd), and A ylk.wa WNN E C(P(M)))
Proof. For the first statement, proceed via induction. For = O, (2 is the identity, so there is nothing to show. Fix s E N and suppose that (=(11), M + Rd is continuous. Let (an)n be sequence in M that converges to a E M.. By the induction hypothesis, ( 7 h h1 (p)- The convergence
[
N1.0 h (d(an)())ss - -g(e) h hd--a)((w))
(160)
bet
follows similarly as N (--) E C(MI Rd) and P(M)-1) e ((an)s)s 3tt (ass) Continuity of N finally yields continuity of h()), Thus, the proof of the first statement complete. The second part follows directly, as (5) P E C(M Rds), NA is continuous, and we are considering the topology of weak convergence on P(MI)).
In the following theorem, we will get to the objective of this section: Showing that the two formu- lations of k-order GNNs we have stated so far are indeed equivalent, in the sense that applying the k-WL measure version to the k-WL distribution of a graphon-signal (Definition F.2) indeed gives the same output as the original definition (Definition F.I).
Theorem F.4 (Equivalence of formulations), Let fW E WS,, and let N- be an WNN. For the formulations from Definition F.1 and Definition F.2, we obtain that
K-N fW,
(161)
Proof. We first show that
h (x) (e)
(c Co (a:)
(162)
for all & E No and alammtstt all x E 1 We proceed via induction. For a = 0 this obvious, as A ArK-WN is initialized with the atomic types of the k &-WL test. Consider some fixed but arbitrary s E N. and suppose that the equality (162) holds for s - 1. Then,
(.00((t (Ctw.. (2)))
Arle) UUDDATE
(n6--1) (e(w.)) (m))
Vnre Nof() (0-1)) a( aiC o ozll//5). SE(M]
(163)
-r((s)
(/l-1)) (etveh))
(c (m))
UPPDATE
Your -of0) (0-1)
CH d(x) d(xl-/51).) SE(M) )))m))))
((w.))
(164)
(l)))) (hran 11300 h d(al-)(())))))))
NeCebarE
(165)
jE(N]
120-1)(2)) (Jon (0700
(166)
SE(M)
(x),
(167)
44

---

Published as a conference paper at ICLR 2025
where used the induction hypothesis in (165). This proves (162). For the final o N the equality follows just as easily by moving the pushforward W. (W.f) = (W.,)) )x into the integrand.
Note that-akin signal-weighted homomorphism densities ($ D.2)-one one could apply the Stone- Weierstrass theorem to show that the set of all k-order WNNs (or IWNs) is universal on M and, therefore, k-order WNNs are k-WL expressive. We omit the proof here.
Similar characterizations as in this section could also be derived for the Folklore k-WL test (see, e.g., Jegelka (2022)) and the corresponding k-FGNNs (Maron et al., 2019a), which achieve the same expressivity as (k: + 1)-GNNS. While extending the k-FWL test and FGNNs is straightforward, ob- taining a characterization via signal-weight weighted homomorphism densities derived using tri- labele graphs ($
require slightly more effort.
45

---

Published as a conference paper at ICLR 2025
G CUT DISTANCE AND TRANSFERABILITY OF HIGHER-ORDER WNNS
G.1 PROOF OF PROPOSITION 5.1
Proposition 5.1. Let e [0, + I. Then, the assignment Wo - w + e(W) W, where is applied pointwise, is continuous w.r.t |llla if and only if is linear.
Proof. We will show that the assignment
Wo W e(W) E W,
(168)
where @ is applied pointwise, is continuous if and only if is linear. First, note that W E W fo.1p W dx² is linear and continuous w.r.t. |1-1|, since
JONP W dxa
< sup
/ /sxT 8,TC(0.11
W dA?
|W
(169)
Let e j0. + IR such that W + e(W) is continuous. Then, also W Sp.12 e(W) dx² is
continuous. Let p E (0, 1) and set W, == p- to be a constant graphon. we sample G(a)) G, (Wp)) p,), i... from Erdös-Rényi model with edge probability p. Gb)) Wp in the cut norm almost surely. But
/ e (WWo.) dx² + p. p()(1) + (1 (1 e(0),
(170)
while fo.up e(W,) dx2 = e(p). This implies
Vp E (0 : o(p) = p. e(1) + p) e(0),
(171)
i... ø a linear function. is trivial to check that if e(x) ax + is linear function, W e(W) is indeed continuous.
G.2 PROOF OF THROREM 5.2
Theorem 5.2 (Transferability). Let r > 1. Let N WS, + R such that N is contained in the closure of
span (t((F, d). deetigrraphhdee.. S Co(WS, 81)
(16)
w.r.t uniform convergence.
Then, for any (W, WS, and (Gns fu)s (Gm, fm)
G. f), (W.
E N + 0, m - 00.
(17)
Proof. Fix e 0. For such N, there exists a linear combination of signal homomorphism densities, i.e., finite collection of {a;}: E IR, multigraphs {Fihi and exponents {d,},, d, E No (R) such that
v Σ (st((FF,d))) ..).
S c.
(172)
=:N
Set
((W.S)= Σ ((Fsimpl di, (W,
(173)
where F; ++ F. piimple removes parallel edges. Nr is Lipschitz continuous in the cut distance by $ C.I and, crucially, agrees with No on {0, 13-vlled graphons (since any monomial + zd has 0 and fixed points), and, thus, finite graph-signals. Let M > 0 be the &g-Lipschitz constant of /
46

---

Published as a conference paper at ICLR 2025
Now, consider (G fm), (Gm, fm) GW,,,f), (W, f). By the graphon-sigaa sampling
lemma (Levie (2023); (4)), we can bound
E [ (G,, fm) - N (G,; E (G fn) Ne(G fw)l] +I TE [N, - NN fm)]]
(174)
(175)
( fm) N (G fm)
(176)
S 2e + M W..BBoo(GGaa fn); (Gm, fm)))
(177)
$ 2e + M [E[6 fn), (W) + B(o (Gms fm))l)
(178)
3 2: + 15M (logn) (I m/
(179)
where the sampling lemma used in (+). Hence,
S lim
sup sup [[ f.) - N (G fm)l] S 25
(180)
for all > 0, which completes the proof.
G.3 PROOF OF COROLLARY 5.3
Corollary 5.3 (Transferability of higher-order WNNs). The assumption of Theorem 5.2 holds for
(1) any IWN with continuous nonlinearity @. W-W for a continuous N P(M)) + R.
(2) any N: WS, - R for which fW, = NWW(w,)
Proof. (1): Let. NeWw be an IWN with nonlinearity and fix O. Let R - R be polynomial such that the IWN NAW which is obtained from A VIwN by replacing each occurrence of o with fulfills
IN - A/W 11:0
sup IN (NM((W.)) - -V (WW <
(181)
(W.f)ews.
Such exists: We can approximate o: :: R uniformly arbitrarily well on compact subsets of R by the standard Weierstrass theorem, and, as the domain of 1/WNN only contains bounded functions W and f. for any input (W, WS,, @ is only ever considered on some fixed bounded set (which depends on the model parameters). The argument is the same as switching activation functions, as integral over [0, 1]" of polynomial in the variables W W(r,, TG) and f(xx), ), for i, k [n) and some E N. This implies that N fINN a linear combination of
done multiple occasions in $ 4.3. Now, observe that NVIN can be reduced
homomorphism densities.
(2): This follows immediately by combining Theorem D.7 with Proposition D.9, using that the algebra generated by functions the form v + f dv de for f E C(M++ dense C(P(M++) by the Stone-Wo Weierstrass theorem. Note that such factorization specifically exists for k-WNNs by Theorem F.4.
G.4 QUANTITATIVE TRANSFERABILITY RESULTS
Theorem 5,4 (Quantitative transferability of IWNs, informal). Let > 1. For any NOWN in universal class of 2-layer IWNs with real-analytic nonlinearity there exists constant My > 0 such that for (W,J .)) WS, and (Gn, fn), (Gmn fm) (,, (W, for large n, m,
TWN fn)
NIWK (G Fm)) S My (logn) -1/2 1/2 + (log m) -1/2)
(18)
For simplicity, we consider a simple two-layer IWN of the form
N(W.f) = Joar
Σ
asW(as) + Σ bef(xe) + dx,
(182)
(S((
47

---

Published as a conference paper at ICLR 2025
where the input (W, E WS, is a graphon-signtl and (as)s, (bi)e, are real-valued coefficients. Note that linear combinations of (182) of arbitrary order & can distinguish any two sraphon-signatee that are not weakly isomorphic, simply by switching activation functions and showing that they can approximate any signal-weighted homomorphism density, akin to the arguments in & 4.3 and Keriven & Peyré (2019). This parametrization, however, is impractical, it typically requires an intractable number of addends of the form (182), and is introduced mainly to illustrate the core idea of the argument. We note that
N is generally not continuous in cut distance, long as o is nonlinear (Proposition 5.1), Yet, .V' is still transferable (or estimable; see also Lovász (2012, $ 15)), in the sense that N' restricted finite graphs is continuous in cut distance, and can be uniquely extended function N which cut distance continuous. Formally, from Theorem 5.2 we can conclude that
(Brc..to)oon (W,, (G NEN
(183)
is Cauchy, and simply set
fW, = lim B.G. fn]] n
(184)
However, to make quantitative statements about the transferability of N when applied to graphs of different sizes, we would need Lipschitz bound for N in cut distance, similar as can be obtained for MPNNs. For multigraph homomorphism densities, it is straightforward to see that the cut dis- tance continuous extension be simply obtained by removing parallel edges. The latter admits Lipschitz bound in cut norm/distance (by the graphon- signal counting lemma; see $ C.I). As such, any graph parameter consisting of (finite) linear combination of homomorphism densities is also Lipschitz in I-Ila- However more generally, for non-polynomial O. (182) might depend on an in- finite number of multigraph homomorphism densities. It is therefore not immediate to see that A will generally still be Lipschitz continuous in cut norm/distance, even if N is w.r.t. L (which holds as long as o is Lipschitz; see Lemma 4.5).
One general recipe to ensure that limits of Lipschitz functions stay Lipschitz is looking at their Lipschitz (semi-)norms: Let X be some metric space, and (fn), a sequence of real-valued Lipschitz functions on X' such that Il < so for all n. Supposing that En fn is defined on all of X, one can obtain
Σ n=1
fm
S
1.falleapp
(185)
Lip
n=
If the r.h.s. is still finite, this implies that the series Σm= fn is still Lipschitz continuous as a function X' + R. To make bounding potential Lipschitz constant of (182) tractable, we can try to write it as a series of bomomorphism densities. For this, we assume that the nonlinearity is real-tna,ytic, i.e., has a power series expansion e(x) = Eee Yea' with convergence radius R E (0, oo]. While this is much stronger assumption compared to Lipschitzness of e (on the compact domains of graphon-signal values we consider), is one that is fulfilled by many common activation functions like Sigmoid, Softplus, Swish (each with R T), or GELU (Rt = oo). With the above definitions in place, we will now state a formal version of Theorem 5.4 and proceed with its proof.
Theorem G.1 (Quantitative transferability of IWNs, formal). Let 1 and N be an IWN of the form (182), with real-analytic nonlinearity e of convergence radius R E (0) If we have r (a, b, c)ll <. R for the weights (a, b, c) of N. then there exists constant Mx > 0 such that for any two finite graph-signals (G1, fi). (G2, f2) E WS,, identified with their step graphon- siophon-signals,
(G f1) - fa)1 < My S fi),
(186)
The statement of Theorem 5.4 can be directly obtained from Theorem G.I, under the same condi- tions the IWN and nonlinearity as well as r > 1, simply by taking expectations over random graphs and invoking the graphon-signal sampling lemma on the r.h.s. of (186). The resulting mul- tiplicative constant is then the Lipschitz constant of the continuous IWN extension N, up to an absolute factor.
48

---

Published as a conference paper at ICLR 2025
Note that, since Theorem 5.4 is merely stating Lipschitzness of N for finite graphs (or Lipschitz- ness of Ñ on WS+), any other known bounds cut distance can be directly applied to obtain quantitative rates for the statement of Theorem 5.4. Under sampling simple graphs G, (W) from stochastic block model with & blocks, for example, rate of O TTog
& )//2) can be achieved (Klopp
& Verzelen, 2019), which significantly surpasses the generic rate of ( n) 1/2) typically given by the sampling lemmas. In fact, different discretization techniques have been used in the literature on convergence and transferabilitty, such as grid sampling (Ruiz et al., 2020) or discretization of the shift operator (Le Jegelka, 2023) (which equivalent to grid averaging for graphons), typically under regularity assumptions like Lipschitzness and with rates of O (111/ (these would, however, needed to be explicitly stated in cut distance to be applied to Theorem G.1).
Proof of Theorem G. J. Suppose we are given an IWN A as from (182) with real-analytic nonlin- earity o. and is given by its series expansion. Given graphon-signal (W, f) and a E [0, 1Jk, we can expand
Σ
ag agW(xs) + Σ bes(zz) + = EEe
Σ
as asW(xz)+ + Σ bef((r)) +
SE(
(1)
tE[k]
(E(())
tE]K]
(187)
8
Σas (ass(Es) )" m
(Zoslor)
7 Σ
(188)
m, n2
Σ
Σ as ... as by b, (((ss)) ... ((Fg.)((E)) (Ire
7t
n,n,P)
t=0
m+n+p==
Sm
(189)
and (by absolute convergence),
N(W.f) Σ
Σ S1 Aly...fa
as as by bi, (t,.s de (W. (W.f))
m. D.P.
0= m+n+p=l
(190)
where (Fst....S... S... de de is the multigraph on k vertices with edges Smy and node fea- tures (dl )a = [t E (tt,...,tt, ... It i)}. With this expansion of N in (190), it straight- forward to see that the cut distance continuous extension
N(W.f) Σ YE Σ
Σ as, as b .,, Cf Sm.... S Binnnt
Sm de........ (W.
m, n,
m+n+p=2
(191)
can be simply obtained by removing parallel edges in all occuring multigraph homomorphism den- sities. Note that e( (F Sm... S m, and Dr,...... = Σ, (d. = n. By the graphon-signal counting lemma ($ C. we bound
simple
t( ((F
simple Si....... de...... ). (W, f)) Lip.ón
(192)
$ max (4r Pi el Stumsmm ), 2D ".... P
(193)
s max max(4r" m, 111 max(4er ( 2011-13 2 40r
131
(194)
49

---

Published as a conference paper at ICLR 2025
and thus, applying (185),
Willipp
hel 1e
Σ 9
las +
Σ
l69l + lc|
(195)
t=
=i)(a,b,c)ll
hel 42 (rll(a,
Arll(a,b,)) (allll--(rrll b'(rll(ab,e))ll))
(196)
where ((z) Eizo heel of is the majorant of g. This bound holds as long as
ri((a, b, c)ll < R
(197)
within the radius of convergence of the series expansion @ (e.g., for GELU, this statement always holds). Hence, N is Lipschitz w.r.t. du.
A similar argument could plausibly be extended to multilayer IWNs; however, the resulting expan- sion quickly becomes unwieldy. The derived Lipschitz constant can blow up due the dependence on Ø. and is likely not tight. Note that by simply applying the triangle inequality to the Lipschitz norms, we lose any potential cancellation that might occur. Likewise, constants for the simple homomorphism densities-wher c.g., we ignore any tightening gained by dropping the parallel edges-is quite loose, chosen only result in a simple final bound.
estimate of the Lipschitz
Indeed, one could show that under the assumptions of Theorem G.I,
fW B(G.n)Ga(W.)) [)G,
(198)
that is, choosing serve as a starting point for an alternative approach to deriving bounds on the transferability of N: Disregarding the node signals, the difference of (198) for two different graphons W, V can be bounded by a constant multiple (depending on and the parameters (a, b, c)) of the variation distance between the random graph distributions Gy (W). (V),,, which in turn can be bounded by their cut distance (Lovász, 2012, $ 10.1). I). though with an exponential dependence on k. To generalize such an argument to craphon-sinaale one would have define a suitable distance for random graph- signal distributions that is compatible with the graphon-signe distance would have to metrize the weak topology on the probability measures over graph-signals, so the standard variation distance does not seem to work here. Further investigations of this approach and establishing tight and general bounds are left for future work.
in (184) already yields unbiased estimator. This formulation could
cut distance. It appears that such a
G.5 ADDITIONAL. REMARKS
Factorization of Higher-Order WNNs. Since pete M closed, defining the factorization from Corollary 5.3 only on measures on Tpk (see D) would also suffice by the Tietze extension theorem. However, it is important to note that defining the extension solely on the k-WL measures (vt-W ((W.))/...)) is priori not enough, as we have not shown that this set is closed.
In other words, can also look these phenomena through the lens of different topologies WS,. The I-WL test and MPNNs continuous in the cut distance, which makes WS,, a compact space, in which convergence is determined by hignal-weightn graphs (Corollary 3.3). For the k-WL test and higher-order graphon neural networks such as the ones we considered (IWNs, k-WNNs), we have seen that this does not hold. However, these models factorize as continuous functions on the compact space of k- colors M whose convergence determined by mudtigraph combines all k-WL measures, l > 1, into a single object (which is again compact by Tychonoff's theorem), which describes precisely the topology of convergence of all multigraph homomorphism densities. A topology which is at least as fine is given by the {5plpe[1, distances, as the multigraph homomorphism densities continuous in these. This is illustrated in Figure 6.
homomorphism densities w.r.t. simple
homomorphism densities. Note that Böker (2023, 4.7)
We want to briefly elaborate on (*) regarding relative compactness in the middle Figure 6. For 1- via distributions of iterated degree measures defined on color space M, the assignment
50

---

Published as a conference paper at ICLR 2025
Topology of cut distance
Topology WL measures
Topology of "edic" distance
6g not compact
compaet
C
relutively compact
C
(M((F))))) .) senki
[o((F) d), Pe
1-WL, MPNNS
A-L, WWNNS IWNS
Figure 6: Relevant graphon-signal topologies.
fW, + V(W.)) is continuous cut distance, and, as such, the above set can be interpreted as the continuous image of a compact set into a Hausdorff space. Hence, {r(w.)) C PPM)) is again compact, and distinguishing between the two sets is not crucial, remarked by Böker et al. (2023). Moreover, the pullback of this map yields a compact topology on the original graphon-signal space WS, which corresponds precisely to convergence of simple signal-weighter homomorphism densities w.r.t. trees. For k- WI. this slightly more subtle, as the map (W, + W is not
(W.f)
continuous in ón but only in dj, and the space (WSr, 81) is not compact. Therefore, one cannot apply the same argument to show that (L ((W.))(w..)) P(M*) is closed.
The "natural" tool modeling IWNs and k-WL continuous functions on compact would appear to be probability graphons (Lovász, 2012; Abraham et al., 2023), whose values are probability measures of the edge weights (i.c., Errrr----eenni graphs would converge a constant graphon of value po1 + (1 10-pppp -p)o. with o, indicating the Dirac measure at x here).
Simple WL (Böker, 2023). Böker (2023) also proposes simple k-WL test for graphons, which iteratively updates the colors using pre-defined set of "shift-likee" operators that explicitly parametrize simple homomorphism densities. They also remark that while simple vs. multigraph ho- momorphism densities yield the same notion of weak isomorphism (see also Theorem 3.2), simple k-WL is strictly weaker than &- for finite k. Analogous to $ D and $ F, would be straightfor- ward to extend the simple k-WL test graphon-signals and design higher-order WNNs based on the simple k-WL test which would be continuous in cut distance. We also note that the parametriza- tion of operators given by Böker (2023, 5.2) for simple k-FWL can be reduced from (k: + 1) to (A2 + 1)2* operators by resolving ambiguities. While both formulations are asymptotically equiv- alent, for small, feasible values of this would yield an improvement when implementing this method (20 vs. 36 operators to consider for h = 2). Yet, Böker (2023) contends that the definition of simple k-WI. is rather complicated and "artificial". In this work, however, we argue that cut distance discontinuity can be fixed and is, indeed, of limited practical concern.
51

---

Published as a conference paper at ICLR 2025
H EXPERIMENT DETAILS
In this section, we provide details for the toy experiments shown in Figure 1, Figure 2, and Figure 3. The purpose of these experiments is empirically validate the findings from $ regarding the distance discontinuity and the transferability of IWNs.
H.1
SETUP
Data. We keep the signal fixed at a constant value of 1 and look at the following different
graphons:
Erdós-Rényí (ER): W := 1/2 constant.
Stochastic Block Model (SBM): We take 5 blocks, each with intra-cluster edge probabili-
ties of 0.8 and inter-cluster edge probabilites q = 0.3.
Triangular: Here, W (xx2) = (xr + /)/2 (the sets {W 2 =),² E [0, 1] are triangles).
Narrow: ((x,y) exp
sin (m-w)²²
2
with 7 0.05.
From each of these graphons, {200, 400, 600, 800, 1000). We use a weighted graph of 1000 nodes sampled from each graphon approximation of the respective graphon itself (convergence of weighted graphs is typically much faster than of simple graphs).
sample 100 simple graphs of each of the sizes
Models. The following two models are compared:
MPNN: A standard MPNN with mean aggregation over the entire node set, used in the
analyses of Levie (2023); Böker et al. (2023).
2-IWN: An IWN of order 2, i.e., with basis dimension of 7.
For both models, we use simple setup of 2 layers, hidden dimension of 16, and the sigmoid function as activation.
Experiment. In Figure 2, plot the absolute errors of the model outputs for the sampled simple graphs in comparison to their graphon limits. Due to the cut distance continuity of MPNNs and the sampling lemma (Levie, 2023, Theorem 4.3), the MPNN outputs decrease as the graph size grows. While the convergence is slow, it is still significantly faster than the worst-case bound. This expected the considered graphons are fairly regular, and the convergence rates can be improved under additional regularity assumptions (Le & Jegelka, 2023; Ruiz et al., 2023). The IWN, however, is discontinuous in the eut distance (Proposition 5.1) and, as such, the errors do not decrease. In Figure 3, we further plot the difference between the 0.95 and 0.05 quantiles of the output distributions on simple graphs for each of the considered sizes. Notably, there are only minor differences visible between the MPNN and the IWN. This validates Theorem 5.2 and suggests that IWNs can have similar transferability properties as MPNNs (also beyond the worst-case bound), and continutyy suffices for transferability.
Code. The code used for the toy experiment is provided under https: htap::://githbbl com/ danlelherbst http//iigghhHrrre WNNs.
52

---

Published as a conference paper at ICLR 2025
H.2
PSEUDOCODE OF MODELS
H.2.1 MPNN
Algorithm MPNN forward pass
1: procedure N (MP E [0, 10, X R
2:
H +-+ X
3:
for tto S do
4:
H 4- 1/n W. H
5:
H LINEAR d._ (H)
6:
if < S then
7:
H 4 el e(H)
8:
end end for
9:
10: return 1/n Ei= H
11:
end procedure
H.2.2 2-IWN
Algorithm 2-IWN forward pass
1: procedure 2W- 1j,nj X E Raxdo)
2: H f- STACK ...
X X.O.) RRa
3:
for f 11o S do
4:
H < 2-2-WWNLINNEAR de 1-rd, (H)
5:
if < Stenn
6:
H e(H)
7: end
8:
end for
9: return 1/n² Eij=n Hij+
10: end procedure
Algorithm 3 2-IWN linear operators
1: procedure 2-IWN-LINEAR (s)
1-sd, (H E IRnnxxd xd.-1)
2:
operators in LE2--2
3:
H1 + 1/n EINSUM 1jjd-ii''
H 4Bx
4:
H2 +- 1/n EINSUM 'ijd->id'
Ø
5:
H3 + 1/n (EINUUM(12) (ijd >jj'' H 1.2
6:
H. <- 1/n HINSUM((1jd->jj) H 1.a
7:
H; + EINSUM( 13d->içd' H
8:
H6 < EINSUM( ijd->jidd, H)
9:
HG + 1/n². EINSUM(
H 2
10:
combine operators and return linear
H + STACK H .,, E 2 x7d,
11:
12:
return LINEAR Rd.-1 7d,-1-d, (H)
(8)
end procedure
53


Reviews:
[{"review_id": "q2a4UfAoFK", "reviewer": "Reviewer_MDWF", "summary": "This paper introduces Invariant Graphon Networks (IWNs), an extension of Invariant Graph Networks (IGNs), to analyze graphons (limit objects of dense graphs) and investigate their expressivity and continuity properties. IWNs leverage a subset of the IGN framework focused on bounded linear operators, allowing them to approximate graphon functions with an expressivity at least as powerful as the k-Weisfeiler-Leman (k-WL) test.", "questions": "Please see the weaknesses part.", "limitations": "", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper introduces Invariant Graphon Networks (IWNs) as an extension of Invariant Graph Networks (IGNs) specifically tailored for graphons, significantly enhancing their expressive power and providing new universal approximation properties for graphon signals. The work advances the theory in graph neural networks by rigorously defining IWNs and aligning them with theoretical results through the introduction of signal-weighted homomorphism densities.\n- The paper presents a thorough comparison of IWNs with existing graph neural networks, including Message Passing Neural Networks (MPNNs) and other IGNs, addressing size transferability and continuity aspects. It establishes that IWNs maintain at least the same expressive power as the k-Weisfeiler-Leman (k-WL) test, a known benchmark in GNN expressivity.\n- The authors have provided extensive mathematical proofs.", "weaknesses": "The absence of empirical experiments and practical application scenarios is the key weakness of this work. Without empirical validation, it is difficult to gauge how IWNs perform on real-world datasets, whether the theoretical advantages translate into meaningful results, and how they compare to established GNN models in practice. IWNs could be applied in scenarios where we need to capture dense graph structures or analyze graphs of varying sizes, which could benefit from their extended expressivity and approximation capabilities.\n- It is unclear whether the mathematical assumptions hold across diverse real-world datasets. This could limit the applicability of IWNs to more constrained datasets where these assumptions are valid.\n- IWNs are discontinuous with respect to the cut distance. This discontinuity implies that minor structural changes in the discrete graph could lead to significant output changes in the IWN, unlike Message Passing Neural Networks (MPNNs).\n- Adapting IWNs to discrete graphs might involve computational overhead, as the model is designed for continuous graphon spaces rather than finite graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c7UPbxVlYA", "reviewer": "Reviewer_fxhj", "summary": "The paper extends IGNs to the graphon-signal space by introducing Invariant Graphon Networks (IWNs). It provides a generalization of linear equivariant layers to measure spaces, specifically the unit interval [0,1]. The authors introduce signal-weighted homomorphism densities to extend the concept of homomorphism densities to graphon-signals. They prove expressivity results for IWNs, showing that IWNs of order $k+1$ are at least as expressive as $k$-WL for graphons and that they are universal approximators on any compact subset of graphon-signals. This extends the standard results from Maron et al. from graphs to graphons. The paper also discusses the continuity properties of IWNs, highlighting that they are discontinuous wrt the cut distance.", "questions": "- Could you discuss your non-continuity results better? What do you think are the consequences?\n- Also: how is it possible that the IWNs from Cai & Wang (2022) preserve convergence when sampling graphs from (sufficiently regular) graphon, but yours doesn't? Cai & Wang (2022)  also consider non-linearities, so is the reason that you consider graphon-signal?\n- 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. Could the authors discuss their technical contributions. \n\n\n## Additional Comments\nWhile the theoretical results appear to be correct (I didn't check all proofs) and generalize some results on graphon neural networks, it is not clear what the broader impact or significance is. I believe answering some of my questions would help to understand this as a reader. I am happy to increase my score if that is done.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper seems sound and the theoretical results extend the results from Cai & Wang (2022), Böker et al. (2023), and Levie (2023)\n- The authors connect their work to previous studies, such as those by Cai & Wang (2022) and Levie (2023), situating their contributions within the broader context of graph(on) neural networks", "weaknesses": "- It's not clear what the consequences for ML on graphs are\n- The non-continuity of IWNs wrt to sampling is mentioned and proved, but it is not clear what consequences it has. Also, the authors mention it as a rather negative point, however, this is not clear to me. Do you have an example where this property hinders size generalization? Or is it rather a worst-case property that doesn't affect IGNs in practice?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "k3EWVoYLVV", "reviewer": "Reviewer_1FQG", "summary": "This work proposes Invariant Graphon Networks (IWNs), which is an extension of Invariant Graph Networks (IGNs) defined on discrete graphs, to *graphons*. They study its separation power in relation to the $k$-WL test and its approximation capability for functions defined on graphons with vertex features.\n\nThey extend the notion of homomorphism densities (which, in turn, is an extension of *homomorphism counting*) from plain graphons to graphons with vertex features, and show that this notion can be used to determine the $k$-WL separation power of graphon neural networks. They then use it to show that their construction yields architectures at least powerful as the $k$-WL test, which in turn implies that it has universal approximation power of functions defined on vertex-featured fraphons.\n\nNotably, their construction is more economic than that of the discrete IGN counterpart, due to a reduced basis for linear layers, leading to slower asymptotic growth in the number of basis elements required.\n\nFinally, they expose a fundamental limitation of IWNs, and thus of IGNs, in that they are discontinuous with respect to the cut distance, which limits their applicability, and in particular their generalization capability, in certain learning scenarios. This is unlike MPNNs, which are continuous w.r.t. the cut distance.", "questions": "### Minor comments\n1. Ln. 140-141: \"Note that $\\delta_{\\square} \\leq \\delta_p$.\" - Does it follow from the L1-Lp inequality? This could benefit a short explanation or a citation.\n2. Ln. 151: \"If simple edges are further sampled...\" - unclear definition of G(W,X).\n3. Eq. (3), (4): Perhaps missing \"as $n \\to \\infty$\".\n\n\n### Suggestions\n1. Ln. 135-141: Some readers may not be familiar with the concept of cut distance. A brief explanation, perhaps as a short note or in a footnote, could benefit readers as well as help highlight your results on discontinuity.\n2. An intuitive explanation for the cut-distance discontinuity, possibly with an illustrative example, could help comprehension.\n3. Ln. 314 and the subsequent paragraph: To reassure the reader, I recommend stating explicitly that the dimension does not depend on $n$, and that the following theorem shows that this independence carries through to the case of graphons.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I believe this work offers significant contribution to the community, in that it provides useful theoretical tools to analyze neural networks on vertex-featured graphons, and these tools are already shown useful in this work in their universal approximation and their discontinuity results. The theoretical analysis of IWNs' separation power with the $k$-WL test could guide future architectural innovations or alternative GNN designs on graphons.", "weaknesses": "The paper does not provide numerical experiments. Nonetheless, it provides valuable theoretical contribution that can potentially explain empirical results, motivate the design of architectures and also lead to new theoretical insights on GNNs. While numerical experiments could have provided practical insights into the theoretical results, the theoretical results themselves have high potential for practical impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YK5yFwAoYf", "reviewer": "Reviewer_cdhd", "summary": "This paper studied Invariant Graphon Networks, a generalization of Invariant Graph Networks (IGN) from Maron (2018) to graphons. The authors show that Invariant Graphon Networks can be characterized using a subset of the IGN basis functions, due to additional discretization invariance. The authors proved that Invariant Graphon Networks of order $k+1$ are at least as powerful as the $k$-dimensional Weisfeiler-Leman test for graphons proposed in Böker (2023). These expressivity results extend the convergence results in Cai and Wang (2022), by making use of signal-weighted homomorphism densities as a new tool for the analysis. The authors show that Invariant Graphon Networks are typically discontinuous with respect to cut distance, in contrast to the continuity results of MPNNs defined on graphons (Levie 2023). This implies a negative result on the size transferability of IGNs.", "questions": "1. The definition of signal-weighted homomorphism densities (Defn 3.1) seems standard from the graphon literature, see for example homomorphism density on weighted graphs per equation 5-6 in [1], or various notions of homomorphism densities on multigraphs per chapter 17 in [2]. Can the authors remark the connections to these existing definitions?\n\n2. Invariance under discretization: As stated in Lemma 4.3 and Lemma D.1, invariance under discretization implies the output $L(U)$ is constant almost everywhere. This also leads to a much smaller dimension of the space of linear equivariant layers in Theorem 4.2. Does it make sense to consider relaxing the notion of invariance under discretization (i.e., approximate invariance). Will the authors expect this leads to stronger expressivity results than those stated in Section 5?\n\n3. Nontrivial IWN in Proposition 5.1: Proposition 5.1 (2) states that IWN is continuous with respect to the cut-distance if and only if the pointwise acitivation function is a linear function, where the authors treat it as \"trivial\" (Line 444). However, such linear IWN may not be trivial if the intermediate layers use higher-order tensors. Can the authors clarify this?\n\n4. The effect of pooling: In the current definition of Invariant/Equivariant Graphon Networks (Defn 4.4), the network consists of linear equivariant maps interleaving with pointwise nonlinearity. In the original works by Maron et al. [3], [4], an invariant pooling operation is often used in practice. Can the authors comment on the role of pooling on the continuity property of IGNs?\n\n\nReferences:\n\n[1] Borgs, Christian, et al. \"Counting graph homomorphisms.\" Topics in Discrete Mathematics: Dedicated to Jarik Nešetřil on the Occasion of his 60th Birthday. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. 315-371.\n\n[2] Lovász, László. Large networks and graph limits. Vol. 60. American Mathematical Soc., 2012.\n\n[3] Maron, Haggai, et al. \"Invariant and Equivariant Graph Networks.\" International Conference on Learning Representations. 2018.\n\n[4] Maron, Haggai, et al. \"Provably powerful graph networks.\" Advances in neural information processing systems 32, 2019.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper makes novel contributions on extending IGNs to graphons and studying their expressivity and continuity properties.\n\n2 .The paper is clearly written and well motivated.\n\n3. The notion of signal-weighted homomorphism densitiy is an interesting combination of the graphon-signal space in Levie (2023) and homomorphism densities in Böker (2023).", "weaknesses": "Practical consequences: The authors remark that since Invariant Graphon Networks (IWNs) are discontinuous with respect to the cut distance, IWNs can assign vastly different values to similar graph inputs (line 96). It will be nice to substantiate this remark using empirical evidence, either through observation made in existing works using IGNs or original experiment studies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lJUVVO4B0p", "reviewer": "Reviewer_p53n", "summary": "This paper proposes the Invariant Graphon Network (IWN) architecture for graphons as an extension of the Invariant Graph Network GNN architecture for discrete graphs. The paper's results are framed as a more natural extension and generalization of the related work of Cai & Wong 2022. The authors provide an overview of the relevant graphon theory and an in-depth introduction to a novel signal-weighted homomorphism density concept, providing a comprehensive characterization of weak isomorphism of graphon-signals using this definition, as well as showing a convergence equivalence to cut distance convergence. A generalization of linear equivariant layers is then introduced, through measure-preserving functions rather than permutations in the discrete case. Several central theorems are shown about this function space, including invariance under discretization, construction of a canonical basis, and analysis of dimension. The IWN architecture is then built and proven to be an instance of an IGN-small network. Continuity with regard to $\\delta_p$ is then shown, as well as lack of continuity for $\\delta_{\\square}$ unless the activation function is linear and thus expressivity is lost. Finally, expressivity of IWNs are shown in the sense that order $k+1$ IWNs are able to distinguish with the strength of $k$-WL for graphons.", "questions": "- You state that IWNs being only continuous for the weaker $\\delta_p$ distances, combined with the lack of compactness, prevent the approach from being applied to the entire space. Is there anything interesting to be said about limited regions of this space under the $\\delta_p$ distance? Is there any hope for an interesting bound in the $\\delta_{\\square}$ distance regardless of discontinuity, or is the behavior fundamentally unworkable?\n- Have you attempted to build some toy examples of the model, even without any sort of training?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- There is very thorough analysis of relation to previous work throughout this paper. This work's placement in the literature is clear.\n- Original contributions are outlined clearly and presented in a cohesive framework.\n- The ideas and results are very original, with several novel concepts defined. The definitions are shown to make sense through the strength of the theory, providing good evidence that these ideas are pointing toward a very useful framework.\n- The proof sketch narration is generally clear, and the full proofs in the appendices are nicely written. It is clear there was a good deal of care taken toward ensuring the quality of presentation for these main results.\n- In relation to the cited related works, the results shown in this paper are a significant contribution to the community.", "weaknesses": "- The discussion of the $\\delta_{\\square}$ discontinuity limiting transferability seems like it could be more complete. Especially as the definitions leading to this point are novel, it seems important to justify this not being a product of a definitional choice that could be reworked and rather a facet of the true underlying problem. Reading the appendix helped clear up my confusions here, but it would be ideal for the section itself to contain just a bit more of that insight.\n- Due to the heavy theoretical nature, this paper requires a very high degree of engagement to fully understand the stated results. It would be much easier to digest the main ideas on an initial reading with more time, even a short section, dedicated to showcasing some of the concepts you develop, perhaps in some experiments. While convergence experiments such as those in Cai & Wong 2022 are not relevant here, I think there are great possibilities for a showcase of the continuity result and the expressivity result which would really elevate the overall impact of the paper.\n\nOne small typo:\n- In Section 6, Paragraph 1, the phrase \"...that IWNs, as a subset their of IGN-small, retain...\" appears. Removing the \"their\" would fix this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)