A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening
Authors: Guy Bar-Shalom
Yam Eitan
Fabrizio Frasca
Haggai Maron
Venue: NeurIPS 2024 poster (2024)
Keywords: Equivariance
Subgraph GNNs
Graph Products
Primary area: graph_neural_networks

Abstract: Subgraph GNNs enhance message-passing GNNs expressivity by representing graphs as sets of subgraphs, demonstrating impressive performance across various tasks. However, their scalability is hindered by the need to process large numbers of subgraphs. While previous approaches attempted to generate smaller subsets of subgraphs through random or learnable sampling, these methods often yielded suboptimal selections or were limited to small subset sizes, ultimately compromising their effectiveness. This paper introduces a new Subgraph GNN framework to address these issues. 
Our approach diverges from most previous methods by associating subgraphs with node clusters rather than with individual nodes. We show that the resulting collection of subgraphs can be viewed as the product of coarsened and original graphs, unveiling a new connectivity structure on which we perform generalized message passing.

Crucially, controlling the coarsening function enables meaningful selection of any number of subgraphs. In addition, we reveal novel permutation symmetries in the resulting node feature tensor, characterize associated linear equivariant layers, and integrate them into our Subgraph GNN. We also introduce novel node marking strategies and provide a theoretical analysis of their expressive power and other key aspects of our approach. Extensive experiments on multiple graph learning benchmarks demonstrate that our method is significantly more flexible than previous approaches, as it can seamlessly handle any number of subgraphs, while consistently outperforming baseline approaches. 
Our code is available at https://github.com/BarSGuy/Efficient-Subgraph-GNNs.

A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening
Guy Bar-Shalom
Yam Eitan'
Computer Science
Electrical & Computer Engineering
Technion Israel Institute of Technology guy b@campus. technion ac il
Technion Israel Institute of Technology yamei ttatan1997 @gmaamm com
Fabrizio Frasca
Haggai Maron
Electrical & Computer Engineering Technion Israel Institute of Technology fabrizio. frasca. effe@gmalll com
Electrical & Computer Engineering
Technion Israel Institute of Technology
NVIDIA Research
haggaimaron@gmill.co
Abstract
Subgraph GNNs enhance ceessage-passingg GNNs expressivity by representing graphs as sets of subgraphs, demonstrating impressive performance across various tasks. However, their scalability is hindered by the need to process large numbers of subgraphs. While previous approaches attempted to generate smaller subsets of subgraphs through random learnable sampling, these methods often yielded suboptimal selections or were limited to small subset sizes, ultimately compromis- ing their effectiveness. This paper introduces new Subgraph GNN framework to address these issues. Our approach diverges from most previous methods by associating subgraphs with node clusters rather than with individual nodes. We show that the resulting collection of subgraphs can be viewed as the product of coarsened and original graphs, unveiling a new connectivity structure on which we perform generalized message passing.
Crucially, controlling the coarsening function enables meaningful selection of any number of subgraphs. In addition, we reveal novel permutation symmetries in the resulting node feature tensor, characterize associated linear equivariant layers, and integrate them into our Subgraph GNN. We also introduce novel node marking strategies and provide a theoretical analysis of their expressive power and other key aspects of our approach. Extensive experiments on multiple graph learning benchmarks demonstrate that method is significantly more flexible than previous approaches, as can seamlessly handle any number of subgraphs, while consistently outperforming baseline approaches. Our code is available at com/ www.coom//aaaeeee CaarSGuyEffficinn SatpntttSuuup--hOOt
Introduction
38 3 have recently emerged as a promising direction in graph neural network research, addressing the expressiveness limitations of Message Passing Neural Networks (MPNNs) [24] 35 25 In essence, Subgraph GNN operates on graph by transforming into a collection of subgraphs, generated based on a specific selection policy. Examples of such policies include removing single node from the original graph simply marking node without changing the graph's 's original connectivity (26]. The model then processes these subgraphs using equivariant architecture, aggregates the derived representations, and makes graph- node- level predictions. The growing popularity of Subgraph GÑNs stems not only from their enhanced
Subgraph GNNs 4 12 39 27 29
Eqqual contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

expressive capabilities over MPNNS but also from their impressive empirical results, as notably demonstrated on well-known molecular benchmarks 38 T2 3].
Unfortunately, Subgraph GNNs are hindered by substantial computational costs as they necessitate message-passing operations across all subgraphs within the bag. Typically, the number of subgraphs is the number of nodes in the graph, バー for bounded degree graphs, this results in time complexity scaling quadratically (O()²)) in contrast to the linear complexity of standard MPNN. This significant computational burden makes Subgraph GNNs impractical for large graphs, hindering their applicability to important tasks and widely used datasets. To overcome this challenge, various studies have explored methodologies that process only a subset of subgraphs from the bag. These methods range from simple random sampling techniques [8] 4
3 more advanced strategies that learn to select the most relevant subset of the bag to process [ 20 29]. However, while random sampling of subgraphs yields subpar performance, more sophisticated learnable selection strategies also have significant limitations. Primarily, they rely on seiining-timee discrete sampling which complicates the optimization process, as evidenced by the high number of epochs required to train them [20 29]. As result, these methods often allow only a very small bag size, yielding only modest performance improvements compared to random sampling and standard MPNNs.
40
Our approach. The goal of this paper is to devise a Subgraph GNN architecture that can flexibly generate and process variable-sized bags, and deliver strong experimental results while sidestepping intricate and lengthy training protocols. Specifically, our approach aims to overcome the common limitation of restricting usage to a very small set of subgraphs.
Our proposed method builds upon and extends an observa- tion made by Bar-Shalom et al. Bl. who draw an analogy be- tween using Subgraph GNNs and performing pressage-passing operations over a larger "prod- uet graph". Specifically,, it was shown that when considering the maximally expressive (node- based) Subgraph GNN suggested by [ the bag of subgraphs and its update rules can be ob- tained by transforming a graph through the graph cartesian product of the original graph with itself, i.e., GDG, and then processing the resulting graph using a standard MPNN. In our approach, we propose to modify the first term of the product and replace it with a coarsened version of the original graph, denoted T(G). obtained by mapping nodes to super-noder (c.g., by applying graph clustering, see Figure leet)), making the resulting product graph TGG) significantly smaller. This construction is illustrated in Fig- ure rightt. This process effectively associates each subgraph a row in Figure rright) with a set of nodes produced by the coarsening function T. Different choices of T allow for both flexible bag sizes and a simple, meaningful selection of the subgraphs.
T(G) T(G)
T(G) G
Figure 1: Product graph construction. Left: Transforming of the graph into a coarse graph; Right: Cartesian product of the coars- ened graph with the original graph. The vertical axis corresponds the subgraph dimension (super-nodes), while the horizontal axis corresponds to the node dimension (nodes).
2
While performing message passing on TGG serves the core update rule in our architecture, we augment our message passing operations with another set of operations derived from the symmetry structure of the resulting node feature tensor, which call symmetry-based updates. Specifically, our node feature tensor is indexed by pairs (S, v) where S is a super-node and v is an original node. Accordingly, X' is a T X X d tensor, where d is the feature dimension, and T is the number of super-nodes (a constant hyper-parameter) As super-nodes are sets of nodes, X' can also be viewed as (very) sparse 2n x d tensor where 2n is the number of all subsets of the vertex set. Since the symmetric group S,, acts naturally on this representation, we use it to develop symmetry based updates.
Interestingly, we find that this node feature tensor, X. adheres to a specific set of symmetries, which, to the best of our knowledge, is yet unstudied in the context of machine learning: applying
'hhe architecture suggested in 38 was shown to be at least as expressive as all previously studied node-based Subgraph GNNs

---

rep- permutation σ E S. to the nodes in S and to results in an equivalent representation of our node feature tensor. We formally define the symmetries of this object and characterize all the affine equivariant operations in this space. We incorporate these operations into our pressage-passing by encoding the parameter-sharing schemes [30] as additional edge features. These additional update rules significantly improve experimental results. We note that our symmetry analysis may be useful for processing bags derived from other high-order generation policies [29 20 by treating tuples of
nodes as sets.
Inspired by these symmetries and traditional binary-based 4 and shortest path-based 38 node- marking strategies, we propose four natural marking strategies for our framework. Interestingly, unlike the full-bag scenario, they vary in expressiveness, with the shortest path-based technique being the most expressive.
The flexibility and effectiveness of our full framework are illus- trated in Figure depicting de- tailed experimental results on the popular ZINC- 1 12K dataset [3I] Our method demonstrates a sig- nificant performance boost over baseline models in the small bag setting (for which they are de- signed), while achieving results that compare favourably to state- of-the-art Subgraph GNNs in the full bag setting. Additionally, we can obtain results in- in-between these two regimes.
0.06
Full setting
Small bag setting
0.08
0:30
Zinc12k (MAE.
Method
02
SSWL4
Sutgraghhrmer
GVV
x
05 0S-GKN
0/14
PE
OSAN (nigh policy!
Mag-GNK
0.36
Policy
Random
4
Bag size
Figure 2: The performance landscape of Subgraph GNNs with varying number of subgraphs: Our method leads the lower bag-size set, outperforming other approaches in nearly all cases. Additionally, our method matches the performance statc-of-the. art Subgraph GNNs in the full-bag setting. The full mean absolute error (MAE) scores along with standard deviations are available in Table 9 in the appendix.
Contributions. The main con- tributions of this paper are: (1) the development of a novel, flexi- ble Subgraph GNN framework that enables meaningful con- struction and processing of bags of subgraphs of any size; (2)
characterization of all affine invariant/equivvarant layers defined on our node feature tensors; (3) theoretical analysis of our framework, including the expressivity benefits of our node-marking strategy; and (4) a comprehensive experimental evaluation demonstrating the advantages of the new approach across both small and large bag sizes, achieving state-of-the-art results, often by a significant margin.
2 Related work
Subgraph GNNs. Subgraph GNNs 39 27
40 26 12
29 17 38
Original Graph
resent a graph as a collection of subgraphs, obtained by a predefined generation policy. For example, each subgraph can be generated by marking exactly one node in the original graph (see inset F an approach commonly referred to as node marking (6);; this marked node considered the root node in its subgraph. Several recent papers focused on scaling these methods to larger graphs, starting with basic random selection of subgraphs from the bag, and extending beyond with more sophisticated techniques that aim to learn how to select subgraphs. To elaborate, [5] introduced Policy-Learn (PI.), an approach based on two models, where the first model predicts distribution over the nodes of the original graph, and the second model processes bags of subgraphs sampled from this distribution. MAG-GNN 20) employs similar approach utilizing Reinforcement Learning. Similarly to our approach, this method permits high-order policies by associating subgraphs with tuples rather than individual nodes, allowing for the marking of several nodes within subgraph.
Subgraphs
'The Figure was taken with permission from 3
3

---

However, as mentioned before, these approaches involve discrete sampling while training, making them very hard to train (1000-4000 epochs vs. 4000 epochs of the 7INC- 1 2K dataset), and limiting their usage to very small bags. Finally, we mention another high-order method, OSAN, introduced by [29], which learns a distribution over tuples that represent subgraphs with multiple node markings. In contrast to these previous approaches, we suggest a simpler and more effective way to select subgraphs and also show how to leverage the resulting symmetry structure to augment our passagg-passing operations.
methods 3 on
Symmetries in graph learning. Many previous works have analyzed and utilized the symmetry structure that arises from graph learning setups [22 23 18 2]. Specifically relevant to our paper is the work of [22] that characterized basic equivariant linear layers for graphs, the work of [1] that characterizes equivariant maps for many other types of incidence tensors that arise in graph learning, that leveraged group symmetries for designing Subgraph GNNs in a principled
and the works 4 12 way.
3 Preliminaries
Notation. Let G be a family of undirected graphs, and consider a graph G = (V, E) within this family. The adjacency matrix E R=** defines the connectivity of the grapt while the feature matrix X E Rand represents the node features. Here, V and E represent the sets of nodes and edges, respectively, with |V| = indicating the number of nodes. We use the notation 01 ~ U2 to denote that i, and i2 are neighboring nodes according to the adjacency A. Additionally, we define [x] = 21. n), and P(nn)) as the power set of [n]
Subgraph GNNs as graph products. In a recent work, 3 demonstrated that various types of update rules used by current Subgraph GNNs can be simulated by employing the Cartesian graph product between the original graph and another graph, and running standard message passing over that newly constructed product graph. Formally, the cartesian product of two graphs G3 (ni nodes) and G2 (12 nodes), denoted by G,UG2, forms a graph with vertex set ((,)) x (G2).. Two vertices (u1, U2) and (11, 02) are adjacent if either i1 01 and U2 is adjacent to 02 in G2. or U2 = 02 and un is adjacent vi in Gi. We denote by A E m t2 and X' Ra the adjacency and node feature matrices of the product graph; in general, we use calligraphic letters to denote the adjacency and feature matrices of product graphs, while capital English letters are used for those of the original graphs. In particular, for the graph cartesian product, G, the following holds:
AG, = Ai @ I++00 A2.
For a detailed definition of the cartesian product of graphs, please refer to Definition concrete example for the analogy between Subgraph GNNs and the Cartesian product of graphs, we refer to a result by B1, which states that the maximally expressive node-basee Subgraph GNN architecture GNN-SSWL+ 33 , can be simulated by an MPNN the Cartesian product of the original graph with itself, denoted as GDG. As we shall see, our framework utilizes a cartesian product of the original graph and coarsened version of it, as illustrated in Figure (right).
A.I As a
Equivariance. A function L U + W is called equivariant if it commutes with the group action. More formally, given group element, g G, the function L should satisfy L(g v) 9 L(v) for all e E U and g E G. L is said to be invariant if L(g v) = L(v).
4 Coarsening-based Subgraph GNN
This section introduces the Coarsening- Subgraph GNN (CS-GNN) framework. The main idea is to select and process subgraphs in a principled and flexible manner through the following approach: (1) coarsen the original graph via a coarsening function, T - see Figure Ieft); (2) Obtain the product graph Figure I rright) defined by the combination of two adjacencies. Aria) (red edges), Ag (grey edges), which arise from the graph Cartesian product operation (details follow); (3) leveraging the symmetry of this product graph to develop symmetry-bass updates, described by
Overview.
AEquiv (this part is not visualized in Figure The general update of our suggested layer takes the following form
'Edge features also allowed but omitted here for simplicity

---

x (S,)) ( w") (e (...,)))
X "'' B (s x w v (5.z)
Original connectivity (horizontal)
Induced connectivity (vertical)
Symmetry- updates
where the superscript indicates the layer index. In what follows, we further elaborate on these three
steps (in Sections (ott
We note that each connectivity in Equation (2) is processed using a distinct MPNN, and after stacking of those layers, we apply a pooling layer to obtain graph representation; that is, p(
MLP"
Eg *T
denotes the final layer.
For more specific implementation details, we refer Appendix
4.1 Construction of the coarse product graph
As mentioned before, maximally expressive node-based Subgraph GNN can be realized via the Cartesian product of the original graph with itself GLG. In this work, we extend this concept by allowing the left operand in the product to be the coarsened version of G, denoted as T(G). as defined next. This idea is illustrated in Figure !I
Graph coarsening. Consider graph G (V, EV with nodes and adjacency matrix A. Graph coarsening is defined by the function g + G, which maps G to a new graph T(G) = (VT, F
with an adjacency matrix AT E R22 x2" and a feature matrix XT E R²" xd Here, VT, the vertex set of the new graph represents super-nodes defined subsets of [n] Additionally, that nodes in V induce a partition over the nodes of the original graph[] The connectivity E" is extremely sparse and induced from the original graph's connectivity via the following rule:
require
AT S2) = f1
if Ee E 3v E S2 s.t. A(v,u) =
(3)
otherwise,
To clarify, in our running example (Figure 1.. it holds that AT b,c, d), {e)) = 1, while AT (fc), (f)) = 0. For more formal definition, refer to Definition A.3
More specifically, our implementation of the graph coarsening function employs spectral cluster- ing [3 to partition the graph into T clusters, which in our framework controls the size of the bag. This results in a coarsened graph with fewer nodes and edges than G. We highlight and stress that the space complexity of this sparse graph, T(G), is upper bounded by that of the original graph G (we do not store 2n nodes).
Defining the (coarse) product graph DG We define the connectivity of the product graph, see Figure [ right,, by applying the cartesian product between the coarsened graph, T(G), and the original graph, G. The product graph denoted by T(G)OG, and is represented by the matrices where by recalling Equation 11
AT(G)DG E (2" x2"xx xn) and X R²2 xaxd8
we obtain,
(ATi))
A
AT = AT ④ I
The connectivity in this product graph induces the horizontal (Ag) and vertical updates (AT(G)) in Equation (2). visualized in Figure rigght) via grey and red edges, respectively.
'For some of the theoretical analysis. this pooling operation is expressed as: p(x*) MLP" (Es (MLP" x²*Ss ()))
"Our method also supports the case of which is not a partition.
"Other graph coarsening clustering algorithms be readily used well.
*We note that while the node matrix of the product graph, X, can be initialized in various ways, e.g., deep sets-
based architecture (37), in our implementation we simply use the original node features. i.e., X v) X(v). given that X is the node feature matrix of the original graph.
5

---

4.2 Symmetry-based updates
In the previous subsection, we used combination coarsening function and the graph Cartesian product to derive the two induced connectivities Ag. AT(G) of our product graph. We use these connectivities to to perform message-passing on our product graph (see Equation (2).
which incorporates and analyzes additional non-local updates arising from various symmetries (c.g., updating node's representation via all nodes in its subgraphs), this section aims to identify potential new updates that can be utilized over our product graph. To that end, we study the symmetry structure of the node feature tensor in our product graph, (S, The new updates described below will result in the third term in Equation (2) dubbed Symmetry-baa updates (Abquiv) For better clarity in this derivation, we change the notation from nodes (v) to indices (i).
Inspired by recent literature on Subgraph GNNs 12
38
4.2.1 Symmetries of our product graph
Since the order nodes in the original graph G is arbitrary, each layer in our architecture must exhibit equivariance to any induced changes in the product graph. This requires maintaining equivariance to permutations of nodes in both the original graph and its transformation TGG). As a result, recalling that A E (2 xn)"xx)(( x (2" xn) and X E R2" xnxd represent the adjacency and feature matrices of the product graph, the symmetries of the product graph are defined by action of the symmetric group Sn. Formally, a permutation a E Sn acts on the adjacency and feature matrices by:
(a A)(S,, 21, i2) A(o '(Si), o (ii)),o (S2). (i2)).
(5)
()))) = x( (
(6)
where we define the action of E Sn on set S = (ii, i2, it of size k as: a.
=
(a- (1)) (ix)) = =a (S).
4.2.2 Derivation of linear equivariant layers for the node feature tensor
We now characterize the linear equivariant layers with respect the symmetry defined above, focusing on Equation (6). We adopt a similar notation to [22], and assume for simplicity that the number of feature channels is d (extension multiple features is straightforward (22]). In addition, our analysis considers the case where V encompasses all potential super-nodes formed by subsets of [r]] (i.e
the sparse coarsened adjaceney
Our main tool is the characterization of linear equivariant layers for permutation symmetries as parameter-sharing schemes (34] 30 (2). In nutshell, this characterization states that the parameter vectors of the biases, invariant layers, and equivariant layers can be expressed as a learned weighted sum of basis tensors, where the basis tensors are indicators of the orbits induced by the group action on the respective index spaces. We focus here on presenting the final results and summarize them in Proposition 4.1 at the end of this subsection. Detailed discussion and derivations available in Appendix
Equivariant bias and invariant layers. The bias vectors of the linear layers in our space are in 2 Xm As shown in Figure riight), the set of orbits induced by the action of S, satisfies:
(P(nn) [n])/S, = ttt :
n; (+.-}}.
(7)
Here, >A= corresponds to all pairs (S,i) E P(nn) x [n] with |S| = k and of S. and 7* to all pairs with [S] = k and S.
As stated in 33 30 22], the tensor set (B 3 (EEPP
where:
= -
11 if (S,1) E
B7. S.
(8)
otherwise.
are a basis of the space of bias vectors of the invariant linear layers induced by the action of S,.
"This is because the action of S,, is well defined over the index P(V[[n]] [n] but not over V VT

---

[5| -
-
1351 215)
res
res
Resines
5
[8]
5
(65
Figure Visualization via heatmaps (different colors correspond different parameters) of the parameter-sharing scheme determined by symmetries for graph with = 6 nodes, zooming-in on the block which corresponds sets of size two. Left: Visualization of the weight matrix for the equivariant basis B i :82,22 (a total of 35 parameters in the block). Right: Visualization of the bias vector for the invariant basis B (a total of 2 parameters in the block). Symmetry- updates reduce parameters more effectively than previously proposed linear equívariant layers by treating indices as unordered tuples (see Appendix E.3 for a discussion).
Weight matrices. Following similar reasoning, consider elements (S1, S2, i2)
(P([i)) x
[n] x P(n])) x [z])- In Appendix we characterize the orbits of S, in this space as a partition in which each partition set is defined according six conditions. Some of these conditions include the sizes of S1, S2 and S1 n S2, which remain invariant under permutations. Given an orbit, TE (P([n)) x [n] x P(nn)) x [nl)/S.. we define basis tensor, B E R22 xnx2" xn by setting:
1, if i1, eT; 0, otherwise.
B Spinsaad
visualization of the two basis vectors in Equations (8) and (9) is available Figure The following (informal) proposition summarizes the results in this section (the proof is given in Appendix G
Proposition 4.1 (Basis of Invariant (Equivariant) Layers). The tensors B (BF) in Equation (Equation ( form an orthogonal basis (in the standard inner product) of the invariant layers and biases (Equivariant layers weight matrix).
4.2.3 Incorporating symmetry-based updates in our framework
In the previous subsection, we derived all possible linear invariant and equivariant operations that respect the symmetries of our product graph. We now use this derivation to define the symmetry-based updates Equation (2), which correspond to the construction ABqui and the application of an MPNN.
To begin, we note that any linear equivariant layer can be realized through an MPNN [3 applied to a fully connected graph with appropriate edge features. This is formally stated Le the main idea is to encode the param- eters on the edges of this graph (see visualization inset). Thus, the natural construction of Arquiy corresponds a fully connected graph, with appropriate edge features derived from the parameter-sharing scheme we have developed.
i.j
= Σ
x
J
However, one of our main goals and guidelines develop- ing our flexible framework is to maintain efficiency, and to align with the (node-based) maximally expressive GNN, namely GNN-SSWL+ [3 coarsening function, ( G (which correspond the full-bag setting). To achieve this, we opt for sparser choice by using only a subset of the basis vectors (defined in Equation (9)) to construct AEquiv Specifically, the ma- trix Arquiv corresponding
d1
di
di
dlf
di
3
e
3, for the case of trivial
the chosen subset of basis
vectors is visualized inset the seannterr-hhainng scheme is represented by edges with matching

---

colors. To clarify, the nodes (S. that satisfy v E S "send messages" (i.e., broadcast their rep- resentation) to all the nodes (S', E') such that = v'. A more formal discussion regarding our implementation of those symmetry based updates is given in Appendix F.4
Maintaining sparsity. While the updates above are defined over the sparse representation of the coarse product graph, in practice we use its dense representation, treating it as a graph over the set of nodes V x VT, which requires space complexity O [V]). The update rules above are adapted to this representation simply by masking all nodes (S, v) in the sparse representation such that S & VT. We note the models using the resulting update rule remain invariant to the action of S.,. See discussion in [
4.3 Marking Strategies and Theoretical Analysis
One of the key components of subgraph architectures is their marking strategy. Two widely used approaches in mode-based subgraph architectures are binary-based node marking 4 and distance- based marking (38), which were proven be equally expressive in the full-bag setup (38] Empirically, distance-basse marking has been demonstrated to outperform other strategies across several standard benchmarks. In this section, our aim is to develop and theoretically justify an appropriate marking strategy. specifically tailored to the structure of our product graph. We present and discuss here our main results, and refer to Appendix for a more formal discussion.
Building on existing marking strategies and considering the unique structure of our product graph, we propose two natural extensions to both the binary node marking 4 and distance-based marking strategies B8 Extending binary node marking, we first suggest Simple Marking (Ts), where an element (S, is assigned binary feature that indicates whether node belongs to subgraph S (v E 5). The second extension, Node + Size Marking (Tss), builds on the simple marking by assigning an additional feature that encodes the size of the super-node S.
For distance-based strategies, we propose Minimum Distance (TMD), where each element (S, v) is assigned the smallest (minimal) shortest path distance (SPD) from node to any node E S. Finally, Learned Distance Function (TLD) extends this further by assigning to each element (S, v) the output of permutation-invariant learned function, which takes the set of SPDs between node and the nodes in S as input.
Surprisingly, unlike the node-base based full-bag case, we find that these marking strategies are not all equally expressive. We conveniently gather the first three strategies as Il { TSS, TMD) and summarize the relation between all variants follows:
Proposition 4.2 (Informal - Expressivity of marking strategies.). (i) Strategies in 11 are all equally expressive, independently of the transformation function T. (ii) The strategy FLD at least as expressive as strategies in II. Additionally, there exists transformation, cottmmaatiiofunctiiiooo functions s.I. it is strictly more expressive than all of them.
The above is formally stated in Propositions C.I and C.2 and more thoroughly discussed in Ap- pendix C In light of the above proposition, we instatiate the learned distance function TLD strategy when implementing our model, as follows,
Xs.
Eda(v,u)
(10)
WES
where (v, u) denotes the shortest path distance between nodes and u in the original
CTO
Coarsening Function and Expressivity. We investigate whether our CS-GNN framework offers more expressiveness compared to directly integrating information between the coarsened graph and the original graph.
The two propositions below illustrate that a simple, straight forward integration of the coarsen graph with the original graph (this integration is referred to the sum graph formally defined in Definition D.2), and further processing it via standard message- message-passing. results in a less expressive architecture. Furthermore, when certain coarsening functions are employed within the CS-GNN framework, our resulting architecture becomes strictly more expressive than conventional node-based
1Too facilitate this, we maintain a lookup table where each index corresponds to a shortest path distance. assigning learnable embedding, Zdg(s.n)) RR each node (S, v).
8

---

subgraph GNNs. These results suggest that the interplay between the coarsening function and the subgraph layers we have developed enhances the model's 's overall performance. We summarize this informally below and provide a more formal discussion in Appendix D
Proposition 4.3 (Informal CS-GNN goes beyond coarsening). For any transformation function T, CS-GNN can implement taasagge-pssinng on the sum graph, hence being at least as expressive. Also, there exist transformations T s.t. CS-GNN is strictly more expressive than that.
Proposition 4.4 (Informal - CS-GNN vs node based subgraphs). There exist transformations T's s.t. our CS-CCN model using T as its coarsening function is strictly more expressive than GNN-SSWL+
5 Experiments
We experimented extensively over seven different datasets to answer the following questions: (Q1) Can CS-GM GNNGNN outperform efficient Subgraph GNNs operating on small bags? (Q2) Does the additional symmetry-based updates boost performance? (Q3) Does CS-GNN offer a good so- lution in settings where full-bag Subgraph GNNs cannot be applied? (Q4) Does CS-GNN in the full-bag setting validate its theory and match state-of-the-art full-bag Sub- graph GNNs?
Table 1: Results ZINC- ZINC-12K dataset. Top two results are reported as First and Second.
Method
Bag size
ZINC (MAE L)
35
T
0.163
0.004
OSAN A
T 2
0.177 + 0.016
T
0.131 0.005
PL 5
T = 2
0.120 1 0.003
Mag-GNN
T 0.106 + 0.014
In the following sections, present main results and refer to Appendix F for additional experiments and details.
Ours
T 2
0.109 1 0.005
Random
T 3
0.124 = N/A
Mug GNN
20
T = 3
0.104 + N/A 0.005
Baselines. For each task, we include several baselines, The RANDOM baseline corresponds to random subgraph selection. We report the best performing random baseline The other two (non- random) baselines are: (1) LEARNED 5 20 29], which
Ours
T 3
0.096
Random 20
T 4 T T
0.125 + N/A
Mag-GNN
N/A
from all prior work [5] 20 29 3
Ours
0.090 = 0.003
Random 5
T 5
0.113 1 0.006
represents methods that learn the specific subgraphs to
PL. 5
T 5
0.109 + 0.005
used; and (2) FULL 38 3, which corresponds to full-bag Subgraph GNNs.
T
0.095 0.003
GNN-SSWL+ 38
Full
0.070 0.005
Subgraphomeer
Full
0.067 1 0.007
ZINC. We experimented with both the ZINC-12K and
Subgraphomer++PF
Full
0.063 + 0.001
Ours
Fall
0.062 0.0007
ZINC-FULL datasets [3T 14 [0]. adhering to 500k parameter budget as prescribed. As shown in Table 1
CS-GNN outperforms all efficient baselines by a significant margin, with at least a +0.008 MAE improvement for bag sizes T E {3, 4, 5). Additionally, in the full-bag setting, our method recovers state-of-the-art results. The results for ZINC-FULL are available in Table & in the Appendix.
OGB. We tested our framework on several datasets from the OGB benchmark collection (16]. Table 4 shows the performance of our method compared to both efficient and full-bag Subgraph GNNs. Our CS-GNN outperforms all baselines across all datasets for bag sizes T E (2,5), except for the MOLHIV dataset with T 2, where PL achieves the best results and our method ranks second. In the full-bag setting, CS-GNN is slightly outperformed by the top-performing Subgraph GNNs but still offers comparable results.
Peptides. We experimented on the PEPTIDES- FUNC and PEPTIDES-STRUCE datasets 9 which full-bag Subgraph GNNs already strug- gle to process evaluating CS-GNN'S ability to scale to larger graphs. The results are sum- marized in Table 2, CS-GNN outperforms all MPNN variants. even when incorporating struc- tural encodings such as GATEDGCN+RWSE Additionally. our method surpasses the ran- dom baseline on both datasets.
Table 2: Results on PEPTIDES dataset.
PEPTIDES-PUNC
PEPTIEEs STRUCT (MAE J)
Model L/ Dataset
(A
GCN 19
0. 0.5930++0.002
0.34196:0. 000013
0.5498-40.0u7
0.3547
GatedGCN 7
0.586440.0077
0.3420=00000 200003
0.6069-10.0035
0.3357=0 0006
Random
0.392110.080 005
0.2591110.00 0021
0.6156+40.ung
0.2539++0.00
ll For the PEPTIDES datasets, we benchmarked our model against the random variant of Subgraphormer PE, which similarly incorporates information from the Laplacian eigenvectors. To ensure fair comparison.

---

Ablation study symmetry-based updates. We assessed the impact of the symmetry-basee update on the performance of CS-GNN. Specifically, we ask, do the symmetry-basee up-
Table Ablation study.
Bag sizee
w/
wlo
dates significantly contribute to the performance of CS-GNN?
Tw2
0.109
005
0.143 003
To evaluate this, we conducted several experiments using the
T=3
0.096.0 005
0.101:0.0000 006
ZINC-12K dataset across various bag sizes, T E {2,3, 4, 5). comparing CS-GNN with and without the symmetry-based up-
T=4
0.090 003
0.106 0.00
0.095+0.003
0.104
date. The results are summarized in Table [ It is clear that the symmetry-based updates play a key
role in the performance of CS-GNN. For bag size of T = 2, the inclusion of the symmetry-based update improves the MAE by a significant 0.034. For other bag sizes, the improvements range from 0.005 to 0.016, clearly demonstrating the benefits of including the symmetry- updates.
Discussion. In what follows, we address re- search questions Q1 to Q4. (A1) Tables T and cclearly demonstrate that we outperform efficient Subgraph GNNs (which operate a small bag) in 10 out of 12 dataset and bag size combinations. (A2) Our ablation study on the ZINC- 1 2K dataset, as shown in Table ]
Table 4: Results OGB datasets. The top two results are reported as First and Second.
Model L Dannset
Hag size
MOLRIV (ROC-AUCC
1)
MOLBACE (ROC-AUIC
(RMSE ()
MOLESOL
GIN 35
T
1
75.38=1.40 40
72.97=4.00
1.17 1.17==0.05
Random
T
77.55
75.30++:225
0
19.13:00000
78.40-2.95
0.877.0
clearly demonstrates the benefits of the symme- try-based updates across all the considered bag sizes. (A3) Table demoonsaeesss that CS-GNN provides an effective solution when the full-bag setting cannot be applied, outperforming all baselines. (A4) On the ZINC-126 dataset (see T.. CS-GNN achieves wfate-ofthhe-ee re- sults compared to Subgraph GNNs. On the
Mag-GNN
200
T=
77.1221.13
Ours
r
77.72=0.76
80.58=1.04
0.850#0.022 0224
OSAN
T- 3
0.95010.188
OSAN
30
==5 5
76.30:33:00
PL 9
m
78 78.49=1.01
78.39-2222
0.8833+0.055 0.002
Random
77.30+22.0 56
78.14+2.80
0.900=0.082
79.09=0.90
79.64=1.48
0.863300000 020
GNN SSWL- 36
Full
79. 00.30
82.70= 90
0.837=20019
Sabgraphormer
Full
80.38
81.6213.55
0.85220:013
Salgruphormer-
Full
84.35_20.03
0.826..0.0
70.4420.87
80.71=1.76
0.81440..00
OGBG datasets (see T), our performance is comparable to these top-performing Subgraph GNNs.
6 Conclusions
In this work, we employed graph coarsenings and leveraged the insightful connection between Subgraph GNNs and the graph Cartesian product devise CS-GNN, a novel and flexible Subgraph GNN that can effectively generate and process any desired bag size. Several directions for future research remain open. Firstly, experimented with spectral clustering based coarsening, but other strategies are possible and are interesting to explore. Secondly, in our symmetry-basee updates, we have only considered portion of the whole equivariant basis we derived: evaluating the impact of other basis elements deserve further attention, both theoretically and in practice. Finally, whether Higher-Order Subgraph GNNs can benefit from our developed parameter-sharing scheme remains an intriguing open question.
Limitations. Our method operates over a product graph. Although we provide control over the size of this product graph, achieving better performance requires a larger bag size. This can become a complexity bottleneck, particularly when the original graph is large.
Acknowledgements
The authors are grateful to Beatrice Bevilacqua, for helpful discussions, and constructive conversations about the experiments. HM is the Robert J. Shillman Fellow and is supported by the Israel Science Foundation through a personal grant (ISF 264/23) and an equipment grant (ISF 532/23). FF is funded by the Andrew and Erna Finci Viterbi Post- tost-ooctrral Fellowship; FF partially performed this work while visiting the Machine Learning Research Unit at TU Wien led by Prof. Thomas Gärtner.
we used a single vote and the same exact bag size of 35 subgraphs. Additionally, since Subgraphormer + PE employs GAT (32 as the underlying MPNN, we also utilized GAT for this specific experiment to maintain consistency and fairness.
10

---

References
[1] Marjan Albooych, Daniele Bertolini, and Siamak Ravanbakhsh. Incidence networks for geo- metric deep learning. arXiv preprint arXiv:/905.1 1460, 2019.
[2] Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. arXiv preprint arXiv:2006.15646, 2020.
[3] Guy Bar-Shalom, Beatrice Bevilacqua, and Haggai Maron. Subgraphormer: Unifying subgraph GNNs and graph transformers via graph products. Forty-first International Conference on Machine Learning, 2024. URL https: httpps//ppenrevieww wwwp:ew..eeeeeeeeeeeeeeeeeeeeeee www//efoouuie id
[4] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan. Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. International Conference on Learning Representations, 2022.
[5] Beatrice Bevilacqua, Moshe Eliasof, Eli Meirom, Bruno Ribeiro, and Haggai Maron. Efficient subgraph gnns by learning effective selection policies. International Conference on Learning Representations, 2024.
[6] Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https: h /www wandb.com. Software available from wandb.com.
[7] Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint 17X053171 2017.
[8] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. In Advances in Neural Information Processing Systems, volume 34, 2021.
[9] Vijay Prakash Dwivedi, Ladislav Rampášek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. Advances in Neural Information Processing Systems, 35:22326-22344 2022.
[10] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48 2023.
[11] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 1903:/90300200 0244822 2019.
[12] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-31390, 2022.
[13] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pages 1263-1272. PMLR, 2017.
[14] Rafael Gómez-Bombardue Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobaue Benjamín Sánchez-Lengeine Dennis Sheberla, Jorge Aguilera-Iparraguiree 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 276, 2018.
[15] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitikk Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint 19X5v 2019.
[16] Weihua Hu, Matthias Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs Advances in neural information processing systems, 1122218--2233, 2020.
[17] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with igngnss The Eleventh International Conference on Learning Representations, 2022.

---

[18] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances Neural Information Processing Systems, 32, 2019.
[19] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2016.
[20] Lecheng Kong, Jiarui Feng, Hao Liu, Dacheng Tao, Yixin Chen, and Muhan Zhang. Mag- gnn: Reinforcement learning boosted graph neural network. Advances in Neural Information Processing Systems, 36, 2024.
[21] Jungmin Kwon, Jeongseop Kim, Hyunseo Park, and Kwon Choi. Asam: Adaptive sharpness- aware minimization for scale-invariant learning of deep neural networks. In International Conference on Machine Learning, 2021.
[22] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint arXtv:1882.099902. 2018.
[23] Haggai Maron, Heli Ben- Dan-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[24] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[25] 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 a 12.09992, 2021.
[26] Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. In International Conference Machine Learning, pages 17323-17345. PMLR, 2022.
[27] Pál András Papp. Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 34:21997-22009, 2021.
[28] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[29] Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks. Advances in Neural Information Processing Systems, 35: 21030-21045, 2022.
[30] Siamak Ravanbakhsh. Jeff Schneider, and Barnabas Poczos. Equivariance through parameter- sharing. In International conference on machine learning, pages 2892-2901. PMLR, 2017.
[31] Teague Sterling and John Irwin. Zine 15 ligand discovery for everyone. Journal of chemical information and modeling,
2015.
[32] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2017.
[33] Ulrike Von Luxburg. A tutorial spectral clustering. Statistics and computing, 17:395 2007.
[34] Jeffrey Wood and John Shawe-Taylor. Representation theory and invariant neural networks. Discrete applied mathematics, (9(1-2):33 -00, 1996.
[35] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
12

---

[36] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie, Small relu networks are powerful memorizers: tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32, 2019.
[37] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
[38] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lemman tests. International Conference on Machine Learning. 2023.
[39] Muhan Zhang and Pan Li. Nested graph neural networks. In Advances in Neural Information Processing Systems, volume 34, 2021.
[40] 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.
13

---

Appendix
The appendix is organized follows:
In Appendix A
we provide some basic definitions that will be used in later sections of the
paper.
In Appendix discuss some theoretical aspects of model implementation, and its
relation to Equation (2)
In Appendix C we define four natural general node marking policies and analyze their theoretical effects on our model, well as their relation to some node-based node marking policies. Finally, we provide a principled derivation of one of these policies using the natural symmetry of our base object.
In Appendix [..] we compare our model to node-hased subgraph GNNs, which are the most widely used variant of subgraph GNNs. Additionally, we demonstrate that different choices of coarsening functions can recover various existing subgraph GNN designs.
In Appendix D.2 we demonstrate how our model can leverage the information provided by the coarsening function in effective way, comparing its expressivity to natural bascline which also leverages the coarsening function. We show that for all coarsening functions, we are at least expressive the baseline and that for some coarsening functions, model is strictly more expressive.
In Appendix D
we delve deeper into the characterization of all linear maps L: (P([)))((]] + that are equivariant to the action of the symmetric group.
(((()))))))) (m]
In Appendix F we provide experimental details reproduce the results in Section 5 well as comprehensive set of ablation studies.
Appendix G we provide detailed proofs all propositions this paper.
A Basic Definitions
We devote this section to formally defining the key concepts of this paper, well as introducing new useful notation. We start by defining the two principle components our pipeline, the cartesian product graph and the coarsening function:
Definition A.1 (Cartesian Product Graph). Given two graphs G1 and G2, their Cartesian product G G is defined as:
The vertex set DZ2 = V(G) V(G2).
Vertices (u1, u2) and (V1, U2) in Gj D2 are adjacent if:
U1 = U1 and uy adjacent to U2 in G2, or - 1/2 02 and un is adjacent to in in G1.
Definition A.2 (Coarsening Function). A Coarsening function T(-) is defined as function that, given a graph G = (V, E) with vertex set V = [n] and adjacency matrix A E Ruxn, takes A as input and returns a of "super-nodes" ((A) C P([n)). The function T()) considered equivariant for any permutation a E Sn, the following condition holds:
T(o A) -(A).
(11)
Here, a and a T(A) represent the group action of the symmetric group S, on Ruxx and P([n) respectively.
coarsening function allows us to naturally define graph structure on the "super-nodes" obtained from a given graph in the following way:
Definition A.3 (Coarsened Graph). Given a coarsening function T(-) and a graph G = (V, with vertex set V [ns) adjacency matrix A _xx,, abuse notation and define the coarsened graph
T(G) = (VT, ET as follows:
T T(A)
14

---

.E = (1S,8)) S, E T(A), E S, E S' s.t. A = 13.
The adjacency matrix of the coarsened graph can be expressed two ways. The dense representation Aense E Ix|V" is defined by:
( ET
A ( (S,
(12)
0 otherwise.
The sparse representation AT Aparse
E ((N(()))P(())) is defined by:
f S,5' 1 ,
E E
A Sparce (S (
(13)
otherwise.
We note that if the coarsened graph T(G) has corresponding node feature map X' : V Rd also has sparse and dense vector representations defined similarly. Though the dense representation seems more natural, the sparse representation is also useful, the symmetric group S, acts it by:
(S = A (o (S),
(14)
When the type of representation is clear from context, we abuse notation and write AT. Note also that the above discussion, we have used the term "node feature map". Throughout this paper, in order to denote the node features of graph G (V,E) with V| n,, use both the vector representation X E Raxd and the map representation X' V - Rd interchangeably. Now, recalling that our pipeline defined to create and update a node feature map XSS v) supported on the nodes of the product graph GCT(G), we define general node marking policy, the following way:
Definition A.4 (General Node Marking Policy). A general node marking policy T(.;)). is a function which takes as input graph G (V, E), and coarsening function T-)), and returns a node fealure map X V x V + Rd.
In Appendix C We provide four different node marking policies, and analyze the effect on our pipeline. We move define the general way in which update given node feature map the product graph.
Definition A.5 (General CS- US-GerLayer Update). Given a graph G = (V,E) and a coarsening function T()), let X* (*, v) V VT + Rd denote the node feature map at layer The general CS CS-GNNlayer update is defined by:
((x))= (S()))),
x (S,)) =
(S,, | 1' u..
(58,))(((((),))),ssss))) vor $R.
(15)
(ss, S' V u
(X.. of E V.s. v' VVs.des)))
Here, fe is an arbitrary (parameterized) continuous function, agg,, i= 1,...4 are learnable permulation invariant aggregation functions, e Es.sy are the (optional) edge features of G and T(G) respectively and the function P[[n]) [n] x P([n]) x [n] - RRd maps each tuple of indices (S, v, S¹, S'),"',))) ) to vector uniquely encoding the orbit of v under the action of S, described in
73
We note that for brevity, the notation used the main body of the paper omits the aggregation functions aggi..... agg", and the edge features from the formulation of some of the layer updates. However, we explicitly state each component of the update, as we heavily utilize them in later proofs.
We also note that this update is different than the general layer update presented in Equation (2), as doesn't 't use global updates characterized in 9 The reason for this is that some of the global updates have an asymptotic runtime of Onn2)where where the number of nodes the input graph. As goal was to create models that improve on the scalability of standard subgraph GNNs which have
15

---

an asymptotic runtime of Ón²)) We decided to discard some of the general global updates and keep only the ones that are induced by the last two entries in equation [ which all have linear runtime. we employ the following pooling procedure on the
After a stacking of the layers in Equation T5) final node feature map- XT:
x(x²) MLP2
Σ EVV
MLP1 Σ
x" x*(
(16)
Finally, we define the set of functions that can be expressed by our model:
Definition A.6 (Expressivity of Family of Graph Functions). Let F be a family of graph functions, we say that F. can express a graph function g(-) if for every finite family of graphs G there exists function I F such that:
(17) Here, G is finite family of graphs if all possible values of nodeledge features of the graphs form finite set, and the maximal size of the graphs within G is bounded.
S(G) g(G) EG
Definition A.7 (Family of Functions Expressed By CS-GNN). Let be general node marking policy and T be a coarsening function. Define S(T T) to be the family of functions, which when given input graph G = (V, E), first compute (S, v) using π (GG T). then update this node feature map by stacking layers of the form 15 and finally pooling (S, 8) using equation [6 We define CS- CS-GNN(T TT) to be the set of all functions that can be expressed by S(T, n)
B Theoretical Validation of Implementation Details
In this section, we provide implementation details of our model and prove that they enable us to recover the conceptual framework of the model discussed thus far. First, note that in Section 4.2 characterized all equivariant linear maps L IR [[)])x[o] -> R P((]))((>) in order incorporate them into our layer update. Given the high dimensionality of the space of all such linear maps, and in order parameters, demonstrate that is possible to integrate these layers into our layer update by adding edge features to a standard MPNN model. This is formalized in the following proposition:
Lemma B.1 (Parameter Sharing MPNN), Let B,.... .B. Ruxn be orthogonal matrices with entries restricted to 1, and let W1,.. W3 pddd' denote sequence of weight matrices. Define B4 Ei B, and choose .1....2k
2g E Rdd to be of unique vectors representing encoding of the index set. The function that represents an update via parameter sharing:
1(X) = Σ B
(18)
can be implemented on any finite family of graphs G, by a stack of MPNN layers of the following form [13]
m
Σ M'(X! en,),
(19)
NENE, (v)
x!+1 U¹ (X! m.).
(20)
where U 2 are multilayer perceptrons (MLPs). The inputs to this MPNN are the adjacency matrix B4, node feature vector X, and edge features the feature of edge (u, v) is given by:
CupV
B.(Buu
(21)
1=1
Here, B,(u,)) v) denotes the (u, v) entry matrix B,,
The proof is given in Appendix The analysis in Section 4.2 demonstrates that the basis of the space of equivariant linear maps Additionally, we notice that some of the equivariant linear functions have asymptotic runtime of
TR P())))x - [[[]]]]X satisfies the conditions of Lemma F.1
16

---

Ó(n²) where is the number of nodes in the input graph. As our main goal is to construct a more scalable alternative to node-based subgraph GNNs, which also have runtime of (n²)), we limit ourselves to a subset of the basis for which all maps run in linear time, This is implemented by adding edge features the adjacency matrices Ap, and Ap.. defined later in this section.
We now move on discussing our specific implementation of the general layer update from Defini- tion A.5
Given a graph G E) and coarsening function T, aim to implement this general layer update by combining several standard message passing updates on the product graph (TT. In the next two definitions, we define the adjacency matrices supported on the node set V x VT which serve as the foundation for these message passing procedures, and formalize the procedures themselves.
Definition B.1 (Adjacency Matrices on Product Graph), Let G = (V,E) be graph with adjacency matrix A and node feature vector X, and let (-)) be coarsening function. We define the following four adjacency matrices on the vertex set VJ x V:
v G n', == S'
e'
(22)
0
otherwise.
S STIG)) S v v otherwise.
0,
(23)
0
V E w=
(,,
(24)
0
otherwise.
1 V' =
15 =
(25)
otherwise.
Given edge features (Eow' I NG v/} and {ēs,s I ~TGG) s'} corresponding the graphs G and T(G), respectively, we can trivially define the edge features corresponding to Ag and Agt as follows:
v, = Ev,t's eT( (S, ēs.s".
(26)
(27)
In addition, for i 1,2, we define the edge features corresponding adjacency matrices Ap, as follows:
EP. US, v') =(S,,,,',
(28)
Here, the function 2 P((n)) x [n] P(nn) x [n] - Rd maps each tuple v = (S, v. S'
v') to
vector uniquely encoding the orbit of v under the action of Sn as described in Equation 73
Definition B.2 (CS-GNN Update Implementation), Given graph G EV, and coarsening function T T-)), let A .....4 A4 enumerate the set of adjacency matrices (Ac, (Ac,))()) Ar, We
define a CS-GNN layer update in the following way:
(S = U/ (a+e)) (1++))xx''S) -S))
Σ (S.))
(' +e..S,,)) (29)
Σ x
x²+1(S,0) U
(30)
Here (', v) and x v) denote the node feature maps of the product graph at layers l and o')....,.. e (S, S' v') denote the edge features associated with
1+1, respectively. et S. " adjacency matrices .t...., As. e,,..., represent learnable parameters R. and U Ut,..., Ut. Um M all refer multilayer perceptrons.
17

---

The next proposition states that using the layer update defined in equations 29 and 30 is enough to efficiently recover the general layer update defined in equation T3
Proposition B.1 (Equivalence of General Layer and Implemented Layer). Ler T-)) be coarsening function, π be generalized node marking policy, and G be finite family of graphs. Applying stack of general layer updates as defined in Equation 75to to the node feature map X(S, v) induced by
(G, T, can be effectively implemented by applying a stack of layer updates specified in Equations
29 and 301o to (SS,)) v). Additionally, the depths of all MLPs that appear in 29 and 30 can be bounded by 4.
C Node Marking Policies- Theoretical Analysis
In this section, we define and analyze various general node marking policies, starting with four natural choices.
Definition C.1 (Four General Node Marking policies). Ler G (V, E) be a graph with adjacency matrix A E Raxx and node feature vector X R and let (-)) be coarsening function. All of the following node marking policies take the form:
T(G T) = X(S, v) = [Xu,, by (S,
(31)
where [1y]] denotes the concatenation operator: We focus on four choices for b (S, v):
1. Simple Node Marking:
= {1
if E s, if $ S.
by (S,
(32)
We denote this node marking policy by wT..
2. Node + Size Marking:
i E s, if S. We denote this node marking policy by Tys-
SS) (0,
(8,
(33)
3. Minimum Distance:
by (S, v) min do(r,
(34)
ee
where de(v, v') is the shortest path distance between nodes and v in the original graph. We denote this node marking policy by TDD-
4. Learned Distance Function:
by = ((fd)))(((dcv....) I d' E S})
(35)
where (6-) is a learned permutation--nvarianne function. We denote this node marking policy by TLD-
We note that when using the identity coarsening function T(G) G. general node marking policies output node feature maps supported on the product V x V. Thus, they can be compared to node marking policies used in node-based subgraph GNNs. In fact, in this case, both ms and Tss reduce to classical node-based node marking, while TMD and TLDD reduce to distance encoding. The definitions of these can be found in [38]. Interestingly, even though in the case of node-based subgraph GNNSs, both distance encoding and node marking were proven to be maximally expressive [38), in our case for some choices of T. TLD is strictly more expressive than the other three choices. The exact effect of each generalized node marking policy on the expressivity of our model is explored in the following two propositions.
Proposition C.1 (Equal Expressivity of Node Marking Policies). For any coarsening function T(-) the following holds:
CS- CS-GNN(T, TT) CS-GNN(T, TTS) = CS-GNN(T, (TMD).
(36)
18

---

Proposition C.2 (Expressivity of Learned Distance Policy). For any coarsening functiion T(-) the following holds:
CS-GNN(T, TT) S CS-GNN(T, TIn).
(37)
In addition, for some choices T()) the containment is strict.
The proofs of both propositions be found in Appendix G Finally, provide principled approach to deriving a generalized node marking policy based on symmetry invariance, and prove its equivalence ssss- Given graph G (V; E) with V [n]]. adjacency matrix A, and node feature vector X E Raxd along with a coarsening function T(-). We define action of the symmetric group S, on the space IR x( as follows:
() (S), for o Su, & E P(A)xl
(38)
Now, for each orbit y E (P([n)) [n])/Sn, define 1, (P(N)) follows:
1, (S, = { [ (S,v) E
(39)
otherwise.
Choosing some enumeration of the orbit set (P( x [m])/S, = 7hh We now define the invariant generalized node marking policy Juy by first setting:
b-parrs
(S. v) ((nn)) x [n] R
Tie
and
VT x V R
follows:
jsparso (S, v) = [1% (S, v). 1e (S,v)
S P(V), VE SEVT, VEV.
(40)
Dmn (S, v) 1/sparse (S, v)
(41)
Then, we define the node feature map induced by Tinw as:
vi (S,0) = [Xu, U))
(42)
Interestingly, Tine, derived solely from the group action of S. on P[[n]) x [m]. is equivalent to the generalized node marking policy ass. This stated more rigorously in the following proposition:
Proposition C.3 (Node Size Marking Invariant Marking). Given a graph G (V, E) with node feature vector X E R and coarsening function T(-). let 7s n be the node feature maps induced by vss and Tin respectively. Recall that:
S (S, v) = [X v. Dis (S, v)], X aa (S = [X,, I (S, v)].
(43)
(44)
The following now holds:
Der, (S, (Ww.bnanSSSSS.. VSEVT, VOEV.
(45)
Here, OHE denotes a one-hot encoder, independent of the choice of both G and
The proof of proposition C33 can be found in Appendix G
D Expressive Power of CS-GNN
D.I Recovering Subgraph GNNs
In this section, we demonstrate that by choosing suitable coarsening functions, our architecture replicate various previous subgraph GNN designs. We begin by focusing on node-based models, which are the most widely used type. We define variant of these models which was proven in (38 to be maximally expressive, and show that our approach can recover it.
Definition D.1 (Maximally Expressive Subgraph GNN), We define MSGNN((TMM) as the set of all functions expressible by the following procedure:
19

---

1. Node Marking: The representation of (u, v) E V x V is initially given by:
(u, [1 ifu === v, ifu #
(46)
2. Update: The representation of tuple (u, v) updated according to:
x (u. X (u, (u, u). X (u. v), aggi (gil((x'0)) (u, (1, co," v/ ~ v.. agg' (x2' (v, (.) en, ~ uut
(47)
3. Pooling: The final node feature vector X² (u, v) is pooled according to:
MLP₂
Σ MLP1 BEV
ExT(u,))) LEV
(48)
Here,for any 1 E [T], is any continuous (parameterized) functions, agg' .ggg2 are any continuous (parameterized) permulation-invaricc functions and MLP MMLP are multilayer preceptrons.
Proposition D.1 (CS-GNN Can Implement MSGNN), Let T()) be the identity coarsening function defined by:
T(G) = [(t) l
VG = EV, CS-GNN AT) (MNGNN(TNN))
(49)
The following holds:
(50)
The proof of proposition D.I can be found in Appendix We observe that, similarly, by selecting the coarsening function:
T(G) E AG = -V,
(51)
one can recover edge-based subgraph GNNs. An example of such a model presented in (DS-
GNN), where it was proven capable of distinguishing between two 3-WL indistinguishable graphs, despite having asymptotic runtime of (mm²), where is the number of edges in the input graph. This demonstrates our model's 'ss ability to achieve expressivity improvements while maintaining (relatively) low asymptotic runtime by exploiting the graph's 's sparsity through the coarsening function. Finally, we note that by selecting the coarsening function:
T(G) {S P(V) |S| = k}
G= GV(VEE (V,
(52)
We recover unordered variant of the k-OSAN model presented in (29]
D.2 Comparison to Natural Baselines
In this section, demonstrate how model can leverage the information provided by the coars- ening function T--) in an effective way. First, we define a baseline model that incorporates T in straightforward manner. We then prove that, for any T--), our model is at least as expressive this baseline. Additionally, we show that for certain choices of (--), our model exhibits strictly greater expressivity. To construct the baseline model, we first provide the following definition:
Definition D.2 (Coarsened Sum Graph). Given a graph G = (V, F) and coarsening function functtio T(-). we define the coarsened sum graph GT (VT ET) by:
VI. = VUVT.
E. = FUET ((S,0) DEV
graph G had node feature vector X RRxd define the node feature vector of G.
[1xos]] [1x x,
vEV
(53)
10t1 v VEVT
Here we concatenated the end of node features of V distinguish them from the nodes of VT
20

---

The connectivity of the sum graph (for our running example Figure 1 is visualized inset.
We now define our baseline model:
Definition D.3 (Coarse MPNN), Let T()) be a coarsening function. De- fine MPNN+ (T) as the set of all functions which can be expressed by the following procedure:
1. Preprocessing: We first construct the sum graph GI of the imput graph G, along with node feature map X :V - IR defined according to equation 53
2. Update: The representation of node v VI is updated according
to:
For E
(v) = fv (v), agsi (x Co,o) u vB.
( IS V .0E .E))
For E VT: x x /rr (2" uggt (5* (ss,, | 1 ~T()) SB. UE V, $}
(54)
3. Pooling:
The final node feature vector X² (-) pooled according
to:
Σ xT(1) VEV
MLP
(55)
Here, for L E [T], P& JivT are continuous (parameterized) functions and agg', agghT are continuous (parameterized) permulation invariant functions. Finally, notice that for the trivial coarsening function defined by
TG( 0,
(56)
the update in Equation 54 devolves into standard MPNN update, as defined 13 and so we define:
MPNN MPNN (To).
(57)
essence, given an input graph G = E), the MPNN_ (T) pipeline first constructs the coarsened graph T(G). It then adds edges between each super-node S E VT and the nodes it is comprised of (i.c., any v E S). This is followed by standard message passing procedure on the graph. The following two propositions suggest that this simple approach to incorporating T into GNN pipeline less powerful than our model.
Proposition D.2 (CS-GNN Is at Least as Expressive as Coarse MPNN ). For any coarsening funntionn T()) the following holds:
MPNN C MPNN (T) S CS-GNN(T, ms)
(58)
Proposition D.3 (CS-GNN Can Be More Expressive Than MPNN+). Let T(-) be the identity coarsening function defined by:
T(G) = uub G= CVV.E).
(59)
The following holds:
MPNN = MPNN+
(60)
Thus:
MPNN (T) CS-GNN(T TS),
(61)
where this containment is strict.
21

---

The proofs to the last two propositions can be found in Appendix G Proposition D.3 demonstrates that CS-GNNis strictly more expressive than MPNN, when using the identity coarsening function. However, this result extends to more complex coarsening functions as well. We briefly discuss one such example. Let T()) be the coarsening function defined by:
Ta (G) = {11, 12, 03 G( 02; 03 = A},
(62)
Lee for an input graph G, the set of super-nodes is composed of all triplets of nodes whose induced subgraph is isomorphic to triangle. To see that CS-G CS-GNN is strictly more expressive then MPNN,; when using (-),,, we look at the two graphs and H depicted Figure 4 In the figure, we see the two original graphs, G and H, their corresponding sum graphs G and H_= and subgraph of their corresponging product graphs GUTz (G) and HOT (H) induced by the sets {(So. v) v E Va} and {So. v) the bag of subgraphs induced by CS-GNN). One can clearly see that both the original graphs and their respective sum graphs 1-WL indistinguisaabl. On the other hand, the subgraphs induced by our method are 1-WL. distinguishable. Since for both G and H the "bag of subgraphs" induced by CS-GNN is composed of isomorphic copies of the same graph, this would imply that method can distinguish between and H, making it strictly mor expressive then MPNN
VH} respectively (this be thought of looking at single subgraph from
G:
G
G 9 (G)
H:
H 9 (
H
Figure 4: Rows and 3 depict two 1-WL indistinguishable graphs> Rows 2 and 4 depict the sum graph of each of these graphs, well one subgraph of their product graphs induced by all node, super-node tuples whose noper-node is fixed.
22

---

We conclude this section with the following proposition, showing there exists coarsening functions which, when combined with CS-GNN, results in an architecture that is strictly more expressive then node-based subgraph GNNs.
Proposition D.4 (CS-GNN can strictly more expressive then node-based subgraph GNNs). Let T be the coursening function defined by:
T(G) ((0) IVEVJUE G = (V,
(63)
The following holds:
1. Let G1, G2 be a pair of graphs such that there exists a M where M(G)) # M(2)). There exists CS-G CS-GNNmodel M' which uses TT such that (G,) + ('2))
subgraph GNN model
2. There exists a pair of graphs G1, G2 such that for any subgraph GNN model M holds that M(G) M(G2), but there exists CS-GNNmodel M' which uses T such that
M' + M22)
This proposition is proved in Appendix G
E Linear Invariant (Equivariant) Layer Extended Section
We introduce some key notation. In the matrix X, the i-th row corresponds to the i-th subset S arranged in the lexicographic order of all subsets of [n], namely, [H0], {0, 1}.
10.1, n)]. Each i-th position in this sequence aligns with the i-th row index in X. It follows, that the standard basis for such matrices in IR2" xn is expressed as e(S) e(i)", where (5) a 1-hot vector, with the value positioned according to S in the lexicographic order. For matrix X E Raxb the operation of vectorization, denoted by vec(X), transforms X into single column vector in R by sequentially stacking its columns; in the context of X, the basis vectors of those vectors are ef & e($) The inverse process, reshaping a vectorized matrix back to its original format, is denoted as [vec(X)] X. We also denote an arbitrary permutation by The actions of permutations on vectors, whether indexed by sets or individual indices, are represented by Ps E GL(2") and Pr E GL(n), respectively. This framework acknowledges Sn, as a subgroup of the larger permutation group S2*, which permutes all 2 positions a given vector vs E IR?".
Sn.
Let L E glx2"-n be the matrix representation of a general linear operator L 2 + IR in the standard basis. The operator C is order-invariant iff
L [vec(P]xPp)) L vec(X).
(64)
Similarly, let L E 222"nx2"-n denote the matrix for L 2 222x,, xn. The operator L is order-equivariant if and only if
vec (Peo)) = P vec
(65)
Using properties of the Kronecker product (see Appendices E.I and E.2 for details), we derive the following conditions for invariant and equivariant linear layers:
Invariant L : Pz Ps vec() vec(L),
(66)
Equivariant L P Pr & Ps vec(L) = vec(L).
(67)
Solving Equations 666 and 67 Let E Sn denote a permutation corresponding to the permutation
matrix P. Let P L denote the tensor that results from expressing L after renumbering the nodes in
VT, V according to the permutation Explicitly, for L E R² the (a(S), (i))--entry of P L equals to the (S, ee-ent of L. The matrix that corresponds to the operator P+ in the standard basis, ( @ (5) the kronecker product Pr & Ps. Since vCc(L) is exactly the coordinate vector of the tensor L in the standard basis we have,
vec (P L) Pr vec(),,
(68)
following the same logic, the following holds for the equivariant case, where L E mx2"
vec (Pc P = Pr c Ps
Pr & Ps vec(L).
(69)
23

---

Given Equations 666 and (68) and Equations 67 and (69) it holds that we should focus on solving,
P L, vP permutation matrices,
(70)
for both cases where L E R22 xn and E IR2" xnx2"xn, corresponding to the bias term, and linear term.
Bias. To this end, let us define an equivalence relation in the index space of a tensor in I22 x Given
a pair (S, E P(r])) x [rn], we define 7* to correspond to all pairs (5,i) such that |S| = k and i & S. Similarly, y corresponds to all pairs (S, such that |S| k and i E S. We denote this equivalence relation as follows:
(P((n)) [n])/~ _ (7 k l......, n; (+, -}.
(71)
For each set-equivalence class E (P([n)) x [n)]),, we define a basis tensor, B E R x by setting:
B = (o. 0,
1. (S. E otherwise.
(72)
Following similar reasoning, consider elements (S), i1, (2) E (P([n)) x [n] x P([n)) x [n])- We define partition according six conditions: the relationship between i and ig. denoted as d + ig. which is determines by the condition: i in or i1 * ig; the cardinalities of S and S2, denoted as k1 and k2, respectively; the size of the intersection S1 n S2. denoted as kn; the membership of i in St for / E {1, 2}, denoted as Ssame E {1, 2, 3, 4}; and the membership of it, in St, for distinct 1 lz E {1, 2), denoted as dan E {1, 3, 4). The equivalence relation thus defined can be represented as:
(P(nn)) x [n] x P([n)) x [ml)/~ A (rensrikaa "aaee
(73)
For each set-equivalence class I' E (P((n)) x [n] x P([n)) x [n]]/>,, we define basis tensor, Bd E 2R2 xnx2" xn by setting:
1, if (S i, S2, 12) E T;
B B
(74)
0, otherwise
The following two proposition summarizes the results in this section,
Lemma E.1 (7 (I) are orbits). The sets fy : k 1,.... n2 E (+, -}} and (T t M are the orbits of Sn on the index space (P([n)) x (nl) and (P((n) x [n] x (P((nl) x [n]), respectively.
Proposition E.1 (Basis of Invariant (Equivariant) Layer). The tensors B (B*) in Equation (72)
(Equation 74)) form an orthogonal basis (in the standard inner product) to the solution of Equa-
tion (66) EEquation (67).
The proof's are given in Appendix G
E.1 Full Derivation of Equation 66
Our goal is to transition from the equation, to the form,
L vec PT (TPPPXPZ)) xP7) = L vec(X')
64
Py @ Ps vLc(L) = vec(L) (L) We introduce the following property of the Kronecker product, vec(ABC) (CT Ae).
66
(75)
Using Equation 75 on the left side of Equation (64) we obtain
LPT @ P (X') L vec(2')
(76)
since this should be true for any X' E 1 xn, we derive
LP & PT LL.
(77)
Applying the transpose operation on both sides, and noting that (P7 &P)) Pr Ps. we obtain
Pr ② PsLT--L'
(78)
Recalling that E IR1x2"M and thus L E E 2221xxx mx1 we find that L = veo(L). Substituting this back into the previous equation achieve Equation 66).
24

---

E.2 Full Derivation of Equation 67
Our goal is to transition from the equation,
[ vec PS = =P' P=
65p
to the form,
Pr & Ps X PT. @ Ps vec(L) = vec(L).
67
Applying the property in Equation
75 after the reverse operation of the vectorization, namely,
vvcc ABC) = [(C @ AJvec(B]]
(79)
on the right hand side Equation 65 for
2 P
(80)
B A L vec(X)];
(81)
C Pı,
(82)
we obtain,
L veec(P xT)) = =PP @ vec()).
(83)
Thus, by omitting the revere-vectorizatton operation,
vve (ve((p]XPz) = PT P vec(X).
(84)
Noting that (PT ② PP)) 12))1- Pr @ Ps. and multiplying by this inverse both sides (from the left),
we obtain,
Py & PsL voL' L vec(A)).
(85)
Applying, again, the property in Equation
75 we obtain,
Pr PsLP P vec L voc(A))
(86)
Since this should be true for any X R xn we derive,
Pr PSLP PS = voc(L).
(87)
Again, applying Equation 775 on the left side, where,
A A Pr & Ps;
(88)
B L
(89)
& P7 ② PT
(90)
get the following equality,
Pz PsLP & P
Pr & Ps 8 Pz & Ps vec(L).
(91)
By substituting this to the left side of Equation (87 we obtain Equation (67
E.3 Comparative Parameter Reduction Linear Equivariant Layers
To demonstrate the effectiveness of our mnrameter-sharinge scheme, which results from considering unordered tuples rather than ordered tuples, we present the following comparison. 3-IGNs [22] are structurally similar to our approach, with the main difference being that they consider indices as ordered tuples, while we consider them as sets. Both approaches use a total of six indices, as shown the visualized block Figure 3 making 3-IGNs natural comparator. By leveraging our scheme, we reduce the number of parameters from 203 (the number of parameters in 3-IGNs) to just 35!
25

---

Table 5: Overview of the graph learning datasets.
Dataset
Graphs
Avg. nodes
Avg. edges
Directed
Prediction fask
Metric
ZINC-122
31
12,000
23,2
24.9
No
Regression
Mean Abs, Error
ZINC-FULL
81
249,456
23.2
49.8
No
Regression
Mean Abs. Error
OGRG MOL
27.5
Binary Classification
AUROC
OGRG-MOL BACE
16
1513
34,1
36,9
No
Binary Classification
AUROC
OGBG MONG-MOLESOLL
16
1,128
13.3
13.7
Regression
Root Mean Squ. Error
PEPTIDES-FUNC
15,535
150.9
307.3
10-task Classification
Avg. Precision
PEPTIDES-STRUCT
0
15,535
150.9
307.3
No
11-task Regression
Meun Abs. Error
F Extended Experimental Section
F1 Dataset Description
In this section we overview the eight different datasets considered; this summarized in Table 5
ZINC-12K and ZINC-FULL Datasets [31] 14, 10]. The ZINC- 12K dataset includes 12,000 molecular graphs sourced from the ZINC database, compilation of commercially available chemical compounds. These molecular graphs vary in size, ranging from 9 to 37 nodes, where each node represents heavy atom, covering 28 different atom types. Edges represent chemical bonds and there are three types of bonds. The main goal when using this dataset is to perform regression analysis on the constrained solubility (logP) of the molecules. The dataset is divided into training, validation, and test sets with 10,000, 1,000, and 1,000 molecular graphs respectively. The full version, ZINC-FULL, comprises approximately 250,000 molecular graphs, ranging from 9 to 37 nodes and 16 to 84 edges per graph. These graphs also represent heavy atoms, with 28 distinct atom types, and the edges indicate bonds between these atoms, with four types of bonds present.
OGBG-MOLHIV, OGRG-MOLBACE, OGBG-MOLESOL. Datasets [16]. These datasets are used for molecular property prediction and have been adopted by the Open Graph Benchmark (OGB, MIT License) from MoleculeNet. They use a standardized featurization for nodes (atoms) and edges (bonds), capturing various chemophysical properties.
PEPTIDES-FUNC and PEPTIDES-STRUCE Datasets 91. The PEPTIDES-FUNC and PEPTIDES- STRUCT datasets consist of atomic graphs representing peptides released with the Long Range Graph Benchmark (LRGB, MIT License). In PEPTIDES-FUNCE the task to perform multi-label graph classification into ten non-exclusive peptide functional classes. Conversely, PEPTIDES-STRE STRUCT is focused on graph regression to predict eleven dimeediimnsiionl structural properties of the peptides.
We note that for all datasets, we used the random splits provided by the public benchmarks.
F.2 Experimental Details
Implementation Details. Our implementation of Equation is given by:
x0+1) -ML Σ
MPNN (+1.6) (x)
(92)
where Ai = Ac. = AT(G), and Aa = AEquii
For all considered datasets, namely. ZINC- ZINC-FULL, OGBG-MOLHIV, MOLGAC, and SGBG-MOLESOL. except for the PEPTIDES-FUNG and PEPTIDES-STREN datasets, we use GINE [15] base encoder. Given an adjacency matrix A, and defining e(s" ((),,)) to denote the edge features from node (8', u') to node v), it takes the following form:
x(S,v) = MLP (1 (1+ x(S,))
Σ
ReLU (XLU(XXS', (
(93)
We note that for the symmetry- based updates, switch the ReLU theoretical analyses (Appendix B). stating that we can implement the equivariant update developed
MLF align with the
With the exception of OGB datasets, to avoid overfitting.
The theoretical analysis assumes the usage of an MLP for all three considered updates.
26

---

in Section 4.2 A more thorough discussion regarding the implementation of the symmetry-base updates is given in Appendix
When experimenting with the PEPTIDES-FUNG and PEPTIDES-STRUC datasets, we employ GAT [32 underlying MPNN to ensure fair comparison with the random baseline- the random variant of Subgraphormer + PE B]. To clarify, we consider the random variant of Subgraphormer + PE as natural random baseline since it incorporates the information the eigenvectors of the Laplacian (which we also do via the coarsening function). To maintain a fair comparison, we use a single vote for this random baseline, and maintained the same hyperparameters.
Our experiments were conducted using the Py PyTorch (28) and PyTorch Geometric [ frameworks (resp. BSD and MIT Licenses), using single NVIDIA L40 GPU, and for every considered experi- ment, we show the mean std. of runs with different random seeds. Hyperparameter tuning was performed utilizing the Weight and Biases framework 6 Appendix [F3] All our MLPs feature single hidden layer equipped with a ReLU non-linearity function. For the encoding of atom numbers and bonds, we utilized learnable embeddings indexed by their respective numbers.
In the case the NGBG-MOLIING OGBG-MOLESOL OGBG-MOLBACE datasets, we follow Frasca et al. [1), therefore adding residual connection between different layers. Additionally, for those datasets (except AGBG-MOLHIP we used linear layers instead of MLPs inside the GIN layers. Moreover, for these four datasets, and for the PEPTIDES datasets, the following pooling mechanism was employed
22 n
x(x) MLP Σ
(0,0))))
(94)
For the PEPTIDES datasets, also used residual connection between layers.
E3 HyperParameters
In this section, we detail the hyperparameter search conducted for our experiments. Besides standard hyperparameters such as learning rate and dropout, our specific hyperparameters are:
1. Laplacian Dimension:
This refers to the number of columns used in the matrix U, where L UU for the spectral clustering in the coarsening function.
2. SPD Dimension: This represents the number of indices used in the node marking equation. To clarify, since |S] might be large, we opt for using the first indices that satisfy i E S, sorted according the SPD distance.
SPD Dimension. For the Laplacian dimension, we chose a fixed value of 10 for all bag sizes for both ZINC- 12K and ZINC-FULL datasets. For OGBG-MOLINE MOLII,,, we used fixed value of since the value 10 did not perform well. For the PEPTIDES datasets, we also used the value 1. For the OGBG-MOLESOI. and OGBG-MOLBACE datasets, we searched over the two values {1,2).
Laplacian Dimension. For the Laplacian dimension, we searched over the values {1, 2} for all datasets.
Standard Hyperparameters. For ZINC- 12K, we used a weight decay of 0.0003 for all bag sizes, except for the full bag size, for which used 0.0001.
All of the hyperparameter search configurations are presented in Table and the selected hyperpa- rameters are presented in Table 7
Table 6: Hyperparameters search for CS-GNN
Danset
Bag size
Nam, layess
Leurning zate
Embedding size
Epochs
Busch size
Dropeut
Laplacian dimersion
SPD dimension
Zixe-12x
[1.2]
Zaxe-128
18)
[1.2]
Zaxc-12k
"Gal""
0/0007
500
128
[1.2]
[1.2]
(0,001)0.0000)
[1.2]
(2.5. "harr
[1.2]
0овC MOLESOL
MOLBACE
(2.5. "fil""
(2,9)
0.3
[1.2]
00005)
(0.01,0005)
(1.23
27

---

Table Chosen Hyperparameters for CS-GNN.
Dateset
Bag size
Num, layers
Learning rate
Embheddnng size
Epochs
Batch size
Dcopout
Laplacian dimension
SPD dimension
ZiNc- 2NC-12K
0.0005
96
400
128
10
ZIN--1KK
D.00I7
D.0007
Zixc- 12K
0.0007
128
ZINc-12K
D.00017
145
400
128
10
Zisc 12K
T "Hull"
0.0007
96
500
128
NIA
10
7INC-BU11 ZINC-FULL
D.0007
96
400
128
1
10
"ful""
0.0005
96
500
128
N/A
N/A
DOBG-MOLRIY
OCRG-MOLESOL
2-
0.001
60
OORG-MOI ESO1.
7=
0.001
60
100
322
0.3
OGBO MOLESOL
T "full"
0.001
60
100
32
0.3
NA
NA
DERG-MOI BACK
7=
0.01
60
100
32
0.3
T-5
0.01
60
"Tull"
NA
7-
PEPTIDES-STRUC
=00
0.01
200
128
Optimizers and Schedulers. For the ZINC-12K and ZINC-FULL datasets, we employ the Adam optimizer paired with a CaattceeROOPlaateees scheduler,factor set to 0.5, patience at 4d and minimum learning rate of For the OGBG- MOLHIV dataset, we utilized the ASAM optimizer [21] without a scheduler. For both DGBG-MOLESOL and OGBG-MOLBACE, we employed constant learning rate without any scheduler. Lastly, the PEPTIDES-FUNT and PEPTIDES-STRUCT datasets, the Adam W optimizer was chosen in conjunction with cosine annealing scheduler, incorporating 10 warmup epochs.
E4 Implementation of Linear Equivariant and Invariant layers Extended Section
this section, a more formal discussion, we specify how to integrate those invariant and equivariant layers to our proposed architecture. We start by drawing an analogy between parameter sharing in linear layers and the operation of an MPNN on fully connected graph with edge features in the following lemma,
Lemma F.1 (Parameter Sharing as MPNN). Let BI.... B& Ruxn be orthogonal matrices with entries restricted to 0 or 1, and let WI,... We E Rdxd' denote sequence of weight matrices. Define B+ = B; and choose 21....2k E Rdd to be of unique vectors representing encoding of the index set. The function, which represents an update via parameter sharing:
((X) Σ B,XW,
(95)
can be implemented by stack of MPNN layers of the following form [f3]
m
Σ
MX cu,u)..
(96)
.EN,, (N)
x (x(x),m
(97)
where UL, M are multilayer preceptrons (MLPs). The inputs to this MPNN are the adjacency matrix B4, node feature vector X, and edge features the feature of edge (u, v) is given by:
Cu,v Σ 2 (B,Bu,,
(98)
Here, Bi(u, v) denotes the (u, v) entry to matrix B;.
The proof is given in Appendix G
For ZINC- 12K. T (2, "full"), ). used patience of 50.
28

---

Table Comparison over the ZINC-Furi FULL molecular dataset under 500k parameter budget. The best performing method is highlighted in blue, while the second best is highlighted in red.
ZINC-FULL (MAE +)
Model 4 Dataset
MAG-GNN 20 (T =
0.03010.002
Ours (7
0.027=0.002
GNN-SSWL (T = "full")
0.026+0.000
GNN-SSWL+ 38 (T' "full""
0.022+0.002
Subgruphormer 3
[T "full")
0.020=000022
Subgraphormer + PE (T "full")
0.02310.001
Ours (T' "full""
0.021=0.001
Thus, our implementation for the global update is as follows,
() = MLPP (1++))
Σ
MLP +
(99)
(S' (8'( Asai (8,1)
where ((),,))((8)) = Er B s. and 2r are orthogonal 1-hot vectors for different I's. The connectivity Agguse is such that Agquir (S, U, S¹, o') contains the value one iff v E S, v = v.. This corresponds to choosing only several I's in the partition, and since each T is invariant to the permutation, this choice still maintains equivariance.
F.5 Additional Results
ZINC-FULL. Below, present our results on the ZINC-FULL dataset for bag size of = 4 and the
full-bag. For the bag size T 4, we benchmark against MAG-GNN [20), which their experiments used the best out of the bag sizes T {2, 3, 4); however, they did not specify which one performed the best. The results are summarized in Table
ZINC- 12K additional results. We present all the results from Figure 2 along with some additional ones, in Table
Runtime comparison. We compare the training time and prediction performance on the ZINC- 1 12K dataset. For all methods, we report the training and inference times on the entire training and test sets, respectively, using batch size of 128. Our experiments were conducted using an NVIDIA L40 GPU, while for the baselines, used the timing reported in ( which utilized RTX A6000 GPU. The runtime comparison is presented in Table I0
F66 ZINC Product Graph Visualization
In this subsection, visualize the product graph derived from the first graph in the ZINC dataset. Specifically, we present the right part of Figure [ for the case of the real-world graphs in the ZINC12K dataset. We perform this visualization for different cluster sizes, T [2, 3, 4,5. 8, 12). which also define the bag size, hence the notation T. The nodes in the product graph, (G)) are (S,,) v), where S is the coarsened graph node (again a tuple), and v is the node index (of node from the original graph). For better clarity, we color the nodes (8, v) with v E S using different colors, while reserving the gray color exclusively for nodes (8, v) where S. The product graphs are visualized in Figures to below.
29

---

Table 9: Test results the ZINC- 12 molecular dataset under 500k parameter budget. The top two results are reported as First and Second.
Method
Bag size
ZINC (MAB
OCN TV
0.521 0.009
GIN 35
T
0.163 + 0.004
+ 0.016
Randum
10
T =
0.131 + 0.005
PI S
T
0.120 + 0.003
Mag-
Our
T
0.109 0.005
0.124 + NIA
Mig-GNN
60
T =
0.104 NVA
Our
T
0.096 0.005
Random
27
T =
0.125 + NAA
Mig-GNN
T
0.101
0.090
5
PL.
T
0.109 0.005
Oues
T
0.095 + 0.003
Random 5
7
0.102 + 0.0n3
PL.
7
0.097 0.005
0.082
NGNN
0.111+0.000
0.116++0.00
DSS-GNN
Pull
0.1022#0.000
GNN-AK
30
Hull
0.105=td.010
GNN-AK+
0.09140.002
0.083+0.003
OSAN 29
Full
0.154::d.009
GNN SSWL
Pull
0.070 + 0.005
Subgraphame
Subgraphormee+PE
Durs
Full
0.062 - 0.0007
Table 10: Run time comparison over the ZINC-12 12K dataset. Time taken at train for one epoch and at inference on the test All values are milliseconds.
Method
Train time (Tor a single epoch; ms)
Test time (ms)
MAE
GIN 35
1370.10 + 10.97
81.81 + 0.26
0.163 + 0.001
OSAN 20 (T' 2)
2964.46 1. 30.36
227.99 1 0.21
0.177 1: 0.016
2489.25
Ours
(7' ==:: 2)
2764.60 1: 234
383.14 + 15.74
0.109 1: 0.005
30

---

5(G)
G
Figure 5: T= 2.
5(G)
G
Figure 6: T = 3.
9(0)
Figure 7: 4.
31

---

5GG)
G
5
Figure 8: T == 5.
F(G)
G
G
Figure 9: T = 8.
900)
9
Figure 10: T 12.
32

---

G
Proofs
G.1 Proofs of Appendix
We first state the memorization theorem, proven in [36 which will be heavily used in a lot of the proofs in this section.
{x,,33 Theorem G.1 (Memorization Theorem). Consider dataset {x,,, y1 b R' x Rdv, with each x; being distinct and every Yy E {0, (0,1)"x, xx, There exists 4-layer fully connected ReLU neural network fo R Rd that perfectly maps each 2j to its corresponding Yj. i.e., fo(2;) = Y, for all
We now restate and prove the propositions and lemmas of Appendix B
Lemma B.1 (Parameter Sharing as MPNN). Let .I....Ba IRax be orthogonal matrices with entries restricted to or 1, and let WI.... W3 E pd denote sequence of weight matrices. Define B+ = - B: and choose 21.... E R to be set of unique vectors representing an encoding the index set. The function that represents an update via parameter sharing:
f(X) Σ B,XW,,
(18)
can be implemented on any finite family of graphs G, by a stack of MPNN layers of the following form 131
m Σ M' en,,)
(19)
NENe, (c)
x (X! m,),
(20)
where U. Mc are multilayer perceptrons (MLPs). The imputs this MPNN are the adjacency matrix B,, node feature vector X, and edge features the feature of edge (u, v) is given by:
Cu,v Σ 2. (.,B,
(21)
Here, Bi(u, v) denotes the (u, v) entry to matrix B,.
Proof. Since we are concerned only with input graphs from a finite family of graphs (where "finite" means that the maximal graph size is bounded and all possible node and edge feature values come from a finite set), we assume that for any v E [n]. i [k:) both the input feature vectors X,, E Rd and the encoding vectors 2; E Rdd are one-hot encoded. We aim to show that under these assumptions, any function f-) of the form 95 can be realized through single-layer update detailed in Equations where M is 4 layer MLP, and U a single linear layer. The proof involves the following steps:
97 96
1. Compute [B,X,... ...., X] using the message function M.
2. Compute f(X) using the update function U.
Step 1: We notice that for every E [kt,, v [m] we have:
(B.X).
Σ
X.
X. 1c, (ENR+(0)
Σ
(100)
B.(e,u)=1
Here 1,, is the indicator function of the set {zz}. We notice that since X, and 2; are one-hot encoded, there is finite set of possible values for the pair (Xu, B. In addition, the function:
enc(Xa, eu,v) = [X,, 1g (e..))....,, 1sp (ea,v)]
(101)
outputs vectors in the set {0, 1]d Thus, employing the memorization theorem G.I we define dataset {z,, y1 - by taking the zys to be all possible (distinct) values of (X,, Eu,e) with each
33

---

corresponding being the output enc(x;). We note that there are finitely many such values as both x, and G,, are one-hot encoded. The theorem now tells us that there exists 4-layer fully connected ReI.U neural network M such that:
M (Xur Cu,u) enc(Xur eu,u)
(102)
and so, equation 100 implies:
My
Σ
M(Xu, = -((Bi))o.......... (B,X)o] (B,x))))..,,,,,,))
(103)
uc NENa (o)
Step 2: Define P; Rxd
-> Idd as the projection operator, extracting coordinates d ++ through
d (i 1) from its imput vector:
P.(V) = V Vla (i+1))
(104)
We define the update function to be the following linear map:
U U(Xu, m.) = Σ P.(m.)W.
(105)
Combining equations 103 and 105 we get:
X. U(X,,
(B,X), W, f(X)..
(106)
Proposition B.1 (Equivalence of General Layer and Implemented Layer). Let T()) be coarsening function, π be generalized node marking policy, and G be finite family of graphs. Applying stack of general layer updates as defined in Equation 75 to the node feature map X(S, v) induced by (G, T, can be effectively implemented by applying stack of layer updates specified in Equations 29 and to (SS v). Additionally, the depths of all MLPs that appear 29 by 4.
29aand and 30 can be bounded
Proof. For convenience, us first restate the general layer update:
(S l' ( (*((),),,
aggi (2 r (S" -ar S}.
15
(S S'e stue,,,
(S) V Vss.e'e (ss.)
as well as the two step implemented layer update:
() = -U² (1+ (1+ (S,
Σ M'(X'S' +e(.,,,,,))
29
(S'w))ma,
x U Σ x4(()
30
We aim to demonstrate that any general layer, which updates the node feature map X' v) at layer
I to node feature map (S, at layer I + as described in equation 15 can be effectively
implemented using the layer update processes outlined in equations 29 and 30
34

---

As we are concerned only with imput graphs belonging to the finite graph family g (where "finite" indicates that the maximal graph size is bounded and node and edge features have finite set of possible values), we assume that the values of the node feature map (S, v) and the edge feature vectors (4 S", ,') are represented as one-hot vectors in R We also assume that the parameterized functions f and aggi.... ..... agg., which are applied in Equation outputs one-hot vectors. Finally, we assume that there exists integers d, d", such that the node feature map values are supported on coordinates 1....dd. the edge feature vectors are supported on coordinates + 1....d d d", and coordinates d + d" + 1,... k are used as extra memory space, with:
k > d x d² + d d²
(107)
We note that the last assumption can easily achieved using padding. The proof involves the following steps:
1. For i 1,..., 4, Use the term:
mf
Σ
(108)
(8,00)),,(55))
to uniquely encode:
((*" e 1 (S'' (S.0)).
(109)
2. Use the term:
X (S,
(110)
to uniquely encode the input of f* as a whole.
3. Implement the parameterized function f"
Step I: Since we assume that node feature map values and edge feature vectors are supported on orthogonal sub-spaces of R* the term:
(S, + (S,
(111)
uniquely encodes the value of the tuple:
(S" eS.
(112)
Since X*(S,v v) one-hot encoded vector with possible values, while (S, v, S' o') a one-hot encoded vector with d' possible values, their sum has d d² possible values. Thus there exists function:
enc R R
which encodes each such possible value as a one-hot vector in IR supported on the last 1: d' coordinates (this is possible because of equation l07p. Now, employing theorem G.I we define the 8yS as all possible (distinct) values of 111 with each corresponding yj being the output enc(r,). The theorem tells us that there exists 4-layer fully connected ReL.U neural network capable of implementing the function enc(.). We choose M to be this network. Now since m defined in equation| [08 is sum of one-hot encoded vectors, it effectively counts the number of each possible value in the set 109 This proves step 1.
Step 2: First, note that:
(S,') o' ~g v = =I( v')) (S,u)~ ~oO (S" v')
(113)
((*' ~ $S
(114)
= (10""(",,)) o))) (8,v) ~ATiO (''
(115)
(((""(() ~r, (8'0'))
35

---

= =(S,,, d')) 1 ES}
(116)
w)) (5, ( ~A, 1'',
Now, since mi and (S, v) are supported on orthogonal sub-spaces of R the sum x'(S v) + m uniquely encodes the value of:
(X' v), Cs,,,,,
(5, ~A, (S' v')).
(117)
Thus, we choose i,,..,, epsiloni, to be all zeroes. To compute the aggregation functions aggi,..., using these unique encodings, and avoid repetition of the value (S, define auxiliary functions agg! : Re _ Rec =or1=1, 1,..., 4 as follows:
(g'(( m{) (x. u) (()
(S, ~A. ('))
(118)
and for i 1:
(X* + m() age' (Xt (s, v), e S" o')) (S. ~A: v'))
(119)
Here, since we avoided repeating the value of X' (S, v) by only adding it to the output of agg (-), the expression:
(2' +
agg (X* +m))
(120)
exactly equal to the input of f In addition, since the function agg¹ outputs one-hot encoded vectors, and the vector (", v) one-hot encoded, the output of agg; is always within the set {0, 1) Now for any input vector X E R define:
Vi() (agg' (X), Oke Okg 0k,).
(121)
(X)) (Okr, (X), Oka Oka).
(122)
(X) = (Ok,, Ok agg (X), Ok,))
(123)
(X( (Okg Okg Ogg agg (X)).
(124)
We note that since the output of agg always within the set {0. 1 Rts the outputs of V is always
within {0, 11tittt.......... t.k..kk Now for i = 1.... 4, employing theorem G.1 we define a dataset {æ,, y/ 1 by taking the rys as all possible (distinct) values of (S, + m/ with each corresponding 3 being the output V/ (2z). We note that there are finitely many such values as both X" v) and m; are one-hot encoded vectors. The theorem now tells us that there exists 4-layer fully connected ReLU neural network capable of implementing the function (-). We choose U/ be this network.
Equations 121
124 now give us:
Σ ((( (a (S, + mi),.... agg' (X'( m()))
(125)
which as stated before, is exactly the input to f². This proves step 2.
Step 3: We employ theorem G.I for final time, defining dataset {x. 1i by taking the ays as all possible(distinet) values of!
Σ (S
(which we showed is a unique encoding to the input of f())), with each corresponding yj being the output (xz)) We note that Given the finite nature of our graph set, there are finitely many such
values. Recalling that (') outputs one-hot encoded vectors, The theorem now tells us that there exists a 4-layer fully connected ReLU neural network capable of implementing the function f*()). We choose Uf to be this network. This completes the proof.
36

---

G.2 Proofs of Appendix C
Proposition C.1 (Equal Expressivity of Node Marking Policies). For any coarsening function T--) the following holds:
CS-GNN(T, TT) CS-GNN(T Tss) = CS-GNN(T, (TD)).
(36)
Proof. Let II = {TTS ss, TMD) be the set of all relevant node initialization policies, and assume for simplicity that our input graphs have no node features (the proof can be easily adjusted to account for the general case). For each E II, let (T u) denote the node feature map induced by general node marking policy т,, as per Definition C.I We notice it is enough to prove for each T1, 71, E II that T (S, v) can be implemented by updating X² v) using stack of T layers of type 54 Thus, we prove the following four cases:
Node Size Marking = Simple Node Marking.
Minimum Distance + Simple Node Marking.
Simple Node Marking = Node Size Marking.
Simple Node Marking = Minimum Distance.
Node + Size Marking = Simple Node Marking:
In this case, we aim to update the node feature map:
(1) v vES S (S, = x (S,e) = (0. [S))
(126)
v $ S.
We notice that:
(S, = ((1,0)) n ( v)).
(127)
where ( denotes the standard inner product in R.? Using CS-GNN update per equation 15 with the update function:
S (A,
01, v)),
(128)
where f(a (a.5))))) indicates that the function f depends solely on the parameter we obtain:
X' f (), ...))))))))))))))))))))))))))))) x (S,
(129)
This implies that for any coarsening function T(-), the following holds:
CS-GNN(T, TT) C CS-GNN(T, mTsss.
(130)
Minimum Distance = Simple Node Marking:
In this case, we aim to update the node feature map:
XS, v) x ( v) min (u v)
(131)
We notice that:
x² (S, = g(x v)
(132)
where g: R + R is any continuous function such that:
g(x) 1 1 2. g(z) 0 Vr 1
Using CS-GNN update as per equation 15 with the update function:
(8, (SX*
(133)
we obtain:
(2 (S) x (S,
(134)
37

---

This implies that for any coarsening function T--) the following holds:
CS-GNN(T, MT) C CS-GNN(T, TMD).
(135)
Simple Node Marking + Node + Size Marking: In this case, we aim to update the node feature map:
{ 0 E
vES
= =
(136)
We notice that:
Σ
(S, |S|-
(137)
r'S
Using CS-GNN update per Equation 15 with aggregation function:
= Σ (S,
(138)
o'ES
and update function:
5 x² Σ xx(())))) (S, Σ (1(0)))) w'S
(139)
WES
we obtain:
(S, = (x9(S,0)))) Σ (S,() x (S,
(140)
V'ES
This implies that for any coarsening function T(-) the following holds:
CS-GNN(T, Tss) S CS-GNN(T, ms).
(141)
Simple Node Marking => Minimum Distance:
In this case, aim to update the node feature map:
[1 vE S (S, T xs,)ss 0 v of S.
(142)
We shall prove that TM can be expressed by updating XS, v) with stack of CS-GNN layers. We do this by inductively showing that this procedure can express the following auxiliary node feature maps:
10 00 {m
mminwes do(v, +1 min 0') St
x) =
(143)
otherwise.
We notice first that:
(S, = (S, v)-
(144)
Now for the induction step, assume that there exists stack of CS-GNN layers such that:
(², v) (S,
(145)
We observe that equation:
min do v') 1 1+1 1
(146)
e'ES
holds if and only if the following two conditions met:
min do v') > t #'E
(147)
3u E No(o) s.t.
min de (u, u/) = t. E'ES
(148)
Equations 143 imply:
min diindd,,,'' > X*, V'ES
(149)
38

---

In addition, since the node feature map X' = X² is bounded by t + 1, Equation (133) implies:
3u E (c(c) s.t. min (o(u, v/) t + max (s. u) N u) = t 1. w'ES
(150)
Now, let 9t R - be any continuous function such that for every pair of natural numbers b E N:
1. (e b) + if a =fa=0
2. g: b) otherwise.
Equations 146
150 imply:
x (S, (S, v), max (s, ~G u))-
(151)
Using CS-GNN update per Equation 15 with aggregation function:
aggi (S ex,rr) o' ~a vB
max X' x'(S, v').
(152)
v'~ov
and update function:
(S,,,, max J'wov
= gr (S, max (S,v'))
(153)
g'mgv
we obtain:
x (S,),, max X', 0') v'),,,);)) X (S,u). v).
(154)
dr
This completes the induction step. Now, let G be a finite family of graphs, whose maximal vertex size n. We notice that:
2T (S, (S, 1,
(155)
Which implics that there exists a stack of n CS-GNN layers such that:
(S, v) = and (', MM,
(156)
This implies:
CS-GNN(T, TMD) S CS-GNN(T, TS).
(157)
This concludes the proof.
2
3
Figure 11: Graphs G and H defined in the proof of Proposition C.2 In each graph, the circle marks the single super-node induced by T, while the number next to each node is the maximal SPD between u and the nodes that compose the super-node.
39

---

Proposition C.2 (Expressivity of Learned Distance Policy). For any coarsening fumction T(-) the following holds:
CS-GNN(T ; AS) S CS-GNN(T TLD).
(37)
In addition, for some choices of (-) the containment is strict.
T-))
Proof. First, since we are concerned with input graphs belonging to a finite graph family 9, the learned function <f-) implemented by an MLP can express any continuous function on G. This follows from Theorem G.1 (see the proof of Proposition B.1 for details). By choosing & min(-) in
equation 35 it is clear that for any coarsening function T(-) we have:
CS-GNN(T, =s) = CS-GNN(T, MD S CS-GNN(T, .TD)
(158)
We now construct coarsening function T(-) along with graphs, G and H, and demonstrate that there exists function in CS- CS-GNN(T, LLD) that can separate G and H. However, every function in CS CS-GNN(T, TT)) cannot separate the two.
For an input graph G = (V, E) define:
T(G) = ((u degg(u) = 3}}.
(159)
ie., T-)) returns single super-node composed all nodes with degree Now, define G = (Va. EG) the graph obtained by connecting two cycles of size four by adding an edge between single node from each cycle. Additionally. define H = (VHr, En) ) as the graph formed by joining two cycles of size five along of their edges. See Figure IT for an illustration of the two graphs. By choosing s max(-) in equation 35 a quick calculation shows that:
XS 16, SEVT(O) VEVo
Σ
Σ
(160)
while:
Σ
Σ
X (S. = 14.
(161)
SEVTOn VEVE
Refer to Figure I1 for more details. Observe that:
f(G) = Σ Σ
(S CCS-GNN(T (LD))
(162)
SEVT(H) VH
Thus it is enough to show that:
f(G)= Af CS--GNNTT mT).
(163)
To achieve this, we use the layer update as per Definition B.2 which was demonstrated in Proposi-
tion to be equivalent to the general equivariant message passing update Definition A.5
First,
we observe that the graphs G and H are WL-indistinguishabl. We then observe that since V 1, the graphs induced by the adjacency matrices Ag and Arr in Definition B. are isomorphic the original graphs G' and H, respectively, and therefore they are also WL-indistinguishable Additionally. notice that the graphs induced by the adjacency matrices AT(G) and AT in Definition B. are both isomorphic to the fully disconnected graph with 8 nodes, making them WW--inditinguuihabte as well. We also observe that there exists a bijection VG > VH that maps all nodes of degree 3 in G to all nodes of degree 3 in H. The definition of T(-) implies that a is an isomorphism between the 2. Finally, we notice that for both
adjacency matrices Ap, corresponding G and H. where
G. and H, the node feature map induced by Ts satisfies:
X (S, v) deg(v)- -
(164)
This node feature map can be easily implemented by the layer update in definition B.2 and so can be ignored. Since all four graphs corresponding to that are induced by the adjacency matrices in Definition B.1 are WL-inndistinguishable from their counterpart corresponding to H, and
equation 29 in definition B.2 is an MPNN update, which is incapable of distinguishing graphs that are WL-indistinguishable we that equation 163 holds, concluding the proof.
D
40

---

Proposition C.3 (Node + Size Marking as Invariant Marking). Given a graph G = (V, E) with node feature vector E TRaxd and coarsening function T(), let 2 a be the node feature maps induced by as and Tay respectively. Recall that:
X (S,0) [X vs bsss (S, v)], X (S, = [X b (S, v)].
(43)
(44)
The following now holds:
byr, (S, (H, E VVEV.
(45)
Here, OHE denotes a one-hot encoder, independent of the choice of both G and T.
Proof. Let G = EV) be a graph with V= = [n|]. and let T(-) be coarsening function. Recall that the maps bars (:) and br (:)-) are both independent of the connectivity of G and are defined as follows:
SS) VE mS (S, (0) &
(165)
Drn (S, (1mm v). (S,
(166)
Here, v E [n]. E T(m)) & P([rl),, 71,...: 7 is any enumeration of the set of all orbits (P(nn)) x In. and 1, denotes the indicator function of orbit %. Since any tuple (S.
P((n)) x [n] belongs to exactly one orbit % we note that the right hand side Equation (166) is a
one-hot encoded vector. Thus, it suffices to show that for every v, v' [n] and S, E P[[n]]. have:
Drs (S) Drsss (S,' o') < dmnn (S, b (S,'0')
(167)
This is equivalent to:
(P((n)) x [n]]/S, = {{(S,)) v) | i =
i e [m], E (0, 10.
(168)
Essentially, this means that each orbit corresponds to a choice of the size of s and whether e E S or not. To conclude the proof, it remains to show that for any two pains o), (8' v') P(nn) x [m].
there exists permutation a E S, such that:
a a.
v')
(169)
and only if
[S] | and 1s(0) 1 5: (v').
(170)
Assume first that (S, v) (S', v'), then o (S) S' and since or is bijection, |S| |S" In addition o (w) o' thus:
v' Eu) (S) S
(171)
Assume now that:
|S| |S
(172)
1s(v) (v')
(173)
It follows that for some r, E [n]:
(otl Is' [e')=r and |m]] Ih)
=
(174)
Write:
S\ (\{u}= = ic), s' S' = t.....,
[m] (SU (h.... inh. [n]
= 1i....
and define:
v x v
(x)
i x = i E [r)
(175)
j1 x = jr, 1 E [m]
We now have:
a. (S, = (S',
(176)
This concludes the proof.
41

---

G.3 Proofs of Appendix D.1
Proposition D.1 (CS-GNN Can Implement MSGNN), Let T()) be the identity coarsening function defined by:
T(G) =
AG (V.
(49)
The following holds:
CS-GNN(T .T) MSGNN((TWW).
(50)
Proof. Abusing notation, for a given graph G = (V, E) we write T(G) = G. VT = V. First, we observe that:
V {u] a u=
(177)
This implies that the initial node feature map (w, v) induced by Tς is equivalent to the standard node marking described in equation 46 Additionally, we note that the pooling procedures for both models, described in equations 16 and 55 are identical. Therefore, it is sufficient show that the CS-GNN and MSGNN layer updates described in equations [5] and 47 respectively are also identical. For this purpose, let (v, u) be node feature map supported on the set V x V. The inputs to the MSGNN layer are the following:
1. X²(u, v).
2. x'(u, u).
3. X((v, v).
4. aggi ((( (,, el), of ~ v..
5. aggb (x' eu, |n' ~ u..
The inputs to the CS-GNN layer are the following:
1. - (u, v).
2. (sg) (x,r)) o' ~G b} = aggi (()
3. agg)((("(((''')) NOT 8 aggb (A'
v..
4. (Fc" Vs' E VT s.t. U S = {(X x0,
5.
Vu' E E S} = { (u, u)
The terms z(u, v, v. v) and z(u, v, u) appearing in the last two input terms of the CS-GNN layer uniquely encode the orbit tuples (u, v, v, v) and (u, v, u, u) belong to respectively. Since these orbits depend solely on whether u = v, these values are equivalent to the node marking feature map X² (u, v). Therefore, these terms can be ignored. Observing the two lists above, see that the inputs to both update layers are identical (ignoring the z(-) terms), Thus, as both updates act these inputs in the same way, the updates themselves are identical. and so
ASGNN(TTMM) = CS-GNN(T, .T))
(178)
G.4 Proofs of Appendix D.2
Proposition D.2 (CS-GNN Is Least Expressive Coarse MPNN For any coarsening T()) the following holds:
MPNN C MPNN (T) CS-GNN(T, .T)
(58)
42

---

Proof. For convenience, let us first restate the CS-GNN layer update:
x (S, = 8²t (8,
(o) ~ v..
(e)(((("(())))esssss))) not Sh.
15
(B 222,(((((S.),,,3333.. df e VsL.' e E
as well as the 4PNN_, layer update:
For v E V
(v) (x) = / (2 (v), aggi (1)) (n,))) Ne agg ( S VT, . SB))
54
For Se VT: (*) fir (S) aggi (S'),,,,, es,s ~ S'B agg (x V)
We note that by setting / to be constant and choosing 1 be any continuous function that depends only on its first two arguments, the update in equation becomes standard MPNN layer. This proves:
MPNN MPNN+
(179)
Next, we prove the following 2 Lemmas:
Lemma G.I. Given a graph G (V, E) such that V [n]] with node feature vector X Raxd
and a coarsening function T-)), there exists CS-GNN(T ,s)) layer such that:
X (S,u) = [0a+1, X., 1] (5),
(180)
Here [ denotes concatenation and (.) denotes the initial node feature map of the coursened sum graph GT.
Lemma G.2. Let (-) denote the node feature maps of G at layers t of a stack of MPNN (T)
layers. There exists a stack of CS CS-GNN(T, TT) layers such that:
(181)
proof of Lemma G.1 Recall that the initial node feature map of CS-GNN(T, .T)) is given by:
(S, = [X.. 1] [x 0] v & S. In addition, the initial node feature map of MPNN (T) is given by:
veS S
(182)
[Xxx 1] VEV
{x)
(183)
10++1
VEVT.
Thus, we choose layer update as described in equation 15 with:
x (². = f (S),
[0 XS, v)2.1.1
(184)
Here, ((, denotes that the function depends only the parameter and Xash indicates that only the coordinates a through of the vector X are taken. This gives us:
x², = (S), (*))).
(185)
43

---

proof of Lemma G.2 We prove this Lemma by induction on t. We note that Lemma G. provides the base case Assume now that for given stack of MPNN, (T) layer updates, with corresponding node feature maps:
+ Rd. i= i=l...,t++
(186)
there exists a stack of + CS-GNN (T, TT) layers with node feature maps:
X V x V - 2d. ......,.+1
(187)
such that:
X
(188)
We shall show that there exists single additional CS-GNN(T Ts) layer update such that:
x (S, - - ( (v)]
(189)
For that purpose we define the following CS-GNN(T, πs) update (abusing notation, the left hand side refers to components of the CS (TT TT) update layer + while the right hand side refers to components the MPNN+ update at layer t):
aggi ++1 = aggill:de>
agg² 1+1 aggil4++:22,.
(190)
aggs 1+1 agggl1:de
agg agg2ld+11:24.
[a (ab,,,,)
b, d), f (aa, (1:4,,
(191)
Here the operation aggh:s initially projects all vectors in the input multi-set onto coordinates a through b, and subsequently passes them to the function agg. equations 190 191
guarantee that:
xL+2 v) = ft (S, u)
aggi ([S, of )ma N v'}, agg² ((S,, v)1.d I S' x*)((w)
(192)
X ()d..)
für (X* (S)
aggi (((S,,, v),, 11:,
S ~T(G) SR. v ES))))
aggå (S, v/ )d,41:2d,
= X (S).
This proves the Lemma.
Now, for a given finite family of graphs & and a function f E MMNN (T), there exists a stack of T
MPNN, (T) layers such that:
Σ {T(O))
[G))=
VG
(193)
NEVV
Here, X", V. + Re denotes the final node feature map, and U is an MLP. Lemma G.2 now tells us that there exists stack of T CS-GNN(T, TT) layers such that:
XT+I(SS v) L (S), (T))).
(194)
Similarly to Lemma G.I
additional layer to pad T (S, (S, u) as follows:
XT x 1ス (S). ( (v),
(195)
44

---

We notice that:
(S), Ex(U) Σ 1
Σ
(5 =
*EVT
LSEVT
SEVT
SEVT
(196)
Σ LSEVT
XT(s,, VT I
(T),,, |T
Thus, in order to get rid of the [V term, We define:
ML.Pia,,b,)) aa. b,,1, a, a R e > 0.
(197)
We note that since we are restricted to finite family of input graphs, the use of an MLP in equation 200 can be justified using Theorem G.1 (sce the proof of Proposition B. for detailed explanation).
Equations
196 and 200 imply:
-I Σ XT(S), Ex(s), x²)),, 1
MLP, Σ xT42(5.0)
(198)
SEVT
LSEV
Thus, similarly to equation 196
Σ
MLP,
Σ
TT (S,
= M1 -11 Σ XT(S), Σ (T())) MA]
(199)
DEV
SEVT
SEVT
DEV
And so, order to get rid of the |V| term, We define:
MLP2(a,b,c) = U(a - b,
abbe RdT , 0.
(200)
Thus for all E g:
Σ xTT(((800))
MLP2
Σ MLP,
WEV
SEVT
(IV)-
Σ (T), (M)) MM)
MML2
Σ XT(S),
SEVT
vEV
(201)
=U Σ (T(1)
PEVT
[(G).
and so CS-GNN(T, Ts). This proves:
MPNN+ S. (SS-GNN[T,TS))
(202)
Proposition D.3 (CS-GNN Can Be More Expressive Than MPNN+). Let T(-) be the identity coarsening function defined by:
=(G)= = luE]) (V.E)).
(59)
The following holds:
MPNN MPNNN (T).
(60)
Thus:
MPNN+ CS-GNN(T. TS),
(61)
where this containment is strict.
45

---

Proof. First, using the notation i to mark the single element set {u} E VT, We notice that the becomes:
MPNN, (T) layer update described in equation 54
(x((x)))) (x),
eV: X (v) -V
agg [ (v') o' ~a (B.
(203)
F VT: (+) f (1))), X (v). age' (1'), u o')
Now, for a given finite family of graphs G and a function f MPNN+ (T), there exists stack of T MPNN (T) layers such that:
Σ (T LEVV
(G)=U
AG gg
(204)
Here, X²" VL Rd denotes the final node feature map, and U is an MPL. We now prove by induction on t that there exists a stack of t standard MPNN layers, with corresponding node feature map X V 2dd: such that
= (x)
(205)
Here, - stands for concatenation. We assume for simplicity that the input graph does not have node features, though the proof can be easily adapted for the more general case. We notice that for the base case 0, equation [33 in definition D.2 implies:
{ VEV,
(v)
(206)
0 VEVT.
Thus, we define:
(c) = (1,
(207)
This satisfies Equation (05)) establishing the base case of the induction. Assume now that Equa- tion (205) holds for some E [7]. Let agg', fv. fūr be the components of layer i, as in equation
203
We define:
agg' [agg"l Itd, agg' Id, 1:24,]
(208)
Here the operation aggl:: initially projects all vectors in the input multi-set onto coordinates a through and subsequently passes them to the function agg.
Additionally, let d' denote the dimension of the output of the function agg We define:
fa b) = [fv (aluades 412,1: bla.d-) ), f (a)a, a/1.0, bl +1:2a))
(209)
Finally, we update our node feature map X using standard MPNN update according
(x) 3 (x), I(X (o'), oo ~a vB))
(210)
equations
203 205 and now guarantee that:
(++ [x (v), x x
(211)
This concludes the inductive proof. We now define:
MLP(x)= = (zx(1ddr) + U (2))dr11:22))
(212)
This gives us:
U Σ x2 (1)) = MLP
Σ [x((w))= -(GG)
(213)
VEVT
PEV
We have thus proven that f MPNN and so:
(PN S MPNN.
(214)
Combining this result with Proposition D.2 we obtain:
MPNN = MPNN,
(215)
46

---

Finally, since Proposition D.I tells us that CS-GNN(T, Ts) has the same implementation power as the maximally expressive node policy subgraph architecture MSGNN, which is proven be strictly more expressive than the standard MPNN, we have:
MPNN (T) C CS-GNN(T, πT).
(216)
Proposition D.4 (CS-GNN can be strictly more expressive then node-based subgraph GNNs), Let T be the coarsening function defined by:
T(G) - (uE]jUE GV(V)).
(63)
The following holds:
1. Let G1 G2 be a pair of graphs such that there exists a node-based subgraph GNN model M where M(G,) * M(G2). There exists a CS-GNNModel M' which uses TT such that (G, # (G2)))
2. There exists a pair of graphs G1, G2 such that for any subgraph GNN model M holds that ((G) = M(22), but there exists a CS-GNNmodel M' which uses T such that M' (G,) # (22)
Proof. First, notice that the super-nodes produced by T are either of size 1, in which case they correspond to nodes, or they are of size two, in which case they correspond to edges. Since an CS- US-GNNmodee processes feature maps X² (S, v) where in the initial layer the sset size of S is encoded in (S, v). we can easily use the CS-GN OS-GGNuu in Definition A.5 to ignore all values of (", u) were |S| (This can be done by using f aggl ..... agg' in Definition A.5 to zero out these values at each update). This means CS CS-GNNusing ' is able to simulate an GN-uuaaaatte with the identity coarsening function, which was shown in Proposition D. to be as expressive as GNN-SSWL+ (Definition D.I) which is maximally expressive node-based subgraph GNN, thus proving part (1) of the proposition. To prove part (2), notice that using the same reasoning as before, an CS-CCS GNNmodel using T as coarsening function cal implement CS-GNNmodel using the edge coarsening function:
(' E G (V.
(217)
An CS- GNNNoddle with the identity coarsening function can be interpreted as a GNN-SSWL+ model. Similarly, an OS-GGNNodel using the edge coarsening function T' generalizes the GNN-SSWL+ framework by extending from node-based subgraph GNNs to edge-based subgraph GNNs. In fact, the same proof in [8 [2] showing that GNN-SSWL+ is at least as expressive as a DSS subgraph GNN using the node deletion policy (see 4 for a definition of the DSS subgraph GNN), can be used to show that CS-GNNusing the edge coarsening function T' is at least as expressive as a DSS subgraph GNN with an edge deletion policy. The latter model was shown in 4 to able to separate pair of 3-WL indistinguishable graphs. In contrast, node-based subgraph GNNs were shown in [12] to not be able to separate any pair of 3-WL indistinguishable graphs. Thus, there exists pair of graphs which CS- GNNusing T can separate while node-based subgraph GNNs cant, proving part (2) of the proposition.
G.5 Proofs of Appendix E
Lemma E.1 (y (I') are orbits). The sets 1-* I,..., n; E+; -}} and (1 shack :8.. th are the orbits of Sn on the index space (P([n)) x (vl) and (P((n)) x [m] (P((m)) x [n]), respectively.
Proof. We will prove this lemma for 7. The proof for I follows similar reasoning; we also refer the reader to 22 for a general proof.
We will prove this lemma through the following three steps.
(1). Given indices (S, i) E P((n) x [n), there exists E (P((x) x [n])~ such that (S, E En
(2). Given indices ()) y, for any Sn, it holds that (o- ( -1 -()) E 7.
47

---

(3), Given (S.t) and (S', E y (the same 7), it holds that there exists (S. (''
Sn such that
We prove what follows.
(1). Given indices (S) P([n]) x [n], w.l.o.g. assume that |S] k, thus if e S (i S) it holds that (S,1) E e ((S, )²), recall Equation (1).
(2). Given indices (5, E 7, note that any permutation E Sn does not change the cardinality of S nor the inclusion (or exclusion) of in S. Recalling Equation (71). we complete this step.
(3. Given that (S E and (S", E 7, and recalling Equation (1). we note that |S| = |S'| and that either both E S and 1' or both $ S and i' $ S'.
(3.1). (3.1) we focus on the case where & S and & S'. Let S fi...... is and S' fi....., 1% Then, we have (fi1..... (x).j) and (ft (f....., J'). Define S, such that consists of k + distinet indices and also consists of k + distinct indices, this is valid E Sn.
((h) = for E [k: and o(j) = j". Since (fi).-..,4e)
(01,-..,44)
(3.2). Here, we focus on the case where E S and 1' E S'. This proof similar to (3.1), but without considering the indices and j', as they are included in S and S", respectively.
Proposition E.1 (Basis of Invariant (Equivariant) Layer). The tensors B (B") in Equation 72 (Equation (74) form an orthogonal basis (in the standard inner product) to the solution of Equa- tion 66 Equation 67
Proof. We prove this proposition for the invariant case. The equivariant case is proved similarly - we also refer the reader for [22] for general proof. We will prove this in three steps,
(1). For any E (P((n)
[n])~ it holds that B solves Equation (66).
(2). Given solution L to Equation (66). is linear combination of the basis elements.
(3). We show that the basis vectors are orthogonal and thus linearly independent.
We prove in what follows.
(1). Given y E (P((n) [m])>. we need to show that B3 B 1(8),o 1()) Since any y (P((n)) x [n]) is an orbit in the index space (recall Lemma E. and B are indicator vectors of the orbits this always holds.
(2). Given a solution L to Equation (66). it must hold that Ls,; = Lo- Since the set fy k 1,..., n;
f+, }} corresponds to the orbits in the index space with respect to S,, L should have the same values over the index space of these orbits. Let's define these values as a for
each 7 E {>** : k = I...., n, * E {}- Thus, we obtain that L' = ( B?,
since B are simply indicator vectors of the orbits. This completes this step.
(3). Once again, since the basis elements are indicator vectors of disjoint orbits we obtain their orthogonality, and thus linearly independent.
48

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] is generally preferable to "[No]" it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract spells all the main contributions in the present paper, both theoretical and empirical ones. These are extensively discussed and recapitulated in the Introduction Section (see paragraphs "Our approach" and "Contributions"), The scope of the paper is well defined in the first periods of the abstract and comprehensively articulated in the first two paragraphs of the Introduction Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
49

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Please refer to paragraph "Limitations" in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Please refer to Appendices to and F.4 which include precise and contextu- alized statements of all theoretical results and derivations, and to Appendix G for proofs thereof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
50

---

Justification: Please refer to Appendix F.1 for a description of the employed datasets and splitting procedure, Appendices F22 F3 for list of experimental details and hyperparameter settings, and Appendix F.5 for series of complementary results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code to reproduce our results can be found in the following GitHub repository: tattps://githhr
www.eeentt-nuua-----eeaee GNNNs
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips. cc/
guuddes/CodeSuumisstt
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/nips.cc/ppili wttps/cccppbccccccccccccccccccct oog.addsee/eeeuuua/asssooooooopa
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
51

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Please refer to Appendix F. for description of the employed datasets and splitting procedure, Appendices F.2 and F3 for a list of experimental details and hyperparameter settings, including the utilized training procedures. The results for baselines approaches are reported according to what stated in Section 3 and Appendix F2
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Our results Section 5 are reported in terms mean and standard deviation calculated over different model initializations (i.e., by setting different random seeds prior to code execution). Table reports error bars for the results illustrated in Figure 2
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the eтror bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma emror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
52

---

For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The hardware employed to obtain all experimental results, as well as a rumtime comparison, are described in Appendix F22 (see "Implementation Details").
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
We have made sure to comply to the Code of Ethics and preserve our anonymity.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The models we developed are not generative, hence not posing risks of malicious use as for what concerns fabricating misleading or otherwise fake information. online profiles and media. Additionally, although our approach improves the efficiency of certain Graph Neural Networks, the models we developed are not scalable enough to apply and impact (online) social networks: represented graphs, their scale is way beyond that considered in our experiments.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinfornation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
53

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our model(s) do not have high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: As explicitly mentioned in the main corpus of the paper, the inset figure in Section is taken with permission by the original authors. Creators of datasets employed in this study, as well as the benchmark frameworks used are properly referenced and cited. For these last we report license information in Appendix [. also reported for code assets Appendix F22
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paweessipppweiiiiae...... thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
54

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
55


Reviews:
[{"review_id": "Tsh2FluhgC", "reviewer": "Reviewer_hoHT", "summary": "The paper is very well written. Existing subgraph GNN methods are mentioned. Then a novel subgraph GNN framework is formulated. The authors discuss the equivariance properties of this new subgraph GNN formulation followed by an experimental evaluation of the proposed method.", "questions": "1. Is there a case where the computational gains leads to a SOTA results on a large scale dataset?\n2. Could the experimental results improved if the proposed approach was combined with an approach similar to [2]. Improving the expressibility of the proposed model even further by combining with other classes of GNNs to get SOTA results would significantly improve the chances of the paper.\n\n[2] https://openreview.net/pdf?id=duLr8BIzro", "limitations": "The authors admit their proposed method has a high computational complexity. Thus naturally one would expect even higher model quality.", "rating": 2, "confidence": 3, "soundness": 1, "presentation": 4, "contribution": 2, "strengths": "* Strong mathematical formulation of the developed methods is provided.\n* The ideas are communicated well. One can see that the authors put a lot of time and effort into this work.\n* A comprehensive appendix is provided explaining the proposed approach in even more detail.", "weaknesses": "### The use of few and small datasets\n\nIf the goal of this work is to keep computational complexity low while improving the model quality, strong experimental results are expected.  This puts into question the developed theory and methods in the paper. I suggest the authors to find a scenario where their model can achieve SOTA results to justify their ideas. I would recommend including more datasets such as PCQM4Mv2 [1] to the experimental evaluation.\n\n### Limited baselines\n\nA simple comparison against a recent linear runtime complexity graph transformer alternative [2] shows that the experimental results are weak. A select few datasets are chosen and the achieved results are well below the current SOTA on them.\n\n### Weak motivation\n\nIf subgraph GNNs address the issue of limited expressiveness of existing work as stated in the introduction of the paper, then it makes one question why are the experimental results not good.\n\n[1] https://ogb.stanford.edu/docs/lsc/pcqm4mv2/\n\n[2] https://openreview.net/pdf?id=duLr8BIzro", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed feedback. We appreciate your positive remarks on our method's novelty, strong mathematical formulation, and clear writing. Below, we address your specific questions.\n\n**Q1:**  *The goal of our work and baselines*\n\n**A1:** Let us clarify. The goal of this work is to reduce the time and space complexity of Subgraph GNNs. As a result, some model degradation is expected. Subgraph GNNs are provably expressive models with theoretical guarantees [3, 4, 5], which may offer certain advantages over MPNNs and graph transformers. However, Subgraph GNNs typically have high computational complexity. Similarly to works like OSAN, PL, and Mag-GNN [6, 7, 8], our objective is to balance the high performance/accuracy of Subgraph GNNs with reduced computational expense. Unlike these other efficient Subgraph GNNs [6, 7, 8], our method offers a much finer control over this trade-off between computational complexity and accuracy in graph learning tasks, this is clearly illustrated in Figure 2, where bag size (x-axis) correlates with computational complexity. Within this family of more efficient Subgraph GNNs, we achieve SOTA results on most of the datasets these baselines are typically benchmarked on (see Tables 1, 4).\n\n**Q2:** *large scale datasets*\n\n**A2:** We refer the reviewer's attention to Table 8 in the appendix (p. 27), which presents results on the larger-scale ZINC-full dataset (250,000 graphs). We achieve top results in the efficient Subgraph GNN regime ($T=4$), outperforming MAG-GNN, the only other efficient subgraph GNN that reported results on this large-scale dataset. Furthermore, when using  our model in the farthest end of the trade-off (Full bag - $T=\"Full\"$), we achieve results comparable to the top-performing traditional \"non-efficient\" Subgraph GNNs, and *outperform leading Graph Transformers*. For instance, GRIT [9] reported an MAE of 0.023 on ZINC-FULL, while we obtained an MAE of 0.021.\n\nAs the reviewer requested, we also conducted a preliminary experiment using the large-scale molpcba dataset (437,929 graphs), which is also considered in the paper mentioned by the reviewer [2]. In particular, we train one instance of our model with a 1M parameter budget and report its performance against the methods in [2], see Table 1 in the attached PDF (in the global response).\n\nNotably, our method achieves comparable results to SOTA on this dataset while using the least number of parameters. Compared to GatedGCN-LSPE, which uses a similar number of parameters, our method demonstrates better performance. This improvement is also evident when compared to the GraphTrans baseline, which utilizes approximately four times more parameters than our approach. We believe that the results over ZINC-FULL, as well as the preliminary results over molpcba, demonstrates the potential of our method to handle large-scale datasets well. If the reviewer considers it important, we will extend our experiments on molpcba and include the results in the final version of the paper.\n\nDue to resource constraints, we couldn't conduct an experiment with the PCQM4Mv2 dataset (approx. 3,500,000 graphs) within the rebuttal period.\n\n**Q3:** *SOTA results on large scale datasets*\n\n**A3:** Recalling **A1**, **A2**, we achieve SOTA results on the large-scale ZINC-FULL dataset (Table 8, appendix, p. 27) in both efficient ($T=4$) and full-bag Subgraph GNN scenarios. Our approach outperforms top transformers like GRIT [9]. Preliminary experiments on the large-scale molpcba also indicate our model's competitive SOTA performance (Table 1 in the pdf).\n\n**Q4:** *Weak motivation*\n\n**A4:** We want to emphasize that our primary motivation, similar to previous works [6, 7, 8], is to reduce the computational cost of Subgraph GNNs. As mentioned in **A1**, we believe that within the family of algorithms that tackle the same setup (OSAN, PL, and MAG-GNN) [6, 7, 8], our method provides significant improvements in most cases – Table 1, 4, 8.\n\n**Q5:** *Could the experimental results improved if the proposed approach was combined with an approach similar to [2]. Improving the expressibility of the proposed model even further by combining with other classes of GNNs to get SOTA results would significantly improve the chances of the paper.*\n\n**A5**: We appreciate the reviewer's suggestion and have incorporated a version of the LCB block from [2] into our framework, which we term `Ours + LCB`. We ran experiments on three datasets (ZINC12k, Molbace, and Molesol) for three different bag sizes ($T=2$, $T=5$, $T=\"Full\"$). The results are in Table 2 of the attached PDF in the global response. \n\nWe positively note that, in the small-bag regime, the `Ours + LCB` method improves the performance of our model (which already outperformed most competitors on these datasets), sometimes significantly. We will do our best to extend and include these results in the final version of the paper, should the reviewer find them relevant.\n\n**Summary:** We believe we have thoroughly addressed your concerns about our method's capability with large-scale datasets and its integration with approaches from [2]. If you find our response satisfactory, we kindly request that you consider raising your score.\n\n**References:**\n\n[1] https://ogb.stanford.edu/docs/lsc/pcqm4mv2/\n\n[2] https://openreview.net/pdf?id=duLr8BIzro\n\n[3] Zhang et al. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. ICML 2023\n\n[4] Bevi. et al. Equivariant Subgraph Aggregation Networks. ICLR 2022\n\n[5] Frasca. et al. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. NeurIPS 2022\n\n[6] Qian et al.  Ordered subgraph aggregation networks. NeurIPS 2022\n\n[7] Bevi. et al. Efficient subgraph gnns by learning effective selection policies. ICLR 2023\n\n[8] Kong et al. Mag-gnn: Reinforcement learning boosted graph neural network. NeurIPS 2024\n\n[9] Ma et al. Graph Inductive Biases in Transformers without Message Passing. ICML 2023", "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": "", "extra_scores": {}}, {"review_id": "47Y9Yjk701", "reviewer": "Reviewer_h2GK", "summary": "The authors introduce a novel graph learning method that leverages message passing over product graphs. Specifically, message passing is performed over both the input graph and its product with a coarsened version of itself, which can be derived through techniques such as node clustering. Additionally, the authors propose a concept called symmetry-based updates, where message passing is enhanced by incorporating a graph representing a linear equivariant layer over the product graphs. A basis for such layers is also developed as part of their contribution. Experimental results demonstrate that this method performs comparably to state-of-the-art approaches.", "questions": "I would appreciate it if the authors could respond to the weak points **W1**, **W4**, **W5**, and explain what they want to convey with the section on “more than a coarsening function\" in Section 5.", "limitations": "This has been addressed in a satisfactory way by the authors.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "**S1 Product construction** The main conceptual contribution of the paper is the use of product graph construction to allow more flexibility and control over certain types of subgraph GNNs. The product construction itself is quite natural, although it introduces some overhead depending on the chosen instantiation.\n\n**S2 Equivariant basis** The key theoretical contribution is the identification of the bases of equivariant layers for such product graphs. This allows for a principled introduction of message passing using symmetries in the product graph.\n\n**S3 Competitive architecture** Experiments validate the proposed methods, showing that they are competitive with state-of-the-art methods.", "weaknesses": "**W1 Unclear key definition** \nThe key idea underlying the paper is commendable, although not extremely innovative. However, one crucial component is the graph coarsening introduced in Section 4.1. I found the definition on page 4 confusing despite multiple readings. What is defined there is an exponentially large fixed graph, with all subsets as nodes and adjacencies defined in equation (3). However, you mention before and after this that various coarsenings can be used, such as spectral clustering. How do these fit into the fixed definition given here? The presentation could be clearer.\n\n**W2 Weak theoretical analysis**\n The significance of Section 5, where the authors use their model for analyzing marking strategies, is not strongly demonstrated, at least based on the main paper. It primarily serves to justify the marking strategy in equation (10) but leaves a more detailed understanding of this strategy open. The section would benefit from a clearer presentation.\n\n**W3 Unclear presentation**\nCertain parts, as noted already in **W1** and **W2**, are not clearly described. Another example is Section 4.2.3, which is too succinct, and the visualization of $A_{equiv}$​ is rather cryptic. You mention a characterization and updates, but it is not clear what is meant here. A clear description of the instantiation of the framework used would be helpful. Similarly, the section starting from line 357 about “more than a coarsening function” is unclear, including the “informal” proposition statement.\n\n**W4 Unclear connection with OSANs**\n In the related work section, the authors contrast their proposal with OSANs [30], stating that OSANs use ordered tuples whereas the current paper uses sets of indices. However, unordered subgraphs play a key role in the OSAN paper as well since they showed that they can encompass most subgraph formalisms. A more detailed comparison would benefit the paper.\n\n**W5 Missing experimental details** \n- For the peptides experiments, you write “by using effective subsets of subgraphs.” What do you mean by this? What is this effective subset? How did you choose it? \n- Which version of OSAN do you compare with in the experiments (Table 4)? \n- Why do you use comparisons with different methods across the experiments (Table 2 vs Table 4)?\n\n**W6 Maximally expressiveness: clarification needed** At several points in the paper, you mention maximally expressive subgraph GNNs. It is unclear what is meant by this and this should be detailed, regardless of whether it was shown in [39].  As far as I know, general subgraph GNN do not have a maximally expressive instantiation, so I assume certain restrictions on the class of subgraph GNNs are in place. It would be beneficial to make these explicit to better understand the limitations of the proposed methods.\n\n**W7 Minor comments**\n\n*All figures (especially the font size used in the text in figures) in the paper are too small. Please enlarge them.*\n\n- L.82: What is $\\mathcal{X}$?\n- L218: The choice of $S_n$​ as a symbol for the symmetric group is not optimal, as subsets are denoted by $S_1$, $S_2$, etc.\n- L225: You mention “extension to multiple features is straightforward” and refer to [22]. A bit more explanation would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. We are pleased you appreciated the novelty of our idea and the identification of the basis of equivariant layers for our product graphs. Below, we address each of your points.\n\n**Q1:** *Key definition* \n\n**A1:** We emphasize that the coarsened graph is not exponentially large in practice (see also lines 288-292 in our paper). While nodes of the coarsened graph are in $P([n])$, only a small number are used. Using spectral clustering, we partition the graph $G$ and construct the coarsened graph $\\mathcal{T}(G)$ with nodes representing these partitions and edges induced by the original graph's connectivity (see Figure 1, left). This results in a coarsened graph with fewer nodes and edges than $G$. Although we define the graph for mathematical rigor, in practice, we use a much sparser graph by making $A^{\\mathcal{T}}$ and $X^\\mathcal{T}$ extremely sparse. **The space complexity of this sparse graph is upper bounded by that of the original graph $G$ (we do not store $2^n$ nodes)**. We thank the reviewer for pointing out this confusion and will clarify this in the final version of the paper.\n\n**Q2:** *Theoretical analysis* \n\n**A2:** We have justified the marking strategy from a theoretical perspective, demonstrating its superiority over previously suggested strategies [1,2,3]. While we have only briefly summarized our results in the main body due to space constraints, App. C (p.16) provides a detailed expansion.  We will make efforts to add more information to the main paper.\n\n\n**Q3:** *Presentation* \n\n**A3:** Thank you for highlighting these issues. Due to space limitations, Section 4.2.3 provides a brief summary of our use of the equivariant layers (see Section 4.2.2). For a detailed discussion, refer to App. F.4, p. 26). We will improve presentation and optimize space in the final version.\n\n'More than a coarsening function’: We wanted to convey the fact that our method does not simply reduce to the joint processing of the graph and its coarsened counterpart. In fact, as we show in App. D.2 in detail, our approach strictly improves over running msg-passing on the graph obtained by combining its original topology with information from the coarsening. We term this new graph the “sum graph” and illustrate it on p. 19. Our method gains in expressiveness over the “sum-graph”, demonstrating the importance of our additional technical contributions, i.e., the use of the graph product and the related equivariant operations.\n\n\n**Q4:**  *Connection with OSAN* \n\n**A4:** We agree with the reviewer and will add a detailed comparison with OSAN in the next revision.\n\nIn OSAN, the authors indeed show that ordered subgraphs are more expressive than unordered ones. In our case, although we choose coarsening functions which output unordered sets of nodes, we additionally leverage a set of additional equivariant operations which we formally derive as part of our contribution. Similarly to OSAN, it would be straightforward to show that our approach can indeed recover Subgraph GNNs operating on unordered subgraphs. However, the question whether OSAN fully captures our approach is of a less trivial answer, due to the aforementioned additional operations. Nevertheless, from an empirical perspective, our model demonstrates significantly better results.\n\nAdditionally, we note that unordered tuples are practically preferred in OSAN due to computational complexity reasons. Throughout their experimental section, the authors focus on unordered subgraphs and learn how to sample subsets of them. Our method shares this trait of (practically) considering only unordered subgraphs. Contrary to OSAN, however, we choose coarsening and graph products as an alternative to sampling. \n\nWe will refer to these observations in the next revision.\n\n**Q5:** *Experimental details* \n\n**A5:** We will answer each of the bullet points below: \n- \"Using effective subsets of subgraphs\": we refer to how our method naturally selects and uses relevant subgraphs for optimal performance.  To clarify, the initial step of our method involves coarsening the original graph $G$. We then use the graph Cartesian product between the coarsened graph $\\mathcal{T}(G)$ and $G$ to create the product graph, as illustrated in Figure 1 on p. 2. Even without explicitly extracting subgraphs, elements in $\\mathcal{T}(G) \\square G$ can be conceptually associated with them. The \"rows\" in the product structure (Figure 1, right) represent implicit subgraphs, a common association in previous works [2,3]. We will improve our wording in the final version of the paper.\n- To ensure a fair comparison, we compared with the best-performing version of OSAN, as shown in Table 1(a) of the OSAN paper [4], p. 9. \n- Different papers use various datasets. We used common datasets where possible for comparison. Using different baselines for different datasets aligns with field practices due to the high computational cost of running all baselines on all datasets, as shown, for example, in Tables 2,3 in [2].\n\n**Q6:** *Maximally expressive* \n\n**A6:** We agree with the reviewer's observation, and indeed certain restrictions exist. To clarify, [1] studies the expressiveness of Subgraph GNNs using node-based policies. Thus, \"maximal expressiveness\" in our paper refers to Subgraph GNNs with node-based subgraph selection [1,3]. We will add an app. section to clarify this point.\n\n**Q7:** *Minor comments*\n\n**A7:** \n- $\\mathcal{X}$ is the node feature matrix of the graph $\\mathcal{T}(G) \\square G$. \n- Thanks for the notes on L218, L225, and the figures. We'll revise them in the final version.\n\n**Refs.:**\n\n[1] Zhang et al. A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests. ICML 2023\n\n[2] Bevi. et al. Equivariant Subgraph Aggregation Networks. ICLR 2022\n\n[3] Frasca. et al. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. NeurIPS 2022\n\n[4] Qian et al.  Ordered subgraph aggregation networks. NeurIPS 2022", "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": "", "extra_scores": {}}, {"review_id": "XWqRTRxDNA", "reviewer": "Reviewer_DujM", "summary": "This paper proposes CS-GNN, a subgraph GNN approach utilizing graph coarsening and graph Cartesian products. This novel and flexible subgraph GNN can effectively generate and process any desired bag size. The paper also discovers new permutation symmetries in the produced node feature tensor during generalized message passing. Theoretical and empirical analysis validate the efficacy of the proposed method.", "questions": "1. The size of the coarsened graph, though sparse, is still very large with $2^n$ nodes, which might result in high computation complexity for large input graphs. Do you have an estimate of the complexity and runtime of the proposed model compared with others?\n2. Eq. (3) indicates that the input graph is unweighted and edge weights might not be considered. What if the input graph is weighted, for example, with edge weights 1,2,3, and 4.", "limitations": "Yes, the authors have adequately addressed the limitations and, if applicable, potential negative societal impact of their work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The topic of subgraph GNNs is interesting.\n2. The paper is generally well-written with clarity.\n3. The proposed method is novel, with theoretical underpinnings.\n4. The empirical results seem promising.\n5. The implementation code is provided for reproducing the results.", "weaknesses": "1. The size of the coarsened graph, though sparse, is still very large with $2^n$ nodes, which might result in high computation complexity for large input graphs.\n2. Eq. (3) indicates that the input graph is unweighted and edge weights might not be considered.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your positive feedback! We are pleased to hear that you find our method novel with solid theoretical foundations. We're also glad that you find the empirical results promising. Below, we address your specific comments and questions.\n\n **Q1:** *The size of the coarsened graph, though sparse, is still very large with $2^n$ nodes, which might result in high computation complexity for large input graphs. Do you have an estimate of the complexity and runtime of the proposed model compared with others?*\n\n **A1:** Let us clarify our approach. In our method, the size of the coarsened graph is always less than or equal to that of the original graph. **To further emphasize, the space complexity of storing this sparse graph is upper bounded by the space complexity of storing the original graph $G$ (we do not store $2^n$ nodes)**. As shown in Figure 1 (left), the coarsened graph $\\mathcal{T}(G)$ has fewer nodes than the original graph $G$. Considering the feature dimension to be constant, and given that $V$ is the number of nodes in the original graph, $T$ is the bag size, and $\\Delta_{\\text{max}}$ is the maximal degree of the original graph, our time complexity is upper-bounded by $\\mathcal{O}(T \\cdot V \\cdot (\\Delta_{\\text{max}} + T))$. When considering $T=\\mathcal{O}(1)$, which is typically the case, the complexity simplifies to $\\mathcal{O}(V \\cdot \\Delta_{\\text{max}})$. The space complexity is $\\mathcal{O}(T \\cdot E + V \\cdot T^2)$, where $E$ is the number of edges in the original graph, which reduces to $\\mathcal{O}(V +E) $, when $T = \\mathcal{O}(1)$. This complexity is comparable to that of other methods in the field [1, 2]. Additionally, we refer the reader to Table 10 in Appendix F.5 (page 28) for a detailed comparison of the runtime of our method with other baselines. Our method's runtime is comparable to theirs. \n\n**Q2:** Eq. (3) indicates that the input graph is unweighted and edge weights might not be considered. What if the input graph is weighted, for example, with edge weights 1,2,3, and 4. \n\n**A2:** Thank you for highlighting this point. Our method is capable of handling weighted graphs. We employ a GINE base encoder [3], which can process edge features when applicable. For further details regarding our implementation, please refer to Appendix F (page 24) -- the update mechanism of the GINE base encoder, which supports edge features, is detailed in Equation (92) on page 24.\n\n**References:** \n\n[1] Bevilacqua et al. Efficient subgraph gnns by learning effective selection policies. ICLR 2023 \n\n[2] Kong et al. Mag-gnn: Reinforcement learning boosted graph neural network. NeurIPS 2024 \n\n[3] Hu et al. Strategies for pre-training graph neural networks. ICLR 2020", "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": "", "extra_scores": {}}]

Author rebuttal:
We are grateful to all reviewers for their feedback and constructive comments and happy to see that our work was positively received in general.

In particular, the reviewers all recognized the novelty and importance of our proposed method:
- “The topic of subgraph GNNs is interesting” (**DujM**)
- “a novel subgraph GNN framework” (**hoHT**)
- “a novel graph learning method” (**h2GK**)
- “The proposed method is novel” (**DujM**)

An essential part of our work involves recognizing that our product graph introduces new permutation symmetries. We demonstrate how to construct networks that respect these symmetries, supported by both theoretical analysis and empirical evidence. This approach has also been positively received:

- “The paper also discovers new permutation symmetries” (**DujM**)
- “Strong mathematical formulation” (**hoHT**)
- “The proposed method is novel, with theoretical underpinnings” (**DujM**)
- “Theoretical and empirical analysis validate the efficacy of the proposed method”. (**DujM**)
- “The key theoretical contribution is the identification of the bases of equivariant layers for such product graphs.” (**h2GK**)
- “Experiments validate the proposed methods, showing that they are competitive with state-of-the-art methods” (**h2GK**)
- “The empirical results seem promising.” (**DujM**) 

Finally, we were also very happy to notice that the reviewers have found our paper to be “very well written” (**hoHT**, **DujM**). 
At the same time, reviewers shared comments and questions, which we address in the specific rebuttals below. Additionally, we conducted new experiments as requested by (**hoHT**). The results, included in the attached PDF file, demonstrate that our method effectively handles large-scale datasets and benefits from combining our approach with his suggested method.

Meta-review: This paper presents a smart idea of efficient subgraph GNNs by performing message passing on the product graph of the original graph and a coarsend graph, where the coarsening degree controls the complexity of the final model. This contrasts from existing acceleration techniques based on random sampling or learning to select a subset of subgraphs, and has the benefit of training-free acceleration and flexible control of the model complexity. The authors also identify the new symmetries in the product graph and characterizes all the linear equivariant operators through solid theoretical analysis. Experimental results demonstrate that the method compares favorably to random sampling and MAG-GNN (RL-based sampling) in small bag size settings, and approaches SoTA results in full bag size settings.

Overall, considering subgraph GNNs are a promising approach to break the expressivity bottleneck of GNNs/GTs and accelerating subgraph GNNs is of vital importance for their wide adoptations by practioners, I would recommend an acceptance of the paper.
Decision: Accept (poster)