Local Permutation Equivariance For Graph Neural Networks
Authors: Joshua Mitton
Roderick Murray-Smith
Venue: ICLR 2022 Submitted (2022)
Keywords: Graphs
Equivariance
Permutation Equivariance
Graph Neural Networks
Representations

Abstract: In this work we develop a new method, named {\it locally permutation-equivariant graph neural networks}, which provides a framework for building graph neural networks that operate on local node neighbourhoods, through sub-graphs, while using permutation equivariant update functions. The potential benefits of learning on graph-structured data are vast, and relevant to many application domains. However, one of the challenges, is that graphs are not always of the same size, and often each node in a graph does not have the same connectivity. This necessitates that the update function must be flexible to the input size, which is not the case in most other domains.

Using our locally permutation-equivariant graph neural networks ensures an expressive update function through using permutation representations, while operating on a lower-dimensional space than that utilised in global permutation equivariance. Furthermore, the use of local update functions offers a significant improvement in GPU memory over global methods. We demonstrate that our method can outperform competing methods on a set of widely used graph benchmark classification tasks.

Under review as a conference paper at ICLR 2022
LOCAL PERMUTATION EQUIVARIANCE FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In this work we develop a new method, named locally snnnutatioo-euivvriin graph neural networks, which provides a framework for building graph neural networks that operate on local node neighbourhoods, through sub-graphs, while using permutation equivariant update functions. Message passing neural networks have been shown to be limited in their expressive power and recent approaches over come this either lack scalability or require structural information to be en- coded into the feature space. The general framework presented here overcomes the scalability issues associated with global permutation equivariance by operating sub- -ab-graahs through restricted representations. In addition, we prove that there is no loss of expressivity by using restricted representations. Furthermore, the pro- posed framework only requires choice of k-hops for creating sub-graphs and choice of representation space to be used for each layer, which makes the method easily applicable across a range of graph based domains. We experimentally vali- date the method on range of graph benchmark classification tasks, demonstrating either state-of-the-art art results or very competitive results on all benchmarks. Fur- ther, we demonstrate that the use of local update functions offers significant improvement in GPU memory over global methods.
INTRODUCTION
Many forms of data are naturally structured as graphs such as molecules, bioinformatics, social, or financial and it is therefore of interest to have algorithms which operate over graphs. Machine learning on graphs has received much interest recent years, with the general framework of a message passing network providing both a useful inductive bias and scalability across range of domains (Gilmer et al. 2017). However, Xu et al. (2019) show that a model based on a message passing framework with permutation invariant aggregation functions is limited in expressive power. Therefore, there exists many non isomorphic graphs that a model of this form cannot distinguish between. Figuresjdemonssraates two non-isomorphic graphs for which message passing framework with max pooling would not be able to distinguish between the two graphs.
More expressive graph networks exists and common measure of expressivity is the Weisfeiler- Lehman (WL) test. One such method of building more expressive networks is based directly on the WL test. Here a neural network architecture is built based on variants of the WL test. [Bouritsas al. (020) use a permutation invariant local update function, but incorporate permutation equivariant structural information into the feature space. Morris al. (2019a) build models based on different WL variants that consider local and global connections. Bodnar et al. (2021b) introduce WL test on simplicial complexes and incorporate this into message passing scheme. Bodnar al, (2021a) extend work on simplicial complexes to cell complexes, which subsume simplicial complexes.
On the other hand, rather than trying to directly incorporate techniques from WL. tests directly into networks other model make use of permutation symmetries to build permutation equivariant graph neural networks (Maron et al. 2018). This model can be built for k-order feature spaces and was shown by Maron et al. (2019) that such models can distinguish between non-isomorphic graphs as well as the kL test. Natural graph networks are a different class of graph neural network, where the constraint placed upon the linear layer is that of naturality (de Haan et al.) 2020). The naturality constraint says that for each isomorphism class a map must be chosen that is equivariant to automorphisms.

---

Under review as a conference paper at ICLR 2022
Degree Subgraphs
Boo
Degrev Subgrapis
Degree 2 Subgraphs
Engut Gruph
Spiit Graph Subgraphs
Perform Convolation
Reinsert Sub-grighh
Output Graph
Figure I: The architecture of layer in a locally permutation equivariant graph network is presented. combines a method of splitting the input graph into sub-graphs, the chosen method of weight sharing, permutation representations as update constraints, and the reconstruction of the graph. In the layer presented here the sub-graph is created by selecting nodes that are 1-hop away from the central update node. The weight sharing scheme involves sharing weights across sub-graphs of the same size. The update of node and graph features makes use permutation representations.
In general the task of learning on graphs consists of utilising many graphs of different sizes. Cur- rent methods for utilising permutation equivariant graph neural networks require that the graph be represented as an adjacency tensor, which limits there scalability. Furthermore, global natural graph networks also perform computations on entire graph features, which leads to a large computational complexity for large graphs. Local gauge symmetries have been considered to build models with local equivariance (Cohen al. 2019). This approach improves scalability of models by utilising local update functions, however for graphs we do not have a single local symmetry. Currently this overcome in the majority of graph neural networks presented by utilising some form of message passing, but, in general, all works use permutation invariant aggregation function leading to good scalability but poor expressivity. Local natural graph networks attempt to overcome the limited pressivity through placing a local naturality constraint on the message passing and having different message passing kernels on non-isomorphic edges.
Through considering graph neural networks from an elementary category theory perspective and making use of aspects of group theory we present a framework for building local permutation equiv- ariant models. This allows to build graph neural network model with local update functions that are permutation equivariant by considering restricted representations of the representation space of the whole graph. Further, prove that this does not cause a loss of expressivity of the model and that this maintains the option to have k-order feature space that ensures expressivity equal k-WL test. Also, by constraining the kernel space under restricted representations, natural weight sharing scheme becomes apparent, namely sharing weights across local graph neighbourhoods of the same degree. The approach of building models with framework based group theory makes clear the generality of the approach, where choices of representation space can be made for each convolu- tional layer without requiring prior information such structural information be encoded into the feature space. This framework can also be shown to include other leading methods as specific cases.
BACKGROUND
2.1
GRAPH NETWORKS
Different graph neural networks express graphs in alternative forms. Generally, for message pass- ing model, a matrix of node features and a matrix of edge features is combined with a sparse edge index array specifying the connectivity of the graph. In other works, the graph is provided in dense format, where the graph is given as a adjacency tensor with node and edge features held in one tensor. In this work we present the graph follows:
Definition A Concrete Graph is a finite set of nodes V(G) C. N and a set of edges { C V(C) x (G).
2

---

Under review as a conference paper at ICLR 2022
The set of node ids may be non-contiguous and make use of this here extract overlapping sub graphs when performing the local updates. The same underlying graph can be given in may forms by permutation of the ordering of the natural numbers of the nodes.
Definition 2 A sub-Concrete Graph H is created by taking node i E V(G), and extracting the nodes; V(G) and edges (i.3) C V(G) V(G), such that there is a connection between nodes i and j.
Once a sub-concrete graph has been extracted, this same underlying sub-graph could be expressed through different permutations of the underlying numbering of the nodes. For brevity we refer to sub-concrete graphs as subgraphs throughout the paper.
Definition 3
A Graph isomorphism, & G G' is a bijection between the vertex sets of two graphs G and G", such that two vertices u and v are adjacent in G if and only if (()) and ((v) are adjacent in G". This mapping edge preserving, i.e. satisfies for all (i.5) V(G) V(G):
(i,5) E E(G) = (oli, (o()) E E(G))
An isomorphism from the graph itself is known as an automorphism.
Relabelling of the graph by permutation of the nodes is called graph isomorphism, where an example two isomorphic graphs is given in Figure We desire that the linear layers of the graph neural network respect the composition of graph isomorphisms. This requires us to define the feature space of the graphs and how feature spaces of isomorphic graphs are related.
2.2 PERMUTATION REPRESENTATIONS
The feature space of the graphs is vector space V, where a representation of the group G is homomorphism p G GL(V) of G to the group of automorphisms of V (Fulton & Harris 2013). map KG between two representations of G a vector space map. The elements of the group g G can act vector V by the representation matrix - p(g)r. The symmetric subspace of the representation is the space of solutions to the constraint vgg E G p(g) = v. Here considering the symmetries of the symmetric group S,,. This constraint can be solved for different order representations (Maron et al.] 2018 Finzi et al. (021). We present the space of linear K -order representations in Figure 2 In addition,
layers mapping from k-order representations for the linear map Kg. we require that if a graph is passed through Kg and then transformed by permutation
isomorphic graph this result is the same as if a graph transformed by the same permutation to an isomorphic graph and then passed through Kg. In short, this requires that permutation equivariance is satisfied.
2.3 CATEGORY THEORY
This section does not provide a complete overview of category theory, nor even a full introduction, but aims to provide a sufficient level of understanding to aid the reader with further sections of the pa- per, where we believe presenting the comparison between models from a category theory perspective makes more clear the distinctions between them. A category, C, consists of set of objects, Ob(C), prreeurrrrreeeiinggg mappings) or arrows, f A + B, A, B Ob(C).
and a set of morphisms There is a binary operation on morphisms called composition. Each object has identity mor- phism. Categories can be constructed from given ones by constructing a subcategory, in which each object, morphism, and identity is from the original category, by building upon category, where objects, morphisms, and identities are inherited from the original category. A functor is a mapping from one category to another that preserves the categorical structure. For two categories C and D a functor C 'D maps each object A E Ob(C) to an object F(A) E Ob(D) and maps each morphism f A + B in C to a morphism F(A) F(B) in D.
Definition& 4 A groupoid is a category in which each morphism is invertible. A groupoid where there only one object is usually a group.
3

---

Under review as a conference paper at ICLR 2022
Po - Po
P1 + P1
P2 + P2
I
1
PO Pi
PO P2
P1 P2
P1 + Pb
P2 Pb
P2 P1
Figure 2: Bases for mappings and from different order permutation representations, where Pk k-order representation. Each color in a basis indicates a different parameter. > Po is mapping from O-order representation level label, and has learnable parameter. P1 + 01 is mapping from a 1-order representation to 1-order representation, i.c. a node level label node level label, and has 2 learnable parameters, one mapping node features to themselves and the other mapping node features to other nodes. Further, there are mappings between different order representation spaces and higher order representation spaces.
0-order representation, i.e. graph level label to graph
3 GLOBAL EQUIVARIANT GRAPH NETWORKS
3.1 GLOBAL PERMUTATION EQUIVARIANCE
Global permutation equivariant models have been considered by Hartford et al. (2018); Maron et al. 2018 2019); Alboooych et al. (2019). with Maron et al. (2018) demonstrating that for order-2 layers there are 15 operations that span the full basis for an permutation equivariant linear layer. These 15 basis elements shown in Figure with each basis element given by different color in the map from representation P22 - P2- Despite these methods, when solved for the entire basis space, having expressivity as good as the k-WL test, they operate the entire graph. Operating on the entire graph features limits the scalability of the methods. In addition to poor scalability, global permutation appears to be strong constraint to place upon the model. In the instance where the graph is flattened and an MLP is used to update node and edge features the model would have n trainable parameters, where the number of nodes. On the other hand, a permutation equivariant update has only 15 trainable parameters and in general 15 & n
Viewing global permutation equivariant graph network from category theory perspective there is one object with collection of arrows representing the elements of the group. Here the arrows or morphisms go both from and to this same single object. The feature space a functor which maps from a group representation to vector space. For global permutation equivariant model the same map is used for every graph.
g1
Symmetric Group
4

---

Under review as a conference paper at ICLR 2022
3.2 GLOBAL NATURALITY
Global natural graph networks (GNGN) consider the condition of naturality, (de Haan et al. 2020 GNGNs require that for each isomorphism class of graphs there is a map that is equivariant to automorphisms. This naturality constraint is given by the condition p'()) KG K p()), which must hold for every graph isomorphism 6 G G G' and linear map Kg. While the global permutation equivariance constraint requires that all graphs be processed with the same map, global naturality allows for different, non-isomorphic, graphs to be processed by different maps and as such generalisation of global permutation equivariance. As the case for global permutation equivariant models, GNGNs scale poorly as the constraint is placed over the entire graph and linear layers require global computations the graphs.
Viewing a GNGN from a category theory perspective there is a different object for each concrete graph, which form groupoid. Then, there mosphism or arrow for each graph isomorphism. These can either be automorphisms, if the arrow maps to itself, or isomorphisms if the arrow maps different object. The feature spaces are functors which map from this graph category to the cat- egory of vector spaces. The GNG layer is a natural transformation between such functors consisting of different map for each non-isomorphic graph.
G2
G3
Groupoid of Concrete Graphs
4 LOCAL EQUIVARIANT GRAPH NETWORKS
Local equivariant models have started receive attention following the successes of global equiv- ariant models and local invariant models. The class of models that are based on the WL test are not in general locally permutation equivariant in that they still use message passing model with permu- tation invariant update function. Despite this, many of these models inject permutation equivariant information into the feature space, which improves the expressivity of the models (Bouritsas al.) 2020 Morris et al. 2019a Bodnar et al. 2021b a). The information to be injected into the feature space is predetermined in these models by a choice of what structural or topological information to use, whereas model uses representations of the permutation group, making it very general model that still guarantees expressivity.
In contrast to utilising results from the WL test covariant compositional networks (CCN) look permutation equivariant functions, but they do not consider the entire basis space as was considered in Maron al. (2018) and instead consider four equivariant operations (Kondor et al. 2018). This means that the permutation equivariant linear layers are not as expressive as those used in the global permutation equivariant layers. Furthermore, in a CCN the node neighbourhood and feature dimen- sions grow with each layer, which can be problematic for larger graphs and limits their scalability. Another local equivariant model is that of local natural graph networks (LNGN) (de Haan et al.) 2020). An LNGN uses a message passing framework, but instead of using permutation invari- ant aggregation function, specifies the constraint that node features transform under isomophisms of the node neighbourhood and that a different message passing kernel is used non-isomorphic edges. practice this leads little weight sharing graphs that are quite heterogeneous and as such the layer is re-interpreted such that message from node p node g. Ep. is given by function k(G Up) of the edge neighbourhood Gpu, and feature value Up at p.
Viewing LNGN from category theoretic perspective there is groupoid of node neighbourhoods where morphisms are isomorphisms between node neighbourhoods and a groupoid of edge neigh- bourhoods where morphisms are ismorphisms between edge neighbourhoods. In addition, there is a functor mapping from edge neighbourhoods to the node neighbourhood of the start node and a functor mapping similarly but to the tail node of the edge neighbourhood. The node feature spaces
5

---

Under review as a conference paper at ICLR 2022
functors mapping from the category of node neighbourhoods to the category of vector spaces. Further, composition of two functors creates mapping from edge neighbourhoods to the category of vector spaces. A LNG kernel is natural transformation between these functors.
N1
N2
E1
E2
N3
E3
Groupoid of Node Neighbourhoods
Groupoid of Edge Neighbourhoods
LOCAL PERMUTATION EQUIVARIANCE
local permutation equivariant graph network (LPEGN) improves upon the scalability of global permutation equivariant models by considering permutation equivariance at lower scales. Here, instead of performing the update function on the entire graph, we perform the update function on node neighbourhoods as is done in message passing models. Furthermore, while performing the update functions on node neighbourhoods, we maintain improved expressivity through using k- order permutation representations. The intuition behind imposing permutation equivariance node neighbourhoods rather than the entire graph is that the model can learn expressive features about a part of the sub-graph without requiring knowledge of permutations multiple hops away from the central update node. This framework generalises global permutation equivariant models as it is compatible with all length scales, meaning that, if the graph structure is used determine node neighbourhoods, then any k value can be chosen to determine the k-hops from the central update node producing the sub-graph which permutation equivariance is required for. Therefore, if the value chosen for the k-hops is sufficiently large then the layer becomes global permutation update. The basis functions for different order representation spaces are given with the split into different degrees for 1-hop node neighbourhood in Figure [ The method therefore requires a choice of k for the number of hops away from the central node consider in the local update and we discuss this choice in Section 5.2 In addition, the framework then allows for choice of weight sharing. which we discuss in Section
5.1 RESTRICTED REPRESENTATION
Given a graph comprised of n nodes, global equivariant models consider the permutation representation of the permutation group G > GL(R"). Here we
G c= S., namely the representation consider local updates on sub- sub-graphs with nodes, where we are interested in the sub-group H Sm. < Sn. Therefore we can consider the restricted representation of the sub-group Sn, where the restricted representation can be seen as dropping some symme- tries from the group S,. The restricted representation is denoted by 7 = Res (p) H - GL(R"). The global equivariance case using representations, p. and the case using restricted representations, are shown in Figure 3 Both figures show basis mapping from order 1 to order permutation representation. The restricted repre- sentation Ress: drops the permutation symmetry associated to node 5. Dropping the permutation
(a)
(b)
Figure 3: (a) Regular repre-
sentation. (b) Restricted rep-
resentation.
symmetry of node 5 results in additional parameters, one for the update of node 5 based on node 5's features, another for the update of node 5 based the features of the other nodes in the graph, and final parameter for the update the other nodes in the graph based on node 5's features. We proove that using restricted representations in framework has no loss of expressivity in Appendix A.8

---

Under review as a conference paper at ICLR 2022
5.2 CHOICE OF LOCAL NEIGHBOURHOOD
The LPEGN model framework performs the permutation equivariant update on local sub-graphs, although choice can be made as to how these sub-graphs are created. One option is the use the underlying graph structure and choose k value to extract local neighbourhoods that include nodes which are at most k-hops from the central node. This method creates sub-graph for each node in the graph. Here the choice of the & value can be seen as choosing length scale for which the permutation symmetry should be exploited over. In other words, choosing a value of k = is the shortest length scale and node features will be updated such that they are permutation equivariant to their 1-hop neighbours, but not equivariant to nodes further away in the graph. On the other hand, choosing a & value sufficiently large will create model equivalent to global permutation equiv- ariant models, where each update is permutation equivariant to permutations of the entire graph. Throughout this work we choose k unless otherwise stated to take the most local permutation equivariant updates. We show how this choice of k value will impact the method through analysing the MUTAG dataset in Figure 10
5.3 CHOICE OF WEIGHT SHARING
In general when constructing the sub-graphs variety of different sized sub-graphs are found due to differing degrees of the nodes in the graph. This allows for a further choice, namely the weight sharing method be used. Given that the permutation equivariance constraint is strong constraint to place over the linear layers, we perform weight sharing across sub-graphs of the same size, This means that sub-graphs of different sizes do not share weights and can be updated differently. The intuition for this is that tub-graphs of the same size already have some similarity in that they are of the same size, while sub-graphs of a different size are less likely to be similar and hence should be updated differently. Throughout this paper we choose to use weight sharing across local neighbour- hoods of the same size degree, although in situations where there is very few local neighbourhoods of particular size we group these together.
5.4 CHOICE OF REPRESENTATION SPACE
In Section 5.1 we considered the restricted representation of sub-group Sm S. Sn and in Section 5.2 we detailed how local sub-graphs are selected. Here we must make a connection between the two to present the representational space used in our LPEGN framework. When focusing in on the nodes that we didn't 't drop the permutation symmetry of it can be seen, in Figure that for these nodes the restricted representation is equivalent to the global permutation equivariant representation. Further- more, given our choice of sub-graph construction we would seek to drop the permutation symmetry from a node in the graph due to the fact it is not connected to the central update node. Therefore the dropping the permutation symmetry
edge features connecting the central node to the node of are zero. Hence, we are not interested in the additional parameters introduced in the restricted representation connecting the two nodes. Furthermore, the node we are dropping permutation symmetries for is not connected to the chosen sub-graph we are also not interested in the additional parameters introduced in the restricted representation for this node. As result, due to the choice of sub-graph construction, the restricted representation for our sub-group has zero features in the position of new parameters introduced and is therefore equivalent to the permutation representa- tion on a lower dimensional space. Therefore where global permutation equivariant updates use representations p : G - (R*) our local permutation equivariant model uses representations i H - (RR), where ē S c. The scheme for creating representations of local neighbourhoods shown in Figure where some representations of the local neighbourhoods are shown.
5.5 LOCAL PERMUTATION EQUIVARIANT GRAPH NETWORK
A LPEGN combines the chosen method of creating sub-graphs as local neighbourhoods with a choice of weight sharing scheme and makes use of permutation representations these sub-graphs. The process of creating sub- aub-graphs, updating based on the choice of weight sharing using permuta- tion representations, and re-constructing the graph structure is presented in Figure
Viewing a LPEGN from a category theoretic perspective, each different size node neighbourhood is sub-group, H, which is different object. There are morphisms or arrows for each permutation
7

---

Under review as a conference paper at ICLR 2022
of the neighbourhood. This forms groupoid. The sub-group representations are functors from the category node neighbourhoods to the category vector spaces.
h
H1
H
H3
ha
ha
Groupoid of Symmetric Sub-Groups
6 EXPERIMENTS
6.1 GRAPH BENCHMARKS
We tested our method on a series of 7 different real-world graph classification problems from the benchmark of (Yanardag & Vishwanathan 2013). It is noteworthy point out some interesting features of each dataset. We note that both MUTAG and PTC are very small datasets, with MUTAG only having 18 graphs in the test when using 10 % testing split. Further, the Proteins dataset has the largest graphs with an average number of nodes in each graph of 39. Also, NCII and NCI109 are the largest datasets having over 4000 graphs each, leading to less spurious results. Finally, IMDB- and IMDB-M generally have smaller graphs, with IMDB-M only having average number of 13 nodes in each graph. The small size of graphs coupled with having classes appears to make IMBD-M challenging problem.
Table compares our LPEGN model to range of other methods. This highlights that our method achieves a new state-of-the-an result on the NCI1 dataset and is the second strongest on PTC and NC1109. Furthermore, our method performs competitively across all datasets. We achieve a poor ranking score the Proteins datasets, although the classification accuracy of the model is competi- tive with leading results and only falls slightly short the bulk of other methods. A comparison of the distribution of training accuracy is presented in figure & and ranking based method is presented in Figure 9
Table 1: Comparison between our LPEGN model and other deep learning methods from de Haan al. 2020). Larger mean results are better.
Dataset
MUTAG
FTC
PROTEINS
NCI1
NC1109
IMDB-B
IMDB- M
size
188
344
1113
4110
4127
1000
1500
classes
2
2
avg node
17.9
25.5
39.1
29.8
29.6
19.7
13
Results
GDCNN
Zhane et al.
2018
85.8+1.7
58.6#2.5
75.5++0.9
74.4+005
NA
70.0++0.9
47.8=0.9
PSCN
Naspett
2016
89.0:24.4
62.31:5.7
75:22.5
76.31:17
NA
71:223
45.2=28
DCNN
[Atwood & Low sky
2016
NA
NA
61,3+116
56.61100
NA
19.1#114
33.5 1.4
DGK
Yanariag
Visawannaliam 2013
87.4
60.1
75.7:10.55
80.310.5
80.3
67.0.0066
14.5
Ying
CCN
(Kondir ail 2018
91 6-7.2
70.6=7.0
NA
76344.1
75.5334
NA
NA
JGN
Maron et 2018
83.9-:13.0
68.5
76.6+:555
74.34:27
728-1.
72.045.5
48.7=3.4
GIN
2019)
$9.41.5.6
64.617:00
76.2:12.88
82.71177
NA
75.1
$2.3-288
1-2-3'GNN GNN Morms ot al 2019b
86.1
60.9
75.5
76.2
NA
74.2
49.5
90.518.77
66.2
77.2:1-.7
83.24:11
81.
72.6:1499
$01:3.2
PPGN
Marun ei
2119
88.917.4
64.7.7..5
76.4.15.0
81.2121
818
72.2.14.3
44.717.9
Maron al
2119
89.41..1
62.917.0
76.7455.6
81.0-11.9
82.2-14
LNGN
(GCN) de Haln
2020
89.4+1.6
66.8=118
71.7+11.0
82.7+14
83.0=199
74.8+2200
51.3=155
GSN-e
Bouritsus ei 2020
90.6:t7.5
68.277.2
76.6:t5..0
83.54:23
NA
77.8-13.3
54.3=3.3
GSN
92.21..55
67.
74.6.1..0
83.5120
NA
76.8.12.0
3..6
SIN
Beditar al.
4021
NA
76.5413.4
82.812222
NA
75.6:13.22
32.5
al
92.716.1
$2.7
LPEGN
89,5+6.11
70.0::11.3
74.5++233
83.7--55 1st
83.2=0.8
74.3::3.77
47.9=3.00
Best Runk
6th
2nd
15th
2nd
10th
8

---

Under review as a conference paper at ICLR 2022
6.2 SCALABILITY
We compare global permutation equivariant models with our local permutation equivariant model assess the improvements in scalability offered by local permutation equivariance. Here we com- pare the GPU memory required by the model against the average size of graph in the dataset. expected that as the computational cost of global methods scales superlinearly with the size of the graph, due to the requirement to treat the entire graph as a single adjacency tensor, that local equivariance will have lower computational cost as each update only requires local node neigh- bourhoods to be expressed as adjacency tensors, which are typically much smaller than the size of graph. Therefore global methods scale with (n*)), ), for graphs with a nodes, while local meth- ods scale with (nn=²) where m is the number of nodes in node neighbourhood and typically m < n. Figure 4 shows how global and local permutation equivariant models scale with GPU memory usage the average size of the graphs in the dataset increases. This will allow the LPEGN method to scale to graph datasets that was not possible with global equivariance.
Equivariance
20
Local Equivariance
15
20
10
20
30
40
Average Number
Computational cost of global and local permutation equivariant models with the same number of model parameters for datasets with varying average size graphs. For the local equivari- ance case local neighbourhoods were computed using 1-hop neighbourhoods.
Figure 4:
FUTURE WORK
From Table it is clear that IMDB-M is a dataset for which our method has weaker performance. As stated in Section A.3 between hidden local equivariant graph neural network layers for the exper- iments in this paper we only make use of order 1 and 2 representations. As it was shown by Maron al. (2019) that increasing the order of the permutation representation increases the expressivity inline with the WI test, the expressivity of our method could be improved through the consider- ation of higher order permutation representations. Making use of higher order representations, we believe, would improve results on the IMBD-M dataset and therefore makes for an interesting future direction.
CONCLUSION
We present graph neural network framework for building models comprising of local permutation equivariant update functions. The method presented is general in that it presents a framework for op- erating on sub-graphs with permutation equivariant convolutions, where choice of representation space can be made depending on the expressivity required. This maintains expressivity in the update functions by utilising restricted representations, while improving scalability over global permutation equivariant methods by operating on smaller sub-graphs. We show that this method includes many previous published approaches specific cases. Using a general approach as our framework does makes it casier to build provably expressive graph neural networks without the need to embed struc- tural information about the task at hand, as is done in other methods. Further, we experimentally validate the method using & = 1 to create the sub-graphs and @ P2 representations for the lo- cal update functions on set of graph classification datasets. This model produces state-of-the-art results one of the datasets, achieves second best results two datasets, and is competitive on the remaining four. In addition, ranking the model against existing methods on each dataset shows that method is one of the strongest performing methods. Furthermore, when compared global permutation equivariant models our method offers a significant improvement in terms of the GPU memory usage, improving the scalability of the method.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Marjan Albooyeh, Daniele Bertolini, and Siamak Ravanbakhsh. Incidence networks for geometric deep learning. arXiv preprint arXiv:1905.11460, 2019.
James Atwood and Don Towsley. Diffusiinn-oonollttinnal neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: CW networks. arXiv preprint arXiv:2106. 12575, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. arXiv preprint urXiv:2103.03212, 2021b.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09255, 2020.
Taco Cohen, Maurice Weiler, Berkay Kicanaoglu, and Max Welling, Gauge equivariant convolu- tional networks and the icosahedral CNN. In International Conference on Machine Learning, pp. 1321-1330. PMLR, 2019.
Pim de Haan, Taco S Cohen, and Max Welling. Natural graph networks, In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3636-3646. Curran Asso- ciates, Inc., 2020. URL,
newrinnerriee httplps..ppppppppppe cc//papprr/220/Ffiee .pdff
2517756c5a www.ebbbbbb0ee.. hat.aa/eeeeeaaeeeeeeeeeeee771111
Mare Finzi, Max Welling, and Andrew Gordon Wilson. practical method for constructing equiv- ariant multilayer perceptrons for arbitrary matrix groups. arXiv preprint arXiv:2104.09450 2021.
William Fulton and Joe Harris. Representation theory: firstst course, volume 129. Springer Science & Business Media, 2013.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing for Quantum Chemistry, In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume Volume 70, pp. 1263-1272, 2017.
Jason Hartford, Devon Graham, Kevin Leyton- Brown, and Siamak Ravanbakhsh. Deep models of interactions across sets. International Conference on Machine Learning, pp. 1909-1918. PMLR, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02907 2016.
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, and Shubhendu Trivedi. Covariant compositional networks for learning graphs. arXiv preprint a0Xiv 2018.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference Learning Representations, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In H. Wallach and H. Larochelle and A. Beygelzimer and F. d'Alché-Buc and E, Fox and R. Garnett (ed.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL httphttsss/prrccedagss..oot
pddf
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. arXiv preprint 1rXiv:1904.011 2019a
10

---

Under review as a conference paper at ICLR 2022
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 4602-4609, 2019b.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3693-3702, 2017.
Keyulu Xu, Weihua Hu. Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019. URL https: //openreview
61 A5Km
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM
SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1365-1374, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in neural infor- mation processing systems, pp. 4800-4810, 2018.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelli gence, volume 32, 2018
A
APPENDIX
A.1
ISOMORPHIC GRAPIIS
An example of two isomporhic and two non-isomorphic graphs are shown in Fi To permu- tation invariant message passing update function utilising max pooling aggregation function the isomorphic and non-isomorphic graphs are equivalent when updating the central node.
Isomorphic
Non Isomorphic
Figure 5: The initial graph on the left is isomorphic to the top graph on the right. On the other hand, the initial graph on the left is non-isomorppic the bottom graph on the right. This is because there is no structure preserving mapping that has an inverse between the two graphs.
A.2 MATHEMATICAL BACKGROUND
Definition 5 A group is set G with binary operation satisfying the following laws:
(GO) (Closure law): For all g, h E G. g
(GI) (Associative law):
(h o k)
(g o h) k for all g, h, G
(G2) [ldentity law): There exists e E G such that o = 60 g = g for all E
(G3) (Inverse law): : For all g G, there exists h E G with g h h g 6
11

---

Under review as a conference paper at ICLR 2022
Definition 6 A representation of finite group finite-dimensional complex vector space V is a homomorphism p - GL(V) of the group to automorphisms of V (Fulton & Harris 2013). This allows group elements be expressed invertible matrices and the group operation be matrix multplicatiin.
A.3 MODEL ARCHITECTURE
We consider the input graphs input feature space that is order 2 representation. For each local permutation equivariant linear layer we use order and representations as the feature spaces. This allows for projection down from graph node feature spaces through the basis for p2 - Pl. projection up from node to graph feature spaces through the basis for + p2, and mappings across the same order representations through P2 - P2 and P1 - P1- The final local permutation equivariant linear layer maps to order 0 representations through P2 - and P1 + Po for the task of graph level classification. In addition the graph layers, we also add MLP layers the end of the model.
Despite these specific choices which were made to provide baseline of our method for comparison to existing methods the framework we present is much more general and different representation spaces can be chosen. present the general framework in Figure 6 This shows how different permutation representation spaces, # @ p2 @ ... @ ps. can be chosen for different layers in the model and how different values can be chosen when creating the sub-graphs in each layer.
Input Graph
Pg representations
k-hop Subgraph
Pj reprosentations
Subgraph Convolution
Pj representations +
. representations
Reinsert Subgraphs
0 O ... P representations
k-hop Subgraphs
T ( x. @ representations
Stack Multiple Layers
Subgraph Convolution pr ② p2 @ ... 1 p representations -> P: 2 P2 @ ... .. representations
Reinsert Subgraphi
P1 Pz A representations
k hop Subgraphs
Pr Pa @ ... p. representations
Subgraph Convolution
Ph 1 +
+
representations representations
Reinsert Subgraphs representations
Figure 6: The general framework for building models with permutation equivariance through rep- resentations of the permutation group is presented. In general for work on graphs the input repre- sentation Pj P2. but this could vary if the input was a layer choice of k value can be made which is the number of hops to consider when extracting sub- graphs. Also, for each layer the permutation representation type can be chosen where the choice of Pi @ p2 @ ... is the order of representations required for that layer. Choosing larger order repre- sentations increases the expressivity of the model, although this increases the bases space increasing the computational cost.
other data structure. Then for each
12

---

Under review as a conference paper at ICLR 2022
A.4 EXPRESSIVITY
Figure shows the training accuracy achived by the LPEGN model across range of datasets. (a, b, c, and d) show that the LPEGN model is able to achieve 100% training accuracy on PTC, Proteins, NCII, and NCI109 datasets. This demonstrates that the model utilising only order 1- and 2-permutation representations is sufficiently expressive. In addition, (e) shows that the model achieves very close to 100% accuracy the IMDBB dataset. On the other hand, (f) shows that the model training accuracy plateaus above 70% accuracy for the IMDBM dataset. This highlights the model not sufficiently expressive to achieve 100% accuracy this datset. As discussed in Section 7 we belive that utilising higher order permutation representations would make the model more expressive and as result achieve higher accuracy on IMDBM.
100
100
Accuracy (%)
Accuracy (%)
90
80
80
70
50
10
30
40
50
10
20
30
40
of epochs
# of epochs
(a) PTC
(b) PROTEINS
100
100
90
Accuracy (9)
90
Accuracy
80
70
70
50
10
20
30
epochs
# of epochs
(c) NCII
(d) NC1109
100
Accuracy (%6
90
Accuracy (%)
60
50
40
60
10
30
50
10
20
40
epochs
epochs
(e) IMDBB
(f) IMDBM
Figure 7: A visualisation of the training accuracy for benchmark graph classification datasets across 10-folds. Each plot shows the training accuracy as a percentage, where higher percentage better.
13

---

Under review as a conference paper at ICLR 2022
A.5 COMPARISON OF RESULTS
In addition to the comparison across datasets in Table 1 Figure 8 shows the training accuracy dis- tribution of the LPEGN method and compares other methods from Table The multimodal distribution LPEGN for the PTC dataset highlights why it has a large standard deviation. This is likely result of the fact that the PTC dataset is very small. Given the poor ranking of the LPEGN method in Table ! comparing the results to other methods here highlights that the LPEGNN result competitive. For the NCT1 and NCT109 datasets the distribution of results of our method highlight the strong performance of the method. For IMDBB and IMDBM the distribution of results for the LPEGN method also highlight that it is competative on these datasets.
Further, we propose additional method of comparison, namely the counts of wins of our LPEGN method with other methods and the counts of significant wins. The result of comparing the counts of wins shown in Figure 9 highlights that method is of the strongest performing across the range of datasets. Where LPEGN under-performs against other methods this can largely be attributed to weaknesses the PROTEINS and IMDBM datasets, which we suspect using higher order representations could improve.
Ressits
pirtration ASCRS
6.5
6.15
6.3
6.00
0.2
6.00
6.4
Accuray
(a) PTC
(b) PROTEINS
Oitrication Other Auauts
Dittibation Otner Resulta
0.3
Accuney
(c) NCI1
(d) NCI109
L'EON
8.6
04
04
05
Se
Acoutts
(e) IMDBB
(f) IMDBM
Figure 8: Comparison between out LPEGN method and other methods on benchmark graph clas- sification datasets. Results for the LPEGNN method are presented as histogram of the 10-fold runs. Each other method is given as Gaussian distribution with mean and standard deviation as is presented in Table [ In addition, we display the sum of the distributions for all other methods to show how our method compares.
14

---

Under review as a conference paper at ICLR 2022
wins by LEGNN
100
70
Percetage
40
GDCAN
PSCN
DCNN
ECC
DGK
DiriPool
CCN
IGW
GIN
I-2-3GNN
PPGWV1
PPGWW2
PPGWV3
LNGN
GSN-e
GSN-v
SIN
CIN
(a) Counts of wins
Percetage ranking wins by LEGNN
100
80
60
GDCNN
PSCN
DCNN
ECC
DGK
Dififool
CCN
IGN
GIN
32-GNNN
PPGWv1
PPGW2
PPGMV3
LNGN
GSN-e
GSN-v
SIN
CN
(b) Counts of significant wins with margin 1.0
Percetage ranking wins by LEGNN
100
40
GDCNN
PSCN
DCNN
ECC
DGK
DifiPool
CCN
IGH
GIN
1.23GNN
PPGWvl
PPGNVv
PRGNV3
LNGN
GSN-
GSN
SIN
CIN
(c) Counts significant wins with margin 2.0
Percetage ranking
100
wins by
60
GDCNN
PSCN
DCNN
ECC
DGK
Dififool
CCN
IGN
GIN
1-2-3GNN
PPGNv1
PPGW2
PPGMV3
LNGN
GSMe
GSH
SIN
CIN
(d) Counts of significant wins with margin 3.0
Percetage ranking wins by LEGNN
100
80
GDCNN
PSCH
DCNN
ECC
DGK
DiffPool
CCN
IGW
GIN
1.2.3GNN
PPGNV1
PPGNv2
PPGHv3
LNGN
GSN-
GSN-v
SIN
CiN
(e) Counts significant wins with margin 4.0
Figure 9: Presented is the percentage of ranking wins across the seven datasets for the LPEGN. A results above 50% means the LPEGN method beats the other method across the majority of datasets.
15

---

Under review as a conference paper at ICLR 2022
A.6 CHOICE LOCAL NEIGHBOURHOOD
We show how this choice of value will impact the method through analysing the MUTAG dataset and comparing the size of sub-graphs found for different k values, ranging from the most local, = 1, up to equivalence a global update, k = 15, shown in Figure 10
1200
Number of Occureences
1250
Orcumences
1000
1000
800
750
400
200
2
6
10
Bab-Graphs
Graphs
k:
600
400
Number of occurenncs
Occurrences
500
300
300
200
200
100
100
0
15.0
Size of Sub Graphs
Size Sub Graphs
k:
400
Number Occurrences
Occurrences
300
200
100
50
10
25
Size of Sub-Gr Sub-Graphs
Size of Sub Graphs
8 8
l 15
Figure 10: Histograms showing the number of occurrences of each size sub- sub-graph in the MUTAG dataset for different choices of k value, where & is the number of hops to take away from the central node when selecting nodes to be included within sub-graph.
16

---

Under review as a conference paper at ICLR 2022
A.7 COMPARISON OF LOCAL AND GLOBAL FEATURE SPACES
We compare the case of global permutation equivariance to our local permutation equivariance, demonstrating how sub-graphs and the choice of representation is made in Figure
(a) Global permutation equivariance.
(b) Local permutation equivariance.
Figure 11: (a) Global permutation equivariance and some of the possible representation choices. (b) Local permutation equivariance demonstrated through local neighbourhoods selected based on graph connectivity. Permutation equivariant representations driven by the degree of the central node, Some of the possible representation choices are shown for each neighbourhood.
A.8 PROOF OF NO LOSS OF EXPRESSIVITY WHENN USING RESTRICTED REPRESENTATIONS
Restricting the permutation representation, from a group G with n nodes to a subgroup H with m nodes yields the restricted representation in == Resh (Pa). The bases for the permutation representation Pr. from set of nodes to of nodes given in Figure Jad has 2 basis elements. We show that the restricted representation adds 3 more basis elements in Figure 3 From definition 2 there no edge features associated between the nodes in the sub- sub-graph and the nodes outside of the sub-ge bob-graph. Therefore 2 of the basis elements introduced in the restricted representations are always multiplied by zeros and not required. Further, the extra 3rd basis element introduced is simply weighting the node features not part of the sub-graph by themselves and as our method extracts sub-graph for each node the graph this update is subsumed by the sub-graph update that node. Therefore the restricted representation for our framework is equal to the permutation representation of a lower dimensional space and Pm = pm- Therefore, the proof of no loss of expressivity when using restricted representations follows from the proof that k-order graph networks powerful as k- WL (Maron et al.) 2019).
A.9 IMPLEMENTING OTHER MODELS WITHIN OUR FRAMEWORK
We have re-drawn our model in a step-by-step format to try and highlight the difference to other models and make clear that this is more general framework for learning permutation equivariant models in Figure 6 In the datasets used, for graph classification benchmark tasks, the input to the model is graph with node and edge features, this can be represented 2nd order permutation representation, so the input representation would be = 2. The convolution can then map from this representation, Pj. to multiple different representation spaces, Pu + P1 + + Pt. Subsequent convolutions can then map from these multiple permutation representations, Po @ pi ..... Pi, to multiple different permutation representations, Po < P1 ( ( ps. The choice of representations used be made depending order representation spaces have less expressivity, but also lower computational cost.
trade off between expressivity and computational cost, as lower
Local Natural Graph Networks (LNGNs) (de Haan et al. 2020) take the input feature space and embed this into an invariant scalar feature of the edge neighbourhood graph. This is the same as using specific choice h-hop sub-graph creation and permutation representation space for the sub- graph convolution. In the case LNGNs the choice would be k = 1 and mapping the input feature space to representation Po creating a permutation invariant feature space. Then any graph neural
17

---

Under review as a conference paper at ICLR 2022
network with invariant features can be used, in the paper the choice made is to GCN (Kipf & Welling 2016). which can also be covered by our framework. Here the choice would again to use
k = I when creating the subgroups and using subgraph convolution with representation spaces Po > Po-
choice of k: n, for n-node graphs when creating the sub graphs, which corresponds to not selecting a sub graph and instead operating
Global Equivariant Graph Networks (EGNs) (Maron al. 2018
the entire graph. They then use the representation space p2 - P2 mapping from a graph feature space to graph feature space.
Local Permutation Equivariant Graph Networks (LPEGN) (Ours) In our paper choose k = throughout to keep inline with the vast majority of previous work on graph neural networks, but use representation space Pt + P2 P1 o P2 the hidden layers of the model and we note that this was simply a choice that seemed simple case to present as a comparison with previous work in the benchmark classification task.
18


Reviews:
[{"review_id": "bTiH41vddVx", "reviewer": "Reviewer_auCg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contribution of this paper is unclear to me. The approach is very similar with 'Natural graph networks' by Pim de Haan, Taco Cohen, Max Welling (NEURIPS 2020) and I would have like to see a clear comparison of the approach and the results.\nThe paper is very hard to follow. I agree that category theory is a very abstract field and an introduction is beyond the scope of the paper but it would have been nice to give some simple examples on toy examples highlighting the benefits of the approach proposed here.\nIt is impossible to understand the architecture used here as the description in Section 5 remains at a very high level. I could not find the code associated with this paper.\nThe experiment about scalability in section 6.2 is not convincing at all as it deals with graphs with a maximum average number of nodes of 40.", "summary_of_the_paper": "This paper introduces local permutation equivariant graph network. The main motivation for introducing these graph neural networks is to improve in term of scalability with respect to global permutation equivariant models.\nThis paper uses the very abstract language of category theory. In Section 6, the authors provide some experimental results on some real-world graph classification problems.", "summary_of_the_review": "The contribution of the paper is unclear. Provide more examples and convincing experiments about scalability which is one of your main motivation.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "OGlwJFUR2ky", "reviewer": "Reviewer_zCkV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n\n1. **Scalability** - the proposed framework introduces a scalable version of global equivariant graph networks [Maron et.al. 2018]. \n2. **Performance** - on the selected datasets the model has been evaluated on, the proposed model performs relatively well across all datasets.\n\n\n\n**Weaknesses**\n\n1. **Motivation** - the motivation for the proposed framework is a bit unclear to me. It seems like a less restricted instantiation of local natural graph networks which choses to work with equivariant layers instead of message passing layers in the local updates, but the claims and justifications feel rather weak and unsupported.\n2. **Theory** - the paper claims that the framework maintains expressivity or even can achieve improved expressivity (Section 5), but it is not clear over what other models? And there are no theoretical results which show that, other then stating it several times in the paper.\n\n\n\n**Clarifications**\n\n1. **Applicability to new graphs** - how does the network handle subgraphs of unseen sizes during training?\n2. **Framework description** - I find it confusing that the framework is only illustrated in a figure which is not close to the text describing it. \n\n", "summary_of_the_paper": "The paper introduces the framework of locally permutation equivariant graph neural networks. \nThis framework applies permutation equivariant layers [Maron et. al. 2018] to local node neighborhoods by treating them as separate subgraphs and using a weight sharing scheme for subgraphs of the same size. \nThe authors build their framework by discussing the different choices made -- local neighborhoods, weight sharing, and representation space. \nThe authors also provide a category theory point of view of their framework. ", "summary_of_the_review": "I think this paper introduces an interesting framework but fails to justify and motivate its constructions. I further feel that the theoretical analysis of the framework is lacking. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LoHmwg7mZjy", "reviewer": "Reviewer_Y3RZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Initial Recommendation: Rejection\n\nReason: In my view, in current format, the weaknesses outweigh the strengths of the paper. Please see details below.\n\nStrengths:\n\n1. Idea - Use of restricted representation of symmetric groups to reduce dimension of vector space - associated with group representation for linear permutation equivariant layers.\n2. Practicality - Employ a weight sharing scheme when the size of the node neighborhood is the same\n3. Demonstrate scalability in terms of GPU memory usage\n\nWeakness:\n\nFor me, the main weakness of this paper is in its exposition and clarity that raised several questions. I have listed my main concerns below.\n1.  Lack of precision and clarity in the paper, for e.g. (i) definition 2 is never again used in the paper (ii) section 3.1 The space of linear equivariant layers, given by bell number (4)) is 15 - what do you mean reducing linear layer to just 15 parameters?\n2. The authors claim that there is no loss of expressivity while using restricted representations of finite symmetric groups but there is no formal proof for the same? Does this always hold? Do you need them to be normal subgroups? Is there any specific requirement for the representations (what happens when irreducible reps are used, etc) used?\n3. While considering node neighborhood and edge neighborhood morphism misses out comparisons with relevant works which use subgraph counting isomorphism/ automorphism over local neighborhood [1][2][3][4] to obtain provably expressive representations The mentioned works also almost always perform better than the proposed work in the datasets.\n4. The scalability studies are incomplete - e.g. do not describe what the datasets used are? how many graphs are there in the dataset? etc?\n5. No study on effect on performance when k>1 (hops) is used (the plots in the appendix only show the size)\n\nReferences:\n\n1. Bouritsas, Giorgos, et al. \"Improving graph neural network expressivity via subgraph isomorphism counting.\" arXiv preprint arXiv:2006.09252 (2020).\n2. Morris, Christopher, Gaurav Rattan, and Petra Mutzel. \"Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings.\" arXiv preprint arXiv:1904.01543 (2019)\n3. Bodnar, Cristian, et al. \"Weisfeiler and lehman go cellular: Cw networks.\" arXiv preprint arXiv:2106.12575 (2021).\n4. Bodnar, Cristian, et al. \"Weisfeiler and lehman go topological: Message passing simplicial networks.\" arXiv preprint arXiv:2103.03212 (2021).", "summary_of_the_paper": "Graph Neural Networks have recently become the state of the art for tasks on graphs due to their flexibility, scalability. In this work, the authors propose a framework to build GNN's that operate on local node neighborhoods in a permutation equivariant way - and argue that since LPEGN operates on lower dimensional spaces in comparison to regular GNN's the proposed technique offers significant improvements  in terms of GPU memory usage. The authors make use of category theory basics - and employ restricted representations of finite symmetric groups (i.e. fix some nodes while permuting other elements) based on the number of nodes in the neighborhood of the node - and ensure there is weight sharing between nodes with the same degree to achieve their objective.", "summary_of_the_review": "The authors propose a practical framework mainly aimed to reduce GPU memory usage via the use of representation theory. However, for me, the main weakness of this paper is in its exposition and clarity - including lack of proofs for statements made, lack of comparison with appropriate baselines, incomplete analysis, etc, ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H9t2wat9aW9", "reviewer": "Reviewer_KECi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed method is impressively practical in terms of performance and efficiency.  The proposed local permutation equivariant local update function is more GPU memory efficient than the global counterpart. Moreover, this work achieves impressive performance in 7 graph classification networks.\n\nHowever, I have several concerns about the paper which I will detail below:\n\n- While I appreciate the paper’s providing sufficient background about graph neural networks to improve readiness,  I am not sure I clearly understand the relation of the provided background with the proposed method. For example, in section 3, I can understand the mechanism of global equivariance. But  I am not sure how section 3 can help elaborate the method. I probably would recommend moving part of those stuff into supplementary.\n\n- I wonder about the novelty compared with other works in Graph convolution. From my viewpoint, the Graph Conv/ Messaging pass network is also locally permutation-equivariant. To be more specific, LNGN is a method that shares the similar idea of using locally permutation-equivariant update functions. It also shows competing performance in table 1 of the paper. Is this work essentially the extension of LNGN?\n\n- Missing baselines GPU memory efficiency comparison. I believe other graph neural networks that employ local update functions also benefit from GPU memory efficiency. I thus recommend the paper also provide a comparison with those methods. \n\n- Experiments for the dataset that has the well-defined local symmetry -- say mesh data. I understand that this work aims to handle natural graph data. But it would be also very interesting to check out the performance of the proposed local permutation equivariant update function in mesh data. Because I think it might be helpful to validate the expressiveness of proposed functions.\n", "summary_of_the_paper": "This paper introduces the local permutation equivariant network (LPEGN). Specifically, this work proposes to apply permutation equivariant update functions locally --- i.e., operating in a local neighborhood. The benefit of doing so is that the large graph is handled through sub-graph, which saves a lot of GPU memory. Moreover, this work handled different sizes of neighborhoods by proposing a heterogeneous weight-sharing mechanism. Weight is shared w.r.t neighborhood size -- local neighborhoods with the same size share weights. While being flexible to input sizes, the local update function is also expressive. The paper demonstrates its superiority in several graph classification benchmarks.", "summary_of_the_review": "While the proposed method is practical, the novelty of methods is limited when compared with existing works that also employ locally permutation equivariant update functions. More importantly, the paper didn't provide a clear comparison to make the proposed method stand out from the previous related works. Thus, I currently vote for weakly reject. However, I still would like to hear more from the authors if I have any misunderstandings. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a graph neural network (GNN) architecture that adopts locally permutation-equivariant constructs, which has better scalability compared to globally permutation-equivariant GNNs, and the paper claims this change also does not lose expressivity of the network.  All reviewers unanimously recommended rejection, and the main issues are the clarity and writing, to the point where it becomes hard for a reader to follow the precise implementation of the proposed approach and how that compares to prior work.  Therefore in its current form this paper is not yet ready for publication at ICLR.  When the authors work toward the next revision I’d suggest clarifying a little more about the precise algorithmic implementation of the proposed ideas, with a bit of additional intuition from a higher-level, rather than staying at the current level of technicality.
Decision: Reject