Year: 2021

Abstract:
Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability. Unfortunately, it was shown that these architectures are limited in their expressive power. This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Thus, we propose to represent each graph as a set of subgraphs derived by some predefined policy, and to process it using a suitable equivariant architecture. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN in terms of these new WL variants. We further prove that our approach increases the expressive power of both MPNNs and more expressive architectures. Moreover, we provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture’s expressive power. To deal with the increased computational cost, we propose a subgraph sampling scheme, which can be viewed as a stochastic version of our framework. A comprehensive set of experiments on real and synthetic datasets demonstrates that our framework improves the expressive power and overall performance of popular GNN architectures.

text: Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability. Unfortunately, it was shown that these architectures are limited in their expressive power. This paper proposes a novel framework called Equivariant Subgraph Aggregation Networks (ESAN) to address this issue. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Thus, we propose to represent each graph as a set of subgraphs derived by some predefined policy, and to process it using a suitable equivariant architecture. We develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism, and prove lower bounds on the expressiveness of ESAN in terms of these new WL variants. We further prove that our approach increases the expressive power of both MPNNs and more expressive architectures. Moreover, we provide theoretical results that describe how design choices such as the subgraph selection policy and equivariant neural architecture affect our architecture’s expressive power. To deal with the increased computational cost, we propose a subgraph sampling scheme, which can be viewed as a stochastic version of our framework. A comprehensive set of experiments on real and synthetic datasets demonstrates that our framework improves the expressive power and overall performance of popular GNN architectures.

heading: 1 INTRODUCTION
text: Owing to their scalability and simplicity, Message-Passing Neural Networks (MPNNs) are the leading Graph Neural Network (GNN) architecture for deep learning on graph-structured data. However, Morris et al. (2019); Xu et al. (2019) have shown that these architectures are at most as expressive as the Weisfeiler-Lehman (WL) graph isomorphism test (Weisfeiler & Leman, 1968). As a consequence, MPNNs cannot distinguish between very simple graphs (See Figure 1). In light of this limitation, a question naturally arises: is it possible to improve the expressiveness of MPNNs?
Several recent works have proposed more powerful architectures. One of the main approaches involves higher-order GNNs equivalent to the hierarchy of the k-WL tests (Morris et al., 2019; 2020b; Maron et al., 2019b;a; Keriven & Peyré, 2019; Azizian & Lelarge, 2021; Geerts, 2020), offering a trade-off between expressivity and space-time complexity. Unfortunately, it is already difficult to implement 3rd order networks (which offer the expressive power of 3-WL). Alternative approaches use standard MPNNs enriched with structural encodings for nodes and edges (e.g. based on cycle or clique counting) (Bouritsas et al., 2020; Thiede et al., 2021) or lift graphs into simplicial- (Bodnar et al., 2021b) or cell complexes (Bodnar et al., 2021a), extending the message passing mechanism to these higher-order structures. Both types of approaches require a precomputation stage that, though reasonable in practice, might be expensive in the worst case.
Our approach. In an effort to devise simple, intuitive and more flexible provably expressive graph architectures, we develop a novel framework, dubbed Equivariant Subgraph Aggregation Networks (ESAN), to enhance the expressive power of existing GNNs. Our solution emerges from the observation that while two graphs may not be distinguishable by an MPNN, it may be easy to find distinguishable subgraphs. More generally, instead of encoding multisets of node colors as done in MPNNs and the WL test, we opt for encoding bags (multisets) of subgraphs and show that such an encoding can lead to a better expressive power. Following that observation, we advocate representing each graph as a bag of subgraphs chosen according to some predefined policy, e.g., all graphs that can be obtained by removing one edge from the original graph. Figure 1 illustrates this idea.
Bags of subgraphs are highly structured objects whose symmetry arises from both the structure of each constituent graph as well as the multiset on the whole. We propose an equivariant architecture specifically tailored to capture this object’s symmetry group. Specifically, we first formulate the symmetry group for a set of graphs as the direct product of the symmetry groups for sets and graphs. We then construct a neural network comprising layers that are equivariant to this group. Motivated by Maron et al. (2020), these layers employ two base graph encoders as subroutines: The first encoder implements a Siamese network processing each subgraph independently; The second acts as an information sharing module by processing the aggregation of the subgraphs. After being processed by several such layers, a set learning module aggregates the obtained subgraph representations into an invariant representation of the original graph that is used in downstream tasks.
An integral component of our method, with major impact on its complexity and expressivity, is the subgraph selection policy: a function that maps a graph to a bag of subgraphs, which is then processed by our equivariant neural network. In this paper, we explore four simple — yet powerful — subgraph selection policies: node-deleted subgraphs, edge-deleted subgraphs, and two variants of ego-networks. To alleviate the possible computational burden, we also introduce an efficient stochastic version of our method implemented by random sampling of subgraphs according to the aforementioned policies.
We provide a thorough theoretical analysis of our approach. We first prove that our architecture can implement novel and provably stronger variants of the well-known WL test, capable of encoding the multiset of subgraphs according to the base graph encoder (e.g., WL for MPNNs). Furthermore, we study how the expressive power of our architecture depends on different main design choices like the underlying base graph encoder or the subgraph selection policy. Notably, we prove that our framework can separate 3-WL indistinguishable graphs using only a 1-WL graph encoder, and that it can enhance the expressive power of stronger architectures such as PPGN (Maron et al., 2019a).
We then present empirical results on a wide range of synthetic and real datasets, using several existing GNNs as base encoders. Firstly, we study the expressive power of our approach using the synthetic datasets introduced by Abboud et al. (2020) and show that it achieves perfect accuracy. We then evaluate ESAN on popular graph benchmarks and show that they consistently outperform their base GNN architectures, and perform better or on-par with state of the art methods.
Main contributions. This paper offers the following main contributions: (1) A general formulation of learning on graphs as learning on bags of subgraphs; (2) An equivariant framework for generating and processing bags of subgraphs; (3) A comprehensive theoretical analysis of the proposed framework, subgraph selection policies, and their expressive power; (4) An in-depth experimental evaluation of the proposed approach, showing noticeable improvements on real and synthetic data. We believe that our approach is a step forward in the development of simple and provably powerful GNN architectures, and hope that it will inspire both theoretical and practical future research efforts.

heading: 2 EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS (ESAN)
text: In this section, we introduce the ESAN framework. It consists of (1) Neural network architectures for processing bags of subgraphs (DSS-GNN and DS-GNN), and (2) Subgraph selection policies. We refer the reader to Appendix A for a brief introduction to GNNs, set learning, and equivariance.
Setup and overview. We assume a standard graph classification/regression setting.1 We represent a graph with n nodes as a tuple G = (A,X) where A ∈ Rn×n is the graph’s adjacency matrix and X ∈ Rn×d is the node feature matrix. The main idea behind our approach is to represent the graph G as a bag (multiset) SG = {{G1, . . . , Gm}} of its subgraphs, and to make a prediction on a graph based on this subset, namely F (G) := F (SG). Two crucial questions pertain to this approach: (1) Which architecture should be used to process bags of graphs, i.e., How to define F (SG)?, and (2) Which subgraph selection policy should be used, i.e., How to define SG?

heading: 2.1 BAG-OF-GRAPHS ENCODER ARCHITECTURE
text: To address the first question, we start from the natural symmetry group of a bag of graphs. We first devise an equivariant architecture called DSS-GNN based on this group, and then propose a particularly interesting variant (DS-GNN) obtained by disabling one of the components in DSS-GNN.
Symmetry group for sets of graphs. The bag SG = {{G1, . . . , Gm}} of subgraphs of G can be represented as tensor (A,X ) ∈ Rn×n×m×Rn×d×m, assuming the number of nodes n and the number of subgraphs m are fixed. Here, A ∈ Rn×n×m represents a set of m adjacency matrices, and X ∈ Rn×d×m represents a set of m node feature matrices. Since the order of nodes in each subgraph, as well as the order of these subgraphs in SG, are arbitrary, our architecture must be equivariant to changes of both of these orders. Subgraph symmetries, or node permutations, are represented by the symmetric group Sn that acts on a graph via (σ · A)ij = Aσ−1(i)σ−1(j) and (σ · X)il = Xσ−1(i)l. Set symmetries are the permutations of the subgraphs in SG, represented by the symmetric group Sm that acts on sets of graphs via (τ · A)ijk = Aijτ−1(k) and (τ · X )ilk = Xilτ−1(k). These two groups can be combined using a direct product into a single group H = Sm × Sn that acts on (A,X ) in the following way:
((τ, σ) · A)ijk = Aσ−1(i)σ−1(j)τ−1(k), ((τ, σ) · X )ilk = Xσ−1(i)lτ−1(k)
In other words, τ permutes the subgraphs in the set and σ permutes the nodes in the subgraphs, as depicted in Figure 2. Importantly, since all the subgraphs originate from the same graph, we can order their nodes consistently throughout, i.e., the i-th node in all subgraphs represents the i-th node in the original graph.2 This setting can be seen as a particular instance of the DSS framework (Maron et al., 2020) applied to a bag of graphs.
H-equivariant layers. Our goal is to propose anH-equivariant architecture that can process bags of subgraphs accounting for their natural symmetry (the product of node and subgraph permutations). The main building blocks of such equivariant architectures are H-equivariant layers. Unfortunately, characterizing the set of all equivariant functions can be a difficult task, and most works limit themselves to characterizing the spaces of linear equivariant layers. In our case, Maron et al. (2020) characterized the space of linear equivariant layers for sets of symmetric elements (such as graphs) with a permutation symmetry group P (Sn in our case). Their study shows that each such layer is composed of a Siamese component applying a linear P -equivariant layer to each set element independently and an information sharing component applying a different linear P -equivariant layer to the aggregation of all the elements in the set (see Appendix A).
1The setup can be easily changed to support node and edge prediction tasks. 2This consistency assumption justifies the fact that we apply the same permutation σ to all subgraphs, rather
than having a different node permutation (σ1, . . . , σm) for each subgraph.
Motivated by the linear characterization, we adopt the same layer structure with Siamese & information sharing components, and parameterize these ones using any equivariant GNN layer such as MPNNs. These layers L : Rn×n×m × Rn×d×m → Rn×n×m × Rn×d′×m map bags of subgraphs to bags of subgraphs, as follows:
(L(A,X ))i = L1(Ai, Xi) + L2 (∑m j=1Aj , ∑m j=1Xj ) . (1)
Here, Aj , Xj are the adjacency and feature matrices of the j-th subgraph (the j-th components of the tensorsA,X , respectively), and (L(A,X ))i denotes the output of the layer on the i-th subgraph. L1, L2 : Rn×n × Rn×d → Rn×n × Rn×d′ represent two graph encoders and can be any type of GNN layer. We refer to L1, L2 as the base graph encoders. When MPNN encoders parameterise L1, L2, the adjacency matrices of the subgraphs do not change, i.e., the H-equivariant layer outputs the processed node features with the same adjacency matrix. These layers can also transform the adjacency structure of the subgraphs, e.g., when using Maron et al. (2019a) as the base encoder.
While the encoder L1 acts on every subgraph independently, L2 allows the sharing of information across all the subgraphs in SG. In particular, the L2 module operates on the sum of adjacency and feature matrices across the bag. This is a meaningful operation because the nodes in all the subgraphs of a particular graph are consistently ordered. As in the original DSS paper, this sum aggregator for the adjacency and feature matrices ( ∑m j=1Aj and ∑m j=1Xj) can be replaced with
(1) Sums that exclude the current subgraph ( ∑m j 6=iAj and ∑m j 6=iXj) or with (2) Other aggregators such as max and mean. We note that for the subgraph selection policies we consider in Subsection 2.2, an entrywise max aggregation over the subgraph adjacency matrices, A = maxj Aj , recovers the original graph connectivity. This is a convenient choice in practice and we use it throughout the paper. Finally, the H-equivariance of the layer follows directly from the Sn-equivariance of the base-encoder, and the Sm-equivariance of the aggregation. Figure 3 (right panel) illustrates our suggested H-equivariant layer.
DSS-GNN comprises three components:
FDSS-GNN = Esets ◦Rsubgraphs ◦ Esubgraphs (2)
The first component is an Equivariant Feature Encoder, Esubgraphs : Rn×n×m × Rn×d×m → Rn×n×m × Rn×d′×m implemented as a composition of several H-equivariant layers (Equation 1). The purpose of the subgraph encoder is to learn useful node features for all the nodes in all subgraphs. On top of the graph encoder, we apply a Subgraph Readout Layer Rsubgraphs : Rn×n×m × Rn×d′×m → Rd′×m that generates an invariant feature vector for each subgraph independently by aggregating the graph node (and/or edge) data, for example by summing the node features. The last layer, Esets : Rd
′×m → Rd′′ , is a universal Set Encoder, for example DeepSets (Zaheer et al., 2017) or PointNet (Qi et al., 2017). Figure 3 (left panel) illustrates the DSS-GNN architecture.
Intuitively, DSS-GNN encodes the subgraphs (while taking into account the other subgraphs) into a set of Sn-invariant representations (Esubgraphs ◦ Rsubgraphs) and then encodes the resulting set of subgraph representations into a single H-invariant representation Esets of the original graph G.
DS-GNN is a variant of DSS-GNN obtained by disabling the information sharing component, i.e., by setting L2 = 0 in Equation 1 for each layer in Esubgraphs. As a result, the subgraphs are encoded independently, and Esubgraphs is effectively a Siamese network. DS-GNN can be interpreted as a Siamese network that encodes each subgraph independently, followed by a set encoder that encodes the set of subgraph representations. DS-GNN is invariant to a larger symmetry group obtained from the wreath product Sn o Sm.3
In Section 3, we will show that both DS-GNN and DSS-GNN are powerful architectures and that in certain cases DSS-GNN has superior expressive power.

heading: 2.2 SUBGRAPH SELECTION POLICIES
text: The second question, How to select the subgraphs?, has a direct effect on the expressive power of our architecture. Here, we discuss subgraph selection policies and present simple but powerful schemes that will be analyzed in Section 3.
Let G be the set of all graphs with n nodes or less, and let P(G) be its power set, i.e. the set of all subsets S ⊆ G. A subgraph selection policy is a function π : G → P(G) that assigns to each graph G a subset of the set of its subgraphs π(G). We require that π is invariant to permutations of the nodes in the graphs, namely that π(G) = π(σ ·G), where σ ∈ Sn is a node permutation, and σ ·G is the graph obtained after applying σ. We will use the following notation: π(G) := SπG. As before, SπG can be represented in tensor form, where we stack subgraphs in arbitrary order while making sure that the order of the nodes in the subgraphs is consistent.
In this paper, we explore four simple subgraph selection policies that prove to strike a good balance between complexity (the number of subgraphs) and the resulting expressive power: node-deleted subgraphs (ND), edge-deleted subgraphs (ED), and ego-networks (EGO, EGO+), as described next. In the node-deleted policy, a graph is mapped to the set containing all subgraphs that can be obtained from the original graph by removing a single node.4 Similarly, the edge-deleted policy is defined by removing a single edge. The ego-networks policy EGO maps each graph to a set of ego-networks of some specified depth, one for each node in the graph (a k-Ego-network of a node is its k-hop neighbourhood with the induced connectivity). We also consider a variant of the egonetworks policy where the root node holds an identifying feature (EGO+). For DS-GNN, in order to guarantee at least the expressive power of the basic graph encoder used, one can add the original graph G to SπG for any policy π, obtaining the augmented version π̂. For example, ÊGO is a new policy that outputs for each graph the standard EGO policy described above and the original graph.
Stochastic sampling. For graphs of larger size, enlisting the entire bag of subgraphs for some policies can prove to be too expensive. To counteract this, we suggest employing a stochastic subgraph sub-sampling scheme which, in every training epoch, selects a small subset of subgraphs S π
G ⊂ SπG independently and uniformly at random. In practice, we use |SπG|/|SπG| ∈ {0.05, 0.2, 0.5}. Besides enabling running on larger graphs, sub-sampling also allows to increase the batch size, resulting in a faster runtime per epoch. During inference, we combine ` such subsets of subgraphs (we use ` = 5) of subgraphs and a majority voting scheme to make predictions. While the resulting network is no longer invariant, we show that this efficient variant of our method increases the expressive power of the base encoder and performs well empirically.

heading: 2.3 RELATED WORK
text: Broadly speaking, the efforts in enhancing the expressive power of GNNs can be clustered along three main directions: (1) Aligning to the k-WL hierarchy (Morris et al., 2019; 2020b; Maron et al., 2019b;a); (2) Augmenting node features with exogenous identifiers (Sato et al., 2021; Dasoulas et al., 2020; Abboud et al., 2020); (3) Leveraging on structural information that cannot provably be captured by the WL test (Bouritsas et al., 2020; Thiede et al., 2021; de Haan et al., 2020; Bodnar et al., 2021b;a). Our approach falls into the third category. It describes an architecture that uncovers discriminative structural information within subgraphs of the original graph, while preserving
3The wreath product models a setup in which the subgraphs are not aligned, see Maron et al. (2020); Wang et al. (2020) for further discussion.
4For all policies, node removal is implemented by removing all the edges to the node, so that all the subgraphs are kept aligned and have n nodes.
equivariance – typically lacking in (2) – and locality and sparsity of computation – generally absent in (1). Prominent works in category (3) count or list substructures from fixed, predefined banks. This preprocessing step has an intractable worst-case complexity and the choice of substructures is generally task dependent. In contrast, as we show in Section 3, our framework is provably expressive with scalable and non-domain specific policies. Lastly, ESAN can be combined with these related methods, as they can parameterize the Esubgraphs module whenever the application domain suggests so. We refer readers to Appendix B for a more detailed comparison of our work to relevant previous work, and to Appendix G for an in-depth analysis of its computational complexity.

heading: 3 THEORETICAL ANALYSIS
text: In this section, we study the expressive power of our architecture by its ability to provably separate non-isomorphic graphs. We start by introducing WL analogues for ESAN and then study how different design choices affect the expressive power of our architectures. We assume that sum aggregation is used for node features in DSS (Equation (1)) throughout this section.

heading: 3.1 A WL ANALOGUE FOR ESAN
text: We introduce two color-refinement procedures inspired by the WL isomorphism test (Weisfeiler & Leman, 1968). These variants, which we refer to as DSS-WL and DS-WL variants, are inspired by DSS-GNN and DS-GNN with a 1-WL equivalent base graph encoder (e.g., an MPNN), accordingly. The goal is to formalize our intuition that graphs may be more easily separated by properly encoding (a subset of) their contained subgraphs. Our variants are designed in a way to extract and leverage this discriminative source of information. Details and proofs are provided in Appendix E.
(Init.) Inputs to the DSS-WL test are two input graphs G1, G2 and a subgraph selection policy π. The algorithm generates the subgraph bags over the input graph by applying π. If initial colors are provided, each node in each subgraph is assigned its original label in the original graph. Otherwise, an initial, constant color is assigned to each node in each subgraph, independent of the bag.
(Refinement) On subgraph S, the color of node v is refined according to the rule: ct+1v,S ← HASH(ctv,S , N t v,S , C t v,M t v). Here, N t v,S denotes the multiset of colors in v’s neighborhood over subgraph S; Ctv represents the multiset of v’s colors across subgraphs; M t v is the multiset of these last ones (cross-subgraph aggregated colors) over v’s original neighborhood.
(Termination) At any step, each subgraph S is associated with color cS , representing the multiset of node colors therein. Input graphs are described by the multisets of subgraph colors in the corresponding bag. The algorithm terminates as soon as the graph representations diverge, deeming the inputs non-isomorphic. The test is inconclusive if the two graphs are assigned the same representations at convergence, i.e., when the color refinement procedure converges on each subgraph.
DS-WL is obtained as a special setting of DSS-WL whereby the refinement rule neglects inputs Ctv and M tv . These inputs account for information sharing across subgraphs, and by disabling them, the procedure runs the standard WL on each subgraph independently. We note that since DS-WL is a special instantiation of DSS-WL, we expect the latter to be as powerful as the former; we formally prove this in Appendix E. Finally, both DSS- and DS-WL variants reduce to trivial equivalents of the standard WL test with policy π : G 7→ {G}.

heading: 3.2 WL ANALOGUES AND EXPRESSIVE POWER
text: Our first result confirms our intuition on the discriminative information contained in subgraphs:
Theorem 1 (DS(S)-WL strictly more powerful than 1-WL). There exist selection policies such that DS(S)-WL is strictly more powerful than 1-WL in distinguishing between non-isomorphic graphs.
The idea is that it is possible to find policies5 such that (i) our variants refine WL, i.e. any graph pair distinguished by WL is also distinguished by our variants, and (ii) there exist pairs of graphs indistinguishable by WL but separated by our variants. These exemplary pairs include graphs from a specific family, i.e. Circulant Skip Link (CSL) graphs (Murphy et al., 2019; Dwivedi et al., 2020). We show that DS-WL and DSS-WL can distinguish pairs of these graphs:
5In the case of DS-WL it is required that the original graph is included in the bag.
Lemma 1. CSL(n, 2) can be distinguished from any CSL(n, k) with k ∈ [3, n/2 − 1] by DS-WL and DSS-WL with either the ND, EGO, or EGO+ policy.
It is possible to also find exemplary pairs for the ED policy: one is included is Figure 1, while another is found in Appendix E. Further examples to the expressive power attainable with our framework are reported in the next subsection. Next, the following result guarantees that the expressive power of our variants is attainable by our proposed architectures. Theorem 2 (DS(S)-GNN at least as powerful as DS(S)-WL; DS-GNN at most as powerful as DS-WL). Let F be any family of bounded-sized graphs endowed with node labels from a finite set. There exist selection policies such that, for any two graphsG1, G2 inF , distinguished by DS(S)-WL, there is a DS(S)-GNN model in the form of Equation (2) assigning G1, G2 distinct representations. Also, DS-GNN with MPNN base graph encoder is at most as powerful as DS-WL.
In particular, this theorem applies to policies such that each edge in the original graph appears at least once in the bag. This is the case of the policies in Section 2.2 and their augmented versions. The theorem states that, under the aforementioned assumptions, DSS-GNNs (DS-GNNs) are at least as powerful as the DSS-WL (DS-WL) test, and transitively, in view of Theorem 1, that there exist policies making ESAN more powerful than the WL test. This result is important, because it gives provable guarantees on the representation power of our architecture w.r.t. standard MPNNs: Corollary 1 (DS(S)-GNN is strictly more powerful than MPNNs). There exists subgraph selection policies such that DSS-GNN and DS-GNN architectures are strictly more powerful than standard MPNN models in distinguishing non-isomorphic graphs.
The corollary is an immediate consequence of Theorem 1, Theorem 2 and the results in Xu et al. (2019); Morris et al. (2019), according to which MPNNs are at most as powerful as the WL test.

heading: 3.3 THEORETICAL EXPRESSIVENESS OF DESIGN CHOICES
text: Our general ESAN architecture has several important design choices: choice of DSS-GNN or DSGNN for the architecture, choice of graph encoder, and choice of subgraph selection policy. Thus, here we study how these design choices affect expressiveness of our architecture.
DSS vs. DS matters. To continue the discussion of the last section, we show that DSS-GNN is at least as powerful as DS-GNN, and is in fact strictly stronger than DS-GNN for a specific policy. Proposition 1. DSS-GNN is at least as powerful as DS-GNN for all policies. Furthermore, there are policies where DSS-GNN is strictly more powerful than DS-GNN.
Base graph encoder choice matters. Several graph networks with increased expressive power over 1-WL have been proposed (Sato, 2020; Maron et al., 2019a). Thus, one may desire to use a more expressive graph network than MPNNs. The following proposition analyzes the expressivity of a generalization of DS-GNN to use a 3-WL base encoder; details are given in the proof in Appendix F.
Proposition 2. Let the subgraph policy be depth-1 ÊGO or ÊGO+. Then: (1) DS-GNN with a 3- WL base graph encoder is strictly more powerful than 3-WL. (2) DS-GNN with a 3-WL base graph encoder is strictly more powerful than DS-GNN with a 1-WL base graph encoder.
Part (1) shows that our DS-GNN architecture improves the expressiveness of 3-WL graph encoders over 3-WL itself, so expressiveness gains from our ESAN architecture are not limited to the 1-WL base graph encoder case. Part (2) shows that our architecture can gain in expressive power when increasing the expressive power of the graph encoder.
Subgraph selection policy matters. Besides complexity (discussed in Appendix G), different policies also result in different expressive power of our model. We analyze the case of 1-WL (MPNN) graph encoder for different choices of policy, restricting our attention to strongly regular (SR) graphs. These graphs are parameterized by 4 parameters (n, k, λ, µ), where n is the number of nodes, k is the degree of each node, λ is the number of common neighbors for any adjacent nodes, and µ is the number of common neighbors for any non-adjacent nodes. SR graphs are an interesting ‘corner case’ often used for studying GNN expressivity, as any SR graphs of the same parameters cannot be distinguished by 1-WL or 3-WL (Arvind et al., 2020; Bodnar et al., 2021b;a).
We show that our framework with the ND and depth-n EGO+ policies is able to distinguish any SR graphs of different parameters. However, just like 3-WL, we cannot distinguish SR graphs of the
same parameters. On the other hand, the ED policy can distinguish certain pairs of non-isomorphic SR graphs of the same parameters, while still being able to distinguish all SR graphs of different parameters. We now formalize the above statements in Proposition 3.
Proposition 3. Consider DS-GNN on SR graphs: (1) ND, EGO+, ED can distinguish any SR graphs of different parameters, (2) ND, EGO+ cannot distinguish any SR graphs of the same parameters, (3) ED can distinguish some SR graphs of the same parameters. The EGO+ policies are at depth-n. Thus, for distinguishing SR graphs, ND and depth-n EGO+ are no stronger than 3-WL, while ED is strictly stronger than 3-WL.

heading: 4 EXPERIMENTS
text: We perform an extensive set of experiments to answer five main questions: (1) Is our approach more expressive than the base graph encoders in practice? (2) Can our approach achieve better performance on real benchmarks? (3) How do the different subgraph selection policies compare? (4) Can our efficient stochastic variant offer the same benefits as the full approach? (5) Are there any empirical advantages to DSS-GNN versus DS-GNN?.
Datasets. We conduct experiments on eleven graph classification datasets originating from three data repositories: (1) RNI (measuring expressive power) (Abboud et al., 2020), (2) TUD repository (social network analysis and bioinformatics) (Morris et al., 2020a) and (3) Open Graph Benchmark (molecules) (Hu et al., 2020). These datasets are diverse on a number of important levels, including the number of graphs (188-41,127), existence of input node features, and sparsity.
Methods in comparison. We compare our approach to a wide range of methods, including maximally expressive MPNNs (Xu et al., 2019; Morris et al., 2019). We particularly focus on more expressive GNNs (Maron et al., 2019a; de Haan et al., 2020; Bouritsas et al., 2020; Abboud et al., 2020; Bodnar et al., 2021b; Abboud et al., 2020) and also compare to DropEdge (Rong et al., 2019) and ID-GNN (You et al., 2021), that share some similarity with our ED and EGO policies.6
Implementation and experimental details. We experimented with both DSS-GNN and DS-GNN on all the datasets and used popular MPNN-type GNNs as base encoders: GIN (Xu et al., 2019),
6We implemented the fast version of ID-GNN with 10 dimensional augmented node features.
GraphConv (Morris et al., 2019), and GCN (Kipf & Welling, 2017) using all four selection policies (ND, ED, EGO, and EGO+). We use max for aggregating the adjacency matrices for DSS-GNN. More implementation details can be found in Appendix C.
EXP and CEXP datasets. We first tested the benefits of our framework on the synthetic EXP and CEXP datasets (Abboud et al., 2020), specifically designed so that any 1-WL GNN cannot do better than random guess (50% accuracy in EXP, 75% in CEXP). We report the mean and standard deviation from 10-fold cross-validation in Table 5 in Appendix D. While GIN and GraphConv perform no better than a random guess, DS- and DSS-GNN perfectly solve the task when using these layers as base graph encoders, with all the policies working equally well. Table 7 in Appendix D shows the performance of our stochastic variant. In all cases our approach yields almost perfect accuracy, where DSS-GNN works better than DS-GNN when sampling only 5% of the subgraphs.
TUDatasets. We experimented with seven popular datasets from the TUD repository. We followed the widely-used hyperparameter selection and experimental procedure proposed by Xu et al. (2019). Results are reported in Table 1. We observe that: (1) ESAN variants achieve excellent results with respect to SoTA methods: they score first, second and third in, respectively, two, four and one dataset out of seven; (2) ESAN consistently improves over the base encoder, up to almost 5% (DSSGNN: 51/56 cases, DS-GNN: 42/56 cases, see gray background in table); (3) ESAN consistently outperforms other methods aimed at increasing the expressive power of GNNs, such as ID-GNN (You et al., 2021) and RNI (Abboud et al., 2020). Particularly successful configurations are: (i) DSSGNN (EGO+) + GraphConv/GIN; (ii) DS-GNN (ND) + GIN. Table 6 in Appendix D compares the performance of our stochastic sampling variant with the base encoder (GIN) and the full approach. Our stochastic version provides a strong and efficient alternative, generally outperforming the base encoder. Intriguingly, stochastic sampling occasionally outperforms even the full approach.
Table 2: Test results for OGB datasets. Gray background indicates that ESAN outperforms the base encoder.
OGBG-MOLHIV OGBG-MOLTOX21 Method ROC-AUC (%) ROC-AUC (%)
GCN (Kipf & Welling, 2017) 76.06±0.97 75.29±0.69
DS-GNN (GCN) (ED) 74.70±1.94 74.86±0.92 DS-GNN (GCN) (ND) 74.40±2.48 75.79±0.30 DS-GNN (GCN) (EGO) 74.00±2.38 75.41±0.72 DS-GNN (GCN) (EGO+) 73.84±2.58 74.74±0.96
DSS-GNN (GCN) (ED) 76.00±1.41 75.34±0.69 DSS-GNN (GCN) (ND) 75.17±1.35 75.56±0.59 DSS-GNN (GCN) (EGO) 76.16±1.02 76.14±0.53 DSS-GNN (GCN) (EGO+) 76.50±1.38 76.29±0.78
GIN (Xu et al., 2019) 75.58±1.40 74.91±0.51
DS-GNN (GIN) (ED) 76.43±2.12 75.12±0.50 DS-GNN (GIN) (ND) 76.19±0.96 75.34±1.21 DS-GNN (GIN) (EGO) 78.00±1.42 76.22±0.62 DS-GNN (GIN) (EGO+) 77.40±2.19 76.39±1.18
DSS-GNN (GIN) (ED) 77.03±1.81 76.71±0.67 DSS-GNN (GIN) (ND) 76.63±1.52 77.21±0.70 DSS-GNN (GIN) (EGO) 77.19±1.27 77.45±0.41 DSS-GNN (GIN) (EGO+) 76.78±1.66 77.95±0.40
OGB. Finally, we tested the ESAN framework on the OGBG-MOLHIV and OGBG-MOLTOX21 datasets from Hu et al. (2020) using the scaffold splits. Table 2 compares the results of all ESAN variants to the the performance of the base variants (GIN and GCN). It can be seen that when using GIN, all ESAN variants improve the base encoder accuracy by up to 2.4% on OGBG-MOLHIV and 3% on OGBGMOLTOX21. In addition, DSS-GNN performs better that DS-GNN with GCN. Finally, DSSGNN improves the base encoder in 14/16 cases, whereas a DS-GNN improves it in 10/16 cases.
Timing. Detailed timing results are provided in Appendix D. Roughly speaking, on NCI1, DS-GNN and DSS-GNN take respectively 2x and 3x the time of the corresponding base graph encoder for a single training epoch. The sampling approach (20%) reduces these times by 10-15%. Noticeably, the gap decreases when considering the entire training, due to additional overheads.

heading: 5 CONCLUSION AND FUTURE DIRECTIONS
text: We have presented ESAN, a novel framework for learning graph-structured data, based on decomposing a graph into a set of subgraphs and processing this set in a manner respecting its symmetry structure. We have shown that ESAN increases the expressive power of several existing graph learning architectures and performs well on multiple graph classification benchmarks. The main limitation of our approach is its increased computational complexity with respect to standard MPNNs. We have proposed a more efficient stochastic version to mitigate this limitation and demonstrated that it performs well in practice. In follow-up research, we plan to investigate the following directions: (1) Is it possible to learn useful subgraph selection policies? (2) Can higher order structures on subgraphs (e.g., a graph of subgraphs) be leveraged for better expressive power? (3) A theoretical analysis of the stochastic version and of different policies/aggregation functions.

heading: A BACKGROUND: LEARNING ON SETS AND GRAPHS
text: In this section we present a brief introduction to GNNs, equivariance and set learning.
Graph neural networks. GNNs are a type of neural networks that process graphs as input. Their roots can be traced back to the field of computational chemistry Kireev (1995); Baskin et al. (1997) and the pioneering works of Sperduti (1994); Goller & Kuchler (1996); Sperduti & Starita (1997); Gori et al. (2005); Scarselli et al. (2008). In recent years, GNNs have become a major research direction and are used in many application fields such as social network analysis (Fan et al., 2019), molecular biology (Jin et al., 2018), physics (Shlomi et al., 2020) and computer vision (Johnson et al., 2018). Over the years, several ideas have served as inspiration for GNNs, including spectral graph theory (Bruna et al., 2013; Bronstein et al., 2017) and equivariance (Maron et al., 2019b; Bronstein et al., 2021). Message-passing neural networks (MPNNs) (Gilmer et al., 2017; Morris et al., 2019; Xu et al., 2019) have been the most popular approach to this problem. These models are inspired by convolutional networks on images because of their locality and stationary characteristics. These networks are composed of several layers, which update node (and edge, if available) features based on the local graph connectivity. There are several ways to define a message passing layer. For example, the following is a popular formulation (Morris et al., 2019):
xtv = W t 1x t−1 v +W t 2 ∑ u∼v xt−1u + b t (3)
Here, xtv ∈ Rdt is the feature associated with a node v after after applying the t-th layer, Wi ∈ Rdt×dt−1 , bt ∈ Rdt are the learnable parameters, and u ∼ v means that the nodes are adjacent. Expressive power of GNNs. There is a particular interest in the expressive power of GNNs (Sato, 2020). The seminal works of Morris et al. (2019); Xu et al. (2019) analyzed the expressive power of MPNNs and showed that their ability to distinguish graphs is the same as the first version of the WL graph isomorphism test introduced by Weisfeiler & Leman (1968). Importantly, this test cannot distinguish rather simple pairs of graphs (see Figure 1). In general, WL tests are a polynomial time hierarchy of graph isomorphism tests: for k > k′, k-WL is strictly more powerful than k′-WL (Cai et al., 1992), but requires more time and space complexity which is exponential in k. These works inspired a plethora of novel GNNs with improved expressive power (Maron et al., 2019a; Bouritsas et al., 2020; Bodnar et al., 2021b;a; Vignac et al., 2020; Murphy et al., 2019; Chen et al., 2019). See Appendix B for a detailed discussion.
Invariance and equivariance The notion of symmetry, expressed through the action of a group on signals defined on some domain, is a key concept of ‘geometric deep learning’, allowing to derive from first principles many modern deep representation learning architectures (Bronstein et al., 2021). Let H be a group acting on vector spaces V,W . We say that a function f : V → R is H-invariant if f(h · x) = f(x) for all x ∈ V, h ∈ H . Similarly, a function f : V → W is equivariant if the function commutes with the group action, namely f(h · x) = h · f(x) for all x ∈ V, h ∈ H . Constructing invariant and equivariant learning models has become a central design paradigm in machine learning, see e.g., Cohen & Welling (2016); Ravanbakhsh et al. (2017); Kondor & Trivedi (2018); Esteves et al. (2018). In particular, graphs typically do not have a canonical ordering of nodes, forcing GNN layers to be permutation-equivariant.
Deep learning on Sets. Sets can be considered as a special case of graphs with no edges, and learning on set-structured data has recently become an important topic with applications such as computer graphics and vision dealing with 3D point clouds (Qi et al., 2017). A set of n items can be encoded in an n × d feature matrix X , and since the order of rows is arbitrary, one is interested in functions that are invariant or equivariant under element permutations. The works of Zaheer et al. (2017); Ravanbakhsh et al. (2016); Qi et al. (2017) were the first to suggest universal architectures for set data. They are based on element-wise functions and global pooling operations. For example, a Deep Sets layer takes the form
xti = W t 1x t−1 i +W t 2 n∑ j=1 xt−1j + b t (4)
Here, xti is the feature of the i-th set element after applying layer t. Alternatively, this layer can be described as a message passing layer on a complete graph with Equation 3.
Recently, Maron et al. (2020) suggested the Deep Sets for Symmetric elements framework (DSS), a generalization of Deep Sets to a learning setup in which each element has its own symmetry structure, represented by another group G acting on the d-dimensional vectors in the input (the rows of X), such as translations in the case of images. The paper characterizes the space of linear equivariant layers which boil down to replacing the unconstrained fully-connected matrices Wi in the equation above with corresponding linear equivariant layers, like convolutions in the case of images. We observe that when W2 = 0, we obtain a simple Siamese network. Importantly, the paper shows that when W2 6= 0, the network exhibits a greater expressive power. Intuitively this is due its enhanced information-sharing abilities within the set.

heading: B RELATION TO PREVIOUS WORKS
text: Processing subgraphs for graph learning. Our approach is related to multiple techniques in graph learning. Introduced for semi-supervised node-classification tasks, DropEdge (Rong et al., 2019) can be considered as a stochastic version of the ED policy that processes one single edge-deleted subgraph at a time. Ego-GNNs (Sandfelder et al., 2021) resemble our EGO policy, as messages are passed within each node’s ego-net, and are aggregated from each ego-net that a node is contained in. ID-GNNs (You et al., 2021) resemble the EGO+ policy, the difference being the way in which the root node is identified and the way the information between the ego-nets is combined. RNP-GNNs (Tahmasebi & Jegelka, 2020) learn functions over recursively-defined node-deleted ego-nets with augmented features, which allows for high expressive power for counting substructures and computing other local functions. FactorGCN (Yang et al., 2020) is a model that disentangles relations in graph data by learning subgraphs containing edges that capture latent relationships. The graph automorphic equivalence network (Xu et al., 2020) compares ego-nets to subgraph templates in a GNN architecture. Furthermore, Hamilton et al. (2017) introduce a minibatching procedure that samples neighborhoods for each GNN layer — in large part for the sake of efficiently processing large graphs. Other works like Cluster-GCN (Chiang et al., 2019) and GraphSAINT (Zeng et al., 2020) have followed by developing methods for sampling whole subgraphs at a time, and then processing these subgraphs with a GNN.
Provably expressive GNNs. The inability of WL to disambiguate even simple graph pairs has recently sparked particular interest in provably expressive GNNs. A fruitful streamline of works (Morris et al., 2019; 2020b; Kondor et al., 2018; Maron et al., 2019b;a; Keriven & Peyré, 2019; Azizian & Lelarge, 2021) has proposed architectures aligning to the k-WL hierarchy; the expressiveness of these models is well characterized in terms of this last, but these guarantees come at the cost of a generally intractable computational cost for k ≥ 3. Additionally, most of these architectures lack an important feature contributing to the recent success of GNNs: locality of computation. In an effort to maintain the inductive bias of locality, recent works have proposed to provably enhance the expressiveness of GNNs by augmenting node features with random identifiers (Sato et al., 2021; Loukas, 2020; Abboud et al., 2020; Puny et al., 2020) or auxiliary colourings (Dasoulas et al., 2020). Although of scalable and immediate implementation, these approaches may not preserve equivariance w.r.t. node permutations and random features in particular have been observed to under-perform in generalising outside of training data.
A family of works focused on building local and equivariant provably powerful architectures and, for this reason, is especially related to our approach. Of particular relevance are works which argued for the use of (higher-order) structural information. Structural node identifiers obtained as subgraph isomorphism counting were introduced in Bouritsas et al. (2020). Alternatively, Srinivasan & Ribeiro (2020); de Haan et al. (2020); Thiede et al. (2021) argue for the use the automorphism group of edges and substructures to obtain more expressive representations. These features cannot be computed by standard MPNNs (Chen et al., 2020) for substructures different than trees and they can provably enhance the expressiveness of standard MPNNs while retaining their local inductive bias. Bodnar et al. (2021b;a) introduced the idea of lifting graphs to more general topological spaces such as simplicial and cellular complexes. Higher-order structures are first-class objects thereon and message passing is directly performed on them. In general, listing (or counting) substructures has an intractable worst-case complexity and the design of the substructure bank may be difficult in certain cases. This makes these models of less obvious application outside of the molecular and social domain, where the importance of specific substructures is not well understood and their number may rapidly grow.
Our framework, on the contrary, attains locality, equivariance and provable expressiveness with scalable and non-domain specific policies. Any of the ED, ND, and EGO(+) policies make our approach strictly more powerful than standard MPNNs (see Section E), and the generation of the bags is computationally tractable, independently of the graph distribution at hand (more in Section G). Either way, we remark that the aforementioned works are compatible with our overall framework, and can be employed to parameterize the Esubgraphs module in those cases where our approach may benefit from provably powerful and domain-specific base graph encoders.
As a final note, we would like to point out the presence of two recent works which focused on the problem of automatically extracting relevant graph substructures in an automated way. Bouritsas et al. (2021) propose a model that can be trained to partition graphs into substructures for lossless compression; Chen et al. (2021) show how the model introduced in Chen et al. (2020) can achieve competitive results while retaining interpretability by the detection of the graph substructures employed by such model to make its decisions. These approaches may potentially be used to design more advanced subgraph selection policies.

heading: B.1 COMPARISON TO RECONSTRUCTION GNNS
text: Contemporaneous work by Cotta et al. (2021) takes motivation from the node reconstruction conjecture (Kelly, 1957) in developing a model that processes node-deleted subgraphs of a given graph by independent MPNNs. Thus, there are some connections between our work and theirs. Nevertheless, we develop a more general framework; in fact, the Reconstruction GNN (Cotta et al., 2021) is exactly our DS-GNN with a k-node-deletion subgraph selection policy. There are multiple substantial differences between these works, which we discuss below.
Architecture for processing bags of subgraphs: In the terminology of our paper, Cotta et al. (2021) use a DS-GNN architecture, while we perform a rigorous and more specific analysis of equivariance, and argue in favor of a different and more powerful DSS-GNN architecture. We show that DS-GNN is theoretically too restrictive in terms of the invariance it enforces (see the DS-GNN paragraph in Section 2.1) and we prove that DSS-GNN is strictly stronger than DS-GNN for certain policies (see Proposition 1). Moreover, our DSS-GNN achieves better empirical results than DS-GNN in most of the tested settings, so this theoretical benefit leads to practical gains.
General subgraph policies: We advocate general subgraph policies, four of which are studied in the paper (node-deletion, edge-deletion, ego-nets and ego-nets+). There are many other possible subgraph policies that fit into our framework, such as those based on trees. In Section 4, we show that the node-deletion policy is not the optimal subgraph selection policy in many practical settings (e.g., on the ZINC12K dataset, the EGO and EGO+ policies perform significantly better).
More general theoretical analysis: We provide a more general theoretical analysis. First, since we consider general subgraph selection policies, we are able to prove results for many policies in the same way (e.g. as in Proposition 3), not just for node-deletion policies. Second, we consider higherorder graph encoders in our general framework, whereas Cotta et al. (2021) considers MPNNs and universal feed forward networks. We prove results on the integration of higher-order encoders in our ESAN framework in Proposition 2.
Formulation of new WL variants: We also develop and analyze new variants of the WeisfeilerLehman test (DS-WL and DSS-WL). We then characterize the expressive power of DS-GNN and DSS-GNN in terms of these variants (see Theorem 2), which helps us to prove other results in Section 3.3, and will help in proofs for future work. In comparison, there is no such WL variant developed by Cotta et al. (2021).
Basic motivation: The paper of Cotta et al. (2021) is mainly motivated by the Reconstruction Conjecture in graph theory. In contrast, our paper is motivated by the recent work by Maron et al. (2020) on architectures that are equivariant to product symmetry groups arising when dealing with sets of objects containing internal symmetries.
C IMPLEMENTATION DETAILS
We implemented our approach using the PyG framework (Fey & Lenssen, 2019) and ran the experiments on NVIDIA DGX V100 stations. We performed hyper parameter tuning using the Weights and Biases framework (Biewald, 2020) for all the methods, including the baselines.
Details of hyper parameter grids and architectures are discussed in the subsections below.

heading: C.1 TUDATASETS
text: We considered the evaluation procedure proposed by Xu et al. (2019). Specifically, we conducted 10-fold cross validation and reported the validation performances at the epoch achieving the highest averaged validation accuracy across all the folds. We used Adam optimizer with learning rate decayed by a factor of 0.5 every 50 epochs. The training is stopped after 350 epochs. As for DS-GNN, we implemented Rsubgraphs with summation over node features, while module Esets is parameterized with a two-layer DeepSets with final mean readout; layers are in the form of Equation (4). In DSSGNN, we considered the mean aggregator for the feature matrix and used the adjacency matrix of the original graph. We implemented Rsubgraphs by averaging node representations on each subgraph; Esets is either a two-layer DeepSets in the form of Equation (4) with final mean readout, or a simple averaging of subgraphs representations (the choice is driven by hyper parameter tuning). We considered two baseline models, namely GIN (Xu et al., 2019) and GraphConv (Morris et al., 2019) and based our hyper parameter search on the same parameters of the corresponding baseline, as detailed below.
GIN. We considered the same architecture as in Xu et al. (2019), with 4 GNN layers with all MLPs having 1 hidden layer. We used the Jumping Knowledge scheme from Xu et al. (2018) and employed batch normalization (Ioffe & Szegedy, 2015). As in Xu et al. (2019), we tuned the batch size in {32, 128}, the embedding dimension of the MLPs in {16, 32} and the initial learning rate in {0.01, 0.001}. We tuned the embedding dimension of the DeepSets layers of Esets in {32, 64}.
GraphConv. We considered the same architecture as in Morris et al. (2019), with 3 GNN layers and embedding dimension of 64. We added batch normalization (Ioffe & Szegedy, 2015) after each layer in all models, as we noticed a gain in performances. For a fair comparison, we tuned batch size, learning rate and DeepSets hidden channels over the same grid employed for GIN.
Additional comparisons. We additionally implemented and compared our models to Dropedge (Rong et al., 2019), RNI (Abboud et al., 2020) and ID-GNN (You et al., 2021). For Dropedge, we used a drop rate of 20% to drop edges while training. For RNI, we considered Partial-RNI where 50% of node features are randomized and the remaining are deterministically set to the initial node features. For ID-GNN, we implemented the fast version with 10 dimensional augmented node features, due to the good performances presented in the original paper.

heading: C.2 OGB DATASETS
text: We used the evaluation procedure proposed in Hu et al. (2020). Specifically, we ran each experiment with 10 different initialization seeds and we reported the mean performances (along with standard deviation) corresponding to the best validation result. We used Adam optimizer and trained for 100 epochs. We considered two baseline models: GIN (Xu et al., 2019) and GCN (Kipf & Welling, 2017) and we kept the proposed parameters (Hu et al., 2020), i.e., 5 GNN layers with embedding dimension 300. We tuned the learning rate in {0.001, 0.0001}. DS-GNN implements Rsubgraphs as either averaging or summation of node representations, the choice is made based on validation ROCAUC. Esets is a two-layer DeepSets (Equation (4)) with final mean readout. Its hidden dimension is tuned in {32, 64}. As for DSS-GNN, we used the mean aggregator for the feature matrix and used the adjacency matrix of the original graph. Module Rsubgraphs applies averaging over node representations and, in turn, Esets averages the obtained subgraph encodings.

heading: C.3 RNI DATASETS
text: We used the same training procedure and hyper parameter search scheme considered for TUDatasets. The only architectural difference is the number of GNN layers that we increased to 6 and the embedding dimension that we fixed to 32.

heading: D ADDITIONAL EXPERIMENTS
text: In this section, we present some experimental results in more detail. Table 3 shows the full results on the TUDatasets, including a comparison to the graph kernels (Gärtner et al., 2003; Shervashidze
et al., 2009; 2011; Neumann et al., 2016). As discussed in the main paper, to guarantee at least the expressive power of the basic graph encoder used for DS-GNN one can add the original graph G to SπG for any policy π, obtaining the augmented version π̂. We included results for our DS-GNN on the augmented policies in Table 3. As can be seen from the table, DS-GNN obtains very similar results for any policy and its corresponding augmented version. Table 4 shows the full results on the OGB datasets, reporting training, validation and test performances. Table 5 reports the results on the RNI datasets. In the following, we present results from additional experiments and provide an overall discussion of our experimental results.

heading: D.1 STOCHASTIC SAMPLING RESULTS
text: We performed our stochastic sampling using GIN as a base encoder. We considered three different subgraph sub-sampling ratios: 5%, 20% and 50%. While training, we randomly sampled a subset of subgraphs for each graph in each epoch. During evaluation, we performed majority voting using 5 different subgraph sampling sets for each graph. We performed hyper parameter tuning as detailed in Appendix C, and compared the performances of the sub-sampling method both to the base encoder, and to the corresponding approach without the sub-sampling procedure (reported as 100%). Results for the TUDatasets can be found in Table 6. As can be seen in the table, the performance of our approaches do not generally degrade when seeing only a fraction of the subgraphs. We showcased the importance of sampling by adding experiments on RDT-B dataset, which contains large graphs (430 nodes and 498 edges per graph on average) and sampling is employed to alleviate the computational burden. We used the same hyperparameter tuning and evaluation strategy of the other
TUDatasets but we fixed the batch size to 32. ESAN outperforms the base encoder even when only seeing 5% of the subgraphs. Table 7 shows the performance of our stochastic variant on the RNI datasets. Even a small fraction of subgraphs is enough to achieve good results on EXP and CEXP. Notably, DSS-GNN works better than DS-GNN for the fraction 5%. Similarly, Table 7 also reports the performances on the OGB datasets.

heading: D.2 GRAPH ISOMORPHISM TESTING ON THE CSL BENCHMARK
text: To further test the expressive power of our framework, we additionally considered the CSL dataset (Murphy et al., 2019; Dwivedi et al., 2020). The dataset consists of 150 Circulant Skip Link Graphs uniformly distributed in 10 classes, which represent their isomorphism class. These graphs are known to be all 1-WL equivalent and, in virtue of this, standard MPNNs perform as random guessers on this prediction task (10% accuracy) (Dwivedi et al., 2020).
We focused on DS-GNN using ND and ED policies, considering both the full approach and the subgraph sampling one (5%, 20% and 50% sampling rates). Even with 1-WL base encoders, ESAN achieves perfect performance in all cases. Interestingly, we find that, when employing the ND selection policy, DS-GNN with less than 5 layers can not differentiate CSL(41, 9) from CSL(41, 12) and only achieves 90% accuracy. Increasing the number of layers is crucial for DS-GNN to achieve perfect performance in this case. In the case of random subgraph sampling, isomorphic graphs may be
mapped to different representations and possibly different classes due to the randomness introduced by the sampling procedure. However, we observed that sampling does not deteriorate performance in practice: ESAN was able to still obtain perfect accuracy. We hypothesise that different samplings of the same bag are still mapped closely in the embedding space, this allowing our models to easily predict the same isomorphism class for all of them.

heading: D.3 MOLECULAR PROPERTY PREDICTION ON ZINC
text: We further experimented with an additional large scale molecular benchmark: ZINC12K (Sterling & Irwin, 2015; Gómez-Bombarelli et al., 2018; Dwivedi et al., 2020). This dataset has been recently proposed as a solid and convenient test bed to jointly compare the performance of various GNN architectures (Dwivedi et al., 2020). Additionally, it has often been employed as a preferred real-world benchmark for provably powerful GNNs, which have interestingly exhibited particularly strong performance over standard MPNN architectures of bounded expressiveness (Corso et al., 2020; Bouritsas et al., 2020; Bodnar et al., 2021a).
The ZINC12K dataset comprises 12k molecular graphs, with an associated real target value representing the constrained solubility of the molecule, expressed in terms of the octanol-water partition coefficient (logP) (Gómez-Bombarelli et al., 2018). Throughout our experimentation, we used the same train, validation and test splits prescribed in Dwivedi et al. (2020), whose prescribed overall optimization and benchmarking setup we verbatim follow. We used Mean Absolute Error (MAE) as the training loss and evaluation performance metric. Our models are trained with batches of size 128 and an Adam optimizer whose learning rate is initially set to 0.001, reduced by 0.5 whenever the validation loss does not improve after a patience value set to 20 epochs. Training is stopped when the learning rate reduces below 10−5. We ran each experiment for 10 different initialization seeds, and reported the mean performances (along with standard deviation) at the time of the early stopping. All models feature 4 GNN layers, as common in this benchmark. Importantly, in order
to comply with the 10k parameter budget advocated in Dwivedi et al. (2020), we set the embedding dimension of all GNN modules employed in our models to 64.
DS-GNN implements Rsubgraphs as averaging of node representations while Esets is a two-layer invariant DeepSets (Zaheer et al., 2017) with final mean readout. Specifically, we tune φ and ρ to either be both a single layer or a 2-layers MLP, with dimensions fixed to 96. As for DSS-GNN, we used the mean aggregator for the feature matrix and used the adjacency matrix of the original graph. Module Rsubgraphs applies averaging over node representations and, in turn, Esets averages the obtained subgraph encodings.
We observe from Table 8 that all ESAN configurations significantly outperform their base GIN encoder, while having a comparable number of learnable parameters. This is in line with the general
trend emerging from the rest of our experimental results. Second, we notice that our method achieves particularly competitive results, irrespective of the chosen subgraph selection policy. All our configurations outperform the provably expressive PNA model (Corso et al., 2020). At the same time, when equipped with the EGO(+) selection policies, our approach outperforms HIMP (Fey et al., 2020), DGN (Beaini et al., 2021) as well as SMP (Vignac et al., 2020) and GSN (Bouritsas et al., 2020), whose expressive power is strictly greater than standard MPNNs.
CIN (Bodnar et al., 2021a) is the only method outperforming ESAN. However, a large contribution to its performance is given by the explicit modeling of cycles / rings, which are listed beforehand in a preprocessing step. Ring structures are known as powerful inductive biases in organic chemistry and, according to the ablation study reported in the aforementioned paper (Table 9, Appendix E), this indeed represents a pivotal factor in explaining its test performance, more than its ability to disambiguate non-isomorphic graphs. Similarly to CIN, HIMP and GSN also explicitly employ information from rings and their counts, yet are outperformed by ESAN. This is an important result, because, contrary to these models, the policies considered in our paper are not tailored for specific application domains – something that, on the other hand, can be advantageous in other settings.
We can conclude that, on this benchmark, ESAN is the best performing model amongst all provably expressive, domain agnostic GNNs. At the same time, it is competitive with and often of superior performance than (provably expressive) GNNs which employ domain specific structural information such as rings.

heading: D.4 SIZE OF THE MODELS
text: As already discussed, on TUDatasets, our ESAN variants tend to outperform their base encoders in the majority of the cases. We made sure to fairly tune these baseline models specifically for each dataset, aiming at a valid comparison with our approach. However, one may still wonder whether the improvements of ESAN are due to an overall larger number of parameters. This aspect is investigated in the following for the case of GIN base graph encoders.
First, we compared the number of trainable parameters of the best baseline model with that of our best ESAN configuration; numbers are reported in Table 9. We found the best ESAN configuration to utilise fewer learnable parameters in three out of seven datasets: IMDB-B, IMDB-M and PTC.
In order to verify the fairness of our results on the remaining datasets, we conducted additional experiments, training larger GIN architectures obtained by enlarging the dimension of the hidden layers in a way to approximately match the overall number of ESAN parameters. We dub these models “BIG-GIN”. The results are reported in Table 10. We observed that, on average, adding more parameters to baselines produced slightly worse results and did not change the ranking of the methods. Using baselines with more parameters yielded marginally worse results for two datasets (PROTEINS, NCI109) and only insignificantly better results on the remaining ones (NCI1, MUTAG). This demonstrates that, while a larger number of parameters tend to correlate with larger model capacity, it does not necessarily correlate with generalization performance, which is what we are really interested in.
We finally refer readers to Table 8, where we report the results obtained on the ZINC12K datasets. On this benchmark, all ESAN configurations significantly outperformed their GIN base encoder while being all compliant to the 100k parameter budget.

heading: D.5 TIMING
text: We focus our analysis on NCI1 dataset from Morris et al. (2020a) (4110 graphs, 30 nodes/edges per graph on average) and estimated the time to perform a single training epoch on a RTX 2080 GPU. We used GIN as a base encoder and compared the times of: (1) DS-GNN and DSS-GNN without sampling (100% subgraphs – full bags); (2) DS-GNN and DSS-GNN with sampling (20% of subgraphs); (3) the baseline GIN method. We kept the hyperparameters the same for all methods to allow a fair comparison. Results are reported in Table 11. As can be seen in the table, our method takes around 2x the time of the corresponding GIN baseline for DS-GNN, and around 3x for DSS-GNN. Sampling reduces these times by 10-15%, showcasing how our stochastic version can be beneficial in practice. Note that these times consider a single process completing a single training epoch. In our implementation, we perform the cross validation in parallel, making use of multiprocessing. The overall speedup gained by the parallelism comes at the cost of a fixed overhead. This added overhead reduces significantly the gap between our method and the baseline. In practice, we take less than twice the time of GIN on the NCI1 dataset, even without sampling. Indeed, DS-GNN (GIN) takes around 50 minutes to perform the entire 10-fold cross validation with 350 epochs for all policies and full bags, with DSS-GNN (GIN) taking a few minutes longer. GIN takes around 30 minutes for the same amount of work.
Further timing experiments on ZINC12K confirmed the empirically tractable computational complexity of our approach: for a training epoch on 10k graphs, DS-GNN required only between 3 and 3.5 seconds (depending on the policy), while DSS-GNN required between 3.7 and 4.25 seconds (the base encoder ran in slightly less than 1.5 seconds). Full results are reported in Table 11.

heading: D.6 DISCUSSION
text: Do our experimental results answer the research questions we raised at the beginning of Section 4? We discuss them in specific here below.
(1) Is our approach more expressive than the base graph encoders in practice? ESAN perfectly solves the RNI and CSL expressiveness benchmarks with a variety of subgraph selection policies, while the base encoder (GIN) performs as a random guesser (see Table 5). These results provide a (strong) positive answer to this question.
(2) Can our approach achieve better performance on real benchmarks? On real world graph datasets, ESAN has outperformed its base encoder in most of its configurations. Superior performance has been recorded across benchmarks, independently of the choice of the base encoder and the subgraph selection policy. In particular, we found ESAN to outperform its base graph encoder in 91% and 75% of the cases for, respectively, the DSS-GNN and DS-GNN variants. Overall, ESAN attains performance comparable to state-of-the-art methods on the TUDatasets and, in particular, on ZINC12K, where it significantly outperforms all provably expressive, domain agnostic GNNs.
ESAN appears generally less competitive on the OGB dataset with respect to state-of-the-art methods (Bodnar et al., 2021a; Bouritsas et al., 2020; Beaini et al., 2021). We hypothesise that a different choice of base graph encoders may lead to further improvements on this benchmark and defer such investigations to future work.
(3) How do the different subgraph selection policies compare? This question has a less definite answer. We found certain policies to attain more competitive results on some benchmarks (e.g. ND on PROTEINS for DS-GNN(GIN) and EGO(+) on ZINC), while they all seemed to perform equally well on others (e.g. on IMDB-M and on NCI1 for the DSS-GNN variant). Our results do not strongly support correlations between the performance of a specific policy and the application domain. At the same time, the EGO(+) policies were found generally more consistent in their results across datasets.
(4) Can our efficient stochastic variant offer the same benefits as the full approach? Our results suggest a generally affirmative answer. From Table 6, it emerges that, barring a few notable exceptions, our subgraph sampling scheme has marginal to no impact to the overall performance of ESAN, even for drastic sampling rates. This is particularly evident over the IMDB-B and IMDBM social benchmarks, as well as the PROTEINS bioinformatics one. In these and other cases, subgraph sampling sometimes slightly outperforms even the full, deterministic approach. Similar conclusions can be drawn from Table 7. An interesting trend is worth reporting: In the case of the DS-GNN variant, subgraph sampling negatively affects EGO(+) policies, sometimes consistently. This is clearly evident on the MUTAG, NCI1 and NCI109 benchmarks, as well as the OGBGMOLHIV one. Interestingly, the DSS-GNN variant appears more robust in this regard (see paragraph below).
(5) Are there any empirical advantages to DSS-GNN versus DS-GNN? Overall, we observe a tendency for DSS-GNN to perform better than DS-GNN. This observation is more pronounced in certain conditions and datasets, and on ZINC12K in particular (see Table 8). Another interesting finding is that DSS-GNN appears significantly more robust across different scenarios. As already noted above, this variant does not exhibit the same performance drop showed by DS-GNN with EGO(+) policies, and is, in particular, less sensitive to subgraph sampling (see Table 6). In certain cases, we observe DSS-GNN to be (more) robust to the choice of the base graph encoder, as it can be noted by comparing the performance of the two variants on the OGB datasets with GCN encoders (see Table 2 and Table 4). These advantages come at the cost of a slightly larger computational complexity, as observed in Table 11.
When is the ESAN framework advantageous, in general? Given the above, we can conclude that applying our approach to real world datasets is generally beneficial whenever some additional computational resources are available. The DSS-GNN variant, when equipped with EGO(+) policies, is a competitive and versatile architecture, showing strong performance across various benchmarks and conditions. DS-GNN may offer slightly more favourable computational complexity, and it generally works well in conjunction with ND and ED policies.
More specifically, our results indicate that the application of ESAN is recommended in those cases where the task at hand may require expressive power beyond 1-WL. There is some empirical evidence that certain molecular benchmarks fall in this category; our results on the ZINC12K dataset validate this hypothesis by showing that our approach strongly outperforms GIN, while performing best amongst all provably expressive, domain agnostic GNNs (see Table 8). Finally, ESAN is especially suitable in those cases where no domain knowledge is available about graph substructures relevant to the task being solved. As it requires little pre-engineering, our method represents a valid, flexible and provably expressive approach in these conditions.
We are not aware of any particular scenario where the application of ESAN has proved to be consistently unsuccessful. We have observed it to not work well in conjunction with GCN encoders over the OGB datasets, but this would require further future investigation before drawing definite conclusions.

heading: E WL VARIANTS AND PROOFS FOR SECTION 3.2
text: This appendix includes additional details for Section 3.1 and proofs for the theoretical results in Section 3.2 of the main paper, along with additional context and results.
E.1 PRELIMINARIES
Algorithm 1 WL Test
Require: G1, G2, ι : v 7→ lv (opt.) 1: t← 0, converged← false 2: for v ∈ G1 ∪G2 do 3: c0v ← c̄ or ι(v) if provided 4: c0G1 ← { c0v | v ∈ G1}} 5: c0G2 ← { c0v | v ∈ G2}} 6: while ctG1 = c t G2 and not converged do
7: for i ∈ {1, 2} do 8: for v ∈ Gi do 9: N tv ← { ctw | w ∈ N i(v)}}
10: ct+1v ← HASH(ctv, N tv) 11: ct+1Gi ← { c t+1 v | v ∈ Gi}} 12: if ctG1 v c t+1 G1 and c t G2 v c t+1 G2 then 13: converged← true 14: t← t+ 1 15: if ctG1 6= ctG2 then 16: return non-isomorphic 17: else 18: return possibly isomorphic
Let us first introduce some notation and required definitions. We begin with the definition of vertex coloring (Rattan & Seppelt, 2021).
Definition 1 (Vertex coloring). A vertex coloring is a function mapping a graph and one of its nodes to a “color” from a fixed color palette.
Generally, we can define a vertex coloring as a function c : V → C, (G, v) 7→ cGv , where V is the set of all possible tuples of the form (G, v) with G = (V,E) ∈ U (the set of all finite graphs) and v ∈ V . Concretely we write c : (G, v) 7→ cGv and we sometimes drop the superscript G whenever clear from the context. In order to design and compare vertex colorings, it is important to introduce the notion of refinement.
Definition 2 (Vertex color refinement). Let c, d be two vertex colorings. We say that d refines c (or d is a refinement of c) when for all graphs G = (V G, EG), H = (V H , EH) and all vertices v ∈ V G, u ∈ V H we have that dGv = d H u =⇒ cGv = cHu . We write d v c.
When working with a specific graph pair G1, G2, we write d vG1,G2 c when, in particular, it holds that ∀v ∈ V G1 , u ∈ V G2 , dG1v = dG 2 u =⇒ cG 1 v = c G2 u .
The 1-WL test, sometimes known as “naı̈ve vertex refinement” (and sometimes simply as “WL” in this manuscript) is an efficient heuristic to test (non-)isomorphism between graphs. We report the related pseudocode in Algorithm 1.
The algorithm represents a graph with the multiset (or histogram) of colors associated with its nodes. colors naturally induce a partitioning of the nodes into color classes, in the sense that two nodes belong to the same partition if and only if they are equally colored. We denote with c−1(v) the partition to which node v belongs to, according to coloring c. Starting from an initial vertex coloring, the algorithm iterates rounds whereby the node partitioning gets finer and finer. These rounds are referred to as “refinement steps” since, if c indicates the colorings computed by the WL algorithm, ct+1 vG,G ct: Proposition 4. Let G be a graph and ctS be the vertex coloring computed by WL. Then, ∀t > 0, ct+1 vG,G ct.
Proof. For those nodes v, u in the vertex set of G such that ct+1v = c t+1 u we have HASH(c t v, N t v) = HASH(ctu, N t u) and, necessarily, c t v = c t u due to the injectivity of the HASH function.
The refinement is at convergence when the node partitioning is stable, that is, when it does not vary across steps. This means that, both ct+1 vG,G ct and ct vG,G ct+1 hold. At convergence on
both the two input graphs, the test deems them non-isomorphic if assigned distinct multisets of node colors, it is inconclusive otherwise.
Algorithm 2 DSS-WL Test
Require: G1, G2, π, ι : v 7→ lv (opt.) 1: t← 0, converged← false 2: G1 ← π(G1), G2 ← π(G2) 3: for S ∈ G1 ∪ G2 do 4: for v ∈ S do 5: c0v,S ← c̄ or ι(v) if provided 6: c0S ← HASH({{c0v,S | v ∈ S}}) 7: cG1 ← { c0S | S ∈ G1}}, cG2 ← { c0S | S ∈ G2}} 8: while cG1 = cG2 and not converged do 9: for i ∈ {1, 2} do 10: for S ∈ Gi do 11: for v ∈ S do 12: N tv,S ← { ctw,S | w ∈ NS(v)}} 13: Ctv ← { ctv,R | R ∈ Gi}} 14: M tv ← {Ctw | w ∈ N (v)}} 15: ct+1v,S ← HASH(ctv,S , N tv,S , Ctv,M tv) 16: ct+1S ← HASH({{c t+1 v,S | v ∈ S}}) 17: cGi ← { ct+1S | S ∈ Gi}} 18: if ∀S ∈ G1 ∪ G2, ctS v c t+1 S then 19: converged← true 20: t← t+ 1 21: if cG1 6= cG2 then 22: return non-isomorphic 23: else 24: return possibly isomorphic
We report the full DSS-WL test in Algorithm 2. Let us first note that both DSS-WL and DS-WL produce color refinements at the level of each subgraph:
Proposition 5. Let G be a graph, π be a subgraph selection policy and G be the bag induced by π onG. Let ctS be the vertex coloring computed by DSS-WL (DSWL) over subgraph S ∈ G at round t. Then, ∀S ∈ G,∀t > 0, ct+1S vS,S ctS .
Proof. In the case of DS-WL, the assertion is immediately proved by observing that the algorithm performs independent WL refinements on each subgraph, and we know the standard WL procedure is indeed a vertex refinement one.
The assertion trivially holds also in the case of DSS-WL. Suppose there exist nodes v, u in the vertex set of S such that ct+1v,S = c t+1 u,S . This implies HASH(ctv,S , N t v,S , C t v,M t v) = HASH(ctu,S , N t u,S , C t u,M t u) and, necessarily, ctv,S = c t u,S due to the injectivity of the HASH function.
An immediate consequence of the above considerations is that, for vertex refinement algorithms, if two vertices belong to distinct partitions at time step t, they will for any other t̄ > t. This allows us to conclude that both DSS-WL and DS-WL tests eventually terminate on any pair of (finite) input graphs.
Proposition 6. Let G1, G2 be any pair of finite graphs. There exists t̄ < ∞ such that the DSS-WL (DS-WL) test converges when run on G1, G2 with any subgraph selection policy π.
Proof. Let G1,G2 be the bags induced by π on G1, G2. The two tests converge when, on all subgraph, the node partitioning induced by the coloring does not vary across two consecutive steps. Due to Proposition 5, we know that their colorings are vertex refinements on each of the subgraphs. This implies that, at iteration t + 1, the partitioning on a subgraph is either as fine as, or finer than the one at iteration t. In other words, if Nt,S is the number of color classes at round t on subgraph S, we have that Nt+1,S ≥ Nt,S . At the same time, the value Nt,S ,∀t ≥ 0 is upper bounded by NS < ∞, i.e. the cardinality of the vertex set of S. This implies that the number of possible iterations before convergence must be upper-bounded by the value ν = maxi (∑ S∈Gi NS ) , which is, itself, finite.
The concept of vertex color refinement is linked to the ability to distinguish between non-isomorphic graphs. This is a consequence of the following Lemma, whose proof is adapted from Bodnar et al. (2021b).
Lemma 2. Let c, d : V → N be coloring functions implementing maps in the form (A, a) 7→ ca, (A, a) 7→ da, with (A, a) ∈ V such that A is a set and a ∈ A. Let A,B be two sets such that
(A, ·), (B, ·) ∈ V and Aφ,Bφ be multisets of colors defined as: Aφ = {{φa|a ∈ A}},Bφ = {{φb|b ∈ B}}, φ ∈ {c, d} Suppose that ∀a, b ∈ A ∪ B, da = db =⇒ ca = cb (we write d vA,B c). Then Ac 6= Bc =⇒ Ad 6= Bd.
Proof. If Ac 6= Bc, we assume, w.l.o.g., that there is a color c̄ which is represented more in Ac than in Bc. In other words, if we define the two sets:
Ac̄ = {a ∈ A|ca = c̄}, Bc̄ = {b ∈ B|cb = c̄}
then |Ac̄| > |Bc̄|. These sets naturally define the partitioning:
A = Ac̄ ∪ Ãc̄, B = Bc̄ ∪ B̃c̄
where Ãc̄ = {a ∈ A|ca 6= c̄}, B̃c̄ = {b ∈ B|cb 6= c̄}. Let us now consider the multisets:
A∗d = {{da|a ∈ Ac̄}},B∗d = {{db|b ∈ Bc̄}}
First, each of these multisets have the same cardinality of the generating sets, that is |A∗d| = |Ac̄|, |B∗d| = |Bc̄| so, we necessarily have A∗d 6= B∗d. Second, in view of the fact that d vA,B c, although the two multisets may generally contain more than one color, these colors cannot appear outside of these last ones. More formally, by construction we have that
∀x ∈ Ac̄ ∪Bc̄, y ∈ Ãc̄ ∪ B̃c̄ cx 6= cy
and, due to d vA,B c it must also hold that:
∀x ∈ Ac̄ ∪Bc̄, y ∈ Ãc̄ ∪ B̃c̄ dx 6= dy
This implies that, if we define multisets
Ã∗d = {{da|a ∈ Ã c̄}}, B̃∗d = {{db|b ∈ B̃ c̄}}
then (A∗d ∪ B∗d) ∩ (Ã∗d ∪ B̃∗d) = ∅.
Now, we have thatAd = A∗d∪Ã∗d,Bd = B∗d ∪B̃∗d,A∗d 6= B∗d. Say that, w.l.o.g., this last holds due to a color d̄ appearing nA times inA∗d and nB times in B∗d with nA > nB . Then, a necessary condition forAd = Bd is that d̄ appears nA−nB times more in B̃∗d than in Ã∗d. However, this condition cannot be met due to the disjointness of the multisets as shown above.
Definition 3. Let c be a vertex coloring. A readout mapAc : (V,E) 7→ φ({{cGv |v ∈ V }}) is function representing a graph G = (V,E) with the multiset of node colors generated by c on V , or an injection thereof (φ).
Readout maps allow us to leverage on colorings to test (non-)isomorphism between graphs: we can define algorithmic tests whereby two graphs are distinguished when their readout representations are distinct. This is the case of the WL test, where φ is the identity function and c is the coloring induced by a certain number of rounds of the refinement procedure.
The following is an immediate consequence of Lemma 2.
Corollary 2. Let c, d be two vertex coloring functions such that d v c. LetAc,Ad be readout maps associated with, respectively, vertex colorings c, d. Then, any two graphs distinguished by Ac are also distinguished by Ad. We say Ad refines Ac and write Ad v Ac.
When Ad v Ac then Ad is said to be at least as powerful as Ac. When the opposite holds, that is Ac v Ad, then the two have the same discriminative power and we writeAc ≡ Ad. On the contrary, if there exist a pair of graphs distinguished by Ad which are indistinguishable by Ac, then we say Ad is strictly more powerful than Ac, and write Ad @ Ac. Let us lastly introduce some general, auxiliary lemmas that will be required for the proofs in the following subsection.
Lemma 3. Let A, B be two multisets with elements in D such that A = {{ai}}mi=1 = {{bi}}mi=1 = B. For any injection ϕ : D → C it holds ϕ(A) = {{ϕ(ai)}}mi=1 = {{ϕ(bi)}}mi=1 = ϕ(B).
Proof. Let us suppose, for the sake of contradiction, that ϕ(A) 6= ϕ(B). Thus, we can assume, w.l.o.g., that there exists an image c̄ such that c̄ appears more times in ϕ(A) than in ϕ(B), that is
|{cA|cA = c̄, cA ∈ ϕ(A)}| > |{cB |cB = c̄, cB ∈ ϕ(B)}|
If ϕ is an injection, then ∀c ∈ Im(ϕ) ⊆ C there exists unique d ∈ D such that c = ϕ(d). This implies that there exist dA, dB , d̄ such that we can rewrite the inequality above as:
|{ϕ(dA)|ϕ(dA) = ϕ(d̄), dA ∈ A}| > |{ϕ(dB)|ϕ(dA) = ϕ(d̄), dB ∈ B}|
and then |{dA|dA = d̄, dA ∈ A}| > |{dB |dB = d̄, dB ∈ B}|
which would immediate entail A 6= B, against our hypothesis.
Lemma 4. Let A, B be two multisets with elements in D1 × . . . × Dk such that A = {{(a1i , . . . , aki )}}mi=1, B = {{(b1i , . . . , bki )}}mi=1 and ∀i,Di is countable. Let Aj = {{a j i}}mi=1, Bj = {{bji}}mi=1,∀j = 1, . . . , k. Then A = B implies Aj = Bj .
Proof. Suppose A = B. Since elements in A,B are from a countable universe, there exists (coloring) bijection ϕ : D1 × . . . × Dk → N uniquely mapping elements in A,B to naturals: ∀i = 1, . . . ,m ai 7→ cai , bi 7→ cbi . Let us define ψj : Dj → Im(ϕ) as ψj : a j i 7→ ϕ(ai) = cai , ai ∈ A and equivalently for elements in B. Map ψj is itself a bijection. Now, maps ϕ,ψj clearly induce colorings such that ϕ vA,B ψj . From Lemma 3 we have that A = B =⇒ ϕ(A) = ϕ(B) and, in light of Lemma 2 we have that ϕ(A) = ϕ(B) =⇒ ψj(A) = ψj(B). Finally, by applying Lemma 3 again we have ψj(A) = ψj(B) =⇒ ψj−1 ◦ ψj(A) = ψj−1 ◦ ψj(B), which concludes the proof.

heading: E.2 PROOFS FOR RESULTS IN SECTION 3.2

heading: E.2.1 DSS-WL VS. DS-WL
text: We start by formally proving that DSS-WL is at least as expressive as DS-WL. We will require the following Lemma, which describes a refinement relation between DSS-WL node coloring on each subgraph and WL ones.
Lemma 5. Let π be any subgraph selection policy, G1, G2 be any two graphs and D1,D2 the π-bags thereof. Let a(t), b(t) generally refer to the coloring generated by t steps of, respectively, the WL and DSS-WL algorithms. Then, for any t ≥ 0, ∀G = (VG, EG), H = (VH , EH) ∈ D1 ∪ D2, b(t) vG,H a(t).
Proof. We seek to show that ∀v ∈ VG, u ∈ VH , bG,(t)v = bH,(t)u =⇒ aG,(t)v = aH,(t)u . As usual, let us prove the lemma by induction on t.
(Base case) The thesis trivially holds for t = 0 given that all nodes in all subgraphs are assigned the same color. Let us assume the thesis holds true for t > 0, we seek to show it also holds for t+ 1.
(Step) Suppose that, for nodes v, u we have bG,(t+1)v = b H,(t+1) u . The equality can be rewritten as HASH(b G,(t) v , N G,(t) v , C (t) v ,M (t) v ) = HASH(b H,(t) u , N H,(t) u , C (t) u ,M (t) u ), which implies the equality between each of the inputs to the HASH function. Importantly, this means that bG,(t)v = b H,(t) u and NG,(t)v = N H,(t) u . The induction hypothesis immediately gives us a G,(t) v = a F,(t) w and {{aG,(t)i |i ∈ NG(v)}} = {{a F,(t) j |j ∈ NF (w)}}, by the definition of N G,(t) v and N F,(t) w and in view of Lemma 2. These are equalities between the (only) inputs in the WL color refinement step, which applies an injective HASH to obtain aG,(t+1)v and a H,(t+1) u . It then immediately follows that a G,(t+1) v = a H,(t+1) u .
As a consequence, we have the following corollary:
Corollary 3. Let π be any subgraph selection policy, G1, G2 be any two graphs and D1,D2 the π-bags thereof. Let a(t)G and b (t) G refer to the subgraph colors assigned to subgraphs G at step t by, respectively, DS-WL and DSS-WL. For any pair of subgraphs G,H ∈ D1 ∪ D2, and time step t ≥ 0, if DS-WL assigns a distinct color to G and H then DSS-WL does so as well: a(t)G 6= a (t) F =⇒ b (t) G 6= b (t) F .
Proof. In both algorithms, subgraph colors are obtained by injectively hashing the multisets of node colors therein. Furthermore, in DS-WL, the node colors at time step t on generic subgraph G are obtained by independently running t rounds of the WL procedure on G. The thesis therefore holds in view of Lemma 5, Lemma 2 and Lemma 3.
Equipped with the above, we can now prove the following: Proposition 7. Let π be any subgraph selection policy. When both are run on the same π-induced bags, DSS-WL is at least as powerful as DS-WL in distinguishing non-isomorphic graphs, i.e., any two non-isomorphic graphs G1, G2 distinguished by DS-WL via policy π are also distinguished by DSS-WL via the same policy.
Proof. Let D1 = {{G1k}}mk=1,D2 = {{G2h}}mh=1 be the bags induced by π on G1, G2. Let a(t) and b(t) refer to the subgraph coloring computed at step t by, respectively, DS-WL and DSS-WL (these assign each subgraph a color by hasing the multiset of node colors at time t). Also, suppose DSWL distinguishes between G1, G2 at time step T . The theorem immediately follows in light of Corollary 3 and Lemma 2. Let D1,D2 correspond to, respectively sets A,B from Lemma 2, and let a(T ), b(T ) correspond to, respectively, colorings c, d from the same proposition. If G1, G2 are distinguished by DS-WL at step T , then we have Ac 6= Bc. Also, in view of Corollary 3, it holds that b(T ) vD1,D2 a(T ), that is d vA,B c. All hypotheses in Lemma 2 hold and we can then conclude that Ad 6= Bd that is Ab(T ) 6= Bb(T ) . This shows DSS-WL assigns the two bags distinct multisets of colors, and thus, as DS-WL, it distinguishes between the two graphs G1, G2.

heading: E.2.2 EXPRESSIVENESS OF WL VARIANTS
text: In this Subsection we will characterize the expressive power of our variants in relation to the standard WL test. We will first show that DSS-WL and DS-WL are indeed at least as powerful as the standard WL test when equipped with non-trivial subgraph selection policies. These will form the necessary premise to prove Theorem 1.
We start by characterizing DSS-WL and, in particular, with some required Definitions and Lemmas. Definition 4. Let G = (V,E) be any graph. Let π be any subgraph selection policy generating an m-subgraph bag SπG = {Gi = (Vi, Ei)}mi=1 over G. Policy π is said to be vertex set preserving if ∀i = 1, . . . ,m, Vi = V .
Intuitively, a vertex set preserving policy is a policy which does not perturb the original vertex set; subgraphs are obtained by taking subsets of edges. Note that the ND policy is vertex set preserving if, instead of removing one node and all the related connectivity, it removes its incident edges only.
An important component of the DSS-WL algorithm is the HASH input C(t)v , which represents the multiset of colors for node v across the subgraphs in the bag. Definition 5. Let G = (V,E) be any graph. Let π be a vertex set preserving policy generating an m-subgraph bag SπG. The needle node color for node v ∈ V at time step t ≥ 0, denoted C (t) v , is defined as {{c(t)v,S}}S∈SπG , where c (t) v,k is the node color of node v on subgraph k at time step t. We remark that the needle node color C(t)v is employed by the DSS-WL algorithm to obtain a refinement at time step (t+ 1).
We now introduce a first result allowing us to compare DSS-WL and WL. Lemma 6. Let π be any vertex set preserving policy. Let bπ denote the (needle) node coloring from DSS-WL running on bags induced by π, and a be the node coloring from the standard WL algorithm. Then bπ v a, that is, for all graphs G1 = (V 1, E1) and G2 = (V 2, E2) and all nodes v ∈ V 1, w ∈ V 2 we have that bπv = bπw =⇒ av = aw.
Proof. Let G1, G2 be any two graphs, a(t) refer to the WL coloring at iteration t, and b(t) refer to the needle coloring induced by DSS-WL at the same iteration (we drop the superscript π to ease the notation). We seek to prove that b(t) v a(t)∀t ≥ 0. We prove the lemma by induction on time step t.
In particular, let us refer with a(t)v to the WL-color assigned to node v at time step t, and with b (t) v to the needle node color DSS-WL assigns to the same node at the same iteration. We remark that this last is defined as b(t)v = C
(t) v = {{c(t)v,S}}S∈SπG , with c (t) v,k the DSS-WL color assigned to node v
at time step t on subgraph S.
(Base case) At t = 0, it clearly holds that b(0) v a(0) given that all nodes are initialised with the same constant color c̄.
(Step) Let us assume the thesis holds true at time step t: b(t)v = b (t) w =⇒ a(t)v = a(t)w . We seek to prove that if that is the case, it also holds true at time step t+ 1.
Suppose b(t+1)v = b (t+1) w . Unrolling one step backwards in time we get:
{{g(b(t)v,S , N (t) v,S , C (t) v ,M (t) v )}}S∈Sπ G1 = {{g(b(t)w,R, N (t) w,R, C (t) w ,M (t) w )}}R∈Sπ G2
where g ≡ HASH. In view of Lemma 3, the following equality also holds:
{{g−1 ◦ g(b(t)v,S , N (t) v,S , C (t) v ,M (t) v )}}S∈Sπ G1 = {{g−1 ◦ g(b(t)w,R, N (t) w,R, C (t) w ,M (t) w )}}R∈Sπ G2
since, due to the injectivity of g, the left inverse g−1 : Im(g) → D(g) exists and is injective. Thus we have:
{{(b(t)v,S , N (t) v,S , C (t) v ,M (t) v )}}S∈Sπ G1 = {{(b(t)w,R, N (t) w,R, C (t) w ,M (t) w )}}R∈Sπ G2
where, in view of Lemma 4, we also have:
{{C(t)v }}S∈Sπ G1 = {{C(t)w }}R∈Sπ G2 , {{M (t)v }}S∈Sπ G1 = {{M (t)w }}R∈Sπ G2
The elements of these multisets do not depend on index k, therefore we can rewrite the equalities as the set equalities:
{(C(t)v , |SπG1 |)} = {(C(t)w , |SπG2 |)}, {(M (t)v , |SπG1 |)} = {(M (t)w , |SπG2 |)}
which obviously imply C(t)v = C (t) w , M (t) v = M (t) w
First, we note that b(t)v = C (t) v = C (t) w = b (t) w , which by the induction hypothesis gives us a (t) v = a (t) w .
Second, we note that M (t)v = {{b(t)i |i ∈ N (v)}} and M (t) w = {{b(t)j |j ∈ N (w)}}. By the induction hypothesis, Lemma 2 gives us that M (t)v = M (t) w =⇒ {{a(t)i |i ∈ N (v)}} = {{a (t) j |j ∈ N (w)}}. This, along with the result above, implies a(t+1)v = a (t+1) w , since both the two inputs to hash g at time step t coincide. The proof terminates.
Finally, by leveraging on the above Lemma, we show that DSS-WL is at least as powerful as the WL test in distinguishing between non-isomorphic graphs, when equipped with vertex set preserving policies. Lemma 7. Let π be any vertex set preserving policy. DSS-WL on π-induced bags is at least as powerful as WL in distinguishing non-isomorphic graphs, i.e., any two non-isomorphic graphs G1, G2 distinguished by WL are also distinguished by DSS-WL when run on the respective π-induced bags.
Proof. Throughout the proof, we will denote with a colorings generated by the WL algorithm, while b will denote needle colorings generated by DSS-WL and c its node colorings on subgraphs. Additionally, we denote as D1,D2 the π-bags of, respectively, G1, G2. We suppose the two bags have both cardinality m, and are defined as D1 = {{G1k = (V 1, E1k)}}mk=1,D2 = {{G2h = (V 2, E2h)}}mh=1. We do not explicitly focus on the case |D1| 6= |D2| as the two graphs would then be (trivially) distinguished by DSS-WL.
Let us start by recalling that at time step t, two graphs are deemed non-isomorphic by the WL algorithm when the two are assigned two distinct multisets of node colors:
{{a(t)v |v ∈ V 1}} 6= {{a(t)w |w ∈ V 2}} while the DSS-WL algorithm deems them non-isomorphic when the two are assigned two distinct multisets of subgraph colors, that is:
{{b(t) G1k }}mk=1 6= {{b (t) G2h }}mh=1
where b(t) Gij generally indicates the color computed for subgraph j of graph Gi: {{c(t)v,j |v ∈ V i}}.
Suppose WL distinguishes between the two graphs at iteration T . In view of Lemma 6, we know that b(T ) v a(T ), where b(T ) is the needle node coloring generated by DSS-WL at time step T . At the same time, it can be shown that the needle coloring at T is refined by the coloring generated by DSS-WL at T + 1 on any pair of subgraphs: ∀G,H ∈ D1 ∪ D2 c(T+1) vG,H b(T ). Let us shortly prove it. We seek to show that for all nodes v in G, u in H:
c (T+1) v,G = c (T+1) u,H =⇒ b (T ) v = b (T ) u
The antecedent implies the equality of all inputs to the HASH function at time step T , that is: c (T ) v,G = c (T ) u,H , N (T ) v,G = N (T ) u,H ,M (T ) v = M (T ) u and, importantly, C (T ) v = C (T ) u . By the definition of needle node colors, this last equality is rewritten as b(T )v = b (T ) u , which proves the refinement.
This tells us that, by transitivity, that ∀G,H ∈ D1∪D2 c(T+1) vG,H a(T ). Therefore, by Lemma 2, if two graphs are deemed non-isomorphic by the WL algorithm at step T , then at step T + 1, DSSWL assigns a distinct color to any pair of subgraphs from the respective bags, that is:
b (T+1) G1k = {{c(T+1)v,k |v ∈ V 1}} 6= {{c(T+1)w,h |w ∈ V 2}} = b(T+1) G2h ∀h, k ∈ {1, . . . ,m}
This immediately leads DSS-WL to distinguish between graphs G1, G2 as their corresponding multisets of subgraph colors are disjoint.
Let us now characterize the expressive power of DS-WL. We start by proving that, under certain subgraph selection policies, it can be made at least as expressive as the WL test. Lemma 8. Let π̂ be any augmented subgraph selection policy. DS-WL on π̂-induced bags is at least as powerful as WL in distinguishing non-isomorphic graphs, i.e., any two non-isomorphic graphs G1, G2 distinguished by WL are also distinguished by DS-WL when run on the respective π̂-induced bags.
Proof. We focus on the non-trivial case in which the two graphs have the same number of edges (and nodes) and policy π̂, on the two graphs, generates bags of same cardinality. Let us remark that subgraph colors are obtained by DS-WL by running an independent WL procedure on each of them.
Let G1, G2 be two graphs distinguished by WL at round T ≥ 1. Let a1, a2, a1 6= a2 be the representations WL assigns to the two input graphs at time step T . Also, let us denote by C1 = {{c1k}}mk=0, C2 = {{c2k}}mk=0 the multisets of subgraph colors computed by DS-WL on the two input π̂bags at round T . In particular, if c10, c 2 0 are the subgraph colors associated with G 1 0 = G 1, G20 = G 2, clearly, c10 = a 1, c20 = a
2, c10 6= c20. Now, any other subgraph from any bag has a number of edges smaller than the one in the original graphs. This implies that, if S is a proper subgraph of G, then WL assigns it a color distinct from the one assigned to G already at the first round. Then, ∀k = 1, . . . ,m, i = 1, 2, cik /∈ {c10, c20}. This entails the presence of a color in C1 which is not in C2 (and vice-versa), thus C1 6= C2 which implies DS-WL distinguishes between the two graphs.
As for DS-WL, the inclusion of the original graphs in the generated bags guarantees a lower bound on the expressive power of the test, which corresponds to that of the standard WL algorithm. Nonetheless, there exist families of graphs undistinguishable by WL, which can be are separated by DS-WL when equipped with policies which do not include the original graph in the induced bags. Lemma 1 provides examples of them: CSL(n, 2) graphs can be distinguished from any CSL(n, k) with k ∈ [3, n/2− 1] with either ND, ED, EGO and EGO+ policy. We prove it below.
Proof of Lemma 1. We start with a lemma that reduces the problem to considering a single subgraph of each CSL graph.
Lemma 9. All node-deleted subgraphs of G = CSL(n, k) are isomorphic. All depth-1 ego-nets of G = CSL(n, k) are isomorphic.
Proof. For i ∈ {0, . . . , n − 1}, there is an isomorphism from node-deleted subgraphs G − v0 to G− vi given by mapping node j in G− v0 to node j+ i mod n in G− vi. This same isomorphism works for mapping the ego-net rooted at v0 to the ego-net rooted at vi.
Let the nodes of CSL(n, 2) be denoted v(1)0 , . . . , v (1) n−1 and similarly denote the nodes of CSL(n, k) as v(2)0 , . . . , v (2) n−1. First, we start with the node-deleted case.
Node-deleted policy. Denote the subgraph G1 = CSL(n, 2) − v(1)0 and G2 = CSL(n, k) − v (2) 0 . Due to Lemma 9, it suffices to show that G1 6=1−WL G2.
After deleting the nodes, in G1 we note that v (1) 1 , v (1) n−1, v (1) 2 , and v (1) n−2 have degree 3 while all other nodes have degree 4. Also, these degree 3 nodes each have at least one neighbor of degree 3.
In G2, the nodes of degree 3 are v (2) 1 , v (2) n−1, v (2) k , and v (2) n−k. However, it can be seen that none of these nodes have a neighbor of degree 3.
In fact, it suffices to prove that just v(2)1 has no neighbors of degree 3. To see this, note that v (2) 1 has neighbors v(2)2 , v (2) 1+k, and v (2) n−k+1. The constraints n ≥ 7 and k ∈ [3, n/2 − 1] show that these neighbors are disjoint from the degree 3 nodes S = {v(2)n−1, v (2) k , v (2) n−k}. This is because these constraints imply that the indices of the degree 3 nodes in S satisfy
3 < n/2 < n− 1 < n 3 ≤ k ≤ n/2− 1
4 < n/2 + 1 ≤ n− k ≤ n− 3.
On the other hand, the indices of the neighbors of v(2)1 satisfy:
0 < 2 < 3
k < k + 1 ≤ n/2 n/2 + 2 ≤ n− k + 1 < n− 2.
Which together suffice to show that the indices do not overlap. Indeed, 2 is less than all of the indices of degree 3 nodes. k + 1 is less than n− k, greater than k , and less than n− 1. Finally, n− k + 1 is less than n− 1, greater than k, and greater than n− k.
Thus, v(2)1 has no degree 3 neighbors, so that 1-WL distinguishes G1 and G2 after two iterations.
EGO policies. Let G1 be the depth-1 ego-net of CSL(n, 2) rooted at v (1) 0 , and let G2 be the depth-1 ego-net of CSL(n, k) rooted at v(2)0 . This proof works for both the EGO and EGO+ cases, as we will simply show the degree distribution of G1 and G2 differ. This is because G1 has 6 edges total
— 4 edges from v(1)0 to v (1) n−1, v (1) n−2, v (1) 1 , and v (1) 2 , as well as edges (v (1) n−2, v (1) n−1) and (v (1) 1 , v (1) 2 ). However, G2 only has 4 edges — those incident to the root v (2) 0 . The proof that no other edges exist is the same as the above proof that the nodes of degree 3 in the node-deleted subgraphs of G2 have no other neighbors of degree 3. As the degree distributions differ, 1-WL can distinguish G1 and G2.
The derivations above are enough to prove the thesis hold for DS-WL under policies ND, EGO and EGO+. Proposition 7 ensures that these graphs are also distinguished by DSS-WL and allows us to conclude the proof.
We now exhibit an example of a graph pair separated by our variants with ED policy (and undistinguishable by WL). Definition 6 (C6 and 2 × C3). The C6 graph is a 2-regular graph composed by a chordless cycle of 6 nodes. The 2 × C3 graph is 2-regular and is a graph formed by two disconnected cycles of 3 nodes each (triangles). These graphs are illustrated in Figure 5a.
It is easy to verify that, when run on this pair, the WL test converges at the first iteration: each node is assigned a color representing degree 2. This is a consequence of being 2-regular. We now show that they are indeed distinguished by our variants with ED policy. Lemma 10. The C6 and 2× C3 are disambiguated by DS-WL and DSS-WL under ED policy.
Proof. We discuss the DS-WL variant; if this is able to distinguish between the two graphs, then DSS-WL is as well, in light of Proposition 7. We first note that, on each of the two graphs, the ED policy induces bags of only one isomorphism class (shown in Figure 5b). This means that it is sufficient to show these two subgraphs are distinguished by WL to prove DS-WL separates them. We simulate two WL rounds on these subgraphs starting from a constant color initialisation.
(Iter. 1) Colors after the first WL refinement uniquely represent node degrees. Each of the two subgraphs will therefore contain two nodes with color 1 and four nodes with color 2. The subgraphs are not yet separated.
(Iter. 2) After the second WL refinement, we note that the number of nodes of color (2, {{1, 2}}) is two in C6, while this color is absent in 2× C3 because there is no node having both a 1-degree and a 2-degree node in its neighborhood. At this step the subgraphs are separated.
The proof terminates.
We are now ready to prove Theorem 1.
Proof of Theorem 1. (DSS-WL) Policies ND, ED, EGO, EGO+ are vertex set preserving, in view of Lemma 7, DSS-WL refines WL under these subgraph selection strategies and we know that there exists exemplary graph pairs distinguished by DSS-WL under these policies and not by WL. In particular, Lemma 1 exhibits exemplary pairs for policies ND, EGO, EGO+: these CSL pairs are indeed indistinguishable by WL (Murphy et al., 2019; Chen et al., 2019). Lemma 10 exhibits another such exemplary pair for policy ED. This is sufficient to prove the thesis for DSS-WL.
(DS-WL) Let us consider augmented policies N̂D, ÊD, ÊGO, ÊGO+. In view of Lemma 8, these policies are such that DS-WL refines WL. Additionally, we note that Lemma 1 and Lemma 10
trivially hold also when considering these policies, thus providing counterexamples of graphs undistinguishable to WL but separated by DS-WL under these policies. This allows us to conclude the proof.

heading: E.2.3 NEURAL COUNTERPARTS
text: We will now focus on characterizing the relation between the proposed WL variants and neural counterparts such as the DSS-GNN architecture introduced in the main text, seeking to prove Theorem 2. In this Subsection we always assume to work with a DSS-GNN architecture with GraphConv encoders (Morris et al., 2019) and entry-wise max adjacency matrix aggregation. Accordingly, the representation for node v in subgraph i is given by:
ht+1v,i = σ ( W 11 h t v,i +W 1 2 ∑ u∼iv htu,i +W 2 1 m∑ j=1 htv,j +W 2 2 ∑ w∼v m∑ j=1 htw,j )
(5)
where σ is the ReLU non-linearity, ∼i indicates the connectivity over subgraph i and ∼ indicates the connectivity induced by the aggregated subgraph adjacency matrices. Let us remark that, for all policies of interest in this work, each edge in the original graph is present in at least one subgraph. In these cases, ∼ corresponds to the connectivity in the original graph. We conveniently formalize this intuition in the following definition:
Definition 7 (Edge-covering policies). A subgraph selection policy π is said to be edge covering if for any graph G = (V,E), ∀ e ∈ E, ∃S = (VS , ES) ∈ π(G) such that e ∈ ES .
Clearly, policies ND, ED, EGO(+) are all edge-covering. Let us now show that in the case of edgecovering policies, there exists a DSS-GNN architecture with layers in the form of Equation (5) that, when working on graphs of bounded size, can “simulate” the color refinement steps of the DSS-WL algorithm.
Lemma 11. Let G = {{Gi = (Vi, Ei)}}mi=1 denote the bag generated by an edge-covering selection policy on any G from a family F of graphs with bounded size, optionally endowed with node labels from a finite support. Let c(T )v,k be the color assigned by DSS-WL to node v in subgraph k, after T < ∞ iterations. There exists a DSS-GNN modelM with D = 10T layers of the form described in Equation (5) such that c(T )v,k is uniquely represented by a one-hot encoding h (D) v,k , the representation for node v in subgraph k computed by such a model.
Proof. We will prove the lemma by describing how to parameterize the DSS-GNN layers in a way to simulate the DSS-WL color refinement step on each subgraph.
(Preliminaries) We assume to work with finite graphs whose size is upper-bounded by positive integer M ∈ N and whose degree is upper-bounded by N ∈ N. From these assumptions it immediately follows that any employed subgraph selection policy generates bags of bounded cardinalities, whose subgraphs are finite graphs with size upper-bounded by M and degree upper-bounded by N . Let us denote with B < ∞ the maximum possible bag cardinality under the considered selection policy on F . Additionally, if initial node labels are present, it is assumed that they are defined over a finite support. For a DSS-GNN to simulate color refinement steps, it is necessary to encode colors in vector/matrix form. Under the aforementioned boundedness assumptions, at any step, each of the four inputs in the DSS-WL color refinement equation belongs to a finite set of bounded size. The domain of the HASH function is therefore represented by the cross-product of such these sets and is therefore finite and of bounded size. Due to the injectiveness of HASH, its image must therefore be finite and bounded as well. The application of this injective function effectively computes a unique representation of the inputs by assigning them a color.
(Encoding) Given these premises, it is clear that, at each time step t, including t = 0, it is possible to represent colors as one-hot vectors of proper dimension without losing any information. This allows the application of our DSS-GNN model. In the following, we indicate with t ∈ N a time step in the DSS-WL procedure, and with dt ∈ N the corresponding layer of the described DSSWL model. Note that, in general, dt ≥ t as more than one layer is required to simulate one color refinement step. Let c(t)v,k be the color assigned to node v on subgraph k at time-step t and h (dt) v,k be its representation computed by our DSS-GNN model, of dimension adt . At time step t = 0, each
node in each subgraph is assigned a constant color c(0)v,k = c̄; if initial colors are available, they are retained. We consider h(d0)v,k = h (0) v,k to be a proper one-hot encoding of these initial colors. For a color refinement from time step t to t+ 1 we consider inputs to layer dt to be one-hot encoded. The refinement is simulated with layers dt to dt+1, where the final output of these is a one-hot encoding uniquely representing the result of the HASH function.
(Computation) Starting from the one-hot color representation in input to layer dt, the refinement step is implemented by: (i) computing unique representations for all the four inputs to the HASH function; (ii) simulating the HASH function by mapping them to an output, unique, one-hot encoding. Let us start by describing step (i). An important observation is that the summation is an injective aggregator over multisets when elements are represented by one-hot encodings. In other words, we can uniquely represent a multiset of one-hot encoded elements by simply summing its members. This implies that there exists one DSS-GNN layer which computes a unique representation for each of the first three inputs to the HASH function: c(t)v,k, N (t) v,k, C (t) v . In this layer, each matrix W has dimension 3 · adt × adt and b has dimension 3 · adt . In particular: W 11 = [I,0,0],W 1 2 = [0, I,0],W 2 1 = [0,0, I],W 2 2 = 0, b = 0, where [·, ·] indicates vertical concatenation.
In output from this layer are vectors in the form h(dt+1)v,k = [h (dt) v,k , h (dt,N) v,k , h (dt,C) v ], with the last two components representing unique encodings of, respectively, inputs N (t)v,k, C (t) v . In order to also compute a unique representation for the fourth input (M (t)v ), we cannot directly apply summation on the just computed h(dt,C)v , because these are not one-hot encoded anymore, and summation is, generally, not injective. To overcome this, we employ additional layers to first uniquely encode each h(dt,C)v,k with a one-hot scheme so that the original neighborhoods N (v) would be uniquely encoded by the summation over them, inherent in the DSS-GNN layer. This one-hot encoding scheme is possible because there is only a finite number of multisets of size m ≤ B that can be constructed from a finite color palette of cardinality adt . Additionally, this encoding can be computed by stacking 4 DSS-GNN layers with ReLU activations as shown by the following:
Lemma 12. Let H be a finite set. Let elements in H be uniquely encoded by h(·). There exists a 4-layer DSS-GNN model which computes the map µ : h(a) 7→ e, a ∈ H with e being a unique one-hot encoding for element a.
Proof. We consider an ordering relation < determining an overall sorting s of the elements in H. This can be obtained, for example, by a lexicographic ordering of the elements in the encodings h(·). This sorting associates any element with an integer index, that is s : H → N, s : a 7→ i. We can therefore denote each (encoded) element with hi, i = 1, . . . , |H|. We seek to implement the mapping µ : hi 7→ ei, such that: ei ∈ {0, 1}|H| and (ei)j = 1 if j = i, (ei)j = 0 otherwise.
We define the dataset D = {(hi, ei)}Hi=1. This dataset satisfies Assumption 3.1 in Yun et al. (2019): all hi’s are distinct and labels ei’s are in [−1,+1]dy , dy = |H|. Moreover we have that ∀i, ei ∈ 0, 1dy . Thus, according to Proposition 3.2 in the same work, there exists a 4-layer ReLU network parameterised by θ and with Ω( √ |H|+|H|) neurons which perfectly fitsD. This network computes
µ and is exactly implemented by a 4-layer DSS-GNN model with matrices W 12 (l) ,W 21 (l) ,W 22 (l) = 0, l = 1, . . . , 4 and θ = (W 11 (l) , b(l)) 4 l=1.
We invoke Lemma 12 with H being the (finite) set of all possible B-size multisets over node colorings h(dt), which are from a finite palette of size adt . Accordingly, there exists a stacking of 4 DSS-GNN layers such that h(dt+5)v,k = [h (dt) v,k , h (dt,N) v,k , h̄ (dt,C) v ], with h̄ (dt,C) v being the one hot
encoding of h(dt,C)v , dimension et,C . If (W̃ 11 (l) , b̃(l))
d+5 l=d+1 are the parameters from Lemma 12 one-
hot encoding h(dt,C)v , then these layers are obtained simply by W 11 (l) = [[I|0], [0|W̃ 11 (l) ]], bl = [0, b̃(l)],W 12 (l) ,W 21 (l) ,W 22 (l) = 0. Here [·|·] indicates horizontal concatenation and I is always of size 2·adt×2·adt . Overall, each h (dt+5) v,k has dimension adt+5 = (2·adt)+et,C . Importantly, we no-
tice that component h̄(dt,C)v is computed for node v but independently of k, and is thus shared across all subgraphs. Layer dt+6 now computes the encoding of M (t) v . Each weight matrix has dimension (adt+5 + et,C)× adt+5 with: W 11 = [I,0] (I size adt+5), W 12 ,W 21 = 0,W 22 = [0, [0⊥| 1mI]] ( 0⊥ size et,C × (2 · adt), I size et,C), b = 0 ∈ Radt+5 .
Now, h(dt+6)v,k = [h (dt) v,k , h (dt,N) v,k , h̄ (dt,C) v , h̄ (dt,M) v ], of dimension adt+6 = adt+5 + et,C , constructed as the concatenation of unique representations of the inputs to the HASH function. It is only left to “simulate” the application of this last. We do this by computing a one-hot encoding of vector h
(dt+6) v,k . As already discussed, this encoding is possible due the fact that HASH is an injection with domain of finite and bounded cardinality. In other words, vectors h(dt+6)v,k can only assume a finite, bounded number of distinct values. Again, this encoding is computable by 4 DSS-GNN layers, as per Lemma 12 invoked considering the (finite) set of all possible colorings attainable by encodings h(dt+6).
Finally, we have that h(dt+1)v,k = h (dt+10) v,k . This construction can be arbitrarily repeated to exactly simulate T iterations of the DSS-WL color refinement step with D = 10T layers, which concludes the proof.
The following Lemma shows that there exists a DS-GNN architecture with layers of the form in Equation (5) that, when working on graphs of bounded size, can “simulate” the color refinement steps of the DS-WL algorithm.
Lemma 13. Let G = {{Gi}}mi=1 denote the bag generated by a subgraph selection policy applied on any G from a family F of graphs with bounded size. Let c(T )v,k be the color assigned by DS-WL to node v in subgraph k, after T iterations. There exists a DS-GNN modelM with D = 5T layers of the form described in Equation (5) such that c(T )v,k is uniquely represented by a one-hot encoding h (D) v,k , the representation for node v in subgraph k computed by such a model.
Proof. The proof closely follows the one for Lemma 11; we work in the same regime (finite graphs of bounded size and degree, initial labels from a finite support) and assume the network encodes node colors with a proper one-hot encoding at each refinement step being simulated. The difference is that, in this case, the described DS-GNN model always has parameters W 21 ,W 2 2 = 0 and does not need to encode the HASH inputs C(t)v ,M (t) v (not present in its update equations).
Let c(t)v,k be the color assigned to node v on subgraph k at time-step t and h (dt) v,k be its representation computed by our DS-GNN model, of dimension adt and properly one-hot encoded. We seek to describe a stacking of DS-GNN layers producing h(dt+1)v,k , a unique, one-hot encoding of color c (t+1) v,k .
Once more, since summation is an injective aggregator over multisets when elements are represented by one-hot encodings, there exists one DS-GNN layer which computes a unique representation for the two inputs to the HASH function: c(t)v,k, N (t) v,k. In this layer, each matrix W has dimension 2 · adt × adt and b has dimension 2 · adt . In particular: W 11 = [I,0],W 12 = [0, I], b = 0 where [·, ·] indicates vertical concatenation.
In output from this layer are vectors in the form h(dt+1)v,k = [h (dt) v,k , h (dt,N) v,k ], with the last component representing a unique encoding of N (t)v,k. In order to obtain h (dt+1) v,k it is only left to one-hot encode h (dt+1) v,k . We perform this operation with a stacking of 4 DS-GNN layers leveraging only on matrix W 11 (in module L1) and bias b. This stacking is described by Lemma 12, invoked considering the (finite) set of all possible colorings attainable by encodings h(dt+1).
Let us now move to prove Theorem 2 from the main text.
Proof of Theorem 2. (DS(S)-GNN v DS(S)-WL) We will directly describe a DSS-GNN architecture satisfying the requirements under edge-covering policies. According to Equation (2), a DSS-GNN architecture computes a representation for a graph in input as: hG = Esets ◦Rsubgraphs ◦Esubgraphs(G).
Let T be the time step at which DSS-WL (resp. DS-WL) distinguishes two input graphs G1, G2. At this round, the overall coloring is such that the multisets of subgraph colors for the two graphs are distinct:
{{c(T ) G1k }}mk=1 6= {{c (T ) G2h }}mh=1
where c(T ) Gij generally indicates the color computed for subgraph j of graph Gi: HASH({{c(T )v,j |v ∈ V i}}). Now, let Esubgraphs be the module obtained by the stacking described in Lemma 11 (resp. Lemma 13). We know that this module uniquely encodes each subgraph node color c(T )v,j with onehot representations h(dT )v,j . Therefore, it is only left to describe modules Rsubgraphs, Esets in a way to injectively aggregate such representations into an overall graph embedding.
Given that subgraph node colors are (uniquely) represented by one-hot encodings, the required Rsubgraphs can be simply obtained by summation over node representations on each subgraph. This is because summation is an injective aggregator when multiset elements are described in a one-hot fashion. Let us generally refer to the computed subgraph representations as hj .
Let us finally describe module Esets. The graphs of interest have a number of nodes upper-bounded by a positive integer and so hj’s uniquely represent bounded-sized multisets of colors from a finite palette. The set of all possible such multisets is finite, so it is possible to compute a one-hot encoding for these subgraph representations with a 4-layer ReLU MLP applied in a siamese fashion. Lemma 12 ensures the existence of such a network as the described stacking of DSS-GNN layers effectively boils down to a Siamese MLP. This would constitute the first 4 layers ofEsets. To conclude, one last layer applying summation to these one-hot encodings would suffice to output an embedding uniquely describing the multiset of subgraph colors.
(DS-WL v DS-GNN) As for DS-GNN and DS-WL, we show in the following that, if a DS-GNN distinguishes two graphs, then DS-WL also distinguishes these two graphs. Suppose DS-GNN distinguishes between G1 and G2. If the bags SG1 and SG2 are of different sizes, then DS-WL separetes the two graphs as well because it hashes multisets of different sizes to different outputs. Assume they have the same size. Letting 1-WL: G → Σ denote the 1-WL graph coloring function and MPNN : G → Σ denote the MPNN base graph encoder employed by DS-GNN, we have:
{{MPNN(G11), . . . ,MPNN(G1m)}} 6= {{MPNN(G21), . . . ,MPNN(G2m)}} (6)
By Morris et al. (2019); Xu et al. (2019), we know that 1-WL v MPNN, i.e. that 1-WL(H1) = 1-WL(H2) implies that MPNN(H1) = MPNN(H2) for any graphs H1 and H2. Thus, Lemma 2 tells us that
{{1-WL(G11), . . . , 1-WL(G1m)}} 6= {{1-WL(G21), . . . , 1-WL(G2m)}}. (7)
Hence, the final readout of DS-WL maps these multisets to different values, so that DS-WL distinguishes G1 and G2.
This is enough to prove the second part of the thesis, terminating the overall proof.

heading: F PROOFS FOR SECTION 3.3: DESIGN CHOICE EXPRESSIVENESS
text: This appendix section contains proofs for Section 3.3. First, we note that we use DS-GNN and DSWL interchangeably in proofs, as they are equivalent in power for distinguishing graphs (as shown in Theorem 2).

heading: F.1 PROOFS OF DSS VERSUS DS
text: Proof of Prop 1. That DSS-GNN is at least as powerful as DS-GNN follows directly from the definition. For any DS-GNN, there is a DSS-GNN with L2 = 0 in each layer that implements the DS-GNN. To show that DSS-GNN is strictly more powerful, we provide two examples.
A trivial example. Consider the subgraph selection policy SE : G = (V,E) 7→ {(V, {e}) | e ∈ E}. Each subgraph is a single edge from the original graph. Now, let G1 be the path on 4 nodes, and let G2 be the 3-star. In other words, G1 has a vertex set of {1, 2, 3, 4} and edges {(1, 2), (2, 3), (3, 4)}, while G2 has a vertex set of {1, 2, 3, 4} and edges {(1, 2), (1, 3), (1, 4)}.
Now, we show that DS-GNN cannot distinguish G1 and G2. Note that the bags are of the same size: |SE(Gi)| = 3. Moreover, any other subgraph is a single edge, and these single edges are isomorphic and hence 1-WL equivalent. Thus, the multisets of subgraph colors are equal
{{1-WL(H) : H ∈ SE(G1)}} = {{1-WL(H) : H ∈ SE(G2)}}, (8)
so that DS-WL cannot distinguish these graphs, and hence DS-GNN cannot distinguish these graphs by Theorem 2.
To see that DSS-GNN can distinguish these graphs, we letL1(A,X) = 0 andL2(A,X) = A ( 1 3X ) . These operations are simple and can be implemented by MPNNs with sum pooling; for instance, GIN (Xu et al., 2019) and GraphConv (Morris et al., 2019) can both implement L1 and L2. Letting the initial node features in each subgraph i be X(0)i = ~1 = [1 . . . 1]
>, we compute the node features after one layer as
X (1) i = L 1(Ai,~1) + L 2 ∑ j Aj , ∑ j ~1  (9) = 0 + L2 ( A, 3~1 ) (10)
= A~1. (11)
Thus, the kth component of X(1)i is the degree of node k. Since G1 has no nodes of degree 3 while G2 has one node of degree 3, these node features differ between G1 and G2. Thus, DSS-GNN distinguishes these two graphs. This is because the multiset of node features in G1 differs from the multiset of node features in G2 after this iteration, so a final set pooling across nodes can map these two graphs to different outputs (for instance, a max pooling outputs 2 for G1 and 3 for G2).
This example is trivial because it is easy to make a change to the policy that would allow DS-GNN to distinguish these two graphs. Since the two original graphs have different degree distributions, they are directly distinguished by 1-WL. Thus, adding the original graph to the bags of subgraphs would allow DS-GNN to distinguish these graphs.
A strengthened result. For an extension of the above example, we consider the policy ŜE that is given by adding the original graph to the SE policy, so ŜE(G) = SE(G) ∪ {G}. For this policy, we can again show that DS-GNN cannot distinguish a pair of graphs that DSS-GNN can, though we need to allow a slightly different type of aggregation for DSS-GNN. In particular, when computing the features for subgraph i, we use an L2 that is mentioned in Section 2.1: L2 (∑ j Aj , ∑ j 6=iXj ) .
Now, consider the pair of non-isomorphic graphs: G1 is two triangles 2× C3 and G2 is the 6-cycle C6 (these graphs are depicted in Figure 5). Denote the subgraph corresponding to the single edge (i, j) as G(i,j), and the corresponding adjacency as A(i,j) ∈ {0, 1}6×6.
We show that DS-GNN cannot distinguishG1 andG2. First, note that the bag is of size |ŜE(Gi)| = 7 for each graph — they each have 6 edges and the original graph adds one more element to the bag. Note that G1 and G2 are regular of the same number of nodes and degree, so they are 1-WL equivalent. As any other subgraph is a single edge, we once again know that these single edges are isomorphic and thus 1-WL equivalent. Hence, the multisets of subgraph colors are equal
{{1-WL(H) : H ∈ ŜE(G1)}} = {{1-WL(H) : H ∈ ŜE(G2)}}, (12)
so that similarly to the previous example, DS-GNN cannot distinguish these graphs.
Now, we show that DSS-GNN can distinguish G1 and G2. We give a choice of parameters for DSS-GNN that distinguishes these graphs. Let the input node features be all one, so X(0) = ~1 = (1, . . . , 1) ∈ Rn×1. Let the first layer graph encoders be given by:
L1(A,X) = AX, L2(A,X) = 0 (13)
Once again, these two graph encoders can be implemented by both GIN and GraphConv. Then the kth element of the representation of the nodes of A(i,j) after one layer is:
X (1) (i,j),k = (L(A,X )) (i,j) k = L 1(A(i,j),~1)k (14)
= (A(i,j)~1)k (15) = 1k∈{i,j}. (16)
In other words, the feature on node k for A(i,j) is one if k is i or j, and zero otherwise. Also, a similar computation shows that subgraph G corresponding to the original graph has node feature 2~1 after this layer.
Now, let the second layer graph encoders be:
L1(2)(A,X) = 0, L 2 (2)(A,X) =
( 1
2 A
)( −X + 4~1 ) , (17)
where L2 takes the standard sum pooled ∑ j Aj as well as the modified pooled ∑ j 6=iXj . These can be implemented by GraphConv with bias terms. Then the kth element of the representation of the nodes of A(i,j) after the second layer is:
X (2) (i,j),k = L 2 (2) A+ ∑ (i,j)∈E A(i,j), X (1) G + ∑ (v,w)∈E\{(i,j)} X (1) (v,w)  k
(18)
= L2(2) 2A, 2~1 + ∑ (v,w)∈E\{(i,j)} X (1) (v,w)  k
(19)
= L2(2) ( 2A, Z(i,j) ) k
(20) = ( A(−Z(i,j) + 4~1) ) k (21)
where Z(i,j),l is 4 if l /∈ {i, j} and is 3 if l ∈ {i, j}. Thus, −Z(i,j),l + 4 is 0 if l /∈ {i, j} and 1 if l ∈ {i, j}. We show that X(2)(i,j) differs between G1 and G2.
For G1, let k be the other node in the triangle that node i and j are in. Then X (2) (i,j),k = 2. On the other hand, for G2, there is no value of k such that X (2) (i,j),k is 2. This is because there is no node k that is adjacent to both i and j (there are no triangles in G2). Thus, we have shown that DSS-GNN distinguishes these two graphs after the second layer, and we are done.

heading: F.2 PROOFS OF INCREASING ENCODER EXPRESSIVENESS
text: First, we introduce certain graphs that provide useful examples for our proofs, and that have been used to study expressiveness of graph algorithms more generally.
Circulant Skip Link Graphs. For parameters n ≥ 7 and k ∈ [2, n − 2], CSL(n, k) is a 4-regular graph with vertex set V = {0, . . . , n − 1} and edges between node i and i ± 1 mod n as well as between i and i± k mod n (Murphy et al., 2019). For an infinite subset of non-isomorphic pairs of these graphs, we prove that DSS-GNN with two different policies can distinguish pairs that 1-WL cannot.
Rook’s graph and Shrikhande graph. We also introduce a particular pair of commonly-used example graphs that will be useful for us. Figure 6 illustrates the 4-by-4 Rook’s graph and the Shrikhande graph. These are non-isomorphic graphs that are strongly regular of the same parameters, so they cannot be distinguished by 3-WL / 2-FWL (Arvind et al., 2020; Balcilar et al., 2021).
We number the nodes for ease of reference in the below proofs. For the either graph, let the vertex set be V = {(x, y) : x ∈ {0, 1, 2, 3}, y ∈ {0, 1, 2, 3}}, so each of the 16 nodes are viewed as a point on a grid in the plane. For each node (x, y) ∈ V , the Rook’s graph has edges ((x, y), (x′, y)) for x′ 6= x and ((x, y), (x, y′)) for y′ 6= y. The Shrikhande graph has edges ((x, y), (x, y ± 1 mod 4)),
((x, y), (x± 1 mod 4, y)), and ((x, y), (x± 1 mod 4, y ± 1 mod 4)). We number the nodes on the grid from left to right then top to bottom, so node 1 is (0,3), node 2 is (1,3), node 5 is (0,2), node 6 is (1,2), and so on.
Proof of Prop 2. Note that the generalization of DS-GNN to 3-WL encoders is straightforward, as we simply use the graph representation vectors from the readout of the 3-WL encoder as the subgraph representations in the DeepSets module. In other words, letting 3-WL-GNN(G) be the final coloring of G that is obtained from a GNN that is equivalent to 3-WL, we apply a DeepSets module to {{3-WL-GNN(Gi) : Gi ∈ SG}} for DS-GNN with a 3-WL encoder. This DS-GNN with 3-WL is at least as strong as DS-GNN with 1-WL since 3-WL is at least as strong as 1-WL. Also, DS-GNN with 3-WL is at least as strong as 3-WL since the original graph is included in S.
To show that DS-GNN with 3-WL is strictly stronger than the other two models, we show that it can distinguish the Rook’s graph and the Shrikhande graph, which the other two models cannot. Recall that 3-WL cannot distinguish the two because they are both strongly regular graphs of the same parameters (Arvind et al., 2020).
Now, note that all depth-1 ego-nets of the Rook’s graph consist of two disjoint triangles with a root node that is connected to all nodes. All depth-1 ego-nets of the Shrikhande graph consist of a 6-cycle with a root node that is connected to all nodes. It is easy to see that 1-WL cannot distinguish these ego-nets, as 1-WL cannot distinguish two disjoint triangles from a 6-cycle. Thus, DS-GNN with the depth-1 ÊGO or ÊGO+ policy cannot distinguish the two graphs.
On the other hand, 3-WL can distinguish these ego-nets as 3-WL can distinguish two disjoint triangles from a 6-cycle; for instance, this can be seen due to 3-WL being able to count triangles at initialization (Chen et al., 2020).

heading: F.3 PROOFS OF POLICY CHOICE AND EXPRESSIVENESS
text: Before restricting to strongly regular graphs, we give an example that shows how the power of the EGO policy can depend in interesting ways with the depth — increasing ego-net depth may either increase or decrease the expressivity of DS-GNN.
Proposition 8. Our DS-GNN model with depth-1 or depth-3 EGO policies do not distinguish CSL(12,3) and CSL(12,5), while the depth-2 EGO policy does distinguish them.
Proof of Prop 8. The depth-1, depth-2, and depth-3 ego-nets of CSL(12, 3) and CSL(12, 5) are all isomorphic, so DS-GNN with a 1-WL encoder can distinguish the two graphs if and only if 1-WL can distinguish the ego-nets. The ego-nets are plotted in Figure 7.
The depth-1 ego-nets of both CSL(12, 3) and CSL(12, 5) are K1,4 — the star with one root node of degree 4 and four nodes of degree 1 connected to the root. As these are isomorphic, 1-WL does not distinguish any subgraphs, so our DS-GNN cannot distinguish CSL(12, 3) and CSL(12, 5) with depth-1 EGO policy.
The depth-2 ego-nets are displayed in Figure 7. It can be seen that the depth-2 ego-nets have different degree distributions: for instance, that of CSL(12, 3) has degree 3 nodes while the ego-nets of
CSL(12, 5) do not have any degree 3 nodes. Thus, 1-WL distinguishes these ego-nets, and hence DS-GNN does as well with the depth-2 EGO policy.
As both CSL(12, 3) and CSL(12, 5) have diameter 3, the depth-3 ego-nets are in both cases just the original graph. As both graphs are regular of the same number of nodes and same degree, 1-WL does not distinguish the subgraphs, so DS-GNN cannot distinguish CSL(12, 3) and CSL(12, 5) with depth-3 EGO policy.

heading: F.4 STRONGLY REGULAR GRAPH PROOFS
text: In this Section, we prove Proposition 3 on the power of different policies for distinguishing strongly regular graphs.

heading: F.4.1 ND AND EGO+ ON STRONGLY REGULAR GRAPHS
text: Lemma 14. DS-GNN with the ND policy can distinguish any strongly regular graphs of different parameters, but cannot distinguish any strongly regular graphs of the same parameters.
Proof. We show that the 1-WL algorithm converges to the same coloring of any node-deleted subgraph of a strongly regular graph in at most 3 iterations, and that the coloring only depends on the strongly regular parameters. Let G be a strongly regular graph of parameters (n, k, λ, µ), meaning that G has n nodes, is regular of degree k, any two adjacent vertices have λ common neighbors, and any two non-adjacent vertices have µ common neighbors. We step through the 1-WL iterations on the node-deleted subgraph G− u:
• Iteration 1: Initialize each node to have color a.
• Iteration 2: Degree k − 1 nodes are colored b and degree k nodes are colored c.
• Iteration 3: All degree k − 1 nodes are colored d, as they each had color b and have λ b neighbors and (k − 1− λ) c neighbors. To see this, note that these nodes were adjacent to the deleted node u in the original graph G, so they had exactly λ common neighbors with u. Since the neighbors of u are now degree k − 1 in G − u, they had color b. Thus, there are exactly λ b neighobrs, and the remaining color is c, so there are also exactly (k−1−λ) c neighbors.
Also, all degree k nodes are colored e, as they had color c and have µ b neighbors and (k− µ) c neighbors. This is because these nodes are not adjacent to u in the original G, so
they have exactly µ common neighbors with u in G. Thus, they have exactly µ b neighbors and (k − µ) c neighbors.
As the colors of iteration 2 and 3 are isomorphic, 1-WL has converged. Since this coloring is the same for any node-deleted subgraphs of any strongly regular graph of the same parameters, DS-WL and hence DS-GNN cannot distinguish any strongly regular graphs of the same parameters.
Likewise, this coloring differs for any strongly regular graphs G1 and G2 of different parameters. The coloring differs at iteration 1 if n differs, at iteration 2 if k differs, and at iteration 3 if λ or µ differ. Thus, DS-WL and hence DS-GNN is able to distinguish any two such graphs.
Lemma 15. DS-GNN with the depth-n ÊGO+ policy can distinguish any strongly regular graphs of different parameters, but cannot distinguish any strongly regular graphs of the same parameters.
Proof. Consider a depth-n ego-net rooted at u. This proof is similar to that of the ND case in Lemma 14. We compute the 1-WL iterations:
• Iteration 1: u has color a1 and all other nodes have color b
• Iteration 2: u has color a2 (as it is the only node with previous color a1).
The k neighbors of u have color c (they each have previous color b, have the one neighbor u of color a1, and have k − 1 neighbors of the remaining color b). The n − k − 1 non-neighbors of u have color d (they each have previous color b, have no neighbors of color a1, and thus have k neighbors of color b).
• Iteration 3: u has color a3 (it is the only node with previous color a2)
The k neighbors of u have color e. They each had previous color c, have one neighbor of color a2, have λ neighbors of color c because they are adjacent to u and all neighbors of u had color c, and have k − λ− 1 neighbors of the remaining color d. The n−k−1 non-neighbors of u have color f (they had previous color d, have no neighbors of color a2, have µ neighbors of color c because they are non-adjacent to u and all neighbors of u had color c, and have k − µ neighbors of the remaining color d).
This coloring is stable, so the algorithm terminates. Note that this coloring only depends on the strongly regular parameters. Once again, it differs for any strongly regular graphs of different parameters, and is the same for any strongly regular graphs of the same parameters. Also, note that besides the unique color of the root node u, this coloring is the same as that of the 1-WL coloring of the node-deleted graph G− u.

heading: F.4.2 ED ON STRONGLY REGULAR GRAPHS
text: Lemma 16. 3 iterations of 1-WL on any edge-deleted subgraph of a strongly regular graph gives a coloring that only depends on the strongly regular parameters. This coloring distinguishes any strongly regular graphs of different parameters.
Proof. Say we have deleted edge (u1, u2). The 1-WL iterations are as follows:
• In iteration 1, each node has initial color a.
• In iteration 2, we have two nodes of degree k − 1 that are colored b, i.e. u1 and u2. There are n− 2 nodes of degree k that are colored c.
• In iteration 3, we have two nodes of degree k − 1 that are colored d (because they are both only adjacent to degree k nodes previously colored c). For the degree k nodes, there are three possible colors, which we call e, f, g: the color e is for nodes adjacent to 2 b nodes and k− 2 c nodes, f is for nodes adjacent to 1 b node and k− 1 c nodes, and g is for nodes adjacent to k c nodes. We show that the number of colors e, f, and g only depend on the strongly regular graph parameters.
First, there are λ nodes of color e, as the nodes adjacent to 2 b nodes are common neighbors of u1 and u2, which are adjacent in the original graphG. By definition there are λ common neighbors of u1 and u2.
Next, there are 2(k − 1− λ) nodes of color f. This is because each node of color f is only adjacent to one of u1 or u2. Each of u1 and u2 has (k − 1 − λ) neighbors that are not in common with the other, so there are in total 2(k − 1− λ) nodes of color f. The only other choice is color g, so we can compute the number by subtracting all the other color counts from the total number of nodes n. There are thus n− 2− λ− 2(k− 1− λ) = n+ λ− 2k nodes of color g.
It is clear that ifG1 andG2 are strongly regular graphs that differ in any of the n, k, or λ parameters, then three iterations of 1-WL distinguishes due to the above coloring differing. Now, if G1 and G2 differ in the µ parameter, the same argument holds, because the µ parameter for a strongly regular graph is related to the other parameters by
(n− k − 1)µ = k(k − λ− 1) (22) (See Theorem 1.1 in Cameron (2004)). Thus, G1 and G2 must differ in at least one of n, k, or λ, and hence they are distinguished by 3 iterations of 1-WL.
Lemma 17. The 4 × 4 Rook’s graph and the Shrikhande graph are distinguished by DS-GNN and DSS-GNN with the ED policy.
Proof. We prove that DS-GNN can distinguish these two graphs by directly computing 1-WL colorings of edge-deleted subgraphs. It can be checked computationally that all edge-deleted subgraphs of the Rook’s graph are isomorphic, and likewise all edge-deleted subgraphs of the Shrikhande graph are isomorphic. Thus, it suffices to show that a 1-WL coloring of one edge-deleted subgraph of the Rook’s graph differs from a 1-WL coloring of one edge-deleted subgraph of the Shrikhande graph.
We use the numbering of nodes as we defined in the beginning of Appendix F.2. Each node starts with an initial color that we denote ‘a’. See Tables 12 and 13 for the coloring, which differs for the two graphs at iteration 4 (as an aside, note that the first 3 iterations were already computed in the proof of Lemma 16). Thus, these two graphs are distinguished by DS-GNN, and hence DSS-GNN, with the ED policy.

heading: F.5 PROOF OF PROPOSITION 3
text: With the above lemmas for different policies we may formally prove Proposition 3.

heading: Proof of Prop 3.
text: (1) Lemmas 14 and 15 show that ND and depth-n ÊGO+ can distinguish strongly regular graphs of different parameters. Lemma 16 shows the same for ED.
(2) is proven in Lemmas 14 and 15.
(3) is directly proven by Lemma 17, as DS-GNN with ED distinguishes the Rook’s graph and the Shrikhande graph, which are strongly regular of the same parameters.
Finally, note that 3-WL cannot distinguish strongly regular graphs of the same parameters (Arvind et al., 2020), so ED is strictly stronger than 3-WL. While we have only provided one pair of strongly regular graphs of the same parameters that ED can distinguish, the general case for all strongly regular graphs is hard; while a lot of work has gone into distinguishing non-isomoprhic strongly regular graphs, there is no known polynomial-time algorithm to do so (Babai et al., 2013).

heading: G COMPLEXITY

heading: G.1 FORWARD PASS
text: Here, we analyze the complexity of our method, when using MPNNs as graph encoders, compared to other graph networks that are more expressive than 1-WL. In Table 14 we summarize the results. We assume that the feature dimensionality is a constant.
For dense graphs, our method requires O(|S|n2) time, as each of the |S| subgraphs is processed using a MPNN of time complexity O(n2). When |S| = O(n) as in the case of node-deleted and ego-net policies, the time complexity is O(n3), just as in the case of PPGN (Maron et al., 2019a)
and 3-IGN (Maron et al., 2019b). When |S| = O(n2) as in the case of edge-deleted policies, the time complexity is O(n4) like 3-GNN (Morris et al., 2019). More specifically, the time complexity of our method improves toO(|S|n∆max) where ∆max is the maximum node degree, which is low for sparse graphs. This is a major benefit of our method, as PPGN, k-IGN do not have time complexity improvements for sparse graphs, as they perform global aggregations instead of just local neighborhood aggregations. For sparse graphs where ∆max = O(1), we gain a factor of O(n) in time complexity over PPGN and 3-IGN and a factor of O(n2) over 3-GNN.
Table 14 also reports the time complexity of two provably expressive, sparse architectures: GSN (Bouritsas et al., 2020) and CWN (Bodnar et al., 2021a). The first method has the same complexity of standard GNNs as long as the number of considered subgraphs in the bank is a small constant. ESAN can match the complexity of GSN only in the case where |S| = O(1), which is only the case for stochastic policies that we consider. The remarkable efficiency of GSN, however, is paid in terms of preprocessing complexity (discussed in the next subsection). As for CWN, we report the time complexity for a generic lifting procedure generating a 2-dimensional cellular complex, with np denoting the number of cells at dimension p and Bp the maximum considered boundary size. Here, n0 = n, n1 = O(n∆max) refer to, respectively, the number of nodes and edges. In the case of ring-liftings with ring size upper-bounded a small constant, the complexity can be rewritten as O (n∆max + n2). In the case of molecules, the number of rings, n2, is generally contained. However, the number of 2-cells may grow even exponentially for general graph distributions. When employing policies ND, ED, EGO(+), on the contrary, our approach works with bags whose cardinality never exceeds the number of edges, irrespective of the graph distribution.
The space complexity of our method isO (|S|(n+ n∆max)), as we need to compute n node features for each subgraph, while keeping the subgraph connectivity in memory. This evaluates to O(n2 + n2∆max) for node-deleted and ego-net policies and O(n2∆max + (n∆max)2) for the edge-deleted policy. We also note that the space complexity of our method can be improved to O(n + n∆max) when using the DS-GNN architecture, as we may compute the GNN embedding of each subgraph online and accumulate them in one tensor that represents the sum over all subgraphs — though this requires sacrificing parallelism across subgraphs. Also, note that certain policies that significantly reduce the size of subgraphs, such as low-depth ego-net policies, are even more efficient because the number of edges in the subgraphs are much lower.

heading: G.2 PREPROCESSING
text: In order to perform message passing on subgraphs, it is first required to apply a selection policy and generate the bag. This amounts to a one-off computation that can be performed prior to training. Simple implementations of the ND and ED policies have complexities O(nm) and O(m2), respectively, where n is the number of nodes and m is the number of edges. As noted above, m can be upper-bounded by n∆max, with ∆max typically small in sparse graphs. EGO policies are easily implemented inO(n(n+m)), whereO(n+m) is the complexity of a generic Breadth First Search algorithm employed to recover the k-hop neighborhood of a source node. More sophisticated implementations of these selection policies may be possible, making the preprocessing step even more parsimonious. As pointed out above, the preprocessing complexity directly depends on the size and density of the graphs at hand; while practical run-times may be drastically reduced when working with sparse graphs, we remark that they can never exceed the aforementioned theoretical bounds, independently of the nature of graphs characterising the task being solved.
This is in contrast with the preprocessing complexity of GSN and CWN, which is generally O(nk) for a generic substructure of size k. Preprocessing times are remarkably reduced in practice for certain families of graphs (e.g. planar graphs) and substructures for which specialised algorithms exists (e.g. triangles and rings). For example, these methods have been observed to attain tractable practical run-times on molecular datasets. Still, the worst-case exponential complexity may hinder their application in the presence of graphs of non-characterised distribution or when substructures of more efficient matching are not known to play a relevant role.
Finally, we remark that all these preprocessing strategies are embarrassingly parallel w.r.t. the different graphs in a dataset and parallelisation techniques can be applied to dramatically reduce the empirical run-time.

Review summaries:
This paper proposed a novel way of increasing MPNN expressive power without using higher order node tuples representation, thus proposed method has lower complexity compare to naive powerful GNN methods. The core idea is to create a set of subgraphs for each graph in the given dataset by using single node or edge deleting,...etc policy. They create a virtual graph that adjacency is summation of subgraph's adjacencies and node feature matrix is the summation of subgraph's feature matrix. Each subgraph's next layer representation will be obtained by aggregation of self subgraph's new representation by baseline MPNN and also this virtual graph's representation by another MPNN. In application this virtual graph is replaced by original graph or in another version is basically neglected. After arbitrary number of layers, they apply subgraph level pooling to obtain invariant representations. They see all subgraph's final representation as a set of representations. Thus to obtain final graph level representation, they apply another layer on set of subgraph representations such deepsets.   

The paper addresses known limitations of the expressiveness of message passing neural networks (MPNNs). Key idea is to generate subgraphs from the original graph, to encode each subgraph with a GNN, and to aggregate the resulting set of subgraph-encodings. Since generating all possible subgraphs is computational infeasible for larger graphs, only a smaller subset of subgraphs is used in practice. The paper shows that their approach is more expressive than 1-WL. Moreover, the paper shows that different variants of the proposed method can outperform the base model.

This paper proposes to improve the expressivity of MPNN by using H-Equivariant layers to process bags of subgraphs accounting for their natural symmetry. The proposed DS(S)-GNN is proven to be equivalently powerful as DS(S)-WL, which can be strictly more powerful than 1-WL. It also provides theoretical results about how design choices such as the subgraph selection policy and equivariant neural architecture affect the architecture’s expressive power. In addition, a stochastic sampling scheme is proposed to mitigate the computational overhead. 

This paper aims to improve GNNs' expressive power based on bag-of-subgraph representation. The authors develop a Equivariant Subgraph Aggregation Network, which uses equivariant layers to encode subgraphs and aggregate subgraph representations. The authors have performed theoretical analysis of the proposed framework, subgraph selection policies, and their expressive power. The experiments show that such an encoding can lead to a better expressive power on several real and synthetic graph classification datasets.