Schur Nets: exploiting local structure for equivariance in higher order graph neural networks
Authors: QINGQI ZHANG
Ruize Xu
Risi Kondor
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural networks
equivariance
spectral graph theory
higher order message passing
Primary area: graph_neural_networks
TL;DR: We show how to build higher order GNNs that are equivariant to the automorphism groups of subgraphs without actually having to find the automorphism groups.

Abstract: Recent works have shown that extending the message passing paradigm to subgraphs communicating with other subgraphs, especially via higher order messages, can boost the expressivity of graph neural networks. In such architectures, to faithfully account for local structure such as cycles, the local operations must be equivariant to the automorphism group of the local environment. However, enumerating the automorphism groups of all subgraphs of interest and finding appropriate equivariant operations for each one of them separately is generally not feasible. In this paper we propose a solution to this problem based on spectral graph theory that bypasses 
having to determine the automorphism group entirely and constructs a basis for equivariant operations directly from the graph Laplacian. 
We show that this approach can boost the performance of GNNs on some standard benchmarks.

Schur Nets: effectively exploiting local structure for equivariance in higher order graph neural networks
Qinggi Zhang" Ruize Xu and Risi Kondor *Computational and Applied Mathematics Departments of R CCmmuter Science and Sttttistics University of Chicago
{qingqi richardixur rrisii wwwiiiiisiiiiioo Cachicago.....o. edu
Abstract
Recent works have shown that extending the message passing paradigm sub- graphs communicating with other subgraphs, especially via higher order messages, can boost the expressivity of graph neural networks. In such architectures, faithfully account for local structure such as cycles, the local operations must be equivariant to the automorphism group of the local environment. However, enumer- ating the automorphism groups of all subgraphs of interest and finding appropriate equivariant operations for each one of them separately is generally not feasible. this paper we propose solution to this problem based on spectral graph theory that bypasses having determine the automorphism group entirely and constructs a basis for equivariant operations directly from the graph Laplacian. We show that this approach can boost the performance of GNNs on some standard benchmarks.
Introduction
Message pasing neural networks (MPNNs) are the most popular paradigm for building neural networks graphs [18]. While MPNNs have proved to be remarkably effective in range of domains from program analysis [1] to drug discovery [20], a series of both empirical [3] and theoretical [40, 10] results have shown that the fact that MPNNs are based just vertices sending messages to their neighbors limits their expressive power. This problem is especially acute in domains such chemistry, where the presence absence of specific small structural units (functional groups) directly influences the behavior and properties of molecules.
Recent papers proposed to address this issue by extending the message paradigm to also allow for message passing between vertices and edges [24] or between subgraphs [2, 15, 4, 46). However, if the actual messages remain scalars, the added expressive power of these networks is relatively limited.
newer development is the appearance of higher order MPNNs, where the messages are not just scalars, but more complex objects indexed by the vertices of the sending and receiving subgraphs [31, 34, 14]. For example, in organic molecule, the internal state of benzene ring (six carbon atoms arranged in a cycle) can be represented as matrix T E R6xe, where the rows correspond to the individual carbons. When this benzene ring passes a message that it shares an edge with, information relating to the two shared carbons can be sent directly to the corresponding atoms the second ring. Information relating to the other vertices has to be treated differently. Hypergraph neural networks [15, 45, 41] and neural networks on more abstract mathematical structures such as simplicial complexes [7, 6] are closely related, since these also
neighboring benzene ring
denotes equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

involve higher order generalizations of message passing between combinatorial objects interlocked in potentially complicated ways.
In prior work we introduced a formalism called P-tensors that provides a flexible framework for implementing and reasoning about higher order MPNNS [21]. P-tensors build closely on the by now substantial literature on permutation equivariance in neural networks from Deep Sets [43], to various works studying higher order permutation equivariant maps [32]. is also related to the category theoretic approach employed in Natural Graph Neural Networks [12].
One aspect of higher order message passing that has hithero not been studied in detail is the interaction between the local graph structure and the equivariance constraint. Intuitively. the reason that GNNs must be equivariant permutations is that when the same, analogous, graphs are presented to the network with the only difference being that the vertices have been renumhered, the final output must remain the same. However, Thiede et al. [37] observed that enforcing full permutation equivariance, especially at the local level, can be too restrictive. When considering specific, structurally important subgraphs such as paths or cycles, the operations local to such a subgraph S should really only be equivariant to the automorphism group of S, rather than all |S|! permutations. The Autobahn architecture described in [37] explicitly accounts for the automorpism group of two specific types of subgraphs, cycles and path. Defining bespoke convolution operations on these two types of subgraphs was shown improve performance on molecular datasets like ZINC [26].
The drawback of the Autobahn approach is that it requires explicitly identifying the automorphism group of each type of subgraph, and crafting specialized equivariant operations based on its repre- sentation theory. For more flexible architectures leveraging not just cycles and paths but many other types of subgraphs this quickly becomes infeasible.
Main contributions. The main contribution of this paper is a simple algorithm based on spectral graph theory for constructing basis of automorphism equivariant operations any possible subgraph without explicitly having to determine its automorphism group, let alone derive its irreducible representations. The algorithm is based on imitating the structure of the group theoretical approach to equivariance, which we summarize in Section 3, but bypassing having to use actual group theory. Section 4 describes the algorithm itself and the resulting neural network operations, which we call Schur layers. In Section 5 we show that the introduction of Schur layers does indeed improve the performance of higher order graph neural networks on standard molecular benchmarks.
2 Background: equivariance with side information
Let G be an undirected graph with vertex set V (1, 2, ........... by the adjacency matrix A E R Graph neural networks (GNNs) address one of two, closely related tasks: (a) given a function f V - IR on the vertices of G. learn to transform function fou;; : V + R; (b) given not just one graph, but an entire collection of graphs, learn to map each graph G. or rather its adjacency matrix, to a scalar or vector (AA that characterizes G's structure.
. n. and edge set E S V V represented
another
In both cases, the critical constraint is that the network must behave appropriately under permuting the order in which the vertices are listed. The group of all permutations of {1, 2, ... .n is called the symmetric group of degree n and denoted S., Applying a permutation a E S, to the vertices changes the adjacency matrix to A' = (A) with
Ale = Ag 1(0,0 1())
(1)
The basic constraint on algorithms that operate on functions on graphs is that if the input is transformed along with the numbering of the vertices, = 1(2) then the output must transform the same way, Leun = - This property is called equivariance. Formally, denoting the mapping from inputs to outputs 0: fin + fout, equivariance states that the action a: I + f' of permutations on functions given by f fo-1(1) must commute with é, that is,
(())
Hlo ((o()=)) (()))
for any E S., and any input function مشP E VRR. In contrast, for networks that just learn embeddings g (((A) (A), the constraint invariance to permutations, i.e., (AA) = (A)). In practice, the two cases are closely related because most graph embedding networks work with functions defined on the

---

vertices, and then symmetrize over permutations in their final layer using readout function such as (G)) ft
Enforcing (2) on the hypothesis space directly would be very limiting, effectively constraining GNNs to be composed of symmetric polynomials of f combined with pointwise nonlinearities. Message passing graph neural networks cleverly get around this problem by using the adjacency matrix itself as side information to guide equivariance. For example, classical (zeroth order) MPNNs, the output of each layer is a (vector valued) function on the graph, and the update rule from layer to layer & + 1 in the simplest case
fe+ --l=n(W nn( +0)
where Mii) denotes the neighbors of node in G. W and are learnable weight matrices/vectors and 7) is suitable nonlinearity. The fact that the summation only extends over the neighbors of vertex i induces a dependence of á on the adjacency matrix A. Hence it would be more accurate to use the notation A for the mapping, and write the equivariance condition as
(o(A)(o(f")) ))
In this interpretation, when the vertices are permuted, A can implicitly provide information about this to the algorithm, allowing it to compensate. However, A cannot convey any information about permutations that leave it invariant, so O must still be equivariant to the group of all such permutations, called the automorphism group of G, denoted Aut(G) or just Aut(A). This observation about A acting as a source of side information that can reduce the size of the group that individual GNN operations need to be equivariant to is the starting point for the rest of this paper.
2.1 Higher order GNNs
Despite the great success of message passing networks, long sequence of empirical as well as theoretical results [40, 34, 30, 13, 35] over the last several years have made it clear that the expressive power of algorithms based on simple update rules like (3) is severely limited. In response, the community has extended the message passing paradigm to message passing between vertices and edges or between carefully selected subgraphs [18, 34, 6, 8]. These networks maintain the local and equivariant character of earlier MPNNs. but they can more faithfully reflect local topological information and are particularly well suited to domains such as chemistry, where capturing local structures such as functional groups is critical.
In tandem, researchers have developed higher order MPNN architectures, where the outputs of individual edge or subgraph "neurons" are not just scalars, but vector or tensor quantities indexed by the vertices of the graph involved in the given substructure. For example, in the chemistry setting, if n is titular neuron corresponding to a benzene ring in a molecule, the output of n, assuming we have channels, might be matrix T E R or a tensor T E 5x or T E 16x6666X etc.. In each of these cases the non-channel dimensions correspond to the six atoms making up the ring, and when n communicates with other subgraph-neuroons, must be treated accordingly. Such higher order representations offer greater expressive power because they allow T to capture information about relations between pairs of vertices, triples, and so on. The general trend towards studying higher order message passing is also closely tied to the emergence of hypergraph neural networks [15], "topological" neural networks and simplicial complex networks [7, 6].
Recently, [21] proposed general formalism for describing such higher order architectures using so-called P-tensors. In this formalism, given a neuron n attached we say that the output of is a zeroth order P-tensor T with C' channels if it is simply vector T E C. The elements this vector are scalars in the sense that they are invariant to permutations of the vertices of S. We say that T is a first order P-tensor if it is matrix T e R whose columns transform under permutations of S similarly to how f and fout transform under global permutations of the full graph:
subgraph S with m vertices,
T T"
The = -T
E SSS-
(5)
We say that T is a second order P-tensor T mmxxxC if each slice corresponding to a given channel transforms according to the second order action of the symmetric group, similarly (1):
T + T
The To T
E Sm-
(6)
3

---

Continuing this pattern, a k 'th order P-tensor T E IBmXXxX..Xxxx transforms under local permuta- tions as
T:THT
TV A1 T -0)
S
[21] derives the general rules for equivariant message passing between such P-tensors in the cases that the sending and receiving subgraphs S resp. are (a) the same (b) partially overlap (c) are disjoint. However, in each of these cases however it was assumed that 7 needs to be equivariant to all possible permutations of the vertices of the underlying subgraphs and S"
As we discussed above, this is an overly restrictive condition that limits the extent to which a higher order subgraph neural network can exploit the underlying topology. In the following sections focus on just the type of messages that are sent from given subgraph S to itself (called linmaps in the P-tensors nomenclature), and derive way of making these messages equivariant to just Aut(S) rather than the full symmetric group Sm-
3 Equivariance to local permutations: the group theoretic approach
Recall that a representation of a finite group such as S., or Aut(S) a (complex) matrix valued function p: G + Cd where the p(o) matrices multiply the same way the corresponding group
elements do
p(a201) p(o2)p((1)
01 02 EG
Two representations P and p' said to be equivalent if there is invertible matrix Q such that p' = p(r) Q for all group elements. A representation of finite group is said to be reducible block diagonal form
there some invertible matrix Q that reduces
p(a) = Q- Q-
(0-1(000) (m)(O)
(p
P2(0)
Q-
Some fundamental results in representation theory tell us that G only has finite number of inequiva- lent irreducible representations (irreps, for short), these irreps can be chosen to unitary, and that any representation of G is reducible to some combination of them [36]. These facts give rise to type of generalized Fourier analysis on finite groups that can decompose vectors that acts on into parts transforming according to the unitary irreps of the group.
The general approach to defining -qquiiaaqu maps for first, second, and higher order subgraph neurons would use this machinery. In particular, defining permutation matrices as usual as
PP {
if o(j)= =i
otherwise,
dropping the channel indices without loss of generality, and writing our P-tensors in vectorized form T vec( E R=" (55)(7) can be written in a unified form
T = ==='
where (a) is the k-fold Kronecker product matrix pk (a) = Pg P.. Crucially, as a ranges over the automorphisms S, these product matrices (a), form unitary representation of the automorphism group.
According representation theory. pk must then be decomposable into a direct sum irreps P Pp of Aut(S) with corresponding multiplicities K1, Kpp The same unitary matrix Q that accomplishes this can also used decompose T into a combinations of smaller vectors (t) E (R )..:
QT
where each tú now transforms independently under the action of the group as E + (p( ty. Al- ternatively, stacking all Eÿ vectors transforming according to the same irrep p. together in matrix T E Rd xx; we arrive at sequence of matrices T T ...., T transforming as
((pp(())
2 H p2(0) T
T + Pp(o) T
(8)

---

It is very easy to see how one might construct learnable linear operations that are equivariant to these actions: simply multiply each T from the right by learnable weight matrix W".
This general, group theoretic approach to constructing automorphism group equivariant linear maps between k'th order P-tensors can be seen special case of [29, 38). Operationally, it just reduces to the following sequence of steps:
1. Find the unitary matrix Q that decomposes ph (o) Po @ Po into direct sum of Aut(S) irreps.
2. Use Q to decompose the input P-tensor into a sequence of matrices T!.. Tp transforming as (8).
3. Multiply each T" by an appopriate learnable weight matrix W E TR
4. Use the inverse map Q 1 Q' reassemble T T ..... T into the output P-tensor 7
Notwithstanding its elegance, this representation approach to implementing automorphism group equivariance also has some disadvantages. Specifically, it requires to (a) determine the automorphism group of each subgraph, and (b) explicitly find its irreducible representations, which is also not trivial. The underlying mathematical structure however is important because it forms the basis to generalizing the approach to a much simpler framework the next section:
1. We have collection of (orthogonal) linear maps { (Pk (ar): U + UOEAU(S) (with U = Rm that the neuron's 's operation needs to be equivariant to.
2. U is decomposed into an orthogonal sum of subspaces U = U1 .... @ Up corresponding to the different irreps featured in the decomposition of pł
3. Each U, is further decomposed into an orthogonal sum of subspaces U₁ V1 + V corresponding to the different columns of the T" matrices.
4. The decomposition is such that the { [P& (a)) maps fix each Vj subspace. Moreover, for fixed
i, (P* acts the same way on each Vj subspace by p;(o))
5. This structure implies that any linear map that linearly mixes the Vi.... V subspaces but does
not mix information across subspaces with different values of is equivariant.
4 Equivariance via spectral graph theory: Schur layers
In place of the representation theoretical approach described in the previous section, in this paper we advocate simpler way of implementing automorphism group equivariance based on just spectral graph theory. The cornerstones of this approach are the following two theorems. The proof's can be found in the Appendix.
Theorem 1. Let G' be a finite group acting on space U by the linear action {g: U + U} JEGG Assume that we have a decomposition of into a sequence of spaces of the form
U U...
where each U3 is invariant under the action of the group (this means that for any 9 E Gand e U,, have g(u) E U.). Let o: U + U be a linear map that is a homothety on each Ug i.e. Φ(w) = a; for some fixed scalar as for any Ug. Then & is equivariant to the action of G, i.e. Ø(g(u)) g for any u E U and any g G.
The representation theoretic result of the previous section corresponds a refinement of this result involving a further decomposition of each U; space into a sequence of smaller subspaces.
Theorem Let and U be as in Theorem 1, but now assume that each Ug further decomposes into an orhthogonal sum of subspaces in the form U, V ..... ④ V such that (a) Each Vi subspace is individually invariant by G;
(b) For any fixed value of i, the spaces Vi...., Vi, are isomorphic and there is set of canonical isomorphisms 1//30: Vi Vj between them such that
= ())s;((()))))
YueV3.
Let o: U + U be map of the form
Φ(v) = afy (0)
v V Vj
for some fixed set of coefficients {af J. Then is equivariant to the action of G on U.
5

---

In the matrix language of the previous section, U1.... Up correspond to the T TT..... T matrices, whereas the Vi..... V subspaces U, correspond individual columns of T', For any fixed i, the (o) scalars correspond to the individual matrix entries of the learnable weight matrix W For our simplified spectral approach to automorphism group equivariance we will content ourselves with using Theorrm I rather than Theorem 2.
4.1 Automorphism invariance the simple way via spectral graph theory
The key insight of this paper is that we do not necessarily need to use heavy representation theoretic machinery to find a system of subspaces to plug into Theorem 1. In particular, we have the following simple lemma.
Lemma 1. Let S be an undirected graph with vertices, Auts its automorphismm group, and its combinatorial graph Laplacian. Assume that I has distinct eigenvalues >1,-..,>, Xp and corresponding subspaces U1,-.., Up. Then each U, is invariant under the first order action (5) of gutg on IRm..
Proof. Since Auts is a subgroup of the full group of vertex permutations, its action on 1h is just V a(v) v.v with E Autz. L is real symmetric matrix, its eigenspaces U..... Up mutually orthogonal and U1 @ @ Up = IR.. Furthermore, E U, if and only if Lv v.v. By definition, Auts is the set of permutations that leave the adjacency matrix, and consequently the Laplacian invariant, so. In particular, Po LP = L for any a E Auts. Therefore, for any v U;
(o(v)) = LP.v
PP PaLv= A.vv= >xo(y)
V
showing that ((v) E U, Hence U; an invariant subspace.
The following Corollary puts this lemma to use, providing a surprisingly easy way of creating locally automorphism equivariant neurons. We define a Schur layer as a neural network module that applies this operation to every instance of given subgraph in the graph, for example, every benzene ring in molecule. For the sake of global permutation equivariance, the weight matrices for any given subgraph S must shared across all instances of S across in the graph.
Corollary 1. Consider a GNN on a graph that involves a neuron ng corresponding to a subgraph S with vertices. Assume that the imput of ng is matrix T E mxxx the rows of which transform covariantly with permutations of and Cm is the number of channels. Let L be the combinatorial Laplacian of S, U1 U1....,U Up be the eigenspaces of L, and M; an orthognal basis for the i 'hth eigenspace stacked into an R8 [nxdim(U dimensional matrix. Then for any collection of learnable weight matrices
W1.... ........ Wp E R Row
P T: Σ
M.M.T.WW TW:
a permutation equivariant linear operation.
The spectral approach also generalizes to higher order permutation equivariance, in which case we can take advantage of the more refined two-level subspace structure implied by Theorem
(i....., in) {L. we define its type as the tuple n = (Mi,.... nPp), where ny is the number of occurrences j in and we define In as the set of all multi- inttiis of type n. Assume that the input to neuron ns is a k 'thh order permutation equivariant tensor T E Rmx. Xmx6o, as defined in Section 3. For any given i, define the 'th order eigen- Sgen-projector
Theorem 3. Let S. and the M, 's be as in Corollary 1. Given multi-index
I1 = PM, & M., &... M,,, @ 1): DD:BB....... +
where Pi is a permutation map that canonicalizes the form of the projection, as defined in the Appendix. Let T o W denote multiplying T by the matrix W only along its last dimension. Then for any collection of weight matrices {Wr.r E Re the map
6: T
ΣΣΣ I'ET.
nI (IL(T 3 Wr.r)
is permutation equivariant map.
Corollary 1 and Theorem 3 give sufficient but not necessary conditions for equivariance w.r.t. the automorphism group. discussion of the potential gap between our approach and the full group theoretical approach described in Section 3 can be found in Appendix D.

---

5
Experiments
To empirically evaluate our Schur layers, we implement the first order case described in Corollary 1 and compare it with other higher order MPNNs. Note that the theorem only gives the equivariant maps to transform local representation on a subgraph, i.e., é 7 Y 7 where 7 E IR. mRx and Toul E IR G are the inputs and output of neuron corresponding to a specific subgraph. The rest of the message passing is conducted in the usual way, in particular, everything is implemented the P-tensors framework [21].
There are several design details about the architecture that worth mentioning: (1) We chose cycles of lengths three to eight in most of the experiments and also added branched cycles to show our algorithm's 's scalability. The reason is that in the chemical dataset we used, cycles are the most important functional group to the property to be predicted, other subgraphs such as m-stars, and m-paths did not help the performance. (2) While having first-order representation on the cycles, we also maintain O'th-order representation (i.e., scalars) on node and edges, as in [6, 21J. These node and edge representations capture more elementary information about the graph, such k-hop neighborhoods, and are still important in higher order MPNNs. The representations pass messages with each other by intersection rule as defined in P-tensor framework. (3) As discussed in Appendix G, we view Schur layer's operation as a spectral convolution filter [5] applied to the subgraph and the number of channels to indicate how many times expands the input feature to the output feature. The codes used to run our experiments can be found at https: : //gg hgggtthubb.... com com/risth www.rriialbbb//br.... sisssb/Schureetttt
5.1 Schur layer improves over Linmaps
First of all, we want to show that considering more possible equivariant maps on the subgraph can indeed boost the performance. To this end, we performed controlled experiments to compare Schur layer with the equivariant maps w.r.t. Sn, (following [21] we called these linmaps). To make fair comparison, we use the same architecture including MLPs and message passing defined by P-tensor and only replace the equivariant maps used in Linmaps by what is defined in Corollary 1. We didn't compare with Autobahn [37] because it didn't t use the P-tensor framework in the original paper and it's hard for us to implement the convolution w.r.t. automorphism group for all the subgraphs we chose. However we note that for the case of the cycles (see Table 4), the equivariant maps given by our approach are equal to that given by the group theoretical approach.
We'll present the results on the commonly used molecular benchmark ZINC-12K [26] dataset in the main text. Results on TUdatasets as well runtime comparison can be found in Appendix H. The task on ZINC- -2K is to regress the log P coefficient of each molecule and the Mean absolute error (MAE) between the prediction and the ground truth used for evaluation.
We design experiments to compare Limmaps and Schur layers in various scenarios, to showcase the robustness of the improvement. Table shows under various message passing schemes between edges and cycles, Schur Layer consistently outperforms Linmaps. Those are indications of the added expressive power of extra equivariant maps in Schur layer, and they're dey're effective in various architectural design settings. Another ablation study regarding different cycle sizes can be found in Appendix H.
Layer
Pass message when overlap
Pass message when overlap 2 2 0.074 + 0.005
Linmaps (baseline)
0.074 + 0.008
Schur layer
0.070 + 0.006
0.071 + 0.003
Comparison between Schur Layer and Linmaps with different message passing schemes. The message passing scheme is a design choice in P-tensor framework, where the user can set when two subgraph's 's representations communicate. The mostly common use case to require at least vertices in the intersection of two subgraphs for them to communicate. Experiments on ZINC-12k dataset and all scores are test MAE. Cycle sizes of (3,4.5,6,7.88111 are used.
Table 1:
Then we studied the possibilities of adding Schur layer in different places of higher-order message passing scheme. In table 2, we observed that the more condensed the higher-order feature is, the more improvement that the Schur Layer brings to us over Linmaps. We attribute the improvements of adding/replacing Schur layer in various scenarios over Linmaps the benefit gained from utilizing the
7

---

subgraph structure and increased number of equivariant maps. We also tried other ways to use Schur layer, the result is summarized in Appendix G.
Model
Test MAE
Linmaps
0.071 = 0.004
Simple Schur-Net
0.070 = 0.005
Linmap Schur-Net
0.068 0.002
Complete Schur-Net
0.064 + 0.002
Table 2:
An experiment demonstrating different ways of using Schur layer. "Complete Schur Layer" means that we apply Schur Layer on the incoming messages together with the original eycle represen- tation. "Linmap Schul.aeer means that we just apply the Schur Layer on the aggregated subgraph representation feature. "Simple Schur Layer" means we directly apply Schur Layer on the subgraph features without any preprocessing. We can observe that as the subgraph information diversifies, Schur layer tends to decouple the dense information better and results better performance. The test MAE of Linmaps in this table is taken from [21].
5.2 Flexibility
The other advantage of Schur layer is that it computes the feature transform only based the subgraph's 's Laplacian, bypassing a difficult step of finding the automorphisms group and irreps the subgraph it acts As diseussed in the theory, Schur layer constructs equivariant maps only based on the subgraph's 's Laplacian and is applicable directly to any subgraphs, making the implementation much easier when different subgraphs are chosen than the group theoretical approach. This allows it to easily extend to any subgraph templates that' re favorable by the user. To demonstrate this, we augment the subgraphs in the model by all the five and six cycles with one to three branches (including in total 16 non-isomorphic subgraph templates), comparing with baseline model where only the cycle itself considered. Results can be found in Appendix G.
5.3 Benchmark results
Finally, and most importantly, we compare the Schur-Net to several other higher-order MPNNs I on ZINC-12K dataset and OGB-HIV dataset [23] in table 3. We included baselines of (1) classical MPNNs: GCN[28], GIN [40], GINE [24], PNA[11], HIMP [16] (2) higher order MPNNs: 22-GNN
[14] 2, CIN [6], P-tensors [21] (3) Subgraph-GNNs: DS-GNN(EGO+) and DSS-GNN(EGO+) [4],
GNN-AK+ [46], SUN(EGO+) (4) Autobahn [37].
We find that Schur Net ranked second on 7INC-12K and outperformed all other baselines OGB- HIV dataset. This shows the expressivity of adding more equivariant maps by leveraging the subgraph topology. Furthermore, note that while 2N-GNN outperforms Schur Net ZINC-12K, it's second- order model whereas in our experiment, we only used first-order activation. Also, the partial reason Autobalin didn't 't perform well is in the original implementation, the authors didn't use P-tensor framework and used only a part of all possible linear message passing schemes. This shows to get the full power of equivariant maps w.r.t. subgraph automorphism group, need combine it with general message passing framework between subgraphs as well.
Limitations
Unlike the representation theoretic approach, the spectral approach is guaranteed the give the finest possible decomposition into invariant subspaces. Hence, equations like (9) do not necessarily define the most general possible automorphism-equeeee eeqiivariinvviinntt linear maps. In this paper we did not investigate from a theoretical point of view the extent of this gap. In general, being able to craft automorphism- equivariant layers of any order for any types of subgraphs opens up host of possibilities for making GNNs more powerful. Our experiments are limited to some of the simplest cases, such as exploiting cycles and edges. We also only used first order activations.
AA discussion related work can be found in Appendix C. "The works [31, 34] don't 't have results in those two dataset.
8

---

Model
ZINC-12K MAE())
OGB-HIV ROC-AUC(%
GCN
0.321 + 0.009
76.07 + 0.97
GIN
0.408 + 0.008
75.58 + 1.40
GINE
0.252 + 0.014
75.58 + 1.40
PNA
0.133 + 0.011
79.05 1.32
HIM
0.151 + 0.002
78.80 1 0.82
N2-GNN
0.059 = 0.002
CIN
0.079 = 0.006
80.94 0.57
P-tensors
0.071 + 0.004
80.76 0.82
DS-GNN (EGO+)
0.105 + 0.003
77.40 2.19
DSS DSS-GNN (EGO+)
0.097 = 0.006
76.78 + 1.66
GNN-AK+
0.091 = 0.011
79.61 + 1.19
SUN (EGO+)
0.084 = 0.002
80.03 + 0.55
Autobahn
0.106 + 0.004
78.0 + 0.30
Schur-Net
0.064 + 0.002
81.6 + 0.295
Table 3: Comparison of different models the ZINC-12K and OGBG-MOLHIV datasets.
7 Conclusions
Enforcing equivariance to the automorphism group of subgraphs in higher order neural networks seemingly requires the of advanced tools from group representation theory. This is likely large part of the reason why automorphism based architectures such as [37] are not used more commonly practical applications. this paper we have shown that a simpler approach based on spectral graph theory, following the same underlying logic as the group theoretic approach but bypassing having enumerate all irreducible representations of the automorphism group, can lead to an architecture that is almost expressive. Our algorithm, called Schur Nets, easily generalizes to higher order activations, as well incorporating other types of side information such as vertex labels. practical setting, Schur Nets is easiest to deploy in conjunction with message passing framework like P-tensors that hides the complexities of the higher order message passing component. The empirical performance of Schur Nets on the ZINC 12K dataset is superiror to all other comparable (non-transformer based) architectures that we are aware
Given the similarity between the way we utilize the eigenspaces of the graph Laplacian and the so-called graph Fourier transform, our approach exposes heretofore unexplored connections between permutation equivariance and spectral GNNs such as [9, 22]. It also highlights the fact that while permutation equivariance is fundamental constraint on graph neural networks, the key building high performing, expressive GNNs is to reduce the size of the group that the network needs to be equivariant as much as possible, using whatever ind-infforntion we can employ, whether that be the adjacency matrix, vertex degrees something else.
Acknowledgements
We would like to thank Andrew Hands for many valuable pieces of advice and much practical assistance that he has given the experimental side of this project. We also gratefully acknowledge the Toyota Technological Institute of Chicago and the Data Science Institute at the University of Chicago for making their computational resources available for use, well as NSF MRI-1828629 for additional infrastructure that was used in the course this project.

---

References
[1] Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning to Represent Programs with Graphs. In International Conference Learning Representations (ICLR), 2018.
[2] Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[3] Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, and al. Relational Inductive Biases, Deep Learning, and Graph Networks. In arXiv: /806.01666011... 2018.
[4] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant Subgraph Aggregation Networks. In International Conference on Learning Representations (ICLR), 2022.
[5] Deyu Bo. Xiao Wang, Yang Liu, Yuan Fang, Yawen Li, and Chuan Shi. A Survey Spectral Graph Neural Networks. arXiv preprint arXiv:2302. 05630, 2023.
[6] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Liò, Guido Montufar, and Michael Bronstein. Weisfeiler and Lehman Go Cellular: CW Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[7] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pictro Lió, and Michael Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In International Conference Learning Representations (ICLR), 2021.
[8] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. In International Conference on Learning Representations (ICLR), 2020.
[9] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral Networks and Locally Connected Networks Graphs. In International Conference on Learning Representations (ICLR), 2014.
[10] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can Graph Neural Networks Count Substructures? In Advances Neural Information Processing Systems (NeurlPS), 2020.
[11] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Velickovic. Principal Neighbourhood Aggregation for Graph Nets. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[12] Pim de Haan, Taco S. Cohen, and Max Welling, Natural Graph Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[13] Nima Dehmamy, Albert-Lászlle Barabási, and Rose Yu. Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[14] Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, and Yixin Chen. Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler- Lehman. In Advances in Neural Information Processing Systems (NeurIPS), 2023.
[15] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2019.
[16] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical Inter-Message Passing for Learning on Molecular Graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
[17] Fabrizio Frasca, Beatrice Bevilacqua, Michael M. Bronstein, and Haggai Maron. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. Advances in Neural Information Processing Systems (NeurIPS), 2022.
[18] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry. International Conference on Machine Learning (ICML), 2017.
[19] Martin Grohe Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Cambridge University Press, 2017.
10

---

[20] Rafael Hommez-Bommarelli Jennifer N. Wei, David Duvenaud, José Miguel Hernnndez- Benjamín Sänchez-Lengelingg Dennis Sheberla, Jorge "guilera-Iparraguire Timothy D. Hirzel, Ryan P. Adams, and Alán Aspuru-Guzik. Automatic Chemical Design Using Data-Driven Continuous Representation of Molecules. ACS Central Science, 2018.
[21] Andrew R. Hands, Tianyi Sun, and Risi Kondor. P-Tensors:
General Framework for Higher
Order Message Passing in Subgraph Neural Networks. In Proceedings The 27th International Conference Artificial Intelligence and Statistics (AISTATS), 2024.
[22] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep Convolutional Networks on Graph- Structured Data. arXiv:
2015.
[23] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems (NeurIPS). 2020.
[24] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for Pre- Training Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2020.
[25] Sergey loffe and Christian Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In International Conference on Machine Learning (ICML), 2015.
[26] John J. Irwin, Khanh G. Tang, Jennifer Young, Chinzorig Dandarchuluun, Benjamin R. Wong, Munkhzul Khurelbaatar, Yurii S. Moroz, John Mayfield, and Roger A. Sayle. ZINC20-A Free Ultrlarge-Scae Chemical Database for Ligand Discovery. Journal of Chemical Information and Modeling, 2020.
[27] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations (ICLR), 2015.
[28] T. N. Kipf and M. Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR), 2017.
[29] Risi Kondor and Shubhendu Trivedi. On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups. In International Conference on Machine Learning (ICML), 2018.
[30] Andreas Loukas. How Hard is it to Distinguish Graphs with Graph Neural Networks? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[31] Haggai Maron, Heli
Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[32] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and Equivariant Graph Networks. In International Conference on Learning Representations (ICLR), 2019.
[33]
Christopher Morris, Nils M. Kriege. Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A Collection of Benchmark Datasets for Learning with Graphs. ICMI, Graph Representation Learning and Beyond (GRL++) Workhop, 2020.
[34] Christopher Morris, Martin Ritzert, Matthias Fey, William I.. 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 (AAAI), 2019.
[35] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation Ratios of Graph Neural Networks for Combinatorial Problems. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[36] Jean-Pierre Serre. Linear Representations of Finite Groups. Springer-Verlle 1977.
[37] Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-Ban -Bsed Graph Neural Nets. In Advances in Neural Information Processing Systems (NeurlPS), 2021.
[38] Erik Henning Thiede, Truong-Son Hy, and Risi Kondor. The General Theory of Permutation Equivariant Neural Networks and Higher Order Graph Variational Encoders. a3X99.2004.03990 2020.
[39] Boris Weisfeiler and Andrei Leman. The Reduction of a Graph a Canonical Form and the Algebra Which Appears Therein. Srachho--Tehhichhee Informatsiya, 1968.

---

[40] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2019.
[41] Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha Talukdar. HyperGCN: A New Method for Training Graph Convolutional Networks on Hypergraphs. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[42] Jiaxuan You, Jonathan
Rex Ying, and Jure Leskovec. Identity-Aware Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
[43] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R. Salakhutdinov, and Alexander Smola. Deep Sets. Advances Neural Information Processing Systems (NeurIPSS, 2017.
[44] Muhan Zhang and Pan Li. Nested Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[45] Ruochi Zhang, Yuesong Zou, and Jian Ma. Hyper-SAGNN: A Self-Attention Based Graph Neural Network for Hypergraphs. In International Conference on Learning Representations (ICLR), 2020.
[46] 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 (ICLR), 2022.
12

---

A Additional details
The purpose of the permutation map P; in Theorem is remap the tensor product space RdimmU; (x.oi,,))x... )x...Xxim((,, )xC into a canonical form that those dimensions that correspond to ij 1 are mapped to the first nı slots, those dimensions with iz = are mapped to the second n2 slots, and so on. Given the permutation т: {1, ..,... Æ} + {1,2,. 2,..... .................... ......,,,... k} that canonicalizes the indices in this way, Pi is just the corresponding permutation map. i.e.
Pi(r1 .....y .I @ xz) = Ix(1) @ ... I((k) 8 Tc.
B Proofs
Proof of Theorem 1. Let (ght, U; UU+U be the restriction of the action of G to Us. Since G fixes each U., the action of G on the full space decomposes in the form
g(u) Σ (ubu.)
UEU.
Now since multiplication by scalars commutes with linear maps,
p ((g(w)) Σ as ghe (ubv;) Σ sha, (luu));)) g(
g
for any E U and any E G.
Proof of Theorem 2. Each of the Vj subspaces is invariant, hence homothety on each is equivariant operation for the same reason as in Theorem 1. addition, since G acts the same way any pair of subspaces (V), Vj), any map of the form Sj ViVi that just a scaling is also equivariant. The composition of equivariant linear maps is an equivariant linear map, hence any map of the given form is equivariant.
Proof of Theorem 3. For any multi-index i, the subspace Im(M,, M. .... & M, & Ie) is invariant to permutations. Further after applying the permutation map Pt. all such subspaces of the same type n, the action of S5 all such subspaces will be the same. Hence directly apply Theorem to prove this theorem.
B.1 Alternative Proof for Corollary 1
Here we give a more direct proof for Corollary 1.
Proof. Without loss of generality, we assume Can = Cout = 1. Since the M,'s and A,'s are cigenspaces and eigenvectors of the Laplacian L. L MAM where M [M...... Mpl and A = )m,)
The neuron ns is linear transform Rm R" with ((T) E,M, TW, MVM"T. where V = diag(W: In,, ... W W,,,). Here the W,'s are just scalars and In, is an identity matrix of the size the corresponding eigenspace.
Given a permutation E S,, we want to show that dz T) = a de (T), which the definition of equivariance. Note that do actually depends since we'r re doing eigenvalue decomposition on the Laplacian of the subgraph transformed by a. This is the key to proving equivariance. We use to denote the identity permutation.
Now L P.LP7 M,MMT, where M, P.M, while the eigenvalues remain invariant after permutation and eigenspaces are transformed in the same manner as L. Thus,
( o T) M. P.T
PaMVM, P. P.T
= Pa (T)
13

---

which is the desired result.
The key to the proof is that the transform & depends an object transformed with permutation o, specifically, gruph Laplacian L. And all we need is that the object L is transformed equivariantly with We can also add side informatino such as node labels or degrees to further constrain the automorphism group and increase the number of distinct eigenvalues. One easy way to do that is set L' = L + V. where V diag(U1,"" (U1,-.. Um captures the node labels degrees, and build the Schur neuron ng from L'.
Remark 1.
C Related works
Higher order MPNNs have become popular research area in graph representation learning since the seminal work by [32], which characterized the space of equivariant map w.r.t. S, for k'th order tensors. The following works have mainly been divided into two streams, the one is based on k-Weisfeiler Leman test (L- test) [39, 19], for instances, [31] proposed k-order graph neural networks that is as powerful as k-WL test; [34] proposed k-GNN to approximate (or simulate) k-WL test; [14] further designed a (A, t)-FWL++ hierarchy that extends the k-WL test and implemented the corresponding neuron version. A common feature of these approaches is they all work on all k-tuples of vertices for k-th order neural networks and thus make their space and time complexity at least (.x²))
The other line of work is seeking ways to choose subgraphs in the graph, that are representative or contain important information, such as functional groups in a molecule. [7] chooses simplicial complex and [6] further extends this to any cell complex such as cycles. [21] incorporates any subgraph template and uses the equivariant maps defined [32] for local feature transform and devised high order message passing scheme between those subgraphs, called P-tensor. This is arguably the most general framework in this line of work. This line of work is kind of independent of the k-WL test since the k-WL test is aimed to distinguish any pair of non-isomorphic graphs while chosen subgraphs are meant to work in some specific regions with domain prior. It's possible to still compare this kind of network with the distinguishing power of k-WL test, for example, [6] shows if they include cycles of size at most l (including nodes and edges), their network are as powerful as WL test. However, such comparisons domain-specific approach. In our opinion, the ability to learn certain features (such as count cycles of certain sizes learn some function related to specific functional groups) might be better criterion. It'll be an interesting research direction to design suitable criteria for the expressive power of such higher order MPNNs in general.
not very meaningful to indicate the expressive power of such
Our work follows this line of work since we 'e choosing specific subgraphs to learn representation on. But we utilize the subgraph's 's automorphism group to devise more possible equivariant maps (none of the aforementioned methods are built on the automorphism group). The only other work to our knowledge that uses the automorphism group is Autobahn [37], which is the first to introduce equivariance to the automorphism group to GNNs. The difference between our work and lines twofold: (1) Autobahn theoretically introduces equivariant maps w.r.t. automorphism group via gen- eralized convolution and Cosets, which is another group theoretical approach to construct equivariant maps, while we'ne re using the decomposition irreps (2) More importantly, Autobahn didn't 't mention a practical approach to construct those equivariant maps explicitly, hindering the utilization of more diverse subgraphs. In their experiments, they only use cycles of length five and six and paths of length three to six and construct the equivariant maps potentially by hand. In contrast, we give a simple and efficient way to construct equivariant maps w.r.t. automorphism group by EVD, which is very general to be used by any subgraph. Though our approach doesn't 't give the full set of equivariant maps, experiments show improvement over the traditional approach where only equivariant maps w.r.t. S,, are used. We believe this algorithm, together with the group theoretical idea about decomposition Rm into stable subspaces and irreps are beneficial the research community.
There is a "third" type of higher order GNNs that called Subgraph GNN, which deviates from the original definition of higher order MPNNs but can still be considered as higher order network. In particular, node-based GNNs such as [44, 46, 4, 42, 17] associate each node with subgraph (by deleting the node, marking the node extracting the EGO-network and do MPNN on each subgraph,
14

---

where they get the resulting representation X E R that can be considered as 2nd order tensor representation on the original graph.
D Analysis of Schur layer
First of all, we notice that the equivariant map characterized in 1 (or 3) may not be the full set of equivariant maps w.r.t. Aulg. Because (1) In the decomposition of U Rm eigenspaces U1=11 @ eb...U, while Ug is stable subspaces, it might not be irreducible and finer decomposition may possible. In other words, there might be two irreps (isomorphic not) corresponding to the same eigenvalue. (2) The maps defined by I didn't It take into account the isomorphic subspaces corresponding to the same type of irrep, thus ignored the possible equivariant maps between Vj and Vj. So, it is of interest to find out how much the gap would be between our approach and the group theoretical approach. We first look at some examples in the first-order case (see table 4).
# of distinct Eigenvalues (Schur Layer)
(R))
Graph
Auls
Σ; Ki
irreps approach
6-cycle
De
4
4
4
5-cycle
Dr
3
4-cycle
D4
3
3-cycle
D3
2
2
2
5-star
S4
5
4-star
S3
5
3-path
S2
5
3
n-cliques
S
2
5-cycle
S2
6
20
6
with one branch
6-cycle
S₂
29
with one branch
Table 4: Examples on EVD approach vs group theoretical approach towards # of equivariant maps Auts- To calculate the decomposition of Rm into irreps, can calculate Kę (ølx)) where 6 and X is the character of the first-order action and ith irrep respectively, and (l) is inner product. Another quick approach is to use (á(r) En <xXu(a) and look some examples of determine what the Ką should be.
We note that for cycles in the graph case, there's no gap. However, when we add branches to the cycle to make the automorphism group smaller, the multiplicities of the irreps increase, c.g., in 5-cycle with one branch case, S₂ only have two I-dimensional irreps: trivial and sign representation of permutation, and the first-order action decompose to 4 copies of trivial and 2 copies of sign representation, gives in total 4 * + 2 * 20 possible equivariant maps. However, note that # of irreps (counting multiplicities given by Σ, Hs)) is equal to # of distinct eigenvalues, meaning that each eigenspace corresponds to an irreducible subspace and the decomposition of Rm provided by eigenspaces is indeed a decomposition to the irreps in all of the cases listed in the table. Therefore, the multiplicities are the key reason for the gap between our EVD approach and the group theoretical approach, since our EVD approach can't an capture the isomorphic property between subspaces. In principle, it is possible to find out which eigenspace is isomorphic to which, but in our current implementation. didn't 't take this into account because found out that only considering cycles is enough for a very good performance the datasets we used.
Generally, it's complicated to determine the gap between our EVD approach and the group theoretic approach, especially higher-order cases (where merely determining the K; 's is tricky), so we leave this into feature exploration.
E A brief overview about P-tensor framework
The P-tensor framework a framework for linear equivariant maps w.r.t. S,, both between the same subgraph and across different subgraphs. It is built on the equivariant maps characterized by [32].
15

---

Definition 1 (P-tensors), Let U be a finite set of atoms and D = (ei.....Td)) an ordered subset of U. We say that a k-th order tensor T E Rdxxxx.xxd xd is a k-th order permutation covariant tensor (or P-tensor for short) with reference domain D under reordering by Sa D it transforms
[T o Riddamndn Tr 1(6)).... (6a))
E.1 Message passing between P-tensors with the same reference domain
Consider the equivariant maps sending I on D to Tout on D. The space of equivariant maps w.r. Sm characterized by [32]:
Proposition 1. The space of linear maps & Radi Rakka that is equivariant to permalations T E Sa spanned by basis indexed by the purtitions of the set 21,2..... kn + k2).
Then the authors designed a straightforward way to write the maps explicitly. Specifically, for each partition of the set f1, k1 k2), there are three parts that determines the equivariant map: (1) summing over specific dimensions or diagonals of 7 (2) transferring 7hth to 7 by identifying indices of 7 with indices of 7 (3) broadcasting the result along certain dimensions of Tour, These three operations correspond to the three different types of sets that can occur in given partition P: (1) those that only involve the second 12 numbers, (2) those that involve mixture of the first i and 22 and (3) those only involve the first k1 numbers. The type (I) (3) corresponds to type (1) (3) of operations with the dimensions the sets.
For example, in the case 1 = k2 3, the P [[1,3) 3). (2,022233 5, 6). {4}} partition corresponds to (a)
summing T along its first dimension (corresponding to {4}) (b) transferring the diagonal along the second and third dimension of 7 to the second dimension of 7 (corresponding to {2, 5, 6)) (c) broadcasting the result along the diagonal of the first and third dimensions (corresponding (1.3). 3)). Explicitly, this gives the equivariant map:
Tour a.baa
Σ Trin
See table 5 for another example for kn k2 2 case.
P
P
[II,, (2), (3), [4)]
T
Thn
[12], (133,4)
1 T 7 in
c.d
(2,,
T Σ Tin
[11,2.3,, (4)1
Tout Σ T
(2,4, (3))
Tout Σ. TTmm
((1,2,4),
Tout ΣB b,a
(2.3, (4))
a.b E. Em
[(122)
Tou E. Tin
(14.31
Th Tin
[113))
T Tim
((1.3). (2,41)
Tout Σ. T
((.,4),
Tout Tim
[(1,233,4))
Tout Tin
([1,2,344)
T T
Table The ((4) = 15 possible partitions of the equivariant linear maps ó R - kkxk
(1,2,3,4) and the corresponding permutation
E.2 Message passing between P-tensors with the different reference domains
If T'i has reference domain D, and Tou has D2, with D * D2 and D, n nD2 & 0. We could have more options corresponding to summing either over the intersection or over Di, and broadcasting either over the intersection or over D2. So the number of maps corresponging to partition of type (p1, P2.Pa) Ps) is tPa) Let D2 n D2 = d", the previous example would have the following maps in
D2 # D2 case:
Dd
Tin b,b,b
a. a otherwise,
(a (l....,, ce (L....,
Dd' Tin
b,b b dd otherwise,
Touut
(a deh CE (1....,d"))
0
16

---

Eo=1 T
a.b otherwise,
(a (L....,.. CE (L....,d1))
0
Tin c==
b b d otherwise,
T a,b,a
o,b,b
(1..,...., d2). CE (f.
F Group Representation Theory Background
Here, we explain detail the decomposition of k-th order permutation to irreps Sm. Proposition 2. Let Px. X F m the irreps of Sm. U Rm a E Sm act on in the manner of equation 7, and suppose this action contains irteps . Pxp with multiplicities K1....y Kp have:
Ny
U U1 B Up U. D V!
where the first part gives the canonical decomposition of U and the second part further decompose each Us into irreducible subspaces, where V² correspond to ph. In matrix form,
Px (xx(0) (o)
0
Ph
p(k) M
M for all Sm
(x)
where M the orthogonal transformation for basis and we abuse px, (σ) to denote also the matrix of i-th irrep in the decomposition.
If take closer look at M, can find that since ( is under the standard basis of Rm* thus M is just the orthonormal basis of each Ug (thus each V combined together, we denote M = (M....., Mp) with M, a * x (dxa * k,) dimensional matrix, where d,, the degree of px Therefore, T becomes:
Px (a)
O
M
Pha
M
p(K) [M1, M2...... Mp]
(10)
:
Pap (o)
M
The part (1) is generalized Fourier transform of T to its Fourier components (coordinates under
MfT M
B
B2
the orthonormal basis) f
and the part (2) the irreps PAr....,PP PAp act
: M
Bp
(x.
independently on I with each component B, +
Bi. Note that there're iy
(o)
multiple of Px, act the same on components of B; correspond to V2, with slight abuse notation, we can think B, E Rds, x*; (instead of R(ds, *=:)x! and write this map as Px. (a) the fact that the map by irrep px; independently on each column of B, allow to identify directly set of equivariant maps by multiplying B, with matrix W. E R* to the right, and using associativity of matrix multiplication: Px. (B)(B, W;) (px, (.) This gives total of Σ, xē independent cquivariant maps, as stated in the main text. The last part of the above equation maps Fourier components to their original space. In short, we can write:
P = Σ (.p M.T
(11)
B,
17

---

with the abuse of notation to rearrange elements in B; mentioned above.
Then present detailed version of theorem in the main text.
Theorem 4 (Necessary and sufficient condition for equivariant map). Let G be finite group acting on a vector space U by the linear action {g : - gyeG and assume the action can be decomposed into irress Pl..--:Pp with multipiictties K1, ; Kip and degree dę:
NA
U = U U2 U U.
V
Then o ::U. + U is an equivariant map w.r.t. this group action if and only if & is of the form:
Φ(v) = Σ (- for EVj
(12)
8'
for some fixed set of coefficient {a) : [1, [1.... pl.J.j' E E (I,....,,,]]
In matrix form, suppose the matrix of is Rg under basis (es) and diem(U) = n,, and it decompose into:
p1(g)
(2(g)
Rg M
M
(13)
0
Po(g)
= Σ M.
(14)
Then o: R" R" equivariant if and only if it is of the form:
Wi
0
0
W2
0
6(T) TM
(15)
W
Σ M, M,T,T,
(16)
where I E R", W₁ E RR.xx, is the fixed coefficients and B, rearrange to Rd.xx. when needed. The coefficients j's corresponds to (We),.''
Proof. Sufficiency: firstly, af T3- (v) is equivariant by definition of isomorphism map. And the equivariance of á follows from the fact that sum of equivariant maps are equivariant.
Necessity: consider on Vj and let W Im(Øly;) the image of on Vj. Since 6og g & and g(v) E Vj for any E Vj, we have g(ő(v)) = ((g(v)) W, so W is stable under the action. Thus we can decompose W into irreducible spaces W W1 @... W.. Apply this decomposition to d(v) for u E Vj, we get:
(v)=)((1)) +op()) where dx(v) W;
In other words dx- Projx ó where is the projection of W onto Wい. (uniquely defined by the direct sum decomposition). Then Φx V/j W. and du og a Φx. By Schur's lemma [36], for Φ * 0, we must have Wj isomorphic to Ví and dh(()) = OuTy; w, (v). Since only VJ is isomorphic to V7, we have W₁- = Vt and @u (v) = (T)) where (w) is the isomorphic map sending V to Vg. Thus Φ(v) Σx (v( Σn (T)() for VJ.
Finally, by linearity and U Dz, Vj the only possible equivariant function Φ U - U is given by 12.
Similar discussions could be found in Section 4 of [38], but without proof for necessity.
18

---

Connection to matrix form: first note that the isomorphism 7J V3 - Vj is given by:
Ty (u,,)) = u where {u),r, = -....... ,.....,, and ful 1.... K.) are orthonormal basis for Vj and V respec- tively such that the action of is associated with matrix p=(g)- Therefore,
H(ug,) = E Co
8
= ((ss(())
Thus the matrix of under basis (u/ P.j.
1...., Kg, I.....d.) is
Wi
W1 0
0
2
W2
0
(which the same as
with B, rear-
:
W
W
range to Rd.xke) and M is just the matrix to transform standard basis (e:) to basis (u
G Ways to Use Schur Neuron
While Schur neuron can be viewed as a generic transform on any subgraph's 's first-order activation, we provide some thoughts and possibilities instantiate it.
our experiment, we primarily view Schur neuron as way to expand the feature subgraph. can be viewed analogue CNN's convolution filter and it's indeed constrained version of spectral convolution filter [5] on the subgraph. In light of this, we call number of channels of Schur neuron how many times expand the output feature versus the input feature.
Besides, we observe that the linear equivariant map described [32] is a special case of Schur neuron's map. The two possible linear map in [32] is (1) identity map. corresponding to take all weights W; = (2) T + E,T.1, where 1l is all ones vector, corresponding set W1 1, and W; = 0 for i + 1 since I is eigenvector of any graph Laplacian with eigenvalue 0. Consequently, we suggest to keep the two basic important linear maps and augment them with Schur neuron. Empirically we verified this by experiment only vary the number of channels. In figure 1, we see that further increase the number of channels beyond 4 wouldn't 't give us performance gain since cycle and only has 3 and 4 distinct cigenvalues respectively.
Furthermore, we suggest that number of channels of Schur neuron be proportional or approximately equal to number of distinct eigenvalues of the subgraph it attach to. This is because the later is the number of independent linear maps for Schur neuron.
330
432
Figure 1: A study num of channels in Schur layer. Cycle 5 and are included.
Additonally, we're wondering if we can use Schur layer place of ML.P' to provide a local structure aware transform to subgraph activations. Therefore, we tried to replace the 2-layer MLP with 2-layer
19

---

Schur layer in the original Linmaps architecture. But it turns out this use case wasn't t as effective as the use as learning new feature. Possibly because Schur layer learns feature itself while MLP transform the learned feature to some desired space.
Methods
Validation MAE
Linmaps
0.087
Schur layer
0.081
(in place of MLP)
Schur layer
0.076
(as learning new feature)
Table 6: Comparison about two use cases of Schur layer. Experiment on ZINC-12K.
Finally, regarding flexibility discussed 5 5.2, in table 7, that adding cycles with branches could provide the Schur Net with more detailed topological information, thus improving the performance. And the code for adding this actually only requires single definition of those templates without modification to the neural network.
Model
Validation MAE
Schur-Net on 5,6 cycles(baseline Schur-Net on 5,6 cycles with up to three branches
0.113 + 0.008
0.105 0.001
Table 7: Flexibility of Schur layer. Experiments on ZINC-12k dataset. All other settings the same. smaller network than previous experiments was used.
H More experiment results
We first start with some molecular datasets in TUdataset [33], which is small but commonly used benchmark for GNN. In table 8, we see that Schur layer consistently improves over Linmaps in various bioinformatics and molecule datasets.
Dataset
Linmaps
Schur Layer
Proteins
74.7 3.8
75.4 4.8
MUTAG
89.9 + 5.5
90.94 + 4.7
PTC_MP
61.1 + 6.9
64.6 + 5.9
NCII
82.1 1.8
82.7 1.9
Table 8: Comparison of Limmaps and Schur Layer performance on TUdatasets. Numbers are binary
classification accuracy.
In table 9, we compare the runtime of our Schur layer and Linmaps, which shows the extra compu- tational cost of Schur layer wasn't significant while being able to use more equivariant maps and achieving better accuracy.
Dataset
Linmaps
Schur Layer
Zine- 12k
25.4s
27.6s
NCI1
9.5s
11.5s
Table 9: Runtime per epoch with hyper-params num num_layers 4, rep_dim- = 128, dropout = 0.0, batch_size sizeessieee 256, num of channels 4, cycle_siue sizes 3,4,5,6,7,8. This shows Schur Layer didn't add much computational costs to Linmaps while being more expressive.
Another ablation study is perform on ZINC-12K dataset. In table 10, we see that Schur layer outperforms Linmaps when certain cycle sizes are considered, especially when only cycles and chosen subgraphs in the neural network.
20

---

Layer
cycle size (5.6)
cycle size [3,4,5,6]
Linmaps (baseline)
0.139 = 0.007
0.103 = 0.011
Schur layer
0.100 = 0.009
Table 10: Comparison between Schur Layer and Linmaps with different of cycles chosen.
Experiments on ZINC-12K dataset and all scores are test MAE.
I Architecture and experiment details
In designing of our architecture, we design a message passing scheme similar to [21] and add Schur layer to each of the convolution layers. A visualization of our architecture can be found in Figure 2. In each convolution layer, we maintain Oth-order node representation (hg E R(lV=ddmm) and edge representation (he E R Edemm where we assume the input graph G = (V, E). We further maintain where Dj is cycle of length k and o₁ is
1storrder representation on cycles (hp, E R( the number of such cycle in G. We did message passing between node and edge representation the same as CIN [6]. The edge and cycle pass message with each other by tranfer maps described by [21] and then the incoming message cycles well the original cycle representation is transformed by Schur layer. When updating the edge representation and cycle representation, we combine the original representation with the incomming message by either concatenation e-add described in GIN [40] and feed it into an MLP to get new representations.
Aggregate peripheral branching structure into cyde
But we also have SchurLayers
(h OP)
Or.
(h,)
SchurLayer
12 As (h2)
SchurLayer peripheral features architecture
An example illustration of one layer of our model architecture. For an input graph, we first execute the standard node and edge level message passing and lift up the model to higher-order by forming higher-ordes representations on specific template graphs. In this example, we learned the representation Naphthalene. To further decouple its information, we may apply the SchurLayer on the template graphs that would potentially provide us insight about the graph. In this example, the 6 cycle, star graph. and path graph all applying SchuLayer to learn the features locally. Through our architecture design, we can also incorporate the peripheral information. Automorphism group then helps us discover distinct key features such non-symmetries, and pass these aggregated features into the next layer of the architecture.
Figure 2:
21

---

Hyperparameterrs For experiments on ZINC-I2K and OGB-HIV, we tune representation dimension in (32, 64, 128). and experiment on cycles up length 18. In the best-performing model, we use representation dimension 128 and cycle lengths from 3 to 8 and number-of-lay -layerrsss is always 4. For Schur layer, we tuned number of channels from it is used as an augmentation to Liumaps. For MIPs, we either use 2 to 3 layers depending on how dense the input's information is. We always use a batchnorm [25] after the Linear layer and then do ReLu activation. For training hyperparameters, we an init learning rate of 0.01 and use ReduceLROnPlateauu scheduler in PyTorch with patience of 10 or 30. We use Adam optimizer [27] for all trainings. We train for 500 or 1000 epochs depending the models have representation dimension 32, so is trained to only 500 epochs. All other models trained 1000 epochs. A batch size of 256 is used for all models. All results are run at least three times to calculate the standard deviation.
and found 2,4 are a suitable choice when
model size. In particular, in table 10,
For experiments on TUdataset (table 8), we chose set of hyper-params by intuition (we didn't 't tune demonstrate the effectiveness of Schur layer and compare Schur
them because this experiment layer with Linmaps under the same experiment setting. we don't It aim to compare with Sota on this experiment). Hyper-params for both Schur Layer and Linmaps: num layers 4, rep_ rep_dim- = 32,64, dropout = 0.5, batch_size 128128, Ir 0.01, num of channels (2,4), cycle sizes = 3,4,5,6. We're We're training with StepLR scheduler where reduce Ir to 1/2 after every 50 epochs, with a total of 300 epochs. The hyperparams weren't 't tuned, we just chose smaller value for smaller dataset and bigger value for bigger datasets by rule-of-thumb. Linmaps is implemented on our own according to the description of P-tensor, then Schur Layer replaces Linmaps operation by Schur operation. We follow the evaluation strategy specified in [40].
Used Compute Resources Experiments are all
Tesla L4 from PyTorch Lightning
Workspace and one NVIDIA RTX 4090. The code is implemented in Py PoTch.. For the running time, on the ZINC-12K 12 dataset, it takes around 8.53 + 1.2 hours to finish training for 1000 epochs with layers and 128 dimension representation on an NVIDIA RTX 4090. We're running on a desktop with Ryzen 7900 CPU and 64GB of RAM.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the paper relate to specific properties of message passing algorithms. The claims that we make about our own algorithm are accurate.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: We have a section on limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: For each Lemma and Theorem in the paper we provide a proof.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We document our experiments in detail, including the dataset, the architecture and parameters.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We have included the link to github repository containing all the files needed to reproduce the experiments.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Yes, we give all these details in the Appendix.
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: For each of our results on the benchmarks datasets we provide the standard deviation of the performance.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time exccution) needed to reproduce the experiments?
Answer: [Yes]
23

---

Justification: We provide this information in the Appendix.
9. Code Of Ethies
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpa: : http::pp.....pbiiiii/cccccccciae
Answer: [Yes]
Justification: We have reviewed the code of ethics and our research conforms to it.
Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: Our work is foundational/hheorrtiaall in nature and we not foresee it having any direct social impacts. Indirectly, it could have impact because higher order automorphism- equivariant could be used drug discovery, for example. Applications with negative social impacts also possible, but a little more difficult to pinpoint. Space limitations prevented us from discussing this topic in more detail.
11. Safeguards
Does the paper deseribe 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: The model itself does not pose such a risk.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: We provide citation for every baseline model and benchmark dataset that use. All assets were used in a way that conforms to their published licenses.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification: We do provide new assets.
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 details about compensation (if any)?
Answer: [NA].
Justification: This research did not involve crowdsourcing or human subjects research.
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA].
Justification: This research did not involve crowdsourcing human subjects research.
24


Reviews:
[{"review_id": "Un1cVq7o4M", "reviewer": "Reviewer_EFuW", "summary": "This paper proposes to define permutation equivariant functions on subgraphs via spectral theory as opposed to the more traditional 'equivalence classes' of permutations [Maron et al.] The paper lays out the theory behind producing equivariant maps via the eigen decomposition of the subgraph's Laplacian and the permutation invariance of the eigenspaces, which along with standard arguments from representation theory produces equivariant functions, although not all of them. The validity and robustness of the approach is further exemplified in the experiments on benchmark tasks and datasets, comparing this approach to [Maron et al.]\n\n[Maron et al.] Maron et al., Invariant and Equivariant Graph Networks NeurIPS 2019", "questions": "1. I read the background but I still don't understand what this means in line 337, \"In table 1, we see that Schur layer outperforms Linmaps under different cycles sizes, especially when only cycle 5 and 6 are considered. \" Do you choose as your neurons as only cycles of certain size and then computing the equivariant layers in your proposed spectral approach?", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a novel method that can significantly reduce the exponential search space of permutation equivariant layers between overlapping subgraphs in the P-tensor formalism.\n2. This can be extended to Subgraph GNNs and other high order networks\n3. Some experimental verification of good performance", "weaknesses": "1. The background is not clearly laid out, especially that of the P-tensor formalism. Without referencing back to these papers it wasn't possible for me to understand this manuscript. I suggest to add background in the supplementary material. \n\n2. Other than the spectral convolution being permutation equivariant, there are no theoretical guarantees on its expressivity (in terms of Weisfeiler Leman or Subgraph GNNs.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments and questions. \n\nQUESTION 1. We experimented with various architectures, but in the final experiments we just used subgraph-layers corresponding \nto cycles, edges and vertices. The cycles were of size 5 and 6 corresponding to the aromatic rings \nthat commonly occur in molecules. The experiments show that applying the Schur-layer idea to just the cycles alone \nconsistently improves performance over the baseline P-tensors model. The P-tensor model is the natural baseline here \nhere since it is currently the state-of-the art model amongst subgraph-based higher order GNNs. The experiments (both those that are in the original paper and those that we have done since) show that automorphism-group aware convolutions with Schur layers within subgraphs robustly improve performance over the more traditional local convolutions that ignore the automorphism group of the subgraphs. \n\nQUESTION 2. There might be a slight misunderstanding here. The naive approach would not involve an exponential \nnumber of layers. It would involve first finding the automorphism group of each subgraph (which is a \ncomplicated combinatorial problem but could be done in precomputation) then symmetrizing over the \nautomorphism group in each layer either by (a) enumerating each of its elements or (b) using the representation theory of \nthe specific group. Technically, both finding the automorphism group and enumerating over its elements is \nNP-hard in the size of the subgraph. The real problem is not just the computational cost but how \ncomplicated considering all potential automorphism groups, generating the irreducible representations, etc. \nwould be. We are not aware of any higher order GNN paper that seriously proposed doing this. Therefore, we \ncannot directly compare the running time of our model with this. What our paper shows is that all of \nthis can be bypassed with a simple spectral graph theory \"trick\".\n\nA huge benefit of our approach is its flexibility. We can easily change to other subgraphs just by changing \nthe subgraph template, the Laplacian etc are computed automatically, and there is no need to search for \nthe automorphism group, somehow derive its irreducible representations, and so on, neither there is a need to \nsum over all group elements, which would have $O(m!)$ complexity in principle, where $m$ is the size of the \nsubgraph.\n\nIn practical terms, as we also explain in our response to Reviewer fyBT, the biggest computational bottleneck \nin higher order GNNs is orchestrating the message passing process in parallel across all subgraphs in a given \nlayer, given that the subgraphs overlap with each other in different ways. To facilitate this we had to write \na separate library complete with specialized CUDA kernels and a considerable amount of engineering. \nIn practice, using this library, first order message passing, like in our experiments, is only 3-4 times \nslower than conventional GNNs. The actual Schur layers only make up a small fraction of the run time. \nIf we summed over all elements of the automorphism group, however, we estimate that the automorphism-group equivariant \nlayers would be about 100 times slower, but for the reasons cited above such an approach would be very clunky \nto implement anyway.\n\nQUESTION 3. There might be another slight point of confusion here. First of all, \"Linmaps\" is not the same as [Maron et al]'s original model, since all the layers in [Maron et al.]'s model operate on the entire graph, whereas we consider subgraph based models where the Linmaps happen at the level of subgraphs. The reason that [Maron et al.] is cited is that we apply the same linear transformations at each subgraph as they did at the level of the entire graph and they were the first to enumerate all such possible linear transformations.\n\nSecondly, the problem with \"Linmaps\" (as implemented in for example P-tensors) is not that they are expensive but that \nthey are not expressive enough because they fail to take into account the automorphism group of the subgraph. Schur layers are a plug-in replacement for Linmaps that can take into account the automorphism group, which is basically a form of equivariant side information (see Sections 3 and 4). Fortunately, (see response to fyBT), using to the spectral graph theory trick, the added computational cost is minimal and in practice pales in comparison to the cost of using higher order message passing in the first place (please see the response to fyBT for the theoretical complexity). In summary, we have a more expressive model and achieve a consistent improvement over other higher order models like P-tensors without any appreciable extra computational cost.   \n\nThe reason we did not manage to get results on the full ZINC dataset is primarily a memory issue. \nAs we explain, to achieve speed, we need to cache a variety of control data structures on the GPU and on the \nfull ZINC dataset we simply ran out of memory. We are presently working on removing this limitation from the software by improving the engineering of the backend.\n\nFURTHER COMMENTS. \n\n- We appreciate your comment about the paper not being self-contained because it doesn't explain the mechanics of higher order message passing, especially since this is a relatively new formalism. In the main paper we just wanted to concentrate on what is novel, which is the Schur layer. We will add background information on P-tensors, etc. to the appendix. \n\n- See the global rebuttal for further results on the performance boost of Schur layers, unfortunately these only came after the deadline.\n\n- Thank you for bringing [Feng et al.] to our attention, we were not aware of it and the results on ZINC 12K are very impressive! One fundamental difference is that theirs is a fundamentally 2nd order model. While we have worked out the theory of higher order Schur layers we have not used them in our experiments. This paper gives a strong motivation to explore 2nd order Schur layers.", "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": "ZFkFZxyQqi", "reviewer": "Reviewer_uFzV", "summary": "This paper introduces Schur Net, an architecture designed to attain subgraph equivariance without fully determining the automorphism group. Utilizing spectral graph theory, Schur layers incorporate equivariant side-information from local structures to improve expressiveness. The authors have confirmed Schur Net's effectiveness through experiments conducted on the ZINC dataset.", "questions": "How were Schur layers implemented in the experiments? Was equation (8) simply applied to the features of the subgraphs?", "limitations": "The limitations are outlined in Section 6, where the authors recognize the limited expressiveness of Schur Nets, the narrow range of experiments conducted, and the use of first-order activations.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "- Efficiency. The proposed Schur Nets attain subgraph equivariance without the necessity to identify the full automorphism group of the subgraph, rendering it more efficient than the group theoretic approach.\n- Theory. The authors have demonstrated the first-order permutation equivariance of Schur layers and have extended this to include higher-order permutation equivariance.\n- Experiments. Schur Nets have shown impressive performance on the ZINC dataset.", "weaknesses": "- Presentation. This paper suffers from numerous spelling and grammar errors, as well as incorrect citations. The authors are advised to carefully proofread their work to amend these mistakes. Additionally, the theoretical background part is challenging to comprehend. The authors should work to simplify this part, incorporating only the necessary parts for the main results in the text and elaborating details in the appendix.\n- Theory. The authors have indicated the use of only first-order activations; thus, it appears that only Corollary 1 is applied as the form of Schur Nets in the experiments. If this is the case, including Theorem 3 in the main text is unnecessary. The outcomes of Corollary 1 seem trivial, offering limited contribution.\n- Expressiveness. Schur layers, as the paper admits, cannot express all equivariant linear maps, which constrains their expressiveness. The conclusion asserts that their method is \"almost as expressive\" as the group theoretic approach without providing supporting theorems. Furthermore, the paper lacks a thorough discussion on the precise expressiveness of Schur Nets and how they compare to other models.\n- Missing Related Works. The absence of a related works section hinders the reader's ability to compare this study with prior research. The authors should introduce a section on related works and highlight the novelty of their study in comparison.\n- Experiments. The scope of the experiments is too narrow, being limited to the ZINC dataset without a robust set of baseline models for comparison.\n\nDespite the paper's subpar presentation, I acknowledge that my understanding may be flawed, and I am receptive to the authors' clarifications. Nevertheless, I urge the authors to enhance the paper's clarity and accessibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and several suggestions that are very much on point.\n\nQUESTION 1. Yes, in our experiments we used for order Schur layers, which just use equation 8. What we like about our approach is that it bypasses all the group theory and reduces to something so simple. The rest of the network however, which \ninvolves message passing between different subgraphs is technically quite complicated because \nit has to account for how many vertices any pair of subgraphs have in common etc., as it is \ngenerally the case in higher order GNNs. In the main body of the paper we decided to focus only on Schur layers, because that is the novelty relative to other higher order message passing papers.  \n\nMaybe we should emphasize that what gives our architecture its power is the combination of Schur layers with higher order message passing. Schur layers on their own, if they could only communicate via scalars, would not give very good performance. Conversely, higher order message passing on its own has already been shown to give state-of-the-art results, but we show (see also our more recent experiments mentioned in the global rebuttal) that take the automorphism group into account with Schur layers consistenltly improves performance further.\n\nFURTHER COMMENTS\n\nThank you for pointing out the need to proofread the paper and increase the clarity of some sections. It \nis also a good idea to add a \"Related works\" section, the reason we decided to cite the literature inline \nwas mostly to save space, but if the paper gets accepted, the extra page available in the camera ready \nversion would allow us to add a separate section for this purpose.\n\n- Theory. While equation 8 is simple, we beg to differ about it being trivial. Since the early days of \nGNNs, researchers have proposed building GNNs based on the \"graph Fourier transform\", i.e., some kind \nof expansions of functions in the eigenvectors of the Laplacian. However these architectures were usually \nmotivated by an analogy with convolution in Euclidean space. Somewhat independently, people studied \nGNNs from the point of view of equivariance alone and proposed corresponding architectures.\n\nCorollary 1 and Theorem 3 bring these two threads of work together, and show that equivariance to the \nautomorphism group (of subgraphs), which seems like a complicated algebraic issue, can in fact be enforced \nvia the Laplacian. The proof not only shows that this approach is equivariant but also why it is \nequivariant: because the eigenspaces of the Laplacian MUST transform independently under permutations. \nThe only case that the spectral approach is weaker than a fully group theoretical approach (which to our \nknowledge has never been implemented) is when some of the eigenespaces further split into smaller \ninvariant subspaces, i.e., if some of the eigenvalues of the Laplacian \"accidentally\" coincide. \nThis gives a whole new interpretation to spectral GNNs and suggests that the reason they could achive \nrelatively good performance was maybe not so much the analogy with convolution but simply that they \ncould take the automorphism of the group into account. Of course the actual setting in our case is different \nbecause we apply Schur layers at the subgraph level rather than at the level of the whole graph.\n\nIn summary, the reason that we included the theoretical results, including the proofs in the main body of the paper in full detail is that we think they are of independent importance. The proofs themselves shed light on a new connection between spectral graph theory and equivariance. Potentially this could be exploited in other settings as well. Further, it can be the basis of theoretical studies of expressivity (see below). \n\n- Limitations of expressiveness. We mainly mention the fact that Schur layers cannot necessarily \naccount for all equivariant linear maps because we think that studying in what cases they can or cannot \nis an interesting theoretical research question. As mentioned above the \"gap\" only arises if some of the \neigenvalues of the Laplacian coincide, while the corresponding subspaces are not, in fact, irreducible invariant \nspaces of the action of the automorphism group. We know from the literature on e.g. graph isomorphism that \nin the typical case this does not happen: unless there is some specific symmetry involved, the eigenvalues \nof moderate to large graphs are typically distinct. In fact, for most graphs they are sufficient to \ndistinguish between non-isomorphic graphs. So studying this gap comes down to studying the \"special\" \ngraphs that defeat the Schur layers and possibly there is an interesting connection to graph isomorphism. \nHowever, we felt that this would go beyond the scope of the present paper.\n\n- Regarding further experiments please see the \"global rebuttal\".", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7zXBZccHxl", "reviewer": "Reviewer_fYBT", "summary": "This paper introduces Schur layers, a novel approach in graph neural networks (GNNs) that enhances expressive power by leveraging spectral graph theory. Traditional GNNs struggle with capturing complex local graph structures due to their reliance on full permutation equivariance, which is overly restrictive and computationally intensive. Schur layers address this issue by computing basis functions directly from the graph Laplacian, circumventing the need for explicit enumeration of automorphism groups. This method is shown to significantly improve GNN performance, particularly in scenarios like molecular data analysis where local subgraph structures (e.g., cycles) are crucial.", "questions": "1. How does the computational complexity of Schur layers compare to traditional GNN approaches in terms of training time and memory usage?\n\n2. How sensitive are the performance gains of Schur layers to different types of molecular datasets beyond the benchmarks used in the paper, and how would they perform in varied experiments using larger datasets such as OGB datasets and different tasks like link prediction to validate the model's versatility and resilience?", "limitations": "The authors have addressed several limitations, such as the spectral approach not ensuring the finest decomposition into invariant subspaces, potentially limiting the generality of automorphism-equivariant linear maps and the theoretical expressivity gap this might cause. However, a more detailed discussion of the method's limitations in terms of computational overhead and potential impact on large-scale graph datasets would be beneficial.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. This paper makes a significant contribution by introducing Schur layers, which offer a novel approach to enhancing the expressive power of GNNs through higher order message passing.\n\n2. The theoretical framework and mathematical rigor underpinning Schur layers are robust and well-explained.", "weaknesses": "1. Experimental Evaluation: Limited empirical evaluation on diverse datasets and benchmarks undermines broader applicability and comparison with existing methods.\n\n2. Contextualization: The paper could better situate its contributions within the broader landscape of GNN research, particularly in comparison with other higher order message passing techniques.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "QUESTION1 In short: it is not the Schur layers themselves that make this architecture more expensive than \nclassical GNNs, but rather the higher order message passing itself (like in P-tensors). \nThe natural thing to compare Schur-layers to are the vanilla \"linmaps\" operations. \nIn the case of a subgraph with $m$ nodes represented with a 1st order permutation equivariant tensor with \n$c$ channels (i.e., $X \\in R^{m*c}$) the cost of the Linmaps operation followed by a linear layer mixing \nthe channels is $O(mc+mc^2)$, whereas the cost of the Schur Layer would be $O(m^2 c+ mc^2)$. \nSince the number of channels is typically much larger than the size of the subgraph, \nthese are essentially the same.\n\nIn general, higher order GNNs are more expensive because (a) there are potentially many more overlapping \nsubgraphs than vertices (b) in the case of k'th order message passing between subgraphs of size m, \nthe size of the messages scales with $m^k$ (c) the way that each pair of subgraphs communicates depends \non exactly how many vertices and which vertices they overlap in, so the communication protocol cannot be \nreduced to a simple gather/scatter operation of the type that PyTorch Geometric performs. \nSince the subgraphs used in practice are still relatively small (think $m=6$) it is really the last point \nthat constrains speed. To get around it we spent months architecting a C++/CUDA based higher order \nmessage passing library with which we could run our experiments only 3-4 times slower than conventional GNNs. \nUnfortunately we can't give a pointer to this library without jeopardizing anonymity. \n\nAs for memory, this is again a general higher order GNN issue. Instead of just storing a $c$ element vector \nat each vertex, we now store $m\\times c$ matrices of $m\\times m\\times c$ tensors. For the types of small \nmolecules datasets that we mostly experimented with this is still not an issue. The practical issue  is that \nefficient higher order message passing on GPUs involves precomputing various control data structures and for \nlarge datasets we can't store all of these in the GPU's RAM, while moving information back and forth between \nthe GPU and system memory is slow.\n\nQUESTION 2. We did some more experiments on TUdatasets and OGB-hiv datasets. \nResults are attached in general rebuttal. We observe consistent improvement by just adding Schur layer \n(replacing Linmaps) which shows the robustness of performance gain. Since Schur layers are strictly more expressive than layers which cannot take the local automorphism group into account (as a form of side-information), it makes sense that they should boost performance but it is reassurring to see that this is indeed consistently the case. \n\nOn a more general level, higher order GNNs, and Schur nets are really not just a specific architecture but a class of \narchitectures -- in particular the theory leaves open the question of how the subgraphs are selected and which subgraphs should \ncommunicate with which others. Implicit in your question is whether these choices should change when we \nmove to different types of datasets or we move to a different task, e.g. link prediction. This is a very valid question, but we think it cannot be answered in just one paper. It will take the community some time to fully explore the vast design space of higher order networks. One thing that we are specifically working on is finding out whether in chemistry datasets including subgraphs corresponding to actual functional groups is helpful or not.  \n\nCOMMENTS. Thank you for appreciating that this paper is not just about a specific design variation on GNNs, \nbut a general connection between spectral graph theory and automorphism-group equivariance, which, to the best of our knowledge, has not appeared in the literature previously. Automorphism group equivariance is important, but there have been few papers that explicitly exploited it in GNNs. Our hope is that the theory outlined in this paper will make it a little less daunting to \nincorporate automorpshism group equivariance in GNNs.", "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": "TRtwJBNRWx", "reviewer": "Reviewer_uvzr", "summary": "This paper proposes Schur layers. Schur layers are meant to be used in higher-order MPNNs and are based on respecting local automorphism equivariance, however without the need for explicitly computing all automorphisms. In experiments, this method achieves state-of-the-art results on ZINC.", "questions": "- **(Q1)** What is the (intuitive) meaning behind: Theorem 1, Theorem 2 and Theorem 3?\n- **(Q2)** As far as I understand it Schur Layers are equivariant under the automorphism. Does that mean that there is some limit to their expressivity? Otherwise, you would be solving the NP-hard automorphism problem?\n\n\n## Miscellaneous\n- **(M1)** In my opinion, Table 5 is important enough to your narrative to warrant being in the main paper.\n- **(M2)** Missing citation in line 186.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- **(S1 - Significance)** Schur Layer are a general  architecture and can thus be used in a lot of higher-order architecture. This means that (theoretically) interesting properties of Schur Layers can be used to improve many other architectures\n\n- **(S2 - Significance)** In experiments on the ZINC dataset, SchurNets seem to consistently outperform other methods.\n\n- **(S3 - Novelty)** The approach does seem to be entirely novel, albeit based on some well-known mathematics.\n\n- **(S4 - Clarity & Quality)** Sections 1 and 2 are very well written. Especially Section 2 which introduces MPNNs based on the way the authors understand equivariance presents an extremely interesting way of thinking about GNNs.", "weaknesses": "- **(1 - Clarity)** The theorems are difficult to understand and no intuitive explanation is given. To me it is not clear what the theoretical contributions of this paper mean.\n- **(W2 - Significance)** It seems to me, as if the theoretical contributions are quite small. However, I am unable to really verify this due to (W1).\n- **(W3)** The paper is not reproducible as the code is not supplied (“ We will also make our code publicly accessible if the paper get accepted”).\n- **(W4 - Quality)** The experiments are lacking:\n\t- **(W4.1)** All experiments are performed on a single dataset (ZINC12k). This dataset in particular has been used in a lot of GNN papers and by now the community is probably overfitting to this specific dataset.\n\t- **(W4.2)** The advantages of SchurNet are small often only making a difference in the third digit of the MAE (for example in Table 3 the difference between the best SchurNet achieves 0.064 \\pm 0.004 and a higher order MPNN $0.071 \\pm 0.02$, that is a difference of 0.007).\n\t- **(W 4.3)** Replacing layers in higher-order MPNNs with Schur-Layers is in my opinion the most exciting application of this approach. Unfortunately, the authors only experiment with this for a single model ($P$-tensors).\n\n\nOverall, I think that SchurNets could be an interesting and useful method to be used with higher-order GNNs. However, I think  this paper requires more work and thus vote to reject. In particular: (1) the writing needs to be improved and better explanations are needed for the theory; and (2) the paper needs more experiments on diverse datasets with more models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments on the paper.\n\nQUESTION 1. What is the intuition behind Lemma 1- theorem 3? The theory of equivariant neural nets \nusually proceeds by considering the action of a group on the space that the output of a given layer of the \nnetwork lives in,  and decomposing this space into an orthogonal sum of subspaces that transform \nindependently, i.e. subspaces that are invariant under the action. Then they find operators on each \nsubspace that are invariant and show that any linear combination of these operators is a valid \nequivariant map. All this usually involves irredudible representations of the group, generalized \nFourier transforms and other abstract mathematical tools.\n\nIn contrast, Section 4.1 of our paper shows that in the case of equivariance to the automorphism group \nof subgraphs, essentially the same can be accomplished simply by finding the eigenspaces of the \ngraph Laplacian. To the best of our knowledge, this has not been done before, and we believe that it is of independent interest. \nSo, in summary, the intuition is that the outputs of the subgraph-layers decompose into subspaces that transform independently under elements of the automorphism group, the specific decomposition is reflective of structure of the automorphism group, but still, the decomposition (up to the the expressiveness gap discussed below) can be found simply from the graph Laplacian. We think this result is not obvious, but it can be visualized intuitively, and it is an important contribution of the paper. Following your comments, we will try to make Section 4.1 less dry and more intuitive. Specifically, some diagrams might help visualize the decomposition into subspaces.\n\nQUESTION 2. Yes and no. There is indeed an interesting connection to graph isomorphism but as we also \nmention in the response to Reviewer uFzV, it is not that simple. As we admit in the Limitations, \nSchur layers are not guaranteed to be the most general automorphism-equivariant linear layers. \nSpecifically, following the proof of our theorems, there might be a gap in expressivity if the eigenvalues \ncorresponding to distinct invariant subspaces coincide. However, the literature on graph isomorphism \namongst others suggests that barring extra symmetries, for moderate sized graphs, this is quite exceptional. \nSo for pratical purposes Schur layers are almost as good as the full group theoretical approach (which \nwould be infeasible to implement in a practical GNN). \n\nRegarding using Schur layers for finding the automorphism group, that is unfortunately not so easy. \nSchur layers can generate automorphism equivariant maps without having to find the automorphism group \nexplicitly. That does not mean that we could somehow reconstruct the automorphism group itself \nfrom the equivariant maps. \n\nFURTHER COMMENTS\n\n- We acknowledge that the experimental results are limited. We were pressed for time and limited in \ncomputational resources before the deadline. We have since conducted experiments on several other \nstandard benchmarks and we see a consistent improvement when we add Schur layers (see global rebuttal). \n\n- The reason we mostly focus on comparing performance to P-tensors is that P-tensors [Hands et al, AISTATS 24] is currently the best performing (and in many ways most general) prior model amongst subgraph based higher order GNNs. \nSpecifically on ZINC 12K, according to the results reported in [Hands et al, AISTATS 24] they represent the state of the art. Moreover, Schur layers work best in tandem with a broader higher order message passing architecture, and P-tensors are one of the most general such frameworks. So it is natural to focus our experiments on contrasting higher order message passing with or without Schur-layers. \n\n- Finally, it is not uncommon for the competition between GNNs to come down to just the 1% level in accuracy. This is a crowded field and experience shows that even very simple architectures can bring down the error to ~90% of the state of the art. Recent works focus on extracting more subtle information from graphs that is responsible for the last few percent of improvement. Admittedly, the competition on the standard benchmarks is getting saturated. In future work we want to apply Schur Nets to practical chemistry problems where the flexibility of the framework and its ability to capture chemically relevant structures (functional groups) will be the most important. First, however we need to validate the architecture by showing its performance on the benchmarks.\n\n- Reproducibility. As we explain the response to Reviewer uFzV, Schur layers themselves are not difficult \nto implement. However, because of the irregular nature of information flow between subgraphs, the rest of \nthe higher order GNN framework is quite involved, especially if all the messages need to be computed \nin parallel on the GPU. This forced us to write a separate C++/CUDA software library for general higher \norder message passing with a PyTorch interface. The library is available on github, but we cannot share a \nlink to it here without jeopardizing anonimity. Once the injunction for anonimity is lifted, the \nlink to the library will be added to the paper and naturally we will also make the training scripts public.", "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 thank all the reviewers for their careful reading of our paper and thoughtful comments. Points raised by individual reviewers are addressed in the individual responses, here we would like to make some general comments.

- First of all, we stress that our paper has two separate aims: 1. Making a general theoretical contribution to the literature by pointing out a connection between spectral graph theory and the theory of equivariant GNNs, specifically, how the eigendecomposition of the graph Laplacian can "mimick" the decomposition into irreducible subspaces that is at the heart of the mathematically more sophisticated group theory based approach to equivariance. 2. Making a practical contribution by showing how the theoretical results can be used to easily "upgrade" higher order subgraph-based GNN to take into account the automorphism group of subgraphs as  "side information". This upgrade makes the GNNs strictly more expressive at little additional computational cost. 

- Several reviewers ask about the potential gap in expressivity related to the fact that in principle the Laplacian-based decomposition into invariant subspaces might be coarser than the group theory based approach. We explain that finding the cases in which this happens is quite a deep theoretical question that goes beyond the scope of the present paper. In practical cases for moderate sized subgraphs however we argue that there is little or no gap.  

- Regarding the comments about the limited scope of the experiments, we have now conducted further experiments, and found that they confirm that taking the automorphism group of subgraphs into account with Schur layers boosts the performance of higher order subgraph neural networks. For example, on the classic TUDatasets we find: 

  | Dataset   | *Linmaps*   | SchurLayer  |
  |-----------|-----------|-------------|
  | Proteins  | 74.7±3.8  | **75.4±4.8**|
  | MUTAG   |   89.9±5.5  | **90.9±4.7**   |
  | PTC\_MR   | 61.1±6.9  | **64.6±5.9**|
  | NCI1      | 82.1±1.8  | **82.7±1.9**|

  Importantly, on the OGBG-MOLHIV dataset we achieve an ROC-AOC of 81.6%+- 0.295, whereas a corresponding P-tensor model without Schur-layers only achieves 77.925% +- 2.461. Please note that this result is highly significant on its own terms, in particular it beats all other competing models (GINE, PNA, HIMP, CIN, SUN, etc.) cited in the P-tensor paper [Hands et al, 2024].

- Several reviewers also ask the computational cost of our model. In addition to our detailed comments about computational complexity and the practical challenges of implementing higher order message passing, here are some illustrative single GPU per-epoch wall-clock runtimes:

  | Dataset   | Linmaps | SchurLayer |
  |-----------|---------|------------|
  | ZINC-12k  | 25.4s   | 27.6s      |
  | NCI1      | 9.5s    | 11.5s      |

  **Table 2**: Runtime per epoch with hyper-params num_layers = 4, rep_dim = 128, dropout = 0.0, batch_size = 256, cycle_sizes = 3,4,5,6,7,8. The implementation of Linmaps and SchurLayer is based on our internal software.

Meta-review: This paper brings forth a new method based on spectral graph theory to achieve permutation equivariance in subgraph-based graph neural networks (GNNs). By constructing a basis for equivariant operations directly from the graph Laplacian, the paper bypasses the need to explicitly determine automorphism groups, which is computationally expensive. This approach helps to enhance the expressiveness of GNNs when dealing with complex local structures, such as cycles within molecules/subgraphs.

The reviewers recognized the significance of this contribution, noting that Schur Nets offer an efficient and theoretically sound method for incorporating equivariant operations in GNNs. The additional experiments added during the rebuttal phase, particularly on the MOLHIV dataset, provided further empirical validation of the method's effectiveness, addressing some concerns about the initial limited scope of evaluation.

On the flip side, issues with the clarity of the theoretical sections were consistently highlighted, with some reviewers finding the explanations of key parts of the paper difficult to follow. While the additional experiments help to mitigate some concerns, further refinement of the paper's presentation, particularly in simplifying and better explaining the theoretical contributions, would strengthen the work.

Given the novelty of the approach, the empirical improvements demonstrated, and the potential impact on the field, I recommend accepting this paper, with the expectation that the authors will continue to refine the clarity and depth of their explanations in the final version.
Decision: Accept (poster)