ARelated work (expanded)

Recently, graph neural networks [42, 87] emerged as the most prominent (supervised) GRL architectures. Notable instances of this architecture include, e.g., [31, 47, 97], and the spectral approaches proposed in, e.g., [19, 30, 56, 72]--all of which descend from early work in [57, 69, 87, 90]. Recent extensions and improvements to the GNN framework include approaches to incorporate different local structures (around subgraphs), e.g., [2, 36, 50, 82, 106], novel techniques for pooling vertex representations in order perform graph classification, e.g., [20, 37, 108, 113], incorporating distance information [110], and non-euclidian geometry approaches [22]. Moreover, recently empirical studies on neighborhood aggregation functions for continuous vertex features [28], edge-based GNNs leveraging physical knowledge [4, 58], and sparsification methods [85] emerged. A survey of recent advancements in GNN techniques can be found, e.g., in [21, 103, 114]. Dasoulas et al. [29], Abboud et al. [1] investigate the connection between random coloring and universality. Recent works have extended GNNs' expressive power by encoding vertex identifiers [80, 98], adding random features [86], using higher-order topology as features [18], considering simplicial complexes [3, 14], encoding ego-networks [109], and encoding distance information [61]. Although these works increase the expressiveness of GNNs, their generalization abilities are understood to a lesser extent. Further, works such as Vignac et al. [98, Lemma 6] and the most recent Beaini et al. [11] and Bodnar et al. [14] prove the boost in expressiveness with a single pair of graphs, giving no insights into the extent of their expressive power or their generalization abilities. For clarity, throughout this work, we use the term GNNs to denote the class of message-passing architectures limited by the 1-WL algorithm, where the class of distinguishable graphs is well understood [5].