Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
This 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.
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.
The 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.
It 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.
The 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_review: The contribution of the paper is unclear. Provide more examples and convincing experiments about scalability which is one of your main motivation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Initial Recommendation: Rejection

Reason: In my view, in current format, the weaknesses outweigh the strengths of the paper. Please see details below.

Strengths:

1. Idea - Use of restricted representation of symmetric groups to reduce dimension of vector space - associated with group representation for linear permutation equivariant layers.
2. Practicality - Employ a weight sharing scheme when the size of the node neighborhood is the same
3. Demonstrate scalability in terms of GPU memory usage

Weakness:

For me, the main weakness of this paper is in its exposition and clarity that raised several questions. I have listed my main concerns below.
1.  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?
2. 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?
3. 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.
4. The scalability studies are incomplete - e.g. do not describe what the datasets used are? how many graphs are there in the dataset? etc?
5. No study on effect on performance when k>1 (hops) is used (the plots in the appendix only show the size)

References:

1. Bouritsas, Giorgos, et al. "Improving graph neural network expressivity via subgraph isomorphism counting." arXiv preprint arXiv:2006.09252 (2020).
2. Morris, Christopher, Gaurav Rattan, and Petra Mutzel. "Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings." arXiv preprint arXiv:1904.01543 (2019)
3. Bodnar, Cristian, et al. "Weisfeiler and lehman go cellular: Cw networks." arXiv preprint arXiv:2106.12575 (2021).
4. Bodnar, Cristian, et al. "Weisfeiler and lehman go topological: Message passing simplicial networks." arXiv preprint arXiv:2103.03212 (2021).
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,
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
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.

However, I have several concerns about the paper which I will detail below:

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

- 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?

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

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

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper introduces the framework of locally permutation equivariant graph neural networks. 
This 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. 
The authors build their framework by discussing the different choices made -- local neighborhoods, weight sharing, and representation space. 
The authors also provide a category theory point of view of their framework. 
main_review: **Strengths**

1. **Scalability** - the proposed framework introduces a scalable version of global equivariant graph networks [Maron et.al. 2018]. 
2. **Performance** - on the selected datasets the model has been evaluated on, the proposed model performs relatively well across all datasets.



**Weaknesses**

1. **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.
2. **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.



**Clarifications**

1. **Applicability to new graphs** - how does the network handle subgraphs of unseen sizes during training?
2. **Framework description** - I find it confusing that the framework is only illustrated in a figure which is not close to the text describing it. 


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.
review_title: null

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