Partition and Code: learning how to compress graphs
Authors: Giorgos Bouritsas
Andreas Loukas
Nikolaos Karalias
Michael M. Bronstein
Venue: NeurIPS 2021 Poster (2021)
Keywords: lossless graph compression
neural compression
graph neural networks

Abstract: Can we use machine learning to compress graph data? The absence of ordering in graphs poses a significant challenge to conventional compression algorithms, limiting their attainable gains as well as their ability to discover relevant patterns. On the other hand, most graph compression approaches rely on domain-dependent handcrafted representations and cannot adapt to different underlying graph distributions. This work aims to establish the necessary principles a lossless graph compression method should follow to approach the entropy storage lower bound. Instead of making rigid assumptions about the graph distribution, we formulate the compressor as a probabilistic model that can be learned from data and generalise to unseen instances. Our “Partition and Code” framework entails three steps: first, a partitioning algorithm decomposes the graph into subgraphs, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally,  an entropy encoder translates the representation into bits.  All the components (partitioning, dictionary and distribution) are parametric and can be trained with gradient descent. We theoretically compare the compression quality of several graph encodings and prove, under mild conditions, that PnC achieves compression gains that grow either linearly or quadratically with the number of vertices. Empirically, PnC yields significant compression improvements on diverse real-world networks.

Partition and Code: learning how to compress graphs
Giorgos Bouritsas" Imperial College London, UK g. bouritsas@imperial. ac uk
Andreas Loukas EPFL, Switzerland andreas. www.kluueuflllccomm ch
Nikolaos Karalias
Michael M. Bronstein
EPFL. Switzerland nikolaos www.
Imperial College London Twitter, UK wwwnsteiiiinnerri............... ac uk
Abstract
Can we use machine learning to compress graph data? The absence ordering in graphs poses significant challenge to conventional compression algorithms, limiting their attainable gains as well as their ability to discover relevant patterns. On the other hand, most graph compression approaches rely on domain-dependent handcrafted representations and cannot adapt to different underlying graph dis- tributions. This work aims to establish the necessary principles a lossless graph compression method should follow to approach the entropy storage lower bound. Instead of making rigid assumptions about the graph distribution, we formulate the compressor as probabilistic model that can be learned from data and generalise to unseen instances. Our "Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into subgraphs, then these are mapped the elements of small dictionary on which learn a probability distribution, and finally, entropy encoder translates the representation into bits. All the components (partitioning, dictionary and distribution) are parametric and can be trained with gradient descent. We theoretically compare the compression quality several graph encodings and prove, under mild conditions, that PnC achieves compression gains that grow either linearly quadratically with the number of vertices. Empirically, PnC yields significant compression improvements on diverse real-world networks
1 Introduction
Lossless data compression has been one of the most fundamental and long-standing problems in computer science, It is by now well-understood that the intrinsic limits of compression are governed by the entropy of the underlying data distribution [I]. Crucially, these limits expose an intimate connection between compressibility and machine learning: the better one models the underlying data distribution (from limited observations) the more bits can be saved and vice-versa (2).
The compression of ordered data such as text, images, or video, underpins the modern technology from web protocols video streaming. However, graph-structured data remain a notable exception. As graph data are becoming more prevalent, it becomes increasingly important to invent practical ways to encode them parsimoniously.
There are three main challenges one faces when attempting to compress graphs:
"This work was done while Giorgos Bouritsas was visiting Dr. Andreas Loukas EPFL, Lausanne. 'The source code publicly available /tlttpss//github con//bboritsss/Pnd
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

CI. Dealing with graph isomorphism (GI). A key difficulty that distinguishes graphs from conven- tional data lies in the absence of an inherent ordering of the graph vertices. In order to be able to approach the storage lower bounds, isomorphic graphs should be encoded with the same codeword. However, since the complexity of known algorithms for GI is super-polynomial on the number of vertices [3] a direct use of GI is impractical for graphs consisting of more than few hundred vertices. Indeed, an examination of the graph compression literature reveals that most progress has been made by optimising vertex ordering and adapting methods originally invented for vectored data [4)6. Unfortunately, naively encoding graphs as vectors results in a significant loss in compressionf
C2. Evaluating the likelihood. An optimal encoder [ requires one to accurately estimate and evaluate the probabilities of all the possible outcomes of the underlying domain. When dealing with high-dimensional data, this can be addressed by partitioning the data into parts to obtain decomposition of the probability distribution: e.g., images can be compressed by modelling the distribution of pixels patches (10H12), and text by focusing characters or n-grams [13]1]] However, since graphs do not admit an efficiently computable canonical ordering, it is unclear what decomposition one should employ.
C3. Accounting for the description length of the learned model. The classical learning theory trade-off between model complexity and generalisation is of paramount concern for effective compression. Though in typical deep learning applications one can aim to model the data distribution with an overparametrised neural network (NN) that generalises well, utilising such models to compress information is problematic: since decoding is impossible unless the decoder also receives the learned model (i.e., the NN parameters), overparametrised models are, by definition, suboptimal. This is pertinent issue for likelihood-batt based neural approaches as overparametrisation is commonly argued to be a key component of why NNs can be trained 22
The Partition and Code (PnC) framework. Our main contribution is PnC. framework for learning compression algorithms suitable for encoding graphs sampled from underlying distribution. In the heart of PnC lie two ideas: (a) Learn to break the problem into parts. Rather than predicting directly the likeli- hood, we aim to learn how to decompose graphs into non-overlapping subgraphs, see Fig. T (b) Identify and code recurring subgraphs when possible. We use learned dictionary to code subgraphs that appear frequently. whereas rare subgraphs are encoded sep- arately. The dictionary is restricted to contain only a finite number of small recurring subgraphs. This biases the model towards interpretable and well gen- eralising solutions. Both the "partition" and "code" components of PnC are learned directly from the data, by optimising the total description length.
Figure 1: Illustration of the graph decom- position. The subgraph colours correspond to dictionary atoms 01, d2 and 0g. Cuts are denoted in red.
Our framework provides solution to the three challenges of graph compression. C1: By constraining the dictionary to only contain graphs of size up to a small constant, we can efficiently solve GI. C2: Graph partitioning provides with the desirable decomposition of the distribution. Using appropriate parametrised probabilistic models, we obtain a closed-form expression for the likelihood that can be later used by any doseett-opptimll entropy coder 23/25) C3: Since we use NNs to decompose the distribution (and not to predict the likelihood), we can rely on overparametrisation without having to relay the NN parameters to the decoder. Also, the complexity of our learned hypothesis (the dictionary) can be computed, and thus optimised, during training.
Theoretical results. Our analysis reveals that PnC can significantly improve upon less sophisticated graph encoders and justifies the usefulness of both the "Partition" and the "Code" component. Specifically, we prove that under mild conditions on the underlying graph distribution, PnC requires in expectation ( less bits than standard graph encodings, even if the latter are given access to an
"This follows by a simple counting argument: there are 2(5) labelled undirected graphs while the respective number for unlabelled graphs is asymptotically equal to 2(3) /nn (7]. Thus, if all graphs of n vertices are equally probable, encoding that does not consider isomorphism would sacrifice log n. bits [8.9.

---

oracle that solves GI. Further, the dictionary induces additional savings of (n) bits, with the gain being inversely proportional to the entropy of the distribution of the dictionary atoms. Thus, the more repetitive the patterns in the graph distribution are, the larger will be the compression benefits of PnC.
Practical algorithms. We instantiate of our framework using the following algorithmic modules: (a) a low-parameter learnable estimate of the probability distribution, (b) learning to select the dictionary from a graph universe of finite size, and (c) learning to partition. The latter a parametric randomised iterative algorithm, the probabilities of which are inferred from a Graph Neural Network (GNN) and optimised with reinforeement learning. Importantly, all algorithms can be jointly trained in order to minimise the total description length in a synergistic manner. We evaluate our framework on diverse real-world graph distributions and showcase compression gains with respect to both conventional and advanced baseline compressors, in observed and unseen data.
2 Related work
Engineered codecs. The majority of graph compressors are not probabilistic, but rely on hand- engineered encodings optimised to take advantage of domain-specific properties of e.g., Web- Graphs 4. social networks 16 26 27]. and biological networks (28). A common idea in these
approaches is vertex reordering 6 26 27, 29 31], where the adjacency matrix is permuted in such a way that makes it "compression -rappreessiioo-fenllll for mainstream compressors of sequences, such as gzip. The algorithms identifying the redorieriggs are usually based on heuristics taking advantage of specific network properties, e.g., community structure. Another recurrent idea is detect or use predefined frequent substructures (e.g., cliques) to represent more efficiently different parts of the graph via grammar rules [32]. These approaches do not attempt to model the underlying graph distribution and thus to approach the storage lower bounds, but strive to find a balance between compression ratios and fast operations on the compressed graphs Thus, despite their practical importance, they are less relevant to our work. A comprehensive survey can be found in 33
Theory-driven approaches. Several works have contributed to the foundations of the information content and the complexity of graphs R 9 44). However, few works have attempted to model the underlying graph distribution. Perhaps the most outstanding progress has been made for graphs modelled by the Stochastic Block Model (SBM) 41) Although originally invented for clustering be seamlessly used for compression due to their exact likelihood computation. In fact, as we argue in this work, virtually any graph clustering algorithm can be used successfully for compression, by defining codewords corresponding community-based random graph model. However, as our experiments confirm, such approaches are less effective at compressing graphs that do not contain clusters.
and network analysis purposes, these approaches
Likelihood -based neural approaches. Any generative model that can provide likelihood estimates in finite sample space can be used for lossless compression. As result, a plethora of likelihood- based neural compressors have been recently invented, ranging from autoregressive models for text [8
19 49
50 and images [I] [2] to latent variable models (51-55) (paired with bits-back
coding 56 57 and Asymmetric Numeral Systems- ANS (25)), normalising flows [58-61 and
However, the vast majority of current graph generators lack the necessary theoretical properties an effective graph compressor should have: they compute probabilities on labelled graphs instead of isomorphism classes by resorting to a heuristic ordering [64/[T] (in general this will be suboptimal unless we canonicalise the graph/solve graph isomorphism, while different orderings will have non-zero probabilities, hence we will incur compression losses), and/or do not provide a likelihood (6)
most recently, diffusion-based generative models 62 63
An important caveat, which often ignored in the literature, is that when parametrising the distribution with a neural network, the data cannot be recovered unless the decoder has access to the network itself. Hence is necessary account for the NN's description length when evaluating compression gains. However, generative models are usually parameter inefficient, while compressing them (especially during training) a challenging problem [77]. Note that this is significantly different than compressing neural classifiers, since the capacity to infer the likelihood up to high precision needs to be retained. Therefore, these approaches can have diminishing (or even negative) returns when the dataset size is not large enough. In contrast, by optimising the total description length (equivalent to maximum d-posteriori), we design a compressor that is practical even for small datasets, while the learned dictionary makes our compressor interpretable.
3

---

Other related work includes using compression objectives paired with heuristic algorithms for downstream tasks, such as motif finding 78 79 and graph summarisation [80]]] [T] lossy compres-
sion/coarsening 82 87,
and graph dictionary learning in the context of sparse coding [8 89
3 Preliminaries
We use capital letters for sets A, B, bold font for vectors x and matrices X, and calligraphic font X for families of sets. We express the information content in bits by using a base-2 logarithm log,
Graphs. Let G } be a graph with vertices V {VI..... Un and m edges, where egj E E whenever vertices 0, 2y E V are connected by an edge. For simplicity, we assume the graphs to be undirected, though the same methods apply to directed graphs well with minimal modifications. Let cut(A,, B) = {eg E E 04 E A and Uy E B} denote the set of edges with endpoints at two different vertex sets A, B V.
Information theory. Following the usual terminology in information theory and Minimum Descrip- tion Length (MDL) theory (2 90, (I], we assume an observation spuce 0 (in our case a space of possible graphs), and probability distribution p (sometimes referred to as probabilistic source) producing samples from the observation space. We observe dataset 9 {G1, G2..... G19) } of i..d. observations drawn from Note that this setting is in contrast with most works on graph compression 4 30 5 6) where the target is to compress a single large network, such web graph. Let a description method or symbol code CODE: 6 - {0. 1)" be mapping from the observation space to variable-length sequence of binary symbols, the output of which is codeword.
social network or
In the context of graph compression, we are interested in the description length of the code LCODE (G), or L(G) for brevity, i.e., the number of bits needed to encode the graph G, rather than the code itself, given a single requirement: the code needs to be uniquely decodable, meaning that any concatenation of codes can be uniquely mapped to sequence of observations. This property can be casily verified using only the description lengths by the well-know kolln Kraft- Mreff-MMMlllan inequality (lh.ss in formula (I)) an important implication of which is that every uniquely decodable code implies probability distribution (G) (r.h.s):
2 L(G)
2-L1C) < (code) - ((G) = EGEO 2 L(G) (distribution)
(I)
GEB
This equivalence allows to always define underlying probabilistic models when working directly with description lengths. When the Kraft-McMillan inequality holds with equality, we say that the code is complete; the case of strict inequality means the code is redundant. Moreover, in the case of complete codes, the expected length of the code corresponds to the distribution entropy [[][G]] (plus a constant term when the code is redundant). Thus, compression is synonymous to defining probabilistic models with the lowest possible entropy. An important notion that frequently appears in our theoretical analysis is the binary entropy, i.e., the entropy of bernoulli variable with probability of success p. To distinguish it from the general notion of entropy we will denote it as H(p) -p log p (1 p) log(1 p). It holds that < H(p) S 1, where the l.h.s equality is satisfied for p E {0, and the r.h.s. for 1/2.
Common graph encodings. An important principle that follow is that whenever we cannot make any assumptions about an underlying distribution, or modelling it is impractical, then the uniform distribution Punit is chosen for encoding. The reason is that uniform distribution worst- case optimal [90]: for any non-uniform unknown distribution p, there always exists a distribution q the corresponding encoding of which will be on expectation worse than the uniform encoding: Ez-pl-log (=)] > Ez<pl- log (=] In the context of graphs, when we cannot make any assumptions or when enumeration is impossible, we will be using a slightly more informative distribution: the Frdös-Rény: (ER) random graph model. This model assigns equal probability to all labelled graphs with n vertices and m edges. Assuming uniform probability over the possible number of vertices and number of edges m given we get:
Tmuil (G) = Log(Amax + 1) + log ((")
T1
+1)
log
2
(2)
where Tomax is an upper bound on the number of vertices. The "null" encoding compresses more efficiently graphs that are either very sparse or very dense (low-surprise) as the number of possible graphs with m edges is maximised when m n(n 1)/4.

---

4 The Partition & Code (PnC) graph compression framework
Our pipeline consists of three main modules: a partitioning module, a dictionary module, and an entropy encoding module. (a) The partitioning module is responsible for decomposing the graph into disjoint subgraphs and cross cross- subgraph edges (or cuts). Subgraphs play the role of elementary structures, akin characters or words text compression, and pixels or patches in image compression. (b) The dictionary is small collection of subgraphs (atoms) that are recurrent in the graph distribution. The dictionary module maps partitioned subgraphs to atoms the dictionary, allowing us to represent the graph as collection of atom indices and cuts. (c) Finally, this representation is given as input to the an entropy encoder that translates it into bits.
Decoding the graph in a lossless way involves inverting these three steps: initially the atom indices and cuts are decoded using the same probabilistic model with the encoder, then the atoms are retrieved from the dictionary, and finally all elements are composed back to obtain the original structure. The composition becomes possible by making sure that the cuts are encoded w.r.t. an arbitrarily chosen ordering of each atom's 's vertices, hence the decoded graph is guaranteed to be isomorphic to the input, but not necessarily with the same vertex ordering.
4.1 Step 1. Partitioning
The first step of PnC is to employ parametric partitioning algorithm PART, to decompose each graph G into subgraphs of bounded size:
PARTx(G) = (IC, C) and H(= = (H,, H2, ... Hob,
(3)
where H, = [V. E is the i-th subgraph and C = (V, Ec} is a b partite graph containing all cut edges Eec = F. F.. Variable indicates the learnable parameters.
Is partitioning necessary? In order to convert probability estimates to codewords, entropy encoders 25 need be able compute the probability of every graph in the observation space (or cquivalently to have access to the cumulative distribution function (c.d.f.)) see challenge C2 in Section [ To achieve this goal, one needs to partition the observation space in a way that permits efficient enumeration of the possible outcomes. Analogously, as we will see in Section 43 graph partitioning allows us to decompose the distribution and thus obtain closed-form expression for the likelihood. Further, Theorem suggests that partitioning brings a useful inductive bias for graph data providing significant storage gains compared distributiin--anosti baselines.
4.2 Step 2. Graph dictionary
Rather than naively compressing each subgraph in 3 under null model, an effective compression algorithm should exploit regularities in the output of PART We propose utilise dictionary that stores the most commonly occurring subgraphs. Concretely, we define a dictionary D to be collection of connected subgraphs (or atoms) from some universe [[:
= (a1, 02 ,.D)). where ag E $..
(4)
There are two viable choices for the atom encoding: (a) If the universe is small enough to be efficiently enumerable then we can assume uniform distribution over il which yields the description length I.(D) = D) log [4]. Intuitively, this would amount to storing the index of each atom within list enumerating it. (b) On the other hand, when too large to enumerate the atoms can be stored one-by-one based on the null-model encoding given in (2)
L(D)
Σ Lo.u( a.ED
(5)
It is important to note that, to be as effective as possible, the partitioning and the dictionary should be co-designed: should capture those subgraphs that are most likely, whereas PART, a should be biased towards subgraphs with similar structure. The use of dictionary makes it possible to explicitly account for (and thus optimise) the description length of the learned hypothesis (i.e., equation above), which is essential component of any compression algorithm (sce challenge C3 in Section
5

---

4.3 Step 3. Graph encoding
The last step entails compressing G by encoding the output (IC, C)) of PART g. As discussed in Section uniquely decodable code implies a probability distribution, i.e., (G) (3C, C*) which corresponds to a description length (HH C*-
log go (H. C), where & denotes the learnable parameters. In the following we explain how ds is decomposed.
Subgraphs. We opt for a dual encoding of subgraphs: one for the subgraphs that belong to the dictionary Haka, and one for non-dictionary subgraphs Hmmlll that are encoded with the help of a null model as in Eq. 2 This choice has a dual purpose: (a) It allows PART, to choose non-dictionary atoms. This is crucial to our approach, since constraining the partitioning to specific isomorphism classes would significantly complicate optimisation. (b) Further, it enables us to maintain a balance between two common structures found in real-world networks-frequee dictionary), and low-entropy subgraphs as implied by the null model (i.e., very sparse or very dense subgraphs). The distribution is therefore decomposed into the following components:
subgraphs (stored in the
Number of subgraphs. First, we encode the number dictionary and non-dictionary subgraphs (bdiet and mull respectively) as follows:
(beict, mmall)
Binomial(baiaale ()) (baict)
-6)
San han
qo (b),
where - 8 H D) is the probability of arbitrary subgraph to belong in the dictionary and (b) is a categorical.
Dictionary subgraphs. The dictionary subgraphs encoded in permutation invariant way via multinomial distribution, i.e, we encode the histogram of atoms:
(a dn b
4sb (ddic) buiit, D) Multinomial(bi, b2, ........ppp beiitt Φ) = baser!
aED
where b. = =| E Hail H _ a}} and E.ED by bdiet.
Non-Dictionary subgraphs. The non-dictionary subgraphs are encoded independently according the null model:
go (H (rult D)
II
Jaun (H;).
H. E3Ki
Cuts. We encode the cuts conditioned on the subgraphs, using non- non-paraeetric uninformative null
model for multi-partite graphs similar [45] (see Appendix [B.] for the detailed expression) that prioritises low-entropy cuts. In this way we give more emphasis to the subgraphs and an inductive bias towards distinct clusters in the graph.
Overall, the description length of (HC, C) PART (G) is given by (H,, D) = Lop (baict, bman) + L.g (Hdier) Udiet: D) + Lmall (Hmun D) + Lmalt Lmn (CIH))
(9)
and the learnable parameter set is 88 (b)}
Aan b=bann" (oo(a))oED)
Remarks about graph isomorphism (GI). Observe that given a fixed decomposition, our parametri- sation is invariant to isomorphism, which is desirable property since isomorphic graphs will be assigned codewords with the same length. Note that this is not sufficient to guarantee that all isomor- phic graphs will be assigned the same codeword. Since this would imply a solution to GI, it remains an open problem. However, our graph encoding provides desirable tradeoff's between the expressivity of the probabilistic model, its number of parameters, and computational complexity, since it can adapt to different graph distributions using only few parameters and solving GI only for small graphs.
4.4 Selecting a hypothesis by minimising the total description length
Putting everything together, in order to encode graph dataset 9 sampled i.i.d. from & we minimise the total description length
min O.D.O
Σ (PART((G)) D) + L(DD)
(10)
GES

---

with respect to the parameters 0 of the parametric partitioning algorithm, the dictionary D, and the parameters @ of the probabilistic model. Eq. (TO) is typical two-part Minimum Description Length
(MDI) objective [92 [90. Using standard MDI. terminology. the tuple (0, D, Φ) is a point hypotheses
and minimising (10 amounts finding the simplest hypothesis that best describes the data.
Theoretical analysis: quadratic and linear gains
The following section performs comparative analysis of the description length growth rate of various graph compressors. We compare PnC against two strong baselines: (a) The code length Lpant induced by pure partitioning-base based graph encoding. Here, a graph is decomposed into subgraphs and cuts, but the distribution of subgraphs is not modelled (i.e., both subgraphs and cuts are encoded with a null model Lpaat (G) Lmuit (IFC + muult (CIHH). (b) The code length of encodings that do not rely partitioning but encode each graph as a whole. Importantly, our results hold even for those baselines that encode the isomorphism class of each graph, rather than the graph itself, such the Erdös-Renyi model for unlabelled graphs of rt vertices: LER-S log [8,,m| + log(n² + 1), where 8n.m is the set of all graphs with n vertices and m edges. (E) serves lower bound typical encodings such as that of Eq. (2) but can be impractical to implement due to the complexity of GI. The analysis of additional baselines can be found in Appendix [A]
Our main theorem shows that, under mild conditions on the underlying graph distribution, the expected description lengths of the compared encodings are totally ordered:
Theorem 1. Consider a distribution p over graphs with vertices and partitioning algorithm that decomposes graph into b blocks of k = 011 vertices. Then holds that:
(1b)
(1a) S EGSpIIERS((G)
EGppIIpac S PTu
(11)
under the following conditions:
(Ia) log(k2+1)) + Hmy < Hm, where Hmy = EE (T22 ) and H., EG [H( ]1 is the 12
(H(
expected binary entropy of the cut size may between two subgraphs and that of the total number of edges m, respectively.
(Ib) [D] (122 + 1)2*"Bmi, where [D] is the size of the dictionary and Hm, Ra [H 2 the expected hinary entropy of the number of edges my in a subgraph.
The compression gains are:
[G (G)) S BT -n² -n²(mm log(k2 + -mmsss
(12)
122
and
H(D) - log(k2 +1)
EG LPac S Bepnp nk(1 -6) Hm,
(13)
k22
where 1 - 5 is the probablity that a subgraph belongs in the dictionary and Hi(D) = (ajag(aj]aa) is the entropy of the distribution on dictionary atoms (a(a).
Theorem I provides insights the compressibility of certain graph distributions given their structural characteristics. In particular, we can make the following remarks: (a) Condition (1a) can be satisfied even for very small values of k as long as the graphs possess community structure. Perhaps counter- intuitively, when k = 0(1) we can satisfy the condition even if the communities have O(n) size by splitting them into smaller subgraphs. This is possible because, in contrast the majority of graph partitioning objectives that are based on minimum cuts, the compression objective attains its minimum when the cuts have "low entropy". Since communities that are tightly internally connected have large cuts, Hm, and the code length will be kept small. This is key observation that strongly motivates the use of partitioning for graph compression. (b) Condition (1b) provides an upper bound to the size of the dictionary, which can be easily satisfied for moderately small values of k. More importantly, the dependence of the compression gain on the entropy (D), reveals that dictionary atoms should be frequent subgraphs in the distribution, confirming our intuition. The bounds also show that, since the probabilities of the atoms are estimated from the data, PnC does not need to make assumptions about the inner structure of the subgraphs and can adapt to general distributions.
7

---

In Appendix A.44, we also provide theoretical evidence on the importance of of encoding dictionary subgraphs as isomorphism classes instead of adjacency matrices, which is related challenge C1 mentioned in the introduction. In particular, Theorem 2 that, if isomorphism is not taken into account, the number of bits that will be lost will grow linearly with the number of vertices, All proofs and detailed assumptions can be found in Appendix
6 Optimisation and learning algorithms
We turn our focus to learning algorithms for the optimisation of the MDL objective TT). The following sections explain how each parametric component of PnC is leamee.
Subgraph encoding Φ. The graph encoding is parametrised as follows: (as) and (b(b) are parametrised by learnable variables that are converted into categorical distributions over the dictionary atoms and the number of vertices respectively, using softmax function. Similarly, de is parametrised by a learnable variable converted to probability via the sigmoid function.
Dictionary D. Let 1( 22,..2..... )
{ (01;02,-.. ....a.. be a practically enumerable universe and define
[1 if a E D 0 otherwise.
Thus, z; indicates whether D contains subgraph a,. Now, optimising w.r.t the dictionary amounts to finding the binary assignments for that minimise (10). To circumvent the combinatorial nature of this problem, we apply the continuous relaxation &, a (ets), Vi E {0, (,....,...). where a is the sigmoid, ib are learned continuous variables, and ât [0. 1] fractional alternative to zz. Appendix B.3 shows how (10p can be re-written w.r.t. x and optimised by using the surrogate gradient w.r.t á;.
It is important to note that, in practice, we do not have to introduce indicator variables for the entire universe: Since most subgraphs a, will be never encountered in the graph distribution, we build the universe adaptively during training, by progressively adding the different graphs that the partitioning algorithm yields. We also allow the universe to contain subgraphs of size up to A = O(1), in order to ensure that the isomorphism testing between atoms and subgraphs can be efficiently computed.
Parametric graph partitioning algorithm. Finding the graph partitions that minimise (TO) in principle requires searching in the space of partitioning algorithms. Instead, we constrain this space via a differentiable parametrisation that allows us to perform gradient-based optimisation. Currently, learning to partition is an open problem, as to the extent of our knowledge known neural approaches require a fixed number of clusters (3 or do not guarantee that the subgraphs are connected (96].
Our Neural Partitioning is randomised algorithm parametrised with a graph neural network (GNN). When run on a graph, the GNN outputs a random (H, C) together with corresponding probability Pe (GNN(H,, CIG) and training is performed by estimating the gradients w.t.t. 0 with REINFORCE (97). Our algorithm proceeds by iteratively sampling (and removing) subgraphs from the graph until becomes empty. At each step we select subgraph Hr, by first sampling its vertex count k; and subsequently sampling at most ky vertices. To guarantee connectivity, we also sample the vertices iteratively and mask-out the probabilities outside the pre-selected vertices' neighbourhoods. The complexity of the algorithm is Onn). where n the number of the vertices of the graph. Please refer to Appendix B.4 for an in-depth explanation of the algorithm and relevant implementation details. We stress that we mainly consider this algorithm as a proof of concept that we ablate against other non-paree non-parmmttric partitioning algorithms. A plethora of solutions can be explored in parametric setting and we welcome future work in this direction.
MDL objective. Given dataset S. we train all components by minimising the description length:
= =x()) +
Σ GES
(14)
Taking the expectation over the GNN output ~ ~M (J, CIG), we calculate the gradients as: VoL(9) = Eaeg E[V & (H,, GNN (HC and V9L Eceg (XL, V(D)Vslnp
ED) EE[V L CID)),
8

---

Figure 2: PnC + Neural Part. Most probable graphs in the IMDB-B dataset (left) and the attributed MUTAG dataset (right). Atom types and bond types are represented as vertex and edge attributes.
7 Empirical Results
We evaluate our framework a variety of datasets: small molecules, proteins and social networks [98] [02]. Across all methods, we assume an optimal encoder that attains the entropy lower bound (this is often realistic since modern entropy coders asymptotically approach it) to evaluate the expressive power of each model independently of the encoder. We measure the description length of the data as their negative log-likelihood (NLL) under each probabilistic model, as well as the total description length by adding the cost of the parameters which need be transmitted to the decoder (see Appendix D for details).
Baselines. We aim assess representative approaches across the entire spectrum of graph proba- bilistic models, i.e., from completely uninformative non-parametric distributions to overparametrised neural generative models. We consider the following types of compressors: (a) Null models. We select the uniform model, where all edges are assumed to be sampled independently with probability equal 0.5, the edge list model, typical graph representation, and the Erdös-Rend Renyi model (Eq. (2). (b) Partitioning siattioonnn-basdd.. non-parametric methods that aim at grouping vertices in tightly-onnected clusters. They can be used for any type of sparse matrix [103] and are based on the assumption that there exists a hidden community structure in the graph. The partioning algorithms used are SBM fitting 44 Louvain 104] and Label Propagation [105] clustering. The encoding we use to encode the clusters corresponds exactly to the SBM assumptions, hence the partitioning-han based results are always superior for this approach. (c) Likelihood bassd neural compressors. As with any likelihood-basee model, graph generative models can be transformed into graph compressors. We evaluate the original GraphRNN (66) and GRAN 68 networks, as well as smaller instantations that have undergone model compression using the Lottery Ticket Hypothesis algorithm [106].
Results. Tables D and 2 report the compression quality of each method measured in terms of the average number of bits required to store each edge in a dataset (bpe). We present four variants of PnC, differing on the type of partitioning algorithm used [0SS] 104 We report separately the cost of compressing the data well as the total cost (including the parameters). Several observations can be made with regards to the baselines:
First off, off- tff-th likelihood- breeeeood-bbsed neural approaches are poor compressors due to failing to address challenge C3. These models exhibit an unfavorable trade-off between the data and model complexity, often requiring significantly more bpe than the null models. Although model compression techniques can alleviate this tradeoff (especially for larger datasets, e.g., pruned GraphRNN on ZINC), in most of the cases the compression ratios required to outperform PnC are significantly higher than the best that have been reported in the literature (See Table 4 in the Appendix). Perhaps more importantly, it is unclear how to optimise the model description length during training (one of the few exceptions [177) and usually model compression might be tedious and is based on heuristics 108 See Appendix C.2 for more details and additional experiments.
In addition, as expected from Theorem (la), non- poramaraetriic clustering algorithms work well when the dataset has a strong community structure, but are not good choice for more structured datasets. For instance, the best clustering algorithm requires 2.4x more bpe for ZINC than the best PnC. PnC variants achieve the best compression in all datasets considered. This follows from Theorem (1b), since the learned dictionaries are relatively small, and confirms our hypothesis that our framework is sufficiently flexible to account for the particularities of each dataset. As seen, neural partitioning

---

recovered for social Table 1: Average bits per edge (bpe) for molecular graph datasets. First, Second, Third
Method
Graphh typo
Small Mokxulls
type
Dataset
MUTAG
PTC
ZINC
data
paramns
data
total
paraens
data
Total
paramn
Uniform (raw adjac.)
8.44
17.43
10.90
Nuil
Edge list
7.97
9.38
8.60
Renyi
Partitioing
3BM-Bayes
4.62
5.12
4.75
parametric)
Louvain
4.80
5.27
4,77
PropClust
4.85
Neural
GraphRNN
1.33
3338.21
38&K
1.57
1394, 59
389K
1.62
43.16
388K
(likeihood)
GRAN
0.81
12557.75
1-60K
2.18
$269.82
1470K
1.30
157.7
1461K
GraphRNN (pruned)
GRAN (praned)
2.59
24.56
2.23K
4.31
14.00
2.36K
3.26
3.47
1.99K
PaC
PaC SBM
3.81
4.11
49
4.38
4.79
155
3.34
3:45
594
PaC
PaC + PropClust
2.42
3.03
63
3.38
4.02
178
2.20
2.35
726
PoC + Neural Part.
2,1740.22
2.45+00.02
46+1
2,6340.266
2.97s0.14
143+31
2,040.022
2,07:0.033
384+105
Table 2: Average bits per edge (bpe) for social and protein graph datasets. First, Second, Third
Method
Graph type
Biology
Social Networks
type
PROTEINS
IMDB-M
data
total
params
data
total
params
data
total
params
Uniform (raw adjac.)
24.71
2.52
1.83
Null
10.92
7.74
Erdös Enndi-Renyi
5,46
1.94
1.32
(non-parametric)
Pattitioinng
Louvain
SBM-Bayes
PropClust
4.11
3,95
3,98
0.80
1.99
1.22
1.37
0.60
Neural
GruphRNN
2.03
156
392K
1.03
132.27
395K
0.72
127.84
392K
(likelihood)
GRAN
607.96
1545K
0.26
488.88
1473K
0.17
475.13
GripRRNN (pruned)
2,63
3.76
2.56K
1.43
1.92
1 1.88
0.91
1.39
1.28%
GRAN (pruned)
4.28
5,11
1,78K
0.84
1,75
2.38K
0.55
1,41
2.31K
PnC
PnC + Lovaiin
3.34
3.58
854
0.96
1.02
202
0.66
0.70
141
PuC PropClust
3,42
3.68
866
1.45
1.64
241
0.93
1,04
178
3.51+0.23
717=61
1.05=0.04
0.6640005
0.7240.05
performs in every case better, par with the combination of PnC with the Louvain algorithm. However, the social network datasets, the combination of PnC with SBM achieves the best performance. This occurs because these networks fit nicely with the SBM inductive bias (which as a matter of fact exactly that of low-entropy cuts), and most importantly, due to the fact that the clusters recovered by the SBM are small and repetitive, which makes them ideal for the PnC framework. We also observe that there room for improvement for the neural partitioning variant, and hypothesise that more powerful parametrised algorithm be designed. Since learnable partitioning is still an open problem, we leave this research direction to future work.
Fig. 2 shows the most likely dictionary atoms for the IMDB-B and the MUTAG dataset (also including attributes Appendix C.3 provides additional experiments). Observe that cliques or near-cliques and typical molecular substructures, such carbon cycles and junctions networks and molecules respectively. This clearly highlights the connection between compression and pattern mining and provides evidence for potential applications of our framework.
8 Conclusion
This paper marks an important step towards learnable cntropy-based graph compression. To the best of our knowledge, our work represents the first attempt to address the basic principles of parametric compressors of unlabelled graphs learned from observations. In addition, we suggest practical instantiations of our framework that can be trained with gradient- based optimisation, accounting for the total description length, hence aiming for the largest possible parsimony. A number of new research questions arise, such as how to design more expressive, albeit parsimonious distribution estimators, how to improve the neural partitioning algorichms, and how to ensure scalability to single large networks that pose a significant challenge w.r.t the memory constraints of GPUs. We hope that work will inspire further research in this emerging research area.
10

---

Acknowledgements and Disclosure of Funding
We would like to thank the anonymous reviewers for their valuable feedback and suggestions to improve our paper. This project was partially funded by the ERC Consolidator Grant No. 724228- LEMAN. Giorgos Bouritsas is partially supported by a PhD scholarship from the Dpt. of Computing. Imperial College London. Andreas Loukas and Nikolaos Karalias thank the Swiss National Science Foundation for supporting them in the context of the project "Deep Learning for Graph Structured Data", grant number P/00P 179981. Michael Bronstein acknowledges support from Google Faculty awards and the Royal Society Wolfson Research Merit award.
References
[1] Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-423, 1948.
[2] David JC MacKay and David JC Mac Kay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
[3] László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth anmual ACM symposium on Theory of Computing, pages 684-697, 2016.
[4] Paolo Boldi Sebastiano Vigna and P Boldi. The webgraph framework i: compression tech- niques. In Proceedings of the 13th International Conference on World Wide Web, pages 595 602, 2004.
[5] Yongsub Lim, Kang, and Christos Faloutsos. Slashburn: Graph compression and mining beyond caveman communities. IEEE Transactions Knowledge and Data Engineering, 26(12):37773308, 2014.
[6] Laxman Dhulipala, Igor Kabiljo, Brian Karrer, Giuseppe Ottaviano, Sergey Pupyrev, and Alon Shalita. Compressing graphs and indexes with recursive graph bisection. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1535-1544, 2016.
[7] Frank Harary and Edgar M Palmer. Graphical enumeration, Elsevier, 2014.
[8] Moni Naor. Succinct representation of general unlabeled graphs. Discrete Applied Mathematics, 28(3):303-307, 1990.
[9] Yongwook Choi and Wojciech Szpankowski. Compression of graphical structures: Fun- damental limits, algorithms, and experiments. IEEE Transactions on Information Theory, 58(2):620-638, 2012.
[10] Jon Sneyers and Pieter Wuille. Flif: Free lossless image format based on maniac compression. In 2016 IEEE International Conference on Image Processing (ICIP), pages 66-70. IEEE, 2016.
[11] Aäron van den Oord, Nal Kalchbrenner, and Koray Kavukcuoglu. Pixel recurrent neural net- works. Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. volume 48 of JMLR Workshop and Conference Proceedings, pages 1747-1756. JML.R. ..ogg 2016.
[12] Fabian Mentzer, Firikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Practical full resolution learned lossless image compression. In Proceedings of the IEEE/VE Conference on Computer Vision and Pattern Recognition, pages 10629-10638, 2019.
[13] Terry A Welch. A technique for high-performance data compression. Computer, 17(06):8-19, 1984.
[14] Jacob Ziv and Abraham Lempel. universal algorithm for sequential data compression. IEEE Transactions information theory, 23(3):337-343, 1977.

---

[15] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE transactions on Information Theory, 24(5)550--53,, 1978.
[16] Timothy Bell, Ian Witten, and John G Cleary. Modeling for text compression. ACM Computing Surveys (CSUR), 21(4):557-59) 1989.
[17] Michael Burrows and David Wheeler. A block-sorting lossless data compression algorithm. In Digital SRC Research Report. Citeseer, 1994.
[18] Jürgen Schmidhuber and Stefan Heil. Sequential neural text compression. IEEE Transactions on Neural Networks, 7(1):142-146, 1996.
[19] Matthew Mahoney. Fast text compression with neural networks. In FLAIRS conference, pages 230-234, 2000.
[20] Simon S. Du, Xiyu Zhai, Barnaáás Póczos, and Aarti Singh. Gradient descent provably optimizes over parammmeeteeee neural networks, In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019.
[21] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssüsssan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 244-253. PMLR, 2018.
[22] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over preettrratttiiiitionn. In Proceedings of the 36th International Conference on Machine Learn- ing, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 242-252. PMLR, 2019.
[23] David A Huffmann A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-11000 1952.
[24] Ian H Witten, Radford M Neal, and John G Cleary. Arithmetic coding for data compression. Communications of the ACM, 3006):500-540, 1987.
[25] Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv: 2013.
[26] Alberto Apostolico and Guido Drovandi. Graph compression by bfs. Algorithms, 2(3):1031- 1044, 2009.
[27] Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th international conference on World Wide Web, pages 587-596, 2011.
[28] Leonid Peshkin. Structure induction by lossless graph compression. In 2007 Data Compression Conference (DCC'07), pages 53-62. IEEE, 2007.
[29] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Michael Mitzenmacher, Alessandro Pan- conesi, and Prabhakar Raghavan. On compressing social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 219-228, 2009.
[30] Francisco Claude and Gonzalo Navarro. Fast and compact web graph representations. ACM Transactions on the Web (TWEB), 4(4)
[31] Ryan A Rossi and Rong Zhou. Graphzip: a clique- clique-based sparse graph compression method. Journal of Big Data, 5(1:1-114, 2018.
[32] Sebastian Maneth and Fabian Peternek. Compressing graphs by grammars. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 109-120. IEEE, 2016
[33] Maciej Besta and Torsten Hoefler. Survey and taxonomy of lossless graph compression and space-efficient graph representations. arXiv preprint arXiv:1806.0179) 2018.
12

---

[34] Ernesto Trucco. A note on the information content of graphs. The bulletin of mathematical biophysics, 18(2):129-135, 1956.
[35] Ernesto Trucco. On the information content of graphs: compound symbols; different states for each point. The bulletin of mathematical biophysics, 18(3):237-253, 1956.
[36] János Körner. Coding of an information source having ambiguous alphabet and the entropy of graphs. In 6th Progue conference information theory, pages 411 411-425, 1973.
[37] György Turán. On the succinct representation of graphs. Discrete Applied Mathematics, 8()):299-24, 1984.
[38] Matthias Dehmer. Information- theeorttonnthooortiic concepts for the analysis of complex networks. Applied Artificial Intelligence, (17-8):684-706, 2008.
[39] Matthias Dehmer, Nicola Barbarini, Kurt Varmuza, and Armin Graber. A large scale analysis of informatiion-theoreiee network complexity measures using chemical structures. PLoS One, 4( (15)7 2009.
[40] Abbe Mowshowitz and Matthias Dehmer. Entropy and the complexity of graphs revisited. Entropy, 14(3):559-557) 2012.
[41] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardr. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
[42] Martin Rosvall and Carl T Bergstrom. Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences. 2008.
[43] Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
[44] Tiago P Peixoto. Entropy of stochastic blockmodel ensembles. 85(5):056122, 2012.
Physical Review E,
[45] Tiago P Peixoto. Parsimonious module inference in large networks. Physical review letters, 10(14)):487011 2013.
[46] Tiago Peixoto.
Nonparametric bayesian inference of the microcanonical stochastic block model. Physical Review E, 95(1):012317,
[47] Tiago P Peixoto. Bayesian stochastic blockmodeling. Advances in network clustering and blockmodeling, pages 289-332, 2019.
[48] Clement Lee and Darren J Wilkinson. A review of stochastic block models and extensions for graph clustering. Applied Network Science, 4(1):1-50, 2019.
[49] David Cox. Syntactically informed text compression with recurrent neural networks. arXiv preprint arXiv: 1608.0088... 2016.
[50] Mohit Goyal, Kedar Tatwawadi, Shubham Chandak, and Idoia Ochoa. Deepzip: Lossless data 2018.
compression using recurrent neural networks. arXiv preprini
[51] James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
[52] Friso H. Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 3408-3417. PMLR, 2019.
[53] James Townsend, Thomas Bird, Julius Kunze, and David Barber. Hilloe: lossless image com- pression with hierarchical latent variable models. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26- 26-30, 2020. OpenReview.net, 2020.
13

---

[54] Yangjun Ruan, Karen Ullrich, Daniel Severo, James Townsend, Ashish Khisti, Arnaud Doucet, Alireza Makhzani, and Chris Maddison. Improving lossless compression rates via monte carlo bits-back coding. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9136-9111 9147. PMLR, 2021.
[55] Daniel Severo, James Townsend, Ashish Khisti, Alireza Makhzani, and Karen Ullrich. Com- pressing multisets with large alphabets. arXiv preprint arXiv:2107.09202 2021.
[56] Chris S Wallace. Classification by minimum- message-length inference. In International Conference on Computing and Information, pages 72-81. Springer, 1990.
[57] Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pages 5-13, 1993.
[58] Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with flows via local bits-back coding. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3874-3883, 2019.
[59] Emiel Hoogeboom, Jorn W. T. Peters, Rianne van den Berg, and Max Welling. Integer discrete flows and lossless compression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 12134-12144, 2019.
[60] Dustin Tran, Keyon Vafa, Kumar Krishna Agrawal, Laurent Dinh, and Ben Poole. Discrete flows: Invertible generative models of discrete data. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 14692-14701, 2019.
[61] Rianne van den Berg, Alexey A. Gritsenko, Mostafa Dehghani, Casper Kaae Sønderby, and Tim Salimans. IDF++; analyzing and improving integer discrete flows for lossless compression. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[62] Diederik P Kingma, Tim Salimans, Ben Poole, and Jonathan Ho. Variational diffusion models. arXiv preprint f07.::/000000330 2021.
[63] Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. arXiv preprint arXiv:21 (tt::2/10.0200. 10.02037, 2021.
[64] Wengong Jin, Regina Barzilay, and Tommi S. Jaakkola. Junction tree variational autoencoder for molecular graph generation. In Proceedings of the 35th International Conference on Machine Learning. (ICML), volume 80, pages 2328-2337 PMLR, 2018.
[65] Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 18Vv:1803.03324 2018.
[66] Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15 15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5694-5703. PMLR, 2018
[67] Qi Liu, Miltiadis Allamanis, Mare Brockschmidt, and Alexander L.. Gaunt. Constrained graph variational autoencoders for molecule design. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pages 7806-7815, 2018.
[68] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancowver, BC, Canada, pages 4257 2019.
14

---

[69] Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In Proceedings of the 37th International Conference on Machine Learning, ICMI, 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2302-2311 2312. PMIR, 2020.
[70] Chence Shi, Minkai Xu, Zhaocheng Zhu, Weinan Zhang, Ming Zhang. and Jian Tang. Graphaf: a flow-based autoregressive model for molecular graph generation. In 8th International Conference on Learning Representations, ICLR 2020. OpenReview.net, 2020.
[71] Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. In Proceedings of the 38th International Conference on Machine Learning, ICML, volume 139 of Proceedings of Machine Learning Research, pages 7192-7203, PMLR, 2021.
[72] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv: 1973, 2018.
[73] Carl Yang, Peiye Zhuang, Wenhan Shi, Alan Luu, and Pan Li. Conditional structure generation through graph variational generative adversarial nets. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1338-1349, 2019.
[74] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating graphs via random walks. In Proceedings of the 35th International Conference on Muchine Learning, (ICML), volume 80, pages 609-618. PMLR, 2018.
[75] Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 4474 4484. PMLR, 2020.
[76] Meng Liu, Keqiang Yan, Bora Oztekin, and Shuiwang Ji. Graphebm: Molecular graph generation with energy-based models. arXiv preprini urXiv:2102.00544: 2021.
[77] Thomas Bird, Friso H. Kingma, and David Barber. Reducing the computational cost of deep generative models with binary neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[78] Nikhil S Ketkar, Lawrence B Holder, and Diane J Cook. Subdue: Compression frequent pattern discovery in graph data. In Proceedings of the Ist international workshop on open source data mining: frequeni paltern mining implementations, pages 71 71-76, 2005.
[79] Peter Bloem and Steven de Rooij. Large-scale network motif analysis using compression. Data Mining and Knowledge Discovery, 1421-143, 2020.
[80] Danai Koutra, Kang, Jilles Vreeken, and Christos Faloutsos. Vog: understanding large graphs. In Proceedings of the 2014 SIAM international conference data mining, pages 91-99. SIAM, 2014.
Summarizing and
[81] Kristen LeFevre and Evimaria Terzi. Grass: Graph structure summarization. In Proceedings of the 2010 SIAM International Conference on Data Mining, pages 454-465. SIAM, 2010.
[82] Farshad Nourbakhsh, Samuel Rota Bulo, and Marcello Pelillo. A matrix factorization approach to graph compression with partial information. International Journal of Muchine Learning and Cybernetics, 6(4):523-536, 2015.
[83] Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018 volume 80 of Proceedings of Machine Learning Research, pages 3243-3252. PMLR, 2018.
[84] Andreas Loukas. Graph reduction with spectral and cut guarantees. Mach. Learn, Res., 20(116):1-42) 2019.
15

---

[85] Vikas K. Garg and Tommi S. Jaakkola. Solving graph compression via optimal transport. In Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 8012-8023, 2019.
[86] Yihe Dong and Will Sawin. Copt: Coordinated optimal transport on graphs. Advances in Neural Information Processing Systems, 33, 2020.
[87] Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4452-4462. PMLR, 2020.
[88] Xuan Zhang, Xiaowen Dong, and Pascal Frossard. Learning of structured graph dictionaries. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3373-3376. IEEE, 2012.
[89] Cédric Vincent-Cuaz, Titouan Vayer, Rémi Flamary, Marco Comeli, and Nicolas Courty. Online graph dictionary learning. In Proceedings of the 38th International Conference on Machine Learning, (CM1,2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Muchine Learning Research, pages 10564-10574. PMLR, 2021.
[90] Peter D Grünwald and Abhijit Grunwald. The minimum description length principle. MIT press, 2007.
[91] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
[92] Jorma Rissanen. Modeling by shortest data description. Automatica, 1 14(5):465-471, 1978.
[93] Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. End to end learning and optimization on graphs. In Advances in Neural Information P Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 4674 4685, 2019.
[94] Azade Nazi, Will Hang. Anna Goldie, Sujith Ravi, and Azalia Mirhoseini. Gap: Generalizable approximate graph partitioning framework. arXiv preprint arXiv:1903.0088 2019.
[95] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 874-883. PMLR, 2020.
[96] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning frame- work for combinatorial optimization on graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 6-, 2020, virtual, 2020.
[97] Ronald J Williams. Simple statistical foaliint-ollowing algorithms for connectionist rein- forcement learning. Machine learning. 8(3):229-22 256,, 1992.
[98] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
[99] John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zine: a free tool to discover chemistry for biology. Journal of chemical information and 2012.
modeling, 52(7))1757-11)
[100] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
[101] Karsten M Borgwardt, Cheng Soon Ong. Stefan Schönauer, SVN Vishwanathan, Alex J Smola, and Pater Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21 ('suppp_))i47-5566. 2005.
16

---

[102] Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 17(1):107-108, 2001.
[103] Deepayan Chakrabarti, Spiros Papadimitriou, Dharmendra Modha, and Christos Faloutsos. Fully automatic associasoossss In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 79-88, 2004.
[104] Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 P10000,,,,, 2008.
[105] Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. Near linear time algorithm to detect community structures large-scale networks. Physical review E. 76(3):036106, 2007.
[106] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations, ICLR 20/9, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[107] Marton Havasi, Robert Peharz, and José Miguel Hernández- Lobato. Minimal random code learning: Getting bits back from compressed model parameters. In 7th International Con- ference on Learning Representations, ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019.
[108) Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- work with pruning, trained quantization and huffman coding. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[109] Christos Louizos, Karen Ullrich, and Max Welling. Bayesian compression for deep learning. Advances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3288-3292 0298, 2017.
[110] Song Han, Jeff Pool, John Tran, and William J. Dally. Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1135-1143, 2015.
[111] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint arXiv:1503.02531, 2015.
17


Reviews:
[{"review_id": "XC89GeGcDHX", "reviewer": "Reviewer_Q2XE", "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. ", "questions": "", "limitations": "", "rating": 5, "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": "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.\n\nOverall, 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.  \n\nSome detailed concerns:  \n\n0. 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. \n\n1. 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.\n\n2. 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. \n\n4. 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?\n\n5. Missing related work that you may want to cite and discuss:\n\nSolving graph compression via optimal transport. NeurIPS 2019.\n\nLearning-Based Low-Rank Approximations. NeurIPS 2019.\n\nLearning Sublinear-Time Indexing for Nearest Neighbor Search. ICLR 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UAevhHU30Om", "reviewer": "Reviewer_u2r2", "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. \n", "questions": "", "limitations": "", "rating": 8, "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": "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.\n\n- Pros: \n\t- Overall the article is very well written and enjoyable to follow.\n\t- 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.\n\n- Cons:\n\t- Some parts of the article are a bit vague/unclear in my opinion and would deserve more details.\n\t- There are a lot of \"black-boxes\" so that it is sometimes hard to understand the intuitions behind the different mechanisms.\n\t- I am not really convinced by the usefulness of the \"dictionary part\".\n\nOverall 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).\n\n- About the universe and the dictionnary: \n\n(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.\n\n(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.\n\n- About the encoding: \n\n(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 ?\n\n- About the partitioning algorithm: \n\n(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 ?  \n\n- About the decoding:  \n\n(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 ?\n\n(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.\n\n\n- Experiments: \n\n(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).\n\n\n- Other comments: \n\t- I think in Section 4.5 authors talk about eq (8) and not eq (7) \n\n\n----- AFTER REBUTTAL -----\n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7LiC-vm0c8l", "reviewer": "Reviewer_5v1K", "summary": "The authors establish a theoretically well-motivated, general-purpose graph compression framework they call Partition-and-Code (PnC).\nThe 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.\n\nThe compression pipeline, given a graph partitioning function and a subgraph dictionary, works as follows:\n1) 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.\n2) 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.\n\nImportantly, 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.\nThe 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.\n\nThe authors perform experiments on multiple popular graph datasets and achieve good results.\n", "questions": "", "limitations": "", "rating": 8, "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": "# Strengths\nThe work is based on a well-motivated idea and contains several well-executed solutions to the problems considered.\n\nThe 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.\n\nThe proposed solutions to all 3 steps are simple, sensible and work well.\n\nThe 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.\n\nThe 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.\n\nThe paper is very clearly written with a logical, easy-to-follow layout. \n\n# Weaknesses\nMy only issue with this otherwise very nice submission is in their comparison with what the authors call \"neural, likelihood-based approaches\".\nThe 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.\nIn 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).\nWhile of course, it is easier to calculate the model size this way, I think this doesn't provide a representative comparison,\nand 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\nrecent 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.\n\nIf the authors can address my concerns, I will be very happy to increase my score.\n\nAdditionally, some typos that I found:\n- Line 115: Reference 53 appears twice\n- Line 338: \"... store each each in a dataset ...\" - the second \"each\" should read \"edge\".\n\n# After the Rebuttal\n\nAfter 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.\n\n[1] M Havasi, R Peharz, and JM Hernández-Lobato. Minimal random code learning: Getting bits back from compressed model parameters. ICLR 2019.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe they addressed the limitations of their work very thoroughly.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-6"}, "extra_text": {}}, {"review_id": "2dT54mJ28eC", "reviewer": "Reviewer_dgax", "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", "questions": "", "limitations": "", "rating": 7, "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": "*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.\n\n### Detailed Comments\n\nAbstract: This is good, although it'd be even better with some numbers.\n\nIntro: This is also well written, and explains the fundamental idea quite well, breaking it up into the constituent parts.\n\nRelated Work:\n- 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.\n- L94: Surely the premise here is that we are learning a (limited) graph grammar, so in some sense this is related?\n- L124: Typo for 'therefore'\n\nPreliminaries:\n- 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.\n- I thought this section was fairly well written; you may wish to expand the explanation of eq. 1 though.\n\nS4:\n- 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.\n- 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.\n\nS5:\n- 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.\n\nS6:\n- 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?\n- Table 1/2: the results are good, but there's no indication of training time here (for any method), which should not be ignored.\n- 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 :-) )\n\n#### Other Questions:\n- 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?\n- Similarly, what happens if you take a compressor and apply it to a dataset it wasn't trained on? How well do things transfer?\n- How much data do you need to train a reasonable compressor? Would it be possible to plot a graph?\n- Finally, how do you handle node / edge features?\n\nI'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 :-)\n\n#### Overall Thoughts\n\nI 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.\n\n===== Post rebuttal\n\nI'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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)