Equivariant Subgraph Aggregation Networks
Authors: Beatrice Bevilacqua
Fabrizio Frasca
Derek Lim
Balasubramaniam Srinivasan
Chen Cai
Gopinath Balamurugan
Michael M. Bronstein
Haggai Maron
Venue: ICLR 2022 Spotlight (2022)
Keywords: Graph Neural Networks
Expressive power
Equivariance
Weisfeiler-Leman

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. 

Published as a conference paper at ICLR 2022
EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS
Beatrice Bevilacqua"
Fabrizio Frasca"
Derek Lim" MIT CSAIL derek Limmmit edu
Purdue University Abevilac&purduee edu
Imperial College London & Twitter
Efrasca@twitter.cm com com
Balasubramaniam Srinivasan Purdue University bsriniv@purdue.edi
Chen Cai
Gopinath Balamurugan
UCSD CSE
University of Tuebingen gbm0 9880998e00 @mma com
Michael M. Bronstein
Haggai Maron
Imperial College London & Twitter mbronsteinntwittee com
NVIDIA Research
bmaron@nvidia.com
ABSTRACT
Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due their simplicity and scal- ability. Unfortunately. it was shown that these architectures are limited in their expressive power. This paper proposes a novel framework called Equivariant Sub- graph 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 a set of subgraphs derived by some predefined policy, and to process using a suitable equivariant architecture. We develop novel variants of the I-dimensional Weisfeiler-Leman (I-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 ex- pressive architectures. Moreover, design choices such as the subgraph selection policy and equivariant neural archi- tecture affect architecture's expressive power. To deal with the increased com- putational cost, we propose subgraph sampling scheme, which can be viewed as stochastic version of our framework. A comprehensive set of experiments on real and synthetic datasets demonstrates that our framework improves the expres- sive power and overall performance of popular GNN architectures.
provide theoretical results that describe how
INTRODUCTION
Owing to their scalability and simplicity, Clessage-Passing Neural Networks (MPNNs) are the lead- ing 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 expressive as the Ceisfeiler-Lehman sequence, MPNNs cannot distinguish between very simple graphs (See Figure In light of this limitation, a question naturally arises: is it possible to improve the expressiveness of MPNNs?
(WL. graph isomorphism test (Weisfeiler & Leman 1968). As a con-
Several recent works have proposed more powerful architectures. One of the main approaches in- volves higher-order GNNs equivalent to hierarchy of the k-WL tests (Morris et al. 2019) 2020bb
Maron et al.] 2019b a. Keriven & Peyré, 2019: Azizian & Lolarge [021] /Gertt (020). offering 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.) [2022 Thiede et [021] or lift graphs into simplicial- (Bodnar et al., 2b) or cell complexes (Bodnar et al.] (222aa), 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.
"Equal contribution, authors in alphahetical order.

---

Published as a conference paper at ICLR 2022
WL-indistiguissable now-iileee-nniieeooo con-isooooppiic graphs
Bags of WL-distiguishable subpsttppuhhabblesuppphhhh
Subgraph
WL coloring
WL subgruph histngram
Original
WL color histogrant
WL
coloring
Original
Suhgraph
WL Wilcalrinng
WL. subgmpph histngram
graph
WL color histogram
WL. colocing
du
Figure 1: We present a provably expressive graph learning framework based on representing graphs as bags of subgraphs and processing them with an equivariant architecture composed of GNNs and set networks. Left: A pair of graphs not distinguishable by the WL test. Right: The corresponding bags (multisets) of edge-deleted subgraphs, which can distinguished by our framework.
Our approach. In an effort to devise simple, intuitive and more flexible provably expressive graph architectures, develop novel framework, dubbed Equivariant Subgraph Aggregation Networks (ESAN), to enhance the expressive power of existing GNNs. Our solution emerges from the ob- servation that while two graphs may not be distinguishable by 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 encoding can lead to better expressive power. Following that observation, we advocate represent- ing each graph as a bag of subgraphs chosen according to some predefined policy, c.g., all graphs that can be obtained by removing one edge from the original graph. Figure illustrraee 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 architec- ture specifically tailored capture this object's symmetry group. Specifically, we first formulate the symmetry group for set of graphs as the direct product of the symmetry groups for sets and graphs. We then construct neural network comprising layers that are equivariant to this group. Motivated by Maron et al. (2020), these layers employ two base graph encoders subroutines: The first encoder implements a Siamese network processing each subgraph independently; The second acts 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 represen- tations into an invariant representation of the original graph that used in downstream tasks.
An integral component of our method, with major impacts on its complexity and expressivity, is bag of subgraphs, which is then
the subgraph selection policy: function that maps a graph 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 WI. test, capable of encoding the multiset of subgraphs according to the base graph encoder (e.g.. WI. for MPNNs), Furthermore, 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 separate 3- indistinguishable graphs using only 1-WL graph encoder, and that it can enhance the expressive power of stronger architectures such as PPGN MMrrnn et al.) 2019a).
We then present empirical results wide range of synthetic and real datasets, using several isting 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 achieves perfect accuracy.
2

---

Published as a conference paper at ICLR 2022
We then evaluate ESAN 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 gener- ating 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 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.
2 EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS (ESAN)
In this section, we introduce the ESAN framework. It consists of (1) Neural network architectures for processing bags of subgraphs (DSS IDSS-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 clasiffcationnreerrssiin setting We represent a graph with nodes as a tuple G' = (A, where A E RTX= is the graph's 's adjacency matrix and X Raxd is the node feature matrix. The main idea behind our approach to represent the graph G' as a bag (multiset) SG G ......... Gm } of its subgraphs, and to make a prediction on graph based on this subset, namely FG) := F(Sc). Two crucial questions pertain to this approach: (1) Which architecture should be used to process bags of graphs, i.e., How to define F(Sa)?, and (2)
Which subgraph selection policy should be used, i.e., How to define Sc?
2.1 BAG-OF-GRAPHS ENCODER ARCHITECTURE
To address the first question, we start from the natural symmetry group of bag of graphs. We first devise an equivariant architecture called DSS-GNN based on this group, and then propose par- ticularly interesting variant (DS-GNN) obtained by disabling one of the components DSS-GNN.
Symmetry group for sets of graphs. The bag SG [GI...., Gm } of subgraphs of G can be represented as tensor (A, x') E Raxaxm x Raxdxm, assuming the num- ber of nodes n and the number of subgraphs m are fixed. Here, A E ę=x*xm represents a set of m adjacency ma- trices, and X' E _exdxm represents set of m node feature matrices. Since the order of nodes in each sub- graph, as well as the order of these subgraphs in Sa, 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 graph via (a A) Ag-1(i) (j) and the permuta- tions of the subgraphs in Sa. represented by the symmet- ric group Sm that acts sets of graphs via (T- A)ija A Aijr-((k) and (T- x) -ar-1(1)- These two groups can be combined using a direct product into a single group H Sm x Sn that acts on (A, X)) in the following way:
Original graph
Bag of subgraphs
Tensor representation
Figure 2: The symmetry structure of a bag of subgraphs, in this case the set of all m = 3 edge-deleted subgraphs. This set of subgraphs is represented m x n x tensor A (and additional node features that are not illustrated here). (T, E Sm x Sn acts on the tensor A by permuting the subgraphs (r) and the nodes in the subgraphs (a), which are assumed be ordered consistently.
an
(a X)a Xi)-(i)-- Set symmetries
((T, A)isk = Ag- A (0)-)())~-(())) ((T, Xa) = Xx-1((N)-1
In other words, T permutes the subgraphs in the set and a permutes the nodes in the subgraphs, as depicted in Figure 2 Importantly, since all the subgraphs originate from the same graph, can order their nodes consistently throughout, i.e., the i-th node in all subgraphs represents the i-th node in the original graph ( This setting can be seen a particular instance of the DSS framework (Maron et al. 2020) applied to a bag of graphs.
'The setup can he casily changed to support node and edge prediction tasks. This consistency assumption justifies the fact that we apply the same permutation to all subgraphs, rather than having different node permutation (a1,..., Fm) for each subgraph.
3

---

Published as a conference paper at ICLR 2022
DSS-GNN Architecture
H-Equivarianl Layer
Input: (A,
Processed graphs
Invariant
Final graph representation
Input
Output
(per) subgraph
(Ag.X)
features
E! (GNN)
(1
H- H-Eqqivvarian Layer
H H-E-qivarraa Layer
H-Equivariant Layer
Set Encoder
(Aver X
(GNN)
(Aqu
pool
(I ΣX)
Esubgraphs
Rsubgraphs
Eets
(GNN)
Figure 3: DSS-GNN layers and architecture. Left panel: the DSS- GNN architecture is composed of three blocks: Feature Encoder, Readout Layer and Set Encoder. Right panel: DSS-GNN layer is constructed from a Siamese part (orange) and an information-sharing part (yellow).
Il t/-qquivariant layers. Our goal is to propose an H H-equivariant architecture that can process bags of subgraphs accounting for their natural symmetry (the product of node and subgraph permutations). The main building blocks such equivariant architectures are H equivarriat layers. Unfortunately. characterizing the set of all equivariant functions be difficult task, and most works limit them selves to characterizing the spaces of linear equivariant layers. In our case, Maron et al. (2020) characterized the space of linear equivariant layers for sets symmetric elements (such graphs) with a permutation symmetry group P (S,, in our case). Their study shows that each such layer is composed of Siamese component applying a linear P-cquivariant layer each set element inde- pendently and an information sharing component applying a different linear P-equivariant layer to the aggregation of all the elements in the (see Appendix
Motivated by the linear characterization, we adopt the same layer structure with Siamese & infor- mation sharing components, and parameterize these ones using any equivariant GNN layer such as MPNNs. These layers R2xxxm x paxdxm + guxnxm x Raxd' d' xm map bags of subgraphs to bags of subgraphs, as follows:
(L(A, L' L', L3 4,,
Here, X, are the adjacency and feature matrices of the j-th subgraph (the j-th components of tensors A, X, respectively), and (L(A, X)); denotes the output of the layer on the i-th subgraph. L',L² L2 == 1dd - _2ax= x guxd' represent two graph encoders and can be any type of GNN layer. We refer to I_, 2 as the base graph encoders. When MPNN encoders parameterise I,,, L,,, 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. (2019)) as the base encoder.
While the encoder I acts every subgraph independently. 1,2 allows the sharing of information across all the subgraphs in Sç. In particular, the 2 module operates on the sum of adjacency and feature matrices across the bag. This is 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 (E)=1 A, and Σ)= X)) can be replaced with (1) Sums that exclude the current subgraph (E Aj and Em Xj) or with (2) Other aggregators such as max and mean. We note that for the subgraph selection policies we consider in Subsection aggregation over the subgraph adjacency matrices, A max, Aj. recovers the original graph connectivity. This is a convenient choice in practice and we use it throughout the paper. Finally, the --equivariance of the layer follows directly from the S,-equivariaace of the base-encoder, and the Sm-equee -nuuivavaraa of the aggregation. Figure 3 (right panel) illustrates our suggested H -equivarriant layer.
2.2 entrywise
DSS-GNN comprises three components:
F GNN = Frees Rauhngrahss o Fruhhgrapss
The first component is an Equivariant Feature Encoder, Exuhgrapha R x Raxdxm
Raxnxm Raxd' xm implemented as composition of several H-equivariant layers (Equation)

---

Published as a conference paper at ICLR 2022
The purpose of the subgraph encoder is to learn useful node features for all the nodes in all sub- graphs. On top of the graph encoder, we apply a Subgraph Readout Layer Rsubgraphs R=xaxm x Raxd xm - Rd' xm 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, Esess R xm T is a universal Set Encoder, for example DeepSets (aheer et al. 2017)
or PointNet QQ 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 set of S, invarrint representations (Bauhgraphs Raubgraph)) and then encodes the resulting set of subgraph representations into a single H-invariant representation Eyets of the original graph G.
DS-GNN is variant of ESS-GNN obtained by disabling the information sharing component, i.e., by setting L = 0 in Equation I for each layer in Ssuggraphs As a result, the subgraphs are encoded independently, and Esubgraphs is effectively a Siamese network. DS-GNN
be interpreted Siamese network that encodes each subgraph independently. followed by a set encoder that encodes the set of subgraph representations. DS-GNN is invariant to larger symmetry group obtained from the wreath product S,, S.
we will show that both DS-GNN and DSS-GNN are powerful architectures and that in In Section 3
certain cases DSS-GNN has superior expressive power.
2.2 SUBGRAPHI SELECTION POLICIES
The second question, How to select the subgraphs?, has 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 S g. A subgraph selection policy is a function π : 9 + P()) that assigns to each graph G' subset of the set of its subgraphs (G). We require that π is invariant to permutations of the nodes in the graphs, namely that x (G) = ( G), where a E S, is a node permutation, and a G is the graph obtained after applying Ø. We will use the following notation: rTG) ST. As before, Sg 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-delcted subgraphs (ED), and ego-networks (EGO, EGO+), as described next. In the node-deleted policy, graph mapped to the set containing all subgraphs that can be ob- tained from the original graph by removing single node Similarly, the edge-deleted policy is defined by removing 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 node its k-hop neighbourhood with the induced connectivity). We also consider a variant of the ego- networks policy where the root node holds 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 ST for any policy obtaining the augmented version म. For example, EGÔ is new policy that outputs for each graph the standard EGO policy described above and the original graph.
Stochastic sampling, For larger graphs, using the entire bag of subgraphs for some policies can be expensive. To counteract this, we sometimes employ a stochastic subgraph sub-sampling scheme which, in every training epoch, selects a small subset of subgraphs 3 C S7 independently and uniformly at random. In practice, we use |S" /1ST E {0.05, 0.2, 0.5}. Besides enabling running on larger graphs, sub-sampling also allows larger batch sizes, resulting in a faster runtime per epoch. During inference, we combine l such subsets of subgraphs (we use f = 5) and majority voting scheme make predictions. While the resulting model 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.
Thee wreath product models setup in which the subgraphs are not aligned, see Maron al. 2020 Wang (220)) for further discussion.
ctal. al.
For all policies, node removal is implemented by removing all the edges to the node, so that all the sub- graphs are kept aligned and have n nodes.
5

---

Published as a conference paper at ICLR 2022
2.3 RELATED WORK
Broadly speaking, the efforts in enhancing the expressive power of GNNs can be clustered along three main directions: (1) Aligning the k-WL hierarchy (Morris al. 2019 2020b Maron al., 20196 a); (2) Augmenting node features with exogenous identifiers (Sato et al. 2021 Dasoulas al. 2020 Abboud et al., 2020); (3) Leveraging on structural information that cannot provably be captured by the WL test (Bouritsas et al. 2022; Thiede et al., [021] de Haan et al. 2020, Bodnar al., 202Tb aj. Our approach falls into the third category. It describes an architecture that uncov- ers discriminative structural information within subgraphs of the original graph, while preserving equivariance -typiclly lacking in (2) and locality and sparsity of computation - generally absent in (I). 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, 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, they can parameterize the Psuhgraphs module whenever the application domain suggests so. We refer readers to Appendix [or a more detailed comparison of our work to relevant previous work, and Appendix Forrr in-depth analysis of its computational complexity.
THEORETICAL ANALYSIS
In this section, we study the expressive power of our architecture by its ability 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.
3.1 WL ANALOGUE FOR ESAN
We introduce two color-refinement procedures inspired by the WI. isomorphism test (Weisteiler & Leman 1968). These variants, which we refer to as DSS WI and DS-WL. variants, are inspired by DSS-GNN and DS-GNN with I-WL equivalent base graph encoder (e.g., 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 way extract and leverage this discriminative source of information. Details and proofs are provided in Appendix[D
(Init.) Inputs to the DSS-WL WL test are input graphs G¹, G2 and subgraph selection policy n. The algorithm generates the subgraph bags over the input graph by applying æ. 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 is refined according the rule: c HASH(C s. sy Nt s. Ct MG). Here, N denotes the multiset of colors v's neighborhood over subgraph S: C₁ represents the multiset of e's colors across subgraphs; M, is the multiset collecting these cross-bag aggregated colors for v's neighbors according to the original graph connectivity.
(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 corre- sponding bag. The algorithm terminates as soon as the graph representations diverge, deeming the inputs non-isomorphic. The test inconelusive if the two graphs are assigned the same representa- tions at convergence, i.e., when the color refinement procedure converges on each subgraph.
DS-WL obtained special setting of DSS-WL whereby the refinement rule neglects inputs C and M.. These inputs account for information sharing across subgraphs, and by disabling them, the procedure runs the standard WI. on each subgraph independently. We note that since DS-W WI. is a special instantiation of DSS-WI. we expect the latter to be as powerful as the former; we formally prove this Appendix [D] Finally, both DSS- and DS-WL variants reduce trivial equivalents of the standard WL test with policy G + {G}.
3.2 WI. ANALOGUES AND EXPRESSIVE POWER
Our first result confirms our intuition on the discriminative information contained in subgraphs: Theorem (DS(S)-WL strictly more powerful than I-WL). There exist selection policies such that DS(S)- WL. is strictly more powerful than /-WL. in distinguishing between non-isoe non-isomorphic graphs

---

Published as a conference paper at ICLR 2022
The idea is that it is possible to find policies such that (i) our variants refine WL, i... any graph pair distinguished by WL is also distinguished by our variants, and (ii) there exist pairs graphs indistinguishable by WL but separated by 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-WI. and DSS-WL can distinguish pairs of these graphs:
Lemma 1. CnL 2) can be distinguished from any CSL(n, k) with & E [3,n/2 1] by DS WL and DSS- WL with either the ND, EGO, or EGO+ policy.
is possible to also find exemplary pairs for the ED policy: one included is Figure while another is found in Appendix D 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 be any family of bounded-sized graphs endowed with node labels from a finite set, There exist selection policies such that, for any two graphs Gt, G2 in F, distinguished by DS( there is a DS(S)-GNN model the form of Equation ( assigning G G2 distinct representations. Also, DS-GNN with MPNN base graph encoder is at most as powerful as DS-WL.
Let DL-
In particular, this theorem applies to policies such that each edge in the original graph appears at least once in the bag. This the case of the policies 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 | 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 (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 ! Theorem 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.
3.3 THEORETICAL EXPRESSIVENESS OF DESIGN CHOICES
Our general ESAN architecture has several important design choices: choice of DSS-GNN or DS- GNN 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 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; Maaon et al. 2019a). Thus, one may desire to use a more expressive graph network than MPNNs. The following proposition analyzes the expressivity of generalization of DS-GNN to use a 3-WL base encoder; details are given in the proof in Appendix
Let the subgraph policy be depth-/ / EGO or EGO+ Then: (1) DSSGGN 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.
Proposition 2.
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 different poli- cies also result in different expressive power of our model. We analyze the case of 1 1-WL (MPNN)
'In the of DS-WI. it is required that the original graph included in the bag.
7

---

Published as a conference paper at ICLR 2022
Table I: TUDatasets. Gray background indicates that ESAN outperforms the base encoder. SoTA line reports results for the best performing model for each dataset.
Method Dataset
MUTAG
PROTEINS
NCI1
NC1109
IMDB-B
IMDB-M
SOTA
92.7266.1
68.2
77.244.77
83.6
84.0 1.6
77.8
54,3
GIN Xu 2019
89.45:566
64.6=7.0
76.2+:2888
82.7
82.2=1.6
75.1=5.11
52.3++2.88
DS-GNN (GIN) (ED)
89.9113.7
66.01122
7..8:14.6
23.3
83.0
76.11226
$2.911244
DS-GNN (GIN) (ND)
89.4--4.8
6..3+77.0
77.1-1-.66
83
1.
75.4::29
52.7++2..0
DS-GNN (GIN) (EGO)
89.9.66.5
68.6:15.8
76.7::5.8
81.4
1..
76.1
52.6.12.88
DS-GNN (GIN) (EGO+)
91.0+--.88
68.7
76.7++444
82.0 1.4
80.3-1:099
77.1-
53.2++2..8
DSS-GNN (GIN) (ED)
910++4.8
66.67.33
75.8++:455
83,4+225
82,8=0.9
76.8=4.33
53.5+33
DSS-GNN (GIN) (ND)
91.0.3..5
66.11.5
76.143344
83.6 1.5
83.1
16.1
13.34199
DSS-GNN (GIN) (EGO)
68.245.88
76.7+:4.1
83.6=
1.
7655288
53.343.11
DSS-GNN (GIN) (EGO+)
91117.0
69.2::6.5
75.9+
83.7++1.
82.8-112
77.1=330
23.2+
graph encoder for different choices of policy, restricting our attention to strongly regular (SR) graphs. These graphs are parameterized by 4 parameters (n, k, X, ()). 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
We show that our framework with the ND and depth-n EGO+ policies can 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 formalize the above statements in Proposition 3
Proposition 3. Consider DS-GNN on SR graphs: 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 as strong as 3-WL, while ED is strictly stronger than 3-WL.
EXPERIMENTS
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?. In the following, we report our main experimental results. We defer readers to Appendices C.2 and C.3 for additional details and results, including timings. An overall discussion of the experimental results is found at Appendix C.4 Our code is also available 6
Expressive power: EXP, CEXP, CSL. In an effort answer question (1), first tested the benefits of our framework on the synthetic EXP, CEXP (Abboud et al.) 2020), and CSL datasets (Murphy al.
2019 Dwivedì al. 2020), specifically designed that any 1-WL GNN cannot do better than random guess (50% accuracy in EXP, 75% in CEXP, ,, 10% in CSL.) As for EXP and CEXP. report the mean and standard deviation from 10-fold cross-validation in Table Appendix C.2 While GIN and GraphConv perform no better than random guess, DS- and DSS-GNN perfectly solve the task when using these layers base graph encoders, with all the policies working equally well. Table [ in Appendix C.3 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 sam- pling only 5% of the subgraphs. On the CSL benchmark, both DS- and DSS-GNN achieve perfect performance for any considered 1-WL base encoder and policy, even stochastic ones. More details found in Appendix C.2 and Appendix C.3
TUDatasets. We experimented with popular datasets from the TUD repository. We followed the widely-used hyperparameter selection and experimental procedure proposed by Xu et al. 2019))
Salient results are reported in Table I where the best performing method for each dataset is reported
as SoTA; in the following we discuss the full set of results, reported in Table 4 in Appendix C.2 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
httpp::/ thub. com www.///.wwbr...eee/ wew.beeii//eee /HSAN
8

---

Published as a conference paper at ICLR 2022
improves over the base encoder, up almost 5% (DSS-GNN: 51/56 cases, DS-GNN: 42/56 cases, see gray background); (3) ESAN consistently outperforms other methods aimed at increasing the expressive power of GNNs, such ID-GNN (You et al. 2021 and RNI (Abboud et al. 2020 Particularly successful configurations are: (i) DSS-GNN (EGO+) GraphConv/GINN; (ii) DS GNN (ND) + GIN. ia Appendix C.3 compares the performance of 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.
OGB. We tested the ESAN framework on the OGBG-MOLHII and OGBG-MOLTON datasets from Hu et al. (020)) using the scaffold splits. Table 2 shows the results of all ESAN variants to the performance of its GIN base en-
Table Test results for OGB datasets. Gray back- ground indicates that ESAN outperforms the base encoder.
OOBO-MOLHIV ROC-AUC (S)
OGBU-MOLTON21
coder, while in Table 5 in Appendix C.2 we re-
Method
(OC-ALIC())
port results obtained when employing a GCN
GIN Ku 2019
15:5821.40
74.9110511
base encoder. When using GIN, all ESAN vari-
DS-GNN (GIN) (ED)
76,43+22122
75,12+0.00
DS-GNN (GIN) (ND)
76.1920996
15:34+1.21
ants improve the base encoder accuracy by up to 2.4% on MOLIIM and 3% OGBG- MOLTOX21. In addition, DSS-GNN performs better that DS-GNN with GCN. In general, DSS-GNN improves the base encoder in 14/16 cases, whereas a DS-GNN improves it in 10/16 cases. Finally, Table g in Appendix C.3 shows the performance of our stochastic variant.
DS-GNN (GIN) (RGO)
78.00=1.422
7622::0.622
DS-GNN (GIN) (RGO+)
27.40=2.19
76.39: 1.18
DSS-GNT (GIN) (ED)
17.03:1181
16.71:10667
DSS-GNN (GIN) (ND)
76.63:11552
77.21::0.70
GNN (GIN) (EGO)
77,19-11227
DSS-GNN (GIN) (EGO+)
76.78:1:.60
77.95:1:.40
Table 3: ZINC12k dataset. Gray background in- dicates that ESAN outperforms the base encoder.
ZINC12K. We further experimented with an additional large scale molecular benchmark:
Method
ZINC L)
ZINC12K (Sterling & Irwin 2015; Gómez-
PNA
Corso ct
2020
0.188+00004
Bombarelli et al. Dwiveedi et al.) 2020),
DGN
Beean
202
0.168-10.003
where, as prescribed, we impose 100k param-
SMP
Vignac ct gl
2020
0.138
GIN
Xu
0.252::0.017
eter budget. We observe from Table 3 that all ESAN configurations significantly outperform their base GIN encoder. In general, our method achieves particularly competitive results, irre- spective of the chosen subgraph selection pol- icy. It always outperforms the provably ex- pressive PNA model (Corso et al.] (020). while other expressive approaches (Beaini et al. 2021 Vignac et al., (220) are outperformed when our model is equipped with EGO(+) poli- cies. With the same policy, ESAN also outper-
HIMP et
2020)
0.051+0.000
GSN (Bouriiuu
2022
0.108-:0.018
CIN SMALL (5xcinr clal
2021a
0.004.10.004
DS-GNN (GIN) (ED)
0.172::0.008
DS-GNN (GIN) (ND)
0.1711100110
DS-GNN (GIN) (EGO)
0. 0.12::10.006
DS-GNN (GIN) (EGO+)
0.116:00009
DSS-GNN (GIN) (ED)
0.172::0.005
DSS-GNN (GIN) (ND)
0.166:10.004
DSS-GNN (GIN) (EGO)
0.107-10.00
DSS-GNN (GIN) (EGO+)
1022::0.033
forms HIMP (Fey et al. 2020), and GSN (Bouritsas et al. 2022) which explicitly employ informa- tion from rings and their counts, predictive signal this task (Bodnar et al.) 2021ap. In conclusion, ESAN is the best performing model amongst all provably expressive, domain agnostic GNNs, while being competitive with and often of superior performance than (provably expressive) GNNs which employ domain specific structural information.
CONCLUSION
We have presented ESAN, novel framework for learning graph-structured data, based on decom- posing 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 learn- ing architectures and performs well on multiple graph classification benchmarks. The main limita- tion 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 subgraphs (c.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.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We would like to thank all those people involved in the 2021 London Geometry and Machine Learn- ing Summer School (LOGML), where this research project started. In particular, we would like to express our gratitude to the members of the organizing committee: Mehdi Bahri, Guadalupe Gon- zalez, Tim King, Dr Momehil Konstantinov and Daniel Platt. We would also like to thank Stefanie Jegelka, Cristian Bodnar, and Yusu Wang for helpful discussions. MB is supported in part by ERC Consolidator grant no 724228 (LEMAN).
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprini urXiv:2010.01199 2020.
Vikraman Arvind, Frank Fuhlbrücc, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 11::42-59, 2020.
James Atwood and Don Towsley, Diffussion-convolutional neural networks. In NIPS, pp. 1993-2001, 2016.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. In International Conference on Learning Representations, 2021.
László Babai, Xi Chen, Xiaorui Sun, Shang-Hus Teng, and John Wilmes. Faster canonical forms for strongly regular graphs. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 166. IEEE, 2013.
Muhammet Balcilar, Pierre Heroux, Benoit Gauzere, Pascal Vasseur, Sebastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 599-608. PMLR, 18-24 Jul 2021.
Igor Baskin, Vladimir A Palyulin, and Nikolai S Zefirov. A neural device for searching direct correlations between structures and properties of chemical compounds. J. Chemical Information and Computer Sciences, 37(4):715-721, 1997.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference Machine Learning, 2021.
Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https://wart wandb. com/ Software available from wandb.com.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: CW networks. In Advances in Neural Information Processing Systems, volume 34, 202
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Lio, and Michael Bronstein. Weisfeiler and lchman go topological: Message passing simplicial networks. ICML, 2021b.
Giorgos Bouritsas, Andreas Loukas, Nikolaos Karalias, and Michael Bronstein. Partition and code: learning how to compress graphs. In Advances in Neural Information Processing Systems, volume 34, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42 2017.
10

---

Published as a conference paper at ICLR 2022
Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličkovié. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv:2104. 2021.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1r 2013.
Chen Cai, Nikolaos Vlassis, Lucas Magee, Ran Ma, Zeyu Xiong, Bahador Bahmani, Teng-Fomt -ong Wong, Yusu Wang, and WaiChing Sun. Equivariant geometric learning for digital rock physics: estimating formation factor and effective permeability tensors from morse graph. arXiv preprint arXiv:2104.05608, 2021.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Peter Cameron. Strongly regular graphs. Topics in Algebraic Graph Theory, 102:203-224 2004.
Lei Chen, Zhengdao Chen, and Joan Bruna. Learning the relevant substructures for tasks graph data. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8528 8032,,53,220 2021. doi: 10.100/CCASSP33922222000999
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. arXiv preprint urXiv:1905.1 /2560, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International confer- ence on machine learning. pp. 2990-2999 2999.0999..00 PMLR, 2016
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Sys- tems, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. In NeurIPS, 2021.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Christian Bessiere (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2126-2132, 7 2020. doi: 10.24966/ijcci.22200229 Main track.
Pim de Haan, Taco Cohen, and Max Welling. Natural graph networks. In NeurlPS, 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.009922 2020.
Carlos Esteves, Christine Allen-Blanchette Ameesh Makadia, and Kostas Daniilidis. Learning so
(3) equivariant representations with spherical cnns. In Proceedings of the European Conference Computer Vision (ECCV), pp. 52 68, 2018.
Wenqi Fan, Yao Ma. Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
M. Fey, J. G. Yuen, and F. Weichert. Hierarchical inter-message passing for learning on molecular graphs. ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric.
arXiv preprint arXiv: arXiv:1903.000 02428, 2019.
11

---

Published as a conference paper at ICLR 2022
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pp. 129- 143. Springer, 2003.
Floris Geerts. The expressive power of kth-order invariant graph networks, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Christoph Goller and Andreas Kuchler. Learning task-dependent distributed representations by backpropagation through structure. In ICNN, 1996.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sänchez-Lengeling Dennis Sheberla, Jorge Aguilera-Ipanee Iparraguirre, Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru- Guzik. Automatic chemical design using a data-driven continu- ous representation of molecules. ACS Central Science, 4(2):268-277) 276, Jan 2018. ISSN 2374-7951. doi: 10. /te2l/acscentsc.bb005522
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 1025-1035, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems, volume 33, pp. 22118-22133 22-3..3. Curran Asso- ciates, Inc., 2020.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICML, 2018.
Justin Johnson, Agrim Gupta, and Li Fei-Fei. Image generation from scene graphs In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
Paul Kelly. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1):911-968, 1957.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32:7092-7101, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In ICLR, 2017.
Dmitry B Kireev. Chemnet: a novel neural network based method for graph/property mapping. J.
Chemical Information and Computer Sciences, 355-) 1995.
Risi Kondor and Shubhendu Trivedi. On the generalization of equivariance and convolution in neural networks to the action of compact groups In International Conference Machine Learning, pp. 2747-2755. PMLR, 2018.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint arXiv:1801 120000.0214,,.... 2018.
Andreas Loukas. What graph neural networks cannot learn: depth width. In ICLR, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In NeurlPS, 2019a.
Haggai Maron, Heli HamuH Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In ICI.R, 2019h.
12

---

Published as a conference paper at ICLR 2022
Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In Interaational Conference on Machine Learning, pp.
PMLR, 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop. 2020a.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 21824- 21840. Curran Associates, Inc., 2020b.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
Marion Neumann, Roman Garnett, Christian Bauckhage, and Kristian Kersting. Propagation ker- nels: efficient graph kernels from propagated information. Machine Learning, 102(2):209-245, 2016.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks gener- alization. arXiv preprint arXiv:2006.0753 2020.
Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning point sets for 3d classification and segmentation. In Proceedingy of the IEEE conference on computer vision and pattern recognition, pp. 652-660, 2017.
Gaurav Rattan and Tim Seppelt. Weisfeiler-lema graph spectra, and random walks. arXiv preprint arXiv:2103.02972, 2021.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Deep learning with sets and point clouds. arXiv preprint arXiv:1611.04500 2016.
Siamak Ravanbakhsh, Jeff Schneider, and Barnabas Poczos. Equivariance through parameter- sharing. In International Conference Machine Learning, pp. 2892 2901. PMLR, 2017.
Yu Rong.
Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. In ICASSP 2021-2021 IEEE International Conference Acousties, Speech and Signal Processing (ICASSP), pp. 8523-8527. IEEE, 2021.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 313-34331111 SIAM, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80) 2008.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borgwardt. Ef-
ficient graphlet kernels for large graph comparison. In AISTAT, pp. 488-495, 2009.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lehman graph kernels. JMLR, 12(Sep):2539-25611 201
13

---

Published as a conference paper at ICLR 2022
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
Alessandro Sperduti. Encoding labeled graphs by labeling RAAM. In NIPS, 1994.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Trans. Neural Networks, 8(3)714-735, 1997.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node em- beddings and structural graph representations. In International Conference Learning Repre- sentations, 2020.
Teague Sterling and John J. Irwin. ZINC 15 ligand discovery for everyone. Journal of Chemical Information and Modeling, (5(11):2322-2337, 11 2015. doi: 11122//ac.jcim55500555.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher graph neural networks: Possibility and impossibility results. arXiv preprint arXi4:00/2.03174 2020.
Erik Henning Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism- graph neural nets. In Advances in Neural Information Processing Systems, volume 34, 2021.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. In NeurIPS, 2020.
Renhao Wang, Marjan Albooyeh, and Siamak Ravanbakhsh. Equivariant networks for hicrarchical structures. NeurlPS, 2020.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Fengli Xu, Quanming Yao, Pan Hui, and Yong Li. Graph neural network with automorphic equiva- Ience filters. arXiv preprint arXiv:201 1,04218, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462. PMLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. Advances in Neural Information Processing Systems, 33, 2020.
Jiaxuan You, Jonathan M
Rex Ying, and Jure Leskovec. Identity graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. In NeurlPS, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in Neural Information Processing Systems, 30, 2017.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. AAAI, 2018
14

---

Published as a conference paper at ICLR 2022
A BACKGROUND: LEARNING ON SETS AND GRAPHS
In this section we present a brief introduction to GNNs, equivariance and set learning.
Graph neural networks. GNNs are type of neural networks that process graphs as input. Their
roots can be traced back to the field of computational chemistry Kireev (1995); BBskin et al. (1997)
and the pioneering works of [Sperduti (1994); Goller & Kuchler (1996); Sperduti & Starita (997);
Gori et al. )2005): [Scarselli et al.J (2008). In recent years, GNNs have become a major research
direction and used in many application fields such as social network analysis (Fan et al. 2019),
2020; Cai et al., (021] 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. [013 Bronstein et al.. 2017) and equivariance (Maron al. 2019b Bronstein et al. (202)). Message-passingg neural networks (MPNNss) (Gilmer et al. 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 sta- tionary 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):
molecular biology (Jin et al. 2018), physics (Shlomi et al.
2017
5.. W/ + W Σ
2 +b
Here, 2y E Rele is the feature associated with a node v after after applying the I-th layer, W; E means that the nodes are adjacent.
Rd xd; 1, , E Rdd are the learnable parameters, and
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); y; Xu et al. (2019) analyzed the expressive power of MPNNN 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 polynomial time hierarchy of graph isomorphism tests: for k >> k', k-WL is strictly more powerful than --WL (Cail ct al. 1992). but requires more time and space complexity which is exponential in k. These works inspired plethora of novel GNNs with improved expressive power (Maron et al. 2201 9a. Bouritsas cct al. 2022 Bodnar et al.) 2021b a Vignac et al. 2020 Murphy et al. 2019 Chen ct 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 + is H-invariant if f(h x)- f()) for all x V. h E H. Similarly, function f V + W is equivariant if the function commutes with the group action, namely f(h x)) = h f(x) for all x E V, h E H. Constructing invariant and equivariant learning models has become central design paradigm in machine learning, see e.g., Cohen & Welling (2016); RRavanbakhsh et al. ): Kondor & Trivedi (0188; Esteves et al.] (2018). In particular, graphs typically do not have canonical ordering of nodes, forcing GNN layers to be permutation-equivarine
special case of graphs with edges, and learning on set-structured data has recently become an important topic with applications such as computer graphies and vision dealing with 3D point clouds (Qi et al. 2017). A set of n items can be encoded in an n x 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 Zaherr et al. (017);; [Ravanbakhsh et al. (2016); Qi et al.) (2017) were the first to suggest universal architectures for set data. They are based on element- functions and global pooling operations. For example, a Deep Sets layer takes the form
Deep learning on Sets. Sets can be considered
x = Wix!
+ W
+-1
b'
(4)
Here, of is the feature of the i-th set element after applying layer t. Alternatively, this layer can be described as message passing layer on complete graph with Equation 3
15

---

Published as a conference paper at ICLR 2022
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 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 replacing the unconstrained fully-connected matrices W, in the equation above with corresponding linear equivariant layers. like convolutions in the case of images. We observe that when W2 = O, we obtain a simple Siamese network. Importantly, the paper shows that when W22 & O, the network exhibits a greater expressive power. Intuitively this is due its enhanced information -harring abilities within the set.
B RELATION TO PREVIOUS WORKS
Processing subgraphs for graph learning. Our approach is related to multiple techniques in graph learning. Introduced for semi- remi-supervised classifassiii tasks, DropEdge (Rong et al. 2019) can be considered as a stochastic version of the ED policy that processes one single edge-deleted subgraph a time. Ego-GNNs (Sandfelder al. 2021) resemble our EGO policy, as messages 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. 202T) 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 al. 2020) learn functions over recursively-defined node-deleted ego-nets with augmented features, which allows for high expressive power for counting substructures and com- puting other local functions. FactorGCN (Yang et al., 2020) is model that disentangles relations in graph data by learning subgraphs containing edges that capture latent relationships. The graph auto- morphic 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 sam- ples 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.
The inability of WL to disambiguate even simple graph pairs has re- cently sparked particular interest in provably expressive GNNs. A fruitful streamline of works (Mor- ris et al. 2019 2020b Kondor et al. 2018: Maron et al. 201 9b/ 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 h 2 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 expres- siveness 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). AT- though 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-perfore in generalising outside of training data.
Provably expressive GNNs.
A family of works focused on building local and equivariant provably powerful architectures and, for this reason, is especially related for the use of (higher-order) structural information. Structural node identifiers obtained as sub- graph isomorphism counting were introduced in Bouritsas et al. (2022). Alternatively, (Srinivasan & Ribeiro (2020); de Haan et al. (2020); Thiede et al. (022 I) argue for the use the automorphism group of edges and substructures obtain more expressive representations. These features cannot be computed by standard MPNNs (Chen et al. (0200) for substructures different than trees and they can provably enhance the expressiveness of standard MPNNs while retaining their local inductive bias. BBodnrr 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 do- main, where the importance of specific substructures is not well understood and their number may rapidly grow.
approach. Of particular relevance are works which argued
16

---

Published as a conference paper at ICLR 2022
Our framework, on the contrary, attains locality, equivariance and provable expressiveness with scal- able and non-domain specific policies. Any of the ED. ND, and EGO(+) policies make our approach strictly more powerful than standard MPNNS (see Section[D). and the generation of the bags is com- putationally tractable, independently of the graph distribution at hand (more in Section F). Either way, we remark that the aforementioned works are compatible with our overall framework, and can be employed to parameterize the Esabgraphs 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 an automated way. Bouritsas et al. (202I) propose a model that can be trained to partition graphs into substructures for lossless compression; Chen al. (02T) show how the model introduced in Chen et al. (2020) can achieve competitive results while retaining interpretability by the detection of the graph substructures em- ployed by such model make its decisions. These approaches may potentially be used to design more advanced subgraph selection policies.
B.1 COMPARISON TO RECONSTRUCTION GNNS
Contemporancous work by Cotta al. (2021) takes motivation from the node reconstruction conjec- ture (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., (021)) is ex- actly 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,Cotte et al. (2021) use a DS-GNN architecture, while we perform a rigorous and more specific analysis of equivariance, and argue in favor of 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- OSNGNN is strictly stronger than DS-GNN for certain policies (see Proposition D). Moreover, the tested settings, so this theoretical benefit leads to practical gains.
OSS-GNN achieves better empirical results than DS-GNN in most of
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 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 ZINCI26 2K 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 (c.g. as in Proposition B) not just for node-deletion policies. Second, we consider higher- order graph encoders in our general framework, whereas Cotta et al. (202T) 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 Weisfeiler- Lehman test DL 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 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 al. (202T).
Basic motivation: The paper of Cotta et al. (2021) is mainly motivated by the Reconstruction Conjecture in graph theory. In contrast, our paper 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.
17

---

Published as a conference paper at ICLR 2022
Table 4: TUDatasets. The top three are highlighted by First, Second, Third. Gray background indicates that ESAN outperforms the base encoder.
Datasel
MUTAG
PTC
PROTEINS
NCT1
NCT109
IMDB-B
IMDB-M
RWK (Girmer et al 3onn
79.24:211
55.94003
99.620.11
>3 days
NIA
NIA
NIA
81.41:77
55.74.0.5
7144:0.3
60.520.3
624203
PK Noumine ml
76.0:22.7
99.54:24
73.7:077
82.50055
NIA
NIA
NIA
WL
KERNEL Siarrashiie et 1
90,4:25.7
59.9:1-133
75.0::3.1
$6.0
NIA
73.8::3.9
50.92:388
DCNN
Alword & Towsley 2016
N/A
N/A
61.31:1.6
$6.6110
NIA
49.11:14
33.521..4
DGCNN
85.8:1-18
58.6::2..5
75.5
74,4::055
NIA
70.0:0099
47
(Mayi bulku
728-15
7204:5.5
PPCNNE
Marome: Fi k
90.6:287
667.666
77.2::477
83.211
82.2114
73015588
30.52:6
NATURAL GN loda
2020
19
6681111
71.71:1.0
1.44
NIA
73.54:2.0
1.
Bourrisas et
92.24.55
NIA
SIN Kidine 2i II 2071
N/A
N/A
76.413.33
82.722.11
NIA
7561:122
$2.42299
CIN Bontar 20210
92.76611
68.24:56
77.0
836:114
84.02166
75.6
52.753.1
GIN (X ct al. 2019)
89.4+556
64.647
7622228
82.7
82.2
75.14:5.1
$23##28
GIN ID-GNN You 3021
90.4454
67,244.3
75.422.77
82.6216
82.1
760227
$2.72422
DaorEoca Rong et
2019)
91.0
64.542.6
73.5
82.02266
82.2
76.5 3.3
$2.8 288
DS-GNN (GIN) (ED)
89.9:4337
66.0::7.2
76.8
8334-25
8..0-112
96.1
$2.9
DS-GNN (GIN) (ND)
89.4:1488
66:377
1:46
2.
824=1.3
75.4
2..74200
DS-GNN (GIN) (EGO)
89.944-55
68.64-5.8
D8-GNN (GIN) (RGO+)
01.0-2488
68.74 68.747.
76.71:44
820214
80.12099
77.1
23.2228
DS-GNN (GIN) (ED)
90.5458
66.0::64
77.02:3.2
82.8:111
82.9
76.22 24224
$2.9228
DS-GNN (GIN) (ND)
90.0::00
66.928.77
77.3
83.0
82.3-207
75.51:2.2
22.4229
DS-GNN (GIN) (EGO)
91.0:553
68447744
76.44:444
81.51:11
796621.
76.622
$2.622.8
DS-GNN (GIN) (EGO+)
90.5144.7
68.11788
76.61:400
$2.02:22
804:1.44
76.8:22.7
23.3
D88-GNN (GIN)
01.0114
666:7.3
75.4::455
83.422
82.8
76.32:33
$3.5214
DSS-GNN (GIN) (ND)
91.0:1355
66.34.9
76.1 1:344
83.6
83.1=0088
76.1
13.3
DSS-GNN (GIN) (EGO)
91.0+4477
68.24:5.8
76.7+:4.1
83.6+1
82.5=116
76.5+::1.8
53.3+33.1
D88-GNN (GIN) (EG0+)
91.1470
69.216.5
83.218
82.821.2
77.11:.00
$3.222.4
GRAPHCONY Monis al. 2019
90.54:46
64.9
73.9:6.11
82.4
81.7=110
76.12:39
$3.1::9
GRAPECONV ID-GNN You 2021
89.4:14.1
65.4477.1
719:44.6
8344:2.4
82.9
96.1
53.7+3.3
RNI (bbbodd 2020
91,0:14.9
61.3:66.1
73.34:3.3
82.1
81.7=100
75.5::3.3
$3.1
DS-GNN (GRAPHCONY) (ED)
90.4:24.1
65.74:52
7631::522
82.7119
824
75.3422.3
$3.5223
DS-GNN (GRAPHCONV)
66.64-7.8
75.74-299
D8-GNN (CRAPHCoNV) (BGO)
89.4
666-66.
76.71554
81.3-119
79.6220
76.6::4.0
1..1
DS-GNN (GRAPECONV) (EGO+)
90.4
67.44.4.7
76.8
8288
80.6
76.0:166
$3.3422444
(GRAPBCONV) (ED)
90.0:14.3
66.0:77.1
76.61:3.7
$3.0
82.6:111
76.3433.11
13
DS-GNN (GRAPHCoSV)
90.4++4.0
66.04--.00
76.5 +-4.8
83.0+:23
62.7=:14
75.1
$3.7+2.11
DS-GNN (GRAPUCONV) (EGO)
90.0
67895599
76.8
11.9
80.-20
76.4:3322
$3.1222
DS-GNN (GRAPUÇONY) (RGG+)
91.5453
67.044.555
76.54.0
8.001.2
80.51177
7644227
$3.3226
D8S.GNN (GRAPHCONV)
91.0-588
D88-GNN (GRAPHCONV) (ND)
90.6:25.22
65 65.4:55.8
76.11.500
13.711777
824213
75 11:3.2
$3.1226
DSS-GNN (GRAPHCONY) (EGO)
91.5:14.9
68.01:6.1
76.61:4.6
83.5:1.1
62.5=1.6
76.3::3366
$3.1
DSS.GNN (GRAPHCONV) (EGO+)
92.0---..0
61.14-577
71.0
76.6-:288
C EXPERIMENTS: FURTHER DETAILS AND DISCUSSION
C.I DATASETS AND MODELS COMPARISON
We conducted experiments on thirteen graph classification datasets originating from five data repos-
itories: (1) RNI (Abboud al. 2020) and CSL (Murphy et al.) 2019 Dwivedi al. 2020) (mea- suring expressive power) (2) TUD repository (social network analysis and bioinformatics (Morris) 2020a) (3) Open Graph Benchmark (molecules) (Hu et al. 2020) and (4) ZINC12K (molecules) (Dwivedi et al. 2020). These datasets are diverse on a number of important levels, including the number graphs 1127- existence of input node and edge features, and sparsity.
We compared our approach to a wide range of methods, including maximally expressive MPNNS (Xu et al. 2019 Morris et al. (019). We particularly focused on more expressive GNNs Maron
et al. [019a]] de Haan et al. 2020) Bouritsas et al., 2022 Abboud et al.] 2020 Bodnar et al. 202 lb
Abboud et al. 2020) and also compared to DropEdge (Rong et al. 2019) and ID-GNN You et al,
2021 that share some similarity with our ED and EGO policies
We experimented with both DSS-GNN and DS-GNN on all the datasets and used popular MPNN-
type GNNs base encoders: GIN (Xu et al. 2019), GraphConv (Morris et al. 2019). and GCN
We implemented the fast version of ID-GNN with 10 dimensional augmented node features.
18

---

Published as a conference paper at ICLR 2022
Table Results for OGBG-MOLHIV and OGBG-MOLTOX21. Gray background indicates that ESAN outperforms the base encoder. Note that ESAN achieves much higher training accuracies with re- spect to base graph encoders.
LUBG-MMLHIV ROC-AUC (%)
OGBG-MOLTOX21 ROC-AUC (%)
Method
Training
Training
Validation
GCN Kipf & Welling, 2017
88.65 19
82.04 1.4
76.06 0.97
92.064 1881
79.04
75.29
DS-GNN (GCN) (ED)
86.25=2.777
82.36=0.75
74.70:2:1. 1.94
90.97++1.70
80.05:20.59
74.86+00.2
DS-GNN (GCN) (ND)
86.82:1..26
81.90-0082
2.448
89.18110.99
80.56.10.61
75.79
DS-GNN (GCN) (EGO)
91.91
03.51
74.00=22..38
89.29 1.64
80.48:10.52
75.41
DS-GNN (GCN) (EGO+)
3.58
73.54::2.58
90.24-1:..20
80.77::0.51
0.974
DSS-GNN (GCN) (ED)
99.52:1:0.34
1 1.10
76.00 1.41
94.601 1.10
$0.05-0..40
75.34:00.69
DSS-GNN (GCN) (ND)
97.40:1:.55
82,88 1
75.17::1.33
93.82:1:244
81.22:10.52
05.56:1...99
DSS-GNN (GCN) (EGO)
98.56=t:2.08
84.34=1 1.02
76.16 1.02
93.06++2.54
81.51=00443
76.14+00.53
DSS-GNN (GCN) (BGO+)
98.47::22220
84.45=0.65
76.50:t 1.38
91.60-1:188 1.81
81.55-10.63
76.29
Xu
2..54
82.32:10.90
93.06:10.88
78.32:1:048
74.91
DS-GNN (GIN) (ED)
3.550
83.32
2..47:12.12
92.18111.57
78.98
75.12:10.50
DS-GNN (GIN) (ND)
3,270
83.21 0.87
76.19:10.96
91.23:+2.115
79.61=00.59
75.34++1122 1.21
DS-GNN (GIN) (EGO)
93.43-22.17
84,28=0.90
78.00= 1.42
92.08+1.79
81.28=0.54
76.22=00.22
DS-GNN (GIN) (EGO+)
90.53
84.63=0083
77.40 2.19
90.07 1.65
81.29920.57
76.39 14.39.2.111 1.18
(GIN) (ED)
31.6943.477
83.33=0098
77,03
95.85422.08
80.83:0.41
76.71=0.67
DSS-GNN (GIN) (ND)
90.71 4.228
83.62=1122 1.2001200
76.63 1.52
96,90+ 1.45
81.22-00.23
77.21+20.70
DSS-GNN (GIN) (EGO)
97.05
85.72 1.21
77.19 1.27
95.58.1 1.61
81 01.80:20:20
77.4514411
(GIN) (EGO+)
76.78.1
96.06.1..66
81.82100.11
0..95
Table 6: Results for RNI datasets. Gray background indicates that ESAN outperforms the base coder. DS/DSS-GNN can boost the performance of both base graph encoders, GIN and GraphConv, from random perfect.
EXP
CEXP
GIN Xu et al.
2019
51.1=2.1
70.2:44.1
GIN ID-GNN You al.
2021
100=0.0
100::0.00
(GIN) (ED/ND/EGO/EGO))
DSS-GNN (GIN) (ED/ND/GGO/EGO+)
100=0.0
100::0.0
GRAPHCONY Morris al.
2019
50.3.12.6
72.91...6
You
2021
100=0.0
100::0.0
DS-GNN (GRAPUCONY) (ED/ND/EGO/EGO+)
100=0.0
100::0.00
DSS-GNN (GRApHCOnv) (ED/NDEGOO/GGH+)
100=0.0
100::0.0
Kipf & Welling 2017) using all four selection policies (ND, ED, EGO, and EGO+). We used max for aggregating the adjacency matrices for DSS-GNN.
C.2 FURTHER EXPERIMENTAL DETAILS
We implemented our approach using the PyG framework (Fey Lenssen 2019) and ran the exper- iments 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 discussed in the subsections below.
C.2.1 TUDATASETS
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 de- cayed by a factor of 0.5 every 50 epochs. The training is stopped after 350 epochs. As for DS-GNN, implemented Raubgraphs with summation with a two-layer DeepSets with final mean readout; layers are in the form of Equation 44) In DSS- GNN, considered the mean aggregator for the feature matrix and used the adjacency matrix of
node features. while module Evers is parameterized
19

---

Published as a conference paper at ICLR 2022
the original graph. We implemented Rsubgraphs by averaging node representations each subgraph; Esess is either a two-layer DeepSets in the form of Equation ( with final mean readout, or a simple averaging of subgraphs representations (the choice is driven by hyper parameter tuning). We con- sidered 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 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 (Toffe & Szegedy 2013). As in Xu et al. 2019). ) we tuned the hatch size in {32, 128), }. the embedding dimension of the MLPs in {16, 32} and the initial learning rate in {0.01, 0.0013. We tuned the embedding dimension of the DeepSets layers of Esets in (32, 64).
GraphConv. We considered the same architecture in Morris et al. (2019), with 3 GNN layers and embedding dimension of 64. We added batch normalization (loffe & Szegedy 2015) after each layer in all models, as we noticed gain in performances. For 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 Drope- dge (Rong et al.) 2019), RNI (Abboud et al., 2020) and ID-GNN (You et al. (02I). 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 fea- tures, due the good performances presented in the original paper. Table 4 shows the full results on the TUDatasets, including a comparison to the graph kernels (Gärtner et al. 2003 Shervashidze jet al.) 2009 2011 Neumann al. 2016). As discussed in the main paper, to guarantee least the expressive power of the basic graph encoder used for DS-GNN one can add the original graph G to ST for any policy π, obtaining the augmented version î. We included results for our DS-GNN on the augmented policies in the same table. As can be seen, DS-GNN obtains very similar results for any policy and corresponding augmented version.
C.2.2 OGB DATASETS
We used the evaluation procedure proposed in|Hu 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 Rubgraphs as either averaging or summation of node representations, the choice is made based on validation ROC- AUC. Esas is two-layer DeepSets (Equation (4)) with final mean readout. Its hidden dimension 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 Rsubgrahs applies averaging over node representations and, in turn, Exers averages the obtained subgraph encodings. Table shows the full results on the OGB datasets, reporting training, validation and test performances.
C.2.3 RNI DATASETS
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 em- bedding dimension that fixed to 32. Table the results on the RNI datasets.
C.2.4 CSL
We tuned the batch size in {8, 16), the embedding dimension of the MLPs in {32, 64) the initial learning rate in (0.01, 0.001} and number of layers in {4, Interestingly, we find that, when employing the ND selection policy, DS-GNN with less than 5 layers not differentiate CSL(41, 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. Similarily, ego networks of CST and
20

---

Published as a conference paper at ICLR 2022
Table Results of our stochastic sampling approach on TUDatasets, where each graph sees 100%, 50%, 20%, 5% of the subgraphs in the selected policy (100% corresponds to full bags). Gray background indicates that ESAN outperforms the base encoder.
MUTAG
PTC
PROTEINS
NCI
NC1109
IMD8-8
IMDB-M
RDT-B
Xu et 2
2019
99,44-56
K2741.7
52.24166
75.145.1
52334-288
92.4225
100%
80.9:3.7
66.027
76.844
833222
761466
52.922.4
NIA
DS-GNN (GIN) (ED)
50%
20%
90.5250
66.3253
67.7-5.9
77:11:455
830+188
136:119
819211
330=1a
76.21:24
763322
529422.6
$3.2424
NIA
NIA
5%
68.82665
65.727.3
76.822466
1.8
81.72118
76.222.8
53.34224
92.-11
100%
49
66.317.0
77.1
K38.124
$24.113
75.41:2
$2.7.120
NIA
DS-GNN (GIN) (ND)
50%
58. 4.3
66.21668
76.81:52
13.12:15
62.72:16
75.5:22
$2.9:12.2
NIA
20%
58. 58.925.5
66.0=66.
77.242.9
82.7
75.5
52.5422.9
N/A
5%
48.31445
66.31.
77.3.14.1
83.212.
62.8.0077
15.1139
$2.11188
92.4 1.2
100%
9.946.5
68.6
76.745588
814+00.7
19.511
76.122
52.642288
N/A
DS-GNN (GIN) (EGO)
20%
50%
76.94-4.6
81.7-114
78.3.2.11
80.4-08
76.3-22.3
76.9 1.26
52.441177
NIA
56.87711
67.7=866
76.94:44
77.0199
1400116
76.933
52.34228
590=2.
100%
91.01:88
68.7170
76.71444
12.0114
8031009
532:2288
NIA
DS-GNN (GIN) (EGO+)
50%
54
67.8=84
77.54:47
135-111
8042111
76443.1
NIA
20%
91.5=60
66.3=80
77.14:44
1.
72.02211
76.2422
$2.6116
NIA
5%
51,45511
67.7+644
77,24+422
7.22+17
75.2+
77.242.3
53.2439
291=23
100%
91.0-4488
66.6-773
75.8++-4
K34:25
S1N:2099
76.84-4.3
53.4434
NIA
DSS-GNN (GIN) (ED)
20%
50%
90,4155
90.5.15.1
66.61.6
66.31.6.7
15.9
76.31138
8M11117
K30.12.4
82.9119
$2..1155
76.5133
76.1
$2.9118
$3.7.12.4
NIA
NIA
60.42:62
66.7270
83222.11
13.3
77.22:22
$3.3114
100%
91.02:35
66.350
76.12:34
836215
831
76.1222
$333119
N/A
DSS-GNN (GIN) (ND)
50%
$8.466.1
65.1243
76.4933
831+23
1.
75.64:24
53.1226
NIA
20%
76.2+:4
N324222
75
53544-10
NIA
5%
19.91:52
67.21:70
77.0
828
76.3-14.66
53.1428
92.7 13
68.21.58
12.1115
DSS-GNN (GIN) (EGO)
20%
50%
91.52555
91.52248
66. 5..9
8177
77. 1::44
77.31:35
835118
13
8300008
76.313322
76.91:000
$2.81111
$29111
NIA
MIA
5%
90.455
77.1
76.612443
83.322.0
13
77.2
$2.9224
928=16
100%
91.1=:00
09.226.5
75.95
13
77.1331
532222
N/A
DSS-GNN (GIN) (EGO+)
20%
50%
90.51.52
91.0-:588
66.61:72
66.9-744
77.4-445
77.133300
837.113
137+114
$29.1111
77.71344
7644-4.11
$3.2.19
5304-1.11
NIA
NIA
$9.41.52
67.21...1
76.8..3.1
8.3114
83.2.113
$3.1.166
CSL(41, 12) depth 2 and 3 are isomorphic. Therefore, when working with EGO and EGO+ policies, we need depth 4 to distinguish those two classes.
C.2.5 ZINCI2K
Throughout our experimentation, we used the same train, validation and test splits in Dwivedi et al. 2020), whose prescribed overall optimization and benchmarking setup verbatim follow. We used Mean Absolute Error (MAF) 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) the time of the early stopping. All models feature 4 GNN layers, as common this benchmark. Importantly, in order to comply with the 100k parameter budget advocated in Dwivedi et al. (2020), we set the embedding dimension of all GNN modules employed our models to 64. For the EGO and EGO policies we used depth 3 ego-nets centered at each node.
DS-GNN implements Rsubgraphs as averaging of node representations while Esets is a two-layer in- variant DeepSets (Zaheer et al. 2017) with final mean readout. Specifically, we tune e and p to either be both a single layer or a 2-layers MLP, with dimensions fixed to 96. As for DSS- DNN-GNN, used the mean aggregator for the feature matrix and used the adjacency matrix of the original graph. Module Rauhgraphs applies averaging over node representations and, in turn, Exes averages the obtained subgraph encodings.
21

---

Published as a conference paper at ICLR 2022
Table 8: Results of our stochastic sampling approach OGB and RNI datasets, where each graph sees 100%, 50%, 20%, 5% of the subgraphs in the selected policy. Gray background indicates that ESAN outperforms the base encoder.
NGRG-MOI FIV
0CRG-MOUTOX3]
EXP
CEXP
auetall 2019
15.58
74.91:10.11
51.24::211
70.24:4.11
100%
76433-2.112
75.1240.50
100400
100400
DS-GNN (GIN) (ED)
20%
50%
76.57::14 188
74,39+0071
75.6720.89
100000
99920.2
5%
77,82-t 1,:00.0000
76.39
99.7004
99.9-0.2
100%
76. 16:19.9
15.34
1000000
100:0000
DS-GNN (GIN) (ND)
20%
50%
77.65:0.844
77.23 1.32
75.66:10.46
74.82:1000 1.05
100::0.0
1001:0.0
99:0::22
99.91:022
5%
78.26 1.02
76.51 1.04
97.24-111
99.8:-088
100
78:00:114
76222:0.62
100+0.0
100+000
DS-GNN (GIN) (EGO)
50%
76.52-40.72
75.98:40.72
100
999950.2
20%
77 177494:11 1.32
75.88:0..00
99 94:02
75.90
74.95:0.554
93.5
83.433
100%
77,40:22.19
76 76.3911.11 1.18
1001:0.0
1001:0.0
(GIN) (EGO+)
20%
50%
25,92:1: 1.59
75.69
75.84:10.63
99.71:04
97.01:14
92.-4-02
5%
73,46:111 1,80
75.08:10.99 96
93.712.77
63.212..6
100%
77:05-1: 1.81
7677120067
1000000
10000000
DSS-GNN (GIN) (ED)
20%
50%
77. 50. 1.82
76.31
0.84
100+0000
100+0.0
1000000
100000
.44 76.71
76.4420.544
09.00
100:000
76.63
11:21:10070
1001:00
1001:00
DSS-GNN (GIN) (ND)
20%
50%
76.2 26.233--1.8 1.48
96-1: 1.71
77.07 1.03
76.92:10.94
1001:000
1000:00.0
100
1001:00
5%
76.74:::.67 1.67
76.54:10.86
97.71:
99.91:022
100%
77.19:1.27
77.45#00.41
100+:000
100+:003
DSS-GNN (GIN) (EGO)
50%
76.47:2
76.37::1.00
1000000
100
20%
76.41
77.47:40.65
100+0.0
100+0.0
76.38 1.48
77.40:
99/24-0.6
100-00000
100%
76.78 1.55
17.95:1:0:40
1001:0.0
100:::0:
DSS-GNN (GIN) (EGO+)
20%
50%
26.33--
70.45--00881 76.88
76. 06.92:10.93
100+00.0
1001:0.0
100--0.0
1001:0.0
76.70:10.56
99.5:1:0.6
Table 9: Number of parameters of the best models
MUTAG
PTC
PROTEINS
NCI1
NC1109
IMDB-B
IMDB-M
GIN (X al.
2019
8296 18625
8692 5601
8164 10865
9286 47137
9319 20481
39305
40091
ESAN (GEN)
33729
26833
C.3 ADDITIONAL EXPERIMENTS
C.3.1 STOCHASTIC SAMPLING RESULTS
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 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 7 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 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 also reports the performances sampling policies on the CSL dataset. Although isomorphic graphs may be mapped to different representations and possibly different classes due to the randomness introduced by the sampling procedure, 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
the OGB datasets. We additionally experimented with stochastic
22

---

Published as a conference paper at ICLR 2022
Table 10: Results with larger number of trainable weights
MUTAG
PROTEINS
NC11
NC1109
GIN (Xu al.
2019)
89.44556
76.242288 75.81:5.5
82.7+117 82.91.8
82.2+:166
BIG GIN
89.914499
81.61:155
ESAN (GIN)
91.1
77.14:4.6
83.842.
83.1
Table 11: Timing comparison per epoch on RTX 2080 GPU. Time taken for single epoch with batch size 32 on the NCII dataset and with batch size 128 on the ZINC dataset. All values are in seconds.
BASELINE
100% SUBGRAPHS
20% SUBGRAPHS
BASELINE
100% SUBGRAPHS
GIN et 2019
1.00=0.55
1.45:0011
DS-GNN (GIN) (ED)
2.07
1.73+0000
3.56:20.03
DS-GNN (GIN) (ND)
0.08
1.71:00001
3.42-10.02
DS-GNN (GIN) (EGO)
1.96.10.01
1.72.10.01
3.02.10.04
DS-GNN (GIN) (EGO+)
2.01:1:.02
1.73:0001
3.09110.04
DSS-GNN (GIN) (ED)
3.26.10.07
2.9410.001
4.20.10.00
DSS-GNN (GIN) (ND)
3.19::0.07
2.91+:0.02
4, 12:10.003
DSS-GNN (GIN) (EGO)
3.14:00.4
2.79++0.02
3.63:200.02
DSS-GNN (GIN) (EGO+)
3.19::0.03
2.90=:0.01
3.69
still mapped closely in the embedding space, this allowing our models to easily predict the same isomorphism class for all of them.
C.3.2 SIZE THE MODELS
As already discussed, on TUDatasets, our ESAN variants tend to outperform their base encoders in the majority of the cases. We made sure 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 trainable parameters of the best baseline model with that of our best ESAN configuration; numbers are reported in Table 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 way to approximately match the overall number of ESAN parameters. We dub these models "BIG-GIN". The results are reported in Table I0 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, NC1109) and only insignificantly better results the remaining ones (NCI1, MU- TAG). This demonstrates that, while a larger number of parameters tend to correlate with larger model capacity, does not necessarily correlate with generalization performance, which is what we are really interested in.
We finally refer readers to Table where we report the results obtained the ZINCI2K datasets. On this benchmark, all ESAN configurations significantly outperformed their GIN base encoder while being all compliant the 100k parameter budget.
C.3.3 TIMING
We focus our analysis on NCII 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 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
23

---

Published as a conference paper at ICLR 2022
to allow fair comparison. Results reported in Table I1 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-GR 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.
As can be seen in the table, our
Further timing experiments on 2IN confirmed the empirically tractable computational com- plexity of our approach: for a training epoch on 10k graphs, DS- DS-GNN required only between 3 and 3.5 seconds (depending on the policy), while DSS-GNT 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 IT]
C.4 DISCUSSION
Do our experimental results answer the research questions we raised at the beginning of Section 4 We discuss them in specific here below.
(I) Is our approach more expressive than the base graph encoders in practice? ESAN perfectly solves the RNI and CSL expressiveness benchmarks with variety of subgraph selection policies, while the base encoder (GIN) performs as a random guesser (see Table 6). These results provide a (strong) positive answer this question.
(2) Can our approach achieve better performance on real benchmarks? On real world graph datasets, ESAN has outperformed its hase encoder in most of its configurations. Superior perfor- mance has been recorded across benchmarks, independently of the choice of the base encoder and the subgraph selection policy. In particular, we found ESAN 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-ar 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
meth- ods (Bodnar et al. [221a]] Bouritsas et al. 2022 Beaini et al. (021). 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 some benchmarks (c.g., ND on PROTEINS for DS-GNN (GIN) and EGO(+) on ZINC), while they all seemed to perform equally well others (e.g.. on IMDB-N -M and on NCII 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 7 it emerges that, barring a few notable ex- ceptions, our subgraph sampling scheme has marginal no impact the overall performance of ESAN, even for drastic sampling rates. This is particularly evident over the IMDB-B -B and IMDB- M 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 T 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, NCII and N9 benchmarks, as well as the OGBG- MOLHIV 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 ten- dency for OSS-GNN to perform better than DS-GNN. This observation is more pronounced in cer- tain conditions and datasets, and on ZINC12K in particular (see Table 3. Another interesting
24

---

Published as a conference paper at ICLR 2022
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 subgraph sampling (see Table 7 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 the OGB datasets with GCN encoders (see Table 2 and Table 5). These advantages come at the cost of a slightly larger computational complexity, observed Table 11
When is the ESAN framework advantageous, in general? Given the above, we can conclude that applying our approach real world datasets generally beneficial whenever some additional com- putational 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, results indicate that the application of ESAN is recommended in those cases where the task hand may require expressive power beyond 1-WL. There some empirical evi- dence that certain molecular benchmarks fall in this category; our results on the ZINC122 2K dataset validate this hypothesis by showing that our approach strongly outperforms GIN, while performing best amongst all provably expressive, domain agnostic GNNs (see Table 33. Finally, ESAN is pecially suitable in those cases where no domain knowledge is available about graph substructures relevant the task being solved. As requires little pre-engineering. our method represents valid, flexible and provably expressive approach in these conditions.
We aware of any particular scenario where the application of ESAN has proved be con- sistently 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.
25

---

Published as a conference paper at ICLR 2022
D WL VARIANTS AND PROOFS FOR SECTION 3.2
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.
D.1 PRELIMINARIES
Let us first introduce some notation and required definitions. We begin with the definition vertex coloring (Rattan & Seppelt, 2021).
Algorithm 1 WL Test
Require: Graphs G', G², initial v v + L. (optional)
Definition 1 (Vertex coloring). A vertex coloring a function mapping a graph and one of its nodes "color" from a fixed color palette.
1: 0, converged
false
2: for r E G UGUG do
c + čor ((v)
if provided
4: o + fch G
Generally, we can define a vertex color-
5: C² + (cd G
ing a function V + C, (G,v) + C where V the set of all possible
6: while dg = c/2 and not converged do
7:
for i {1, 2 do
tuples of the form (G, v) with G (V. E) E U (the set of all finite graphs)
8:
for u E G do
9:
N {ct TwwE (EN
write (G, v) + Co and we sometimes drop the superscript G whenever clear from the context. In order to design and compare vertex colorings, it is important intro- duce the notion of refinement.
and E V. Concretely &
10:
c + HASH(C
11:
1+ [ct GE &
12:
if d E GJ c
1+1 and cgra C Ga then
13:
conterged true
14:
t
15: if
c/1 # c02 then 16: return non-isomorphic
Definition 2 (Vertex color refinement).
Let c, d be two vertex colorings. We say that d refines c (or is refine-
17: else
18: return possibly isomorphic
ment of c) when for all graphs G ,EG, H,H-- (VH, EHt) and all ver- tices VG u E VH we have that do dll
(VG (VG,EG),
c c. We write
When working with a specific graph pair G G2, G², we write d Ea ga when for all ya' and all yo² if dG = ad then & c
The 1-WL test, sometimes known "naïve vertex refinement" (and sometimes simply as "WL" in this manuscript) an efficient heuristic test (non-) "ssmoorhmmm between graphs. We report the related pseudocode in Algorithm
The algorithm represents graph with the multiset (or histogram) of colors associated with its nodes. colors naturally induce partitioning of the nodes into color classes, in the sense that two nodes belong the same partition if and only if they are equally colored. We denote with (-)( the partition to which node belongs to, according to coloring Starting from an initial vertex coloring, the algorithm iterates rounds whereby the node partitioning gets finer and finer. These rounds are referred to "refinement steps" since, if indicates the colorings computed by the WL algorithm, d+1 Ea.a c²:
Proposition 4. Let a graph and dg be the vertex coloring computed by WL. Then, Vt d+1 Eg. c..
Proof. For those nodes v, u in the vertex set of G such that c++1 = cf+1 we have HASH NO) HASH(e,, Nt) and, necessarily, ct ct due the injectivity of the HASH function.
The refinement is at convergence when the node partitioning is stable, that is, when does not vary across steps. This means that both t+1 Ea. et and et Eag d++1 hold. At convergence on both the
26

---

Published as a conference paper at ICLR 2022
two imput graphs, the test deems them non-isomorphic if assigned distinct multisets of node colors, and it is inconclusive otherwise.
We report the full DSS-WL test in Al-
gorithm - Let us first note that both
DSS-WL and DS-WL produce color re- finements at the level of each subgraph:
Algorithm 2 DSS-WL Test
Require: G G policy n, 6 u (optional)
Proposition 5. Let G be a graph, a be subgraph selection policy and G be the bag induced by π on G. Let d's be the ver- tex coloring computed by DSS-WL (DS- WL) over subgraph S E GG at round L. Then, 4S E G. vt > O, CS Es,s c's.
1: I + 0, converged + false
g' + T(G'), G ((²))
3: for Segi U do
4: forve do
5:
L t cor ((v) if provided
6: dg HASS
S})
Proof. In the case of WL, the asser- tion is immediately proved by observing that the algorithm performs independent WL refinements on each subgraph, and we know the standard WL procedure is indeed vertex refinement one.
S 7: cG + [c]] S E cG2 t E E
8: while cGI Cga and not converged do
9:
for i E [1,2] do
10:
for S G do
11:
for v E S do
12:
N t {cm.s w (eN
The assertion trivially holds also in the case of DSS-WL. Suppose there exist nodes v, u in the vertex set of
13:
C² < Cd, REg
14:
M + fC w WEN(U))
15:
4+1 t HASH(C No M.
such that c+1 S.S
.41 This
16:
(+1 + HASH( ( (EES))
implies HASH(C No.s, C,,M, M,)
17:
c < ( $ G
HASH(C u, st CL MD) and, neces-
18:
if AS E G¹ U dg E "g then
sarily, ct = ct s due to the injectivity of the HASH function.
19:
converged + true
20:
t t+
21: cg. * Cg² then
An immediate consequence of the above
22:
return non-isomorphic
considerations that, for vertex refine-
23: else
ment algorithms,, if two vertices belong
24: return possibly isomorphic
to distinct partitions at time step t, they will for any other & > t. This allows to conclude that both DSS-WL WL and DS-WL.
tests eventually terminate on any pair of (finite) input graphs.
Proposition 6. Let G G2 be any pair of finite graphs. There exists & < co such that the DSS-WL (DS- WLS test converges when run G G2 with any subgraph selection policy n.
Proof. Let GT, G2 be the bags induced by G²,G2, The two tests converge when, on all sub- graph, 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 + 1, the partitioning on a subgraph either as fine as, or finer than the one at iteration f. In other words, if Nt,s is the number of color classes at round i on subgraph S, we have that N.+1.5 2 Nr,s. At the same time, the value Nr.s, Vt > 0 is upper bounded by Ns co, i.e. the cardinality of the vertex set of S. This implies that the number of possible iter- ations before convergence must be upper-bounded by the value v = max; (Eee: Ns), which is, itself, finite.
The concept of vertex color refinement linked to the ability to distinguish between non non-isomorphic graphs. This is consequence of the following Lemma, whose proof is adapted from Bodnar et al. 2021b).
Lemma 2. Let c, V + be coloring functions implementing maps the form (A, a) + Ca. (A,a) d,, with (A, a) V such that A is set and E A. Let A, B be two sets such that
27

---

Published as a conference paper at ICLR 2022
(B..).(B.)) V and Ag. B& be multisets of colors defined as: As foala a AB, B fbbb BJ. E {c, d] Suppose that for all a, b E AUB, it holds that da = db = Ca Cb (we write d EA,B c). Then A. # B. Ad # Ba-
Proof. Ae * Be, we assume, w.L.ogg, g., that there is a color č which is represented more in A. than in Be. In other words, if we define the two sets:
A {a E Alc, c) fb
then AA B. These sets naturally define the partitioning:
== A=A-AA B
where === {a Alca # ej, B = 1b B Blc + 2). Let us now consider the multisets:
Aa = E
B ddobb B²B
First, each of these multisets have the same cardinality of the generating sets, that is [A [A [By] = |Be so, we necessarily have A # Bi Second, in view the fact that EA.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
Vx E B yE A B
+ Cy
and, due to d EA,B it must also hold that:
Vo E A FUB DE 7 U dg #
This implies that, if we define multisets
A adala A B2 ddobb B"B
then (A)U (Á u
B3 = Ø.
Now, have that Aa Us inequality holds due to color d appearing nA times in A and na times in Ba with nA > n-- Then, necessary condition for Aa Ba is that d appears n. ns times more in B2 than in A However, this condition cannot be met due to the disjointness of the multisets as shown above. L
B2 U B2 and Ai * B2- Say that, w.l.o.g.. this last
Definition 3. Let be vertex coloring. A readout map A : EV, + ol Cc VB) is function
representing graph G = (V, F.) with the multiset of node colors generated by e on V, or an injection thereaf (Φ).
Readout maps allow define algorithmic tests whereby two graphs are distinguished when their readout representations are distinct. This is the case of the WL test, where e is the identity function and e is the coloring induced by a certain number of rounds of the refinement procedure.
leverage colorings to test (non- Jiomoorhomoo between graphs: we
The following is an immediate consequence of Lemma 2
Let d be two vertex coloring functions such that d c. Let A.: Agg be readout maps associated with, respectively, verlex colorings c, d. Then, any two graphs distinguished by A are also distinguished by Ad- We say Ad refines A. and write Aa A
Corollary 2.
When Aa [ Ac then Aa is said to be at least as powerful as Aç. When the opposite holds, that is A E Ad, then the two have the same discriminative power and we write A, = Ad- On the contrary, if there exist pair of graphs distinguished by Aa which are indistinguishable by Ac, then we say Aa is strictly more powerful than A., and write A. C 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= fa (b,bm = B. For any function yp : D C it holds that ({A) = [(((a,) li ((bb:) (
28

---

Published as a conference paper at ICLR 2022
Proof. Let yp be any function (not necessarily injective). Suppose A B. but ( # ((B). There is some č such that w.l.o.g č appears more in ((A) than p(B). Defining
A { dA : (((A)= = E, dA E AD, B = dd <(d)) = e, dB E B
(5)
Thus, A * B because |A] > [3]. Note that A = AU Å for the complementary set A that is disjoint
from A defined Á = (d (dd + ē, E, AB. and similarly B = BUB.
Since |.A| > [8], we can choose
A such that the multiplicity #a(A) of d E A is greater
than # Further, since A = A U À and A is disjoint from A, we have that #a(A) = #a(A). Likewise, #a(B) #a(B). However, this is contradiction, because then
#a(A) # #a(B) #a(B).
(6)
so # B.
Lemma 4. Let A. B be two multisets with elements in D x ... x DE such that A
(aa)... a m 1: B = If (b),...., B Let A = {ay H B = (. Vjj = 1 1....,K k.
Then A B implies A = B³ for each j.
Proof. The above is proven by considering that, for any j. it is possible to construct the mapping sp DD x x... x D - DV such that (a....., ..))....))))).....)))) + ag. Then, (A) = A and o (B) = B'. At the same time, by Lemma A B implics & (A) = 4p (B) and thus A = BJ.
D.2 PROOFS FOR RESULTS IN SECTION 3.2
D.2.1 DSS-WL vs. DS-WL
We start by formally proving that DSS- DSS-WL is at least as expressive as DS-WL WL. We will require the following lemma, which describes refinement relation between DSS-WL and WL node colorings at the level of subgraphs.
Let x any subgraph selection policy, G G2 be any two graphs and DD, D2 the T- n-bags thereof. Let a!t), ((t)) generally refer to the coloring generated by t steps of. respectively, the WL and DSS- WL algorithms, with WL running independently on each subgraph. Then, for any t 0, VG (Ve, Ec), H =VH,, E④) E Dj U D2, b(t) EG.h a!!).
Lemma
Proof. We seek to show that Vo VG, u E VH, G.0 (G,0) = (.)))) us prove the lemma by induction on t.
G.(
H.(t) au
As usual, let
(Base case) The thesis trivially holds for 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.
(Inductive Step) Suppose that, for nodes v, u we have ((((++1) = b 11(++)) The equality can be rewritten HASH(bC G.(t) G...(t) clt), M! HASH H.(0) .N..(()) c.l MM!",, which im- plies the equality between each of the inputs to the HASH function. Importantly, this means NH.(()) The inductive hypothesis immediately gives us au (.(*) = a. (T,(t) and {a G.00% | e (V(()) = Ka ( E (N"(w) B. by the definition of N.G.(t)
that &G.(1)
b H.((() and NG.(0)
and (t) and in view of Lemma These are equalities between the (only) inputs in the WL color refinement step, which applies an injective HASH to obtain dy G.(++1 and da H.(t+1). It then immediately follows that ag
G.(++1) au (I((++))
As consequence, we have the following corollary: Corollary 3. Let π be any subgraph selection policy, G.,, G22 be any two graphs and D', D2 the x T-bags thereof. Let (1) and b 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 D, U and time step
t 2 0, DS- assigns a distinct color to G and H then DSS-WI WL does so as well: ae & a = (0)
GG * 644)
29

---

Published as a conference paper at ICLR 2022
Proof. In both algorithms, subgraph colors are obtained by injectively hashing the multisets of node colors therein. Furthermore, in BS-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 LemmaBand Lemmmmaa 3
Equipped with the above, we can now prove the following:
Proposition 7. Let be any subgraph selection policy. When both
the same n-induced bags, DSS- WL is at least as powerfil as DS-W WL in distinguishing non-isomorphic graphs, i.e. any Iwo non-isomorphic graphs G G² distinguished by DS-WL via policy π are also distinguished by DSS-WL via the same policy.
[G D be the bags induced by и on G1, G2. Let (+) and 6(0) refer to the subgraph coloring computed at step by, respectively, DS-W WL and DSS-WI (these assign each subgraph color by hashing the multiset of node colors at time t). Also, suppose DS-
Proof. Let D'
WL distinguishes between G G2 at time step T. The theorem immediately follows in light of
Corollary and Lemma 2 Let D D2 correspond to, respectively sets A, B from Lemma 2 and
let (2"), (lT) correspond to, respectively, colorings c, d from the same proposition. If G G
distinguished by DS-WL at step T, then we have A. F Be. Also, in view of Corollary [ holds that ((T)) Epi ppipa aLT), that is d EA.B C. All hypotheses in 2 hoold and we can then conclude
that Aa * Ba that is AgeZ) * Byery- This shows DSS-WI WI. assigns the two bags distinct multisets of colors, and thus, as DS- WL, it distinguishes between the two graphs G ,,
D.2.2 EXPRESSIVENESS
WL VARIANTS
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 premises to prove Theorem I
We start by characterizing DSS-WL WL, and giving some required definitions and lemmas.
Definition 4. Let G (V, F.) be any graph. Let be any subgraph selection policy generating an E.) over G. Policy π is said to be vertex set preserving if
m-subgraph bag St = [G: V; = V for each 1, ,.. m.
Intuitively, a vertex set preserving policy is a policy which does not perturb the original vertex set; subgraphs are obtained by taking subsets edges. Note that the ND policy is vertex set preserving node and all the related connectivity, it removes its incident edges only
if, instead of removing and leaves the isolated node the vertex set.
An important component of the DSS- DSS-WL algorithm is the HASH input C( which represents the multiset of colors for node v across the subgraphs in the bag.
Definition 5. Ler G (V, E) be any graph. Let π be a vertex set preserving policy generating an m-subgraph bag Să. The needle node color for node E V at time step 2 0, denoted c(t)) is defined as ( 3t sEST. where cg is the node color of node u on subgraph k at time step t. remark that the needle node color c(t) 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
bags induced by n, and be the node coloring from the standard WL algorithm. Then bat [ a, that is, for all graphs G = (V) and G2 = =(V2, (V2,E²) and all nodes E V E 2 we have that bū b
Or Cxp-
Proof. Let G1, G2 be any two graphs, (t) refer to the WL coloring at iteration t, and ((0) 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 ((O) 5 (!) 2 O. We prove the lemma by induction on time step
30

---

Published as a conference paper at ICLR 2022
In particular, let refer with (8) the WL-color assigned node time step and with b 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 C If & Issss with (t) co the DSS-WL color assigned to node
at time step subgraph S.
(Base case) At 0, it clearly holds that b(0) C ( given that all nodes are initialised with the same constant color č.
(1) = aio We seek to (Step) Let us assume the thesis holds true at time step t: 6.d Dar prove that if that the case, also holds true at time step +
Suppose ((+1))
= (++1) Unrolling one step backwards in time we get:
(g(bb v,St
NOO) C,,, M..)) {g(b NOO) T W, C M BRRES
where g = HASH. In view of Lemma 3 the following equality also holds:
gg - g(b N00 0
fg g(b w.R: N( C M ResT
since, due the injectivity of g, the left inverse g mm(g) (gg) exists (and is injective). Thus we have:
( o.S. o.S: CiO, M( sEss = (00 10 w Ro
N00) C(O M )
where, in view of Lemma 4 also have:
[C It sEST
(C BREST
{ = f If Rese
The elements of these multisets do not depend on index k, therefore we can rewrite the equalities as the set equalities:
((C |S ()) ((C 15²=
(MM9,18E,1)) = ((M))115.))
which obviously imply
C00 C M M(
First, we note that 6/ = c(l Ciff) (t) which by the induction hypothesis gives us (!)) a
Second, note that M (t) (b(0) l E Nob) and M
-66/015 E (.w)). By the induction
hypothesis, Lemma gives that M, Ml
fa (1) A(O)) 8a e A(ww)
This, along with the result above, implies a (++1) dew
(t+1) since both the two inputs to hash g
time step coincide. The proof terminates.
Finally, by leveraging the above lemma, we show that DSS-WL. 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 r-induced bags least as pow- erful as WL in distinguishing non non-isomorphic graphs, i.e. any two non-ison mo-iisomopppic graphs G G distinguished by WL are also distinguished by DSS WL when run on the respective R-induced bags.
Proof. Throughout the proof, we will denote with colorings generated by the WL algorithm,,, while b will denote needle colorings generated by DSS-Wi and its node colorings on subgraphs. Addi- tionally, we denote D D the --bags of, respectively, G1 G² We suppose the two bags have both cardinality m, and are defined as D= [G). (VI He D2 = G (V2, E pm We do not explicitly focus on the case |D'| # [D2 as the two graphs would then be (trivially) distinguished by DL.
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 v V # ( w 22
31

---

Published as a conference paper at ICLR 2022
while the DSS-WL algorithm deems them non-isomorphic when the two assigned two distinct multisets of subgraph colors, that is:
Of + C
where bg generally indicates the color computed for subgraph j of graph G¹: [c v'}.
Suppose WL distinguishes between the two graphs at iteration T. In view of Lemma 6 know that B(T) _ 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 T is refined by the coloring generated by DSS-WL + on any pair of subgraphs: VG, H D U c(T+1) EG. b(T), Let us shortly prove it. We seek to show that for all nodes v in G, u in H:
(T+1)
(T+1) H..H
b(T)
b(T)
Cg
The antecedent implies the equality of all inputs to the HASH function at time step T, that is: (T) 2 i, No. N M = M and, importantly, C!T) c(?) By the definition of needle node colors, this last equality is rewritten bl = -b0", which proves the refinement.
This tells us that, by transitivity, that YG, H D' c(T+1) Ec.H (T)), Therefore, by Lemma 2 two graphs are deemed non-isomorphic by the WL algorithm at step T,, then at step T + 1, DSS- WL assigns distinet color any pair of subgraphs from the respective bags, that is:
(T+ c
(c.T+") V + ( ww e v2
(T+1) cR
Yh, k E {L.....m) m}
This immediately leads DSS-WL to distinguish between graphs G¹, G² their corresponding mul- tisets 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. Recall that for policy æ,, the augmented policy से is defined by RG)) = π (G) (G), which augments i with the original graph G.
Lemma 8. Let be any augmented subgraph selection policc. DS- WL on i-innuced bags is at least as powerful as WL. in distinguishing non-isomorphic graphs, iee. any G G distinguished by WL are also distinguished by DS-WL when run on the respective R-inddced bags.
-n-issomorphic graphs
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 obtained by DS-WL by rumning an independent WL procedure each of them.
Let G G2 be two graphs distinguished by WL at round 2 1. Let a² a², a² + a² be the representations WL assigns to the two input graphs at time step T. Also, let us denote by C* {ct m k= C = {o I k the multisets of subgraph colors computed by DS-WL on the two input 7- bags round T. In particular, if ch. cp are the subgraph colors associated with G G¹, G G², clearly, of = a! o a²,ch * cg.
Now, any other subgraph from any bag has 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 color distinct from the one assigned to G already This entails the presence of a color in C which is not in C2 (and vice-versa), thus C¹ + C which implies DS-WL distinguishes between the two graphs.
the first round. Then, Vk 1,... m. i 1, 2, ct & fcl. og)
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 the standard WL algorithm. Nonetheless, there exist families of graphs undistinguishable by WL, which can be are separated by DS-WI when equipped with policies which do not include the original graph in the induced bags. Lemma I provides examples of them: CSL(n, 2) graphs can be distinguished from any CSL(n, k) with & [3. n/2 - 1] with either ND, EGO and EGO+ policy. We recall the definition these example graphs:
32

---

Published as a conference paper at ICLR 2022
Circulant Skip Link Graphs. For parameters 2 and E [2, n 2). CSL(n,,)) is 4-regular graph with vertex set = {O....,,2 - 1 and edges between node and = mod n as well as between i and + k mod n (Murphy al., 2019). For infinite subset of non-isomorphic pairs of these graphs, we prove that DS-WI. with two different policies can distinguish pairs that 1-WI. cannot.
(a) CST((8.2) (left) (right)
CSL(8,3) 3)
(b) Suhgraphs from ND over CSL(8, 2) and CSL.(8,3)
Figure 4: Graphs CSL((,2) and CSL(8, 3) (left) and their node-deleted subgraphs (right).
Proof of Lemmal / of each CSL graph.
We start with lemma that reduces the problem to considering a single subgraph
Lemma 9. All node-deleted subgraphs of G CSL(n, k) are isomorphic. All fepth-I ego-nets of G Cn,L(,, k) are isomorphic.
Proof. For i n 1), there is isomorphism from node-deleted subgraphs G Up to G-v: -t given by mapping node j in G Up to node j + mod n in U, This same isomorphism works for mapping the ego-net rooted at un to the ego-net rooted ez.
Let the nodes of CSL(n, 2)
be denoted to
un and similarly denote the nodes of CSL(n, kc)
(1)
(2) n-1- First, we start with the node-deleted case.
as 0g
Node-deleted policy. Denote the subgraph G1 = CSL(n, 2) - no and G2 = CSL(n, k)) x/²) Due to Lemma suffices to show that G₁ -I G2.
After deleting the nodes, in G₁ we note that vi _ (1) and n have degree 3 while all other nodes have degree 4. Also, these degree nodes each have at least one neighbor of degree
In G2, the nodes of degree 3 are u o o and p However, can be seen that none of these nodes have neighbor of degree 3.
(2) has no neighbors of degree 3. To see this, note that of - The constraints > and k [3, n.n/2 1] show that
In fact, it suffices to prove that just tj
has neighbors U/2 Vitk+ and (2)
(2) (2)
these neighbors are disjoint from the degree 3 nodes S [1 uk -n=k). This is because these
(2) (2)
constraints imply that the indices of the degree 3 nodes in satisfy
3 < n/2 1
3 n/2
<< 2 + < 3
On the other hand, the indices of the neighbors of // (i.e. u/ (2)
1 satisfy:
0<2<3 k k<k+1<m n/2
2
2.
Which together suffice show that the indices do not overlap. Indeed, is less than all of the indices of degree 3 nodes. & + is less than n k, greater than i. and less than n 1. Finally, n k + less than greater than k. and greater than k.
33

---

Published as a conference paper at ICLR 2022
(2) has no degree neighbors, so that 1-WL distinguishes G1 and G2 after two iterations. Thus, V1
EGO policies. Let G1 be the depth-1 ego-net of CSL(n, 2) rooted at v0 and let G2 be the depth-1 ego-net Cn, k) rooted at ug²) 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 7 edges total
(1) well edges (1) " (of 02 ), and 4 edges from ro to 1 n (1) and U/2
(1)
(1)
(2
(1) However, G2 only has 4 edges - those incident to the root (2) The proof that no other
edges exist 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 G₁ 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 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 undistin- guishable by WL).
Definition 6 (Ce and 2 C3). The Co graph is a 2-regular graph composed by a chordless cycle of 6 nodes. The 2 x C3 graph is 2-regular and is graph formed by two disconnected cycles of 3 nodes each (triangles). These graphs are illustrated in Figure Sa
(a) C. (left) and Cs (right)
(b) Subgraphs from ED over Co and
2 x Ca
Figure 5: Graphs Co. 2 x C3 (left) and their edge-deleted subgraphs (right).
It is casy to verify that, when 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.
this pair, the WL test converges the first iteration: each node
Lemma 10. The Cs and 2 x C3 are disambiguated by DS- WI. and DSS-WL under ED policy.
DS-WI.
Proof. We discuss the DS-WL variant; if this is able to distinguish between the two graphs, then DSS-WI. 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 show these two subgraphs are distinguished by WL prove DS-WL separates them. We simulate two WL rounds on these subgraphs starting from 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 WI. refinement, we note that the number of nodes of color (2, (1,2)) is two Cs. while this color absent in 2 C3 because there no node having both a 1-degree and a 2-degree node in its neighborhood. At this step the subgraphs are separated.
We are now ready to prove Theorem
Proof of Theorem 7 (DSS-WLL Policies ND, ED. EGO, EGO+ are vertex set preserving. Thus, in view of Lemma OSS-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, Temma I exhibits exemplary pairs for policies ND, EGO, EGO+: these CSL pairs
34

---

Published as a conference paper at ICLR 2022
indeed indistinguishable by WL (Mrphy 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-W
(DS-WIL WL) Let us consider augmented policies ND, ED, EGO, EGÖ+. In view of Lemma 8 these policies are such that DS-WL refines WL. Additionally, we note that Lemma | and Lemma T0
trivially hold also when considering these policies, thus providing counterexamples of graphs indis- tinguishable by WL but separated by DS-WL under these policies. This allows us to conclude the proof.
D.2.3 NEURAL COUNTERPARTS
We will now focus 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 The- orem 2 In this subsection we will always work with DSS-GNN architecture with GraphConv encoders (Morris et al. 2019) and entry-wise max adjacency matrix aggregation. Accordingly, the representation for node e in subgraph is given by:
m
m
h 1 = hW + W.2 Σne, + W?
Σ 1=1
Ke + W
Σ w~w j=1
(7)
where a is the ReLU non-linearity, m 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 defimition:
Definition (Edge-covering policies). A subgraph selection policy π is said to be edge covering if for any graph G E), Ve E, 3S (Vs, Es) E (T)) such that e Eg.
Clearly, policies ND, ED, EGO(+) are all edge-covering Let now show that in the case of edge- covering policies, there exists a USS-GNN architecture with layers the form of Equation (7) that, when working on graphs of bounded size, can "simulate" the color refinement steps of the DSS-WI. algorithm.
Lemma 11. Lerg = [G; = E.) denote the bag generated by an edge-covering selection policy on any G from family F of graphs with bounded size, optionally endowed with node labels from a finite support. Let ( be the color assigned by DSS-WL to node in subgraph k, after T <. so iterations. There exists DSS- ESS- model M with D 10T layers of the form described
Equation 7 such that co.k is uniquely represented by a one-hot encoding h bo the representation for node v in subgraph ls computed by such a model.
(D)
Proof. We will prove the lemma by describing how to parameterize the DSS-GNN layers in way to simulate the DSS-WL color refinement step on each subgraph.
(Preliminaries) We assume work with finite graphs whose size is upper-bounded by positive integer M E N and whose degree is ately follows that any employed subgraph selection policy generates bags of bounded cardinalities, whose subgraphs are finite graphs with size super-bouuded by M and degree upper-bounded by N. Let us denote with B < oo 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 OSS-GNN to simulate color refinement steps. is necessary encode colors in vector/matrix form. Under the aforementioned boundedness assumptions, at any step, each of the four inputs in the DSS-WI color refinement equation belongs to finite set of bounded size. The domain of the HASH function is therefore represented by the cross- pross-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 well. The application of this injective function effectively computes a unique representation of the inputs by assigning them a color.
by N E N. From these assumptions it immedi-
(Encoding) Given these premises, it is clear that, 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 N time
35

---

Published as a conference paper at ICLR 2022
step in the DSS-WL procedure, and with de E N the corresponding layer of the described DSS- WL model. Note that, in general, de 2 t as more than one layer is required to simulate one color refinement step. Let C. be the color assigned to node v subgraph &: at time-step t and h (d+) be its representation computed by our DSS-GNN model, of dimension as,, At time step t = O, each node in each subgraph is assigned a constant color ce,k č; if initial colors are available, they are retained. We consider ((ee)) Ni,k to be a proper one-hot encoding of these initial colors. For a color refinement from time step to + we consider inputs to layer de to be one-hot encoded. The refinement is simulated with layers de to dz+1, where the final output of these is one-hot encoding uniquely representing the result of the HASH function.
(Computation) Starting from the one-hot color representation in input to layer de, 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 output, unique, one-hot en- coding. 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 sum- ming 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: (!) (V v,k. cf In this layer, each matrix W has dimension 3 - add X ad, and b has dimension 3 ad,- In particular: W| [T, 0), W22 [0, T, W? [0, 0. T, W? 0, O, where [ indicates vertical concatenation.
In output from this layer are vectors in the form (do+1) [n AddeN) Aida. with the last Bock
v.ki c( In order to also compute a unique representation for the fourth input (M, we cannot directly apply summation on the just computed A. n,(4..) 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 (d..C) with a one-hot scheme so that the original neighborhoods (u)) 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 I B that can be constructed from a finite color palette of cardinality a.,- Additionally, this encoding can be computed by stacking 4 DSS-GNN layers with ReLU activations as shown by the following:
two components representing unique encodings of, respectively, inputs (1(0)
Let H be a finite set. Let elements in H be uniquely encoded by h(.). There exists 4-layer DSS-GNN model which computes the map p. h(a) + e,a E H with e being a unique one-hot encoding for element a.
Lemma 12.
Proof. We consider an ordering relation < determining an overall sorting s of the elements in H. This be obtained, for example, by a lexicographic ordering of the elements in the encodings f(-). This sorting associates any element with an integer index, that is H + N, s a + i. We can therefore denote each (encoded) element with h 1,.... HH). We seek implement the mapping μ : 14 ej, such that: e, E (0, 1)1M and (et); 1 if = i, (ex); 0 otherwise.
We define the dataset D {(h,, ) This dataset satisfies Assumption 3.1 in Yun et al. 2019 all h,'s 's are distinct and labels eg's are in [11,+1],,, dy = [7t). Moreover we have that Vi, 0, 1dv Thus, according Proposition 3.2 in the same work, there exists 4-layer ReLU network parameterised by @ and with 22 /12 +|Zl)) neurons which perfectly fits D. This network computes and is exactly implemented by 4-layer DSS-GNN model with matrices W:((1) w??") w:(") 0,1 = 1, ....,, and (W1(0)
(1) )
We invoke Lemma 12 with H. being the (finite) set of all possible B-size multisets over node col- orings hdde), which are from finite palette of size ade Accordingly, there exists a stacking of
4 DSS-GNN layers such that 1, o,k = (de) (d...) . TTdd,.C) with [,(d.C) being the one hot
(dc+5)
encoding of (dr.C) dimension eg.o If (WW (1) B00 1=d+i the parameters from Lemma 12 one-
d45
36

---

Published as a conference paper at ICLR 2022
hot encoding he ()).CC then these layers are obtained simply by w1 [[, [o]l) 11.6
(1)
[0, 1, W W2 w O. Here [-I-] indicates horizontal concatenation and I is always of size 2-ad, 2- ad, Overall, each (d++5) has dimension +-5 (2-a4,) +et.c. Importantly, we no- tice that component [,dde.)) is computed for node v but independently of k, and is thus shared across all subgraphs. Layer de + now computes the encoding of M Each weight matrix has dimension (aa,45 + ex,c) X ad, with: W = [Z, 0] (I size ad,+ W W 0, W - [0, (0 []] (0 size E,, x (2 Od. ), size et,c), b b= 0 1R44-3,
Now, , [/d+tt) [hdde) n (d...) R.(d..)) .i. J, of dimension ad,+6 ad, + ct,C, constructed Pe,k 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 b (d++)) 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 u. (d++6) can only assume finite, bounded number of distinet values. Again, this encoding is computable by DSS-GNN layers, as per Lemma 12 invoked considering the (finite) set of all possible colorings attainable by encodings h((++))
Finally, we have that h hy.k kg.k simulate T iterations of the DSS-WL color refinement step with D = 10T layers, which concludes the proof.
(dde+))
A This construction can be arbitrarily repeated to exactly
The following Lemma shows that there exists DS-GNN architecture with layers of the form in Equation (7) that, when working on graphs of bounded size, can "simulate" the color refinement steps of the DS-WI algorithm.
Lemma 13. Let G &G denote the bag generated by subgraph selection policy applied on any G from a family F of graphs with bounded size. Let (T) be the color assigned by DS-WL to node v in subgraph k after T iterations. There exists a DS-GNN model M with D = 5T layers of the form described in Equation ? such that o is uniquely represented by one-hot encoding hD the representation for node in subgraph computed by such a model.
Proof. The proof closely follows the one for Lemma 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 proper one-hot encoding each refinement step being simulated. The difference is that, in this case, the described DS-GNN model always has parameters W?, W2 = 0 and does need encode the HASH inputs c!') _M. (not present in its update equations).
(t) Let C. be the color assigned to node v on subgraph & at time-step and h be its representation computed by our DS-GNN model, of dimension dd, and properly one-hot encoded. We seek to describe stacking of DS-GNN layers producing h by,k (d(e)) unique, one-hot encoding of color C, (1+-1)
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:
(t) A-(() Cy u.k- In this layer, each matrix W has dimension
2 ad, ad, and b has dimension 2 ad,, In particular: W1 [1, 0j. W.] 10, b = 0 where [+--] indicates vertical concatenation.
In output from this layer vectors in the form (d++1) (de) (d,,N)] with the last component (d::1) it is only left one-hot encode
representing a unique encoding of No, In order obtain 1 h h (d++1) We perform this operation with a stacking of 4 DS-GNN layers leveraging only on matrix W! (in module L2) and bias b. This stacking is described by Lemma
12 invoked considering the
(finite) set of all possible colorings attainable by encodings (11++))
Let us now move prove Theorem 2 from the main text.
37

---

Published as a conference paper at ICLR 2022
Proof of Theorem 2 (DS(S)-GNN _ DS(S)-WL) We will directly describe a DSS-GNN GNNN architecture
satisfying the requirements under edge-covering policies. According to Equation 2 a DSS-GNN architecture computes a representation for graph in imput as: hg Exess o Roubyraphs Esuhgraphs (G). Let T' be the time step at which DSS-WL (resp. DS-WL) distinguishes two input graphs G², GP. At this round, the overall coloring is such that the multisets of subgraph colors for the two graphs are distinct:
G DE +
H DE
where (7)
Gy V*)). Now, let Esuhgraps be the module obtained by the stacking described in Lemma (resp.
generally indicates the color computed for subgraph j of graph G:: HASH @f v.
V
Lemma 13 We know that this module uniquely encodes each subgraph node color Co. with one-
(T)
hot representations ((dr), Therefore, is only left describe modules Raubgraphss: Evess 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 Raabgraphs can be simply obtained by summation over node representations on each subgraph. This because summation is an injective aggregator when multiset elements are described in a one-hot fashion. Let generally refer to the computed subgraph representations as hy.
Let us finally describe module Exas- The graphs of interest have a number of nodes upper-bounded by positive integer and so hy's 's uniquely represent bounded-sizer multisets of colors from a finite palette. The set of all possible such multisets is finite, so is possible to compute a one-hot en- coding for these subgraph representations with 4-layer ReLU MLP applied in siamese fashion. Lemma [2 ensures the existence of such a network as the described stacking of DSS-GNN layers ef- fectively boils down to Siamese MLP. This would constitute the first 4 layers of E To conclude, one last layer applying summation to these one-hot hot encodings would suffice to output an embedding uniquely describing the multiset of subgraph colors.
(DS-WL C DS-GNN) As for DS-GNN and DS-WL, we show in the following that, if DS-GNN distinguishes two graphs, then DS-WL also distinguishes these two graphs. Suppose DS-GNN distinguishes between G and G2. If the bags Sor and Se² are of different sizes. then DS-WL separates 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-WI. graph coloring function and MPNN 9 + Σ denote the MPNN base graph encoder employed by DS-GNN, we have:
(MPNN(G)),...
7 [MPNN(C)) MMNNG(".))
..,PNNC)...,,,NNNCG....
(8)
By Morris et al.
2019); ; Xu et al. (019)), we know that 1-WL MPNN, i.e. that 1-WL
1- 1-WL((H*) implies that MPNN(H MP2 for any graphs H² and H², Thus, Lemma
tells us that
H [IWL(C))..... (WW + (I-WL(C))
Hence, the final readout of DS-WL maps these multisets to different values, so that DS-WL distin- guishes G and G²
This is enough prove the second part of the thesis, terminating the overall proof.
E PROOFS FOR SECTION 3.3 DESIGN CHOICE EXPRESSIVENESS
This appendix section contains proofs for Section 3.3 First, note that we use DS-GNN and DS-
WL interchangeably in proof', as they are equivalent in power for distinguishing graphs (as shown in Theorem 2)
E. PROOFS OF DSS VERSUS DS
Proof of Prop That DSS-GNN is at least as powerful as DS-GNN follows directly from the def- inition. For any DS-GNN, there is a DSS-GNN with I = O in each layer that implements the DS-GNN. To show that DSS- OSS-GNN& is strictly more powerful, provide two examples.
A trivial example. Consider the subgraph selection policy SE : G (V,E) + {(V(ee)) e F). Each subgraph is single edge from the original graph. Now, let G1 be the path
38

---

Published as a conference paper at ICLR 2022
nodes, and let G2 be the 3-star. In other words, G1 has vertex set of (1, and edges ((1,2), 2), (2, 3), (3, 4)}. while G2 has a vertex set of {1, 2, 3, 4} and edges (1, (1,4)).
Now, show that DS-GNN cannot distinguish G1 and G2. Note that the bags are of the same size: |SE(G,) = 3. Morcover, 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
{ [IWWL(H): H B = { [I-WL(H) H E SE
(10)
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 let (A, = 0 and (A(A, = A x These operations are simple and can be implemented by MPNNS with sum pooling: for instance, GIN (Xu et al. 2019) and GraphCony (Morris et al. 2019) can both implement L and L Letting the initial node features in each subgraph i be X after one layer as
1] we compute the node features
ΣイソΣ
x = IA,,
(11)
,
= =0+ L2 (A,3I)
(12)
=AT.
(13)
Thus, the kth component of x!!) 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 G₁ and G2- Thus, DSS-GNN distinguishes these two graphs. This is because the multiset of node features in G₁ 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 G₃ and 3 for Gz).
This example is trivial because it is easy to make 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 I-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, consider the policy SE that is given by adding the original graph the SE policy, so SE(() SE(G) U (G). For this policy, we can again show that DS-GNN cannot distinguish a pair of graphs that DSS-GNI can, though we need allow a slightly different type of aggregation for ASS-GNN. In particular, when computing
the features for subgraph i, we use an 2 that is mentioned in Section 2.1 L Σ At,
Now, consider the pair of non-isomorphic graphs: G1 is two triangles 2 x C3 and G2 is the 6-cycle Gg (these graphs are depicted in Figure 5). Denote the subgraph corresponding the single edge (i,j) as G..,), and the corresponding adjacency as ((-5)) {0, 1) 1666
We show that DS-GNN cannot distinguish G1 and G2. First, note that the bag of size |SE SE)))) 7 for each graph - they each have 6 edges and the original graph adds one more element to the bag. Note that G₁ and G2 are regular of the same number of nodes and degree, so they are 1-WI. equivalent. As any other subgraph is 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
(-W H E SE(G)) = [ (1-WL(HH: H E SE(G2)
(14)
so that similarly to the previous example, DS-GNN cannot distinguish these graphs.
Now, 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, (0) I (1 e _= Let the first layer graph encoders be given by:
1.7 TA AX,
1,, X) 0
(15)
39

---

Published as a conference paper at ICLR 2022
Figure 6: The Rook's graph (left) and Shrikhande graph (right) (Arvind et al., 2020) are non- isomorphic strongly regular graphs of the same parameters. They thus cannot be distinguished by 3-WL.
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 ( after one layer is:
x (1.).. = (L(A, x)) = L' (A())) I)s
(16)
= (A(
(17)
IKE(Es}
(18)
In other words, the feature on node h for (bJ) is one if k is i or j. and zero otherwise. Also, similar computation shows that subgraph G corresponding to the original graph has node feature 21 after this layer.
Now, let the second layer graph encoders be:
(2 (A) 0,
16 (A, (1A) (-x +
(-x+41) 41).
(19)
where T.2 takes the standard sum pooled Σ, Aj as well as the modified pooled Ejt; X,. These can be implemented by GraphConv with bias terms. Then the kth element the representation of the nodes of (655) after the second layer is:
(2) (1.)).
= (2)
++ Σ (L)))E
A
x +
Σ
X(1 (1)20)
(20)
(
-La2)
2A, 2Î
Σ
x
(21)
k
T2an) (2A, 7(0a))
(22)
(A(- (A(-Z(0)) + +T)) k.
(23)
where Z(s,a is if & {i,j} and is 3 if E {i,j]. Thus, - (Z()) 4f & (i,5) and if I e {i,j). We show that (2) differs between G1 and G2. (1,5)
For G1, let be the other node in the triangle that node and are in. Then x (t.).. 2. On the
other hand, for G2, there no value of k such that x(2 (K.J). is 2. This is because there no node that is adjacent to both 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 done.
E.2 PROOFS OF INCREASING ENCODER EXPRESSIVENESS
First, we introduce certain graphs that provide useful examples for our proofs, and that have been used study expressiveness of graph algorithms more generally.
40

---

Published as a conference paper at ICLR 2022
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 ss graph and the Shrikhande graph. These are non-isomorphic graphs that are strongly regular of the same parame- ters, so they cannot be distinguished by 3-WI. / 2-FWI. (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 = {(z, y) x E (0, 2, y E {0. 1, 2, } so each of the 16 nodes are viewed as a point on grid in the plane. For each node y) E V. the Rook's graph has edges ((x, y), (x', v)) for x' o a and ((x,y), y²) for y' + y. The Shrikhande graph has edges ((I, y), (2, y = mod 4)), ((x, y), (z + mod 4, y)), and ((z, y). (x + 1 mod 4, y = mod 4)). We number the nodes on the grid from left to right then top to bottom, so node is (0,3), node 2 is (1,3), node 5 is (0,2), node 6 (1,2), and so on.
Proof of Prop Note that the generalization of DS-GNN to 3-WL encoders is straightforward, as simply use the graph representation vectors from the readout of the 3-WL encoder the sub- graph representations in the DeepSets module. In other words, letting 3- WW--GNN()) be the final coloring of G that is obtained from GNN that is equivalent to 3-WI., we apply DeepSets module to (3-WL-GNN(G.) : G, E Sc H 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 least strong as I-WL. Also, DS-GNN with 3-WL is at least as strong as 3- WL since the original graph is included in any augmented policy n.
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 root node that is connected to all nodes. All depth-1 ego-nets of the Shrikhande graph consist of 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 6-cycle. Thus, DS-GNN with the depth-1 EGÖ or EGO+ + policy cannot distinguish the two graphs.
On the other hand, 3-WL can distinguish these ego-nets as 3-WL can distinguish two disjoint tri- angles from 6-cycle; for instance, this can be seen due to 3-WL. being able to count triangles at initialization (Chen et al. 2020).
E.3 PROOFS OF POLICY CHOICE AND EXPRESSIVENESS
Before restricting 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 DSSGNN model with depth-1 or depth-3 EGO policies do not distinguish CSL( and (2),,, while the depth-2 EGO policy does distinguish them.
Proof of Prop 8 The depth- 2epth-2, and depth-3 ego-nets of CSL.(12, 3) and CSL((1, 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) 3) and CSL 5) are K1,4- the star with one root node of degree 4 and four nodes of degree I connected to the root. As these are isomorphic, 1-WL does not distinguish any subgraphs, so our DS-GNN cannot distinguish CSL 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 3) has degree 3 nodes while the ego-nets of CSL(12, 5) do not have any degree nodes. Thus, 1-WL distinguishes these ego-nets, and hence DS-GNN does 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 regular of the same number of nodes and same degree, 1-WI.
41

---

Published as a conference paper at ICLR 2022
(a) Depth
(b) Depth 2
Depth 3
Figure 7: Ego-nets of CSL((1,3) (left) and CSL(12, 5) (right) for depths 1, 2, and 3. These are used Proposition g
does not distinguish the subgraphs, so DS-GNN cannot distinguish CSL(12,3) and CSL((1, with depth-3 EGO policy.
E.4 STRONGLY REGULAR GRAPH PROOFS
In this Section, prove Proposition the power of different policies for distinguishing strongly regular graphs.
E.4.1 ND AND EGO+ ON STRONGLY REGULAR GRAPIS
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 sub- graph of a strongly regular graph at most 3 iterations, and that the coloring only depends on strongly regular parameters. Let G be strongly regular graph of parameters (n, k. X, 11), 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 the node-deleted subgraph ut
Iteration 1: Initialize each node have color a.
Iteration 2: Degree k nodes are colored b and degree k nodes are colored c.
nodes are colored d, as they each had color and have À neighbors and (k- 1 A) 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 Since the neighbors of now degree k in G u, they have color b iteration 2. Thus, there are exactly b neighbors, and the remaining color is c, so there are also exactly (K 1 A) neighbors.
Iteration 3:
All degree
Also, all degree & nodes are colored e, as they had color and have μ b neighbors and (k (4) neighbors. This is because these nodes not adjacent to in the original G, so they have exactly μ common neighbors with in G. Thus, they have exactly a b neighbors and (k (4) neighbors.
42

---

Published as a conference paper at ICLR 2022
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 G₁ and G2 of different parameters. The coloring differs iteration 1 if differs, at iteration if lo differs, and at iteration 3 if X or differ. Thus, DS- DS-WL. and hence DS DS-GNN is able to distinguish any two such graphs.
Lemma 15. DS-GNN with the depth-n EGO+ policy can distinguish any strongly regular graphs of different parameters, but cannot distinguish any strongly regular graphs of the same parameters.
Proof. Consider depth-n ego-net rooted at u. This proof is similar to that of the ND case in Lemma 14. We compute the 1-WI. iterations:
Iteration 1: u has color al and all other nodes have color
Iteration 2: u has color a2 (as it is the only node with previous color al).
The & neighbors of have color e (they each have previous color b, have the one neighbor u of color al, and have & neighbors of the remaining color b).
The n - neighbors of color al, and thus have & neighbors of color b).
non-neighbors of u have color d (they each have previous color b, have no
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 с because they are adjacent and all neighbors of had color c, and have k x neighbors of the remaining color d.
The k- non-neighbors of u have color f (they had previous color d, have no neighbors of color a2, have neighbors of color e because they are non-adjacent to u and all neighbors had color c, and have k - μ neighbors the remaining color d).
This coloring is stable, the algorithm terminates. Note that this coloring only depends the strongly regular parameters. Once again, it differs for any strongly regular graphs of different pa- rameters, 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
E.4.2 ED ON STRONGLY REGULAR GRAPHS
subgraph of strongly regular graph gives a coloring that only depends on the strongly regular parameters. This coloring distinguishes any strongly regular graphs of different parameters.
Lemma 16. 3 iterations of I-WL on any
Proof. Say have deleted edge (M1, u2). The 1-WL iterations follows:
In iteration 1, each node has initial color a.
In iteration 2, we have two nodes of degree 1 that are colored b, i.e. un and u2. There are nodes of degree & that colored
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 for nodes adjacent to b nodes and k - 2 nodes, iis for nodes adjacent to I b node and le 1 e nodes, and g is for nodes adjacent to & с nodes. We show that the number of colors e, f, and only depend on the strongly regular graph parameters.
43

---

Published as a conference paper at ICLR 2022
First, there are À nodes of color e, the nodes adjacent 2 nodes are common neighbors U1 and ug, which are adjacent the original graph G. By definition there are common neighbors of and U2.
Next, there are 2(k - X) nodes of color This is because each node of color f is only adjacent to of i1 u2- Each of uj and u2 has (k common with the other, so there are total 2(k 1 - X) nodes of color f.
A) neighbors that are not in
The only other choice is color g. color counts from the total number of nodes n.. There are thus n - 2 - X 2(k - π + X 2k nodes of color g-
compute the number by subtracting all the other
It is clear that if G and G2 are strongly regular graphs that differ in any of the n. k or À parameters, then three iterations 1-WL distinguishes due the above coloring differing. Now, G, and G2 differ in the parameter, the same argument holds, because the μ parameter for strongly regular graph is related to the other parameters by
(n - k 1)1r k:k - 1-
(24)
(See Theorem 1.1 in Cameron (2004) ) Thus, G1 and G2 must differ in least one of n, k, or X, and hence they are distinguished by iterations of 1-WL.
Lemma 17.
The 4 x 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 color- ings 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 I-WL coloring of one edge-deleted subgraph of the Rook's s graph differs from a I-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 E.2 Each node starts with an initial color that we denote 'a'. See Tables T2 and 13 for the coloring, which differs for two graphs at iteration 4 (as aside, note that the first 3 iterations were already computed in the proof Lemma 16). Thus, these two graphs are distinguished by DS-GNN, and hence DSS DSS-GNN, with the ED policy.
Node
Iter 1
2
3
4
b
h
b
h
HASH(M(b)
M(+)
c
initialize
a
c
C
b (a, aаааа)
5
a
c
(a, aаaааa)
6
f
d
(b, ceccc)
(c, bbccoc)
a
(c. heceec)
10
9
a
C
C
g
(c, ceccce)
(d, eefff)
11
C
(e. dddegg)
12
g
(f, dfffgg)
13
a
k (g. effggg)
14
a
15
K
16
k
Table 12: 1-WL on an edge-deleted subgraph of the Rook's graph, where we delete edge (1,2). The table the right shows MMv),, which is a tuple containing the current color of node along with the multiset of neighbor colors. In each iteration of 1-WL, M(r) is updated to HASH(M())).
44

---

Published as a conference paper at ICLR 2022
Node
Iter
2
b
d
HASH(M(v))
M(U)
b
initialize
a
c
f
J
b (a, ааааa)
f
f
C
(a, аааааа)
d (b, cocce)
e
(c, bbccec)
C
f
(c, beccce)
C
g
k
g
(c, cccece)
g
(d, cefff)
10
11
C
g
j
(f, dfffgg)
k
(g. effgeg)
12
Reeu
1
(f, defgeg)
13
m
(e, ddffgg)
14
n (g. ffffgg)
15
g
16
C
Table 13: 1-WL on an edge-deleted subgraph of the Shrikhande graph, where we delete edge (1,2).
E.5 PROOF OF PROPOSITION
With the above lemmas for different policies may formally prove Proposition 3
Proof of Prop
(1) Lemmas 14 and 15 show that ND and depth-n EGÖ+ can distinguish strongly regular graphs of different parameters. Lemma shows the same for ED.
(2) is proven in Lemmas 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 ctt al. 2020). so ED is not less powerful than 3-WL in general, and is strictly more powerful than 3-WL the family of strongly regular graphs. While 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 lot of work has gone into distinguishing non-isomorphic strongly regular graphs, there is no known polynomial-tine algorithm to do so (Babai et al. 2013).
COMPLEXITY
F.1 FORWARD PASS
Table 14: Complexity of graph networks that are more expressive than 1-WL. Amax denotes the maximum degree over all nodes.
PPGN
3-IGN
3.GNN
GSN
CWN
Ours
Time
Onn3)
(nn²)
O(n')
O (nAmmx)
E E (y +2 n E n,(1 + B, 2( 2(
O n.maa))
Space
(n²²)
(n))
(n)))
nAmas)
O [[S[[n ndmmm))
Here, we analyze the complexity of our method, when using MPNNs as graph encoders, compared to other graph networks that We assume that the feature dimensionality is constant.
expressive than 1-WL. In Table 14 we summarize the results.
For dense graphs, method requires O[[S)n?) time, as each of the |S| subgraphs is processed using a MPNN time complexity O(n When |S| = O(n) as in the case of node-deleted and ego-net policies, the time complexity is O(n)), just in the case of PPGN (Maron al. 2019a)
45

---

Published as a conference paper at ICLR 2022
and 3-IGN (Maron et al. 2019b). When |S| O(n²) as in the case of edge-deleted policies, the time complexity is (( like 3 GNN (Morris et al. 2019).
More specifically, the time complexity of our method improves to ([SS)AAmax) where Amax 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 A Amax = O(1), we gain a factor of (n) in time complexity over PPGN and 3-IGN and a factor of O(22) over 3-GNN.
Table 14 also reports the time complexity of two provably expressive, sparse architectures: GSN (Bouritsas et al. 2022) 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 only the case for stochastic policies that we consider. The remarkable efficiency of GSN, how- ever, 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 2-dimensional cellular complex, with 7e denoting the number of cells at dimension p and Bp the maximum considered boundary size. Here, Ro = n, Ω1 = O(nAmax) refer to, respectively, the number of nodes and edges. In the case of lingliitinns with ring size upper-bounded small constant, the complexity can be rewritten as O (nAmax + 722)- 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 distribu- tions. 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 is O (n + n1mma))) )), as we need to compute n node features for each subgraph. while keeping the subgraph connectivity in memory. This evaluates to O(n + n² mmax)) for node-deleted and ego-net policies and Onn2Amax + mx4maxx)) for the edge-deleted policy. We also note that the space complexity of our method can be improved O(n + m2Amax) 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 much lower.
F.2 PREPROCESSING
In order to perform message passing on subgraphs, it is first required to apply selection policy and generate the bag. This amounts one-off computation that can be performed prior to training- Simple implementations of the ND and ED policies have complexities (nm) and O(m²²) respec- tively, where n is the number of nodes and ma is the number of edges. As noted above, m can be upper-bounded by n. with Amax typically small in sparse graphs. EGO policies are easily implemented in O (n + m))) where O(n + m) is the complexity of a generic Breadth First Search algorithm employed to recover the k-hop neighborhood of source node. More sophisticated im- plementations 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(z²) 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 dif- ferent graphs in a dataset and parallelisation techniques can be applied to dramatically reduce the empirical run-time.
46


Reviews:
[{"review_id": "bveexeTJPw", "reviewer": "Reviewer_tGsP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper develops a Equivariant Subgraph Aggregation Network to enhance the\nexpressive power of GNNs. The idea is to 1) represent graphs as bags of\nsubgraphs 2) use permutation-equivariant layers to encode the subgraphs 3)\naggregate the subgraph representations into an invariant graph representation.\n\nStrength:\n\nS1. The idea of using equivariant subgraph representation and aggregation is novel.\n\nS2. Very solid theoretical analysis showing the expressive power of DS-GNN and DSS-GNN.\n\nS3. The experiments are comprehensive as they conducted experiments on various\nreal and synthetic graph classification datasets and include most existing\nmethods on expressive GNNs. The results are mostly positive, showing the\nbenefits of DS/DSS-GNN architectures.\n\nWeakness:\n\nW1. It'll be better if the authors can perform a detailed breakdown. Of the\nexperimental results to show. To provide some insights above, when does the\nDSS. Architectural works well and when does it not? The.\n\nW2. The model introduces extra time overhead. Although the authors introduced\na stochastic strategy that can mitigate this issue to some extent, the time\ncost is still several times larger than standard GNNs. Also, it's better to\nshow how the method scales with graph sizes.\n\nW3. How will this method work for other graph related tasks beyond graph classification? \n", "summary_of_the_paper": "This paper aims to improve GNNs' expressive power based on bag-of-subgraph\nrepresentation. The authors develop a Equivariant Subgraph Aggregation\nNetwork, which uses equivariant layers to encode subgraphs and aggregate\nsubgraph representations. The authors have performed theoretical analysis of\nthe proposed framework, subgraph selection policies, and their expressive\npower. The experiments show that such an encoding can lead to a better\nexpressive power on several real and synthetic graph classification datasets.\n", "summary_of_the_review": "This is a solid paper on improving the expressive power of graph neural networks. The proposal approach of equivariant subgraph representation and aggregation is novel, the theoretical analysis is solid, and the results are positive. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8P4rOHnf47", "reviewer": "Reviewer_rtwc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n- This paper gives solid theoretical formulation and analysis of graph representation learning over bag of subgraphs. The technical contribution of this paper is sound and significant.\n- This paper gives detailed formal analysis of design choices such as base graph encoders and subgraph selection policies.\n- The presentation of this paper is clear.\n\nCons:\n- In the experiment results, some DS(S)-GNN variants have inferior performance than basic graph encoders on some graphs.  Can there be any insights or guidance on whether to use DS(S)-GNNs for specific kinds of graph data? As we might want to quickly estimate this DS(S) architecture can be beneficial before actually conducting its heavier computation.\n\n\nSome work that might be relevant:\n- [1] is on the empirical side of using the aggregation of subgraph representation to represent a graph. It tries to factorize the original graph into disentangled subgraphs, then to utilize the factor subgraph embedding to represent the whole graph.\n- [2] shares similar high-level ideas with this paper, which is to encode the graph through different subgraph channels then aggregate them.\n\n[1] Factorizable Graph Convolutional Networks, Yiding Yang, Zunlei Feng, Mingli Song, Xinchao Wang, NeurIPS 2020\n\n[2] Graph Neural Network with Automorphic Equivalence Filters, Fengli Xu, Quanming Yao, Pan Hui, Yong Li, arxiv 2020\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "This paper provides a solid foundation on the theoretical formulation and analysis of graph representation learning over bag of subgraphs. The contribution is technically sound and the solution is well supported by detailed analysis of design choices. Thus I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6ujoR2atrFN", "reviewer": "Reviewer_B3oK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strong Points\n1. Searching more expressive GNN is hot topic and has a lot of importance both academic and industrial perspective. The main motivation and their approach is definitely eligible. This problem is one of the most important problems in GNN and recently there are a lot of different approaches. \n2. The way of explanations and writing manner of the author are nearly perfect. Seems they spent a lot of effort to present the idea clear and didactic way.\n3. Theorems and their proofs are clear and sufficient.\n4. The researches that are in the same track with this paper, usually use predefined handcrafted features and/or structures which needs domain expertise among nearly infinite number of selections. Proposed approach does not need that kind of engineering efforts.\n\n### Weak Points\n1. Increasing expressive power of MPNN by applying baseline MPNN onto each subgraph of given graph and later somehow aggregate them in order to get graph level representation is very smart idea. However, It is not new at all. Recently, one (maybe concurrent research) already published the node deleted subgraph idea in [1]. Their proposal almost the same with DS-GNN in this paper. In addition their proposal of sampling strategy is exact the same. Just the differences is that in inference time, they used full sampling to get invariant graph representation.  That paper in [1] was not seen in this paper. I think the differences between these two papers are not significant.  But I am happy to hear the differences by author point of view.\n\n2. If the baseline MPNN has linear time and memory complexity, proposed method with full sampling has quadratic complexity (when one node deleted subgraphs is used) that makes it infeasible easily w.r.t increasing number of nodes. Stochastic sampling of subgraphs seems reasonable solution, but this time the method lose the invariance property. Though this shortcoming, it may gives comparable results in the benchmark datasets, but how can we say it is more powerful than 1-WL in terms of separation power? It may separate non-isomorphic graphs but also it separates isomorphic graphs as well. Basically it separates all given pair of graphs because of stochastic sampling in inference time.\n\n3. Experimental part of the paper is very weak unlikely to the theoretic parts.  Since TU datasets have limited number of instance and results standard deviation is very high, we cannot make reliable comparison. I think, TU datasets result does not deserve place in main paper but maybe in appendix for just giving some idea. In the paper, just EXP datasets is the unique result that gives idea about separation power of GNN. However, this dataset is very small and all pairs are 1-WL equivalent. The paper also mentioned SR dataset which consist of 3-WL equivalent graphs. I would like to see separation power analysis of SR dataset. I guess it is missing because of stochastic sampling. It basically separates all graph pairs even though pairs are isomorphic. Also Circular Skip Link dataset in (Murphy  2019) would be great expressive test of proposal method. But I strongly think that proposed methods fails, because that dataset includes isomorphic graphs that needs to be map on the same point in latent space. It is known that even though having more powerful GNN does not mean we will have better generalization on various datasets. But at least in some dataset such as Zinc12K, powerful methods outperformed 1-WL ones with a huge margin. I would like to see your method result on ZINC with compare to relevant recent powerful GNNs. In addition to Zinc, we know that in some artificial task such as substructure counting, 1-WL equivalent MPNNs fail ridiculously. So that kind of tasks would be great test to show your methods expressive power experimentally. \n\n### Reference\n[1] Cotta, L., Morris, C., & Ribeiro, B. (2021). Reconstruction for Powerful Graph Representations. NeurIPS 2021.", "summary_of_the_paper": "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.\n\n\n", "summary_of_the_review": "Since the idea is not original if Cotta et al. work is seen, and it has lack of experimental tests in initial submission as mentioned above, I would recommend rejection to this work.\n\nBut as the author mentioned that Cotta et al. work should be seen as contemporaneous work and there are a lot of additional test in second version, I changed my rate to 6.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "2XiB4qiU-rp", "reviewer": "Reviewer_Ebj3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is well-written, easy to read and provides lots of details at the same time.\n- The proposed idea is rather simple, which is kind of an advantage and a disadvantage at the same time.\n- The proposed method shows (small) improvements over the base encoder in many cases.\n\nWeaknesses:\n- Even though the proposed method shows improvements, it should be mentioned that the improvements are rather smaller, especially given the increased complexity and computing requirements of the proposed method. Hence, it seems rather unlikely that it will be widely adopted in its current form.\n- The paper does not provide details about the size of the models (e.g. in terms of number of trainable parameters). This problematic since it remains unclear if the performance improvement stems from the increases expressiveness or is simply due to a larger model size.\n- Highlighting the top three models (e.g. in Table 1) is highly misleading since only one version of each prior method is compared against 16 versions of the proposed idea. In general, this comparison does not make sense since the propose method has 16 trials to achieve a good result while all reference models only have a single trial.\n- No code is provided to verify the results.", "summary_of_the_paper": "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.", "summary_of_the_review": "To summarize, the paper proposes a fairly simple but reasonable idea that achieves some improvements. However, since the improvements are rather small and the complexity of the model increases substantially, it is unclear if this idea will receive a lot of attention.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Improving the expressiveness of GNN is an important problem in the current graph learning community. Its key idea is to generate subgraphs from the original graph, then encode the subgraphs into the message passing process of GNN. The proposed method is proven to be strictly more powerful than 1-WL. The authors also quantize how design choices such as the subgraph selection policy and equivariant neural architecture can affect the architecture’s expressive power.

After the rebuttal, all reviewers are glad to accept this submission.

During the discussion, while reviewer B3oK has shown some concerns on the concurrent works in NeurIPS 2021, it should not affect the decision of the submission once the authors have discussed them in the main text. The authors have done this in their revision, thus an acceptance (spotlight) is suggested.
Decision: Accept (Spotlight)