Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
Authors: Fabrizio Frasca
Beatrice Bevilacqua
Michael M. Bronstein
Haggai Maron
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Subgraphs
Expressive power
Equivariance
Weisfeiler-Leman

Abstract: Subgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, we study the most prominent form of subgraph methods, which employs node-based subgraph selection policies such as ego-networks or node marking and deletion. We address two central questions: (1) What is the upper-bound of the expressive power of these methods? and (2) What is the family of equivariant message passing layers on these sets of subgraphs?. Our first step in answering these questions is a novel symmetry analysis which shows that modelling the symmetries of node-based subgraph collections requires a significantly smaller symmetry group than the one adopted in previous works. This analysis is then used to establish a link between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the questions above by first bounding the expressive power of subgraph methods by 3-WL, and then proposing a general family of message-passing layers for subgraph methods that generalises all previous node-based Subgraph GNNs. Finally, we design a novel Subgraph GNN dubbed SUN, which theoretically unifies previous architectures while providing better empirical performance on multiple benchmarks.

Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
Fabrizio Frasca'
Beatrice Bevilaequa* Purdue University bbevilacqpurdue edu
Imperial College London & Twitter Efrasca@twitter.co com
Michael M. Bronstein
Haggai Maron
University of Oxford & Twitter mbronstein@twiiterrccmm
NVIDIA Research hmaron@nvidia com
Abstract
Subgraph GNNs are a recent class expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, study the most prominent form of subgraph methods, which employs node-based subgraph selection policies such as ego-networks node marking and deletion. We address two central questions: (1) What the upper-bound of the expressive power of these methods? and (2) What is the family of equivariant message passing layers these sets of subgraphs?. Our first step in answering these questions is novel symmetry analysis which shows that modelling the symmetries of node-based subgraph collections requires a significantly smaller symmetry group than the one adopted in previous works. This analysis is then used to establish link between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the questions above by first bounding the expressive power of subgraph methods by 3-WL, and then proposing general family of paassage-asssingg layers for subgraph methods that generalises all previous node-based Subgraph GNNs. Finally, we design novel Subgraph GNN dubbed SUN, which theoretically unifies previous architectures while providing better empirical performance on multiple benchmarks.
1 Introduction
Message Passing Neural Networks (MPNNs) are arguably the most commonly used version of Graph Neural Networks (GNNs). The limited expressive power of MPNNs [36] (55) has led to a plethora of works aimed at designing expressive GNNs while maintaining the simplicity and
scalability of MPNNs [T
39
49
30 Several recent studies have proposed new class of such
architectures [4 59 7
61
42). dubbed Subgraph GNNs, which apply MPNNs to collections
('bags') of subgraphs extracted from the original input graph and then aggregate the resulting representations. Subgraphs are selected according to predefined policy: in the most popular ones, each subgraph tied a specific node in the original graph, for example by deleting extracting its local ego-nktwork. Subgraph GNNs have demonstrated outstanding empirical performance, with state-of-the-ar results on popular benchmarks like the ZINC molecular property prediction [61|7] 77.
While offering great promise, it is fair to say that we still lack a full understanding of Subgraph GNNs. Firstly, on the theoretical side, it is known that subgraph methods strictly stronger than
Eqqual contribution. Author ordering determined coin flip.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the Weisfeiler-Leman (WL) test [54] 39, but an upper-bound on their expressive power is generally unknown. Secondly, on a more practical level. Subgraph GNN architectures differ considerably in the way information is aggregated and shared across the subgraphs, and an understanding of the possible aggregation and sharing rules is missing. Both aspects are important: an understanding of the former can highlight the limitations of emerging architectures, a study of the latter paves the way for improved Subgraph GNNs.
Main contributions. The goal of this paper is to provide a deeper understanding of node-based Subgraph GNNs in light of the two aforementioned aspects. The main theoretical tool underpinning our contributions is a novel analysis of the symmetry group that acts on the sets of subgraphs. While several previous approaches [43 [4 7 have (often implicitly) assumed that a subgraph architecture should be equivariant to independent node and subgraph permutations, we leverage the fact that node- based policies induce an inherent bijection between the subgraphs and the nodes. This observation allows us to align the two groups and model the symmetry with single (smaller) permutation group that acts on nodes and subgraphs jointly. Other works 66 56 59 have (again, implicitly) recognised such node-subgraph correspondence but without studying the implications the symmetry group, and resorting, as a result, to a partial and heuristic choice of equivariant operations.
The use of this stricter symmetry group raises a fruitful connection with k-order Invariant Graph Net- well studied family of architectures for processing graphs and hypergraphs designed to be equivariant to the same symmetry group. This connection allows us to transfer and reinterpret previous results on IGNs to our Subgraph GNN setup. As our first contribution we show that the expressive power of Subgraph GNNs with mode-based policies is bounded by that of the 3- WL test. This is shown by proving that all previous Subgraph GNNs can be implemented by a 3-IGN and by leveraging the fact that the expressive power of these models is bounded by 3-WL 21 []
works (k- IGNs) 33 32
Our second contribution is the proposal of general layer formulation for Subgraph GNNs, based on the observation that these methods maintain an n X n representation of n subgraphs with n nodes, following the same symmetry structure of 2- --NGSs (same permutation applied to both rows and columns of this representation). We propose novel extension of 2- IGINS capturing both local (message-pare saatss--assnnnniiiie like) and global operations. This extension easily recovers previous methods facilitating their comparison. Also, we present a number of new operations that previous methods did not implement. We build upon these observations to devise a new Subgraph GNN dubbed SUN, (Subgraph Union Network). We prove that SUN generalises all previous node-based Subgraph GNNs and we empirically compare it to these methods, showing it can outperform them.
2 Previous and related work
Expressive power of GNNs. The expressive power of GNNs is central research focus since it was realised that message-passing type GNNs are constrained by the expressivity of the WL isomorphism test [36] 55). Other than the aforementioned subgraph- based methods, numerous approaches for more powerful GNNs have been proposed, including positional and structural encodings [
45
11
17
28
3T, higher-order wessage-passing schemes [36] 38 10 9. equivariant models 24
33
32
53
13
51 40). We refer readers to the recent survey by Morris et al. [39] for additional details. Finally we
note that, in a related and concurrent work. Qian et al. (46) propose a theoretical framework study
the expressive power of subgraph- based GNNs by relating them to the k- WL hicrarchy, and explore how to sample subgraphs in a data-driven fashion.
Invariant graph networks. IGNs were recently introduced in a series of works by Maron et al. 33 32 34 as alternative MPNNs for processing graph and typer-graph data. For 2 2, kGNNs
represent hyper-graphs with hyper-edges up to size with k-order tensor ) E RR* where each entry holds information about a specific hyper-edge. On these they apply linear S,.equivariant layers interspersed with pointwise nonlinearities. These models have been thoroughly studied in terms of: (i) their expressive power; (ii) the space of their equivariant linear layers. As for (i), IGNs were shown to have exactly the same graph separation power as the k-WL graph isomorphism test [32 5 21 and, for sufficiently large k. to have universal approximation property w.r.t. S, -nniinvari and equivariant functions [34] 26 47). Concerning (ii), the work in [33 completely characterised the space of linear
layers equivariant to S,, from 18** g=* the authors derived a basis of bell + k') linear operators consisting of indicator tensors of equality patterns over the multi-index set (1...., "...,,m)=t [ 1n]&+*/
Albooych et al. (2) showed these layers can be (re- (re-)written sums of pooling- brodinggbooacsttinggg.. operations

---

between elements of y indexed by the orbits F of the action of Sn on [n]* and [n]]*. Take, e.g.. k K' In this case there are only two orbits: {i i [n] corresponding to on-diagonal terms, and (i.j}; i 7 j E [n], off-diagonal terms. According to Albooyeh et al. 2 any equívariant linear layer L: P. + IR can be represented as a composition of pooling and broadcasting operations on the elements indexed by these orbits. One example is the linear map that sums the on-diagonal elements and broadcasts the result the off-diagonal ones: L()"). = Ex Ves for A j. 0 otherwise. See Appendix B for additional details. These results particularly important as they underpin most of our theoretical derivations. Lastly, a more comprehensive coverage of IGNs can be found in [39].
Subgraph GNNs. Despite motivated by diverse premises, a collection of concurrent methods share the overarching design whereby graphs are modelled through the application of GNN to their subgraphs. Bevilacqua et al. 7 first explicitly formulated the concept of bags of subgraphs generated by predefined policy and studied layers to process them in an equivariant manner: the same GNN can encode each subgraph independently (DS-GNN), or information can be shared between these computations in view of the alignment of nodes across the bag (35 (DSS-GNNN. Building upon the Reconstruction Conjecture [25] [22, Reconstruction GNNs 14] obtain node-deleted subgraphs, process them with GNN and then aggregate the resulting representations by means of a set model. Nested GNNs [59] and GNN-As- models (GNN-AK) [61] shift their computation from rooted subtrees to rooted subgraphs, effectively representing nodes by means of GNNs applied to their enclosing ego-networks. Similarly to DSS-GNNs M. GNN-AK models may feature information sharing modules aggregating node representations across subgraphs. ID-GNNs [56] also process ego-network subgraphs, but their roots are 'marked' so to specifically alter the exchange of messages involving them. Intuitively, the use of subgraphs implicitly breaks those local symmetries which determine the notorious expressiveness bottleneck of MPNNs. We note that other works can be interpreted as Subgraph GNNs, including those by Papp et al. Papp and Wattenhofer [42
3 Node-based Subgraph GNNs
Notation. Let G X), be member of the family G of node-altributed, undirected, finite, simple graphe] The adjacency matrix A =R= represents G's edge set E over its set of n nodes V. The feature matrix X E Raxd gathers the node features; we denote by ær E Rdx1 the features of node j corresponding to the j-th row of X. BG is used to denote a multiset (bag) of m subgraphs of G. Adjacency and feature matrices for subgraphs in BG are arranged in tensors A E R xxxx and
X' E Rmxxad_ Superscript (.(t) refers to representations on subgraph i at the t-th layer of a stacking,
1,((), Finally, we denote [n] = (l...., .n. All proofs are deferred to Appendices and D
as in zz
Formalising Subgraph GNNs. Subgraph GNNs compute representation of G E G as
(A, + (popos π) X).
..... (A"h, xm) } = BB) is selection policy generating a bag of subgraphs from G; S = Lr ....... o L1 : B + B is a stacking of T (node- and subgraph-) permutation equivariant layers; p: (G, (G, ) function, μ is an MLP. The layers in S comprise a base-encoder in the form of a GNN applied to subgraphs: throughout this paper, we assume it to be 1-WL maximally expressive MPNN such as the one in Morris et al. [36]. Subgraph GNNs differ in the implementation of π, S and, in some cases, p. For example, in (n- Reconsttsstt GNNs 14] क selects node-deleted subgraphs and applies a Siamese MPNN to each subgraph independently. To exemplify the variability in S, DSS-GNN Z extends this method with -ubgraah node and connectivity aggregation. More details are on how currently known Subgraph GNNs are captured by Equation 1 can be found in Appendix A
Here, :: G (G),..,GGM) =
(T) + IG is a permutation invariant pooling
Node-based selection policies. In this work, we focus on a specific family of node-based subgraph selection policies, wherein every subgraph is associated with a unique node in the graph. Formally, we call a subgraph selection policy bade-basedii if it is of the form (G) = {f v)) for some selection function f(G, v) that takes graph G and a node v as inputs and outputs subgraph G". In the following, we refer
the root of subgraph Go. We require f to be a bijection and we
FFor group G acting on set X, the orbits of the action G on X are defined as (G x a E X}. These partition X into subsets whose elements can (only) reach all other elements in the subset via the group action. We do not consider edge features, although an extension to such setting would be possible.
3

---

ESAN symmetries: S,* S,
Node-based symmetries: (same as in 3-1GN)
Group inclusion
Function space inclusion (Invarse] 3-IGNs 3,- equiv.
S
T
Subgripht
ESAN S, 3,- equix
nodeo-
modec
rodec
Figure 1: Symmetries of bags of subgraphs (left) and corresponding function space diagrams (right). In ESAN 7 symmetries are modelled as direct product of node and subgraph permutation groups; however, node-based policies enable the use of one single permutation group, the same as in 3-IG.s 3-IGNs are less constrained, thus more expressive than ESAN and other Subgraph GNNs. See diagram on the right and formal statement Section S
note that such policies produce in different subgraphs. Amongst the most common examples are node-deletion (ND), node-marking (NM), and ego-networks (EGO) policies. For input graph G, IND(G, u) removes node and the associated connectivity; (NM(G.v) u) adds special 'mark' attribute to v's features (with no connectivity alterations), and (EGO(L) (G, v) returns the subgraph induced by around the root v. EGO policies can be 'marked': fEGO+(N) (G, v) extracts the hi-hop ego-net net around and marks this node as done by fNM. For convenience, we denote the class of such node-based selection policies by II:
the
Definition (Known mode-based selection policies IT). Let E be the set of all node-based subgraph selection policies operating on G. Class II C E collects the node-based policies node-deletion (ND), node-marking (NM), ego-nets (EGO) and marked ego-nets (EGO+) of any depth: II (NND, NNM, Tg)(()): TEGO+(N)
0}.
Node-based Subgraph GNNs are those Subgraph GNNs which, implicitly explicitly, process bags generated by node-based policies. We group known formulations in the following family:
Definition (Known node- based Subgraph GNNs Ty. Let E be the set of all mode-based Subgraph GNNs. Class T C Egt collects known Subgraph GNNs when equipped with 1-WL base-encone encoders: T (mn-I)-Reoosstr. GNNN, GNN-AK, GNN-AK-etx, NGNN, ID-GNN, DS-GNN1, DSS- n DS-GNN DSS-GNNN refer to DS- and DSS-GNN models equipped with any π E IT.
Importantly, all these methods apply MPNNs subgraphs of the original graph, but differ the way information is shared between subgraphs/nodes. In all cases, their expressive power is strictly larger than 1-WL, but an upper-bound currently unknown.
4 Symmetries of node-based subgraph selection policies
In an effort to characterise the representational power of node-based Subgraph GNNs, we first study the symmetry group of the objects they process: 'bags of subgraphs' represented as tensors (A, X) e
pmxaxx xxxd assuming nodes across m subgraphs. Previous approaches 14 4 used
two permutation groups: one copy of the symmetric group S, models node permutations, while another copy Sm models subgraph permutations in the bag. These two were combined by a group product" acting independently on the nodes and subgraphs in X). For example, Bevilacqua et al. 7 model the symmetry as:
(T,,o)AAuss = A. (0-1
((T,O)-2),)) X2-1(00-1000 (T, E Sm x Sn (2)
Our contributions stem from the following crucial observation: When using node-based policies, the subgraphs in (A, can be ordered consistently with the nodes by leveraging the bijection + Go characterising this policy class. In other words, suggests node-subgraph alignment inducing a new structure on (A,, whereby the subgraph order is not independent of that of nodes
Bevvilaquaa et al. 7 use direct- producc,, assuming nodes in subgraphs are consistently ordered. Cotta et al. use the larger wreath product assuming node ordering in the subgraph is unknown.

---

edges to / from roof nodes
representations of root nodes
edges between non-roof nodes
representations of non-root nodes
Depiction of cubed tensor y, its orbit-induced partitioning and the related semantics when )' is interpreted as a bag of node-based subgraphs, 5. Elements in the same partition are depicted with the same colour. Left: the whole tensor. Middle and right: sections; elements in purple and green constitute sub-tensor X' the remaining ones sub-tensor A.
Figure 2:
anymore. Importantly, this new structure is preserved only by those permutations operating identically on both nodes and subgraphs. Following this observation, the symmetry of node-based bag of subgraphs is modelled more accurately using only one single permutation group Sn jointly acting on both nodes and subgraphs:
(o Alijk = A.r (()or (AA): (a. X0)z = X, 2()a P() a E Sn
(3)
should be noted that S. is significantly smaller than S, x S Informally, the latter group contains many permutations which not in the former: those acting differently nodes and subgraphs and, thus, not preserving the new structure of (A, Since they are restricted by a smaller set of cquivariance constraints, we expect GNNs designed be equivariant S, to be be more expressive than those equivariant to the larger groups considered by previous works (34 (see Figure [].
The insight obtain from Equation A exactly matches the symmetries of third-order tensors used by 3-IGNs, and similarly, that the symmetry structure for X' matches the symmetries of second-order tensors used by 2-IGNs. In the following, we will make use of this insight and the fact that IGNs are well-studied objects to prove an upper-bound on the expressive power of Subgraph GNNs and design principled extensions to these models. We remark that bags of node-based subgraphs can also be represented as tensors D E IR" xd the same objects on which 3- B-IGNs operate. Here, X' is embedded in the main diagonal plane V. A in its remaining entries. Within this context, informative to study the semantics of the 5 orbits induced by the action of S, on )'s multi-index set [n]S; each of these uniquely identify root nodes, non-root nodes, edges to and from root nodes as well as edges between non-root nodes (see Figure and the layer construction by Albooych et al. 2 to prove many of the results presented in the following.
profound: it reveals that the symmetry structure of
and additional details in Appendix [II..).. We build upon this observation, along with
A representational bound for Subgraph GNNs
In this section we prove that the expressive power of known node-based Subgraph GNNs bounded by 3-WL by showing that they can be implemented by 3-IGNs, which have the same expressive power as 3-WL. Underpinning the possibility of IGNs to upper-bound certain Subgraph GNN A in its expressive power is the ability of IGNs to (i) implement ' subgraph selection policy (T)) and (ii) implement ' (generalised) message- message-passing and pooling equations (μI p o S). This would ensure that whenever.J N assigns distinct representations to two non-isomorphic graphs, an IGN implementing N would do the same. We start by introducing a recurring, useful concept.
Definition 3 ("implements"). Let f Dj - Cy. D2 + C. be two functions and such that D, C Dy, C, Cf. We say implements (and write g) when vr Dg. f(x) g(x).
MMor formally, Sa's orbits the indices in refine the orbits of the product group in 2
5

---

Our first result shows that 3- 3-IGNs can implement the selection policies in class II (Definition D which, to the best of our knowledge, represent all known node-based policies utilised by previously proposed Subgraph GNNs.
Lemma 4 (3- IGNs implement known mode-based selection policies). For any ι E there exists stacking of 3- IGN layers M2 s.t. M ~ π.
Intuitively, 3-IGNS start from a R² representation of G and, first, move to a RT tensor 'copying' this latter along its first (subgraph) dimension. This is realised via an appropriate broadcast operation. Then, they proceed by adding a 'mark' to the features of some nodes and/or by nullifying elements corresponding to some edges. We refer readers to Figure 2 and Appendix B.1.2 for additional details on how nodes in each subgraph are represented in 3- B-NGS. Next, we show 3- 3-IGNs can implement layers of any model E Y.
Lemma 5 (3-IGNs implement Subgraph GNN layers). Let G1. G2 be two graphs in 9 and N a model in family Yf equipped with Morris et al. (36] cesssage-passingg base-encoders. Let B(") BB()) be bags of subgraphs in the input of some intermediate layer L in N. Then there exists a stacking of for i )(B(())oro
3- 3GN layers M for which (z(B, B((+1) L(B())
1,2.
Lemmas 4 and allow to upper-hound the expressive power of all known instances of node-based Subgraph GNNS by that of 3-IGNs:
Theorem 6 (3-IGNs upper-bound node-based Subgraph GNNs). For any pair of non-isomorphic graphs G1, G2 in family 9 and Subgraph GNN model N E Y equipped with Morris et al. (36) message-passing base-encoders, if there exists weights O such that G1, G2 are distinguished by instance Ne. then there exist weights St for a 3-IGN instance Ma such that G1, G2 are distinguished by Ma as well.
Theorem 6 has profound consequences in the characterisation of the expressive power of node-based Subgraph GNNs, as we show in the following
Corollary 7 (3-WL upper-bounds node-based Subgraph GNNs). Let G1, G2 E G be two non- isomorphic graphs and No E Y one instance of model N with weights Q. If No distinguishes G1, G2, then the 3- WL algorithm does so as well.
Proof idea: If there is a pair of graphs undistinguishable by 3-WL, but for which there exists a Subgraph GNN separating them, there must exists IGN separating these (Theorem op. This is in contradiction with the result by Geerts (21), Azizian and Lelarge 15
A design space for Subgraph GNNs
As discussed, different formulations of Subgraph GNNs differ primarily in the specific rules for updat- ing node representations across subgraphs. However, until now is not clear whether existing rules exhaust all the possible equivariant options. We devote this section to systematic characterisation of the 'layer space' of Subgraph GNNs.
In the spirit of the previous Section 5 where we "embedded" Subgraph GNNs in 3-IGNs, one option would be consider all (6) 203 linear equivariant operations prescribed by this formalism. However, this choice would be problematic for three main reasons: (i) This layer space is too vast to
be conveniently explored; (ii) It includes operations involving Onn)) space complexity, impractical in most applications; (iii) The linear IGN basis does not directly support local message passing, a key operation in subgraph methods. Following previous Subgraph GNN variants, which use ((n)) storage for the representation of nodes in n subgraphs, we set the desideratum of Onn) memory complexity as our main constraint, and use this restriction to reduce the design space. Precisely, we interested in modelling S, -quuivraai transformations on the subgraph-nok -ode tensor X.
6.1 Extended 2-1GNs
As have already observed in Equation in Section 4 such second order tensor X' abides by the same symmetry structure of 2-IGNs. We therefore gain intuition from the characterisation of linear equivariant mappings as introduced by Maron al. [33] and propose an extension of this formalism.
k--WL is equivalent to (k-1) Le. the "Folklore" WL test, see Morris al. [36]

---

(n-o)-Reconstr GNN NGNN DS-GNN
ID-GNN
DSS-GNN
GNN-AKK-cx
SUN
ReiGN(2)
2/GN
off-diag. (non-roots)
updates
on-diag. (roots)
subgraphs
nodees
Figure 3: Comparison aggregation and update rules in Subgraph GNNs, illustrated on an n matrix (n subgraphs with nodes). Top row: off-diagonal updates; bottom row: diagonal (root node) updates. Each colour represents different parameter. Full squares: global sum pooling; triangles: local pooling; two triangles: both local and global pooling. See Appendix C for more details.
2-IGN layer space. A 2-IGN layer Le updates X' Ruxaxd x(++1) Le (x(()) by applying specific transformation to on- (x:) and off-diagonal terms (r), i j):
A1++1 uo,
(a:
6.(1)
A.00)
(4)
k.(+11 uns (xt 2
k.())
1.00
(A)
1.())
h.00)
k.(0)
6,00)
5.10)
37
Here, indicates a permutation invariant aggregation function, v0, va, apply specific x d' linear transformation to each input term and sum the outputs including bias terms.
ReIGN(2) layer space. As 2-IGN layers are linear, the authors advocate setting ==> = per- forming pooling as global summation. Here, we extend this formulation to additionally include different local aggregation schemes. In this new extended formalism, entry x. represents node i in subgraph k; accordingly, each aggregation in Equation can be also performed locally, i.e. extending only over i's neighbours, as prescribed by the connectivity of subgraph & or of the orig- inal input graph. As an example, when updating entry x. (.((), term [j a
expanded as -) with denoting adjacency in subgraph k, and ~ that in the original graph connectivity. Each term in the expansion is associated with a specific learnable linear transformation. We report a full list of pooling operations in Appendix [ Table 3 These local pooling operations allow readily recover sparse message passing, which constitutes the main computational primitive of all popular (Subgraph) GNNs. Other characteristic Subgraph GNN
k.(()
(Ai (() Diw,, 2t x. (.(t)
operations also recovered by this formalism: for example, Da h.((t) operates global pooling of node i's representations across subgraphs, as previously introduced in Bevilacqua et al. 7 Zhao al. [6]. We also note that additional, novel, operations are supported, e.g. the transpose 1.(()) We generally refer to this framework as ReIGN (2) ("Rethought 2-IGN").
ReIGN (2) architectures. ReIGN (2) induces (linear) layers in the same form of Equation but where terms are expanded to both local and global operations, as explained. These layers can operate any bag generated by node-based selection policy म, and can be combined together in ReIGN (2) stacks of the form SR L(T) o (T--)) o o (1),, where a's is are pointwise nonlinearities and L's are ReIGN (2) layers. This allows define ReIGN (2) models as Subgraph
GNNs in the form of Equation where S is a ReIGN (2) layer stacking and π is node-based: R₂ = f p SR
More generally, ReIGN (2) induces a 'layer space' for node-based Subgraph GNNs: the expanded terms in its update equations represent pool of atomic operations that can be selected and combined to define new equivariant layers. Compared to that of 3-IGNs, this space of tractable size, yet recovers previously proposed Subgraph GNNs and allows to define novel interesting variants.
Recovering previous Subgraph GNNs. The following result states that the ReIGN (2) generalises all known subgraph methods in Y, as their layers are captured by ReIGN (2) stacking.
7

---

Theorem 8 (ReIGN (2) implements node-based Subgraph GNNs), Let N be a model in family T equipped with Morris et al. [36] message-passsin base-encoders. For any instance No. there exists (2I instance Rn such that Rn = Ne.
This shows that known methods are generalised without resorting to the O(n²) computational complexity of 3-IGNs. Figure [ illustrates the aggregation and sharing rules used by previous Subgraph GNNs to update root and non-root nodes, and compare them with those of ReIGN (2) and 2-IGNs. We visualise these on the subgraph-node sub-tensor gathering node representations across subgraphs: here, root nodes occupy the main diagonal, non-root nodes all the remaining off-diagonal entries. As for to the 2-IGN Equations + the elements in these two partitions may be updated differently, so we depict them separately in, respectively, the bottom and top rows. In each depiction we colour elements depending on the set of weights parameterising their contribution in the update process, with two main specifications: (i) Elements sharing the same colour are pooled together; (ii) Triangles indicate such pooling is performed locally based on the subgraph connectivity at hand (two triangles indicate both local and global pooling ops are performed). E.g., note how DS-GNN equivalently updates the representations of root and non-root nodes via the same (local) message- passing layer (triangles, yellow, leftmost picture). By illustrating how ReIGN (2) generalises previous node-based methods, this figure is to be interpreted visual support for the Proof of Theorem (sec Appendix D Additional details and discussions on Figure are found in Appendix C
Notably, as methods in T have been shown to be strictly stronger than 2-WL 7 14
61
59
56
Theorem implies the same lower bound for ReIGN (2). Nevertheless, when employing policies in II and 3 IGN- Comppuaabel invariant pooling functions (as those used by models in T). ReIGN (2)s are upper-bounded by 3-IGNs:
Proposition 9 (3-IGNs implement ReIGN (2)). For any pair of non-isomorphic graphs G1, G2 in family G. if there exist policy îे E II, parameters O and 3 B-IGN-computable invariant pooling P such that the ReIGN (2) instance Rg,0,= distinguishes G1, G2, then there exist weights for 3- IGN instance Ma such that G1, G2 are distinguished by Ma as well.
poolingfunction function
This proposition entails an upper- Corollary 10 (3-WL upper-bounds ReIGN (2)). The expressive power of a ReIGN(2) model with policy π E II and 3 3-IGN-ca TCN-computable invariant pooling function is upper-bounded by 3-WL.
upper-bound bound on the expressive power of ReIGN
We note that there may be layers equivariant to Sn over RT² not captured by ReIGN (2). Yet, previously proposed Subgraph GNN layers do not exhaust the (2) design space, which remains largely unexplored. One, amongst possible novel constructions, is introduced next.
6.2 A unifying architecture: Subgraph Union Networks
We now show how the ReIGN (2) layer space can guide the design of novel, expressive, Subgraph GNNs. Our present endeavour is to conceive a computationally tractable architecture subsuming known node-based models: in virtue of this latter desideratum, we will dub this architecture "Subgraph Union Network" (SUN). To design the base equivariant layer for SUN, we select and combine specific aggregation terms suggested by the ReIGN (2) framework:
5. ((++1) (vo, (0,,
1000
Σ
100
T
h.(1)
ΣΣ
)
(5)
jimi
2. k.(++) a (vo, U02 (az
k.00)
Σ
410
(.)))
Σ
10(0
ΣΣ
A,00
(6)
where v's sum their inputs after applying a specific lincar transformations to each term. One of the novel features of SUN is that roots transformed by different set of parameters (0;) than the
other nodes (02, see Figure In practice, the first and last two terms in each one of Equations (5) and (6) can be processed by maximally expressive MPNNs 36 (5), the remaining terms by MLPs.
We test these variants in our experiments, with their formulations in Appendix G SUN remains an instantiation of the ReIGN (2) framework:
Proposition 11 (A ReIGN (2) stacking implements SUN layers), For any SUN layer L defined accord- ing Equations and there exists a ReIGH (2) layer stacking St, such that St, z L.
As result, the architecture mark root nodes, for example.
8

---

Table I: Test mean MAE on the Counting Substructures and ZINC- datasets. All Subgraph GNNs
employ a GIN base-encoder. 'This version of GNN-AK+ does not follow the standard evaluation procedure.
Mothod
ZINC (MAE L)
GCN 2x
0.321 + 0.009
Counting Substructures (MAE ))
GIN 55
0.163 + 0.004
Method
PNA
15
0.133 + 0.011
Triangle
Tailed Tri.
Star
4-Cycle
GSN
[
0.101 + 0.010
GCN
0,4186
0.3248
0.1798
0.2822
CIN
0.079 0.006
GIN 35
0.3569
0,2373
0.0224
0.2185
NGNN 69
0.111 + 0.003
0.3532
0,2648
DS-GNN (EGO)
0.115 + 0.004
PPGN
32
0.0089
0.0096
0.0148
0.0090
DS-GNN (EGO-)
F
0.105 + 0.003
GNN-AK
0.0934
0.0751
0.0168
0.0726
DSS-GNN (EGO)
0,099 + 0.003
GNN-AK-CTX
61
0.0885
0.0696
0.0162
0.0668
DSS-GNN (EGO+)
0
0.097 1 0,0016
GNN-AK+
0.0123
0.0112
0.0126
GNN
1 0.010
GNN-AK
M
0.093 + 0.002
SUN (EGO)
0.0092
0.0105
0.0064
0.0140
GNN AK+
61
0.086 1 ???
SUN (EGO+)
0.0079
0.0080
0.0064
0.0105
GNN-AK-
+
SUN (EGO)
0.083 + 0.003
SUN (EGO+)
0.084 0.002
Finally, we show that stacking of SUN layers can implement any layer of known node-based Subgraph Networks, making this model a principled generalisation thereof.
Proposition 12 (A SUN stacking implements known Subgraph GNN layers), Let N be model in family Y employing Morris et al. [36] as message-passiing base-encoder. Then, for any layer L in N, there exists a stacking of SUN layers St such that St L.
Beyond SUN. As it can be seen Figure SUN does use all possible operations in the ReIGN (2) framework, Notably, two interesting operations that are not a part of SUN are: (i) The 'transpose': : of = ug (xft), which shares information between the i-th node in the k-th subgraph and the k-th node in the i-th subgraph; (ii) Local vertical pooling a.f va (Ens ..)). The exploration of these and other operations is left to future work.
7 Experiments
We experimentally validate the effectiveness of one (2IGN instantiation, comparing SUN to previously proposed Subgraph GNN We seek to verify whether its theoretical representational power practically enables superior accuracy in expressiveness tasks and real-world benchmarks. Concurrently, we pay attention to the generalisation ability of models in comparison. SUN layers are less constrained in their weight sharing pattern, resulting in more complex model. As this is traditionally associated with inferior generalisation abilities in low data regimes, we deem it important to additionally assess this aspect. Our code is also available
Synthetic. Counting substructures and regressing graph topological features are notoriously hard tasks for GNNs 112 [3]. We test the representational ability of SUN common benchmarks of this kind 12 13 Table I reports results on the substructure counting suite, on which SUN attains
state-of-the-art results in 3 out of 4 tasks. Additional results on the regression of global, structural properties are reported in Appendix G
Real-world. On the molecular ZINC-12K benchmark (constrained solubility regression) [50 [5022] 22, 16].
SUN exhibits best performance amongst all domain-agnostic GNNs under the 500k parameter budget, including other Subgraph GNNs (see Table II. A similar trend is observed dataset from the OGB (23 (inhibition of HIV replication). Results are in Table 2 Remarkably, on
the large-scale Molhiy
both datasets, SUN either outperforms approaches HIMP [19] GSN [1] and CIN [9, GNNs which explicitly model rings. We experiment on smaller-scale TUDatasets also compare selection policies.
37 in Appendix G where we
'For GNN-AK variants 61]. we run the code provided by the authors, which 'context' and 'subgraph' embeddings sum only over ego-network nodes. httpp::// //gg::////tttbb wtt.h/bbb.co//bbbbb///////

---

4 Cydee (EGO)
4 Cycks (EGO+)
ZINC (EGD)
GMNAK
MGNN
0.35
0.00
0.40
0.25
0.15
0.9
0.00
200
1201 550
3000 850
1000
200
400
3209 800
850
1000
3400
6000
5620
10000
training examples
training examples
training
Figure 4: Generalisation capabilities of Subgraph GNNs in the counting prediction task (Figures 4a and 4b) and in the ZINC-12K dataset (Figure 4c
Generalisation from limited data. In this set of experiments we compare the test performance of Subgraph GNNs when trained on increasing fractions of the available training data. Each architecture is selected by tuning the hyperparameters with the entire training and validation sets. We run this experi- ment on the 4-cycle counting task and the real-world ZINC-12K. We illustrate results in Figures 4a to 4cl Except for a short ini- tial phase in the EGO policy, SUN generalises better than other Subgraph GNNs on cycle-counting. On ZINC-12K, SUN out- runs DSS-, DS-GNN and GNN-AK variants from, respectively, 20, 30 and 40% the samples. These results demonstrate that SUN's expressiveness is not at the expense of sample efficiency, suggesting that its modelled symmetries guarantee strong rep- resentational power while retaining important inductive biases for learning on graphs.
Table 2: Test results for OGB dataset. GIN base-encoder for each Subgraph GNN.
Method
ROC-AUC
GCN GIN
76.06:1:0:7
651
75 18-58:1:1 100
PNA
13
79.05 + 1.32
DGN
79. 19.90
GSN 11
80.29 0.90
CIN
80.51
RECONSTR GNN
76.30:1 440
DS-GNN (FGD+)
77:0022.119
(EGO+)
76.78:1:666
GNN-AK+ 61)
1911
SUN (EGO+)
$0.00:05555
8 Conclusions
Our work unifies, extends, and analyses the emerging class of Subgraph GNNs. Notably, demonstrated that the expressive power of these methods is bounded by 3-WL. Towards systematic study of models whose expressivity lies between 1- and 3-WL, we proposed new family of layers for the class of Subgraph GNNs and, unlike most previous works on the expressive power of GNNs, we also investigated the generalisation abilities these models, for which SUN shows considerable improvement. Appendix E lists several directions for future work, including an extension of our work ordher-order node- based policies.
Societal impact. We do not envision any negative, immediate societal impact originating from our theoretical results, which represent most of our contribution. Experimentally, our model has shown promising results on molecular property prediction tasks and strong generalisation ability in low-data regimes. This leads to believe our work may contribute to positively impactful pharmaceutical research, such as drug discovery 220 3]
Acknowledgments and Disclosure of Funding
The authors are grateful to Joshua Southern, Davide Eynard, Maria Gorinova, Guadalupe Gonzalez, Katarzyna Janocha for valuable feedback on early versions of the manuscript. They would like to thank Bruno Ribeiro and Or Litany for helpful discussions, Giorgos Bouritsas for constructive conversations about the generalisation experiments and, in particular, Marco Ciccone for the precious exchange on sharpness-aware optimisation and Neapolitan pizza. MB is supported in part by ERC Consolidator grant no 724228 (LEMAN). No competing interests are declared.
10

---

References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), 2020.
[2] Marjan Albooyeh, Daniele Bertolini, and Siamak Ravanbakhsh. Incidence networks for geo- metric deep learning. arXiv preprint arXiv: 1460, 2019.
[3] Han Altae-Tran, Bharath Ramsundar, Ancesh S Pappu, and Vijay Pande. Low data drug discovery with one-shot learning. ACS Central Science, 3(4):283-293, 2017.
[4] James Atwood and Don Towsley. Diffusiinn-comvouttional neural networks. In Advances in Neural Information Processing Systems, volume 29, 2016.
[5] Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. International Conference on Learning Representations, 2021.
[6] Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pictro Liò. Directional graph networks. International Conference on Machine Learning. 2021.
[7] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
[8] Lukas Biewald. Experiment tracking with weights and biases, 2020. Software available from wandb.com.
[9] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Liò, Guido F Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In Advances in Neural Information Processing Systems, volume 34, 2021.
[10] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montúfar, Pictro Liò, and Michael Bronstein. Weisfeiler and lchman go topological: Message passing simplicial networks. In International Conference Machine Learning, 2021.
[11] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Puttern Analysis and Machine Intelligence, 2022.
[12) Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in Neural Information Processing Systems, volume 33, 2020.
[13] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pictro Liô, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Systems, volume 33, 2020.
[14] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. In Advances in Neural Information Processing Systems, volume 34, 2021.
[15] Pim de Haan, Taco S Cohen, and Max Welling. Natural graph networks. In Advances in Neural Information Processing Systems, volume 33, 2020.
[16] Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
[17] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference Learning Representations, 2022.
[18] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903:022330002 2019.

---

[19] Matthias Fey. Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
[20] Thomas Gaudelet, Ben Day, Arian Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy B R Hayter, Richard Vickers, Charles Roberts, Jian Tang, David Roblin, Tom I. Blundell, Michael M Bronstein, and Jake P Mhylor-King. Utilizing graph machine learning within drug discovery and development. Briefings in Bioinformatics, 05 2021. ISSN 1477-4054.
[21] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007.12035, 2020.
[22] Rafael Kómezz-oombrreli, Jennifer N. Wei, David Duvenaud, José Miguel Heránndez-Lbbar Benjamín Sânchez-Lengelinng Dennis Sheberla, Jorge Sguuilera-parraguirre Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik, Automatic chemical design using a data-driven continuous representation of molecules. ACS Central Science, 4(2):268-217 Jan 2018. ISSN
2374-7951. doi: 1aa.02//acccentsci/bb0000
[23] 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 Advances in Neural Information Processing Systems, volume 33, 2020.
[24] Truong Son Hy, Shubhendu Trivedi, Horace Pan, Brandon M Anderson, and Risi Kondor. Covariant compositional networks for learning graphs. Anchorage '19: 15th International Workshop on Mining and Learning with Graphs, 2019.
[25] Paul J. Kelly. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1):961-968,
1957.
[26] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
[27] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[28] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Advances in Neural Information Processing Systems, volume 34, 2021.
[29] Jungmin Kwon, Jeongseop Kim, Hyunseo Park, and In Kwon Choi. Asam: Adaptive sharpness- aware minimization for scale-invariant learning of deep neural networks. In International Conference on Machine Learning, 2021.
[30] Pan Li and Jure Leskovec. The expressive power of graph neural networks. In Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao, editors, Graph Neural Networks: Foundations, Frontiers, and Applications, pages 63-98. Springer Singapore, Singapore, 2022.
[31] Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
[32] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
[33] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019.
[34] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning, 2019.
[35] Haggai Maron, Or Litany, Gal Chechik, and Ethan Fetaya. On learning sets of symmetric elements. In International Conference on Machine Learning. 2020.
12

---

[36] 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 artificial intelligence, volume 33, 2019.
[37] 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. 2020.
[38] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. In Advances in Neural Information Processing Systems, volume 33, 2020.
[39] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:21 S..iv:2112.09992 2021.
[40] Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity-aware permuaation-cquivarian graph networks. In ICLR 2022 Workshop on Geometri- cal and Topological Representation Learning, 2022.
[41] Mathias Niepert, Pasquale Minervini, and Luca Franceschi. Implicit mle: Backpropagating through discrete exponential family distributions. In Advances in Neural Information Processing Systems, volume 34, 2021.
[42] Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. arXiv preprint arXiv:2201.12884 2022.
[43] Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Ran- dom dropouts increase the expressiveness of graph neural networks. In Advances in Neural Information Processing Systems, 2021.
[44] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32, 2019.
[45] Omri Puny, Heli Ben- Bem-Hamu, and Yaron Lipman. Global attention improves graph networks generalization. arXiv preprint arXiv:2006.07885 2020.
[46] Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Ordered subgraph aggregation networks. In Advances in Neural Information Processing Systems, volume 35, 2022.
perceptrons. In International Conference [47] Siamak Ravanbakhsh. Universal equivariant perceptooee on Machine Learning, 2020.
[48] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2019.
[49] Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04075. 2020.
[50] Teague Sterling and John J. Irwin. ZINC 15 -igand discovery for everyone. Journal of Chemical Information and Modeling, 55(11):2322 2337, 11 2015. doi: 10.1021/acc.jcmm.500555..
[51] Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-base graph neural nets. In Advances in Neural Information Processing Systems, volume 34, 2021.
[52] Stanislaw M. Ulam. A collection of mathematical problems, volume 8 Interscience Publishers, 1960.
13

---

[53] Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. Advances Neural Information Processing Systems, volume 33, 2020.
[54] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representationss 2019.
[56] Jiaxuan You, Jonathan Gomes-Selman, Rex Ying. and Jure Leskovec. Identity-aware graph neural networks. AAAI Conference on Artificial Intelligence (AAAI), 2021.
[57] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie, Small relu networks are powerful memorizers: tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, volume 32, 2019.
[58] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances Neural Information Processing Systems, volume 30, 2017.
[59] Muhan Zhang and Pan Li. Nested graph neural networks. In Advances in Neural Information Processing Systems, volume 34, 2021.
[60] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learn- ing architecture for graph classification. Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[61] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. International Conference on Learning Representations. 2022.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discussed limitations of
several previous works, well our own model, throughout the paper as our main contribution.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section g
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices B D
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See Section and Appendix G
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix G
(c) Did report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We report the standard deviation computed over multiple seeds for experiments ZINCI 12 (Table D. ogbg-molhiv (Table 2 and all gen-
cralisation experiments (Figures 4a to 4c We report the standard deviation for the
"Counting Substructures" experiments (Table I in Appendix
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix G
4. If you are using existing assets (e.g., code, data, models) or curating/reelasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "vOBDwssPglD", "reviewer": "Reviewer_qAH9", "summary": "This paper proposes a unified analysis of subgraph GNNs based on node selection (e.g., ego-networks, node deletion, etc), and shows that these GNNs map directly to 3-IGNs (invariant graph networks) by representing their different components (subgraph selection, layers, pooling, MLP) as 3-IGN layers. Based on this correspondence, the paper then shows that any subgraph GNN based on node selection (where every subgraph is computed through a bijection over the selected node and the original input graph) can be implemented through a 3-IGN. This result is shown first by proving that all known graph selection policies can be emulated by a 3-IGN (Lemma 4) and then showing how the following components of subgraph GNNs can also be captured by this same model (Lemma 5). Based on this result, the paper proves that all subgraph GNNs based on node selection have expressive power upper-bounded by 3-WL, the upper bound for 3-IGNs. \n\nBuilding on this insight, the paper then considers potentially novel designs for invariant/equivariant operations over nodes and subgraphs, and draws on the potential operations of 3-IGN and 2-IGN. In particular, it looks for equivariant functions with an at-most quadratic memory footprint (like 2-IGN) and then extends 2-IGNs with local node neighborhood aggregation (as standard in MPNNs) so as to naturally emulate subgraph GNNs. This extension, called ReIGN, is sufficient to capture all known subgraph GNNs. Finally, the paper proposes subgraph union networks (SUNs), which build on the ReIGN framework, and evaluate this model empirically on subgraph counting benchmarks, demonstrating strong performance.", "questions": "None at the moment", "limitations": "Limitations: The model properties are thoroughly discussed in this paper, and the corresponding limitations of ReIGN are clear. However, SUN could have been better  analyzed in terms of the limitations stemming from its model choices (See ''Weaknesses\" section for more details.)\n\nSocietal Impact: Not applicable", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The unified analysis of subgraph GNNs is very valuable, and the upper-bound is quite useful to understand the limitations of current models. I have briefly checked the 3-IGN construction in the appendix, and all proofs appear sound.\n- The proposed ReIGN framework offers interesting avenues to extend subgraph GNNs, and the coverage of existing models is very good.\n\nWeaknesses: \n- The experimental section is rather limited, as the paper makes no ablation analyses of the SUN model, nor does it conduct case studies to further validate its hypotheses. I believe an interesting question is how SUN performance changes relative to the different components in its equations (i.e., how much gain comes from, e.g., using different update functions v_theta1, v_theta2, using all the different components fed into the update equation).\n- The intuition provided in the paper is not sufficient to fully understand the result. In particular, I had to consult the appendix on multiple occasions to understand orbits and the constructions for the proof. Therefore, I strongly recommend a slightly more detailed coverage of the 3-IGN construction and of orbits to facilitate the explanation\n-  It seems that the font used in the submission differs from what is expected from the NeurIPS template: To demonstrate, the \"Do not distribute\" footer stretches into a second line, which isn't the case in the normal template. This could well be a bug, and clearly is to the disadvantage of the authors (i.e., the font is less generous in terms of space than it should be). Hence, I strongly suggest you revisit your source file. The added space could help you more clearly explain your proofs as suggested above. ", "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": "sznMeQVAz5Z", "reviewer": "Reviewer_F5Bg", "summary": "This work provides a theoretical framework for subgraph GNNs. It first points out that the theoretical analysis of subgraph GNN with node-based subgraph policy can be simplified. Then, with the existing invariant graph networks (IGN) model, the author embeds node-based subgraph GNN into the 3-IGN and thus bounds the expressive power of node-based subgraph GNNs by 3-WL. Besides expressivity analysis, this work also provides a detailed illustration of the design space of subgraph GNN and a new subgraph GNN model, SUN. SUN exhibits good generalization ability in experiments.", "questions": "1. How large is the expressivity gap between IGN(3) and ReIGN(2)?\n\n2. Time complexity of IGN(3)?", "limitations": "The societal impact is adequately addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper is clear and well-written.\n2. The connection between subgraph GNN and 3-WL is novel. \n3. The topic is significant as using subgraph is an important method to boost expressivity.\n\nWeakness:\n1. The discussion is heavily based on IGN. However, this paper does not introduce it.\n2. The design space of subgraph GNN is based on extended IGN(2) and has little connection to the theoretical analysis based on IGN(3).\n3. Time complexity is not discussed.\n4. Discussing how subgraph selection rules affect expressivity will also be very interesting.", "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": "WI3vsIIQPsI", "reviewer": "Reviewer_SuEM", "summary": "This paper extends and analyzes the class of Subgraph GNNs. Importantly, the authors proved that the expressive power of these Subgraph GNNs is bounded by 3-WL. Then, a new family of layers for the class of Subgraph GNNs is proposed, with better generalization abilities. Overall, this is a solid theory paper, and provides a deeper understanding for subgraph GNNs.", "questions": "How is the complexity of subgraph GNN?  ", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: 1. Provide a deeper understanding of subgraph GNN\n2. Design a novel Subgraph GNN, which unifies previous architectures and provides better empirical performance.\nWeakness: 1. Scalability or computation/storage cost is not discussed. \n2. The empirical improvement is not impressive", "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": "NPzrQvkmQv", "reviewer": "Reviewer_GpAd", "summary": "This paper focus on understanding the expressiveness of subgraph graph neural networks. Under its proposed node-based subgraph selection policy, the author demonstrates the representation power as strong as 3-WL test via bridging it with 3-IGNs. In the mean time, the algorithm is realized as Re-IGN and reports superior performance than other existing subgraph GNNs.", "questions": "1. Compared with traditional GNNs that achieves better performance in benchmark datasets, what's the potential reason? I understand it is not a disadvantage that SUN can not beat GIN/CIN on existing benchmarks? Some insights that why SUN with 1 MLP operators cannot beat existing methods with geometric group symmetries, might be helpful for the community. \n\n2. Do you require pre-defined motifs in node-based selection policies?", "limitations": "N.A.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The presentation is clear and easy to follow.\n2. Subgraph GNN is a uprising research topic in graph neural networks, theoretical understanding and its symmetries to existing invariant or equivariant GNNs help explain the design choices and applications.\n3. The extensive experiments in main paper and appendix not only shows its superior performance in family of subgraph GNNs but also on par performance with established traditional graph neural networks.\n\n\n**Weaknesses**\nNot I can think of. I think the experiment table 1 is missing an entry.", "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