Schur Nets: exploiting local structure for equivariance in higher order graph neural networks

Authors: qingqi  zhang
ruize  xu
risi  kondor
applied  mathematics
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:10:20

Abstract: Several 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 empirically this approach can boost the performance of GNNs.

Main paper: 
 introduction: 
 Message pasing neural networks (MPNNs) are the most popular paradigm for building neural networks on graphs [19] . While MPNNs have proved to be remarkably effective in a range of domains from program analysis [1] to drug discovery [21] , a series of both empirical [3] and theoretical [43, 10] results have shown that the fact that MPNNs are based on just individual vertices sending messages to their neighbors limits their expressive power. This problem is especially acute in domains such as chemistry, where the presence or 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 [25] or between subgraphs, treated as single units [2, 16, 4, 49] . However, if the actual messages remain scalars, the added expressive power of these networks is relatively limited.Another recent development is higher order message passing networks, where subgraphs communicate with each other via not just scalars, but more complex messages indexed by the individual vertices of the sending and receiving subgraphs [32, 35, 15] . For example, in an organic molecule, the internal state of a benzene ring (six carbon atoms arranged in a cycle) can be represented as a matrix T ∈ R 6×c , in which the rows correspond to the individual carbons. If this benzene ring passes a message to a neighboring benzene ring with which it shares an edge, information relating to the two shared carbons can be sent directly to the same atoms in the second ring, whereas information relating to the other vertices has to be treated differently. Hypergraph neural networks [16, 48, 44] and neural networks on more abstract mathematical structures such as simplicial complexes [7, 6] are closely related, since these also involve higher order generalizations of message passing between combinatorial objects interlocked in potentially complicated ways.The theory of higher order MPNNs builds on the by now substantial literature on permutation equivariance in neural networks from Deep Sets [46] , to various works studying higher order permutation equivariant maps [33] , and is also related to the category theoretic approach expounded employed Natural Graph Neural Networks [13] . The recently introduced P -tensors formalism provides a flexible framework for implementing message passing in higher order MPNNs and enumerating all possible linear maps between subgraphs [22] .One aspect of higher order MPNNs that has garnered relatively little attention, however, is the interaction between the local graph structure and the equivariance constraint. Intuitively, the reason that GNNs must be equivariant to permutations is that when the same, or analogous, graphs are presented to the network with the only difference being that the vertices have been renumbered, the final output must remain the same. However, Thiede et al. [40] observed that at the local level enforcing full permutation equivariance is 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 group of automorphisms of S, rather than all |S|! permutations of its vertices. The Autobahn architecture described in [40] explicitly takes the automorpism group of two specific types of subgraphs, cycles and paths, into account and defines a bespoke form of equivariant convolution on them, which is shown to improve performance on molecular datasets like ZINC [27] .The drawback of the Autobahn approach is that it requires explicitly identifying the automorphism group of each type of subgraph of interest, and crafting specialized equivariant operations for it based on its representation 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 a basis of automorphism equivariant operations on 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. 
background: equivariance with side information: 
 Let G be an undirected graph with vertex set V = {1, 2, . . . , n} and edge set E ⊆ V × V represented by the adjacency matrix A ∈ R n×n . Graph neural networks (GNNs) address one of two, closely related tasks: (a) given a function f in : V → R on the vertices of G, learn to transform it to another function f out : 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 A, to a scalar or vector ψ(A) that characterizes G's structure.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 n . Applying a permutation σ ∈ S n to the vertices changes the adjacency matrix to A = σ(A) withA i,j = A σ -1 (i),σ -1 (j) .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,f in i = f in σ -1 (i), then the output must transform the same way,f out i = f out σ -1 (i). This property is called equivariance. Formally, denoting the mapping from inputs to outputs φ : f in → f out , equivariance states that the action σ : f → f of permutations on functions given by f i = f σ -1 (i) must commute with φ, that is,EQUATIONfor any σ ∈ S n and any input function f in ∈ R V . In contrast, for networks that just learn embeddings G → ψ(A), the constraint is invariance to permutations, i.e., ψ(A) = ψ(σ(A)). In practice, however, the two cases are closely related because most graph embedding networks work with functions defined on the vertices, and then symmetrize over permutations at the very top of the network by using a readout function such as ψ(G) = i f out i . Enforcing the constraint (1) on the hypothesis space directly would be very limiting, effectively constraining GNNs to be composed of symmetric polynomials of f in combined with pointwise nonlinearities. Graph neural networks cleverly get around this problem by using the adjacency matrix itself as side information to guide equivariance. For example, in classical (zeroth order) message passing neural networks (MPNNs), the output of each layer is itself a (vector valued) function on the graph, and in the simplest case the update rule from layer to layer + 1 isEQUATIONwhere N (i) denotes the neighbors of node i in G, W and θ are learnable weight matrices/vectors and η is a 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 write φ as φ A , and the equivariance condition asEQUATIONSince vertex permutations transform both f in and A, when the vertices are permuted A can implicitly provide information about this to the algorithm allowing it to compensate, even if for fixed A, φ A is not equivariant to all n! factorial permutations. Update rules such as (2) work in this way automatically. The adjacency matrix cannot carry information about permutations that leave it invariant however, so φ A must still be equivariant to the group of all such permutations, called the automorphism group of G and denoted Aut(G) (or 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 and hence increase the expressive power of the network as a whole motivates much of the rest of this paper.Despite the great success of message passing networks, a long sequence of empirical as well as theoretical results [43, 35, 31, 14, 38] over the last several years have made it clear that the expressive power of algorithms based on simple update rules like (2) is severely limited. In response, the community has turned to extensions of the MPNN paradigm involving message passing not just from vertices to vertices but also between vertices and edges or between carefully selected subgraphs [19, 35, 6, 8] . While these networks maintain the local and equivariant character of earlier MPNNs, 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 output 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 a titular neuron corresponding to a benzene ring in a molecule, the output of n, assuming we have C channels, might be a matrix T ∈ R 6×C or a tensor T ∈ R 6×6×C , or T ∈ R 6×6×6×C , 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-neurons, must be treated accordingly. Such higher order representations offer far greater expressive power since T can effectively represent not just information related to individual vertices, but also relations between pairs of vertices, triples, and so on. The general trend towards higher order message passing is also closely tied to hypergraph neural networks [16] , "topological" neural networks and simplicial complex networks [7, 6] .Recently, [22] proposed a general formalism for describing such higher order architectures using so-called P -tensors. In this formalism, given a neuron n attached to a subgraph S with m vertices, if the output of n is a zeroth order P -tensor T with C channels then that means that it is simply a vector T ∈ R C . The elements of this vector are scalars in the sense that they give a global description of S, which is invariant to permutations of the vertices of S. If T is a first order P -tensor then that means that it is a matrix T ∈ R m×C whose columns transform under permutations of S similarly to how f in and f out transform under global permutations of the full graph:EQUATION)If T is a second order P -tensor T ∈ R m×m×C , then each slice of it corresponding to a given channel transforms according to the second order action of the symmetric group, like the adjacency matrix:EQUATIONContinuing this pattern, a k'th order P -tensor T ∈ R m×m×...×m×C transforms under local permutations asEQUATION[22] derived the general rules for equivariant message passing between such P -tensors in the cases that the sending and receiving subgraphs S resp. S are (a) the same (b) partially overlap (c) are disjoint. In all these cases however it was assumed that T needs to be equivariant to all permutations of the underlying subgraphs S 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 we describe how the P -tensor framework can be extended so that the S → S type of message passing steps (called linmaps in the P -tensors nomenclature) are equivariant to just Aut(S) rather than the full symmetric group S m .3 Equivariance to local permutations: the group theoretic approachRecall that a representation of a finite group G such as S m or Aut(S) is a (complex) matrix valued function ρ : G → C dρ×dρ such that the matrices multiply the same way as the corresponding group elements do ρ(σ 2 σ 1 ) = ρ(σ 2 )ρ(σ 1 ) σ 1 , σ 2 ∈ G. Two representations ρ and ρ are said to be equivalent if there is an invertible matrix Q such that ρ (σ) = Q -1 ρ(σ) Q for all group elements. A representation of a finite group is said to be reducible if there is some invertible matrix Q that reduces it to a block diagonal formρ(σ) = Q -1 ρ 1 (σ) ρ 2 (σ) Q.Some fundamental results in representation theory tell us that G only has a finite number of inequivalent irreducible representations (irreps, for short), these irreps can be chosen to all be unitary, and that any representation of G is reducible to some combination of them [39] . These facts give rise to a type of generalized Fourier analysis on finite groups, consisting of decomposing vectors that G acts on into parts transforming according to the unitary irreps of the group.The most general approach to defining Aut(S)-equivariant maps for first, second, and higher order subgraph neurons uses exactly this machinery. In particular, defining permutation matrices as usual as[P σ ] i,j = 1 if σ(j) = i 0 otherwise,dropping the channel indices w.l.o.g., and writing our P -tensors in vectorized form T = vec(T ) ∈ R m k , we note that ( 4)-( 6) can be written in a unified formT = P k (σ) Twhere P k (σ) is the k-fold Kronecker product matrix P k (σ) = P σ ⊗ P σ ⊗ . . . P σ . Crucially, P k (σ), regarded as a function Aut(S) → C m k ×m k is a unitary representation of the automorphism group.According to representation theory, P k must then be decomposable into a direct sum of irreps ρ 1 , . . . , ρ p of Aut(S) with corresponding multiplicities κ 1 , . . . , κ p . The same unitary matrix Q that accomplishes this can also be used to decompose T into a combinations of smaller vectors(t i j ∈ R dρ i ) i,j : QT = i κi j=1 t i j ,where each t i j now transforms independently under the action of the group as t i j → ρ i (σ) t i j . Alternatively, stacking all t i j vectors transforming according to the same irrep ρ i together in a matrix T i ∈ R dρ i ×κi , we arrive at a sequence of matrices T 1 , T 2 , . . . , T p trasforming asEQUATION)Now it is very easy to see how to construct learnable linear operations that are equivariant to these actions: simply multiplying each T i from the right by an apporpriate weight matrix W i .In summary, this general, group theoretic approach to constructing automorphism group equivariant linear maps between k'th order P -tensors can be seen as a special case of e.g. [30, 41] , and involves the following sequence of steps:1. Find the unitary matrix Q that decomposes P k (σ) = P σ ⊗ . . . ⊗ P σ into a direct product of irreducible representations of Aut(S). 2. Use Q to decompose the input P -tensor into a sequence of matrices T 1 . . . T p transforming as (7) . 3. Multiply each T i by an appopriate learnable weight matrix W i ∈ R κi×κi . 4. Use the inverse map Q -1 = Q † to reassemble T 1 , T 2 , . . . , T p into the output P -tensor T out .Notwithstanding its elegance and power, the representation theoretic approach to implementing automorphism group equivariance has some major disdvantages, namely that it requires explicitly determining the automorphishm group of each subgraph of interest, which is in and of itself a combinatorial problem, and explicitly finding its 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 in the next section:1. We have a collection of (orthogonal) linear maps {P k (σ) :U → U } σ∈Aut(S) (with U = R m k) that the neuron's operation needs to be equivariant to. 2. U is decomposed into an orthogonal sum of subspaces U = U 1 ⊕ . . . ⊕ U p corresponding to the different irreps featured in the decomposition of P k . 3. Each U i is further decomposed into an orthogonal sum of subspacesU i = V i 1 ⊕ . . . ⊕ V i κicorresponding to the different columns of the T i matrices. 4. The decomposition is such that the {P k (σ)} maps fix each V i j subspace. Moreover, for a fixed i, {P k (σ)} acts the same way on each V i j subspace by ρ i (σ). 5. This structure implies that any linear map that linearly mixes the V i 1 , . . . V i κi subspaces but does not mix information across subspaces with different values of i is equivariant. 
equivariance via spectral graph theory: schur layers: 
 Instead of the representation theoretical approach described in the previous section, for practical purposes we advocate a simpler way of implementing automorphism group equivariance based on just spectral graph theory. The cornerstones of this approach are the following two theorems. The proofs can be found in the Appendix. Theorem 1. Let G be a finite group acting on a space U by the linear action {g : U → U } g∈G . Assume that we have a decomposition of U into a sequence of spaces of the formU = U 1 ⊕ . . . ⊕ U p such that each U i is invariant under G in the sense that for any g ∈ G and v ∈ U i , we have g(v) ∈ U i .Let φ : U → U be a linear map that is a homothety on each U i , i.e., φ(w) = α i w for some fixed scalar α i for any w ∈ U i . Then φ is equivariant to the action of G on U in the sense that φ(g(u)) = g(φ(u)) for any u ∈ U and any g ∈ G.The representation theoretic result of the previous section actually corresponds to a refinement of this result involving a further decomposition of each U i space into a sequence of smaller subspaces. Theorem 2. Let G and U be as in Theorem 1, but now assume that each U i further decomposes into an orhthogonal sum of subspaces in the formU i = V i 1 ⊕ . . . ⊕ V i κi such that (a) Each V i j subspace is individually invariant by G; (b)For any fixed value of i, the spaces V i 1 , . . . , V i κi are isomorphic and there is a set of canonical isomorphisms ι i j→j :V i j → V i j between them such that g(ι i j→j (v)) = ι i j→j (g(v)) ∀ v ∈ V i j . Let φ : U → U be a map of the form φ(v) = j α i j,j ι i j→j (v) v ∈ V i jfor some fixed set of coefficients {α i j,j }. Then φ is equivariant to the action of G on U .In the matrix language of the previous section, U 1 , . . . , U p correspond to the T 1 , T 2 , . . . , T p matrices, whereas the V i 1 , . . . , V i κi subspaces of U i correspond to individual columns of T i . For any fixed i, the α i j,j j,j scalars correspond to the individual matrix entries of the learnable weight matrix W i .It remains to find the actual systems of invariant subspaces that can be plugged into Theorems 1 and 2. The following lemma suggests such a system of subspaces can be found directly from the graph Laplacian, effecitvely bypassing the need for group representation theory. Lemma 1. Let S be an undirected graph with m vertices, Aut S its automorphism group, and L its combinatorial graph Laplacian. Assume that L has p distinct eigenvalues λ 1 , . . . , λ p and corresponding subspaces U 1 , . . . , U p . Then each U i is invariant under the first order action (4) of Aut S on R m . Proof. Since Aut S is a subgroup of the full group of vertex permutations , its action onR m is just v → σ(v) = P σ v with σ ∈ Aut S .L is a real symmetric matrix, so its eigenspaces U 1 , . . . , U p are mutually orthogonal andU 1 ⊕ . . . ⊕ U p = R n . Furthermore, v ∈ U i if and only if Lv = λ i v.By definition, Aut S is the set of permutations that leave the adjacency matrix, and consequently the Laplacian invariant, so, in particular, P σ LP σ -1 = L. Therefore, for any v ∈ U i and any σ ∈ Aut S ,L P σ v σ(v) = P σ LP σ -1 P σ v = P σ Lv = λ i P σ v σ(v)showing that σ(v) ∈ U i and hence that U i is an invariant subspace.The following Corollary puts this lemma to use and gives 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 a given subgraph in the graph, for example, every single benzene ring in a molecule. Clearly, for the sake of global permutation equivariance, the weight matrices for the same subgraph S must be shared across the network. Corollary 1. Consider a GNN on a graph that involves a neuron n S corresponding to a subgraph S with m vertices. Assume that the input of n S is a matrix T ∈ R m×cin , the rows of which transform covariantly with permutations of S and c in is the number of channels. Let L be the combinatorial Laplacian of S, U 1 , . . . , U p be the eigenspaces of L, and M i an orthognal basis for the i'th eigenspace stacked into an R n×dim(Ui) dimensional matrix. Then for any collection of learnable weight matricesEQUATIONis a permutation equivariant linear operation.The spectral approach also generalizes to higher order permutation equivariance, and in that case we can take advantage of the more refined two-level subspace structure implied by Theorem 2. Theorem 3. Let S, L and the M i 's be as in Corollary 1. Given a multi-index i = (i 1 , . . . , i k ) ∈ {1, . . . , p} k , we define its type as the tuple n = (n 1 , . . . , n p ), where n j is the number of occurrences of j in i and we define I n as the set of all multi-indices of type n. Assume that the input to neuron n S is a k'th order permutation equivariant tensor T ∈ R m×...×m×cin , as defined in Section 3. For any given i, define the k'th order eigen-projectorΠ i = P i (M i1 ⊗ M i2 ⊗ . . . ⊗ M i k ⊗ I) : R m×...×m×c → R m×...×m×c where P i is a permutation map that canonicalizes the form of the projection, as defined in the Appendix. Let T • W denote multiplying T by the matrix W only along its last dimension. Then for any collection of weight matrices {W i ,i ∈ R cout×cin } the mapφ : T -→ n i ∈In i∈In Π i (Π i (T W i ,i ))is a permutation equivariant map.As mentioned earlier, this gives sufficient but not necessary conditions for equivariant maps w.r.t. the automorphism group. A discussion of potential gap between our approach and the group theoretical approach can be found in appendix D. 
experiments: 
 To empirically evaluate Schur net, we implement the first order case 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., φ : T in → T out where T in ∈ R m * cin and T out ∈ R m * cout are representations of the subgraph. Another key component that is missing is the message passing between different subgraphs, which as mentioned in the previous section, is already given by [22] (P-tensor). In P-tensor framework, the most general linear equivariant message passing is defined based on an extension of equivariant maps by considering different domains. More details can be found in appendix E. We implement our Schur net based on the P-tensor framework but use Schur layer to transform local representation.There are several design details about the architecture that are 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 scalability. The reason to do so is in the chemical dataset we used, cycles are indeed the most important functional group to the property to be predicted, other subgraphs such as m-stars, and m-paths didn't help the performance. ( 2) While having first-order representation on the cycles, we also maintain 0th-order representation (just scalar) on node and edges, as in [6, 22] . Those node and edge representations captures more elementary information about the graph, such as k-hop neighborhood, and is 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 it expands the input feature to the output feature. The codes used to run our experiments can be found at https://github.com/risilab/SchurNet.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. S m (following [22] we called it Linmaps). To make a 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 [40] because it didn'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. But 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 [27] dataset in the main text. Results on TUdatasets as well as runtime comparison can be found in appendix H. The task on ZINC-12K is to regress the logP coefficient of each molecule and the Mean absolute error (MAE) between the prediction and the ground truth is used for evaluation.We design experiments to compare Linmaps and Schur layers in various scenarios, to showcase the robustness of the improvement. 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 subgraph structure and increased number of equivariant maps. We also tried other ways to use Schur layer, the result is summarized in G.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 cycle representation. "Linmap SchuLayer" 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 in better performance. The test MAE of Linmaps in this table is taken from [22] .The other advantage of Schur layer is it computes the feature transform only based on the subgraph's Laplacian, bypassing a difficult step of finding the automorphisms group and irreps of the subgraph it acts on. As discussed in the theory, Schur layer constructs equivariant maps only based on the subgraph'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 is considered. Results can be found in appendix G.Finally, and most importantly, we compare the Schur-Net to several other higher-order MPNNs1 on ZINC-12k dataset and OGB-HIV dataset [24] in table 3. We included baselines of (1) classical MPNNs: GCN [29] , GIN [43] , GINE [25] , PNA [12] , HIMP [17] (2) higher order MPNNs: N2 -GNN [15] 2 , CIN [6] , P-tensors [22] (3) Subgraph-GNNs: DS-GNN(EGO+) and DSS-GNN(EGO+) [4] , GNN-AK+ [49] , SUN(EGO+) [18] (4) Autobahn [40] .We find that Schur Net ranked second on ZINC-12K and outperformed all other baselines on OGB-HIV dataset. This shows the expressivity of adding more equivariant maps by leveraging the subgraph topology. Furthermore, note that while N 2 -GNN outperforms Schur Net on ZINC-12K, it's a second-order model whereas in our experiment, we only used first-order activation. Also, the partial reason Autobahn didn't perform well is in the original implementation, the author 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, we need to combine it with a general message passing framework between subgraphs as well. 
limitations: 
 Unlike the representation theoretic approach, the spectral approach is not guaranteed the give the finest possible decomposition into invariant subspaces. Hence, equations like (8) do not necessarily define the most general possible automorphism-equivariant linear maps. In this paper we did not investigate from a theoretical point of view the potential gap in expressivity due to this fact. In general, being able to craft automorphism-equivariant layers of any order for any types of subgraphs opens up a 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. 
conclusions: 
 Enforcing equivariance to the automorphism group of subgraphs in higher order neural networks seemingly requires the use of advanced tools from group representation theory. This is likely a large part of the reason why automorphism-based architectures such as [40] are not used more commonly in practical applications. In 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 to enumerate all irreducible representations of the automorphism group, can lead to an architecture that is almost as expressive. Our algorithm, called Schur Nets, easily generalizes to higher order activations, as well as incorporating other types of side information such as vertex labels.In a practical setting, Schur Nets is easiest to deploy in conjunction with an another algorithm like P-tensors [22] which 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 of.Our approach exposes heretofore unexplored connections between permutation equivariance and spectral GNNs such as [9, 23] . It also highlights the fact that while permutation equivariance is a fundamental constraint on graph neural networks, the key to building high performing, expressive GNNs is to use as much side information as possible, whether it be the adjacency matrix, vertex degrees or something else, to reduce the size of the group that the network needs to be equivariant to.  
 
 Appendix: The purpose of the permutation map P i in Theorem 3 is to remap the tensor product space R dim(Ui 1 )×...×dim(Ui k )×C into a canonical form so that those dimensions that correspond to i j = 1 are mapped to the first n 1 slots, those dimensions with i j = 2 are mapped to the second n 2 slots, and so on. Given the permutation τ : {1, 2, . . . , k} → {1, 2, . . . , k} that canonicalizes the indices in this way, P i is just the corresponding permutation map, i.e.,P i (x 1 ⊗ . . . x k ⊗ x c ) = x τ (1) ⊗ . . . x τ (k) ⊗ x c .Proof of Theorem 1. Let {g↓ Ui : U i → U i } g∈G be the restriction of the action of G to U i . Since G fixes each U i , the action of G on the full space decomposes in the formg(u) = p i=1 g↓ ui (u↓ Ui ) u ∈ U.Now since multiplication by scalars commutes with linear maps,φ(g(u)) = p i=1 α i g↓ ui (u↓ Ui ) = p i=1 g↓ ui (α i u↓ Ui ) = g(φ(u))for any u ∈ U and any g ∈ G.Proof of Theorem 2. Each of the V i j subspaces is invariant, hence a homothety on each is an equivariant operation for the same reason as in Theorem 1. In addition, since G acts the same way on any pair of subspaces (V i j , V i j ), any map of the form ξ i j,j : V i j V i j that is 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 i1 ⊗ M i2 ⊗ . . . ⊗ M i k ⊗ I c ) is invariant to permutations. Further after applying the permutation map P i , all such subspaces of the same type n, the action of S k on all such subspaces will be the same. Hence we can directly apply Theorem 2 to prove this theorem.Here we give a more direct proof for Corollary 1.Proof. Without loss of generality, we assume c in = c out = 1. Since the M i 's and λ i 's are eigenspaces and eigenvectors of the Laplacian L, L = M ΛM T , whereM = [M 1 , • • • , M p ] and Λ = diag(λ 1 , • • • , λ m ). The neuron n S is a linear transform φ : R m → R m , with φ(T ) = Σ p i M i M T i T W i = M V M T T , where V = diag(W 1 I n1 , • • • , W p I np ).Here the W i 's are just scalars and I ni is an identity matrix of the same size as the corresponding eigenspace.Given a permutation σ ∈ S n , we want to show that φ σ (σ • T ) = σ • φ e (T ), which is the definition of equivariance. Note that φ σ actually depends on σ, since we're doing eigenvalue decomposition on the Laplacian of the subgraph transformed by σ. This is the key to proving equivariance. We use e to denote the identity permutation.Now L σ = P σ LP T σ = M σ ΛM T σ, where M σ = P σ M , while the eigenvalues remain invariant after permutation and eigenspaces are transformed in the same manner as L. Thus,φ σ (σ • T ) = M σ V M σ P σ T = P σ M V M σ P σ P σ T = P σ φ e (T )which is the desired result.Remark 1. The key to the proof is that the transform φ depends on an object transformed with permutation σ, specifically. graph 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 to set L = L + V , where V = diag(v 1 , • • • , v m ) captures the node labels or degrees, and build the Schur neuron n S from L .Higher order MPNNs have become a popular research area in graph representation learning since the seminal work by [33] , which characterized the space of equivariant map w.r.t. S n for k'th order tensors. The following works have mainly been divided into two streams, the one is based on k-Weisfeiler Leman test (k-WL test) [42, 20] , for instances, [32] proposed k-order graph neural networks that is as powerful as k-WL test; [35] proposed k-GNN to approximate (or simulate) k-WL test; [15] further designed a (k, 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 θ(n k ).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. [22] incorporates any subgraph template and uses the equivariant maps defined [33] for local feature transform and devised a 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 k (including nodes and edges), their network are as powerful as WL test. However, such comparisons are not very meaningful to indicate the expressive power of such a domain-specific approach. In our opinion, the ability to learn certain features (such as count cycles of certain sizes or learn some function related to specific functional groups) might be a better criterion. It'll be an interesting research direction to design suitable criteria for the expressive power of such higher order MPNNs in general.Our work follows this line of work since we're choosing specific subgraphs to learn representation on. But we utilize the subgraph'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 [40] , which is the first to introduce equivariance to the automorphism group to GNNs. The difference between our work and it lines twofold: (1) Autobahn theoretically introduces equivariant maps w.r.t. automorphism group via generalized convolution and Cosets, which is another group theoretical approach to construct equivariant maps, while we're using the decomposition to irreps (2) More importantly, Autobahn didn'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 give the full set of equivariant maps, experiments show improvement over the traditional approach where only equivariant maps w.r.t. S n are used. We believe this algorithm, together with the group theoretical idea about decomposition R m k into stable subspaces and irreps are beneficial to the research community.There is a "third" type of higher order GNNs that is 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 [47, 49, 4, 45, 18] associate each node with a subgraph (by deleting the node, marking the node or extracting the EGO-network) and do MPNN on each subgraph, where they get the resulting representation X ∈ R n×n that can be considered as a 2nd order tensor representation on the original graph.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. Aut S . Because (1) In the decomposition of U = R m k to eigenspaces U = U 1 ⊕ . . . U t , while U i is stable subspaces, it might not be irreducible and finer decomposition may be possible. In other words, there might be two irreps (isomorphic or not) corresponding to the same eigenvalue. (2) The maps defined by 1 didn't take into account the isomorphic subspaces corresponding to the same type of irrep, thus ignored the possible equivariant maps between V i j and V i j . 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 ).Aut S # of distinct Eigenvalues (Schur Layer)EQUATION6-cycle with one branch S 2 7 29 7Table 4 : Examples on EVD approach vs group theoretical approach towards # of equivariant maps w.r.t. Aut S . To calculate the decomposition of R m into irreps, one can calculate κ i = (φ|χ i ) where φ and χ i is the character of the first-order action and ith irrep respectively, and (|) is inner product. Another quick approach is to use φ(σ) = k κ k χ k (σ) and look at some examples of σ to 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, e.g., in 5-cycle with one branch case, S 2 only have two 1-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 * 4 + 2 * 2 = 20 possible equivariant maps. However, note that # of irreps (counting multiplicities given by i κ i ) is equal to # of distinct eigenvalues, meaning that each eigenspace corresponds to an irreducible subspace and the decomposition of R m 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 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, we didn't take this into account because we found out that only considering cycles is enough for a very good performance in the datasets we used.Generally, it's complicated to determine the gap between our EVD approach and the group theoretic approach, especially in higher-order cases (where merely determining the κ i 's is tricky), so we leave this into feature exploration.The P-tensor framework is a framework for linear equivariant maps w.r.t. S n both between the same subgraph and across different subgraphs. It is built on the equivariant maps characterized by [33] .Definition 1 (P-tensors). Let U be a finite set of atoms and D = (x 1 , . . . , x d ) an ordered subset of U . We say that a k-th order tensor T ∈ R d×d×•••×d is a k-th order permutation covariant tensor (or P-tensor for short) with reference domain D if under reordering by τ ∈ S d D it transforms to[τ • T ] i1,i2,...,i k = T τ -1 (i1),...,τ -1 (i k ) .E.1 Message passing between P-tensors with the same reference domainConsider the equivariant maps sending T on D to T out on D. The space of equivariant maps w.r.t S m is characterized by [33] : Proposition 1. The space of linear maps φ : R dk1 → R dk2 that is equivariant to permutations τ ∈ S d is spanned by a basis indexed by the partitions of the set {1, 2, . . . , k 1 + k 2 }.Then the authors designed a straightforward way to write the maps explicitly. Specifically, for each partition of the set {1, 2, . . . , k 1 + k 2 }, there are three parts that determines the equivariant map:(1) summing over specific dimensions or diagonals of T in (2) transferring T in to T out by identifying indices of T in with indices of T out (3) broadcasting the result along certain dimensions of T out . These three operations correspond to the three different types of sets that can occur in a given partition P:(1) those that only involve the second k2 numbers, (2) those that involve a mixture of the first k 1 and k 2 and (3) those only involve the first k 1 numbers. The type ( 1) -( 3) corresponds to type (1) -( 3) of operations with the dimensions in the sets.For example, in the case k 1 = k 2 = 3, the P = {{1, 3}, {2, 5, 6}, {4}} partition corresponds to (a) summing T in along its first dimension (corresponding to {4}) (b) transferring the diagonal along the second and third dimension of T in to the second dimension of T out (corresponding to {2, 5, 6}) (c) broadcasting the result along the diagonal of the first and third dimensions (corresponding to {1, 3}).Explicitly, this gives the equivariant map:T out a,b,a = c T in c,b,bSee table 5 for another example for k 1 = k 2 = 2 case. Here, we explain in detail the decomposition of k-th order permutation to irreps of S m .Proposition 2. Let ρ λ , λ m be the irreps of S m , U = R m k , σ ∈ S m act on U in the manner of equation 6, and suppose this action contains irreps ρ λ1 , . . . , ρ λp with multiplicities κ 1 , . . . , κ p , we have:U = U 1 ⊕ U 2 ⊕ • • • ⊕ U p , U i = κi j V j iwhere the first part gives the canonical decomposition of U and the second part further decompose each U i into irreducible subspaces, where V j i correspond to ρ λi . In matrix form,P (k) σ = M     ρ λ1 (σ) 0 • • • 0 0 ρ λ2 (σ) • • • 0 . . . . . . . . . . . . 0 0 • • • ρ λp (σ)     M T , for all σ ∈ S mwhere M is the orthogonal transformation for basis and we abuse ρ λi (σ) to denote also the matrix of i-th irrep in the decomposition.If we take a closer look at M , we can find that since P (k) σ is under the standard basis of R m k , thus M is just the orthonormal basis of each U i (thus each V j i ) combined together, we denote M = (M 1 , . . . , M p ) with M i a m k × (d λi * κ i ) dimensional matrix, where d λi is the degree of ρ λi . Therefore, P (k) σ T becomes:EQUATIONThe part (1) is a generalized Fourier transform of T to its Fourier components (coordinates under the orthonormal basis)T =      M T 1 T M T 2 T . . . M T p T          B 1 B 2 . . . B p    , and the part (2) is the irreps ρ λ1 , . . . , ρ λp act independently on T with each componentB i →    ρ λi (σ) • • • 0 . . . . . . . . . 0 • • • ρ λi (σ)    B i .Note that there're κ i multiple of ρ λi act the same on components of B i correspond to V j i , with a slight abuse of notation, we can think B i ∈ R d λ i ×κi (instead of R (d λ i * κi)×1 ) and write this map as ρ λi (σ)B i , the fact that the map by irrep ρ λi act independently on each column of B i allow us to identify directly a set of equivariant maps by multiplying B i with matrix W i ∈ R κi×κi to the right, and using associativity of matrix multiplication: ρ λi (σ)(B i W i ) = (ρ λi (σ)B i )W i . This gives in total of i κ 2 i independent equivariant 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:EQUATION)with the abuse of notation to rearrange elements in B i mentioned above.Then we present a detailed version of theorem 2 in the main text. Theorem 4 (Necessary and sufficient condition for equivariant map). Let G be a finite group acting on a vector space U by the linear action {g : U → U } g∈G and assume the action can be decomposed into irreps ρ 1 , . . . , ρ p with multiplicities κ 1 , . . . , κ p and degree d i :U = U 1 ⊕ U 2 ⊕ • • • ⊕ U p , U i = κi j=1 V j iThen φ : U → U is an equivariant map w.r.t. this group action if and only if φ is of the form:EQUATION)for some fixed set of coefficient {α i j,j : i ∈ [1, . . . , p], j, j ∈ [1, . . . , κ i ]}. In matrix form, suppose the matrix of g is R g under basis (e i ) and dim(U ) = n, and it decompose into:EQUATIONThen φ : R n → R n is equivariant if and only if it is of the form:EQUATIONEQUATIONwhere T ∈ R n , W i ∈ R κi×κi is the fixed coefficients and B i rearrange to R di×κi when needed. The coefficients α i j,j corresponds to (W i ) j,j .3 Proof. Sufficiency: firstly, α i j,j τ i j→j (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 V i j and let W = Im(φ| V i j ) the image of φ on V i j . Since φ • g = g • φ and g(v) ∈ V i j for any v ∈ V i j , we have g(φ(v)) = φ(g(v)) ∈ W , so W is stable under the action. Thus we can decompose W into irreducible spaces W = W 1 ⊕ . . . W p . Apply this decomposition to φ(v) for v ∈ V i j , we get: φ(v) = φ 1 (v) + . . . + φ p (v) where φ i (v) ∈ W iIn other words φ k = P roj k • φ where k is the projection of W onto W k (uniquely defined by the direct sum decomposition). Then φ k : V i j → W k and φ k • g = g • φ k . By Schur's lemma [39] , forφ k = 0, we must have W k isomorphic to V i j and φ k (v) = θ k τ V i j ,W k (v). Since only V i j is isomorphic to V i j , we have W k = V i k and φ k (v) = α i j,k τ j,k (v), where τ j,k (v) is the isomorphic map sending V i j to V i k . Thus φ(v) = k φ k (v) = k α i j,k τ j,k (v) for v ∈ V i j .Finally, by linearity and U = i,j V i j , the only possible equivariant function φ : U → U is given by 11.Connection to matrix form: first note that the isomorphism τ i j→j : V i j → V i j is given by: τi j→j (u i j,l ) = u i j ,lwhere {u i j,l , l = 1, . . . , κ i } and {u i j ,l , l = 1, . . . , κ i } are orthonormal basis for V i j and V i j respectively such that the action of g is associated with matrix ρ i (g). Therefore,φ(u i j,l ) = j α i j,j τ i j→j (u i j,l ) = j α i j,j (u i j ,l )Thus the matrix of φ under basis (u i j,l , i = 1, . . . , p, j = 1, . . . , κi , l = 1, . . . , d i ) is           W 1 . . . W 2 . . . W p . . .          (which is the same as    W 1 0 • • • 0 0 W 2 • • • 0 . . . . . . . . . . . . 0 0 • • • W p     with B i rear- range to R di×κi) and M is just the matrix to transform standard basis (e i ) to basis (u i j,l ).While Schur neuron can be viewed as a generic transform on any subgraph's first-order activation, we provide some thoughts and possibilities to instantiate it.In our experiment, we primarily view Schur neuron as a way to expand the feature of a subgraph. It can be viewed as an analogue to CNN's convolution filter and it's indeed a constrained version of spectral convolution filter [5] on the subgraph. In light of this, we call number of channels of Schur neuron as how many times it expand the output feature versus the input feature.Besides, we observe that the linear equivariant map described [33] is a special case of Schur neuron's map. The two possible linear map in [33] is (1) identity map, corresponding to take all weightsW i = 1 (2) T → Σ i T i 1,where 1 is all ones vector, corresponding to set W 1 = 1, and W i = 0 for i = 1 since 1 is eigenvector of any graph Laplacian with eigenvalue 0. Consequently, we suggest to keep the two basic but important linear maps and augment them with Schur neuron. Empirically we verified this by an experiment only vary the number of channels. In figure 1 , we see that further increase the number of channels beyond 4 wouldn't give us performance gain since cycle 5 and 6 only has 3 and 4 distinct eigenvalues 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. We first start with some molecular datasets in TUdataset [34] , which is a small but commonly used benchmark for GNN. In table In table 9, we compare the runtime of our Schur layer and Linmaps, which shows the extra computational cost of Schur layer wasn't significant while being able to use more equivariant maps and achieving better accuracy.Linmaps Schur Layer Zinc-12k 25.4s 27.6s NCI1 9.5s 11.5s Table 9 : Runtime per epoch with hyper-params num_layers = 4, rep_dim = 128, dropout = 0.0, batch_size = 256, num of channels = 4, cycle_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 5 and 6 are chosen as subgraphs in the neural network. In designing of our architecture, we design a message passing scheme similar to [22] and add Schur layer to each of the convolution layers. A visualization of our architecture can be found in figure ?? In each convolution layer, we maintain 0th-order node representation (h v ∈ R |V | * dim ) and edge representation (h e ∈ R |E| * dim ) where we assume the input graph G = (V, E). We further maintain 1st-order representation on cycles (h D k ∈ R (k * (c k ) * dim) ) where D k is cycle of length k and c k is 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 [22] and then the incoming message to cycles as well as 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 or -add described in GIN [43] and feed it into an MLP to get new representations.Hyperparameters For experiments on ZINC-12K and OGB-HIV, we tune representation dimension in {32, 64, 128}, and experiment on cycles up to length 18. In the best-performing model, we use representation dimension 128 and cycle lengths from 3 to 8 and number-of-layers is always 4. For Schur layer, we tuned number of channels from 2 to 8 and found 2, 4 are a suitable choice when it is used as an augmentation to Linmaps. For MLPs, we either use 2 to 3 layers depending on how dense the input's information is. We always use a batchnorm [26] after the Linear layer and then do ReLu activation. For training hyperparameters, we use an init learning rate of 0.01 and use ReduceLROnPlateau scheduler in PyTorch with patience of 10 or 30. We use Adam optimizer [28] for all trainings. We train for 500 or 1000 epochs depending on model size. In particular, in table 10, the models have representation dimension 32, so it is trained to only 500 epochs. All other models are 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.For experiments on TUdataset (table 8 ), we chose a set of hyper-params by intuition (we didn't tune them because this experiment is to demonstrate the effectiveness of Schur layer and compare Schur layer with Linmaps under the same experiment setting. we don't aim to compare with Sota on this experiment). Hyper-params for both Schur Layer and Linmaps: num_layers = 4, rep_dim = 32,64, dropout = 0.5, batch_size = 32,128, lr = 0.01, num of channels = {2,4}, cycle sizes = 3,4,5,6. We're training with StepLR scheduler where reduce lr to 1/2 after every 50 epochs, with a total of 300 epochs. The hyperparams weren't tuned, we just chose a smaller value for a smaller dataset and a 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 [43] .Used Compute Resources Experiments are all run on one Tesla L4 from PyTorch Lightning Workspace and one NVIDIA RTX 4090. The code is implemented in PyTorch. For the running time, on the ZINC-12k dataset, it takes around 8.53 ± 1.2 hours to finish training for 1000 epochs with 4 layers and 128 dimension representation on an NVIDIA RTX 4090. We're running on a desktop with a Ryzen 7900 CPU and 64GB of RAM.A discussion of related work can be found in appendix C.The works[32,35] don't have results in those two dataset.Similar discussions could be found in Sectionof[41], but without a proof for necessity. 


Decision: 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.

Reviews: review: paper_summary: paper_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.]

[Maron et al.] Maron et al., Invariant and Equivariant Graph Networks NeurIPS 2019
strength_weakness: strength_weakness: 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. 

2. Other than the spectral convolution being permutation equivariant, there are no theoretical guarantees on its expressivity (in terms of Weisfeiler Leman or Subgraph GNNs.)
questions: 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: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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.
- 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.
- Experiments. The scope of the experiments is too narrow, being limited to the ZINC dataset without a robust set of baseline models for comparison.

Despite 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.
questions: questions: How were Schur layers implemented in the experiments? Was equation (8) simply applied to the features of the subgraphs?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Experimental Evaluation: Limited empirical evaluation on diverse datasets and benchmarks undermines broader applicability and comparison with existing methods.

2. 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.
questions: questions: 1. How does the computational complexity of Schur layers compare to traditional GNN approaches in terms of training time and memory usage?

2. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - **(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.
- **(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).
- **(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”).
- **(W4 - Quality)** The experiments are lacking:
	- **(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.
	- **(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).
	- **(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).


Overall, 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.
questions: questions: - **(Q1)** What is the (intuitive) meaning behind: Theorem 1, Theorem 2 and Theorem 3?
- **(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?


## Miscellaneous
- **(M1)** In my opinion, Table 5 is important enough to your narrative to warrant being in the main paper.
- **(M2)** Missing citation in line 186.
limitations: limitations: Yes

Comments: title: number of irreducible spaces
Concerns addresses; score raised
updated results table
Response
comment: Thank you for your response! For experimental validation on other (relatively large) datasets, please 
see our result on OGBG-MOLHIV (81.6+-0.295) as reported in the global rebuttal and the detailed results 
table posted to Reviewer EFuW. Further comments:

1. Thank you so much for bringing the [Babai et al., 1982] paper to our attention. Lemma 1 by itself is 
indeed almost trivial (that's why we called it a Lemma not a Theorem). However, the [Babai et al.] paper is still an important reference because it underlines the potential connection to the literature on graph isomorphism. Specifically, 
there might be results in that paper or follow-up publications that allow us to put a bound on the potential 
expressivity gap between the group theoretical and the spectral approaches. We will look into that and 
potentially add a discussion to the Appendix. Thank you!!

2. The intended message of our paper is that something which other papers 
attempted to do in a complicated way with irreducible representations etc., can be done (almost) equally 
well in a simple way using just the eigendecomposition. From this point of view, in our opinion, the fact that Lemma 1 
and Corollary 1 are technically simple is more of a strength rather than a weakness. 

We do appreciate your point about presentation, however. We certainly didn't mean to make the description of the group theoretic approach look more complicated than it needs to be, so we will will rework Sections 3 and 4 to make them as simple and readable as possible. We appreciate that for readers who are not already familiar with the group theoretic approach, 
Section 3 might be too dense, so we will add more background information in the Appendix 
and remove unnecessary details from the main body of the paper. We will also add a description of how Linamps (from [Maron et al., 2019]) work, and provide illustrative examples. 

3. Regarding the gap in expressiveness mentioned in your original review, please see the table in our new 
global comment comparing the number of invariant spaces produced by the group theoretical vs the spectral approach. 
We found that for the specific subgraphs we considered there is, in fact, no gap.
actually there is no gap.
We thank all the reviewers for their comments and the discussion that followed. Since several of you asked about the potential expressivity gap between the group theoretic and spectral approach, we decided to investigate this empirically for the subgraphs that we used (or considered using) in our experiments. The table below compares the number of invariant subspaces found using the two approaches for the first order case. The closer the number of spectral subspaces is to the number of subspaces found by the algebraic approach (which is the theoretical upper limit), the more expressive the Schur layers are. (The number of irreducible subspaces is computed by finding all irreps that occur in the action of $\textrm{Aut}_G$ on $\mathbb{R}^m$ and adding their multiplicities. This is easiest to do with character theory.)


| Graph                                       | Automorphism group | # of distinct eigenvalues (# of independent linear maps found by SchurLayer) | # of irreducible subspaces (# of linear maps found by group theoretic approach) |
|---------------------------------------------|--------------------|-----------------------------------------------------------------|-----------------------------------------------------------------|
| 6-cycle                                     | $D_6$                | 4                                                               | 4                                                               |
| 5-cycle                                     | $D_5$                | 3                                                               | 3                                                               |
| 4-cycle                                     | $D_4$                | 3                                                               | 3                                                               |
| 3-cycle                                     | $D_3$                | 2                                                               | 2                                                               |
| 5-star                                      | $S_4$                | 3                                                               | 3                                                               |
| 4-star                                      | $ S_3 $               | 3                                                               | 3                                                               |
| 3-path                                      | $S_2$                | 3                                                               | 3                                                               |
| n-cliques                                   | $ S_n $               | 2                                                               | 2                                                               |
| 5-cycle with one branch                     |  $S_2$                | 6                                                               | 6                                                               | 

Remarkably, we see that there is in fact no gap between the algebraic and the spectral approach! We are very intrigued to find some class of subgraphs for which there is a gap and to characterize that class. We are currently working on this topic. 

Please note that for the baseline case of full $S_m$ equivariance there would only be two linear maps in each case. Also note that due to the way that product representations work, when there is no gap for a given subgraph in the first order case, there would be no gap in higher order cases either.

Once again, thank you for your careful reading of our paper and all your suggestions on how to improve it!
I thank the authors for their answers and the thorough rebuttal. The additional experiments clearly strengthen this paper (especially the performance on MOLHIV). Furthermore, I find the explanations of the theorems really intriguing and am looking forward to seeing visualizations of them. Overall, if the authors manage to improve their explanations I am not against acceptance and have thus increased my score accordingly.
Overall, using the eigen decomposition to produce equivariant functions is novel and is a standard operation for GNNs. The empirical results are non-marginal. Score raised to 7.
I appreciate the detailed rebuttal; however, my concerns regarding the paper persist. Primarily, the paper's presentation requires refinement. The theoretical sections (Section 3 and the initial part of Section 4) are hard to follow, and their connection to the proposed Schur layer is ambiguous. I recommend that the authors condense these sections to include only essential results. Additionally, the paper's theoretical contributions appear limited. Lemma 1, which seems rather obvious, is essentially Lemma 3.1 from [1], and Corollary 1 is a direct consequence of Lemma 1. Although Theorem 3 extends this to higher-order equivariance, it lacks experimental validation. I would also advise the authors to perform more experiments on larger datasets beyond the TU datasets. For these reasons, I am inclined to retain my original score.

[1] Babai, L., Grigoryev, D. Y., & Mount, D. M. (1982, May). Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing (pp. 310-324)..
Please find the updated Table 5 below:

| Model                          | ZINC-12K MAE (↓) | OGBG-MOLHIV ROC-AUC(% ↑) |
|--------------------------------|------------------|--------------------------|
| GCN [Kipf and Welling, 2017]    | 0.321 ± 0.009    | 76.07 ± 0.97             |
| GIN [Xu et al., 2019]           | 0.408 ± 0.008    | 75.58 ± 1.40             |
| GINE [Hu et al., 2020]          | 0.252 ± 0.014    | 75.58 ± 1.40             |
| PNA [Corso et al., 2020]        | 0.133 ± 0.011    | 79.05 ± 1.32             |
| HIMP [Fey et al., 2020]         | 0.151 ± 0.002    | 78.80 ± 0.82             |
| CIN [Bodnar et al., 2021]       | 0.079 ± 0.006    | 80.94 ± 0.57         |
| DS-GNN (EGO+) [Bevilacqua et al., 2022] | 0.105 ± 0.003    | 77.40 ± 2.19             |
| DSS-GNN (EGO+) [Bevilacqua et al., 2022] | 0.097 ± 0.006    | 76.78 ± 1.66             |
| GNN-AK+ [Zhao et al., 2022]     | 0.091 ± 0.011    | 79.61 ± 1.19             |
| SUN (EGO+) [Frasca et al., 2022] | 0.084 ± 0.002    | 80.03 ± 0.55             |
| First order P-tensors  [Hands et al., 2024] | 0.071 ± 0.004 | 80.76 ± 0.82         |
| **Schur-Net (ours)**            | **0.064 ± 0.002** | **81.6 ± 0.295**         |
Thanks so much for the quick response to our rebuttal.

1. For cycles the relevant group is not the cyclic group but the dihedral group, which is a little bit more complicated because it also has some two dimensional irreducible representations.  Table 4 shows that adding cycles with {1,2,3} branches hanging off them can improve performance, and here the automorphism group is different (see the paragraph titled "Flexibility" in the Experiments section). Without the Schur layer formalism we would have to work out the irreducible representations of all of these group separately by hand. However, for the "production run" used to generate the results of Table 5, we ended up just using cycles, so you make a fair point. 

 Our primary goal with the paper was to develop the general machinery for automorphism group aware message passing in higher order subgraph neural networks. then. After we have done that and wrote the corresponding software, we started working on validating the approach, trying to show that adding automorphism-group aware operations can improve the state-of-the-art in empirical results on benchmark datasets. What we had in mind was adding subgraphs corresponding to actual functional groups. 

  We found that just by adding cycles we can already beat the other papers on ZINC 12K (with the exception of [Feng et al.] which you kindly pointed out but we didn't know about). In addition to branched cycles, we also did some experiments on star-shaped subgraphs for example, but in terms of producing results for this conference deadline we just concentrated on cycles in the end because that seemed like the most direct path to competing with the other algorithms. Our longer term goal is to explore much more adventurous applications of this framework. 

  In summary, you are right, if all that we were interested in were cycles and first order message passing, then we could have developed an architecture specialized to just that and that would have been easier maybe. It would probably be a rather incremental contribution to the field, though.

3. We wish it were just the eigenvectors that need to be cached. The main technical difficulty in GNNs is parallelizing the message passing step on the GPU, given that the graph structure is not regular. Most of the community uses PyTorch Geometric, which solves this problem for classical message passing GNNs by reducing the message passing step to one big "scatter" operation. The problem with using this for higher order message passing is that in architectures like ours for a given pair of sending and receiving subgraphs, the exact form of the message passing map between them depends on how many vertices they have in common and which vertices those are. So effectively the message passing operation is different for each pair of (sending, receiving) subgraphs.

  To solve this problem and be able train our model at a comparable speed to other GNNs, we had to write specialized CUDA kernels and ultimately a separate library. The kernels take as input the source subgraph-layer, a data structure specifying which subgraph communicates with which subgraph (in most of our experiments this is just determined by whether they overlap or not), as well a data structure that specifies for each pair of (source,destination) subgraphs which vertices they share. The latter two data structures are relatively expensive to compute because they need to be created on the CPU so it makes sense to cache them (on the GPU). This is what can lead to memory issues. It also complicates the batching process, because unlike in PyTorch Geometric, we can't just batch the graphs by merging them into one big graph. We are working on relieving the memory issue by updating the library so that it can move these data structures in and out of GPU memory flexibly, but using a preloading strategy so as to hide the latency of the memcpy calls. The overall goal is that the library should make higher order GNNs just as easy to use as regular message passing networks, hiding all these details on the backend. We should also not that the library can also do second order message passing as described in Theorem 3, we just haven't had a chance to experiment with that yet.

----

I don't think we can submit pdf's at this stage, but we will compile the additional results in table format and share them soon.
I highly appreciate your detailed rebuttal.

1. What I'm missing is that if you only restrict to automorphisms of cycles and other simple subgraphs, isn't it computationally feasible to know the decomposition into irreducible representations? Isn't it the decomposition of the representation of the cyclic group acting on the vectors on the subgraph (`neuron')?

2. Thank you for the clarification. Yes, upon looking it over again the number of linear equivariant mappings you have is always larger as the automorphism group of the subgraph is a subgroup of $S_m$, where $m$ is the subgraph size.

3. "cache a variety of control data structures on the GPU": By this you mean the eigendecompositions of the subgraphs?

4. I agree with the comment re [Feng et al.].


I'm still debating whether this merits a score increase. is it possible to put together all the experimental results in a more readable format like a pdf? Or just a reply that is succinct with highlights from the best experimental claims you think from both the paper and rebuttal.

Thank you