On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks
Authors: Paolo Pellizzoni
Till Hendrik Schulz
Dexiong Chen
Karsten Borgwardt
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph neural networks
graph learning
Weisfeiler-Leman
VC dimension
Primary area: graph_neural_networks
TL;DR: A theoretical analysis of the sample complexity of GNNs with node individualization schemes.

Abstract: Graph neural networks (GNNs) employing message passing for graph classification are inherently limited by the expressive power of the Weisfeiler-Leman (WL) test for graph isomorphism. Node individualization schemes, which assign unique identifiers to nodes (e.g., by adding random noise to features), are a common approach for achieving universal expressiveness. However, the ability of GNNs endowed with individualization schemes to generalize beyond the training data is still an open question. To address this question, this paper presents a theoretical analysis of the sample complexity of such GNNs from a statistical learning perspective, employing Vapnik–Chervonenkis (VC) dimension and covering number bounds. We demonstrate that node individualization schemes that are permutation-equivariant result in lower sample complexity, and design novel individualization schemes that exploit these results. As an application of this analysis, we also develop a novel architecture that can perform substructure identification (i.e., subgraph isomorphism) while having a lower VC dimension compared to competing methods. Finally, our theoretical findings are validated experimentally on both synthetic and real-world datasets.

On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks
Paolo Pellizzoni
Till Hendrik Schulz
Max Planck Institute of Biochemistry
Max Planck Institute of Biochemistry
Martinsried, Germany
Martinsried, Germany
pellizzzoni@biochen wpg.mpg....
tschull2biochem.nng de
Dexiong Chen
Karsten Borgwardt f Max Planck Institute of Biochemistry
Max Planck Institute of Biochemistry
Martinsried, Germany
Martinsried, Germany
dchen@biochem. mwchheem.mp....... de
borgwardtt@bioche..nngp de
Abstract
Graph neural networks (GNNs) employing message passing for graph classification are inherently limited by the expressive power of the Weisfeiler-Lemme (WL) test for graph isomorphism. Node individualization schemes, which assign unique iden- tifiers to nodes (e.g., by adding random noise features), are a common approach for achieving universal expressiveness. However, the ability of GNNs endowed with individualization schemes to generalize beyond the training data is still an open question. To address this question, this paper presents theoretical analysis the sample complexity of such GNNs from a statistical learning perspective, em- ploying Vapnik-Cherven Serrk--Chhvvonniii (VC) dimension and covering number bounds. We demonstrate that node individualization schemes that are permutation-con -qquvaarinnniivviiiann result in lower sample complexity, and design novel individualization schemes that exploit these results. As an application this analysis, we also develop novel ar- chitecture that can perform substructure identification (i.e., subgraph isomorphism) while having a lower VC dimension compared to competing methods. Finally, our theoretical findings are validated experimentally both synthetic and real-world datasets.
Introduction
Graph Neural Networks (GNNs) have become a dominant approach in graph learning, leveraging the inherent structural information of graphs through multiple iterations of message passing. This iterative exchange of information between nodes allows GNNs to learn rich representations for both nodes and entire graphs. However, the expressivity of these models in the context of graph classification, i..., their ability to distinguish non-isomorphic graphs, is intrinsically limited by the capabilities of the Weisfeiler-Leman (1-WL) algorithm (63), heuristic used for the graph isomorphism problem [1 [64]. 1-WL is known to fail to distinguish certain classes of graphs, such as regular graphs [4]. Notably, GNNs are in general unable solve the substructure identification task (12), which is concerned with identifying subgraph patterns in the data at hand.
To address these expressivity limitations. higher-order GNNs 41 26 have been proposed. These models consider interactions among larger subgraphs or sets of nodes but often suffer from high
These authors jointly supervised this work.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

computational complexity, An alternative approach, which we call node individualizattin schemes, entails introducing perturbations, such as random noise, into node features to break graph sym- metries artificially. This technique enables message passing GNNs to become universal function approximators
[ without the computational overhead associated with higher-order GNNs. Several node individualization schemes have been proposed in the literature. Random Node Initializations (RNI) [52) add random noise to node labels to make them distinct with high probability, while Relational Pooling (RP) [42] and Colored Local Iterative Procedure (CLIP) [SS] partition nodes based on their labels and assign unique identifiers within partitions. A recent paper [20] proposes a general framework based
algorithms. Other approaches to increase the expressivity of GNNs relabel the graphs with structural or positional node encodings, such as node centralities, graphlet counts [9], Laplacian [16 62] 28, and random walk [17] encodings. These encodings give information about the graph topology, complementing the information obtained from message passing, but cannot guarantee universal expressivity in general.
Beyond expressivity, the sample complexity of GNNs 36 54 231, i.e., the amount of training data required for generalization on unseen data, is critical consideration to obtain effective graph learning models, and it has been recently linked to the I-WL expressivity [37]. Nonetheless, the sample complexity of GNNs with node individualization schemes and with structural or positional node encodings, which is of paramount importance in the understanding of the generalization power of maximally expressive GNNs, remains unanswered question.
This paper presents novel theoretical analysis of both the expressivity and sample complexity of GNNs endowed with node individualization and structural or positional node encodings, bridging the gap between the expressivity analysis of GNNs and statistical learning theory. Specifically, we examine the sample complexity of various node individualization schemes in the binary graph classification setting, offering insights that can guide the design of more effective graph learning models. We make the following contributions:
We demonstrate the utility of node individualization schemes even on graphs recognizable by the I-WL test, thereby enhancing the expressivity of shallow GNNs (Section B
We analyze the sample complexity of GNNs with various node individualization schemes using VCC-dmensiion-base based bounds (Theorem D. Based on our analysis, we develop a model architecture EGONN that is universally expressive for substructure identification and has low VC dimension (Section 4.2).
We provide sharper analysis based on covering-number bounds, leading to the design of novel node individualization schemes (Theorem[E) Our bounds rely on novel covering bound for Lipschitz functions [24], a result that is potentially of independent interest.
We substantiate our theoretical findings with experimental results on both synthetic and real-world datasets (Section5)..
By offering comprehensive analysis and practical guidance, this paper aims to enhance the un- derstanding and development of GNNs through the lens of node individualization, pushing the boundaries of what these models can achieve in terms of expressivity and sample efficiency.
1.1 Related work
Expressivity of GNNs Since the seminal works of [1 64 revealed the limitations of MPNNs due to their expressivity being bounded by the 1-WL test, research has surged toward developing more powerful GNNs. One prominent approach has been to design GNNs that emulate higher-order WL [26] or Folklore-Wi WL [10] tests, exemplified by k-GNNs [41 and k-FGNNs (35]. However, their computational and memory demands often hinder real-world applicability. To mitigate this, researchers have explored more efficient alternatives, leveraging graph locality and sparsity [40] 67
22). Another line of research involves subgraph GNNs, which break symmetry by transforming the original graph into modified subgraphs for GNN processing [1 48
For a more comprehensive
overview, readers encouraged to consult 39]
Node individualizations Individualization schemes have been proposed by several works [22 42 to enhance the expressivity of GNNs. GNNs with such schemes have been shown to be universal function approximators for invariant functions [ 5). Individualization schemes are also erucial on edge-level tasks [34] (53), where they break symmetry among different edge-orbits.
15 20

---

Sample complexity The generalization capabilities of restricted families of GNNs has been ad- dressed by means of VC dimension
[54]. Rademacher complexity [23 and PAC-bayesian approaches
129 33
Recently, 37 21 proposed VC-dimension bounds based on the number of 1-WI. color
classes The sample complexity of frequent subgraph identification has been addressed in [45]. Moreover, [46] [nd address the sample complexity of equivariant models using covering- number-based approach 25]. which is exploited also in [68] in an empirical setting. For a general overview on statistical learning theory, consult [36].
2 Preliminaries
In what follows, we define graph tuple G (Vg, LG), with Vo {1,.... ..........6e [Val) finite set of nodes, and Eg S { (uu o) u # u E Vc} a of undirected edges. We define the vertex-label function as Lg VG + L., with finite set of labels L. For the sake of simplicity,
consider
edges to be unlabeled. We define the neighhorhood of a node as ((v) = ={w E Va: : {v, w) E Fa)- We say that two graphs G and H are isomorphic, denoted
G = H, if there exists bijective
mapping π. VG + VH. called isomorphism, such that LC( = LH (T()), Ve E Ve and (π(य), [ E EH if and only if {u, 2 EGG The isomorphism relation induces equivalence classes, which we call unordered graphs [27]. The group of isomorphisms from G to itself is called the automorphism group (u) We denote a set of graphs with G, and if necessary, explicate the label set. We denote sets of unordered graphs as quotient sets g/ =. Moreover, we consider sets of graphs of bounded size, that is [VG| S mmaxx VG G. A function defined on graphs f: + R is called invariant if for any G = H, f = fHH.. A function from graphs to graphs f: 9 + G' is here called equivariant if for any G H, (G) = ((H).
G2 to
2.1 The Weisfeiler-Leman and Tinhofer algorithms
The color refinement algorithm, also known 1- Mheisfeiler-Lemane (denoted as WL) algorithm. is heuristic algorithm for the graph isomorphism problem. Let Co(v) La(v) E N be the initial color of node Vo. Then the algorithm updates vertex colors at iteration A: >>> 0 as
(v) HASH (Cx (v), ((Cx=1(w)) w (((()) E,
with HASH an injective map. Let p(k) (G) be the partitioning of VG based on colors after the k-th iteration of color refinement. Then, after at most [Va] iterations, the color partition stabilizes, i.e. (G))(G) = (G), vk 2 |Val. Two graphs are deemed k-hop WI.-isomorphic if {{Cx(v) V E Vol] = ((Ca(v): v DEE VHl}, and WL-isomorphic if it holds for k = [VG]. We denote this as G >WL Н. Note that G ~ H + G ~WL H, but the converse is not true. We call a graph G WL-amenable HH such that G + H. G XWL H.
Tinhofer [59] developed
sello-rrfinemeet-beee based algorithm, described in Section A.2 that returns an ordering of the nodes of graph. This is a canonical ordering on large class of graphs, called Tinhofer, which is strict superset of WL-amenable class (4]. The Tinhofer algorithm is instance of the individualizatioo--reneee
paradigm 20 on which several isomorphism solvers are based 3
2.2 Graph neural networks
Message passing graph neural networks (GNNs), given a graph G. iteratively produce for each node v E Va. at each level k = 1, ...., . K, the embeddings h E Rdd by taking into account messages coming from its neighbors (v).. More formally, the embedding of node v is updated as h = fupd (h--1, fugs ((th-1 update operations, respectively. The first layer of the GNN is fed with the initial node embeddings ho, e.g. one-hot encodings of the node labels. Finally, one can get a graph-level readout hG E [0, 1] by aggregating the output node embeddings via function fout. In [64 [1] it was shown that there exist injective functions fagx- Supa and fout yielding GNNs that are provably as expressive as color refinement. We provide examples for such architectures in Section A.I
(())))), where fagg and fupd are the aggregate and the
We denote as GNN k {GNN k.e, 0 E Q} the class of parametric functions formed by such model with K message passing layers and parameter space @ Moreover, we define GNNbin K. (G) =
[GNNK,e (G) > 0.5] and GNN bin K
[GNN
bin K,8, 0 E Q the class of predictors.
3

---

3 Node individualization schemes
In this section, we present general framework for node individualization schemes. Definition 1. A graph G = (V, F., LG) is called individualized if all node labels are pairwise distinct, that is (( o & V |V. Moreover, we define a graph as k-weakly individualized if all nodes have different colors after lc color refinement iterations, that is [[Cx(t): V IV].
Graph individualization is effectively achieved by assigning unique identifiers to nodes through a relabeling process. We formally define a relabeling function Rel Gc x 52 - G2
transformation ((V, E, L) + (V, E, L') that maps injectively the node labels from L : V - L to a new set of labels L' : + L. with L = L x C and L'(v) = (L(v),e), c), c C. This function preserves the graph's underlying structure (the nodes and edges). For the sake of generality, the relabeling function incorporates an additional argument w C N. This integer can be interpreted as source involved in the relabeling process (i.e., a random seed). For example, the relabeling function used in RNI [52], due to its pseudo- random nature, can generate -somooohee relabeled graphs even from two identical copies of the same graph if it is given two different random seeds. Moreover, note that node encodings such as the random walk [17 or the Laplacian [16] positional encodings can be cast as relabeling functions.
of
A relabeling function is an individualization scheme if, for each (G,w) E G x P. it holds that Rel(G,w) w) is a (possibly k-weakly) individualized graph. Moreover, for G E G. let Rel(G) := [Rel(G. (G, w)), w E EQ and let Rel(g) == {Rel(G)= G. G}.
Expressive GNNs on individualized graphs are well known to be universal approximators for functions over graphs [. In fact, even a GNN with a single message passing layer and MLP head is enough to provide universal approximator [I5]. We can generalize this result to w-weakly individualized graphs by noticing that k message passing layers, each simulating a WI. iteration, provide graph individualized by its node embeddings. The following statement formalizes this intuition.
Proposition 1. Let G - {0.1) be an invariant function and k 2 1. Then there exists @ θ suchh that GNN 1g (G) f(G) for every (k- 1)-weakly individualized graph G g.
The above proposition highlights the importance of node individualization schemes, not only for enhancing model expressivity, but also for managing model complexity. While GNNs are theoretically capable of representing arbitrary functions on WL-amenable graphs (which compose the majority of graphs 44). they might require large number of message-passing layers to achieve this. This phenomenon, known as under-reaching (2). can be problematic. GNNs with many layers can suffer from oversmoothing [K] or oversquashing 2 hindering their ability effectively distinguish graphs in practice. However, as Proposition [ demonstrates, endowing GNNs with a (possibly k-weak) individualization scheme can offer sufficient signals for graph discrimination with fewer message- passing iterations, thus mitigating these issues. In Section [.1] we experimentally investigate this assessment and show that it has implications in real-world scenarios.
4 Sample complexity bounds
In this section, we show a general framework to derive sample complexity bounds for GNNs endowed with relabeling functions, for graph-level binary classification tasks.
Let Daata be a joint distribution over a set of graphs 9 and binary labels Y = (0. 1}. Moreover, let D be a joint distribution over the domain of Ddata and integers Z C N. The integers w E Z model any
within the classification model /(G,w). ) In the following, we denote by W.). Given a loss function {(((x), y), our goal, in accordance with standard learning theory to bound the difference between the true risk R(f) and the empirical risk R(f):
Re(f) = -(ee.))))((((()) and RD.(f)= = Σ ((((.))...
where D = (10 y:)} ~ TT represents a training dataset of size m sampled i.idd. from D.
In Sections 4.1 and 4.2 we derive bounds to Re( - Rf)e()) based on the VC dimension, while in Section 4.3 we derive more refined bounds based on covering numbers.

---

4.1 VC dimension
Let {(f()), y) l[f(z) + y] be the 0-1 loss. Then if is the VC dimension of the hypothesis class, we have, with probability 1- over the dataset ~ D",, that supseF [Re(f) - RD e -
22d/m O ((Voog(1//)//// of functions on set.
33 Corollary 3.4]. We define formally the VC dimension of class
Definition 2. Ler X be a set and [f {0,1)} an hypothesis class. We say that F shatters F]
= (Z1.... 215)) if (ff
f F 2 2s1 Then, we say that (X, F) has VC
dimension F) = d the largest set S shattered by F has size d and to0 if the size of sets that can be shattered is unbounded.
In particular, we consider set X 9 Ω consisting of pairs of graphs and integers. Our hypothesis class F comprises binary classification functions formed by the composition of graph relabeling functions (such as individualization schemes) and GNNs that are as expressive as color refinement: GNN Rel {GNNKm bin K.0 o Rel: : GNN K.0 GNN }. setting K 7max to ensure expressivity. GNNs with color refinement expressivity may require number of parameters exponential in the maximum graph size Amax = maxgeg VVel [. which is a strong assumption we have to make. In the cases where the parameter count constraints the expressive power, the VC bounds from [37 Theorem 6] can be applied instead. The following theorem, which follows from [37 Proposition 2). relates the VC dimension to the WL-issomorphsmm classes of the graphs in Rel(G).
Theorem 1. Let Rel: G x Ω G' be a relabeling function. Then VC (g 22 GNN K Rel)
[Rel(G)/ mLL 1. If Rel is an individualization scheme, /Rel(G)/ OWL [Rel(G)/ ~
We provide specific bounds, proven in Section C.2 for relevant examples of relabeling schemes.
The RNI scheme perturbs with some random noise the labels of the nodes. In line with the analysis in the original paper, we suppose that the random noise, selected via w, takes values in finite set C. We then have that a graph G with nodes is mapped to O(C / (G))) relabeled unordered graphs. In the case of unlabeled graphs with n nodes, we then have that [RNI(G)/
Random Node Initializations 52
0 ()) 2())
() @((C)" (9]).
Let be a graph and let Ui...., Un be an arbitrary enumeration of its nodes selected via The simplest version of the RP scheme updates node labels as (v;) = (L(r)),). A more refined version the scheme partitions the nodes as (V,.... Ve} based on their labels and, letting V. (0t, so.,...., Uiiy. ), it updates node labels as f' ((i,,) (E(e;, IValt/ Aut relabeled unordered graphs. For unlabeled graphs with nodes, this amounts to having /RP(G)/ = = e(2(3)) O (G)). The 1-CLIP node individualization scheme is equivalent to RP on the node partition based on initial labels.
Relational Pooling 42] and CLIP [15]
Then, each graph can be mapped
Tinhofer algorithm Let G be graph and let Ui...., Un be an ordering given by the Tinhofer 59 algorithm (Section A.2 Then updating node labels as (((u;) = (f(v:), 4) yields a valid individualization scheme Tinhofer, that is an instance of the general individuullizaiion-reeeee framework given by [00]. Let the algorithm perform at most (i.e, for any choice of w) I individualiza- tion iterations graph G, let (Vi...., Vo } be a partitioning of the nodes of G based on their labels and let R max, [Val. Then we have that [Tinhofer (G)/ ~ < R Aut (G)l < n //Aut((G) (G'). In particular, shown in the following lemma, for data distributions restricted WL--amenable graphs, endowing a GNN with the Tinhofer individualization scheme does not increase its VC dimension.
Lemma 1. Let G be set of WL-amenable graphs. Then VC x2, GNN bin o o'inhofer) = | = K
In fact, the class of graphs for which the Tinhofer individualization scheme does not increase the VC dimension is the class of Tinhofer graphs [4] and is strictly larger than the WL-amenable class.
Positional and structural encodings Deterministic and equivariant encodings such as the random walk structural encoding [17 or adding graphlet counts 9 yield [Re((G] = G and therefore the
increase in VC dimension is only due the increase in the number of WL-iismmrphhimm classes, if any. The Laplacian positional encoding [16) is known not to be cquivariant in general (62).
5

---

Le.. there are graphs G1 = G2 for which Rel(G1.w) z Rel(G2, Therefore we have that [Rel(g)/ ww.. I > /// WW which leads to an increase in the VC dimension and further motivates the attempts to obtain equivariant Laplacian- based relabeling functions 62 28
Discussion Note that, in general, the number of relabeled graphs given by Rel is lower if the relabeling scheme is equivariant and if it does not depend on the second argument w. i.e., it is deterministic. For example, expressive GNNs endowed with the Tinhofer relabeling scheme, when applied to WL-amenable graphs with at most n nodes, have VC dimension that is lower by factor (nn) compared to equally expressive GNNs endowed with the RP scheme.
Finally, relabeling schemes that rely on the randomness introduced by the second argument w (c.g. randomized schemes) are often enhanced by resampling different w values at each epoch 42 [1]]. effectively performing data augmentation. As discussed in [56,, when the augmented dataset includes all possible transformations of each data point (in this case, all possible graph relabelings), the VC dimension of the model reduces to that of a transformation- -nvaariinn model. However, the number of relabeled graphs in our setting often grows super- super-exponentially with the maximum graph size, e.g., mmax! for RP, making it difficult to obtain enough samples for good generalization, as shown experimentally in Section 5.2] The theoretical analysis of sample complexity for randomized individualization schemes remains an open question we leave for future work.
4.2 Improved VC bounds for substructure identification
In this section, we showcase that developing sample complexity bounds and relabeling schemes with low VC dimension can guide the design of architectures tailored to specific tasks. In particular, a
relevant task that has been studied in past works is substructure identification [12 22 45 where the task is to decide if a graph pattern P appears as subgraph or induced subgraph of a query graph G, denoted hereafter as P E G. Notably, message passing GNNs are unable to solve the task in general 12). We provide a message-passing GNN architecture, similar to the one proposed [12 Section 5] that, paired with node individualization schemes, is provably expressive for substructure identification and with lower VC dimension compared to the ones presented in Section 2.2 The idea, as in many subgraph GNNs [14, 48| 8 50), is to transform the original graph into set of smaller subgraphs and feeding them to a GNN.
In particular, let the task at hand concern a subgraph pattern P of radius Ap minge V, ma Sew, where 8yw is the length of the shortest path from u to w. Let k-ego- net of node in graph G be the induced subgraph EGO., of nodes {u E VG &uv S k} at distance at most from v. Then, a model that able to recognize if P appears in any of the A p-ego-nets of the query graph will be able to solve the task. Note that there could be ego-nets that are not recognizable by a GNN alone (Lemma 6 so we individualize each ego-net with a function Rel to guarantee expressivity. Let then
he = GNN 1,0 (Rel(EGO,,,.A
E (0.1), hg = max h: E {0, VcVG
that is, we run I-layer GNN each individualized (potentially using some randomness from w) ego-net and we aggregate the results using max-pooling. We denote such parametric functions as Ap.0- We have the following results on the expressivity and the VC dimension of the model.
EGONNRel Ap,0-
Theorem 2. Let f :G- + {0.1} be f(G) = 1 E G}. Let Rel be an individualization scheme. Then there exists E O such that F.GONNee Ap.o(G) = S(G) for every G E G.
Theorem 3. Let G3 be the set of ego-nets of radius A of the graphs of G. Then VC(g X 2, EGGNN [Rel(g))/ l|
In general, GA is much smaller compared to G, especially for small A. This leads to the fact that, in general, Re) will be much smaller than Rel(G). Thanks to Theorem [ we then have that the VC dimension of EGONN Rel A. is in general lower compared to the one of GN ViN Rel. In particular, relabeling the ego-nets using a scheme with lower ( ~ |. such as the Tinhofer scheme, leads to lower VC dimension compared to schemes that would produce more relabeled ego-nets, such as RP or RNI. This theoretical result is also experimentally validated in Section
This approach clearly increases the space complexity compared to the standard GNN model. Indeed, if a graph G has n nodes, and each ego net has at most ne nodes and me edges, the disjoint union of the ego-nets of G has nn g nodes and nmg edges.

---

4.3 Covering numbers
The generalization bounds based on the VC dimension theory provide results that are useful only in restricted cases, e.g., when the task is substructure identification. Indeed, for a maximally expressive GNN model the VC-based bounds state that one should observe all the possible individualized graphs from the data distribution before the model can generalize. We provide an alternative analysis, following a cooeemaacee--oompeiitt--- bbased approach introduced in [G] and used in 23 for graph classification, which can lead to tighter results.
Let the margin function be M M(f(2),)) v) (2y - ()(2))))(()))))))))))))) E [-1,1]. Then the margin loss, given 7 > O, is defined as
M(f()),)) s s [0. 1]. ((1, v) + ()f()))) :f E F} be the set of margin losses, for each predictor f e Let Fr = GNNK o Rel. We then have (36). with probability 1 - 5 over the dataset D = ((zi, yi) ~ F + O C mmm11///mm) with (FF) the empirical Rademacher complexity of Fe on (see Definition B in the Appendix). In particular, given that P (a.y)~ (x) > 0.5] # v) S R(f), one can then bound the probability of making an error at inference time from the empirical loss. We then bound the empirical Rademacher complexity (FF)) via covering-number-based approach. Let D be the training dataset and let Fz|n = [fln: : S Fi) be the set of margin losses restricted to the dataset.
(())))) = 11 [M) < + MM)(()(())))
Dm that Jez (f( (f) (Fe)
Given a pseudometric space (X, dist) and a subset S C X, we call C S X an e- cover of S if max mincec dist (2, e) S and define the e-covering number of S as (XX,,, e, dist) = min[[C] : C is an e-cover of S}. i.e.. the minimum number of balls of ra- dius e required to cover S. Similarly, for finite S, we call C S X p-norm e-cover of S if (1/xIE Eex mincec dist(ar, e)p) 1/2 S 6 and define the p-norm e-covering number of S as A(() (X, e, dist) min[IC]
a p-norm c-cover of S). With slight abuse of notation, we let ((t))))(, e, dist) = NX( e, dist). In particular, we have that the p-norm e-covering number of metric space is monotonically increasing in p E N U {oo}.
Moreover, for finite set X and F S {f X - [0, 1]], we define the pseudometries Il f2l1p (1/1x Σ z [x( f2(x))))>>> V/2 for p 2 1 and Il f2llx = max (fi(z) f2())) By
Pollard's s bound [47 we then have that
RD S inf (a+ 2 N N n, a, Ih>//DD) a>0
We bound the covering number of the class of functions Fe by covering the space of graphs and assuming the Lipschitzness of GNNs, similarly to the approaches in [19] and [46]. In fact, we provide generalization of covering bound for Lipschitz functions [24] Lemma 5.2], that relaxes the Galmogorov-Tikhomiin
bound 58 Eq. 238], tailored to the aforementioned Rademacher bound.
Lemma 2. Let (X, dist) be psendometric space and S C X finite subset. Let F S (f: [o, 1}} be a set of
Let p. E N NU {+00], 2 2211 1. Then
log.N a, (pp) S log(L/a + 1) ((4) (s, 2C
a dist)
Theorem 4. Let Fe be the set of margin losses for predictors F= GNN Rel. Let Rel(D) = (G' Re,(G, w): (G, w. y) E D) be the graphs of the dataset after the relabeling, endowed with a pseudometric dist. Let functions in GNNK K be C-Lisschizz continuous with respect to dist.. Then
RD( < inf a>0
a aa+ (a+IDI-M 2log(1/a 1) 4NT0) (Rel(D), ar 40" ddist)
dist)
Theorem relies on the assumption that the GNN models are Lipschitz with respect to some pseudometric dist on graphs, such as the edit distance [35] 44), the Tree Mover distance [13 or the WWL distance 66). This assumption, albeit strong, is often taken when considering the generalization of GNNs [28] Note that, for small and arbitrarily complex GNNs, i.e. C >> 1, we have that the covering number is proportional to the number WL-isomorphic graphs in the relabeled dataset Rel(D), effectively retrieving the bounds obtained by the VC dimension. When GNN x is instead simpler, i.e. it has smaller Lipsehitz constant C, the space of graphs can covered with fewer balls, and we obtain better sample complexity.
7

---

(c)
G
60
Comparison between Tinhofer and Tinhoferw. Panel (a): Two graphs, where letters indicate initial node labels. The Tinhofer algorithm finds canonical ordering on the two graphs. Panel (b): The Tinhofer scheme concatenates the position of the node in the ordering to the node label. The relabeled graphs have edit distance 3. Panel (c): The Tinhoferw scheme concatenates the position of the node within its WI. color class. The edit distance remains 1, as in the original graphs.
Figure 1:
Discussion Let the graphs of the dataset DG = {G (G,w,y) v) E D} and the relabeled graphs Rel(D) {Rel(G, w) (G, w. E D) be subsets of the same metric space (G, dist). The results of Theorem 4 suggest that if labeling function does not increase much the covering number of the dataset, i.c. N/1 (Rel(D), e, dist) ~ N/() (Da, e, dist), then the model GNNK Rel would have roughly the same sample complexity as GNNK while being more expressive.
In particular, this can be achieved if the relabeling scheme maps pairs of graphs with low distance (e.g. dist(G1, G2) I c) to pairs of relabeled graphs with low distance. An example of such graphs at low distance could be a pair of graphs that differ only the label of node belonging a singleton color class, like graphs G and G2 in Figure [ These two graphs could be, for example, two molecules where an atom substituted with similar one, or two proteins where an amino-acid substituted with functionally-simit
one [4).
Driven by this intuition, we design (k-weak) individualization scheme, which we call weak Tinhofer scheme Tinhoferw. that relabels only few nodes. The scheme obtains an ordering Ul..... of the nodes via the Tinhofer algorithm. Let {Vi... Vc3 be a partition of the nodes of graph G into color classes after i color refinement steps and let V. (Vi..... Uiival) The scheme then relabels nodes by appending their position in the ordering within their partition as (((;;) (f(v;, ).j). For nodes that belong to singleton classes, which is common in graphs such as molecules or random graphs, no relabeling is necessary.
See Figure for a visual example of comparison between Tinhofer and Tinhoferw on the pair of graphs G1 and G2. We have, for a u E Va, that 36 VG, + Va, such that {Ø(v), ((w)} E Ec, LG, (v), Yu # u VG, and La, (T(U))
La (u). Then dist(G,, G2) would be given by the cost of substituting LG3 (T(u) with LG, (u). Consider the graphs produced by the Tinhoferw procedure. Here we have that the labels of nodes that matched in the original graphs still match in the relabeled graphs. By contrast, with the graphs produced by the Tinhofer procedure, the number of node labels that do not match could be arbitrarily large.
iff {v, w] EGG, LG,(((v)
This scheme ensures that the relabeled graphs are k-weakll individualized,, while yielding no increase in the VC dimension for WI--amenable graphs (Lemma]) [) and increasing the covering numbers only marginally. This in general yields better generalization, as shown experimentally Section 5.4
5 Experimental evaluation
In this section, we provide proof-of-concept experimental evidence about our theoretical results. In particular, Section 5.1 investigates the empirical expressivity of GNNs with and without individualiza- tion schemes, Section 5.2 and Section validate respectively the general VC dimension bounds and valivdda the substructure identification ones, and Section 5.4 explores the results on covering numbers. Details about the datasets, experimental setup, tasks and infrastructure are reported in Section E Code and datasets are available htttps://giitiii com http::///ghhhhaaloooooo/ggaaaaaa /oode wwwiiidddediiiuaanaalaaaaaa
5.1 Expressivity
To highlight the efficacy of individualization schemes in practical applications, we compare a GNN endowed with Tinhofer to ordinary GNNs on challenging datasets. particular, we consider subsets of the real-world datasets MCF-7 and Peptites-fure for which at least six message-passing iterations are necessary to distinguish pairs of graphs, and synthetic datasets Cycles-pis -pin and CSL-pin, for which nine, resp. five, iterations necessary. To compare the performance between
8

---

100
Cyclas-pin
accrcyvi
pln boumeoyi
Tenster 12 Layara)
Iemeter
GNN Lapera
202
432
000
800
1200
220
420
620
800
2000
Epocts
Epecta
100
Papriddss func
:00
Acursty
Kouunss i
NGF-7
60
Thnsder
Timeter
202
600
1000
250
800
2000
Epocts
Figure 2: Accuracy for GNN and GNN, Tinhofer over 1000 epochs on synthetic datasets Cycles-pin and CSL-pin and real-world datasets MCF-7
65
38
and Peptites-fune
57
RNI
RP
Tinhofer
89
50
50
CSL
102
3-reg
30
Surptes
Samgles
Somples.
Figure 3: Difference between test and training accuracy for GNNs with the RNI. RP and Tinhofer individualization schemes, on datasets of CSL and 3-regular graphs various sizes.
the two methods, we measure the models' capabilities to distinguish non-isomorphic graphs. Figure 2 shows the accuracy obtained by ordinary GNNs with a theoretically sufficient number of layers as well as a I-layer GNN endowed with Tinhofer. While the ordinary GNNs can achieve perfect score for both synthetic datasets, their learning process is slow and unstable. For the real-world datasets, it can be observed that ordinary GNNs do not achieve a score close to 100% within the tested 1000 epochs at all. These observations may be explained by the fact that the model has to learn to propagate structural information for several layers, possibly encountering oversquashing issues. In contrast, the GNN with Tinhofer converges faster and more stably with only a single GNN layer. The results particularly emphasize that the Tinhofer individualization scheme can improve the expressive power shallow GNNs, demonstrating the value of our approach practical scenarios.
5.2 VC dimension
We empirically evaluate the generalization bounds based on the VC dimension derived in Section 4.1 Recall that for individualization scheme Rel and set of graphs G. the generalization gap is bounded by the VC dimension d = [Rel(g)/ ~ |- We evaluate RNI, RP, and Tinhofer using 17, 41, 83 and 3-regular graphs of sizes 16, 32, 64. The task is to distinguish non-isomorphic graphs. Figure 3 shows the generalization gap with increasing numbers of permuted copies of the graphs in the training set. RNI and RP. which generate highly randomized individualizations, require several samples to generalize effectively, As graph size increases, the VC dimension increases, resulting in a greater generalization gap. Interestingly, Tinhofer perfectly learns the target function on CSL graphs with only a single copy of the graphs, as the individualization is in fact canonical.
datasets of circular skip link (CSL) 42 graphs of sizes
5.3 Substructure identification
To assess the expressivity and generalization of GNNs for substructure identification, we created four challenging datasets, each comprising 1000 unlabeled 3-regular graphs. The task is to detect whether

---

graphs contain the induced subgraphs: 3-cycle C3. 4-cycle Ca. S-cycle Cs. or complete bipartite graph K2,3. We tested GNNs with and without individualization schemes, along with our novel architecture FGONNAp,. As reported in Table I GNNs lacking individualization fail to distinguish between graphs. Those with RP or Tinhofer individualizations tend to overfit on training data but struggle to generalize. In contrast, EGONN A models generally exhibit smaller generalization gap. Not providing individualizations to ego-nets results in a small generalization gap, but often fails to fit the training data. RP individualization enables the model to fit training data but may lead to overfitting. The Tinhofer individualization yields, as predicted by the theory, the best performance.
Table 1: Train and test accuracies for the substructure identification task on 3-regular graphs.
Datasets
C2
C2
Cs
K2.3
GNN
Rel
Train
Test
Train
Test
Trai
Test
Train
Test
None
50.1 in.0
19.
50.6 .c.0
45.0 i9.4
50.1 10a
49.0
50.0 cs.s
50.0 100
GNNK
RP
100.0.0o
29.8
100.0
60.6
100.0
20.4
100.0
59.6
Tinhofer
100.0.0.
62.0
100.0
61.4
100.0
100.0
62.024a
None
100.0
100.0 ase
g4.2
73.6
92.3
89.
74.1 g2s
74.2
EGONN
RP
100.0 1o.
100.0 ...
99.6 Le.s
93.2
99.4
90.6
97.0
71.6
Tinhofer
100.0 10.9
100.0 9.0
99.4 10.0
99.6 10.
99.8 10.3
99.6 co.s
100.0 1c.0
100.0 ioa
5.4
Covering numbers
To validate the theoretical results on covering numbers from Section 4.3 we use two molecular (NCII and Mutagenicity) and two social network (IMDB-b and COLLAB-b) datasets. As suggested by the theory, we use as a proxy for the sample complexity the ratio between the covering number (for simplicity fixing 0.05, see Section[]]oo for complete results) of the relabeled dataset and the dataset size N = (Re(()) e, d As (pseudo-)metric. we use the distance used by the WWL We report N¹, together with the test accuracy and the difference between test and train accuracy, in T for GNNs with no individualizations with RP, RNI, Tinhofer and weak Tinhofer aaplacian-encodinn basedd relabeling. We observe that across datasets
kernel 60
individualiizaions, and with N strongly correlates with the generalization gap, confirming empirically the intuition provided by the theory. Moreover, we observe that on molecular datasets, that are easily recognizable by the WL test, individualizations don't help expressivity. On the other hand, on unlabeled datasets such as COLLAB-b. ordinary GNNs might struggle to converge to good local minima, and the additional information given by relabeling schemes usually helps. In fact, common in the literature 64 to relabel such unlableled graphs with, e.g., degree centrailities.
Table 2: Covering numbers and classification accuracies on real-world datasets.
Dunseets
NCII
Masagenicity Test
IMDD Text
COLLAD
GNN
Bel
x²
Test
Dif:
Dif:
R²
Dif..
Test
DiE:
Nose
0350
g3.8
16.1 2aa
0.156
g3.0
17.0.6
0.025
71.8
3.5.4
0.214
56.1
2.
RP
0.719
67.8
32.2.
0,746
70.9..a
0.443
65.4
33.0a
0.488
67.5
3.
GNN,
0.705
67.1
22.9.
0.717
73.1 1.
26.
0.500
62.4
37.6.50
0.547
56.8
13
Tinhofer
0.677
28.4..
0.697
24.9
25.
0.266
70.0
19
0.471
648
20g
Taahoey
0.20
21.
180
0,252
g2.6
17.
0.133
24.
21.3
0.110
39.5
136
LPE
0,589
47.3
22.-1xx
0.485
46.2
23.8
0,271
68.0
21.1-x4
0.409
74.6
21.
Nore
0,090
$1.6
18
0.156
a1.5
1844
0.025
71.4
22.44
0,214
35.3
0.0a.
RP
0.719
67
3266.
0,746
71.2
28.8.
0.443
638
34.6
0.488
18
GNN,
0.705
52.0..e
0.717
g2.7
27.3 pm
0.580
63.0
364
0.547
g2.1
1962
Tinhofer
0.677
22.
26.9.
0.697
26.9146
0.266
68.6
20.5
0.471
75.2
19.5
Taahofr,
0.20
21.8
18
0.252
81.2
188
0:133
1962
0.310
30.8
122
L.P
0.589
26.4
23.521
0.485
24.6110
0.271
68.4
20.7
0.409
75.
199
6 Conclusion
In this paper, we developed novel sample complexity bounds for graph neural networks endowed with individualization schemes. Several research directions are left open for future work, including the analysis of data augmentation for individualization schemes via resampling, and the development of tighter covering bounds for specific model architectures. We envision that this work will inspire the development of new, practical graph learning models that are both theoretically sound and empirically effective, ultimately ad advancing the field of graph representation learning.
10

---

Acknowledgements
The authors would like thank Dr. Janko Sattler, Philip Hartout and the reviewers for their feedback.
References
[1] Ralph Abboud, ismail IIkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power graph neural networks with random node initialization. In Proceedings of the Joint Conference on Artificial Intelligence (IJCAT), 2021.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations (ICLR), 2021.
[3] Markus Anders and Pascal Schweitzer. Engineering a fast probabilistic isomorphism test. In Proceedings of the Workshop on Algorithm Engineering and Experiments (AI.ENEX), 2021.
[4] Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. Graph isomorphism, color refinement, and compactness. Computational Complexity, 26:627-685, 2017.
[5] Pablo Barceló, Egor V. Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva, The logical expressiveness of graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[6] Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaiized margin bounds for neural networks. In Advances in Neural Information Processing Systems (NewrIPS), 2017.
[7] Christoph Berkholz, Paul Bonsma, and Martin Grohe Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60(4):581-614, May 2017.
[8] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan. Michael M Bronstein. and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations (ICLR), 2021.
[9] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trans. Pattern Anal. Mach. Intell., 45(1 66657666,6 2023.
[10] Jin-Yi Cai, Martin Fürer,, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4)3899-410, 1992.
[11] Semih Cantürk, Renming Liu, Olivier lapointe-GGanéé, Vincent Létoureau, Guy Wolf, Dominique Beaini, and Ladislav Rampášek. Graph positional and structural encoder. In International Conference Machine Learning (ICML), 2024.
[12] 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, pages 00383-10395, 2020.
[13] Ching- Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks, Advances Neural Information Processing Systems (NeurIPS), 2022.
[14] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[15] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Joint Conference Artificial Intelligence (IJCAI), 2020.
[16] Vijay Prakash Dwivedi, Chaitanya Joshi, Anh Tuan Lun, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research (JMLR), 24(43):1- 48, 2023.
[17] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations (ICLR), 2022.
[18] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems (NeurIPS), 35:22326 22340, 2022.

---

[19] Bryn Elesedy. Symmetry and Generalisation in Machine Learning. PhD thesis, PhD thesis, University of Oxford, 2023.
[20] Billy Joe Franks, Markus Anders, Marius Kloft, and Pascal Schweitzer. A systematic approach to universal random features in graph neural networks. Transactions on Machine Learning Research, 2023.
[21] Billy Joe Franks, Christopher Morris, Ameya Velingker, and Floris Geerts. Weisfeiler-leman at the margin: When more expressivity matters. In International Conference on Machine Learning (ICML), pages 13885-13926, 2024.
[22] Fabrizio Frasca, Beatrice Bevilacqua. Michael Bronstein, and Haggai Maron. Understanding and extending subgraph guns by rethinking their symmetries. Advances Neural Information Processing Systems (NeurlPS), 2022.
[23] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), pages 1439-3430, 2020.
[24] Lee-Ad Gottlie,, Aryeh Kontorovich, and Robert Krauthgamer. Efficient regression metric spaces via approximate lipschitz extension. In Edwin Hancock and Marcello Pelillo, editors, Similarity-Based Puttern Recognition, pages 43-58, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[25] Florian Graf, Sebastian Zeng. Bastian Rieck, Mare Niethammer, and Roland Kwitt. On measuring excess capacity in neural networks. Advances in Neural Information Processing Systems (NeurIPS), 15:10164-10178, 2022.
[26] Martin Grohe Descriptive complexity, cononisation, and definable graph structure theory, volume 47. Cambridge University Press, 2017.
[27] Frank Harary and Edgar M Palmer. Graphical enumeration. Elsevier, 2014.
[28] Yinan Huang, William La, Joshua Rohinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graph neural networks. arXiv preprint arXiv:2310.02579 2023.
[29] Haotian Ju. Dongyue Li, Aneesh Sharma, and Hongyang R Zhang. Generalization in graph neural networks: Improved pac-hayesian bounds on graph diffusion. In International Conference Artificial Intelligence and Statistics (AISTATS), 2023.
[30] Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and validation of toxicophores for muta- genicity prediction. Journal of medicinal chemistry, 48 1:312-20, 2005.
[31] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neumann. Benchmark data sets for graph kernels, 2016. htttp///graphkeereelss cs. tu su-dortmund de
[32] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:I412.66 141.66900 2014.
[33] Renjic Liao, Raquel Urtasun, and Richard Zemel. A PAC-hayesian approach generalization bounds for graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[34] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky, Graph normalizing flows. In Advances in Neural Information Processing Systems (NeurlPS), volume 32, 2019.
[35] Haggai Maron, Heli Ben- Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[36] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
[37] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. International Conference on Machine Learning (ICML), 2023.
[38] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In /CML 2020 Workshop on Gruph Representation Learning and Beyond (GRL+ 2020), 2020.
[39] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far, The Journal of Machine Learning Research. 24(1): 15865 151111155651166,...1111111131131 2023.
12

---

[40] Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-aware permutation-equivaiiant graph networks. International Conference on Machine Learning (ICML), 2022.
[41] Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Fric Lenssen, Gaurav Rattan, and Martin Grobe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, 2019.
[42] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference Machine Learning (ICML), pages 4663 4673. PMLR, 2019.
[43] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), 2020.
[44] Paolo Pellizzoni, Carlos Oliver, and Karsten Borgwardt. Structure- and function-aware substitution matrices via lcarnalle graph matching. In Research in Computational Molecular Biology, 2024.
[45] Paolo Pellizzoni and Fabio Vandin. VC-dimension and rademacher averages of subgraphs, with applications to graph mining. In International Conference on Data Engineering (ICDE), 2023.
[46] Mircea Petrache and Shubhendu Trivedi. Approximatioo--geneeaee generalization trade-off's under (approximate) group equivariance. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023.
[47] David Pollard. Empirical processes: theory and applications. Ims, 1990.
[48] Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. In Advances in Neural Information Processing Systems (NeurlPS), 2022.
[49] Kaspar Riesen and Horst Bunke. IAM graph database repository for graph based pattern recognition and machine learning. In Niels da Vitoria Lobo, Takis Kasparis, Fabio Roli, James Tin-Yau Kwok, Michael Georgiopoulos, Georgios C. Anagnostopoulos, and Marco Loog, editors, Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshop. SSPR SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings, volume 5342 of Lecture Notes in Computer Science, pages 287-297. Springer, 2008
[50] Dylan Sandfelder, Priyesh Vijayan, and William L. Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). 2021.
[51] Ryoma Sato, A survey on the expressive power of graph neural networks. arXiv preprint 20X3::2003.04077, 2020.
[52] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks.
In Proceedings of the SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021.
[53] Victor Garcia Satorras, Emiel Hoogeboom, and Max Welling. E (n) equivariant graph neural networks. In International Conference on Machine Learning (ICML), pages 9323 9332. PMLR, 2021.
[54] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapmik-chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-259, 2018.
[55] Francese Serratosa. Redefining the graph edit distance. SN Computer Science, 2(6):48,, Aug 2021.
[56]
Han Shao, Omar Montasser, and Avrim Blum. A theory of pac learnability under transformation invariances. In Advances in Neural Information Processing Systems (NeurIPS). volume 35, pages 13989--10011, 2022.
[57] Sandeep Singh, Kumardeep Chaudhary, Sandeep Kumar Dhanda, Sherry Bhalla, Salman Sadullah Usmani, Ankur Gautam, Abhishek Tuknait, Piyush Agrawal, Deepika Mathur, and Gajendra PS Raghava. Satpdb: database of structurally annotated therapeutic peptides. Nucleic acids research, (4(DI):D111-DDI 2016.
[58] Vladimir M Tikhomirov. s-entropy and e-capacity of sets in functional spaces. Selected Works of AN Kolmogorov: Volume III: Information Theory and the Theory of Algorithms, pages 86 170, 1993.
[59] G. Tinhofer. A note on compact graphs. Discrete Applied Mathematics, 30(2):253-264, 1991.
[60] Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-Lópzz Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-Iehmar graph kernels. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
13

---

[61] Nikil Wale and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. In Proceedings the 6th IEEE International Conference Data Mining (ICDM), pages 678-689. IEEE Computer Sociely, 2006.
[62] Haorui Wang, Haoteng Yin, Muhan Zhang. and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. International Conference on Learning Representations (ICLR). 2021.
[63] Boris Weisfeiler and Andrei Leman. The reduction graph to canonical form and the algebra which appears therein. 1968.
[64] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR). 2018.
[65] Xifeng Yan. Hong Cheng. Jiawei Han, and Philip S Mining significant graph pattems by leap search. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 433 444, 2008.
[66] Pinar Yanardag and S. V. N. Vishwanathan, Deep graph kernels. In Longbing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams, editors, Proceedings of the ACM International Conference Knowledge Discovery and Data Mining (KDD), pages 1365 1374. ACM, 2015.
[67] Bohang Zhang, Guhao Feng, Yiheng Du, Di Hc, and Liwei Wang. A complete expressiveness hierarchy subgraph gnns via subgraph weisfeiler-Iehma (ICML), 2023.
International Conference on Machine Learning
[68] Sicheng Zhu, Bang An, and Furong Huang. Understanding generalization benefit of model invariance from a data perspective. Advances Neural Information Processing Systems (NeurIPS), volume 34, pages 4328-43444444 2021.
14

---

A Additional details
A.1 Expressive graph neural networks
In it was shown that there exist injective functions for Sagg. Jupd and the graph-level readout function that lead to GNNs that are provably as expressive as color refinement.
An example of such functions that leads to models that are provably as expressive as color refinement denoting as concatenation, is
N mlp
mlm(11)
(1
1 R.d. (EN(U)
Σ
lig
mlp
Σ VEVV
h
[0. 1j.
In fact, provided that different node labels are encoded to linearly independent h even the following simpler architecture, denoting with nonlinear function such as ReL.U, is expressive color refinement
h WW W Σ
h (E)(2)
E Rd
hgg mlp Σ
h E [0, 1].
BeVo
A.2 Tinhofer algorithm
The Tinhofer algorithm 55 returns an ordering of the nodes of graph. particular, works as follows.
1. Run color refinement on G and obtain the stable color partition P(G).
2. Given the partition P(G)
If all nodes belong to a singleton color class, return the ordering of the nodes based on the lexicographie order of their colors.
Else, pick the color class with at least two nodes with the lexicographically smallest color. Individualize one arbitrary node in such class by assigning it the smallest unused color. Then, go to step 1.
Clearly, the algorithm will perform at most Vol individualization steps. In fact, for several classes of graphs a constant number individualizations suffices [00] Therefore, the algorithm can run in polynomial time.
In fact, the Tinhofer algorithm can be generalized to the Individualization -etettmmmen-eeeeeeenttt scheme [20 B), where the refinement operation and the selection of the nodes to be individualized can be more general than the ones used Tinhofer.
Computing a canonical stable partition on a graph G can be done in O((Val + FFal) log Va ) Theorem 9]. Moreover, the Tinhofer algorithm can also be implemented so that takes (([VV) [Eal) log Vcl) time 7 Theorem 10].
B
Limitations
This paper provides sample complexity results for graph neural networks with relabeling schemes, but nonetheless leaves several research directions open. First, most individualization schemes benefit from resampling at random the graph individualizations at each epoch, effectively performing data augmentation. Studying the theoretical properties of such techniques would be major step forward understanding the practical performance of GNNs with individualization schemes. Secondly, our results covering numbers are based on the strong assumption of Lipschitzness of GNN models with respect to some metric on graphs. Alleviating such assumptions would yield stronger theoretical results. We hope that these open questions will foster new research efforts in this field.
15

---

C Definitions and Lemmas
In this section, we provide formal definitions and lemmas, which were only informally described in the main paper.
C.1 Definitions
Definition Let X be a and S (Ii,...,IA)) sample of elements from X. Let J C CU: X - [0, }]} be a family of functions. Let also oi, = =,.... be independent and identically distributed Rademacher random variables, i.e. taking value or -1 with probubility 1/2. The empirical Rademacher complexity is the quantity
(s = E.
sup orr((aa) fEF i=1
where E,g denotes the expectation taken only with respect to the og 's, conditionally on the sample S.
C.2 Lemmas from Section 4.1
Lemma 3. Let RNI be the RNI individualization scheme (522] with random noise taking values in C and G graph with n nodes. Then [RNI(G)/ ~ =[(((/|Aut())) If G is the of of unlabeled graphs with n nodes, then [RNI(G)/ = = -
Proof. In line with the analysis in the original paper, we suppose that the random noise, selected via w, takes values finite set C. Each node of graph G can take (C] values. Therefore there (((C)") different labelings of the graph. To obtain the number of unordered graphs, we divide by the number of automorphisms of G. Moreover, the G of unlabeled graphs with nodes contains O i 2() unordered graphs. Intuitively, is obtained from the fact that for each of the (2) pairs of nodes one can either have an edge or not, and by then dividing by the number of node permutations. Formally, this is obtained via Polya's enumeration [27). A fraction of 1 o(1) of unordered graphs only have trivial automorphism 27). Therefore, we have the claim by summing a contribution of "( over all such graphs.
Lemma 4. Let RP be the RP individualization scheme 442 and G graph with partitioning (Vi.... Vel of the nodes based on their labels. Then (R) ~ ITT (dlD//AAu(())) is the set of of unlabeled graphs with nodes, then [R(())/ ((2(3))
Proof. Each partition V; can take [V] different orderings, for total of IT... |V]l different labelings of the graph. To obtain the number of unordered graphs, we divide by the number of automorphisms of G. Moreover, the set G contains O 2 unordered graphs, and fraction of 1 o(1) of those only have the trivial automorphism (27]. Therefore, we have the claim by summing a contribution of (n!!) i.e., the number of possible different labelings of each graph, over all such graphs.
Lemma 5. Let Tinhofer be the Tinhofer individualization scheme and G graph with partitioning (Vi...., Vel of the nodes based on their labels. Let the algorithm perform at most (i.e, for any choice of w) individualization iterations on graph G, let {Vi...., Vol be partitioning of the nodes of G based on their labels and let R = max, Vel. Then we have that (Tiihofer(GG (G))/ R! A /|/Att(()] n. /1/|\ut((G)
Proof. After each individualization and color refinement iteration, the color class partition of the nodes of G is a refinement of the partitioning . Vc } of the nodes of G based on their labels. At each individualization step, the algorithm can choose to individualize node in the lexicographically. smallest stable color class, which has at most R max, [V] nodes. Therefore we have at most
R! labelings of the graph and we divide by the number automorphisms to obtain the number of distinct unordered graphs. In particular [Tinhofer(G]) (G)) < R Aut((G) < n' /lAut(G)).
L
16

---

Figure The gadgets P1 and Ps from Lemma 6
C.3 Lemmas from Section 4.2
Lemma 6. Let ld be the identity relabeling fanction. There exists pattern P and pairs of graphs G1 & G2 such that P G1, P & G2 and such that they camnot be assigned different outputs by EGONN
Proof. The graphs P1 and P2 depicted in Figure are non-isomorphic. Let the pattern of interest be P Pj. Then åp
Consider graph G. Let G1 be the graph obtained by connecting all nodes of G to the node of P1 and G2 by connecting all the nodes of G to node v of P2, making sure to select such that & G2. Meanwhile, we have that E G1 by construction. Then for any A-eeo-net E, of Gi there is a Ap-ego-net Eg of G2 such that Ej =WL Ez. Therefore, EGONN/ Ap will assign the same outputs to both G1 and G2.
C.4 Lemmas from Section 4.3
Lemma 7 (Pollard's bound 471). Let X be a finite set and F C ( X - [0, 1]}. Consider the
pseulometric F defined [[ f2ll1 1/1x Exex (f(()) [2(x)) Then
(x) < inf a + WF
a>0
Proof. Let C C (f X 0, [] be a-cover of (F, I1I) of size ((F,a,ll) II).. Let also
Cf EC Ce be such that [[ c S a. Then
Ax
sup
1
Σ aof())) S
feF |X|
x.E
< E
sup SET |X|
1
Σ
oi(s(xx)) cx(x)))
+E
sup fet
1
Σ
oser(as)
$
X
#E
2,Ex
22log |C1 XX
<a+B
sup cEC
Σ
o,c(zz)
< +up sup
X
ecc
x,E
where the last inequality follows from Massart lemma and the fact that the functions in take values in [0, 1].
D Missing proofs
In this section, we provide the proofs that were omitted from the main paper.
D.1 Proofs from Section 3
Proposition 1. Let f: + 10.1) be an invariant function and k 2 1. Then there exists 0 E O such that GNNNib bin k. (G) f(G) for every (k 1)-weakly individualized graph G G.
17

---

Proof. We consider the class of GNNs described in Section A.1 with depth K = maXGeg \Va and VG be one-hot encoding for its label (v). for any G E G. Applying [41] Theorem 2] to the disjoint union of the graphs in g, we have that there exists a function GNN E G can simulate A steps of color refinement for all graphs in G. Therefore, from the definition of (A: - 1) 1)-weklly individualized graph,
large enough width [T]. Let the initial node embedding hy
after (k- 1) message passing layers, all the node embeddings hā-1 E {-1.1} 11 of nodes E Vo computed by GNN will be distinct, that is, the graph is individualized. Then this individualized graph is WL amenable and I color refinement iteration suffices to identify the graph [4] Then by [3 Proposition 9], any invariant binary function on be realized.
D.2 Proofs from Section
Theorem 1. Let Rel 9 - G' be a relabeling function. Then VC (g Ω GNN o Rel [Rel(G)/ =WL If Rel is an individualization scheme, [Rel(g)/ =WL [Rel(g)/ =
Proof. We consider the class of GNNs described in Section A. with depth K maxGeg |Va and large enough width [4]]. Let the initial node embedding h of u E VG be a one-hot encoding for its label Lt(v), for any G
Let d : RRe(g)) SwL. J. We prove the upper bound, following the argument of [37 Proposition 8]. Let by contradiction be a (multi)set of d + elements that can be shattered. Then by pigeon hole, two elements (G, w), (G', (w") E S must be mapped by Rel to graphs belonging to the same WL-isomorphism class. Then, by equivalence of GNN K to color refinement 41 Theorem 1J. these
K two graphs are always mapped to the same value by GNN o Rel. Then, there is no set of d +
elements that can be shattered.
We then prove the lower bound. Let S' be set of d graphs that are representatives of the WL- isomorphism classes contained in Rel(g)/ zWL. For G' E S', let Rel Rel = (G.w) E G x Ω such that Rel(G,w) w) = G'. Note that, since Rel is injective in the first argument, the graph G is unique. On the other hand, w may not be unique. We take any such w with a deterministic rule (e.g- the minumum). Moreover, since restrict the domain to S", this inverse always exists. Let then S [Rel (G"): Proposition 9].
"G'): G' E S'). We have that [S] SS d and it can be shattered by 37
When the graphs in Rcl(g) are individualized, WL-isomorphism class correspond to isomorphism classes which proves the second claim.
Lemma 1. Let G be a set of WL-amenable graphs. Then VC (a x S2 GNN o Tinhofer) =
|G/ ~
Proof. Tinhofer algorithm yields a canonical ordering on WL amenable graphs 4 therefore we have [innhofer(G) vG g. Then, by Theorem I we have the claim.
D.3 Proofs from Section 4.2
Theorem 2. Let f 9 + 10,1} be f(G) = 1 1 G).
Let Rel be an individualization scheme. Then there exists E such that EGONN (G) = for every e G.
Proof. By Proposition we have that GNN, o Rel is universally expressive. In particular, it can take value 1 if F.O..G.A, and otherwise for each possible FGO,,G.Ap. Then he maxveve hego 1 if and only if P G.
11
Theorem 3. Les GA be the set of ego-nets of radius A of the graphs of G. Then VC(g x Ω RGl A & (Rel(A))/ l.
Proof. We prove the upper bound. Let d = (R))Ga)/ ~ Suppose by contradiction that there is set ...... Ga+1 of d + graphs that can be shattered. In particular, each graph G; must have an ego net H, E G, that does not appear in any other graph, i.c. H, & Gj, vjj + Indeed, suppose that for
18

---

each ego-net H., EGO,, of graph G, we have that Ha, Gj for some j # i. Then to be for some v. But since H., E G. we have that ha, = 1 and the assignment of G3 to and all the other graphs to 0 cannot be achieved. Therefore, each graph G; must have an ego-net H; & G; that does not appear in any other graph. Then there must be d + 1 distinct ego-nets, which is a contradiction.
able to assign hG. 1, must hold that GNN1, (H,,i)
In fact, there are sets of graphs 9 and radii A for which the VC bound above is almost light. This lower bound can be proven by taking a datasets of k star graphs with maximum degrees 2, k + I and A = Each graph has an ego-net that is unique to the graph, i.e,, the graph itself, so the set be shatlered. Moreover, [Rel(a)) = =|= = 1.
Remark 1.
D.4 Proofs from Section 4.3
Lemma 2. Let (X, dist) be a pseudometric space and S C X
a finite subset. Let F S S
[0, ll} be set of C-Lixcchitz functionns, Let p, q NU (+x}) 2 p 2
Then
(F, (lp) S. (log(1/++1) Nww) (s. 20
a
dist)
Proof. We construct a covering of the space F. Let + xc. Let S. { ( Ty a p-norm a/ a/2C-covering of (S, dist) of size A/w) (S, 20, dist). For point x S, let its center be c(z) = argming,es,, di.tt,, æ;). Recall that p-norm e-covering C' of a finite set S is such that (V/s) Exes (ist(ar,c())) 1/2 SC
Let F = (f: function f. S - {(k + 1/2)a: : == =0..... aa }} such that f((x) = fi(c(z)) Vr E S. Then let F be the set of maps [f f (EF), F}. We have that [F| S (1/a + 1)", as the functions can take up to (1/a + 1) values over points, and [ [F). We show that f is indeed a-covering of F in norm || 1lp-
[kk + 1/2)a: k k= 0, =,.....aaa 1)- For f. F, we construct associated
Let f F. Let f E f be such that Vo E Sa, If(x) - f(x) s a/2, which always exists by construction. Then,
1/8 Σ f(x) -(O))) -(o))
||f f12
#E8
f((=)) ((Gd))))()) (((e)))((()))(ato)))) R(cta)))) 1/-
1/8
ZE8
1/
V/ S (2//2+ 0P2 .18 Σ dist(a, c(x))) d(s)(),((=))))
Σ (a/2 ((iss(( ((000))))(((00000
1/8
ZE8
ZE8
< (ao/2- 0-20- -'2 1/7 a.
In particular, we used that fact that (a + 6) < 2 + bP) for p 2 1, which follows from Jensen's inequality with f(x) = r².
For p oc, we have that S. is a a //CCernv of (S, dist) of size r = N (S, a max.es dist((r, < a/2C. We build & as before. We then have
20, dist), and
Ilf - flloc= = max (x)) - f(x)) s max (f((x)((())))))))))))))))))))))) - f(c(x))) If(x) - f(c(x)) (f()))))) f(c(=)) <
#E8
#E3
S a/2 Cdiss(( o(x)) + +05a.
Finally, noting that A/ (S, 20, dist) 2 (p (S, 20, dist) for each y 2 p. we have the claim.
Theorem 4. Let Fe be the set of margin losses for predictors FF == GNNK Rel. Let Rel(D) (G' Re, w): (G, w. n) E D) be the graphs of the dataset after the relabeling, endowed with pseudometric dist. Let functions in GNN be C-Lipschitz continuous with respect to dist. Then
(D & inf [ (D+1DI- [DD 1/2 2log(1/a++ 1) 4V(11) (Gn.e', 40' asa
ay dist)
19

---

Proof. We have that RF( S infaso (a+ bound the covering number of the loss functions.
l1)///D) by Lemma 7 We
Let (el(D) [Rel(G,,) w) (G) E D} be the graphs of the dataset after the relabel- ing, endowed with a pseudometric dist. We endow D with a pseudometric dist defined as dist ((G, w., y), (G', w', y')) d (Rel(G,w). R..(RRll," Rell("") w/)) y yf and +00 otherwise. More- over, if functions in GNNK are C-Lipschitz on Rel(D) then the functions in F are C-Lipschitz on D by construction. Then, functions {(f(z). y) E Fe are 2C/y-Lipschitz on D.
Let also r be the 1-norm covering number of Rel( D) and S the set of r points that cover the set. Then obtain cover of (D, dist of size 2r by taking the points {(I, 1), (z, 0) S}.
We can then apply Lemma and obtain that
log. log.N(Fill,,,, I1)) log(1/a 1). 2A((a) (Rel(D), मे. dist)
Plugging this result in the first formula, we obtain the claim.
E Experimental Setups and Datasets
In this section, provide detailed descriptions to the experimental setups and datasets used in Sect. 5
E.1
Computing infrastructure
The experiments are run on cluster equipped with Intel(R) Xeon(R) Silver 4116 CPUs and NVIDIA H100 GPUs. The code is based on Py PoToch and PyTorch-Geometric.
E.2 Datasets
In the following, we describe and discuss the datasets and their properties. Real-world datasets (i.e.. NCII, IMDB-b, MCF-7, Mutagenicity, COLLAB-b, and Peptides-func) were provided by [1 38 and [8]. A summary of all datasets and their properties can be found in Tab. 3
CSL We include three circular skip link (CSL) datasets generated analogously to the setup consid- ered in 42). A CSL graph is a 4-regular graph G,,,, with 4 and 1 < s < n/2 which consists of a cycle of length n which all pairs of nodes at distance on this cycle are connected by an additional edge. For a given n, we generate dataset by considering the graphs (Gn.s s S} where S is the set of all skip values leading to non-isomorphic graphs. In particular, we consider graph sizes n E {17, 41, 83) for which there exist 4, 10, and 20 non-isomorphic graphs, respectively. We refer to the datasets CSL-17, CSL-41, and CSL-83. Since classification tasks in this work are generally restricted to binary classification, we assign the graphs of a CSL dataset evenly into two classes. The classification task is then to assign graphs to their binary skip link class. This setup is commonly used as a benchmark for testing the expressive power of a model since 4-regular graphs cannot be distinguished by the 1-WL test.
3-Reg 3-Reg are datasets consisting of 3-regular graphs which are common types of expressivity benchmark datasets. For each E { (16, 32, 64), we generated a dataset containing 10 randomly generated 3-regular graphs of size n. We refer to these three datasets as 3-reg-16, 3-reg-32, and 3-reg-64. We evenly distributed the 10 graphs into two groups such that the binary classification task is to identify the group that a graph belongs to.
Cycles-pin As an example dataset containing k-weakly individualized graphs, we generated 10 graphs of size 33. Each such graph G, consists of pair of cycles of sizes 16 i and 16 + i for i E (0....,9) 9). We then append pin, i.e., an additional node, to one of the nodes in the smaller of the two cycles. evenly distributed the 10 graphs into two groups. The binary classification task then to identify the group that graph belongs to.
20

---

Table 3: Overview of real-world and synthetic graph dataset properties. Datasets marked (*) are composed of subsets of the original datasets. The column "WL number" denotes the minimum number of WL. iterations necessary to distinguish all graphs. The entry (-) this column indicates that this number does not exist, i.e., not all graphs can be distinguished by color refinement.
Name
# Graphs
Classes
Avg. # nodes
Avg. # edges
Node labels
WL number
COLLAB-b
5000
2
74.49
2457.78
1
IMDB-b
1000
2
19.77
96.53
MCF-7*
14
2
45.86
50.29
Mutagenicity
4337
2
30.32
30.77
NCI1
4110
2
29.87
32.30
Peptites-Tunc
15
169.47
172.93
3-reg-16
10
2
16
24
3-reg-32
10
2
32
48
3-reg-64
10
2
64
96
CSL-17
4
2
17
34
CSL-41
10
2
41
82
CSL-83
20
2
83
166
CSL.ppn
10
2
42
83
5
Cycles-pin
10
2
33
33
9
CSL-pin Analogously to the Cycles-pin dataset, we generate dataset called CSL-pin by appending pin, i.c. an additional node, to one of the nodes in every graph of the CSL-41 datasets described above. Adding the pins turns the graphs into k-weakly individualized graphs.
COLLAB consists 5,000 graphs extracted from three scientific collaboration networks. We merge two of the three classes (class and 3) to make the labels binary. Each graph corresponds to an ego-network which represents the collaboration network of particular researcher. The graph is then annotated by the field of this researcher such that the classification task consists of assigning an ego-network the research field.
COLLAB-b [66]
IMDB-b includes 1,000 ego-network graphs obtained from movie collaboration networks. In such graphs, nodes represent actors and edges represent their co-appearance in movie. ego-network graph then classified by the genre of the movie collaboration network was extracted from.
IMDB-b 66
MCF-7 From the original MCF-7 65 38 dataset, we extracted a maximal set of graphs (up to isomorphism) such that no graph can distinguished from all others by the Weisfeiler-Lehman (WL) test after four iterations. We divided these 14 graphs into two groups such that the binary classification tasks, i.e. assigning graph its group, requires at least five color refinement iterations to improve over random guessing and six iterations to perfectly classify all graphs.
Mutagenicity is binary classification benchmark dataset consisting of 4,337 molecular graphs. The classification task is to predict the mutagenic property of molecule.
Mutagenicity 30 49
NCII is binary dataset containing 4,110 molecular compounds, each categorized based on their ability to inhibit the growth of non-small cell lung cancer cell line.
NCTI 61
Peptides-func From the original Peptides-fune [57 18 dataset, we extracted a maximal set of graphs (up to isomorphism) such that no graph can be distinguished from others by the Weisfeiler- Lehman (WL. test after four iterations. We divided these 15 graphs into two groups such that the binary classification tasks, i.e. assigning a graph to its group, requires at least five color refinement iterations improve over random guessing and six iterations to perfectly classify all graphs.
21

---

E.3
Experimental setup
In the following, we give detailed descriptions of the experimental setups of our evaluation section in the main paper.
E.3.1 Expressivity
For the expressivity evaluation, we considered the datasets Cycles-pine CSL-pin, MCF-7, and Peptides-fuu which are described in detail in Sect. E.2 The experiments compare the capability of ordinary GNNs with that of a I-layer GNN that is run on top of the Tinhofer individualization to learn to distinguish dindistinue graphs. For each dataset, we provide the training accuracies obtained by GNN where K the minimum number of color refinement iterations necessary to distinguish all graphs in the respective dataset, as well as the training accuracies obtained by GNN, o Tinhofer. We use, as the GNN k architecture, the one described in Section [A.]] with K MLP-basee message passing layers. In fact, the GNNs based on linear layers for message passing, despite their theoretical equivalence to color refinement, were unable to converge, further strengthening our claims.
The plotted results in Fig. show the accuracy over 1000 epochs where we depict the average over a total of runs in bold and the individual runs faded out. We fixed the embedding dimension to 256 and use an Adam optimizer with learning rate of 0.0001. Due instability in the learning process. we provide smoothened learning curves for better clarity of the results.
E.3.2 VC dimension
To investigate the generalization bounds based on the VC-dimension results, we compare the indi- vidualization methods RNI [52], RP (4), and Tinhofer. The experiments are conducted the CSL and 3-Reg datasets of varying numbers of nodes. To investigate the generalization performance, we generate as the training set 1, 10, 100, and 1000 permutations for each graph in the respective dataset and test on 1000 permuted copies. We report the performance in terms of the difference between the train and test accuracy. Particularly, for every dataset, we consider the generalization gap achieved at the last epoch with a perfect training accuracy score over a total of 1000 epochs. We conduct a total of runs and plot the mean as well the standard deviations over these runs.
In all cases, we used the GNN architecture described Section with K = 4 linear-layer-basee message passing layers. We fix the embedding dimension 256 and use Adam optimizer with learning rate of 0.0001.
E.3.3 Substructure identification
For the substructure identification task, we generate 1000 3-regular graphs of order 30 for each of the task using NETWORKX. In particular, 500 graphs contain the pattern P and 500 do not. We split the dataset in train and test by assigning 90% of the graphs to the train set at random.
We use, as the GNN architecture, the one described in Section A.1 with K linear-layer based message passing layers. In particular, K is set for Cz. C4. K2.3 and for Cs, as these are the minimum number of layers for the message passing to fully cover these patterns.
We the same architecture GNN for the EGONNA model on each of the Ap-ego-nets, with 1 layer for the individualized versions and Ap layers for the non-individualized version. In particular, Ap P is for C33 and 2 for C₁, Os, K2.3. Moreover, we replace the max aggregation with a softmax, in order to allow the gradients to be propagated more casily, as we observe that this allows for an easier convergence. We fix dimension of the GNN embeddings 256. We use the Adam optimizer 32 with learning rate 0.001 and batch size 256.
The model is trained for 1000 epochs. The epoch at which the accuracies reported is selected as the one with highest training accuracy, with ties broken by the lowest training loss. Note that since the focus of this paper is on the (worst-case) generalization gap, the best epoch is not chosen using validation dataset, as it should be done in practice.
We report the mean and I-sigma error bars over 5 runs, on the same splits but with different seeds.
22

---

0.1
0.1
0..55
J36 6302
J03.1 Su0
0.3
0.2
0..05
Figure 5: Covering numbers for the NCI dataset
E.3.4
Covering numbers
For the section covering numbers, we used four real world datasets for binary classification, as described in Section
As metric on the relabeled graphs, we use the Wasserstein distance between the continuous WL embeddings given by [60], which we call WWL distance. particular, we choose Kwr. = WL iterations to obtain the embeddings, ensuring that Kwr. is at leas large the message passing iterations used the GNN models. This gives the WWI distance the ability to distinguish all the graphs that the GNNs can distinguish, which is needed to ensure Lipschitzness, In fact, this property cannot be guaranteed, as there are graphs that are not WL-isomorphic but that have WWL distance To mitigate this issue, we assign one-hot encodings with degree centralities the unlabeled graphs. We then compute N (Rel() D), c, dist)/| WWL distance and = 0.05. In fact, the covering number we report is an approximation (which is also upper bound) computed by running k-median clustering algorithm and selecting the minimum for which the objective function is less than 6.
(Rel
proxy for the sample complexity using the
We use, as the GNNk architecture, the described in Section A.1 with K 2, 5 linear-layer- based message passing layers. We fix dimension of the GNN embeddings to 128. We use the Adam optimizer 32 with learning rate 0.005 and batch size 256.
The model is trained for 1000 epochs. The epoch at which the accuracies are reported selected as the one with highest training accuracy, with ties broken by the lowest training loss. Note that since the focus of this paper on the (worst-case) generalization gap. the best epoch is not chosen using validation dataset, as it should be done in practice. We split the dataset in train and test by assigning 90% of the graphs to the test set random for each run.
We report the mean and 1-sigma error bars for the accuracies over runs with different seeds. We report the covering number just for the first seed due the high computational costs involved with the calculation.
F Additional results on covering numbers
In this section, we report additional results on the covering numbers on real world datasets. In particular, Figures 3 6 and 8 report the covering number curves for the NCII, Mutagenicity. IMDB-b and COLLAB- B-- datasets, respectively. The results are obtained from the train-test splits of the first run, as described in Section E.3
which depends the 1-norm covering number, and A ((el(D)), | which depends on the (сo-norm) covering number of the relabeled dataset. We observe that the 1-norm covering numbers are significantly lower than the oc-norm covering numbers across all scales and datasets, providing experimental evidence of the importance of the results of 2emma
We plot both V = -A(()) (Rel( (D),
23

---

3.05
AM5
0.5
2,03
Figure 6: Covering numbers for Mutagenicity dataset
Nans
Trinttr
Thihafers
Figure 7: Covering numbers for the IMDB-b dataset
Nore
0.3
0.2
CERT
APROCI
Tahole
Thneeees
1.4
02
Affoci
00
35
28
135
331
1E0 125 158 115 300
130 120 150 17.5 353
Figure 8: Covering numbers for the COLLAB-b dataset
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The claims in the abstract and in the introduction are addressed as follows. Section B addresses the expressivity of shallow GNNs with individualization schemes. Section and and Section[4.2 a address the VC dimension bounds. Section (4.3 addresses the covering number bounds. Section reppots the experimental evaluation.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the paper are discussed in the conclusions and more in detail in Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide all the proofs for our lemmas and theorems in Sections and D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the suppiemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The experimental setup is described in Section B Moreover, our code and data are publicly available at htttp:://githu: com /orgwardtwwaaa iiee_nddividuallizedGM ensure reproducibility. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
26

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our code and data publicly available at https: htt:://ggttt.... com/
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
wubbic//guude//Ddeeeltnnnsssss wwt.aaammmiioooooooooooooooeeiie for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips //ipsscc/pput cttp:/scccpubblcccuiiiiie guides http:///wlllllliieeeeooeeuuaaaaa
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provide all the details on the experimental setup in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report all the performance figures means and 1-sigma error bars, taken over runs, as described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CL, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The computing infrastructure is described in Section E.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is mostly theoretical and has no direct societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
28

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We describe and cite the original papers from which we take the datasets used in Section E.2
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
29

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper introduces only simple synthetic datasets, which released with the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
30

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "GdRCMzuiCI", "reviewer": "Reviewer_QJ5E", "summary": "This paper proposes sample complexity bounds for message-passing graph neural networks (GNNs) with node individualization schemes, i.e., the assignment of unique identifiers to nodes. The authors first introduce a mathematical framework which describes node individualization schemes as a relabeling process. Based on this framework, they provide VC-based sample complexity bounds for several node individualization schemes and a more general VC-based sample complexity bound for substructure identification based on ego nets. The authors then use covering numbers to bound the empirical Rademacher complexity and, building upon this bound, propose a novel node individualization scheme. Finally, they perform experiments on synthetic and real-world datasets for substructure identification and graph classification to evaluate their theoretical results.", "questions": "1. Could you elaborate on your definition of an equivariant function (where domain and codomain are both graphs)? How does this differ from an invariant function from graphs to graphs?\n2. Line 107: Why is the max operator used to define $k$? If $|V_G| \\\\neq |V_H$, then the two graphs are not isomorphic as per 1-WL, as there is no bijection between multisets of different sizes.\n3. Why is the graph-level readout defined to be in $[0,1]$ (line 120), but $\\\\{0,1\\\\}$ in Prop. 1? Should it be $GNN_{k,\\\\theta}^{bin}$ in Prop. 1? The same holds for Thm. 2.\n4. Could you please elaborate on the additional arguments from $\\\\Omega$, both with respect to ensuring permutation equivariance (cf. lines 136-141) as well as modelling pseudo-randomness? How do you obtain/choose $\\\\omega \\\\in \\\\Omega$? Does it serve as an enumeration of all possible permutations (and thus is factorial in the number of nodes of a graph)?\n5. On a related note, could you be more explicit about what node individualization schemes are permutation equivariant (invariant) *and* universally expressive (as stated in the proof for Theorem 2)?\n5. lines 150-151: Does this mean that GNNs could be used similary to WL in the Tinhofer algorithm? Or could you elaborate how we can use $k$ message passing layers to obtain a node individualized graph representation?\n7. lines 202-208: Could you elaborate on the relabeling process? Are the words \"features\" and \"labels\" synonymous in this context? If we update the label for each node $v_i$ as $(v_i, i)$, doesn't this make every node set $V_c$ a singleton?\n8. Proof of Lemma 1: Shouldn't this be $VC(\\\\mathcal{G}, GNN_K^{bin}) = |\\\\mathcal{G}/ \\\\simeq_{WL} |$ (instead of $|\\\\mathcal{G}/ \\\\simeq |$)?\n9. All results hold for bounded graphs only. Can you say anything about unbounded graphs? \n10. What is the computational complexity of $GNN^{ego}_{\\\\Delta_P}$ with the Tinhofer individualization scheme?", "limitations": "All presented results hold only for bounded graphs. Additionally, as the authors remark themselves, the VC bounds are somewhat vacuous, as we would have to sample from the set of all possible relabeled graphs.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "To the best of my knowledge, this paper is the first to introduce sample complexity bounds for graph neural networks with unique node identification. I think this contribution fills a gap in the current literature and is of interest to the graph learning community. Additionally, the authors propose an individualization scheme based on the Tinhofer algorithm and ego network construction with impressive results on substructure identification tasks.", "weaknesses": "While the introduction and motivation are well-written, the paper has some issues with respect to clarity. Overall, it would be helpful to point out explicitly which results hold for permutation equivariant (invariant) GNNs, and which are (additionally) universally expressive. Particularly, the role of $\\\\Omega$ is not fully clear to me: How does it address permutation equivariance, and how does it introduce pseudo-randomness?\n\nIn general, the theoretical results could be better situated within related work: How do the node individualization-based bounds differ from GNNs without node individualization? What is the trade-off between expressivity, permutation invariance and generalization? With respect to writing, it would further be helpful to use the definition environment for key terms in the preliminaries to make them easier to locate (e.g., lines 145-147). Additionally, important references such as 1-WL are missing from the preliminaries and line breaks in inequalities or definitions make the paper difficult to follow. Finally, there is ambiguous language, e.g., do node _embeddings_, _features_, and _labels_ refer to the same concept? \n\nOverall, my current score reflects the paper's clarity issues, which made it difficult to fully assess the theoretical results. Please refer to the **Questions** section for more details. If these issues are addressed, I would be willing to raise my score.\n\nPlease find some minor remarks and suggestions below:\n\n* Often the comma is missing after \"i.e.\" and \"e.g.\" (e.g., line 20, line 40, line 120)\n* Please consider double-checking how you use plural/singular throughout the paper (e.g. GNNs in line 149)\n* lines 19-23. Please consider breaking up this super long sentence\n* line 22: certain classes of graphs\n* line 35: typo in expressivity\n* line 38: language sounds off, suggestion: \"These features provide information about the graph topology [...]\"\n* line 40-41: \"The amount of training data required for generalization beyong the training data\" -> Consider re-writing this sentence\n* line 56: universal -> universally\n* line 87: tuple of G -> tuple G\n* line 109: dot missing\n* line 112: \"this algorithm\" -> \"Tinhofer\" or \"The Tinhofer algorithm\"\n* Consider removing \"hereinafter\" from the introduction of abbreviations, e.g., graph-neural networks (GNNs)\n* line 137: $\\\\Omega$ is in $\\\\mathbb{N}$ but referred to as integer in the text\n* line 140: \"in memory\" sounds a bit odd (if they have different vertex orderings)\n* line 246: form -> from\n* line 298: number \"of\" WL\n* line 320: explore -> explores\n* line 325-326: double \"respectively\"\n* line 360: indiced -> induced\n* Consider not having line breaks in formulae, this sometimes hinders readability\n* lines 52-61: consider providing links to the relevant sections/theorems in your list of contributions\n* line 532: suffice -> suffices\n* line 556: arrow points in the wrong direction\n* Consider checking how you refer to theorems etc., this is not always consistent (e.g., Prop. 1 is referred to as theorem in the text)\n* Please consider numbering equations\n* Reference [38] appears to be published in the future (NeurIPS 2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the novelty and the potential impact of our work to the graph learning community.  \nMoreover, we want to thank you for your extremely thorough and insightful review, which is certainly not to be taken for granted. \nYour comments made us spot and address some sections of the manuscript that required further clarifications, therefore enhancing the paper's quality and readability.\nWe believe that we can address most of your concerns and questions with small edits to the paper, possibly using the extra page granted in the camera ready version. \n\nPlease find detailed answers to all of your questions below.\n\n> In general, the theoretical results could...\n\nOur sample complexity bounds are applicable even without node initializations (by choosing the relabeling function to be the identity), leading to the bounds by [31 (Morris et al. 2023)] (for bounded graphs).  We will make this explicit. \n\nWe will include the reference to 1-WL and use the extra page to avoid line breaks. \n\nFeatures and node labels are indeed used as synonyms, and we will change the wording to use just node labels (see also question 7). Embeddings have a similar meaning but are the output of a GNN layer, as opposed to node labels, which are intrinsic properties of the input graph. We will make all of this explicit. \n\n> Minor remarks\n\nThank you, we will fix all typos. \n\n> **Questions:**\n\n1. Our definition of equivariance is slightly relaxed with respect to some works in the literature, but it is still sufficient for our purposes (line 138, line 220), and avoids making the notation heavier. We will mention this explicitly in the definition. \nFor what concerns invariance, note that we use the term just for real-valued functions. \nFor functions outputting graphs, a common definition would be that $G \\simeq H$ implies $f(G) = f(H)$ (equality, not isomorphism). Notice that such a function would be still called  equivariant under our definition. \n\n2. The max operator is indeed not necessary. We will replace the sentence with \"...if it holds for $k = |V_G| = |V_H|$\".\n\n3. In line 120 we define the output to be continuous in accordance with the literature [34 (Morris et al. 2019)], and it can be interpreted as the probability of $y$ being 1. In Prop.1 and Thm.2 the function $f$ to be realized takes binary values, and technically it could be represented by a continuous-output-GNN (with no output in $]0,1[$). We agree with you though that this could be unclear. We then propose the following changes:\n - In Prop.1,  we will use $GNN_{k, \\theta}^{\\rm bin}$ as you suggest.\n - In line 249, we will change $GNN_{1,\\theta}$ to $GNN_{1,\\theta}^{\\rm bin}$, so that both $h_v^{\\rm ego}$ and $h_G$ belong to $\\{ 0,1 \\}$.\n\n4. The choice of encapsulating the pseudo-randomness of models in an additional parameter is needed to model the sample complexity, and is used for example also in [17 (Franks et al. 2021)].\nAs you correctly point out, it could serve as an enumeration of all possible permutations of a graph and its size can be therefore factorial in the number of nodes.\nWe'd like to highlight that the choice of $\\omega \\in \\Omega$ is never done explicitly, and we just use the size of $\\Omega$ (or an upper bound to it) to bound the VC dimension of the hypothesis class, such as in the results of Lemmas 3, 4 and 5 in the Appendix. \n\n\n5. By Prop. 1, all node indiv. schemes are universally expressive. Note that not all relabeling schemes are. \nAs mentioned in line 220 some relabeling schemes, such as RWPE, are deterministic and permutation equivariant, but they cannot guarantee universality in general. \nA node indiv. scheme that is at the same time universally expressive and permutation equivariant can be obtained, e.g., by adding a canonical labelling to the nodes. This choice though is highly impractical due to the complexity of such algorithms. We then use the Tinhofer algorithm, that on WL-amenable graphs is canonical, and therefore guarantees both universal expressivity and permutation equivariance (Lemma 1).\n\n6. Exactly. The first $k-1$ layers of the GNN would be used to simulate WL on the graph. This is possible due to the results of [34 (Morris et al. 2019)]. \n\n7. Features should be replaced with labels. Moreover, we think that you could have interpreted the sentence after \"in fact\" as a continuation of the algorithm for relabeling, while it is an alternative version of the algorithm. Re-phrasing:\nIn the simplest version of the RP scheme, we update the label for each node $v_i$ as $\\ell(v_i) = (\\ell(v_i), i)$.\nThe second version of the scheme instead first partitions the nodes based on their labels into ${V_1, \\dots, V_C}$. Then, letting $V_c = (v_{i_1}, \\dots, v_{i_{|V_c|}})$, it updates the label for each node as $\\ell(v_{i_j}) = (\\ell(v_{i_j}), j)$.\n\n\n8. For the set of WL-amenable graphs, $|\\mathcal{G} /\\simeq_{WL}| = |\\mathcal{G} /\\simeq|$. We will make this explicit. \n\n9. The assumption of bounded graphs is indeed a limitation. However, this assumption is reasonable for many real-world graphs. For example, drug-like molecules generally have less than hundreds of nodes.\nSecondly, there are very few results for unbounded graphs in the literature. Notably, [31 (Morris et al., 2021)] achieves VC bounds for unbounded graphs, but they have to assume that the number of WL color classes is bounded. \nIn this case, one can probably extend the results for GNNs with relabeling schemes (not for node indiv. schemes, which break the regularity of the graphs by design), and this is an interesting question for future work.\n\n10. Let $n_E, m_E$ be the max number of nodes and edges of a ego-net and $n, m$ the number of nodes and edges in the original graph. Extracting each egonet, e.g., using a BFS, is $O(n \\cdot m_E)$. Let $T=o(n_E \\cdot m_E \\log n_E)$ be the max time to run Tinhofer on an egonet, then it takes $O(n T)$ to run the scheme.\nRunning one layer of a GNN on all ego nets will take time $O(n \\cdot m_E)$. We will mention this.", "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": "CR4cnpU8D5", "reviewer": "Reviewer_xW3P", "summary": "In this paper, the authors investigate the generalization properties of node-individualized Graph Neural Networks (GNNs). Specifically, they aim to differentiate between various individualization schemes based on their generalization properties. To achieve this, they employ two techniques: VC dimension and covering numbers. Furthermore, they propose a new individualization scheme informed by their findings.", "questions": "Please address the weak points.", "limitations": "no comments.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "**S1 Highly Relevant Topic:** The study of the generalization properties of GNNs is highly pertinent to understanding their capabilities. Investigating this within the context of individualization is particularly interesting, as individualization has been demonstrated to enhance expressive power.", "weaknesses": "**W1 Presentation:** The presentation of the results and methods is not clear. Particularly in the section following Theorem 1, where bounds on the number of equivalences are presented across various settings without sufficient explanation. More detail or intuition would be beneficial, especially regarding the Tinhofer individualization. Additionally, the comparison of different schemes based on these bounds is not clearly articulated. For instance, why are only amenable graphs considered for Tinhofer, but not for the other two cases? The discussion on positional and structural encodings also lacks clarity. Statements such as the Laplacian increasing VC dimension require more justification. The segments about randomness and super-exponentiality need further elaboration.\n\n**W2 EGOnet Individualization:** In section 4.2, the authors mention that their proposed 1-layer GNN on individualized egonets is guided by observations on VC dimension bounds. This point is unclear and should be detailed more explicitly. It might refer to the last sentence in that section, but the explanation is insufficient. Clear comparisons between different schemes in terms of VC bounds are necessary.\n\n**W3 Covering Number Result:** The conclusions drawn after Theorem 4 are not very clear. The presentation in this part is suboptimal, lacking clarity. The authors should more clearly indicate the insights gained from these results. Also, the proofs are very simple.\n\n**W4 New individualization schema:** The authors mention that a contribution is the design of a new schema, yet it is hidden well in the discussion at the end of Section 4. There one finds a high level and unclear description of that new scheme (appendix contains more details but haven’t checked that). At least, this major contribution could have been explained in the main paper?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your insights on how the paper could be improved, and for acknowledging the high relevance of our work. We think that, by addressing your comments on the lack of clarity of some sections, the paper will be indeed easier to understand. Please find below both the answers to your comments, and the proposed additional explanations and examples to increase the paper's comprehensibility.\n\nWe are however surprised by your evaluation with a score of 3, which entails technical flaws, weak evaluation or inadequate reproducibility. \nWe hope that our response addresses your concerns with clarity, and we would therefore highly appreciate if you would consider reevaluating your final assessment of our article.\nWe’d be happy to address any additional questions you may have.\n\n>**Weaknesses:**\n\n> W1 Presentation\n\nThank you for pointing out some sections that lack clarity. Note though that the level of detail that we could integrate into the main paper was limited by the strict page limit. If the paper is accepted, we will use the extra page granted for the camera ready to explain the sections you deem unclear in greater detail and include parts of the Appendix.\nIn particular, we will describe the individualization schemes in more detail (see also the reply to Point 7 of reviewer 1). \nFor the Tinhofer scheme, we first give a general bound to the size of ${\\rm Rel}(G)$ as for the other schemes. We then give a tighter result for the class of WL-amenable graphs. This result holds, as stated in the paper, just for the Tinhofer scheme, so we don't give similar results for the other schemes.\n\nConcerning the Laplacian increasing the VC dimension, we thank you for pointing out that the sentence needs more justification.\nWe will replace line 223 as follows:\n\"The Laplacian positional encoding [13] is known not to be equivariant in general [52], i.e., there are graphs $G$ such that ${\\rm Rel}(G, \\omega) \\not\\simeq {\\rm Rel}(G, \\omega')$ for some $\\omega \\neq \\omega'$. Therefore we have that $|{\\rm Rel}(\\mathcal{G}) / \\simeq_{WL}| > |\\mathcal{G} / \\simeq_{WL}|$, which, by Theorem 1, leads to an increase in the VC dimension...\"\n\n\n\n> W2 EGOnet Individualization\n\nWe think that by incorporating your comment we can make this section indeed more clear. Please find below an answer to your comment and how we would address it in the paper.\n\nIn general, we showcase that VC dimension bounds can lead to the development of better architectures tailored to specific tasks. \nIn particular, as stated in the paper, we design an architecture whose VC dimension depends on $\\mathcal G_\\Delta$, which is much smaller than $\\mathcal{G}$. This is briefly discussed, as you correctly point out, in the last paragraph of 4.2.\nWe would add the following discussion to make this point more explicit.\n\"In general, $\\mathcal G_\\Delta$ is much smaller compared to $\\mathcal{G}$, especially for small $\\Delta$. This leads to the fact that, in general, ${\\rm Rel}(\\mathcal G_\\Delta)$ will be much smaller than ${\\rm Rel}(\\mathcal{G})$. Thanks to Thm.1, we then have that the VC dimension of $GNN_{\\Delta}^{ego, Rel}$ is in general lower compared to the one of $GNN_{K}^{bin} \\circ {\\rm Rel}$. This theoretical result is also experimentally validated in Section 5.3.\"\n\n> W3 Covering Number Result\n\nWe point out that, although the proofs are not extremely complex, we are the first to develop these bounds, which we believe could be of interest to the entire statistical learning theory community, even beyond graph learning.\nMoreover, we are the first to apply them to relabeling schemes for graph neural networks.\nFinally, we agree that we can give more intuition on the results of Theorem 4 and how they can lead to the design of new relabeling schemes. Please see the reply to your point W4 for an example that we will include in the paper.\n\n\n> W4 New individualization schema\n\nPlease note that we don't claim that the new individualization scheme is a major contribution of the paper. The major contributions are rather the sample complexity bounds, we will make this clearer.\nBased on the covering number bounds, we indeed develop the ${\\rm Tinhofer}_W$ scheme.\n\nWe once again believe that addressing your comments by expanding this section will make the paper easier to understand. We will use the extra space in the camera-ready to integrate the formal description of the ${\\rm Tinhofer}_W$ scheme, which we now give only in the Appendix due to space constraints.\nWe will moreover integrate the following intuition on why the ${\\rm Tinhofer}_W$ scheme can lead to better generalization (as shown empirically in Section 5.4).\n\n\n\nConsider, as a motivating example, the two graphs\nin Figure 1 (*Panel (a)*) of the Supplementary PDF to the rebuttal.\nHere, the letters indicate graphs' node labels, and correspond in fact with WL color classes. \n\nThe ${\\rm Tinhofer}$ scheme would find a canonical ordering on the two graphs by assigning an identifier (e.g., Â) to one of the two nodes labeled with A. Then, assuming a total order A < Â < B < C < D < E, it would concatenate the position of the node in the ordering to the node label. We then obtain (up to ordering of the two A-labeled nodes), the graphs in *Panel (b)*.\nWe therefore have that the relabeled graphs have edit distance 3, even though the edit distance of the original graphs was just 1. By making the \"tail\" of the graphs longer, one can make the difference in edit distances arbitrarily large.\n\nThe ${\\rm Tinhofer_W}$ scheme would use the Tinhofer algorithm to obtain the same node ordering. The main difference lies in the fact that the scheme appends the position of the node in the ordering within its WL color class. One would then obtain the graphs in *Panel \\(c\\)*.\nThe edit distance thus remains 1, as in the original graphs. Then, by Theorem 4, we argue that the ${\\rm Tinhofer_W}$ scheme can lead to better generalization. This is indeed validated by the experiments in Section 5.4.", "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": "IyU30mmLZb", "reviewer": "Reviewer_Tve2", "summary": "The authors explore node individualization schemes and argue that they can improve the expressiveness of shallow GNNs and provide bounds on the sample complexity of these methods. This allows node individualization schemes to be compared in this context. The theoretical findings are then substantiated with experiments.", "questions": "only what's mentioned in weaknesses.", "limitations": "The authors have listed some limitations in the appendix. I don't see the Lipschitzness assumption as a huge limitation as this assumption is made in many works on GNNs.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- Theoretically comparing different node individualization schemes in terms of their generalization abilities is an extremely important result for the community and can help with future architectural design decisions. \n- Theoretical results involving sample complexity are well explained and validated experimentally and the choice of Tinhofer individualization is well motivated and validated.", "weaknesses": "- line [158]. The authors argue that node individualization can improve expressivity for shallow GNNs (with k-weakly individualized graphs). This argument would be more compelling if in practice it is shown that their exists graphs that need a large number of layers to be distinguished. In real-world datasets, particularly with node features, it would be interesting to know if this is ever the case. I understand why this results suggests that GNNs can be better distinguished with fewer layers but I am not convinced (yet) that this occurs in practice. \n- Line [307]. You seem to be suggesting that we may only want to label necessary nodes as it is 'potentially more stable to input perturbations'. I don't fully understand this and the way you phase it is not very compelling. Can you expand on this or provide some intuition? I think it would benefit the paper having a result that suggests we may only want to label a fraction of the nodes and why this would be more beneficial than labeling all nodes in some cases.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing the novelty and the importance of our work.\nWe also would like to thank you for pointing out some potential weaknesses of our paper that we didn't spot before. We are confident that both of them can be addressed by adding a discussion in the paper, which we will do by making use of the extra page granted for the camera-ready version. We think that thanks to your comments, we can make our paper both more impactful (by showing datasets where many layers are needed in practice) and more readable (by providing more intuitions). Please find the detailed comments below.\n\nWe hope that our response adequately addresses all your comments and positively influences your final score. Please let us know if you have any further or follow-up questions so that we can try to address them.\n\n> **Weaknesses:**\n> \n> Concerning line [158]\n\nWe agree with your observation that, on most real-world graph datasets, relatively few GNN layers would be sufficient to distinguish all pairs of graphs. However, motivated by your comment, we looked for and found real-world datasets where few layers are not enough to distinguish all graphs. This makes indeed for a very compelling argument in favor of our paper. \nIn the following, we report the minimum number of WL iterations needed to distinguish all non-WL-equivalent graph pairs for the datasets used in our paper as well as the two additional datasets ${\\tt MCF-7}$ and ${\\tt Peptites-func}$.\n\n| Dataset          | WL iterations needed | \n| --------------- | --------- | \n| COLLAB | 1 |\n| IMDB-BINARY | 1 |\n| MCF-7 | 6 |\n| Mutagenicity | 3 |\n| NCI1 | 3 |\n| Peptites-func | 6 |\n\nWe found that there are quite a few datasets which require at least six WL iterations (when incorporating node attributes). Considering that most GNN architectures commonly use 3-4 layers, we would argue that there are indeed cases where our approach is beneficial in real-world scenarios. \n\nMoreover, we notice that, even though GNNs are theoretically equivalent to WL, in practice they often have lower distinguishing power (e.g. due to bad convergence). We particularly notice this behaviour in the experiments in Section 5.1 (although on synthetic graphs). In fact, this behaviour has been observed in the literature (see, e.g., the recent paper [Wang et al, \"An Empirical Study of Realized GNN Expressiveness\", in ICML 2024]). \n\nSimilar to the experiments in Section 5.1, we now provide further experiments comparing the performance of ordinary GNNs with that of GNNs endowed with ${\\rm Tinhofer}$ on the above mentioned datasets ${\\tt MCF-7}$ and ${\\tt Peptites-func}$. To highlight the difference in performance between the two methods, we extracted a small subset of graphs from both datasets, for which a maximum number of layers (i.e., up to 6 layers) is necessary to distinguish all pairs of graphs. The learning task is to assign each graph to their isomorphism class. Figure 2 in the appended PDF file plots the accuracy of the two methods (i.e., ordinary GNNs with 6 layers and GNNs endowed with ${\\rm Tinhofer}$) over 1000 epochs on these two datasets. It can be seen that the GNN with ${\\rm Tinhofer}$ converges rapidly while the oridnary GNN in many cases does not even reach 100% accuracy within 1000 epochs; thus confirming the above claim on the relevance of our approch to real-world scenarios.\n\n> Concerning line [307]\n\nThank you for pointing out the inaccuracy in this paragraph. We will rephrase the sentence and add the following motivating example to give more intuition on the results of Theorem 4 and how they can lead to the design of new relabeling schemes. \n\nConsider, as a motivating example, the two graphs\nin Figure 1 (*Panel (a)*) of the Supplementary PDF to the rebuttal.\nHere, the letters indicate graphs' node labels, and correspond in fact with WL color classes. \n\nThe ${\\rm Tinhofer}$ scheme would find a canonical ordering on the two graphs by assigning an identifier (e.g., Â) to one of the two nodes labeled with A. Then, assuming a total order A < Â < B < C < D < E, it would concatenate the position of the node in the ordering to the node label. We then obtain (up to ordering of the two A-labeled nodes), the graphs in *Panel (b)*.\nWe therefore have that the relabeled graphs have edit distance 3, even though the edit distance of the original graphs was just 1. By making the \"tail\" of the graphs longer, one can make the difference in edit distances arbitrarily large. \n\nThe ${\\rm Tinhofer_W}$ scheme would use the Tinhofer algorithm to obtain the same node ordering. The main difference lies in the fact that the scheme appends the position of the node in the ordering within its WL color class. One would then obtain the graphs in *Panel \\(c\\)*. \nThe edit distance thus remains 1, as in the original graphs. Then, by Theorem 4, we argue that the ${\\rm Tinhofer_W}$ scheme leads to better generalization. This is indeed validated by the experiments in Section 5.4.\n\nWe note that ${\\rm Tinhofer_W}$ does not necessarily yield a lower sample complexity on all graph distributions. Therefore we do not provide a further theoretical analysis of this relabeling scheme. However, while our article is primarily focused on the sample complexity bounds, we hope that it will spark several works on new relabeling schemes that guarantee lower sample complexity.", "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:
Dear reviewers, 

we would like to express our appreciation for the positive comments on our paper, recognizing 
- the novelty of our work;
- the strong significance of our work for the community, potentially guiding future architectural design decisions;
- the strength of experimental results, particularly on substructure identification tasks.

We would like to thank you for the detailed and insightful feedback, which we believe have strengthened our paper considerably. Below, we provide detailed responses to your comments. Please also refer to the appended PDF file for further experimental evaluations highlighting the relevance of our approach in real-world scenarios as well as a motivating example for the ${\rm Tinhofer_W}$ relabeling scheme.

Meta-review: The paper focuses on an important and well-studied problem, the design and expressive power and generalization of graph neural network (GNN) architectures. The work provides a novel analysis of the sample complexity of GNNs enhanced with node individualization schemes, offering insights into their expressiveness and generalization capabilities. All reviewers agreed that the topic is of high importance and that the analysis presents a valuable contribution to the community. The theoretical findings are backed by numerical experiments.

While there are concerns about the scope of the experimental validation, particularly the reliance on synthetic datasets and certain criticized node classification datasets, the consistency of the results with the theoretical predictions adds credibility to the work. Additionally, although the presentation has been noted as somewhat challenging to follow, the underlying contributions are significant and warrant acceptance. The paper would benefit from further improvements in clarity, but these issues do not detract from the overall impact and novelty of the research. 

The authors are expected to take into account the author comments to improve the accessibility and clarity of the work.
Decision: Accept (poster)