On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks

Authors: paolo  pellizzoni
hendrik  till
  schulz
dexiong  chen
karsten  borgwardt
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 13:07:47

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.

Main paper: 
 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.e., their ability to distinguish non-isomorphic graphs, is intrinsically limited by the capabilities of the Weisfeiler-Leman (1-WL) algorithm [61] , a heuristic used for the graph isomorphism problem [40, 62] . 1-WL is known to fail to distinguish certain classes of graphs, such as regular graphs [4] . Notably, GNNs are in general unable to 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 [40, 25] have been proposed. These models consider interactions among larger subgraphs or sets of nodes but often suffer from high computational complexity. An alternative approach, which we call node individualization schemes, entails introducing perturbations, such as random noise, into node features to break graph symmetries artificially. This technique enables message passing GNNs to become universal function approximators [1] without the computational overhead associated with higher-order GNNs. Several node individualization schemes have been proposed in the literature. Random Node Initializations (RNI) [50] add random noise to node labels to make them distinct with high probability, while Relational Pooling (RP) [41] and Colored Local Iterative Procedure (CLIP) [14] partition nodes based on their labels and assign unique identifiers within partitions. A recent paper [19] proposes a general framework based on individualization-refinement 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 [15, 60, 27] , and random walk [16] 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 [35, 52, 22] , i.e., the amount of training data required for generalization on unseen data, is a critical consideration to obtain effective graph learning models, and it has been recently linked to the 1-WL expressivity [36] . 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 an unanswered question. This paper presents a 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 1-WL test, thereby enhancing the expressivity of shallow GNNs (Section 3). • We analyze the sample complexity of GNNs with various node individualization schemes using VC-dimension-based bounds (Theorem 1). 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 a sharper analysis based on covering-number bounds, leading to the design of novel node individualization schemes (Theorem 4). Our bounds rely on a novel covering bound for Lipschitz functions [23] , a result that is potentially of independent interest. • We substantiate our theoretical findings with experimental results on both synthetic and real-world datasets (Section 5).By offering a comprehensive analysis and practical guidance, this paper aims to enhance the understanding 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.Expressivity of GNNs Since the seminal works of [40, 62] 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 [25] or Folklore-WL [10] tests, exemplified by k-GNNs [40] and k-FGNNs [34] . 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 [39, 65, 21] . Another line of research involves subgraph GNNs, which break symmetry by transforming the original graph into modified subgraphs for GNN processing [13, 47, 8] . For a more comprehensive overview, readers are encouraged to consult [49, 38] .Node individualizations Individualization schemes have been proposed by several works [50, 41, 14, 19, 11] to enhance the expressivity of GNNs. GNNs with such schemes have been shown to be universal function approximators for invariant functions [1, 5] . Individualization schemes are also crucial on edge-level tasks [33, 51] , where they break symmetry among different edge-orbits.The generalization capabilities of restricted families of GNNs has been addressed by means of VC dimension [52] , Rademacher complexity [22] and PAC-bayesian approaches [28, 32] . Recently, [36, 20] proposed VC-dimension bounds based on the number of 1-WL color classes. The sample complexity of frequent subgraph identification has been addressed in [44] .Moreover, [45] and [18] address the sample complexity of equivariant models using a coveringnumber-based approach [6, 24] , which is exploited also in [66] in an empirical setting. For a general overview on statistical learning theory, consult [35] . 
preliminaries: 
 In what follows, we define a graph as a tupleG = (V G , E G , L G ), with V G = {1, . . . , |V G |} a finite set of nodes, and E G ⊆ {{u, v} : u ̸ = v ∈ V G } a set of undirected edges.We define the vertex-label function as L G : V G → L, with a finite set of labels L. For the sake of simplicity, we consider edges to be unlabeled. We define the neighborhood of a node asN (v) = {w ∈ V G : {v, w} ∈ E G }.We say that two graphs G and H are isomorphic, denoted as G ≃ H, if there exists a bijective mapping π :V G → V H , called isomorphism, such that L G (v) = L H (π(v)), ∀v ∈ V G and {π(u), π(v)} ∈ E H if and only if {u, v} ∈ E G .The isomorphism relation induces equivalence classes, which we call unordered graphs [26] . The group of isomorphisms from G to itself is called the automorphism group Aut(G). We denote a set of graphs with G, and if necessary, as G L to 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|V G | ≤ n max , ∀G ∈ G. A function defined on graphs f : G → R is called invariant if for any G ≃ H, f (G) = f (H). A function from graphs to graphs f : G → G ′ is here called equivariant if for any G ≃ H, f (G) ≃ f (H).The color refinement algorithm, also known as 1-Weisfeiler-Leman (denoted as WL) algorithm, is a heuristic algorithm for the graph isomorphism problem.Let C 0 (v) = L G (v) ∈ N be the initial color of node v ∈ V G .Then the algorithm updates vertex colors at iteration k > 0 asC k (v) = HASH (C k-1 (v), {{C k-1 (w) : w ∈ N (v)}}) ∈ N,with HASH an injective map. Let P (k) (G) be the partitioning of V G based on colors after the k-th iteration of color refinement. Then, after at most |V G | iterations, the color partition stabilizes, i.e.P (k) (G) = P (k+1) (G), ∀k ≥ |V G |. Two graphs are deemed k-hop WL-isomorphic if {{C k (v) : v ∈ V G }} = {{C k (v) : v ∈ V H }}, and WL-isomorphic if it holds for k = |V G |. We denote this as G ≃ WL H. Note that G ≃ H =⇒ G ≃ WL H, but the converse is not true. We call a graph G WL-amenable if ∀H such that G ̸ ≃ H, G ̸ ≃ WL H.Tinhofer [57] developed a color-refinement-based algorithm, described in Section A.2, that returns an ordering of the nodes of a graph. This is a canonical ordering on a large class of graphs, called Tinhofer, which is a strict superset of WL-amenable class [4] . The Tinhofer algorithm is an instance of the individualization-refinement paradigm [19] on which several isomorphism solvers are based [3] .Message passing graph neural networks (GNNs), given a graph G, iteratively produce for each node v ∈ V G , at each level k = 1, . . . , K, the embeddings h k v ∈ R d k by taking into account messages coming from its neighbors N (v). More formally, the embedding of node v is updated ash k v = f upd h k-1 v , f agg {{h k-1 u : u ∈ N (v)}}, where f agg and f upd are the aggregate and the update operations, respectively. The first layer of the GNN is fed with the initial node embeddings h 0 v , e.g. one-hot encodings of the node labels. Finally, one can get a graph-level readout h G ∈ [0, 1] by aggregating the output node embeddings via a function f out . In [62, 40] it was shown that there exist injective functions f agg , f upd and f out yielding GNNs that are provably as expressive as color refinement. We provide examples for such architectures in Section A.1.We denote as GNN K = {GNN K,θ , θ ∈ Θ} the class of parametric functions formed by such a model with K message passing layers and parameter space Θ. Moreover, we define GNN bin K,θ (G) =• If all nodes belong to a singleton color class, return the ordering of the nodes based on the lexicographic 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 |V G | individualization steps. In fact, for several classes of graphs a constant number I of individualizations suffices [19] . Therefore, the algorithm can run in polynomial time.In fact, the Tinhofer algorithm can be generalized to the Individualization-Refinement scheme [19, 3] , where the refinement operation and the selection of the nodes to be individualized can be more general than the ones used in Tinhofer.EQUATION]. Moreover, the Tinhofer algorithm can also be implemented so that it takes O((|V G | + |E G |) log |V G |) time [7, Theorem 10].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 a major step forward in understanding the practical performance of GNNs with individualization schemes. Secondly, our results on 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.In this section, we provide formal definitions and lemmas, which were only informally described in the main paper.C.1 Definitions Definition 3. Let X be a set and S = (x 1 , . . . , x n ) a sample of n elements from X. Let F ⊆ {f : X -→ [0, 1]} be a family of functions. Let also σ i , i = 1, . . . , n be independent and identically distributed Rademacher random variables, i.e. taking value 1 or -1 with probability 1/2. The empirical Rademacher complexity is the quantityRS (F) = E σ sup f ∈F 1 n n i=1 σ i f (x i )where E σ denotes the expectation taken only with respect to the σ i 's, conditionally on the sample S. Proof. In line with the analysis in the original paper, we suppose that the random noise, selected via ω, takes values in a finite set C. Each node of a graph G can take |C| values. Therefore there are O(|C| n ) 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 of unlabeled graphs with n nodes containsEQUATION) ) unordered graphs. Intuitively, is obtained from the fact that for each of the n 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 [26] . A fraction of 1 -o(1) of unordered graphs only have the trivial automorphism [26] . Therefore, we have the claim by summing a contribution of O(|C| n ) over all such graphs. EQUATION) ) unordered graphs, and a fraction of 1 -o(1) of those only have the trivial automorphism [26] . 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. [46] ). Let X be a finite set and F ⊆ {f : X → [0, 1]}. Consider the pseudometric on F defined as ∥f 1 -G 1 ̸ ≃ G 2 such that P ∈ G 1 , P ̸ ∈ G 2 andf 2 ∥ 1 = 1 /|X| x∈X |f 1 (x) -f 2 (x)|. Then RX (F) ≤ inf α>0 α + 2 log N (F, α, ∥ • ∥ 1 )/|X| . Proof. Let C ⊂ {f : X → [0, 1]} be an α-cover of (F, ∥ • ∥ 1 ) of size N (F, α, ∥ • ∥ 1 ). Let also c f ∈ C be such that ∥f -c f ∥ 1 ≤ α. Then RX (F) = E   sup f ∈F 1 |X| x i ∈X σif (xi)   ≤ ≤ E   sup f ∈F 1 |X| x i ∈X σi(f (xi) -c f (xi))   + E   sup f ∈F 1 |X| x i ∈X σic f (xi)   ≤ ≤ α + E   sup c∈C 1 |X| x i ∈X σic(xi)   ≤ α + sup c∈C 2 log |C| |X| ,where the last inequality follows from Massart lemma and the fact that the functions in C take values in [0, 1].In this section, we provide the proofs that were omitted from the main paper. Proof. We consider the class of GNNs described in Section A.1, with depth K = max G∈G |V G | and large enough width [40] . Let the initial node embedding h 0 v of v ∈ V G be a one-hot encoding for its label L G (v), for any G ∈ G. Applying [40, Theorem 2] to the disjoint union of the graphs in G, we have that there exists a function GNN k-1,θ ∈ GNN k-1 can simulate k -1 steps of color refinement for all graphs in G. Therefore, from the definition of (k -1)-weakly individualized graph, after (k -1) message passing layers, all the node embeddings h k-1 v ∈ {-1, 1} d of nodes v ∈ V G computed by GNN k-1,θ will be distinct, that is, the graph is individualized. Then this individualized graph is WL amenable and 1 color refinement iteration suffices to identify the graph [4] . Then by [36, Proposition 9] , any invariant binary function on G can be realized.D.2 Proofs from Section 4.1 Theorem 1. Let Rel : G × Ω → G ′ be a relabeling function. Then VC G × Ω, GNN bin K • 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.1, with depth K = max G∈G |V G | and large enough width [40] . Let the initial node embedding h 0 v of v ∈ V G be a one-hot encoding for its label L G (v), for any G ∈ G.Let d := |Rel(G)/ ≃ WL |. We prove the upper bound. Let by contradiction S be a (multi)set of d + 1 elements that can be shattered. Then by pigeon hole, two elements (G, ω), (G ′ , ω ′ ) ∈ S must be mapped by Rel to graphs belonging to the same WL-isomorphism class. Then, by equivalence of GNN bin K to color refinement [40, Theorem 1], these two graphs are always mapped to the same value by GNN bin K • Rel. Then, there is no set of d + 1 elements that can be shattered. We then prove the lower bound. Let S ′ be a set of d graphs that are representatives of the WL-isomorphism classes contained in Rel(G)/ ≃ WL . For G ′ ∈ S ′ , let Rel -1 (G ′ ) = (G, ω) ∈ G × Ω such that Rel(G, ω) = G ′ .Note that, since Rel is injective in the first argument, the graph G is unique. On the other hand, ω may not be unique. We take any such ω with a deterministic rule (e.g. the minumum). Moreover, since we restrict the domain to S ′ , this inverse always exists. Let then S = {Rel -1 (G ′ ) : G ′ ∈ S ′ }. We have that |S| = |S ′ | = d and it can be shattered by Proposition 1 .When the graphs in Rel(G) are individualized, WL-isomorphism class correspond to isomorphism classes [4] , which proves the second claim. f : G → {0, 1} be f (G) = 1 [P ∈ G]. Let Rel be an individualization scheme. Then there exists θ ∈ Θ such that EGONN Rel ∆P,θ (G) = f (G) for every G ∈ G.Proof. By Proposition 1 we have that GN N 1 • Rel is universally expressive. In particular, it can take value 1 if P ∈ EGO v,G,∆ P and 0 otherwise for each possible EGO v,G,∆ P . Thenh G = max v∈V G h ego v = 1 if and only if P ∈ G. Theorem 3. Let G ∆ be the set of ego-nets of radius ∆ of the graphs of G. Then VC(G × Ω, EGONN Rel ∆ ) ≤ |Rel(G ∆ )/ ≃ |.Proof. We prove the upper bound. Suppose by contradiction that there is a set G 1 , . . . G d+1 of d + 1 graphs that can be shattered. In particular, each graph G i must have an ego net H i ∈ G i that does not appear in any other graph, i.e. H i ̸ ∈ G j , ∀j ̸ = i. Indeed, suppose that for each ego-net H v,i = EGO v,Gi,∆ of graph G i , we have that H v,i ∈ G j for some j ̸ = i. Then to be able to assign h Gi = 1, it must hold that GNN 1,θ (H v,i ) = 1 for some v. But since H v,i ∈ G j , we have that h Gj = 1 and the assignment of G 1 to 1 and all the other graphs to 0 cannot be achieved. Therefore, each graph G i must have an ego-net H i ∈ G i that does not appear in any other graph. Then there must be d + 1 distinct ego-nets, which is a contradiction.Remark 1. In fact, there are sets of graphs G and radii ∆ for which the VC bound above is tight. This lower bound can be proven by taking a datasets of d star graphs with maximum degrees 2, . . . d + 1 and ∆ = 1. Each graph has an ego-net that is unique to the graph, i.e., the graph itself, so the set can be shattered. Moreover, |Rel(G ∆ )/ ≃ | = d + 1.D.4 Proofs from Section 4.3 Lemma 2. Let (X, dist) be a pseudometric space and S ⊆ X a finite subset. LetF ⊆ {f : S → [0, 1]} be a set of C-Lipschitz functions. Let p, q ∈ N ∪ {+∞}, q ≥ p ≥ 1. Then log N (F, α, ∥ • ∥ p ) ≤ log(1/α + 1) • N (q) S, α 2C , dist .Proof. We construct a covering of the space F. Let p ̸ = ∞. Let S c = {x 1 , . . . x r } a p-norm α/2C-covering of (S, dist) of size r = N (p) S, α 2C , dist . For a point x ∈ S, let its center be c(s) = argmin xi∈Sc dist(x, x i ). Recall that a p-norm ϵ-covering C of a finite set S is such that1 /|S| x∈S dist(x, c(x)) p 1 /p ≤ ϵ. Let F = f : S c → {(k + 1 /2)α : k = 0, . . . , ⌊α -1 ⌋} . For fi ∈ F, we construct an associated function fi : S → {(k + 1 /2)α : k = 0, . . . , ⌊α -1 ⌋} such that fi (x) = fi (c(x)), ∀x ∈ S.Then let F be the set of maps { f : f ∈ F}. We have that | F| ≤ (1/α + 1) r , as the functions can take up to (1/α + 1) values over r points, and| F| = | F|. We show that F is indeed an α-covering of F in norm ∥ • ∥ p . Let f ∈ F. Let f ∈ F be such that ∀x ∈ S c , | f (x) -f (x)| ≤ α/2,which always exists by construction. Then,∥f -f ∥p = 1 /S x∈S |f (x) -f (x)| p 1/p ≤ ≤ 1 /S x∈S |f (c(x)) -f (c(x))| + |f (x) -f (c(x))|+| f (x) -f (c(x))| p 1/p ≤ 1 /S x∈S (α/2 + Cdist(x, c(x))+0) p 1/p ≤ α p /2 + C p 2 p-1 • 1 /S x∈S dist(x, c(x)) p 1/p ≤ α p /2 + C p 2 p-1 • (α/2C) p 1/p = α.In particular, we used that fact that (a + b) p ≤ 2 p-1 (a p + b p ) for p ≥ 1, which follows from Jensen's inequality with f (x) = x p .For p = ∞, we have that S c is a α/2C-covering of (S, dist) of size r = N S, α 2C , dist , and max x∈S dist(x, c(x)) ≤ α/2C. We build F as before. We then have∥f -f ∥∞ = max x∈S |f (x) -f (x)| ≤ max x∈S |f (c(x)) -f (c(x))| + |f (x) -f (c(x))| + | f (x) -f (c(x))| ≤ ≤ α/2 + Cdist(x, c(x)) + 0 ≤ α.Finally, noting that N (q) S, α 2C , dist ≥ N (p) S, α 2C , dist for each q ≥ p, we have the claim.Theorem 4. Let F ℓ be the set of margin losses for predictors F := GNN K • Rel. Let Rel(D) = {G ′ = Rel(G, ω) : (G, ω, y) ∈ D} be the graphs of the dataset after the relabeling, endowed with a pseudometric dist. Let functions in GNN K be C-Lipschitz continuous with respect to dist. ThenRD (F ℓ ) ≤ inf α>0 α + |D| -1 /2 2 log(1/α + 1) • 4N (1) G n,L ′ , αγ 4C , dist . Proof. We have that RD (F ℓ ) ≤ inf α>0 α + 2 log N (F ℓ | D , α, ∥ • ∥ 1 )/|D| by Lemma 7.We bound the covering number of the loss functions.Let Rel(D) = {Rel(G, ω) : (G, ω, y) ∈ D} be the graphs of the dataset after the relabeling, endowed with a pseudometric dist. We endow D with a pseudometric dist D defined as dist ((G, ω, y), Let also r be the 1-norm covering number of Rel(D) and S the set of r points that cover the set.(G ′ , ω ′ , y ′ )) = dist D (Rel(G, ω), Rel(G ′ , ω ′ )) if y = y ′Then we can obtain a cover of (D, dist D ) of size 2r by taking the points {(x, 1), (x, 0) : x ∈ S}.We can then apply Lemma 2 and obtain thatlog N (F ℓ | D , α, ∥ • ∥ 1 ) ≤ log(1/α + 1) • 2N (q) Rel(D), αγ 4C , dist .Plugging this result in the first formula, we obtain the claim.In this section, we provide detailed descriptions to the experimental setups and datasets used in Sect. 5.The experiments are run on a cluster equipped with Intel(R) Xeon(R) Silver 4116 CPUs and NVIDIA H100 GPUs. The code is based on PyTorch and PyTorch-Geometric.In the following, we describe and discuss the datasets and their properties. Real-world datasets (i.e., NCI1, IMDB-b, MCF-7, Mutagenicity, COLLAB-b, and Peptides-func) were provided by [30, 37] and [17] . 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 considered in [41] . A CSL graph is a 4-regular graph G n,s with n > 4 and 1 < s < n/2 which consists of a cycle of length n on which all pairs of nodes at distance s on this cycle are connected by an additional edge. For a given n, we generate a dataset by considering the graphs {G n,s : s ∈ S} where S is the set of all skip values leading to non-isomorphic graphs. In particular, we consider graph sizes n ∈ {17, 41, 83} for which there exist 4, 10, and 20 non-isomorphic graphs, respectively. We refer to the datasets as 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 n ∈ {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 i consists of a pair of cycles of sizes 16 -i and 16 + i for i ∈ {0, . . . , 9}. We then append a pin, i.e., an additional node, to one of the nodes in the smaller of the two cycles. We evenly distributed the 10 graphs into two groups. The binary classification task is then to identify the group that a graph belongs to. CSL-pin Analogously to the Cycles-pin dataset, we generate a dataset called CSL-pin by appending a pin, i.e. 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-b [64] COLLAB consists of 5,000 graphs extracted from three scientific collaboration networks. We merge two of the three classes (class 2 and 3) to make the labels binary. Each graph corresponds to an ego-network which represents the collaboration network of a particular researcher.The graph is then annotated by the field of this researcher such that the classification task consists of assigning an ego-network to the research field.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 a movie. An ego-network graph is then classified by the genre of the movie collaboration network it was extracted from. None (1) (X, , dist) (X, , dist) RP (1) (X, , dist) (X, , dist) RNI (1) (X, , dist) (X, , dist) Tinhofer (1) (X, , dist) (X, , dist) 0.0 0.5 1.0 1.5 2.0 2.5 3.0 log10 ( ) TinhoferW (1) (X, , dist) (X, , dist) 0.0 0.5 1.0 1.5 2.0 2.5 3.0 log10 ( ) LPE (1) (X, , dist) (X, , dist) None (1) (X, , dist) (X, , dist) RP (1) (X, , dist) (X, , dist) RNI (1) (X, , dist) (X, , dist) None (1) (X, , dist) (X, , dist) RP (1) (X, , dist) (X, , dist) RNI (1) (X, , dist) (X, , dist) Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.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 B Guidelines:• The answer NA means that the paper has no 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 a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
node individualization schemes: 
 In this section, we present a general framework for node individualization schemes. Definition 1. A graph G = (V, E, L G ) is called individualized if all node labels are pairwise distinct, that is |{L G (v) : v ∈ V }| = |V |.(v) : v ∈ V }| = |V |.Graph individualization is effectively achieved by assigning unique identifiers to nodes through a relabeling process. We formally define a relabeling function Rel :G L × Ω → G L ′ as a transformation ((V, E, L), ω) → (V, E, L ′ ) that maps injectively the node labels from L : V → L to a new set of labels L ′ : V → L ′ , e.g. with L ′ = L × C and L ′ (v) = (L(v), 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 ω ∈ Ω ⊆ N. This integer can be interpreted as a source of pseudo-randomness involved in the relabeling process (i.e., a random seed). For example, the relabeling function used in RNI [50] , due to its pseudo-random nature, can generate non-isomorphic relabeled graphs even from two identical copies of the same graph if it is given two different random seeds. Moreover, we note that node encodings such as the random walk [16] or the Laplacian [15] positional encodings can be cast as relabeling functions.A relabeling function is an individualization scheme if, for each(G, ω) ∈ G × Ω, it holds that Rel(G, ω) is a (possibly k-weakly) individualized graph. Moreover, for G ∈ G, let Rel(G) := {Rel(G, ω), ω ∈ Ω} and let Rel(G) := {Rel(G) : G ∈ G}.Expressive GNNs on individualized graphs are well known to be universal approximators for functions over graphs [1] . In fact, even a GNN with a single message passing layer and a MLP head is enough to provide a universal approximator [14] . We can generalize this result to k-weakly individualized graphs by noticing that k message passing layers, each simulating a WL iteration, provide a graph individualized by its node embeddings. The following statement formalizes this intuition. Proposition 1. Let f : G → {0, 1} be an invariant function and k ≥ 1. Then there existsθ ∈ Θ such that GNN bin k,θ (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 [4] ), they might require a 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 [42] or oversquashing [2] , hindering their ability to effectively distinguish graphs in practice. However, as Proposition 1 demonstrates, endowing GNNs with a (possibly k-weak) individualization scheme can offer sufficient signals for graph discrimination with fewer messagepassing iterations, thus mitigating these issues. In Section 5.1, we experimentally investigate this assessment and show that it has implications in real-world scenarios.• 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. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a 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 or 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). 
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 D data be a joint distribution over a set of graphs G and binary labels Y = {0, 1}. Moreover, let D be a joint distribution over the domain of D data and integers Ω ⊆ N. The integers ω ∈ Ω model any (pseudo-)randomness within the classification model f (G, ω). In the following, we denote by x = (G, ω). Given a loss function ℓ(f (x), y), our goal, in accordance with standard learning theory [35] , is to bound the difference between the true risk R(f ) and the empirical risk R(f ):R ℓ (f ) = E (x,y)∼D [ℓ(f (x), y)] and RD,ℓ (f ) = 1 m m i=1 ℓ(f (x i ), y i ),where D = {(x i , y i )} i ∼ D m represents a training dataset of size m sampled i.i.d. from D.In Sections 4.1 and 4.2 we derive bounds to |R ℓ (f ) -RD,ℓ (f )| based on the VC dimension, while in Section 4.3 we derive more refined bounds based on covering numbers.Let ℓ(f (x), y) = 1[f(x) ̸ = y] be the 0-1 loss. Then if d is the VC dimension of the hypothesis class, we have, with probability 1 -δ over the dataset [35, Corollary 3.4] . We define formally the VC dimension of a class of functions on a set. Definition 2. Let X be a set and F ⊆ {f : X → {0, 1}} an hypothesis class. We say that F shatters S = (x 1 , . . . x |S| ) if |{ f (x 1 ), . . . , f (x |S| ) : f ∈ F}| = 2 |S| . Then, we say that (X, F) has VC dimension VC(X, F) = d if the largest set S shattered by F has size d, and +∞ if the size of sets that can be shattered is unbounded.D ∼ D m , that sup f ∈F |R ℓ (f ) -RD,ℓ (f )| ≤ 2d/m + O( log(1/δ)/m)In particular, we consider a set X = G × Ω 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:F = GNN bin K • Rel := {GNN bin K,θ • Rel : GNN bin K,θ ∈ GNN bin K }, setting K = n max to ensure expressivity.GNNs with color refinement expressivity may require a number of parameters exponential in the maximum graph size n max = max G∈G |V G | [1] , which is a strong assumption we have to make. In the cases where the parameter count constraints the expressive power, the VC bounds from [36, Theorem 6] can be applied instead. The following theorem relates the VC dimension to the WL-isomorphism classes of the graphs in Rel(G).Theorem 1. Let Rel : G × Ω → G ′ be a relabeling function. Then VC G × Ω, GNN bin K • Rel = |Rel(G)/ ≃ WL |. If Rel is an individualization scheme, |Rel(G)/ ≃ WL | = |Rel(G)/ ≃ |.We provide specific bounds, proven in Section C.2, for relevant examples of relabeling schemes.Random Node Initializations [50] 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 ω, takes values in a finite set C. We then have that a graph G with n nodes is mapped to O(|C| n /|Aut(G)|) relabeled unordered graphs. In the case of unlabeled graphs with n nodes, we then have that|RNI(G)/ ≃ | = Θ( 1 n! 2 ( n 2 ) |C| n ) = Θ(|C| n • |G|).Relational Pooling [41] and CLIP [14] Let G be a graph and let v 1 , . . . , v n be an arbitrary enumeration of its nodes selected via ω. The simplest version of the RP scheme updates node labels as ℓ ′ (v i ) = (ℓ(v i ), i). A more refined version of the scheme partitions the nodes as {V 1 , . . . , V C } based on their labels and, lettingV c = (v i1 , . . . , v i |Vc | ), it updates node labels as ℓ ′ (v ij ) = (ℓ(v ij ), j).Then, each graph can be mapped to c |V c |!/|Aut(G)| relabeled unordered graphs. For unlabeled graphs with n nodes , this amounts to having |RP(G)/ ≃ | = Θ(2 ( n 2 ) ) = Θ(n! • |G|). The 1-CLIP node individualization scheme is equivalent to RP on the node partition based on initial labels.Tinhofer algorithm Let G be a graph and let v 1 , . . . , v n be an ordering given by the Tinhofer [57, 4] algorithm (Section A.2). Then updating node labels as ℓ ′ (v i ) = (ℓ(v i ), i) yields a valid individualization scheme Tinhofer, that is an instance of the general individualization-refinement framework given by [19] . Let the algorithm perform at most (i.e, for any choice of ω) I individualization iterations on graph G, let {V 1 , . . . , V C } be a partitioning of the nodes of G based on their labels and letR = max c |V c |. Then we have that |Tinhofer(G)/ ≃ | ≤ R I /|Aut(G)| ≤ n I /|Aut(G)|.In particular, as shown in the following lemma, for data distributions restricted to WL-amenable graphs, endowing a GNN with the Tinhofer individualization scheme does not increase its VC dimension.Lemma 1. Let G be a set of WL-amenable graphs. Then VC G×Ω, GNN bin K •Tinhofer = |G/ ≃ |.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 [16] or adding graphlet counts [9] yield |Rel(G)| = |G|, and therefore the increase in VC dimension is only due in the increase in the number of WL-isomorphism classes, if any. The Laplacian positional encoding [15] is known not to be equivariant in general [60] ,i.e., there are graphs G 1 ≃ G 2 for which Rel(G 1 , ω) ̸ ≃ Rel(G 2 , ω). Therefore we have that |Rel(G)/ ≃ W L | > |G/ ≃ W L |, which leads to an increase in the VC dimension and further motivates the attempts to obtain equivariant Laplacian-based relabeling functions [60, 27] .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 ω, i.e., if 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 a factor O(n!) compared to equally expressive GNNs endowed with the RP scheme.Finally, relabeling schemes that rely on the randomness introduced by the second argument ω (e.g. randomized schemes) are often enhanced by resampling different ω values at each epoch [41, 49] , effectively performing data augmentation. As discussed in [54] , 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-invariant model. However, the number of relabeled graphs in our setting often grows super-exponentially with the maximum graph size, e.g., n max ! 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.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, 27, 44] , where the task is to decide if a graph pattern P appears as a subgraph or induced subgraph of a query graph G, denoted hereafter as P ∈ 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 in [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 [13, 47, 8] , is to transform the original graph into a set of smaller subgraphs and feeding them to a GNN.In particular, let the task at hand concern a subgraph pattern P of radius ∆ P = min v∈V P max w∈V P δ vw , where δ vw is the length of the shortest path from v to w. Let a k-egonet of node v in graph G be the induced subgraph EGO v,G,k of nodes {u ∈ V G : δ uv ≤ k} at distance at most k from v. Then, a model that is able to recognize if P appears in any of the ∆ 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 thenh ego v = GNN bin 1,θ (Rel(EGO v,G,∆ P , ω)) ∈ {0, 1}, h G = max v∈V G h ego v ∈ {0, 1},that is, we run a 1-layer GNN on each individualized (potentially using some randomness from ω) ego-net and we aggregate the results using max-pooling. We denote such parametric functions as EGONN Rel ∆P,θ . We have the following results on the expressivity and the VC dimension of the model.Theorem 2. Let f : G → {0, 1} be f (G) = 1 [P ∈ G].Let Rel be an individualization scheme.Then there existsθ ∈ Θ such that EGONN Rel ∆P,θ (G) = f (G) for every G ∈ G. Theorem 3. Let G ∆ be the set of ego-nets of radius ∆ of the graphs of G. Then VC(G × Ω, EGONN Rel ∆ )≤ |Rel(G ∆ )/ ≃ |.In general, G ∆ is much smaller compared to G, especially for small ∆. This leads to the fact that, in general, Rel(G ∆ ) will be much smaller than Rel(G). Thanks to Theorem 1, we then have that the VC dimension of EGONN Rel ∆ is in general lower compared to the one of GN N bin K • Rel. In particular, relabeling the ego-nets using a scheme with lower |Rel(G ∆ )/ ≃ |, 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 5.3. 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 n E nodes and m E edges, the disjoint union of the ego-nets of G has nn E nodes and nm E edges.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 Rademacher-complexity-based approach introduced in [6] and used in [22] for graph classification, which can lead to tighter results.Let the margin function be M (f (x), y) = (2y -1)(2f (x) -1) ∈ [-1, 1]. Then the margin loss, given a γ > 0, is defined asℓ(f (x), y) = 1[M(f(x), y) < 0] + (1 -M (f (x), y)/γ)1[0 ≤ M (f (x), y) ≤ γ] ∈ [0, 1]. Let F ℓ = {(x, y) → ℓ(f (x), y) : f ∈ F } be the set of margin losses, for each predictor f ∈ F := GNN K • Rel.We then have [35] , with probability 1 -δ over the datasetD = {(x i , y i )} i ∼ D m , that sup f ∈F |R ℓ (f ) -RD,ℓ (f )| ≤ RD (F ℓ ) + O( ln(1/δ)/m), with RD (F ℓ ) the empiricalRademacher complexity of F ℓ on D (see Definition 3 in the Appendix). In particular, given thatP (x,y)∼D [1[f (x) > 0.5] ̸ = y] ≤ 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 RD (F ℓ ) via a covering-number-based approach. Let D be the training dataset and letF ℓ | D = {f | D : f ∈ F ℓ }be the set of margin losses restricted to the dataset.Given a pseudometric space (X, dist) and a subset S ⊆ X, we call C ⊆ X an ϵcover of S if max x∈S min c∈C dist(x, c) ≤ ϵ and define the ϵ-covering number of S as N (X, ϵ, dist) = min{|C| : C is an ϵ-cover of S}, i.e., the minimum number of balls of radius ϵ required to cover S. Similarly, for a finite S,we call C ⊆ X a p-norm ϵ-cover of S if 1 /|X| x∈X min c∈C dist(x, c) p 1 /p ≤ ϵ and define the p-norm ϵ-covering number of S as N (p) (X, ϵ, dist) = min{|C| : C is a p-norm ϵ-cover of S}. With slight abuse of notation, we let N (∞) (X, ϵ, dist) = N (X, ϵ, dist).In particular, we have that the p-norm ϵ-covering number of a metric space is monotonically increasing in p ∈ N ∪ {∞}.Moreover, for a finite set X and F ⊆ {f : X → [0, 1]}, we define the pseudometrics ∥f 1 -f 2 ∥ p = 1 /|X| x∈X |f 1 (x) -f 2 (x)| p 1 /p for p ≥ 1 and ∥f 1 -f 2 ∥ ∞ = max x∈X |f 1 (x) -f 2 (x)|. By Pollard's bound [46] we then have thatRD (F ℓ ) ≤ inf α>0 α + 2 log N (F ℓ | D , α, ∥ • ∥ 1 )/|D| .We bound the covering number of the class of functions F ℓ by covering the space of graphs and assuming the Lipschitzness of GNNs, similarly to the approaches in [18] and [45] . In fact, we provide a generalization of a covering bound for Lipschitz functions [23, Lemma 5.2] , that relaxes the Kolmogorov-Tikhomirov bound [56, Eq. 238] , tailored to the aforementioned Rademacher bound. Lemma 2. Let (X, dist) be a pseudometric space and S ⊆ X a finite subset. LetF ⊆ {f : S → [0, 1]} be a set of C-Lipschitz functions. Let p, q ∈ N ∪ {+∞}, q ≥ p ≥ 1. Then log N (F, α, ∥ • ∥ p ) ≤ log(1/α + 1) • N (q) S, α 2C , dist .Theorem 4. Let F ℓ be the set of margin losses for predictorsF := GNN K • Rel. Let Rel(D) = {G ′ = Rel(G, ω) : (G, ω, y)∈ D} be the graphs of the dataset after the relabeling, endowed with a pseudometric dist. Let functions in GNN K be C-Lipschitz continuous with respect to dist. ThenRD (F ℓ ) ≤ inf α>0 α + |D| -1 /2 2 log(1/α + 1) • 4N (1) Rel(D), αγ 4C , dist .Theorem 4 relies on the assumption that the GNN models are Lipschitz with respect to some pseudometric dist on graphs, such as the edit distance [53, 43] or the WWL distance [58] . This assumption, albeit strong, is often taken when considering the generalization of GNNs [27] . Note that, for small α and arbitrarily complex GNNs, i.e. C >> 1, we have that the covering number is proportional to the number of WL-isomorphic graphs in the relabeled dataset Rel(D), effectively retrieving the bounds obtained by the VC dimension. When GNN K is instead simpler, i.e. it has smaller Lipschitz constant C, the space of graphs can be covered with fewer balls, and we obtain better sample complexity. Discussion Let the graphs of the dataset D G = {G : (G, ω, y) ∈ D} and the relabeled graphs Rel(D) = {Rel(G, ω) : (G, ω, y) ∈ D} be subsets of the same metric space (G, dist). The results of Theorem 4 suggest that if a labeling function does not increase much the covering number of the dataset, i.e. N (1) (Rel(D), ϵ, dist) ≃ N (1) (D G , ϵ, dist), then the model GNN K • Rel would have roughly the same sample complexity as GNN K while being more expressive.In particular, this can be achieved if the relabeling scheme maps pairs of graphs with low distance (e.g. dist(G 1 , G 2 ) ≤ ϵ) 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 in the label of a node belonging to a singleton color class, like graphs G 1 and G 2 in Figure 1 . These two graphs could be, for example, two molecules where an atom is substituted with a similar one, or two proteins where an amino-acid is substituted with a functionally-similar one [43] .Driven by this intuition, we design a (k-weak) individualization scheme, which we call weak Tinhofer scheme Tinhofer W , that relabels only few nodes. The scheme obtains an ordering v 1 , . . . , v n of the nodes via the Tinhofer algorithm. Let {V 1 , . . . , V C } be a partition of the nodes of graph G into color classes after k color refinement steps and let V c = (v i1 , . . . , v i |Vc | ). The scheme then relabels nodes by appending their position in the ordering within their partition as ℓ ′ (v ij ) = (ℓ(v ij ), 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 1 for a visual example of a comparison between Tinhofer and Tinhofer W on the pair of graphs G 1 and G 2 . We have, for a u ∈ V G , that ∃ϕ :V G1 → V G2 such that {ϕ(v), ϕ(w)} ∈ E G2 iff {v, w} ∈ E G1 , L G2 (ϕ(v)) = L G1 (v), ∀v ̸ = u ∈ V G1 and L G2 (π(u)) ̸ = L G1 (u). Then dist(G 1 , G 2) would be given by the cost of substituting L G2 (π(u)) with L G1 (u). Consider the graphs produced by the Tinhofer W 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. This scheme ensures that the relabeled graphs are k-weakly individualized, while yielding no increase in the VC dimension for WL-amenable graphs (Lemma 1) and increasing the covering numbers only marginally. This in general yields better generalization, as shown experimentally in Section 5.4. 
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 individualization schemes, Section 5.2 and Section 5.3 validate respectively the general VC dimension bounds and 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 at https://github.com/BorgwardtLab/NodeIndividualizedGNNs.To highlight the efficacy of individualization schemes in practical applications, we compare a GNN endowed with Tinhofer to ordinary GNNs on challenging datasets. In particular, we consider subsets of the real-world datasets MCF-7 and Peptites-func, for which at least six message-passing iterations are necessary to distinguish all pairs of graphs, and synthetic datasets Cycles-pin and CSL-pin, for which nine, resp. five, iterations are necessary. To compare the performance between 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 1-layer GNN endowed with Tinhofer. While the ordinary GNNs can achieve a 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 in shallow GNNs, demonstrating the value of our approach in practical scenarios.We empirically evaluate the generalization bounds based on the VC dimension derived in Section 4.1.Recall that for an individualization scheme Rel and a set of graphs G, the generalization gap is bounded by the VC dimension d = |Rel(G)/ ≃ |. We evaluate RNI, RP, and Tinhofer using datasets of circular skip link (CSL) [41] graphs of sizes n = 17, 41, 83 and 3-regular graphs of sizes n = 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 n 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.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 C 3 , 4-cycle C 4 , 5-cycle C 5 , or complete bipartite graph K 2,3 . We tested GNNs with and without individualization schemes, along with our novel architecture EGONN ∆ P . As reported in To validate the theoretical results on covering numbers from Section 4.3, we use two molecular (NCI1 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 F for complete results) of the relabeled dataset and the dataset size N = N (1) (Rel(D), ϵ, dist)/|D|. As a (pseudo-)metric, we use the distance used by the WWL kernel [58] . We report N , together with the test accuracy and the difference between test and train accuracy, in Table 2 for GNNs with no individualizations, with RP, RNI, Tinhofer and weak Tinhofer individualizations, and with a Laplacian-encoding-based relabeling. We observe that across datasets 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, it is common in the literature [62, 40] to relabel such unlableled graphs with, e.g., degree centrailities. In [62] it was shown that there exist injective functions for f agg , f upd 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 [40] , denoting ∥ as concatenation, ish k v = mlp h k-1 v u∈N (v) h k-1 u ∈ R d k h G = mlp v∈V G h K v ∈ [0, 1].In fact, provided that different node labels are encoded to linearly independent h 0 v 's, even the following simpler architecture, denoting with σ a nonlinear function such as ReLU, is as expressive as color refinement [40] :h k v = σ W k 1 h k-1 v + W k 2 u∈N (v) h k-1 u ∈ R d k h G = mlp v∈V G h K v ∈ [0, 1].The Tinhofer algorithm [57, 4] returns an ordering of the nodes of a graph. In particular, it works as follows.1. Run color refinement on G and obtain the stable color partition P(G). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to usage guidelines or 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes]Justification: We describe and cite the original papers from which we take the datasets we used in Section E.2.Guidelines:• The answer NA means that the paper does not 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 a 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • 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 are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.† These authors jointly supervised this work. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

In 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? 

Overall, 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.

Please find some minor remarks and suggestions below:

* Often the comma is missing after "i.e." and "e.g." (e.g., line 20, line 40, line 120)
* Please consider double-checking how you use plural/singular throughout the paper (e.g. GNNs in line 149)
* lines 19-23. Please consider breaking up this super long sentence
* line 22: certain classes of graphs
* line 35: typo in expressivity
* line 38: language sounds off, suggestion: "These features provide information about the graph topology [...]"
* line 40-41: "The amount of training data required for generalization beyong the training data" -> Consider re-writing this sentence
* line 56: universal -> universally
* line 87: tuple of G -> tuple G
* line 109: dot missing
* line 112: "this algorithm" -> "Tinhofer" or "The Tinhofer algorithm"
* Consider removing "hereinafter" from the introduction of abbreviations, e.g., graph-neural networks (GNNs)
* line 137: $\\Omega$ is in $\\mathbb{N}$ but referred to as integer in the text
* line 140: "in memory" sounds a bit odd (if they have different vertex orderings)
* line 246: form -> from
* line 298: number "of" WL
* line 320: explore -> explores
* line 325-326: double "respectively"
* line 360: indiced -> induced
* Consider not having line breaks in formulae, this sometimes hinders readability
* lines 52-61: consider providing links to the relevant sections/theorems in your list of contributions
* line 532: suffice -> suffices
* line 556: arrow points in the wrong direction
* 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)
* Please consider numbering equations
* Reference [38] appears to be published in the future (NeurIPS 2024)
questions: 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?
2. 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.
3. 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.
4. 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)?
5. 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)?
5. 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?
7. 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?
8. Proof of Lemma 1: Shouldn't this be $VC(\\mathcal{G}, GNN_K^{bin}) = |\\mathcal{G}/ \\simeq_{WL} |$ (instead of $|\\mathcal{G}/ \\simeq |$)?
9. All results hold for bounded graphs only. Can you say anything about unbounded graphs? 
10. What is the computational complexity of $GNN^{ego}_{\\Delta_P}$ with the Tinhofer individualization scheme?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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.

**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.

**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.

**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?
questions: questions: Please address the weak points.
limitations: limitations: no comments.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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. 
- 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.
questions: questions: only what's mentioned in weaknesses.
limitations: 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.

Comments: title: Thanks for the rebuttal
comment: Thank you very much for your answer and for appreciating our work. We really value your input, which will help us enhance and strengthen our contribution.
Thanks for your answer. We understand and respect your decision. In any case, we will make sure to use your feedback to make the paper easy to understand.
Thank you for your positive feedback. Once again, we sincerely appreciate the detailed review and helpful suggestions you provided, which motivated us to put an extra effort to ensure that we could deliver the best version possible of the paper.
Concerning question A4: Indeed $\Omega$ can be understood as a random seed. We will mention it.
I thank the authors for their detailed response and the additional experiments and examples.

Two quick notes on the rebuttal:

* A3: Sounds good to me.
* A4: Thank you for the clarification. I think this needs to be made much more explicit in the paper. I am also still struggling with the term ''pseudo-randomness''; perhaps you could explain that $\omega \in \Omega$ can be seen as a random seed (if I understood the role of $\Omega$ correctly now)?

I also read the other reviews as well as the authors' rebuttals and decided to **raise my score**. While I agree with reviewer xW3P on clarity issues, given the detailed and thoughtful rebuttal by the authors, I am positive that this could be improved for the camera-ready version.
Dear Authors,

Thank you for your detailed rebuttal and thoughtful responses to my concerns. I appreciate the depth of analysis provided and recognize the value of your work. However, my current score reflects the difficulty I had in digesting the presentation of your concepts, even though I am familiar with most of them. I found several parts lacked clarity, a concern also shared by review QJ5E. I believe your work has significant potential, but I am unable to recommend acceptance in its current form.
Thank you very much for your detailed response to my questions. Indeed, I think these additional discussions make the paper stronger and I have increased my score accordingly and will push for acceptance.