Lossless Compression of Structured Convolutional Models via Lifting
Authors: Gustav Sourek
Filip Zelezny
Ondrej Kuzelka
Venue: ICLR 2021 Poster (2021)
Keywords: weight sharing
graph neural networks
lifted inference
relational learning
dynamic computation graphs
convolutional models

Abstract: Lifting is an efficient technique to scale up graphical models generalized to relational domains by exploiting the underlying symmetries. Concurrently, neural models are continuously expanding from grid-like tensor data into structured representations, such as various attributed graphs and relational databases. To address the irregular structure of the data, the models typically extrapolate on the idea of convolution, effectively introducing parameter sharing in their, dynamically unfolded, computation graphs. The computation graphs themselves then reflect the symmetries of the underlying data, similarly to the lifted graphical models. Inspired by lifting, we introduce a simple and efficient technique to detect the symmetries and compress the neural models without loss of any information. We demonstrate through experiments that such compression can lead to significant speedups of structured convolutional models, such as various Graph Neural Networks, across various tasks, such as molecule classification and knowledge-base completion.

Published as a conference paper at ICLR 2021
LOSSLESS COMPRESSION OF STRUCTURED CONVOLUTIONAL MODELS VIA LIFTING
Gustav Sourek, Filip Zelezny, Ondrej Kuzelka Department of Computer Science
Czech Technical University in Prague
(souregus, ze zelezny, kuzelon2 ) cvut.cz
ABSTRACT
Lifting is an efficient technique to scale up graphical models generalized to re- lational domains by exploiting the underlying symmetries. Concurrently, neural models are continuously expanding from grid-like tensor data into structured repre- sentations, such as various attributed graphs and relational databases. To address the irregular structure of the data, the models typically extrapolate on the idea of convolution, effectively introducing parameter sharing in their, dynamically unfolded, computation graphs. The computation graphs themselves then reflect the symmetries of the underlying data, similarly to the lifted graphical models. Inspired by lifting, introduce a simple and efficient technique detect the symmetries and compress the neural models without loss of any information. We demonstrate through experiments that such compression can lead to significant speedups of structured convolutional models, such as various Graph Neural Networks, across various tasks, such as molecule classification and knowledge-band completion.
INTRODUCTION
Lifted, often referred as templated, models use highly expressive representation languages, typically based in weighted predicate logic, to capture symmetries in relational learning problems (Koller et al. 2007). This includes learning from data such as chemical, biological, social, or traffic networks, and various knowledge graphs, relational datahases and ontologies. The idea has been studied extensively in probabilistic settings under the notion of lifted graphical models (Kimmig al.) 2015), with instances such as Markov Logic Networks (MLNs) (Richardson & Domingos) 2006) or Bayesian Logic Programs (BLPs) Kersting & De Raedt 2001).
In wider view, convolutions can be seen as instances of the templating idea in neural models, where the same parameterized pattern is being carried around to exploit the underlying symmetries, i.e. some forms of shared correlations in the data. In this analogy. the popular Convolutional Neural Networks (CNN) (Krizhevsky et al. 2012) themselves can be seen as a simple form of a templated model, where the template corresponds to the convolutional filters, unfolded over regular spatial grids of pixels. But the symmetries are further even more noticeable in structured, relational domains with discrete element types. With convolutional templates for regular trees, the analogy covers Recursive Neural Networks (Socher et al.) 2013), popular in natural language processing. Extending to arbitrary graphs, the same notion covers works such Graph Convolutional Networks (Kipf & Welling 2016) and their variants (Wu et al. 2019). as well as various Knowledge-BBad Base Embedding methods WWang al. 2017). Extending even further to relational structures, there are works integrating parameterized
relational logic templates with neural networks (Sourek et al. 2018 Rocktäschel & Riedel 2017
Marra Kuželka, 2019 Manhaeve et al.) 2018).
The common underlying principle of templated models is a joint parameterization of the symmetries, allowing for better generalization. However, standard lifted models, such as MLNs, provide another key advantage that, under certain conditions, the model computations can be efficiently carried out without complete template unfolding, often leading to even exponential speedups (Kimmig et al. 2015). This is known as "lifted inference" (Kersting 2012) and is utilized heavily in lifted graphical models as well as database query engines (Suciu et al. 201T). However, to our best knowledge, this idea has been so far unexploited in the neural (convolutional) models. The main contribution of

---

Published as a conference paper at ICLR 2021
this paper is thus a "lifting" technique to compress symmetries in convolutional models applied to structured data, which we refer to generically as "structured convolutional models".
1.1 RELATED WORK
The idea for the compression is inspired by lifted inference (Kersting 2012) used in templated graphical models. The core principle is that all equivalent sub-computations can be effectively carried out in single instance and broadcasted into successive operations together with their respective multiplicities, potentially leading to significant speedups. While the corresponding "liftable" template formulae (or database queries) generating the isomorphisms typically assumed to be given (Kimmig et al., 2015). we explore the symmetries from the unfolded ground structures, similarly to the approximate methods based on graph bisimulation (Sen al., 2012). All the lifting techniques are then based in some form of first-order variable elimination (summation), and are inherently designed explore structural symmetries in graphical models. In contrast, we aim to additionally explore functional symmetries, motivated by the fact that even structurally different neural computation graphs may effectively perform identical function.
The learning in neural networks is also principally different from the model counting- based computa- tions in lifted graphical models in that requires many consecutive evaluations of the models as part of the encompassing iterative training routine. Consequently, even though we assume to unfold a com- plete computation graph before is compressed with the proposed technique, the resulting speedup due to the subsequent training is still substantial. From the deep learning perspective, there have been various model compression techniques proposed to speedup the training, such as pruning, decreasing precision, and low-rank factorization (Cheng et al., 2017). However, to our best knowledge, the existing techniques are lossy in nature, with a recent exception of compressing ReLU networks based on identifying neurons with linear behavior (Serra et al. 2020). None of these works exploit the model computation symmetries. The most relevant line of work here are Lifted Relational Neural Networks (LRNNs) (Sourek al. (2018) which however, despite the name, provide only templating capabilities without lifted inference, i.e. with complete, uncompressed ground computation graphs.
BACKGROUND
The compression technique described in this paper is applicable to a number structured con- volutional models, ranging from simple recursive (Socher et al., 2013) to fully relational neural models (Sourek et al., 2018). The common characteristic of the targeted learners is the utilization of convolution (templating), where the same parameterized pattern is carried over different sub- parts of the data (representation) with the same local structure, effectively introducing repetitive sub-computations in the resulting computation graphs, which we exploit in this work.
2.1 GRAPH NEURAL NETWORKS
Graph neural networks (GNNs) are currently the most prominent representatives of structured convolutional models, which is why we choose them for brevity of demonstration of the proposed compression technique. GNNs can be seen as an extension the common CNN principles to completely irregular graph structures. Given particularly structured input sample graph Sy. they dynamically unfold multi-layered computation graph Gj. where the structure of each layer follows the structure of the whole input graph Sj. For computation of the next layer i values, each node from the input graph Sj calculates its own value h(2) by aggregating A ("pooling")) the values of the adjacent nodes edge(u. u, v). transformed by some parametric function Ow, ("convolution"). which is being reused with the same parameterization Wi within each layer i as:
h(w) = ((C())) (k()) edge(u, v)})
The 7,000 (v) can be further combined through another Cw with the central node's representation from the previous layer to obtain the final updated value (v) for layer as:
h(w) = c(. (((o)(t-1,,h()))
(2)
2

---

Published as a conference paper at ICLR 2021
(ar)
2
f(x)
Wh
105
far an x- cooss))))
I
[(n, 2) x ceosyy)
3
f-1
((x)
Figure 1: Depiction of the computation graph (left) compression (right) from Example
This general principle covers a wide variety of GNN models, such the popular GCNs (Kipf & Welling 2016), graph-SAce SAGE (Hamilton et al. (017). GIN (Xu et al.) 20188), and others (Xu al. 2018b Gilmer et al. 2017), which then reduces to the respective choices of particular aggregations A and transformations Ow. An example computation graph of a generic GNN unfolded over an example molecule of methane is shown in Fig.
2.2 COMPUTATION GRAPIIS
For the sake of this paper, let us now define the common notion of computation graph more formally. A computation graph is tuple g (N, F,,,, where N (1, 2. ... n.) is list of nodes and C AA22 x N is a list of directed labeled edges. Each labeled edge is triple of integers (mi, n22 where nı and rı2 nodes of the computation graph and / is the label. The labels weights to the edges in the computation graph. Note this allows to define the weight sharing scheme as part of the graph (ef Example [ below). Finally, = f2..f......
used assign
is the list of activation functions, one for each node from N. As usual, the graph is assumed to be acyelic. Children of node N are naturally defined as all those nodes M such that (M, N, L) E E, and analogically for parents. Note that since & is list, edges contained in it are ordered, and the same edge may appear multiple times (which will be useful later). Children of each node are also ordered given two children C' and C" of node N. C' precedes C' iff (C, N, L) precedes (C" ,,, N L') in the list of edges E. We denote the lists of children and parents of a given node N by Children(N)) and Parents N). respectively. Computation graphs with no children) to the roots of the graph (nodes with no parents). Given a list of weights W, we can now define the value of node N N recursively as:
then evaluated bottom up from the leaves of the graph (nodes
value( N; W) = JN (WL, value( M1; W), WL,,, vvauu(Maa W)).
where (M1,..., Mn) Children(N) is the (ordered) list of children of the node N, and Iı,-... T.m are the labels of the respective edges (N,,N, LI). (Mm, N. Lm)) E &, and Wi, is the Lh component of the list W. Note that with the structured convolutional models, such as GNNs, we assume dynamic computation graphs where each learning sample Sy generates separate 9j- Consequently, we can associate the leaf nodes in each G, with constant functions" outputting the corresponding node (feature) values from the corresponding structured input sample Sy.
PROBLEM DEFINITION
The problem of detecting the symmetries in computation graphs can then be formalized follows. Definition 1 (Problem Definition). Let G = (N,EFF be computation graph. We say that two nodes N1, N2 are equivalent if. for any W, holds that value(N1 W) value (N2; W). The problem of detecting symmetries in computation graphs asks to partition the nodes of the computation graph into equivalence classes of mutually equivalent nodes.
Example 1. Consider the computation graph G (NF,FF), depicted in Fig. ! where
= - 1,,1,,,3,4 E ((0, 2, 1). (1. 3, 1), (2, 2,4, (3,4,2), == =1 f2x) = fa(x) x. fa(x. y) cos(y)).
in contrast static computation graphs where these functions identities requiring the features at input.
3

---

Published as a conference paper at ICLR 2021
Ler W = (W1, W2) be the weight list. The computation graph then computes the function (WIW2)- cos( (w) W2). It is not difficult to verify that the nodes {0, 1}, and {2, 3] are functionally equivalent. This also means, as we discuss in more detail in the next section, that can "merge" them without changing the function that the graph computes. The resulting reduced graph then has the form
(1,3, (1,3,3,44) 4), 8 ( 1), (3, 4, 2), (3, 2)}, N
F= F = =., 1,, (1, = x cos(y)).
In the example above, the nodes {0, }} and {2, are in fact also isomorphic in the sense that there exists an automorphism (preserving weights and activation functions) of the computation graph that swaps the nodes. Note that our definition is less strict: all we want the nodes to satisfy is functional equivalence, meaning that they should evaluate to the same values for any initialization of W.
We will also use the notion of gruccural-equivalenee of nodes in computational graphs. Two nodes are structurally equivalent they have the same outputs for any assignment of weights W and for any replacement of any of the activation functions in the graph That is if two nodes are structurally equivalent then they are also functionally equivalent but not vice versa. Importantly, the two nodes do not need to be automorphic in the graph-theoretical sense while being structurally equivalent, which also makes detecting structural equivalence easier from the computational point of view. In particular, we describe a simple polynomial-timg algorithm in Section 4.2
4 TWo ALGORITTMM FOR COMPRESSING COMPUTATION GRAPHS
In this section we describe two algorithms for compression of computation graphs: non-exact algorithm for compression based on functional equivalency (ef. Definition | and an exact algorithm for compression based detection of grructualll-equivvla the exact algorithm will guarantee that the original and the compressed computation graphs represent the same function, that will not be the case for the non-exact algorithm. Below first describe the non-exact algorithm and then use it as a basis for the exact algorithm.
nodes in the computation graph. While
4.1 A NON-EXACT COMPRESSION ALGORITHM
The main idea behind the non-exact algorithm is almost embarrassingly simple. The algorithm first evaluates the computation graph with randomly sampled parameter lists Wi.... W.. i.e. with n random initializations of the (shared) weights, and records the values of all the nodes of the computation graph (i.e. values per node). It then traverses the computation graph from the output nodes in a breadth-firs manner, and whenever it processes a node N, for which there exists a node N' that has not been processed yet and all n of its recorded values are the same those of the currently processed node N, the algorithm replaces N by N' in the computation graph. In principle, using larger will decrease the probability of merging nodes that not functionally equivalent as long as there is a non-zero chance that any two non-equivalent nodes will have different values (this is the same as the "amplification trick" normally used in the design of randomized algorithms).
It is easy to see that any functionally equivalent nodes will be mapped by the above described algorithm to the same node in the compressed computation graph. However, can happen that the algorithm will also merge nodes that are not functionally equivalent but just happened (by chance) to output the same values on all the random parameter initializations that the algorithm used. We acknowledge that this can happen in practice, nevertheless it was not commonly encountered in our experiments (Sec. 55), unless explicitly emulated. To do that, we decreased the number of significant digits used in each equivalence check between value( N; W;) and value( (N': NN: W.). This allows to compress the graphs even further, at the cost of sacrificing fidelity w.r.t. the original model.
There also cases when we can give (probabilistic) guarantees on the correctness of this algorithm. One such case is when the activation functions in the computation graph are all polynomial. In this case, use Witiiloo-LpttonSSShaaaaa
Lemma (DeMillo & Lipton| 1977h to bound the
"Here, we add that in this definition, obviously, when we replace function by function f', have replace all occurrences of ff in the graph also by f".
Here, when we say "automorphic nodes", we mean that there exists an automorphism of the graph swapping the two nodes.
4

---

Published as a conference paper at ICLR 2021
Wi
W4
Tates)
Lucoa)
Cali)
Ws
Figure 2: A multi-layer GNN model with a global readout unfolded over an exam- ple molecule of methane. Colors are used to distinguish the weight sharing, as well as different node types categorized w.r.t. the associated activation functions, denoted as input (I), convolution (C), and aggregation (A) nodes, respectively.
lates
C
A#
(p(())
4x Wy
Inn
C
4x
Figure 3: compressed version of the GNN from Fig. with the compressed parts dotted.
probability of merging two nodes that are not functionally equivalent. However, since the activation functions in the computation graphs that we are interested in are usually not polynomial, we omit the details here. In particular, obtaining similar probabilistic guarantees with activation functions such as ReLU does not seem doable
4.2
AN EXACT COMPRESSION ALGORITHM
The exact algorithm for compressing computation graphs reuses the evaluation with random parameter initializations while recording the respective values for all the nodes. However, the next steps different. First, instead of traversing the computation graph from the output nodes towards the leaves, it traverses the graph bottom-up. starting from the leaves. Second, rather than merging the nodes with the same recorded value lists right away, the exact algorithm merely considers these as candidates for merging. For that keeps data structure (based on hash table) that indexes the nodes of the computation graph by the lists of the respective values recorded for the random parameter initializations. When, while traversing the graph, processes a node N, it checks if there any node N' that had the same values over all the random parameter initializations and has already so it checks N and N' are structurally equivalent (which we explain in turn) and if they are it replaces N by N'. To test the structural equivalence of two nodes, the algorithm checks the following conditions:
been processed.
The activation functions N and N' are the same.
2. The lists of children of both and N' are the same (not just structurally equivalent but identical, i.e. Children N) = Children(NV) N")). and if C' is the i-th child of N and C' is the i-th child of N', with (C, N, L1) and (C', N, L-2) being the respective edges connecting them to N. then the labels L1 and L2 must be equal, too.
In particular, the proof of DeMillo-L www.ipo-SScwwatt--7755 polynomial is for only finite number of points, which not the case for computation graphs with ReLUs.
I Lemma relies on the fact that any single variable
5

---

Published as a conference paper at ICLR 2021
One can show why the above procedure works by induction. We sketch the main idea here. The base case is trivial. To show the inductive step we can reason as follows. When we are processing the node N, by the assumption, the node N' has already been processed. Thus, know that the children of both N and N' must have already been processed as well. By the induction hypothesis, if any of the children were structurally equivalent, they must have been merged by the algorithm, and it is enough to check identity of the child nodes. This reasoning then allows one to easily finish proof of correctness of this algorithm.
There is one additional optimization that we can do for symmetric activation functions. Here by "symmetric" we mean symmetric with respect to permutation of the arguments. An example of such symmetric activation function is any function of the form f 2x) = h (E Fz) such functions are often used in neural networks. In this case we replace the condition 2 above by:
2'. There is a permutation such that π (Children( = Children( (N")) and if C is the i-th child of N and C' is the (ii)-th child of N', with (C, N, L1) and (C", N, L2) being the respective edges connecting them to N, then the labels L1 and L2 must be equal.
It is not difficult to implement the above check efficiently (we omit the details for brevity). Note also that the overall asymptotic complexity of compressing a graph G with either of the algorithms is simply linear in the size of the graph. Specifically, it is the same as the evaluations of g.
Finally, to illustrate the effect of the lossless compression, we show the GNN model (Sec. 2.1
unfolded over a sample molecule of methane from Fig 2 compressed in Fig.
EXPERIMENTS
To test the proposed compression in practice, we selected some common structured convolutional mod- els, and evaluated them on a number of real datasets from the domains of (i) molecule classification and (ii) knowledge-bard completion. The questions be answered by the experiments are:
1. How numerically efficient the non-exact algorithm in achieving lossless compression?
2. What improvements does the compression provide in terms of graph size and speedup?
3. Is learning accuracy truly unaffected by the, presumably lossless, compression in practice?
Models We chose mostly GNN-based models as their dynamic computation graphs encompass all the elements of structured convolutional models (convolution, pooling. and recursive layer stacking). Particularly, we choose well-known instances of GCNs and graph-SAGE (Sec. I. each with layers. Additionally, we include Graph Isomorphism Networks (GIN) (Xu et al. 2018a), which follow the same computation scheme with 5 layers, but their particular operations (Ow, identity,
sum, Cw, MLP) are theoretically substantiated in the expressiveness of the Weisfeiler-Lehmal test (Weisfeiler) 2006). This is interesting in that it should effectively distinguish non-isomorphic substructures the data by generating consistently distinct computations, and should thus be somewhat more resistant to our proposed compression. Finally, include relational template ("graphlets")) introduced in (Sourek et al. 2018), which generalizes GNNs to aggregate small 3-graphlets instead of just neighbors.
Datasets For structure property prediction, we used 78 organic molecule classification datasets reported in previous works (Ralaivola et al. 2005 Helma al. 2001; Lodhi Muggleton, 2005). Nevertheless, we show only the (alphabetically) first 3 for clarity, the target metrics were extremely similar over the whole set. We note we also extended GCNs with edge embeddings to account for the various bond types, further decreasing the symmetries. For knowledge base completion (KBC), we selected commonly known datasets of Kinships, Nations, and UMLS (Kok & Domingos 2007) composed of different pejject-rredicte--ttee the items and relations, similarly to R-GCNs (Schlichtkrull et al., 2018), and for prediction of each triplet, fed the three embeddings into an MLP, such as in (Dong al. 2014), denoted as "KBE".
triplets. We utilized GCNs learn embeddings of all
The size of the individual input graphs is generally smallest in the molecular data with app. 25 atoms and 50 bonds per single molecule, where there app. 3000 molecules in each of the datasets

---

Published as a conference paper at ICLR 2021
dinession:
107
snidiittioned
mildicaions
00
Mosrrittce urrurs Oyilne chahod)
0
rato (WIIEONO
10*
Siat acceracy
accrnayy
oxmppesseed sizz
0.-
oomppessed
hascline
0
bascline time
haveine trin aoc
10
02
107
2
Right
digts
watel puppleir- datiarnt undeentee (MIAA)
awslel graphitt Amman sudinals (MGAA)
Figure 4: Compression of paramer-prameterizeed graphlets model on molecular dataset. We display progression of the selected metrics w.r.t. increasing number of significant digits (inits=1) used in the value comparisons (left), and number of non-equii equivalet subgraph value clashes detected by the exact algorithm w.r.t. the digits, weight re- re-initializations, and increased weight dimension (right).
Table I: Training times per epocha across different models and frameworks over 3000 molecules. Additionally, the startup graphs creation time of LRNNs (including the compression) is reported.
Model
Lifting (8)
LRNNs (s)
PyG (s)
DGL (s)
LRNN startup (s)
GCN
0.25 + 0.01
0.75 0.01
3.24 0.02
23.25 + 1.94
3.3
g-SAGE
0.34 + 0.01
0.89 0.01
3.83 + 0.04
24.23 : 3.80
35.4 1.8
GIN
1.41 0.10
2.84 0.09
11.19 0.06
52,04 + 0.41
75.3
on average. The input graphs are then naturally largest for the knowledge bases with app. 20,000 triples over hundreds of objects and relations. The sizes of the corresponding computation graphs themselves are then in the orders of 102-10a nodes, respectively.
Experimental Protocol We approached all the learning scenarios under simple unified setting with standard hyperparameters, none of which set to help the compression (sometimes the contrary). We used the (re-implemented) LRNN framework to encode all the models, and also compared with popular GNN frameworks of PyTorch Geometric (PyG) (Fey Lenssen 2019) and Deep Graph Library (DGL) (Wang et al.) 2019). If not dictated by the particular model, we set the activation functions simply as Cw Ite w and A ang. We then trained against MSE using 1000 steps of ADAM, and evaluated with a 5-fold crossvalidation.
5.1 RESULTS
Firstly, we tested numerical efficiency of the non-exact algorithm itself (Sec. 4. for which we used scalar weight representation the models to detect symmetries on the level of individual "neurons"" (rather than "layers").. We used the (most expressive) graphlets model, where we checked the functional symmetries to overlap with the structural symmetries. The results in Fig. then show that the non-exact algorithm is already able to perfectly distinguish all structural symmetries with but a single weight initialization within less than 12 significant digits. While more initializations indeed improved the efficiency rapidly, in the end they proved unnecessary (but could be used in cases where the available precision would be insufficient). Moreover this test was performed with the actual low-range logistic activations. The displayed (10x) training time improvement (Fig left) in
7

---

Published as a conference paper at ICLR 2021
0.8-
0.8
boneline time
0.6-
0.6
0.5-
beacline sirs
couppeoezd
compressed size accuncy
Icdil sunsursuy
0.2-
0.2-
0.0
0.0
0.0
dights
digits
grophlees
donucct motecules (MZN)
suadet mullecates (MOM)
mmddet dastnnt Kinships
Figure 5: Compression of rensor-parameterizee models of graphlets (left), GCNs (middle) and KBEs (right) the molecular (left, middle) and Kinships (right) datasets, with progression of selected metrics against the increasing number of significant digits used for equivalence checking.
0.8
0.84
3.54
beseline time
buseline
0.6-
0.5
3.5-
Irain sus (coxspecosaa)
(boadine')
(ooepeesedd
0.4-
0.4
0.4-
Iest acc (beseline)
compreo
compeessed
0.0
785,0
AJ95
780,0
AJ95
A5-0
kishipo
modccular datieets prophlees mudel
medeccuar daliscts GCN
KBBE mosia
Figure 6: Comparison of 3 different baseline models of graphlets (left), GCNs (middle), and KBEs (right) with their compressed versions over molecule classification (left, middle) and KBC (right).
the scalar models was then directly reflecting the network size reduction, and could be pushed further by decreasing the numeric precision at the expected cost of degrading the learning performance.
Secondly, we performed similar experiments with standard tensor parameterization. where the equivalences were effectively detected on the level of whole neural "layers", since the vector output values (of dim=3) were compared for equality instead. This further improved the precision of the non-exact algorithm (Fig. - right), where merely the first 4 digits were sufficient to achieve lossless compression all the models and datasets (Figure However, the training (inference) time was no longer directly reflecting the network size reduction, which we account to optimizations used in the vectorized computations. Nevertheless the speedup (app. 3x) was still substantial.
We further compared with established GNN frameworks of PyG (Fyy & Lenssen 2019) and DGL (Wang et al.] 2019). We made sure to align the exact computations of GCN, graph- and GIN, while all the frameworks performed equally w.r.t. the accuracies. For more fair comparison, we further increased all (tensor) dimensions to a more common dim=10. The compression effects, well as performance edge of the implemented LRNN framework itself, displayed in Tab.
8

---

Published as a conference paper at ICLR 2021
for sample molecular dataset (MDA). Note that the compression truly least effective for the aforementioned GIN model, nevertheless still provided app. 2x speedup.
Finally, the results in Fig. conffimm that the proposed lossless compression via lifting, with either the exact algorithm or the non-exace algorithm with a high- numeric precision used, indeed does not degrade the learning performance in terms of training and testing accuracy (both were close within margin of variance over the crossvalidation folds).
Note that the used templated models quite simple and do not generate any symmetries their own (which they would, e.g., with recursion), but rather merely reflect the symmetries in the data themselves. Consequently, the speedup Nations, represented via 2 distinct relation types, and higher for the Kinships dataset, representing more densely interconnected social network. The improvement was then generally biggest for the highly symmetric molecular graphs where, interestingly, the compression often reduced the neural computation graphs to a size even smaller than that of the actual input molecules. Note we only compressed symmetries within individual computation graphs (samples), and the results thus cannot be biased by the potential existence isomorphic samples (Ivanov et al. (2019), however, potentially much higher compression rates could be also achieved with (dynamic) batching.
overall lowest for the knowledge graph of
CONCLUSION
We introduced a simple, efficient, lossless compression technique for structured convolutional models inspired by lifted inference. The technique is very hight-weigh and can be easily adopted by any neural learner, but is most effective for structured convolutional models utilizing weight sharing schemes target relational data, such as various graph neural networks. We have demonstrated with existing models and datasets that a significant inference and training time reduction can be achieved without affecting the learning results, and possibly extended beyond for additional speedup.
ACKNOWLEDGMENTS
This work was supported by the Czech Science Foundation project GJ20-19104Y. GS and FZ. are also supported by the Czech Science Foundation project 20-29260S.
REFERENCES
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks. arXiv preprint arXiv:1710.09282, 2017.
Richard A DeMillo and Richard J Lipton. A probabilistic remark algebraic program testing. Technical report, Georgia Inst. of Technology, Atlanta School of Information and Computer science, 1977.
Xin Dong, Evgeniy Gabrilovich, Geremy Heitz, Wilko Horn, Ni Lao, Kevin Murphy, Thomas Strohmann, Shaohua Sun, and Wei Zhang. Knowledge vault: A web-scale approach to proba- bilistic knowledge fusion. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 601-610, 2014.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.0244 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning- Volume 70, pp. 1272. JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001. Bioinformatics, 1771):107-108, 2001.

---

Published as a conference paper at ICLR 2021
Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. arXiv preprint 11XX::19100120900 2019.
Kristian Kersting. Lifted probabilistic inference. In ECA,, pp. 33-38, 2012.
Kristian Kersting and Lue De Raedt. Towards combining inductive logic programming with bayesian networks. In Inductive Logic Programming. I Ith International Conference, ILP 2001, Strasbourg, France, September 9-11, 2001, Proceedings, pp- 118-131, 2001.
Kimmig, L Mihalkova, and L Getoor. Lifted graphical models: a survey. Machine Learning, 99(1): 1-45, 2015.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprini arXiv: 1609:1600.0000 02900, 2016.
Stanley Kok and Pedro Domingos. Statistical predicate invention. In Proceedings of the 24th International Conference on Machine Learning, pp. 433-440, 2007.
Daphne Koller, Nir Friedman, Saso Džeroski, Charles Sutton, Andrew McCallum, Avi Pfeffer, Picter Abbeel, Ming-Fai Wong, David Heckerman, Chris Meek, et al. Introduction to statistical relational learning. MIT press, 2007.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1 1105 2012.
Huma Lodhi and Stephen Muggleton. Is mutagenesis still challenging. ILP-Late-Breaking Papers, 35, 2005.
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. In Advances in Neural Information Processing Systems, pp. 3749-3759, 2018.
Giuseppe Marra and Ondřej Kuželka. 1905 13462, 2019.
Neural markov logic networks.
arXiv preprint
Liva Ralaivola, Sanjay J. Swamidass, Hiroto Saigo, and Pierre Baldi. Graph kernels for chemical informatics. Neural Netw., 1801)1009,-1110, 2005.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 2006.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Advances in Neural Information Processing Systems, 2017.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Prithviraj Sen, Amol Deshpande, and Lise Getoor. Bisimulation- approximate lifted inference. 2616, 2012.
arXiv preprint
Thiago Serra, Abhinav Kumar, and Srikumar Ramalingam. Lossless compression of deep neural networks. arXiv preprint arXiv:2001.000 2020.
Richard Socher, Alex Perelygin, Jean Y Wu, Jason Chuang, Christopher D) Manning, Andrew Y Ng, Christopher Potts, al. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the conference empirical methods in natural language processing (EMNLP), volume 1631, pp. 1642. Citeseer, 2013.
Gustav Sourek, Vojtech Aschenbrenner, Filip Zelezny, Steven Schockaert, and Ondrej Kuzelka. Lifted relational neural networks: Efficient learning of latent relational structures. Journal of Artificial Intelligence Research, 62:69-100, 2018.
Dan Suciu, Dan Olteanu, Christopher Ré, and Christoph Koch. Probabilistic databases. Synthesis lectures data management, 3(2): 2011.
10

---

Published as a conference paper at ICLR 2021
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv preprint 0rXhv:1909.013.11 2019.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. JEEE Transactions on Knowledge and Data Engineering, 29(12): 2017.
Boris Weisfeiler. On construction and identification of graphs, volume 558. Springer, 2006.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. A comprehensive survey graph neural networks. arXiv preprint arxiv:/901.00596, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXi:: 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint arXiv: 03536, 2018b.


Reviews:
[{"review_id": "y9p8c6MVc1E", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors of this paper propose an compression technique for GNNs that was inspired by lifted inference. The compression consists of removing asymmetries by merging nodes. They define two algorithms for compression: a non-exact algorithm that merges two nodes that are \"functional\" equivalent and an exact algorithm that merges two nodes that are structurally equivalent.\n\nThe approach seem quite novel, pretty interesting and it could interest a wide audience that works on graph models. However, I think the presentation could be improved. In particular, it is not clear the evalutation settings that they are using. For knowledge completion how do they compute accuracy? Do they use golden triples?\n\nIn conclusion I think section 5 should be improved and writte more clearly but overall I think it is a good paper and should be considered for acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YPPs7sCftYl", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\n \nThe paper provides an interesting work in the scale/speed up of structured convolutional models. In particular, it proposes an idea using a technique named lifting which is used in scaling up of graphical models to detect the symmetries and compress the neural model such as Graph Neural Network. Authors show that this compression can lead to speedups of the models in many tasks.\n\n##########################################################################\n\nPros:\n \n1. The paper takes one of the most important issue of structured convolutional models: scale/speed up. I think this is an area with real world implication where we need more works.\n\n \n2. I think this method can be very useful for networks using lots of identical nodes like molecular network. It can leverage from the repetition in nodes and compress the network into some smaller network and save time and memory.\n \n3. Overall the paper is well written. I liked the illustrations for explaining the methods. Result section is also well structured. It clearly shows the effectiveness of the algorithm over other methods.\n \n##########################################################################\n\nCons: \n\n \n1. Although I think this work is good for small datasets like molecular networks, i am skeptic about its transferability in large scale graphs. The reason behind that is I don't assume there would be a lot of structurally similar nodes in case of a large scale real life graph. Authors did not provide any information on the size of the graphs used for the experiments. \n \n2. Authors proposed two different algorithm, exact and non-exact. There are no comparisons between these two methods are shown in the result. Proper analysis on time and performance of the algorithms are also absent. The motivation behind using exact or non-exact is not clear.\n\n3. On Table 1, the time of the different experiments are given. There are no analysis on time vs performance metric in this table. Does all the baseline show similar performance as the baseline model? The analysis is not present.\n\n4. It would also be interesting to see an analysis on the effect of the algorithms on different graph types based on their characteristics (degree distribution, density, veracity etc). \n \n##########################################################################\n\nQuestions during rebuttal period: \n\n \nPlease address and clarify the cons above \n\n \n#########################################################################\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "VMA9sqBXsAE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an approach to make learning deep neural networks more efficient using ideas from lifted inference for relational probabilistic models. Specifically, symmetries in the computation graph are identified and then the neural network is compressed into an equivalent model.\n\nThe idea of using symmetries for improving scalability has been successfully used in statistical relational models. Therefore, it seems to be a nice direction for improving scalability in neural networks such as GCNs. Thus, large computation graphs can be reduced to smaller graphs for effective computation.\n\nThe main weakness with the paper is that the compression algorithm was not very clear to me. Particularly, the problem of identifying isomorphisms is a hard problem and several lifted inference techniques have typically used approximate methods to identify symmetries in graphical models [e.g. Niepert UAI 2012, Bui et. al. UAI 2013, Holtzen et al. UAI 2019, etc.]. I was not sure why or how the identification of exact symmetries is not hard in this case. Is the type of computation graph restricted to some form? If so, a more detailed description of the properties of this graph is useful. Since the main focus of the paper is on “exact” symmetries, I think in general, a more detailed analysis of the proposed approach will help in general.\n\nRegarding the experiments, they show that the proposed techniques can help speed up different types of deep models based on GNNs. One aspect that was not very clear was how large were the computation graphs? Also, when the compression is exact would the accuracies still vary between the compressed and uncompressed model?\n\nIn general, I like the idea of using symmetries to compress graph-based neural networks. I am not too clear on the details of the proposed approach, particularly their applicability for general graph structures.\n\nFrom the discussions, the authors make it clear that \"compressing\" the computation graph is possible without the need for expensive operations (as is the case in typical \"lifted\" inference literature). The approach does seem to be simple to implement , maybe a bit more detailed analysis and clarity as suggested by others as well could strengthen the paper further.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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