Ordered Subgraph Aggregation Networks
Authors: Chendi Qian
Gaurav Rattan
Floris Geerts
Mathias Niepert
Christopher Morris
Venue: NeurIPS 2022 Accept (2022)
Keywords: GNNs
expressivity
subgraphs
differentiating through discrete structures

Abstract: Numerous subgraph-enhanced graph neural networks (GNNs) have emerged recently, provably boosting the expressive power of standard (message-passing) GNNs. However, there is a limited understanding of how these approaches relate to each other and to the Weisfeiler-Leman hierarchy. Moreover, current approaches either use all subgraphs of a given size, sample them uniformly at random, or use hand-crafted heuristics instead of learning to select subgraphs in a data-driven manner. Here, we offer a unified way to study such architectures by introducing a theoretical framework and extending the known expressivity results of subgraph-enhanced GNNs. Concretely, we show that increasing subgraph size always increases the expressive power and develop a better understanding of their limitations by relating them to the established $k\mathsf{\text{-}WL}$ hierarchy. In addition, we explore different approaches for learning to sample subgraphs using recent methods for backpropagating through complex discrete probability distributions. Empirically, we study the predictive performance of different subgraph-enhanced GNNs, showing that our data-driven architectures increase prediction accuracy on standard benchmark datasets compared to non-data-driven subgraph-enhanced graph neural networks while reducing computation time. 

Ordered Subgraph Aggregation Networks
Chendi Qian"
Gaurav Rattan" Department Computer Science RWTH Aachen University
Department of Computer Science TU Munich
Floris Geerts
Christopher Morris
Department of Computer Science University of Antwerp
Department of Computer Science RWTH Aachen University
Mathias Niepert
Department of Computer Science University of Stuttgart
Abstract
Numerous subgraph-enhanced graph neural networks (GNNs) have emerged recently, provably boosting the expressive power of standard (message- GNNs. However, there is limited understanding of how these approaches relate to each other and to the Weisfeiler- Leman hierarchy. Moreover, current approuches either use all subgraphs a given size, sample them uniformly random, learning to select subgraphs a data-driven manner. Here, we offer a unified way to study such architectures by introducing theoretical framework and extending the known expressivity results of subgraph-enhanced GNNs. Concretely, we show that increasing subgraph size always increases the expressive power and develop better understanding of their limitations by relating them to the established k-WL hierarchy. In addition, we explore different approaches for learning to sample subgraphs using recent methods for backpropagating through complex discrete probability distributions. Empirically, we study the predictive performance of different Sbograph-enhancee GNNs, showing that our data-driven architectures increase prediction accuracy on standard benchmark datasets compared to non-data-driven subgraph-enhancer graph neural networks while reducing computation time.
hand-crafted heuristics instead of
Introduction
Graph-structured data are ubiquitous across application domains ranging from chemo- and bioinformat- ies [Barabasi and Oltvai, 2004, Jumper et al., 2021, Stokes al., 2020) to image [Simonovsky and Komodakis, 2017] and social-network analysis [Fasley and Kleinberg, 2010]. Numerous approaches for graph-based machine learning have been proposed, most notably those based on graph kernels [Borgwardt al., 2020, Kriege et al., 2020] using graph neural networks (GNNs) [Chami et al., 2020, Gilmer et al., 2017, Morris al., 2021]. Here, graph kernels based on the 1-dimensional Weisfeiler-Leman algorithm (1-WL) [Weisfeiler and Leman, 1968], simple heuristic for the graph isomorphism problem, and corresponding GNNs [Morris et al., 2019, Xu et al., 2019], have recently advanced the state-of oatte--f-th-aatt be-arrt in supervised vertex- and graph-level learning. However, the 1-WL and GNNs operate via local neighborhood aggregation, missing crucial patterns in the given data while more expressive architectures based on the k-dimensional Weisfeiler-Lemon algorithm (k-WL) [Azizian and Lelarge, 2020, Maron al., 2019, Morris et al., 2020b, 2021, 2022] may not scale to larger graphs.
*These authors contributed equally.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Hence, several approaches such as Bevilacqua et al. [2021]. Cotta et al. [2021], Li et al. [2020], Papp et al. [2021], Thiede et al. [2021], You al. [2021] and Zhao al. [2021] have enhanced the expressive power of GNNs, by removing, extracting, or marking (small) subgraphs, so to allow GNNs to leverage more structural patterns within the given graph, essentially breaking symmetries induced by the GNNs' local aggregation function. We henceforth refer to these approaches as subgraph-enhance enhanced GNNs.
Present work First, bring some order the multitude of recently proposed subgraph-enhaneed GNNs, we introduce a theoretical framework to study these approaches" expressive power in a unified setting. Concretely,
we introduce k-ordered subgraph aggregation networks (k-OSANs) and show that they capture most of the recently proposed subgraph-enhanced GNNs.
We show that any k-OSAN upper bounded by (k + 1)-WL terms of expressive power and show that O-OSANs and k-WL are incomparable in terms of expressive power. Consequently, we obtain new upper bounds on the expressive power of recently proposed subgraph-enhanced GNNs.
We show that increasing i.e., using larger subgraphs, always leads an increase in expressive power, effectively showing that k-OSAN, form a hierarchy.
Second, most approaches consider all subgraphs or use hand-crafted heuristics to select them, e.g., by deleting vertices edges. Instead, we leverage recent progress in kack-propagating through discrete structures using perturbation- based differentiation [Domke, 2010, Niepert et al., 2021] to sample subgraphs in data-driven fashion, automatically adapting the given data distribution. Concretely,
we explore different strategies to sample subgraphs leveraging the I-MLE framework [Niepert et al., 2021], resulting in the data-driven k-OSAN architecture.
We show, empirically, that data-driven k-OSANs increase prediction accuracy on standard benchmark datasets compared to non-data-driven subgraph-enhanced GNNs while vastly reducing computation time.
1.1 Related work
In the following, we discuss related work relevant to the present work; see Appendix A for an extended
discussion.
GNNs Recently, GNNs [Gilmer et al., 2017, Scarselli et al., 2009] emerged as the most prominent graph representation learning architecture. Notable instances of this architecture include, e.g., Duvenaud et al. [2015], Hamilton et al. [2017] and Veličković et al. [2018), which can be subsumed under the message-passing framework introduced in Gilmer al. [2017]. In parallel, approaches based on spectral information were introduced in, e.g., Defferrard et al. [2016]. Bruna et al. [2014). Kipf and Welling [2017] and Monti al. [2017] all of which descend from early work in Baskin et al. [1997], Kireev [1995], Micheli and Sestito [2005], Merkwirth and Lengauer [2005], Micheli [2009]. Scarselli et al. [2009] and Sperduti and Starita [1997].
Limits of GNNs and more expressive architectures Recently, connections between GNNs and Weisfeiler-Lenan type algorithms have been shown [Azizian and Lelarge, 2020, Barceló al., 2020, Chen et al., 2019b, Geerts et al., 2020, Geerts, 2020, Geerts and Reutter, 2022, Maehara and NT, 2019, Maron al., 2019, Morris et al., 2019, 2022, Xu et al., 2019]. Specifically, Morris et al. [2019] and Xu et al. [2019] showed that the expressive power of any possible GNN architecture is limited by the 1-WL in terms of distinguishing non-isomorphic graphs.
Recent works have extended the expressive power of GNNs c.g., by encoding vertex identifiers [Murphy al., 2019, Vignac et al., 2020], using random features [Abboud et al., 2020, Dasoulas et al., 2020, Sato et al., 2020], homomorphism and subgraph counts [Barceló et al., 2021, Bouritsas et al., 2020, NT and Machara, 2020], spectral information [Balcilar et al., 2021]. simplicial and cellular complexes [Bodnar et al., 2021b,a), persistent homology [Horn et al., 2021], random walks [Tönshoff et al., 2021], graph decompositions [Tallk et al., 2021], or distance [Li et al., 2020] and directional information [Beaini et al., 2020]. See Morris et al. [2021] for an in-depth survey on this topic.
Subgraph-enhanced GNNs Most relevant to the present work are subgraph-enhunced GNNs. Cotta et al. [2021] and Papp et al. [2021] showed how to make GNNs more expressive by removing one or more vertices from given graph and using standard GNN architectures to learn vectorial representations of the

---

resulting subgraphs. The approaches either consider all possible subgraphs or utilize random sampling to arrive at more scalable architectures. Cotta al. [2021] showed that by removing one or two vertices, such architectures can distinguish graphs the 1-WL and 2-WL, respectively, are not able to distinguish. Extensions and refinements of the above were proposed Bevilacqua et al. [2021], Papp and Wattenhofer [2022], Thiede et al. [2021], You et al. [2021]. Zhang and Li [2021] and Zhao et al. [2021], see Papp and Wattenhofer [2022] for an overview. For example, Bevilacqua et al. [2021] generalized several ideas discussed above and proposed the ESAN framework in which each graph is represented as multiset of its subgraphs and processed them using an equivariant architecture based on the DSS architecture [Maron et al., 2020] and GNNs. The authors proposed several simple subgraph selection policies, e.g.. edge removal, ego networks, or vertex removal, and showed that the architecture surpasses the expressive power of the 1-WL. Moreover, Frasca et al. [2022] presented novel symmetry analysis unifying series of subgraph-enhanced GNNs, allowing them to upper-bound their expressive power and to define a systematic framework to conceive novel architectures in this family. We note here that the above works, unlike the present one, mostly do not study the approaches' expressive power beyond (folklore or non-oblivious) 2-WL and do not compare all to the (folklore or non-oblivious) 3-WL, while our analysis works for the whole k-WL hierarchy.
See Appendix A for detailed overview of recent progress in differentiating through discrete structures.
2 Preliminaries
As usual, for n 2 1, let [m] (1, (I,...,ny) n C N. We use H... B to denote multisets, i.e., the generalization of sets allowing for multiple instances of each of its elements.
A graph G is pair E(G) with finite sets of vertices V(G) and edges E(G) S {(u, v) S V(G) u # v}. If not otherwise stated, we set n == [V)]. For ease of notation, we denote the edge {u.v) in E(G) by (u, v) or (v. u). In the case of directed graphs, E C {(u, r) E V x V
&f v).
A labeled graph G is a triple (V, E.I) with (vertex) coloring or label function 1: V(G) - N. Then
I(1) is a label of for in V(G). The neighborhood of v in G is denoted by Nc(v) = {u E ((G)
{u, u} E } and the degree of a vertex v is [N)( For S S VG), the graph G[S] = (S, Es) is the subgraph induced by S. where Eg == v),, E E(G) U..
Two graphs G and H are isomorphic and we write G ~ H if there exists a bijection yp: V(G) - V(H) that preserves the adjacency relation, i.c.. (u, v) is in E(G) if and only if (yp()), (v)) is in E(H). Then o is an isomorphism between G and H. Moreover, we call the equivalence classes induced by the relation ~ isomorphism types. In the case of labeled graphs, we additionally require that ((v) ((p(t)) for v in V (G). We further define the atomic type atp: V(G)* + N such that atp(v) atp atp(w) (w) for V. w E V(G if and only if the mapping pp: V(G)* + V(G)* where + we induces a partial isomorphism, i.e., we have U. by + w, = W and (v,, vy) E E(G) = ((v,)))(((,)
E(G). Let v be a tuple in V(G)* for k >>0 O, then G[v] is the ordered k-vertex subgraph induced by the multiset of elements of v, where the vertices are labeled with integers from [k] corresponding to their positions in v. Moreover, let t(G[vl) == v. i.e., the k-tuple v underlying the ordered ve-eettx subgraph G[v). We denote the set of all ordered k-vertex subgraphs of a graph G by Gg. Finally, let G be the set of all vertex-labeled labeled graphs.
The 1-WL and the k-WL The 1-WL color refinement is simple heuristic for the graph isomorphism problem, originally proposed by Weisfeiler and Leman [1968].2 Intuitively, the algorithm determines if two graphs are non-isomorphic by iteratively coloring or labeling vertices. Given initial coloring or labeling of the vertices of both graphs, e.g., their degree or application-specifi information, in each iteration, two vertices with the same label get different labels if the number of identically labeled neighbors is not equal. If, after some iteration, the number of vertices annotated with a specific label is different in both graphs, the algorithm terminates and stable coloring (partition) is obtained. We can then conclude that the two graphs are not isomorphic. It is easy to see that the algorithm cannot distinguish all non non-isomonye isomorphic graphs [Cai al., 1992]. Nonetheless, it is a powerful heuristic that can successfully test isomorphism for a broad class of graphs [Babai and Kucera, 1979].
Formally, let G (V, F.,)) be labeled graph. In each iteration, i > 0, the 1-WL computes a vertex coloring C. : V(G) + N, which depends on the coloring of the neighbors. That is, in iteration i > 0, we
*Strictly speaking, the 1-WL and color refinement are two different algorithms. That is, the 1-WL considers neighbors and non non-neight neighbess to update the coloring. resulting in slightly higher expressive power when distinguishing vertices in given graph, see Grohe [2021] for details. For brevity, consider both algorithms to be equivalent.
3

---

set
(v) = RELABEL (I)) (C;) eE No(u)D)),
where RELABEL injectively maps the above pair to a unique natural number, which has not been used in previous iterations. In iteration 0, the coloring Cj == I. To test if two graphs G and H are non-isomorphic, we run the above algorithm in "parallel" on both graphs. If the two graphs have a different number of vertices colored in N at some iteration, the 1-WL distinguishes the graphs non-isomorphic. Moreover, the number of colors between two iterations, and (i + 1), does not change, i.e. the cardinalities of the images of C and C are equal, the algorithm terminates. For such i, we define the stable coloring Che (v) = C. (v) for in (G).. The stable coloring is reached after most ( iterations [Grohe, 2017].
Due to the shortcomings of the 1-WL or color refinmmen in distinguishing non-isomorphic graphs, several researchers [Babai, 1979, 2016, Immerman and Lander, 1990], devised a more powerful generalization of the former, today known as the k-dimensional Weisfeiler-Leman algorithm (k-WL); see Appendix B for detailed description.
Graph Neural Networks Intuitively, GNNs learn vectorial representation, i.e., a di d-dimensional vector, representing each vertex a graph by aggregating information from neighboring vertices. Formally, let G = (V, E, 1) be labeled graph with initial vertex features h E Rd that are consistent with 1. That is, each vertex is annotated with feature h (0) E Rd such that h h! if ((u) I(v), e.g., one-hot encoding of the labels (()) and l(v). Alternatively, h can be an arbitrary real-valued feature vector or attribute of the vertex v, e.g., physical measurements in the case of chemical molecules. A GNN architecture consists of a stack of neural network layers, i.e., a composition of parameterized functions. Similarly to 1-WL, each layer aggregates local neighborhood information, i.c., the neighbors' features, around each vertex and then passes this aggregated information on to the next layer.
Following, Gilmer et al. [2017] and Scarselli al. [2009], in each layer, i O, compute vertex features
(++1) UPD((+)) hh!
(GG
((h No(()H)) Rd
where (PD(++1) and (G+ may be differentiable parameterized functions, e.g., neural networks. In the case of graph-level tasks, e.g., graph classification, one uses
hg = READOUT (Eh!") | (()))) E
(1)
to compute a single vectorial representation based on learned vertex features after iteration T. Again, READOUT may be a differentiable parameterized function. To adapt the parameters of the above three functions, they are optimized end-to-end, usually through variant of stochastic gradient descent, e.g., [Kingma and Ba, 2015), together with the parameters of neural network used for classification or regression.
The Weisfeiler-Leman hierarchy and germutation-invariat function approximation The Weisfeiler- Leman hierarchy is a purely combinatorial algorithm for testing graph isomorphism. However, the graph isomorphism function, mapping non-isomorphic graphs to different values, is the hardest to approximate permutation- invariant
innvaaaiionnnnariaattt function. Hence, the Weisfeiler- hierarchy has strong ties to GNNs' capabilities to approximate permutation-invarian or equivariant functions over graphs. For example, Morris et al. [2019]. Xu al. [2019] showed that the expressive power of any possible GNN architecture is limited by 1-WL in terms of distinguishing non-isomorphic graphs. Azizian and Lelarge [2020] refined these results by showing that if an architecture capable of simulating k-WL and allows the application of universal neural networks on vertex features. it will be able to approximate any ceamutatioo-equivaat
function below the expressive power of k-WL; see also Chen et al. [2019b]. Hence, if one shows that one architecture distinguishes more graphs than another, it follows that the corresponding GNN can approximate more functions. These results were refined in Geerts and Reutter [2022] for color refinement and taking into account the number of iterations of k-WL.
"Strctlly speaking, Gilmer et al. [2017] consider slightly more general setting which vertex features are computed by h (1+1) = (PD(++) ()) AGG(++1) (H((()) (9 (o, u)) | No)))

---

Ordered subgraph Weisfeiler-Leman and MPNNS
the following, we introduce variant 1-WL, denoted k-ordered subgraph WL (k-OSWL). Essentially, the k- k-OSWL labels or marks ordered subgraphs and then executes 1-WL on top of the marked graphs, followed by an aggregation phase. Although unordered subgraphs are also possible, ordered ones lead to more expressive architectures and also encompass the unordered case; see Appendix F.I for a discussion. To make the procedure permutation-invariann we consider all possible ordered subgraphs. Based on the ideas of k-- L-OSWL, then introduce k-OSANs, which can be seen neural variant of the former, allowing us to analyze various subgraph-enhanced GNNs.
3.1 Ordered subgraph WL
We now describe the algorithm formally. Let G be graph, and let E Gj. be ordered vevertex subgraph. Then L-OSWLL computes a vertex coloring, similarly to 1-WL, with the main distinction that structural graph information related to the ordered subgraph G[(u, t(g)),, where v is vertex in V(G).
More precisely, at each iteration i 2 0, k-OSWL computes coloring C V(G) G2 - N where we interpret elements (u, g) E V(G) x GR as a vertex a along with an ordered k-vertex subgraph. Given an ordered k-vertex subgraph g E Gk. initially, for = O, we set Co(u, g) == atp(r, t(g)), and for >> O, we set
C++1V g) = RELABEL ((C,(o. g). (C((u, u DB))
where D is either (t) V(G). We compute the stable partition analogously to 1-WL. Finally, to compute a single color for a vertex v, we aggregate all ordered k-vertex subgraphs, ie., we compute
C(v) = RELABEL Coo (v, g E GxB).
In other words, can regard the k-OSWL as rumning 1-WL in parallel over n² graphs, one for each ordered k-vertex subgraph g E Gg, followed by combining the colors of each vertex in these graphs Furthermore, by restricting the number of considered subgraphs, the algorithm allows for more fine-grate fine-grained control over the trade-off off between scalability and expressivity. Note that 0-OSWL is equal to 1-WL. We also define variation of the l 1-OSSW,, denoted verrer-subgraph k- k-OSWL, which, unlike Equation (2), first computes a color (gg for each ordered k-vertex subgraph g by aggregating over vertices; see Appendix for details.
We remark that in contrast to k-W which has to update the coloring of all n ordered k-vertex subgraphs in complicated manner, the computation of k-OSWL's coloring relies the simple and casy-to-implement 1-WL. Furthermore, k-OSWL's computation can be either done in parallel or sequentially across all vertices and n² graphs. Despite its simplicity, in Section 3.2, we will show that the k-OSWL has high expressivity.
3.2 Ordered subgraph MPNNs
In the following, study the expressivity of subgraph-enhanced GNNs, we introduce k-ordered subgraph MPNNs (k-OSANss) which can viewed as neural variants of the k-OSWL. At initialization, k-OSANs learn two features for each element in G and each vertex
UPD(atp(r, t(g))) e Rdd and Te.g UPD (atp(u, t(g)))
where UPD and UPD, are differentiable, parameterized function, e.g., neural network. Additional vertex features can be concatenated to the first feature. We use the second feature Tv. to select admissible ordered subgraphs for the vertex u; see below. Now in each layer (i + 1), we update the feature of vertex v with regard to the k-ordered subgraph as
(++1) h ggg = (++1) h
AGG
((h(() u E))):
where is either (v) or (G). After T such layers, for each vertex v, we then learn a joint feature over all k-ordered subgraphs. i.e., we apply subgraph aggregation
h (T) = SAGG ( hh.g E GR S.t. TuR + 0.).
(3)
5

---

Here, we leverage W. We.g # O to select subset of the set of k-ordered subgraphs. Finally, analogous to GNNs, we use a READOUT layer to compute a single graph feature. Again, (GG(++1), (PD(++1) READOUT, and SAGG are differentiable, parameterized functions, c.g., neural networks.
We also define variation of k- k-OSANs, denoted vertex-subgraph k: OSOANN,, which, unlike Equation (3), first compute a color for each ordered k-vertex subgraph; see Appendix E for details.
Expressive power of k-OSANs In the following, we study the expressive power of k-OSANs. The first result shows that any possible k-OSAN has at most the expressive power of k-OSWL in terms of distinguishing non-isomorphic graphs. Further, k-OSANs are in principle capable of reaching k-OSWL's expressive power. Hence, the k-OSWL upper bounds k-OSANs ability to represent permutation-invant functions.
Proposition For k 2 1, holds that k-OSANs are upper bounded by k-OSWL in terms of distinguishing non-isomorphic graphs. Further, there exists k- k-OSAN instance that has exactly the same expressive power as the k- I-OS...
The following result shows that any possible k-OSAN is upper-bounded by the (k + 1)-WL in terms of dis- tinguishing con-isomorphic graphs while the expressive power k--SANs and the k-WL are incomparable. That is, there exist non-isomorphic graphs k-WL cannot distinguish while k- A-OSANs can and vice versa.
Proposition 2. For all & 2 1, it holds that (Is + 1--WL stricly more expressive than k-OSANN and there exist non-isomorphic graphs k-WL cannot distinguish while k-OSANs can and vice versa.
Finally, the following results shows that increasing the size of the subgraphs always leads strietly more expressive k-OSANs.
Theorem 3. For all & 1, it holds that (A: + 1)-OSANs is strictly more expressive than k-OSANs.
Subgraph-enhanced GNNs captured by k-OSANs To exemplify the power and generality k-OSANs, show how k-OSANs cover most subgraph-enhaneee GNNs; see Appendix F for a thorough overview. We say that OSOSAN capture a subgraph-enhancee GNN G if there exists a k-OSAN instance that is at least expressive as G.
The first results shows that k- U-OSANs capture k-marked GNNs (k-mGNNs) [Papp and Wattenhofer, 2022] and k-reconstruction GNNs (k-recGNNs) [Cotta et al., 2021]. For both approaches, the sets of l vertices to be marked or deleted correspond to unordered k-vertex subgraphs. It then suffices to ensure that the update and aggregation functions in the k-OSANs treat the vertices in the selected k-vertex subgraphs as being marked or deleted.
Proposition 4. For k 2 1, k-OSANs capture k-mGNNs and vertex-subgraph k-OSANs capture k-recGNNs.
Further, 1-OSANs capture identity-aware GNNs (idGNNs) [You et al., 2021], GNN As Kernel (kernelGNNs) [Zhao al.. 2021], and nested GNNs (nestedGNNs) [Zhang and Li, 2021]. Intu- itively, in these approaches GNNs are used locally around each vertex. It thus suffices to ensure that the update and aggregation functions in the 1-OSANs use the selected single vertex subgraph only pass messages locally.
Proposition 5. 1-OSANs capture idGNNs, kernelGNNs, and nestedGNNs.
Finally, k-OSANs capture the DS-GNNs with the vertex-deleted policy [Bevilacqua et al., 2021].* Proposition 6. Vertex-subgraph t-OSSNs capture DS-GNNs with the k-vertex-deleted policy.
We note that the above result can be further extended to accommodate the edge-deleted and ego-networks policy from Bevilacqua et al. [2021]; see Appendix F.
Importantly, by viewing existing subgraph-enhanen enhanced GNNs as k- k-OSANs we immediately gain insights into their expressive power. Previous results primarily focused on showing more expressivity than 1-WL.
We note here that it is an open question if subrex-subgraph k-OSANs also capture the more general OSS-GNNs [Bevilacqua al., 2021].

---

4 Data-driven Subgraph-enhanced GNNs
In the above section, we thoroughly investigated the expressive power of subgraph-enhanced GNNs. Specifically, we showed that they are strictly limited by the (k + 1)-WL and that they can distinguish graphs which are not distinguishable by k-WL. As indicated by Proposition I and to reach maximal expressive power, however, we need to consider all possible ordered subgraphs, resulting in an exponential running time. Hence, in this section, we leverage the I-MLE framework [Niepert et al., 2021J, to sample ordered subgraphs in data-driven fashion. We first address the problem of learning the parameters of probability distribution over ordered subgraphs using a GNN. Secondly, we show how to approximately sample from this intractable distribution. Subsequently, these subgraphs used within a K-OSAN to compute a graph representation. Finally, we propose a gradient estimation scheme that allows us to use backpropagation in the resulting discrete-continuuus architecture.
Parameterizing probability distributions over subgraphs Contrary to existing approaches, which often consider all possible subgraphs or sample fraction of subgraphs uniformly at random, our method maintains probability distribution over (ordered) subgraphs. Let G be a graph where each vertex v has an initial feature h which we stack row-wise over all vertices into the feature matrix H E Raxd Further, let hw, 9 x Raxd -> Imxx be a permutation-equue -qquivaaaion function, e.g., a message-passingg GNN, parameterized by W1, called upstream model, mapping a graph G and its initial features H to a parameter matrix
= lww, (G, H) E R
Intuitively, each parameter 0z is an unnormalized prior probability of vertex j being part of the ith sampled subgraph of G. Let 0 == (oa...., ...) for i E [mn]. We use these to parameterize in probability distributions p(z; 0.), for E [m]] over vector encodings of ordered k-vertex subgraphs of G, i.c.
p(z; 0,) = { exp ((z, - A(O))) i
(4)
otherwise,
where (1 is the standard inner product and A(O,) is the log- log-partition, funtitionnuuncion defined as A(O:) = log (Ezez exp ((z, 0+))). Furthermore, for a distribution over unordered k-vertex subgraphs, Z is the set of all binary n-component vectors with exactly k non-zero entries indicating which vertices are part of subgraph of G. Hence, there is a bijection between Z and the set of unordered k-vertex subgraphs of G. For distribution over ordered vevertex subgraphs, the set Z is the set of all vectors in [k]" with k non-zero entries. For each non-zen entry z; for 2 E 2 holds that x; = j if and only if vertex é has rank k + 1 - j in the ordered subgraph, encoding the position in the ordered graph. This encoding is required for the gradient computation we perform later. For instance, in an ordered 5-vertex subgraph, if a node has rank 1 but should have rank 5 to obtain lower loss, then the gradient of the downstream loss is proportional to 5 - 1 = 4. Similarly, if a node i is not part of the ordered subgraph, that is, 2, = 0 but should be in position of the ordered subgraph, then the gradient of downstream loss is proportional to 0 6-5 5. For any i E [ki] with # j we have that z; # zj. Hence, again, there is a bijection between Z and the set of ordered k-vertex subgraphs of G.
Efficient approximate sampling of subgraphs Computing the log- par-paatition function and sampling exactly from the probability distribution in Equation (4) is intractable for both ordered and unordered graphs. Since it is tractable, however, to compute a configuration with a highest probability, a maximum a posteriori (MAP) configuration 2" =0.). we can use perturb-an and and [Papandreou and Yuille, 2011, Niepert et al., 2021] to sample approximately. For unordered graphs, determining the top-k values in 0g suffices, while for ordered graphs, we additionally require their rank. Therefore, the worst-case running time of computing z" (0.) for ordered graphs of size k is in O(n + 1 log k). That is, we first use a selection algorithm to find the kth largest element E in the list of weights, taking time O(n), e.g., using the Quickselect algorithm. Now, we go through the list again and select all entries larger to E, taking time (n). Finally, we sort the k values.
Now, to use perturb-and and---nnd-- to approximately sample the i-th ordered kevertex subgraph g; from the above probability distributions, compute
g: = adj (z (0. + E.)) with E (())))),
where p(e) is a noise distribution such as the Gumbel distribution and adj converts the above vector encoding of the (ordered) subgraph to an n n adjacency matrix as follows. The jth row or column encodes the vertex of the ordered subgraph with rank j and its incident edges within the ordered subgraph. All other
7

---

entries are set to 0, i.e., they are masked out. We therefore sample multiset of (ordered) subgraphs = kgg ..... 9m I S Gg, which act as the input to a k-OSAN instance fw.. called downstream model, where π F.. # 0 for e E V(G) if g E S, to compute the target outputs
fw. (G, H. 9.................. 9.
Backpropagating through the subgraph distribution Now that we have outlined a way to approximately sample subgraphs, we still need learn the parameters
(W1, I. W2) of the upstream and downstream model. Hence, given set of examples {[G,, H 9, ) we are concerned with finding approximate solutions to min I/N Ej L(G, H, w), where L is the expected training error
L(G, H. プト w) Eg -p(=:0;) ) (fw: (G, H. Kg 1.......9 9 b)).
(5)
with 0 = hww, (G, H) and L: y' y - > is point-wise loss function. The challenge of training model as defined in Equation (5) to compute VoL(G, H, wy), i.e., the gradient with respect to the parameters 0 of the probability distribution for the expected loss. In this work, we utilize implicit maximum likelihood learning, a recent framework that allows us to use algorithmic solvers of combinatorial optimization problems as black-box components [Rolinek et al., 2020, Niepert et al., 2021]. A particular instance of the framework uses implicit differentation via perturbation [Domke, 2010]. We derive the gradient computation for single ordered subgraph g: to simplify the notation. We compute the gradients of the downstream loss with respect to parameters 0; as
V L(G, H. Uj: w) = Bewo((e [yA (x" (0, + e2)
- z" (0.+c,
where A > O and v., the approximated gradient for single vertex is defined as
v = agg V (Sw, (G, H, (g. w E Nc(v))),
with v E V(G). Here, agg can be any aggregation function such as the element-wise sum or mean. Hence, to approximate the gradients with respect to the parameter 0... which corresponds to vertex v of the imput graph, we aggregate the gradients of the downstream loss with respect to all edges (v, w) incident to vertex e in the original graph.
Hence, the above techniques allow us efficiently learn sample subgraphs, which are then fed into k-OSAN to learn graph representation while optimizing the parameters of all components in an end-to-end fashion.
Experimental evaluation
Here, we aim to empirically investigate the learning performance and efficiency of data-driven subgraph- enhanced GNNs, instances of the k-OSAN framework, compared to non-data-driven ones. Specifically, we aim to answer the following questions.
Do data-driven subgraph-enhanced GNNs exhibit better predictive performance than non-data-driven ones?
Q2 Does the graph structure of the subgraphs sampled affect predictive performance?
Q3
Does data-driven sampling have an advantage in efficiency and predictive performance when used within slate-of-the-aas sabbraph-enhancee GNNs?
All experimental results are fully reproducible from the source code provided at https: com/ Spazierganger/D5..
Datasets To compare our data-driven, subgraph-enhanced GNNs to non-data-driven ones and standard GNN baselines, we used the ALCHEMY [Chen al., 2019a], the QM9 [Ramakrishnan et al., 2014, Wu et al., 2018], DGBG-MOLESSE
[Hu et al., 2020], and the ZINc [Dwivedi et al., 2020, Jin et al., 2017] graph-level regression datasets; see Table in Appendix C for dataset statisties and properties. In addition, we used the ExP dataset [Abboud et al., 2020] to investigate the additional expressive power of subgraph-enhanced GNNs over standard ones. Following Morris al. [2020b], we opted not to use the 3D-coordinates of the ALCHEMY dataset to solely show the benefits of the data-driven subgraph-enhancee
8

---

Table 1: Results on large-scale regression datasets, data-driven versus non- datdda---diven subgraph sampling.
(a) Results for the OGRG-MoI FSO. dataset.
(b) Result for the ALCHEMY datasct.
Method
RSMSE.
Method
MAE
Baseline
1,353 21/093
Raselline
11.12 g0.9
OPERAT
TYPs.
SUBG
OPERAT.
TYPE
4UBG..
J-MLE
Randrm
Deloie
Veries
1,063 65.033
1,215
Random I-MLE
Delete
Verter
13.26 10.4
8.78 29.2e
Random I-MLE
Deleso
Vertex
10
1.325 LEA05
Random I-MI E
Delete
Vertex
10
12.11 10.31
8.87 10
Random 1-MLE
Delex
Delese
Vestes
Vartes
2
2
0,965
1,13P or
1,081 14/01
Random I-MI F
Delete
Verter
12,06 s0.25
9.01 s0
Rasalie
Delete
Verte
5
0.002 a1.115
1.115
Random I-MI
Delete
Vertex
10.29
Rasslien J.ME
Delete
Vertes
5
10
1,347 21/01
1.186
Random I-MLE
Delete
Edge
11.00 so.03
10.80 20:31
Random I-MLE
Select
Vertes
10
1.328 LE/G1
1.009
Random I-MLE
Delete
Edge
3
10.79 s0.54
10.06 so
I-MEEE
Delete
Eddge
1,240
1.105
Random I-MLE
Delete
Edge
3
9:15 20.12
9.08 a0.33
Kandom I-MLE
Delese
Pdge
10
1,066 acars
1,152 21.0
Random T-MLE
Select
Vertex
3
11.48
50:14
1-MLE
Rddgo
1,052
Random I-MI
Select
Edge
Kandrmm 1-MLE
Rarslom J. MLLE
Delete
Deloie
Edge
10
0,509 6C.184
1,077 1eams
1,009
1.491 o5
Random I- F
Delete
Select
I-Egoo
Egg
3
10.97
11.15 23
14.08 20.40
8.05 20:79
T-ML
13.83 2//0
GNNs regarding graph structure. All datasets, excluding ExP and OGBG-MOLESOL, are available from Morris et al. [2020a].5
Neural architectures and experimental protocol For all datasets and architectures, we used the competitive GIN layers [Xu et al., 2019] for the baselines and the downstream models. For data with (continuous) edge features, we used 2-layer MLP to map them to the same number of components as the vertex features and combined them using summation. We describe the upstream and downstream models' architecture used for each dataset in the following. We stress here that we always used the same hyperparameters for the downstream model and the baselines.
Sampling subgraphs Since the number of unordered k-vertex subgraphs is considerably smaller than the number of ordered k-vertex subgraphs, we opted to consider unordered k-vertex subgraphs; see also Appendix F.1. Further, since vertex- -sugrr-h k: OSANs, see Appendix E, are easier to implement efficiently and are closer to DS-GNNs variant of ESAN [Bevilacqua et al., 2021], we opted to use them for the empirical evaluation. In addition, we used a simple GNN architecture for the upstream model to compute initial features for the subgraphs for ease of implementation. We experimented with selecting and deleting a various number of vertices, edges, and subgraphs induced by k-hop neighborhoods (k-Ego) for all datasets; see Appendix C for details.
Upstream models For all datasets and experiments, we used a GCN model [Kipf and Welling, 2017] consisting of three GCN layers, with batch norm and ReLU activation after each layer. We set the hidden dimensions to that of the downstream model one. The model either outputs the vertex or edge embeddings according to the task. We computed edge embeddings based on the vertex features of the incident vertices after the last layers and the edge attributes provided by the dataset.
When sampling multiple subgraphs with I-MLE, they tend to have similar structures. In other words, I-MLE learns similar distributions in different channels of the neural network. This phenomenon is not in our favor, as we need to cover the original full graph as much as possible. To mitigate this issue, we propose auxiliary loss for the diversity of subgraphs. We calculate the cosine similarity between the selected vertex or edge masks of every two subgraphs and try to minimize the average similarity value. We tune the weight for the auxiliary loss on the log scale, e.g., 0.1, 1, 10, and so on.
Downstream and baseline models See Appendix A for a detailed description of the architecture used for the downstream and baseline models, and how we processed subgraphs. For processing the subgraphs, we performed similar steps like ESAN. We first applied intra-subgraph aggregation for the vertices within each subgraph and obtained graph embeddings for each subgraph. After that, performed inter-subgraph mean
Phttps://chrsmm .it.ssg.tttuu................... ho/dattstts//
9

---

pooling to obtain single embedding vector for the original graph. It is worth noting that ESAN does not exclude the vertices deleted during graph pooling but removes the adjacent edges of those nodes, In our experiments, we masked out the deleted or unselected nodes.
See Appendix C for further details the experiments.
5.1 Results and discussion
In the following, we answer the research questions Q1 to Q3.
A1 See Tables 1, 2a, 4 and (in the appendix). On all five datasets, the subgraph-enhanced GNN models based on I-MLE beat the random baseline, excluding edge sampling configurations on the ALCHEMY and the QM9 dataset; see Tables 1b and 2a. For example, on the DGBG-MOLESON the average gain over the random baseline is over 11%. Similar improvements can be observed over the other four datasets. Moreover, the results on the ExP dataset, see Appendix C, clearly indicate that the added expressivity of the (data-driven) subgraph-enhancee GNNs translates into improved predictive performance. The data-driven subgraph-enhanced GNNs improve the accuracy of the non-subgraph-enhancce GNN by almost 50% in all configurations while improving over the random subgraph-enhanced GNN baseline by almost 6%. The data-driven
GNNs also clearly improve over the mhon-uubrrapl--ehanced)) GNN baseline on four out of five datasets.
A2 See Tables and 2a (in the appendix). Deleting or selecting subgraphs leads to a clear boost in predictive performance across datasets over the random baseline while also improving over the non-subgraph-enlen GNN baseline. Further, on all datasets, learning to delete or select k-hop neighborhood subgraphs for k E {2,3} leads to a clear boost over the random as well as non-subgraph-ennant However, the number of deleted vertices seems to affect the predictive performance. For example, on the OGBG-MOLESOL dataset, going from deleting one 2-vertex subgraph to one 10-vertex subgraph leads to a drop in performance. Hence, the drop in performance of the latter is in contrast to our theoretical findings. i.e., larger subgraphs lead to improved expressivity, indicating that more work should be done to understand Sabgrapp-enhaneee GNNs' generalization ability. Interestingly, deleting edges did not perform as well as deleting vertices or other subgraphs. We speculate that a more powerful edge embedding method is needed here, which computes edge features directly instead of learning them from vertex features.
baselines.
A3 See Table 2b (in the appendix). The I-MLE- Ebsed ESAN severely speeds up the computation time. That is, across all configurations, we achieve a significant speed-up. For some configurations, e.g., sampling three vertices, the I-MLE based ESAN more than 3.5 times faster than the non-data-drive ESAN while taking about the same time as the simple random baseline. We stress here that the ESAN implementation provided by Bevilacqua et al. [2021] precomputes subgraphs in a preprocessing step, which is not possible when learning to sample subgraphs using ESAN. Regarding predictive performance, the I-MLE based ESAN is slightly behind the nat-data-driven one, although always better than the non-subgraph enhanced GNN baseline; see Table 5 in Appendix C.
6 Conclusion
We introduced the A-OSAN framework to study the expressive power of recently introduced subgraph- enhanced GNNs. We showed that any such architecture is strictly less powerful than the (k- 1)-WL while heing incomparable to the k-WL in representing permutation-invarian functions over graphs. Further, to circumvent random or heuristic subgraph selection, we devised a data-driven variant of k-OSANs which learn to select subgraph for a given data distribution. Empirically, we verified that such data-driven subgraph selection superior to previously used random sampling in predictive performance. Further, when compared to state-of-the-ar models, we showed promising performance in terms of computation time while still providing good predictive performance. We believe that our paper provides first step in unifying combinatorial insights on the expressive power of GNNs with data-driven insights.
Acknowledgments and Disclosure of Funding
CM is partially funded a DFG Emmy Noether grant (468502433) and RWTH Junior Principal Investigator Fellowship under the Excellence Strategy of the Federal Government and the Länder. GR is funded by the DFG Research Grants Program-RA 3242/1-1-41 1032549. MN acknowledges funding by the German Research Foundation under Germany's 's Excellence Strategy-EXC 2075.
10

---

References
R. Abboud, I. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. CoRR, abs/2210.001199 2020.
S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. V. Steeg, and
A. Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pages 21-29, 2019.
R. Addanki, P. W. Battaglia, D. Budden, Deac, Godwin, T. Keck, W. L. Li, A. Sanchez- Sanchez-Gonzaler Gonzalez, J. Stott, S. Thakoor, and P. Velickovic. Large-scale graph representation learning with very deep gnns and self supervsupri CoRR, abs/2107.0944 09922,, 2021.
U. Alon and E. Yahav. On the bottleneck of graph neural networks and its practical implications. CoRR, abs/2006.08 05205, 2020.
B. M. Anderson, T. Hy, and R. Kondor. Cormorant: Covariant molecular neural networks. In Advances in Neural Information Processing Systems, pages 14510-14519, 2019.
W. Azizian and M. Lelarge. Characterizing the expressive power of invariant and equivariant graph neural networks. CoRR, abs/2006. 15646, 2020.
L. Babai. Lectures on graph isomorphism. University of Toronto, Department of Computer Science. Mimeographed lecture notes, October 1979, 1979.
L. Babai. Graph isomorphism in quasipolynomial time. In ACM Symposium Theory of Computing, pages 684-697, 2016.
L. Babai and L. Kucera. Canonical labelling of graphs linear average time. In Symposium on Foundations of Computer Science, pages 39 46, 1979.
M. Balcilar, P. Héroux, B. Gaüzère, Vasseur, S. Adam, and P. Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pages 599-608, 2021.
A.-L. Barabasi and Z. N. Oltvai. Network biology: Understanding the cell's functional organization. Nature Reviews Genetics, 5(2):101-113, 2004.
Barceló, V. Kostylev, M. Monet, Pérez, L. Reutter, and J. P. Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2020.
P. Barceló, F. Geerts, L. Reutter, and M. Ryschkov. Graph neural networks with local graph parameters. CoRR, 02//2106606707, 2021.
I. Baskin, V. A. Palyulin, and N. S. Zefirov. A neural device for searching direct correlations between structures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, 37(4):115-71, 1997.
D. Beaini, S. Passaro, V. Létournau, W. L. Hamilton, G. Corso, and P. Liò. Directional graph networks. CORR, abs/2010.028al 2020.
B. Bevilacqua, F. Frasca, Lim, B. Srinivasan, Cai, Balamurugan, M. Bronstein, and H. Maron. Equivariant subgraph aggregation networks. CoRR, abs/21 10.00910, 2021.
F. M. Bianchi, D. Grattarola, and C. Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages 874-883, 2020.
C. Bodnar, F. Frasca, N. Otter, Y. G. Wang, P. Liò, G. Montúfar, and M. M. Bronstein. Weisfeiler and Lehman go cellular: CW networks. CoRR, 0bs/2206.1257, 2021a.
C. Bodnar, F. Frasca, Y. Wang, N. Otter, G. F. Montufar, P. Lió, and M. Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pages 1036-1037, 2021b.
C. Bodnar, F. Giovanni, B. Chamberlain, Liò, and M. M. Bronstein. Neural sheaf diffusion: topological perspective on heterophily and oversmoothing in gnns. CoRR, abs/2202.04579, 2022. 2022.

---

K. M. Borgwardt, M. E. Ghisu, F. Llinares-Loo López, L. O' O'Bray, and B. Rieck. Graph kernels: ofate-of-the-arr and future challenges. Foundations and Trends in Machine Learning, 13(5-6), 2020.
G. Bouritsas, F. Frasca, S. Zafeiriou, and M. M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. CoRR, hass20006.025555 2020.
G. Bouritsas, F. Frasca, S. P. Zafeiriou, and M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Trunsactions on Pattern Analysis and Machine Intelligence, 2022.
J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and deep locally connected networks on graphs. In International Conference Learning Representation, 2014.
Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389 410, 1992.
C. Cangea, P. Velickovic, N. Jovanovic, Kipf, and P. Liò. Towards sparse hierarchical graph classifiers. CoRR, 0oos/8111012877 2018.
I. Chami, Ying, C. Ré, and J. Leskovec. Hyperbolic graph convolutional neural networks. In Advances Neural Information Processing Systems, pages 4869 4880, 2019.
I. Chami, S. Abu-EI-Haija B. Perozzi, C. Ré, and K. Murphy. Machine learning on graphs: A model and comprehensive taxonomy. CoRR, abs/2005.03677 2020.
G. Chen, Chen, C. Hsich, C. Lee, B. Liao, R. Liao, W. Liu, Qiu, Q. Sun, J. Tang, R. S. Zemel, and S. Zhang. Alchemy: A quantum chemistry dataset for benchmarking Al models. CoRR, abs/1906.09427, 2019a.
Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems, pages 15868-15876, 2019b.
G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Velickovic. Principal neighbourhood aggregation for graph nets. CoRR, abs/2004.05711, 2020a.
G. Corso, L. Cavalleri, D. Beaini, P. Liò, and P. Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems, 2020b.
L. Cotta, C. Morris, and B. Ribeiro. Reconstruction for powerful graph representations. In Advances in Neural Information Processing Systems, 2021.
G. Dasoulas, L. D. Santos, K. Scaman, and A. Virmaux. Coloring graph neural networks for node disambiguation. In International Joint Conference on Artificial Intelligence, pages 2126-2132, 2020.
M. Defferrard, B. X., and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, pages 3844-3852, 2016.
J. Domke. Implicit differentiation by perturbation. In Advances in Neural Information Processing Systems, pages 523-531, 2010.
D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspura-Guzik, and R. P. Adams. Convolutional networks graphs for learning molecular fingerprints. In Advances in Neural Information Processing Systems, pages 2224-2232, 2015.
V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson. Benchmarking graph neural networks. CoRR, abs/2003.00982 2020.
D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.
M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In International Conference on Learning Representations, Workshop on Representation Learning on Gruphs and Manifolds, 2019.
12

---

M. Fey, J.-G. Yuen, and F. Weichert, Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006. /2/79, 2020.
M. Fey, J. E. Lenssen, Weichert, and J. Leskovee. GNNAutoScale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning, pages 3294 -304,, 2021.
D. Flam- hamm-Shepherd. T. Wu, Friederich, and Aspuru-Guzik, Neural message passing on high order paths. CoRR, abs/2002. 10413, 2020.
F. Frasca, B. Bevilaequa, M. M. Bronstein, and H. Maron. Understanding and extending subgraph GNNs by rethinking their symmetries. CoRR, abs/2206. 11....1111 140. 2022.
M. Fürer. Weisfeiler-Lehman refinement requires least linear number of iterations. In International Colloquium on Automata, Languages and Programming, pages +22-333, 2001.
H. Gao and S. Ji. Graph U-Nets. In International Conference on Machine Learning, volume 97, pages 2083-2092, 2019.
Geerts, The expressive power of kth-order invariant graph networks. CoRR, abs/2007. 12035, 2020.
Geerts and L. Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022.
Geerts, F. Mazowiecki, and G. A. Pérez. Let's agree to degree: Comparing graph convolutional networks in the message-passing framework. CoRR, abs/2004.02592. 2020.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
W. Grathwohl, D. Choi, Y. Wu, G. Roeder, and D. Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. ICLR, 2018.
D. Grattarola, D. Zambon, F. M. Bianchi, and C. Alippi. Understanding pooling in graph neural networks. CoRR, abs/2110.05292. 2021.
M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Cambridge University Press, 2017.
M. Grohe. The logic of graph neural networks. In ACM/EEE Symposium Logic in Computer Science, pages 1-17, 2021.
A. Grover, E. Wang, A. Zweig, and S. Ermon. Stochastic optimization of sorting networks via continuous relaxations. arXiv preprint arXiv:/903.000 2019.
W. L. Hamilton, R. Ying, and J. Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems, pages 1025-1035, 2017.
M. Horn, E. D. Brouwer, M. Moor, Y. Moreau, Rieck, and K. M. Borgwardt. Topological graph neural networks. CoRR, abs/2102.07835, 2021.
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems, 2020.
N. Immerman and Lander. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective: In Honor of Juris Hartmanis the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81, 1990.
G. J. Klicpera, J. GroB. Directional message passing for molecular graphs. In International Conference on Learning Representutions, 2020.
E. Jang, S. Gu, and B. Poole. Categorical reparameterization with gumbel-softmax. ICLR, 2017.
W. Jin, C. W. Coley, R. Barzilay, and T. S. Jaakkola. Predicting organic reaction outcomes with Weisfeiler-Lehnee network, Advances in Neural Information Processing Systems, pages 2604-2613, 2017.
13

---

Y. Jin, G. Song. and C. Shi. Gralsp: Graph neural networks with local structural patterns, CoRR. Obss/991..07675. 2019.
J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Zidek, A. Potapenko, A. Bridgland, C. Meyer, S. A. A. Kohl, A. J. Ballard, A. Cowie, B. Romera- Paredes, Nikolov, Jain, Adler, T. Back, S. Petersen, D. Reiman, E. Clancy, M. Zielinski, M. Steinegger, M. Pacholska, T. Berghammer, S. Bodenstein, D. Silver, O. Vinyals, A. W. Senior,
K. Kavukcuoglu, Kohli, and D. Hassabis. Highly accurate protein structure prediction with AlphaFold. Nature, 2021.
C. Kim, A. Sabharwal, and S, Ermon. Exact sampling with integer linear programs and random perturbations. In Thirlieth AAAI Conference on Artificial Intelligence, 2016.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
D. B. Kireev. Chemnet: A novel neural network based method for graph/property mapping. Journal of Chemical Information and Computer Sciences, 35(2):175-18)) 1995.
J. Klicpera, F. Becker, and S. Günnemann. Gemnet: Universal directional graph neural networks for molecules. CoRR, abs/2106.0890) 08903, 2021.
N. M. Kriege, F. D. Johansson, and C. Morris. A survey on graph kernels. Applied Network Science, 5(1):6, 2020.
G. Li, M. Müller, B. Ghanem, and V. Koltun. Training graph neural networks with 1000 layers. In M. Meila and T. Zhang, editors, International Conference on Machine Learning, pages 6437-6448 6449, 2021.
P. Li, Y. Wang. H. Wang, and J. Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning, Advances in Neural Information Processing Systems, 2020.
C. J. Maddison, A. Mnih, and Y. W. Teh. The concrete distribution: A continuous relaxation of discrete random variables. International Conference on Learning Representations, 2017.
T. Maehara and H. NT. A simple proof of the universality of invariant/equivariant graph neural networks. CoRR, Abs/1910.00880 2019.
H. Maron, H. abs/1905.11136 2019.
H. Serviansky, and Y. Lipman. Provably powerful graph networks. CoRR,
H. Maron, O. Litany, G. Chechik, and E. Fetaya. On learning sets of symmetric elements. In International Conference on Machine Learning, pages
2020.
C. Merkwirth and T. Lengauer. Automatic generation of complementary descriptors with molecular graph networks. Journal of Chemical Information and Modeling, 45(5):1159-1163 2005.
A. Micheli. Neural network for graphs: A contextual constructive approach. IEEE Transactions on Neural Networks, 20(3):498-55 1119981111,1 2009.
A. Micheli and A. Sestito. new neural network model for contextual processing of graphs. In Italian Workshop on Neural Nets Neural Nets and International Workshop on Natural and Artificial Immune Systems, pages 10-17, 2005.
F. Monti, D. Boscaini, J. Masci, E. Rodolà, J. Svoboda, and M. M. Bronstein. Geometric deep learning on graphs and manifolds using mixture model CNNs. In IEEE Conference on Computer Vision and Pattern Recognition, pages 5425-5434, 2017.
C. Morris, K. Kersting, and P. Mutzel. Glocalized Weisfeiler-Lehmaal kernels: Global-local feature maps of graphs. In IEEE International Conference Data Mining, pages 327-336, 2017.
14

---

C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, pages
2019.
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. CoRR, abs/2007 0000000..66,.,.. 2020a.
C. Morris, G. Rattan, and Mutzel. Weisfeiler and Leman go sparse: Towards higher-order graph embeddings. In Advances in Neural Information Processing Systems, 2020b.
C. Morris, Y. L.,, H. Maron, B. Rieck, N. M. Kriege, M. Grohe, M. Fey, and K. Borgwardt. Weisfeiler and Leman go machine learning: The story so far. CoRR, abs/2112.09992 2021.
C. Morris, G. Rattan, S. Kiefer, and S. Ravanbakhsh. SpeqNets: Sparsity- aware permutation-equiiarraatt graph networks. In International Conference on Machine Learning, 2022.
R. L. Murphy, B. Srinivasan, V. A. Rao, and B. Ribeiro. Relational pooling for graph representations. In International Conference Machine Learning, volume 97, pages 4663-4673, 2019.
M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In International Conference on Machine Learning, pages 2014-2023, 2016.
M. Niepert, P. Minervini, and L. Franceschi. Implicit MLE: backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems,
2021.
H. NT and T. Maehara. Graph homomorphism convolution. CoRR, abs/2005.01214, 2020.
G. Papandreou and A. L. Yuille, Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models. In 2011 International Conference on Computer Vision, pages 193-200, 2011.
A. Papp and R. Wattenhofer. A theoretical comparison of graph neural network extensions. CoRR, 1tt/220111188.. 2022.
P. A. Papp. L. F. K. Martinkus, and R. Wattenhofer. DropGNN: Random dropouts increase the expressiveness graph neural networks. Advances in Neural Information Processing Systems, 2021.
M. B. Paulus, D. Choi, D. Tarlow, A. Krause, and C. J. Maddison. Gradient estimation with stochastic softmax tricks. arXiv preprint 2xXi::2006.08063 2020.
R. Ramakrishnan, O. Dral, P., M. Rupp. and O. A. von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 1, 2014. Nature.
M. Rolinek, V. Musil, A. Paulus, M. Vlastelica, C. Michaelis, and G. Martius. Optimizing rank based metrics with blackbox differentiation. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7620-7630, 2020.
Y. Rong, W. Huang, T. Xu, and Huang. DropEdge: Towards deep graph convolutional networks on node
classification. In International Conference on Learning Representations, 2020.
R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. CoRR, abs/2002.03155, 2020.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1 2011):6-88, 2009.
M. Simonovsky and N. Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on
graphs. In IEEE Conference Computer Vision and Pattern Recognition, pages 29-38, 2017.
A. Sperduti and A. Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, ((2):144335 1997. IEEE.
Stokes, K. Yang, K. Swanson, W. Jin, A. Cubillos-Ruiz, N. Donghia, C. MacNair, French, L. Carfrae, Z. Bloom-Ackerman V. Tran, A. Chiappino-Pepe, A. Badran, I. Andrews, E. Chory, G. Church, E. Brown, T. Jaakkola, R. Barzilay, and Collins. deep learning approach antibiotic discovery. Cell. 800-688-702.e33 02 2020.
15

---

R. Talak, S. Hu, L. Peng, and L. Carlone. Neural trees for learning graphs. CoRR, abs/2105.07264, 2021.
E. H. Thiede, W. Zhou, and R. Kondor. Autobahn: Automorphism-base graph neural nets. CoRR, abs/2103.01710, 2021.
J. Tönshoff, M. Ritzert, H. Wolf, and M. Grohe. Graph learning with ID convolutions on random walks. CoRR, hbss/202.008766 2021.
G. Tucker, A. Mnih, C. J. Maddison, D. Lawson, and J. Sohl-Dickstein. Rebar: Low-variance, unbiased gradient estimates for discrete latent variable models. Advances in Neural Information Processing Systems, 2017.
Veličković, G. Cucurull, A. Casanova, A. Romero, Liò, and Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
C. Vignac, A. Loukas, and P. Frossard. Building powerful and equivariant graph neural networks with structural message-passing. Advances in Neural Information Processing Systems, 2020.
O. Vinyals, S. Bengio, and M. Kudlur. Order matters: Sequence to sequence for sets. In International Conference Learning Representations, 2016.
B. Weisfeiler and A. Leman. The reduction of graph canonical form and the algebra which appears therein. Nauchno- Techhhhc-TTch Informatsia, 2(9): 1968. English translation by G. Ryabov is available at https: wttp:///wwwww.. iti zcu. cwww12018// /pff///ff/// htte//ll_ppee_rrrree transtatannitiion .df.
Z. Wu, B. Ramsundar, N. Feinberg, J. Gomes, C. Geniesse. S. Pappu. K. Leswing, and V. Pande. MoleculeNet: A benchmark for molecular machine learning. Chemical Science, 9:513-530, 2018.
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey graph neural networks. CORR, abs/1901.000 00596,, 2019.
K. Xu, C. Li, Y. Tian, T. Sonobe, K. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pages 5453 5453-5462, 2018.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? International Conference on Machine Learning, 2019.
R. Ying, You, C. Morris, X. Ren, L.. Hamilton, and Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, pages 4800 4810, 2018
You, R. Ying. and J. Leskovec. Position-aware graph neural networks. International Conference on Machine Learning, pages 7134-7143, 2019.
You, J. Gomes-Selman, R. Ying, and J. Leskovec. Identity-aware graph neural networks. CoRR, abs/2101. 10320, 2021.
M. Zhang and P. Li. Nested graph neural networks. CoRR, abs/2110.13197, 2021.
M. Zhang, 7. Cui, M. Neumann, and C. Yixin. An end-to-end deep learning architecture for graph classification. In AAAI Conference on Artificial Intelligence, pages 4428 4435, 2018.
Zhao, W. Jin, L. Akoglu, and N. Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. CoRR, abs/21 10.03310. 2021.
J. Zhou, G. Cui, Z. Zhang, C. Yang. Z. Liu, L. Wang. C. Li, and M. Sun. Graph neural networks: A review of methods and applications. CoRR, abs/ 181 12.08444, 2018.
16


Reviews:
[{"review_id": "VqyDr-nq3n", "reviewer": "Reviewer_5AyY", "summary": "Graph Representation Learning, and specifically GNNs have generated tremendous over the past few years. In this work, the authors propose a framework, which builds on recent works on subgraph enhanced (aggregated) GNNs to obtain expressive representations.  Here, the authors firstly propose a unifying framework (which ties most recently proposed works), and secondly introduces a way to 'learn to sample' from the subgraphs leveraging techniques which can back-propagate through discrete distributions.", "questions": "1. Please provide timings for other datasets as well.\n2. Page 4, line 161 - do you mean Union? or both strategies work? What do you see in practice - performance wise?", "limitations": "Yes, the authors do talk about computation costs and ways to scale them down in practice.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The idea to learn using data to 'select' subgraphs is interesting\n2. The paper is largely well written and easy to understand.\n3. The propositions and theorems appear valid\n\n\nWeaknesses:\n1. The results are relatively worse on the ZINC dataset than ESAN, and comparison is not performed on other datasets performed in comparable works (e.g. MUTAG, Proteins, PTC, etc). Is there an underlying reason - which I may have missed.\n2. Per, section 5 (and appendix F.1), sampling subgraphs - the authors use unordered subgraphs rather than the proposed theoretical strategy. Can you provide results atleast on a sample synthetic result, for the proposed framework?\n\n\n\n\n\n\n\nPost Rebuttal Updates:\n\nThank you very much for the rebuttal authors -- for adding the  ordered experimental results, justification for the smaller datasets, etc. After reading the response and the other reviews (and corresponding replies), I am happy to increase my scores.\n\n\nBest,\n\nReviewer 5AyY", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MGyn448WRs", "reviewer": "Reviewer_AFUc", "summary": "This paper provides a unifying framework for a variety of Graph Neural Networks (GNNs) that have been recently introduced and are based on a common principle: providing to the network subgraph information in various forms. The authors show that most of the existing works can be expressed via the so called Ordered Subgraph Aggregation Network (OSAN) framework, where one runs a GNN (or a 1-WL algorithm) over a marked/anchored version of the initial graph. In particular, first a k-vertex tuple is selected as anchor, which in turn induces a k-ordered subgraph. Secondly, each vertex in the graph is initially coloured by computing the atom type (similar to isomorphism type) of the subgraph induced by the vertex along with the k-tuple anchor - this is contrary to classical WL where all vertices initially have the same colour. Then a conventional GNN (or 1-WL) is run over the graph. The processes is repeated for all possible k-tuple anchors and finally the results are aggregated into a final representation. \n\nUsing this general framework, the authors prove that k-OSANs form an hierarchy and, by using some specific graph constructions, they have been able to contrast this hierarchy with the corresponding k-WL. In particular, they show that k-OSANs are incomparable with k-WL, but strictly less expressive than k+1-WL. They further proceed by showing how k-OSANs can simulate popular subgraph enhanced GNN architectures, and discuss the potential consequences of their theory in characterising the expressive power of these specific architectures. Finally, given the high computational complexity of k-OSANs, they propose a practical implementation, where only a handful of anchor subgraphs is used, and their selection is done in a data-driven manner by sampling from a learnable subgraph distribution using the perturb-and-MAP framework. The proposed algorithm is evaluated experimentally, where it is shown in several datasets that data-driven sampling can provide benefits against sampling uniformly at random, while providing improvements against non subgraph-enhanced GNNs.", "questions": "- Since the “upstream model” is a GNN, I can imagine that the end-to-end model will inherit its expressivity issues. Although I understand that the downstream model will do all the heavy-lifting, I am wondering how important is the upstream  model, i.e., what kind of subgraphs does it select? A discussion here would be useful.\n- Regarding the terminology isomorphism type and atomic type: In several papers on k-WL and equivalent higher-order GNNs the term isomorphism type is used to refer to order-preserving bijections between k-tuples (e.g., Chen et al., NeurIPS’20). Perhaps using the term isomorphism class to refer to the equivalence class induced by isomorphism might be more appropriate? Also, I am a bit confused by the atomic type definition: this is not order preserving, right?\n- L260: I found the explanation of the ordered subgraph encoding a bit confusing. Could the authors elaborate more on what they mean by position/rank?\n- L331: “In addition…ease of implementation”: I am not really sure what this sentence refers to. What are the “initial features for the subgraphs”?\n\n### Minor:\n- L179: perhaps use a different symbol for the two different embedding functions (UPD) to avoid confusion.\nWhy does the selection vector $\\pi_{v, \\mathbf{g}}$ depend also on the vertex and not only on the subgraph? I noticed that further down in the text this is instatiated with a subgraph only dependence.\n- Section F.2 SM - id GNNs: It is mentioned that id GNNs can count cycles and this is consistent with the 2-WL expressivity upper bound. Probably this is just a subtle detail, but 2-WL can count cycles up to 7 vertices - perhaps a clarification is needed here.\n", "limitations": "- A more elaborate discussion on the limitations of the data-driven subgraph sampling and on the choice of the subgraph parameters would be helpful (see above).\n- No immediate negative societal impact", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To begin with, I believe that the present manuscript provides an important contribution to the GNN community and will be of interest to various readers working with GNNs and exploring their expressive power, as well as to readers working on graph theory and graph isomorphism. However, I found the presentation unsatisfactory - in my opinion the paper is hard to follow (densely written and notation heavy) and has several clarity issues, which unfortunately now might limit its impact to a small audience. Moreover, the experimental section could be improved, mainly to make the data-driven subgraph sampling more convincing. In detail:\n\n# Strengths\n- Subgraph-enhanced GNNs have become one of the most popular families of GNN architectures in the last couple of years. However, many of these innovations have been proposed almost in parallel and this has created a confusing landscape of methods and it was unclear how to compare them. What I liked the most about this paper is that it brings order to this spectrum of methods, paving the path for future work within this framework.\n- Secondly, the theoretical results are general and intuitive (please see below for my reservations) and clarify the limitations of subgraph-enhanced GNNs.\n- A very appealing aspect of the method is that it relies on 1-WL, which implies that vertex representations are the ones that get updated instead of k-tuple representations.\n- Subgraph sampling has been also a long standing question for these and related architectures (such as the ones that use subgraph features, e.g., GSN, Bouritsas et al., TPAMI'22 and F-MPNNs, Barcelo et al., NeurIPS'21), therefore proposing a learnable algorithm is definitely towards the right direction (also see below for some reservations).\n\n# Weaknesses\n## 1. Exposition and Clarity\n### Theory\n- The exposition of the theoretical results needs to be improved. Right now, the authors do not provide any intuition or proof sketches in the main text, while the proofs are complicated (in some cases based on intricate graph constructions along the lines of the CFI gadgets), which will make it very hard for future readers to obtain an actual understanding of the presented theory. For example: \n   - Proposition 2 and Theorem 3 are important results because they settle an open question regarding the comparison of k-WL with subgraph-enhanced GNNs, but unfortunately are poorly explained, while the proofs in the supplementary material are confusing in certain parts. Moreover, there are some small inconsistencies between the main paper and the proofs, e.g. Theorem 3 says that k+1-OSANs can distinguish non-isomorphic graphs that k-OSANs deem isomorphic, while the proof in the supplementary (Theorem 10) claims a strict inclusion, which is a stronger result. Also, the proof is very brief and points to a theorem in a different paper without adding sufficient explanations. Could the authors provide a more extensive explanation in the rebuttal so as to be able to validate this claim? Also, the chain of arguments to prove these two claims in the supplementary is tangled. Could the authors clearly explain the chain of arguments in the rebuttal and in the main paper?\n   - I am a bit confused by section E.3. supplementary material. How are these results different from section D? In the title the authors mention a comparison between the vertex-subgraph k-OSWL variant and k-WL, yet in the proofs below they mention k-OSWL. Moreover, I think I am missing something in Lemma 23 (which perhaps I am also missing in section D): you mention that k-OSWL is strictly less expressive than (k+1)-WL and that (k+1)-OSWL distinguishes graphs that (k+1)-WL deems isomorphic. However, I don’t see why this immediately implies that k-OSWL is strictly less expressive than (k+1)-OSWL, since there might be graphs that k-OSWL distinguishes, therefore also (k+1)-WL, but are deemed isomoprhic by (k+1)-OSWL.\n\n### Gradient computation\n- The presentation of the I-MLE is also quite elusive. I believe the authors should provide clarifications and improve a lot the exposition in this part, first because this is probably going to be knew to the interested readers from the GNN community, and second because data-driven subgraph sampling is a novel contribution that can be potentially impactful, but currently doesn’t do its complete justice.\n- Furthermore, it is not immediately clear to me why the authors chose this specific parametrisation for the subgraph distribution. Another potential and simpler choice could have been to iteratively sample without replacement k vertices M times (one for each subgraph) and then estimate the gradients with a variant of the REINFORCE algorithm (as in Bouritsas et al., NeurIPS'21). Another idea that comes to my mind is the Plackett-Luce distribution (M times, one for each subgraph), as in the NeuralSort (Grover et al., ICLR'19) or more recent ones. Note that this can be made deterministic (essentialy sampling the top-k vertices with the highest scores) and therefore the overall pipeline can become permutation invariant, contrary to the current version, which is permutation sensitive due to sampling. Is there any particular advantage of the algorithm chosen?\n\n## 2. Experiments:\nI believe that the experimental section should be extended and improved in some respects:\n- First: it would have been useful to include in your tables more baselines, and especially baselines falling under the k-OSAN framework (e.g., as with ESAN). The results in Table 2b raise some concerns that perhaps the data-driven subgraph sampling is not yet at a level that can be reliably used in practice, so more extensive comparisons and/or an explanatory discussion with the potential reasons for this and remedies, would help. Also, note that the performance of the current baseline is not immediately visible in the tables.  \n- Second: even though subgraph sampling is learnable, the authors still have to make several design choices that seem arbitrary, i.e., the number of subgraphs to sample and the number of vertices per subgraph. Can the authors discuss any potential strategies to circumvent ad-hoc selections? An ablation study in a controlled setup, showing how the performance changes when increasing the number of subgraphs and the number of vertices would have been very helpful. \n- Another potential interesting experiment would be to select a more informative baseline, than the random one, for subgraph sampling, e.g., according to certain subgraph properties that either (1) are potentially related to the task at hand, or (2) can break graph symmetries and make the vertices more identifiable.\n- I found it a bit puzzling that the authors experimentally used unordered subgraphs, although all the theoretical analysis refers to ordered subgraphs. If I am not mistaken, unordered subgraphs are sufficient to simulate the architectures from previous works, but I am wondering if the theoretical results comparing k-OSANs to k-WL also hold for unordered subgraphs.\n- Subgraph sampling is not permutation equivariant w.r.t. the subgraphs. The authors mention in appendix C that they use an auxiliary loss to prevent degenerate solutions, but I believe more emphasis should be given to this and this part should be ablated.\n- The tables are not quite self-explanatory. What are the # and #Subg. Columns? Also, I think it is going to be helpful to explain how the operation used is implemented within the k-OSAN framework (I understand that vertex deletion means that the anchor subgraph has n-1 vertices, while vertex selection means a 1-vertex subgraph, is that correct?).  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "M8pyOUd6iy9", "reviewer": "Reviewer_n3h8", "summary": "This work develops a general family of subgraph-based GNN architectures that generalizes and unifies many of the recently proposed subgraph-enhanced GNNs. $k$-OSANs are based on message passing on all ordered $k$-vertex subgraphs of an input graph. Expressive power of this architecture is analyzed, showing that $k$-OSANs incomparable to $k$-WL, but always less powerful than $(k+1)$-WL. Further, a data-driven subgraph sampling procedure is developed.\n", "questions": "1. I think it is worth explicitly stating that your theoretical results give upper bounds on the expressive power of many existing methods, say at the very end of Section 3. This is a nice result!\n2. At the end of the related work (line 84), it would be better to say that the above works *mostly* \"do not study the approaches\" expressive power beyond 2-WL. For instance, some works like the reconstruction GNN (Cotta et al, 2021) demonstrate ability to compute functions on graphs like cycles, that 2-WL cannot count (beyond a certain size). Also, the edge deletion ESAN (Bevilacqua et al. 2022) goes past 2-WL on strongly regular graphs.\n3. Could you clarify, what is the O(n+ klog k ) algorithm for computing the MAP of the subgraph sampling distribution for ordered subgraphs?\n4. It's worth mentioning the diversity loss (Appendix C) used in I-MLE sampling in the main paper.\n5. The MAE numbers reported here for Alchemy and QM9 appear to be in different units than that of other work. In particular, these are much larger. Can you clarify how to compare these to that of other works?\n\n", "limitations": "Unless I missed some things, this work does not discuss limitations much at all in the main paper. I also do not see this in the Appendix, though the Appendix is long, so difficult to search.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The theoretical results are interesting. In particular, the upper bound of $k$-OSANs (and hence many other methods) by $(k+1)$-WL is a nice result.\n2. That the architecture uses message passing, and can independently process subgraphs is great for efficiency; future works can probably take advantage of this even further.\n3. The use of ordered subgraphs in an overall permutation invariant architecture is pretty novel and smart.\n4. The data-driven subgraph sampling seems mostly reasonable, and it tackles the important problem of how to get good performance without using all subgraphs / a uniformly sampled subset of the exponentially many subgraphs.\n\nWeaknesses:\n1. Experimental results are not that strong. Most comparisons are between random sampling and data-driven sampling. Assuming you use edge features on ZINC (is this true?), the results are not great, and the methods get outperformed by some message passing GNNs.\n\n**Note:** I have not checked the proofs of expressive power, and thus I have not read much of the Appendix.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IeUt_UuAILE", "reviewer": "Reviewer_XNdm", "summary": "The paper proposed a subgraph based GNN approach, k-OSAN. The authors showed that increasing subgraph size always increases the expressive power, and k-OSAN is strictly less powerful than the (k + 1)-WL while being incomparable to the k-WL. To circumvent random or heuristic subgraph selection, this paper devised a data-driven variant of k-OSANs. In experiments, the authors verified that data-driven subgraph selection is superior to previously used random sampling in predictive performance. Recently, subgraph GNN is proposed as a promissing approach, and in general, this is a paper of strong theoretical results.", "questions": "1. The paper in its current form is hard to follow, and I suggest the authors can first have a high-level overview of the proposed approach and then going into the detailed mathematical formulations.\n2. It is proved that k-OSAN has a higher expressive power, can the authors provide some empirical results? even on some synthetic data.\nMinors: Please define t(g) at line 154", "limitations": " The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: A new subgraph GNN model with theoretical expressive power guarantee.\nWeakness: Though this paper has strong theoretical results, the experiments is kind of weak. The auhors only showed the data driven approach is better than the random approach, but it is not clear how the proposed subgraph GNN compares with other GNN implementations, given the introduced addtional complexity of proposed method.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept