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 elementary structures, 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 three steps are parametric and can be trained with gradient descent. We theoretically compare the compression quality of several graph encodings and prove, under mild conditions, a total ordering of their expected description lengths. Moreover, we show that, under the same conditions, PnC achieves compression gains w.r.t. the baselines that grow either linearly or quadratically with the number of vertices. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressors.
翻译:我们能否用机器学习压缩图形数据? 图表中没有定序对常规压缩算法提出重大挑战,限制其可实现的收益以及发现相关模式的能力。 另一方面,大多数图形压缩法依靠以域为依存的手工制成的表达方式,无法适应不同的底图分布。 这项工作的目的是建立必要的原则, 一个无损图形压缩法应该遵循的离心图压缩法, 以接近微粒储存的下限。 我们不是对图表分布作出僵硬的假设, 而是将压缩算法设计成一种从数据和一般到不可见实例的概率模型。 我们的“ 分解法和代码” 框架需要三个步骤: 首先, 分区算法将图解成基本结构, 然后这些方法被映射成一个小字典的元素, 我们学习概率分布, 最后, 一种无损的图解解法将代表制成比特。 所有三个步骤都是分辨的, 可以用梯度下降来训练。 我们从理论上比较了几个图表的缩度编码质量, 并且证明, 在比较它们预期的描述长度的完全排序。 此外, 我们用直径网络来显示, 我们的直径直径直径的计算, 增长, 在相同的基准中, 增长中, 增长中, 增长的直径直径直径增长中, 的进进进进进进进进进进进进到直到直到直到直到直到直到直到直到直线式的进。