Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors establish a theoretically well-motivated, general-purpose graph compression framework they call Partition-and-Code (PnC).
The framework consists of 3 general parts: partitioning, creating a dictionary of common subgraphs and entropy coding. Crucially, the first two steps are used to map a graph to its isomorphism class, and it is in fact the isomorphism of the input graph that is encoded using entropy coding.

The compression pipeline, given a graph partitioning function and a subgraph dictionary, works as follows:
1) The graph to be encoded is split up into two types of subgraphs: atoms (subgraphs of a fixed size, such that they should be likely to appear in the dictionary), and cuts, which connect the atoms.
2) Then, atoms appearing in the dictionary are encoded using a distribution tailored to the dictionary. Cuts and atoms missing from the dictionary are coded using an appropriate uniform distribution.

Importantly, ML techniques are only used as heuristics for the partitioning part of the encoding process, which means that the decoder does not need to know the model parameters.
The authors propose various proof-of-concept ways to learn the partitioning function using an e.g. GNN and propose a relaxed, greedy gradient-based way to learn the atom dictionary. Learning of all parts of the encoder is performed by minimizing an appropriately defined minimum description length objective.

The authors perform experiments on multiple popular graph datasets and achieve good results.

main_review: # Strengths
The work is based on a well-motivated idea and contains several well-executed solutions to the problems considered.

The general framework of PnC is elegant, and by operating on the domain of graph isomorphism classes instead of graphs they already achieve good gains in compression efficiency.

The proposed solutions to all 3 steps are simple, sensible and work well.

The fact that the decoder does not require any statistical model beyond the coding distribution to decode the compressed graph representation is very appealing both in terms of computational as well as run-time costs and makes the method widely applicable.

The experimental methodology is sound. The authors perform comparisons to a large number of other methods on multiple graph datasets and their method achieves very good results on all of them.

The paper is very clearly written with a logical, easy-to-follow layout. 

# Weaknesses
My only issue with this otherwise very nice submission is in their comparison with what the authors call "neural, likelihood-based approaches".
The authors assume that some representation of the model that was used to compress the graph has to be transmitted along with the compressed graph representation.
In my opinion, this is a fair assumption, but my issue is that it is assumed that the model parameters are assumed to be uncompressed during transmission (the authors assume 16 bits/parameter).
While of course, it is easier to calculate the model size this way, I think this doesn't provide a representative comparison,
and hence in the current state of the paper, I cannot conclude that the authors' method achieves the best compression among all considered methods. There has been a lot of work recently on the compression of neural networks, with some
recent works (e.g. [1]) achieving up to a 1000-fold reduction in model size. Therefore, I would recommend the authors to perform further experiments where the transmitted neural model is compressed using any reasonable, recent model compression method, include the results in Table 1 and see if their method still performs better.

If the authors can address my concerns, I will be very happy to increase my score.

Additionally, some typos that I found:
- Line 115: Reference 53 appears twice
- Line 338: "... store each each in a dataset ..." - the second "each" should read "edge".

# After the Rebuttal

After reading the other reviewers' comments and the authors responses, I am even more impressed with the work. The authors have addressed my main concern with their work, and therefore I raised my score on the submission.

[1] M Havasi, R Peharz, and JM Hernández-Lobato. Minimal random code learning: Getting bits back from compressed model parameters. ICLR 2019.


limitations_and_societal_impact: I believe they addressed the limitations of their work very thoroughly.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a lossless compression method for graphs. By analogy to patches in images, or words in text, they propose breaking up the graph into sub-graphs, and encoding common sub-graphs using a dictionary. This is then compressed by an entropy encoder. Experiments are provided on a variety of datasets, ranging from molecules to social networks
main_review: *Disclaimer*: While I am familiar with information theory and compression, I certainly would not rank myself as an expert. My expertise is more to do with graphs.

### Detailed Comments

Abstract: This is good, although it'd be even better with some numbers.

Intro: This is also well written, and explains the fundamental idea quite well, breaking it up into the constituent parts.

Related Work:
- L90: it's worth noting that vertex reordering can be very slow to do, so even if it were to provide solid compression, it's not going to be fast.
- L94: Surely the premise here is that we are learning a (limited) graph grammar, so in some sense this is related?
- L124: Typo for 'therefore'

Preliminaries:
- L143: It is interesting that this can compress families of graphs. Arguably, however, this means the size of the compression model is less important though? If you can generalise to unseen graphs, then that's also useful.
- I thought this section was fairly well written; you may wish to expand the explanation of eq. 1 though.

S4:
- I think you could certainly do with having a diagram explaining the overall process around here. The prose is extremely formal, and obscures much of the intuition.
- L247: you should forward reference the next section here, by saying that you'll explain how to optimize it next. This seems rather abrupt and odd as currently written.

S5:
- L295: I am not sure I agree that leaving the partitioning algorithm to the appendix is a good idea if you're selling it as part of the novelty of the paper. The prose is overly verbose and formal: I am certainly you can compress some equations and re-write some sections so you have enough space that this does not need to be relegated.

S6:
- Fig2 is interesting in that individual nodes are considered a probable subgraph for both datasets (although, this is also not surprising); how common are they in practice? Do subgraphs commonly get broken up into this most primitive atom?
- Table 1/2: the results are good, but there's no indication of training time here (for any method), which should not be ignored.
- If you were going to provide another dataset, it might be good to look at something like OGB code? (note: I don't expect you to do this. But just a thought for future :-) )

#### Other Questions:
- An interesting property of this work is that it should generalise to graphs which are "unseen" (just as an image compressor can generalise to images that haven't been seen before). Could you evaluate this property? Maybe you could split the datasets, and report the compression rate on the holdout data?
- Similarly, what happens if you take a compressor and apply it to a dataset it wasn't trained on? How well do things transfer?
- How much data do you need to train a reasonable compressor? Would it be possible to plot a graph?
- Finally, how do you handle node / edge features?

I'm not expecting all of these to be answered necessarily in the time you have for rebuttal. But it'd definitely be useful to answer some of them :-)

#### Overall Thoughts

I think the work is really interesting, but the evaluation doesn't do it complete justice. For now it's a weak reject, but with some work done at rebuttal I am happy to increase the score.

===== Post rebuttal

I'm happy to increase my score (although I stay unconfident in my assessment). Another reviewer did make a good comment about scaling to larger datasets. I think this point is true. Given that the authors are able to show that your method generalizes to the test set/across datasets, I think this is not too difficult for the authors to address given some time.
limitations_and_societal_impact: I don't think the limitations are sign-posted well enough. It'd be useful to provide some discussion about this somewhere. I don't think the authors have done a good enough job of ablating their work, since there are many interesting questions that can be asked.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This article presents a procedure to compress graphs (into a code). It takes the principle of entropy minimization i.e. finding a code that has the lowest possible entropy. In order to do so three steps are considered: 1) partioning the graph into subgraphs ($\operatorname{Part}_{\theta}$ which is parametrized by a NN) 2) finding a dictionary that faithfully describes a prior on the subgraphs structures, and that will be used to encode the different subgraphs coming from PART 3) Graph encoding part: assign a (parametrized) probability to each subgraph (which depends of the dictionary also). From a probability we can derive the length of the code. Overall this defines a description length which can be minimized in order to have the shortest code possible. 

main_review: First a disclaimer: I am not an expert on information theory, especially in the context of graphs, so I may have missed some details. In the following I will note from (1/5) for a comment that have a small impact on my final score to (5/5) for a comment that has a strong impact.

- Pros: 
	- Overall the article is very well written and enjoyable to follow.
	- The problem tackled is quite interesting and far from trivial. I think the article manages to give good insights and paves the path for new perspectives.

- Cons:
	- Some parts of the article are a bit vague/unclear in my opinion and would deserve more details.
	- There are a lot of "black-boxes" so that it is sometimes hard to understand the intuitions behind the different mechanisms.
	- I am not really convinced by the usefulness of the "dictionary part".

Overall I find that the article is very well written, at least up to Section 5, and enjoyable to follow. I thank the authors for that. The different problematic are clearly stated as well as the different "blocks" of reasoning.  I like the idea of relating information theory with ML in the precise context of graphs. The "commun graph encodings" scheme seems reasonable to me, since, as far as I known, the Erdos-Renyi assumption (used to define $L_{\operatorname{null}}$) is one of the few generative process of graphs where we can say something about optimal compression (ref [9]). The fact that the estimated distribution must be invariant to isomorphism is sounded (row 223). For this argument I think Appendix A is quite enlightening and really shows that one needs to encode the isomorphism classes. It is a bit of a shame that this discussion is not included somehow in the main text or at least more detailed (0.5/5).

- About the universe and the dictionnary: 

(4/5) It is not very clear to me how the approximation made by considering eq (6) is "sufficient" for solving the challenge C.1, ie only considering isomorphism with respect to atoms in the dictionary. I can be wrong but it seems that the case $\exists a_i \in D$ such that $H_i \sim a_i$ ($\sim=$ isomorph) is hardly met in practice when the size of $D$ is reasonable. Indeed, for me it is unlikely to find a graph within the dictionary that is isomorphic to a subgraph coming from a black-box GCN used in PART. Or at least it is not clear how often this occurs so that I expect $q_{\phi}(H_i|D)=q_{\operatorname{null}}(H_i)$ everytime; especially in the case of "small" universe. Also it is written in row 284-285 that "most subgraphs (in the universe) will never be encountered in the graph distribution": this sentence is a bit confusing, because it seems to corroborate my remark. Overall I am quite skeptical regarding the usefulness of the dictionary and thus the ability of the method to deal with isomorphisms.

(4/5) More importantly how, in practice, do you choose this "practically enumarable universe" (row 277) ? I do not see any details about this in the article.

- About the encoding: 

(2/5) It is not so clear to me how $q_{\phi}(a_i)$ are defined. It is said that (row 276) "are parametrized by learnable variables that are converted into categorical distributions [...] using a sofmax function". What do you mean by "learnable variables" ? Does it boil down to an optimization on the probability simplex (whose size is the number of elements in the dictionary) ? Or do you choose some parametric family like binomial and learn the different parameters this way ?

- About the partitioning algorithm: 

(3/5) I think a more detailed discussion about the partitioning algorithm is welcomed here. In this form, $\operatorname{Part}_{\theta}$ is a kind of "magic" black-box and we have no idea how the REINFORCE algorithm works. Even if some detailed are given in the supplementary I think it is important to give at least some intuitions behind the PART algorithm and other potential non-parametric strategies (to understand for example the complexity of it). Is it really stable ? Can two runs of the same algorithm give a very different code ?  

- About the decoding:  

(3/5) I do not understand also how one could potentially decode from a compressed graph here. The authors present well the stakes of the information theory with the aim of creating a uniquely decodable code (row 148: " the code needs to be uniquely decodable"). However with the many models and approximations on the true distribution (which seem to be essential because the different problems are NP-hard) I think the resulting code has no reason to be uniquely decodable. How in practice we can recover the graph from the code ?

(1/5) Related to this remark I think it would have been valuable to detail more what is "jointly exchangeable" here, even with one or two sentences.


- Experiments: 

(4/5) I find a bit of a shame that no comparison are made with algorithms that provide compression codes with guarantees. How does it compare for example with a "simpler" algorithm such as Structural zip (SZIP) (ref [9] of the paper) which assumes that the underlying graph distribution is Erdos-Renyi or some other ones described in ref [32] of the paper ? Also I think a small ablation study regarding the usefulness of the dictionary here could be interesting (see my point above about $q_{\phi}(H_i|D) \approx q_{\operatorname{null}}(H_i)$ everytime).


- Other comments: 
	- I think in Section 4.5 authors talk about eq (8) and not eq (7) 


----- AFTER REBUTTAL -----

The authors fully addressed my concerns I think the paper is very rich and deserves publication (see my comment below). I change my score to 8.
limitations_and_societal_impact: Authors did not provide any potential negative societal impact of their work however, it is difficult for me to foresee these impacts... Some other limitations are addressed in the supplementary.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the lossless compression of graphs with  deep learning. The authors propose to compress  the graphs in 3 steps: a partitioning algorithm decomposes the graph into elementary structures, which are mapped to the elements of a small dictionary, and an encoder translates the representation into bits. The partitioning  is parameterized  by a graph neural network output the likelihood of partitioning and optimized with the policy gradient method to achieve as small minimum description length as possible. The minimum description length are decomposed into several parts, the dictionary and encoding etc. A few experiments are conducted on small graph datasets to show 30% space compression  compared to the naive edge list, and 50% compared to the Erdos-Renyi method. 
main_review: The paper studies the lossless compression of graphs with  deep learning. The authors propose to compress  the graphs in 3 steps: a partitioning algorithm decomposes the graph into elementary structures, which are mapped to the elements of a small dictionary, and an encoder translates the representation into bits. The partitioning  is parameterized  by a graph neural network output the likelihood of partitioning and optimized with the policy gradient method to achieve as small minimum description length as possible. The minimum description length are decomposed into several parts, the dictionary and encoding etc. A few experiments are conducted on small graph datasets to show 30% space compression  compared to the naive edge list, and 50% compared to the Erdos-Renyi method.

Overall, this paper presents a well-executed though not surprising method for compressing graphs by learning and exploiting the most common subgraph structures of the dataset. We can save space by using parameterized graph neural network and policy gradient to optimize the encoding length. The proposed method has many steps and obviously it takes time and effort to make sure the engineering eventually works out. It's interesting and in fact impressive to see authors can make such complicated engineering work out. On the down side, there are a few concerns listed below. In any case, my general evaluation is that this paper though not surprising or exciting, still has some values, and hence is borderline for acceptance, that is, it may be accepted or rejected depending on the meta context.  

Some detailed concerns:  

0. The datasets compressed are quite small so I'm not sure  why authors want to compress them.  Can you show  compression performance on datasets with > 300 GB? In my opinion, this is the most important technical weakness of the paper. 

1. The paper is generally easy to read, but it leaves  pretty  much all  details of the algorithm in the appendix. This makes it almost not possible to understand most details of the algorithm. Some questions: a) how exactly the graph partitioning  is parameterized by graph neural network, b) how the cuts connecting subgraphs are represented, c) how to construct dictionary and assign encoding, d) how to exactly connect the subgraphs and write  that in the bits, e) how graph isomorphism is conducted to  further save space.  A pseudo code should also be provided in main text.  The main ideas of these should all be described in the main text, possibly with pictures to better illustrate the algorithm steps.

2. The proposed method is quite complicated engineering, so authors should prepare more details describing how to make such complicated engineering actually work out. This is important for reproducibility as it's imaginable that readers will not be able to reproduce without more practical guidance, which will heavily limit the usage and influence of this paper, as most researchers obviously will not be interested in reading and applying complicated engineering papers that are not easy to follow and reproduce. 

4. I don't see any theoretical insights and depth in this paper. It's fine for practical papers, but I feel  authors can do better in this regard. What are the potential limitations and guarantees? Can you prove a lower and upper bound? Can you show tightness of the bound?

5. Missing related work that you may want to cite and discuss:

Solving graph compression via optimal transport. NeurIPS 2019.

Learning-Based Low-Rank Approximations. NeurIPS 2019.

Learning Sublinear-Time Indexing for Nearest Neighbor Search. ICLR 2020.
limitations_and_societal_impact: None
review_title: null

Meta-review: The paper presents learning-based method for compressing graphs. The method proceeds by partitioning the input graph into simpler parts, and using a learned dictionary to encode frequently appearing subgraphs. Empirical evaluation demonstrates improvements over multiple baselines. 

The main concern was that the sizes of graphs used in evaluation were relatively small. However, given that the technique was shown to generalize to several diverse data sets, most reviewers were comfortable that the results should generalize to larger graphs as well. 
Decision: Accept (Poster)