Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors of this paper propose an compression technique for GNNs that was inspired by lifted inference. The compression consists of removing asymmetries by merging nodes. They define two algorithms for compression: a non-exact algorithm that merges two nodes that are "functional" equivalent and an exact algorithm that merges two nodes that are structurally equivalent.

The approach seem quite novel, pretty interesting and it could interest a wide audience that works on graph models. However, I think the presentation could be improved. In particular, it is not clear the evalutation settings that they are using. For knowledge completion how do they compute accuracy? Do they use golden triples?

In conclusion I think section 5 should be improved and writte more clearly but overall I think it is a good paper and should be considered for acceptance.
review_title: Review

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes an approach to make learning deep neural networks more efficient using ideas from lifted inference for relational probabilistic models. Specifically, symmetries in the computation graph are identified and then the neural network is compressed into an equivalent model.

The idea of using symmetries for improving scalability has been successfully used in statistical relational models. Therefore, it seems to be a nice direction for improving scalability in neural networks such as GCNs. Thus, large computation graphs can be reduced to smaller graphs for effective computation.

The main weakness with the paper is that the compression algorithm was not very clear to me. Particularly, the problem of identifying isomorphisms is a hard problem and several lifted inference techniques have typically used approximate methods to identify symmetries in graphical models [e.g. Niepert UAI 2012, Bui et. al. UAI 2013, Holtzen et al. UAI 2019, etc.]. I was not sure why or how the identification of exact symmetries is not hard in this case. Is the type of computation graph restricted to some form? If so, a more detailed description of the properties of this graph is useful. Since the main focus of the paper is on “exact” symmetries, I think in general, a more detailed analysis of the proposed approach will help in general.

Regarding the experiments, they show that the proposed techniques can help speed up different types of deep models based on GNNs. One aspect that was not very clear was how large were the computation graphs? Also, when the compression is exact would the accuracies still vary between the compressed and uncompressed model?

In general, I like the idea of using symmetries to compress graph-based neural networks. I am not too clear on the details of the proposed approach, particularly their applicability for general graph structures.

From the discussions, the authors make it clear that "compressing" the computation graph is possible without the need for expensive operations (as is the case in typical "lifted" inference literature). The approach does seem to be simple to implement , maybe a bit more detailed analysis and clarity as suggested by others as well could strengthen the paper further.
review_title: An approach to use symmetries to improve scalability of learning in graph based neural networks. The idea seems promising and has been successful in the graphical models community but some details were unclear in the paper.

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################

Summary:

 
The paper provides an interesting work in the scale/speed up of structured convolutional models. In particular, it proposes an idea using a technique named lifting which is used in scaling up of graphical models to detect the symmetries and compress the neural model such as Graph Neural Network. Authors show that this compression can lead to speedups of the models in many tasks.

##########################################################################

Pros:
 
1. The paper takes one of the most important issue of structured convolutional models: scale/speed up. I think this is an area with real world implication where we need more works.

 
2. I think this method can be very useful for networks using lots of identical nodes like molecular network. It can leverage from the repetition in nodes and compress the network into some smaller network and save time and memory.
 
3. Overall the paper is well written. I liked the illustrations for explaining the methods. Result section is also well structured. It clearly shows the effectiveness of the algorithm over other methods.
 
##########################################################################

Cons: 

 
1. Although I think this work is good for small datasets like molecular networks, i am skeptic about its transferability in large scale graphs. The reason behind that is I don't assume there would be a lot of structurally similar nodes in case of a large scale real life graph. Authors did not provide any information on the size of the graphs used for the experiments. 
 
2. Authors proposed two different algorithm, exact and non-exact. There are no comparisons between these two methods are shown in the result. Proper analysis on time and performance of the algorithms are also absent. The motivation behind using exact or non-exact is not clear.

3. On Table 1, the time of the different experiments are given. There are no analysis on time vs performance metric in this table. Does all the baseline show similar performance as the baseline model? The analysis is not present.

4. It would also be interesting to see an analysis on the effect of the algorithms on different graph types based on their characteristics (degree distribution, density, veracity etc). 
 
##########################################################################

Questions during rebuttal period: 

 
Please address and clarify the cons above 

 
#########################################################################


review_title: Room for improvement

Meta-review: The paper shows that show that methods for probabilstic lifted inference can also be used to "compress symmetries" in convolutional models over structured data. The resulting structured convolutional models are then shown to yield speed ups for learning graph neural networks, too. This is highly interesting since the existing literature rather considered how to make use of weisfeiler lehman for classification of graphs, both in neural and a kernel way. This paper, however, shows how to compress the computations. And it paves the way to connect equivariant learning lifted inference by exploiting the connection between lifted probabilistic inference / weisfeiler lehman and their algebraic formulations. 
Decision: Accept (Poster)