Partition and Code: learning how to compress graphs
arXiv:2107.01952
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.
arXiv commentPublished at NeurIPS 2021
References in corpus (42)
- Fast unfolding of communities in large networks
- Distilling the Knowledge in a Neural Network
- Maps of random walks on complex networks reveal community structure
- Neural Message Passing for Quantum Chemistry
- Near linear time algorithm to detect community structures in large-scale networks
- Stochastic blockmodels and community structure in networks
- Pixel Recurrent Neural Networks
- Fast Graph Representation Learning with PyTorch Geometric
- Mixed Precision Training
- Junction Tree Variational Autoencoder for Molecular Graph Generation
- A Convergence Theory for Deep Learning via Over-Parameterization
- GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
- MolGAN: An implicit generative model for small molecular graphs
- Learning Deep Generative Models of Graphs
- Bayesian Compression for Deep Learning
- Constrained Graph Variational Autoencoders for Molecule Design
- TUDataset: A collection of benchmark datasets for learning with graphs
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
- Variational Diffusion Models
- Graph Isomorphism in Quasipolynomial Time
- Parsimonious module inference in large networks
- Benchmarking Graph Neural Networks
- GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation
- Nonparametric Bayesian inference of the microcanonical stochastic block model
- NetGAN: Generating Graphs via Random Walks
- Efficient Graph Generation with Graph Recurrent Attention Networks
- Subgraph Matching Kernels for Attributed Graphs
- Entropy of stochastic blockmodel ensembles
- Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding
- Compressing Graphs and Indexes with Recursive Graph Bisection
- End to end learning and optimization on graphs
- Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations
- Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables
- Practical Lossless Compression with Latent Variables using Bits Back Coding
- Discrete Flows: Invertible Generative Models of Discrete Data
- Compression with Flows via Local Bits-Back Coding
- GAP: Generalizable Approximate Graph Partitioning Framework
- Large-scale network motif analysis using compression
- Scalable Deep Generative Modeling for Sparse Graphs
- Scikit-network: Graph Analysis in Python
- Syntactically Informed Text Compression with Recurrent Neural Networks
- Autoregressive Diffusion Models