# NeuKron: Constant-Size Lossy Compression of Sparse Reorderable Matrices and Tensors

arXiv: https://arxiv.org/abs/2302.04570 · HTML: https://mlsanity.com/paper/2302.04570/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 9 Feb 2023.

## Builds on (most cited first, 11 of 11)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Canonical Tensor Decomposition for Knowledge Base Completion](https://mlsanity.com/paper/1806.07297/) (2018)
- [FedPara: Low-Rank Hadamard Product for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2108.06098/) (2021)
- [SSumM: Sparse Summarization of Massive Graphs](https://mlsanity.com/paper/2006.01060/) (2020)
- [Compressing Graphs and Indexes with Recursive Graph Bisection](https://mlsanity.com/paper/1602.08820/) (2016)
- [Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions](https://mlsanity.com/paper/1811.04150/) (2018)
- [Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach](https://mlsanity.com/paper/2011.04235/) (2020)
- [ACCAMS: Additive Co-Clustering to Approximate Matrices Succinctly](https://mlsanity.com/paper/1501.00199/) (2014)

## Built on by (most cited first, 1 of 1)

- [TensorCodec: Compact Lossy Compression of Tensors without Strong Data Assumptions](https://mlsanity.com/paper/2309.10310/) (2023)

## Abstract (arXiv)

Many real-world data are naturally represented as a sparse reorderable matrix, whose rows and columns can be arbitrarily ordered (e.g., the adjacency matrix of a bipartite graph). Storing a sparse matrix in conventional ways requires an amount of space linear in the number of non-zeros, and lossy compression of sparse matrices (e.g., Truncated SVD) typically requires an amount of space linear in the number of rows and columns. In this work, we propose NeuKron for compressing a sparse reorderable matrix into a constant-size space. NeuKron generalizes Kronecker products using a recurrent neural network with a constant number of parameters. NeuKron updates the parameters so that a given matrix is approximated by the product and reorders the rows and columns of the matrix to facilitate the approximation. The updates take time linear in the number of non-zeros in the input matrix, and the approximation of each entry can be retrieved in logarithmic time. We also extend NeuKron to compress sparse reorderable tensors (e.g. multi-layer graphs), which generalize matrices. Through experiments on ten real-world datasets, we show that NeuKron is (a) Compact: requiring up to five orders of magnitude less space than its best competitor with similar approximation errors, (b) Accurate: giving up to 10x smaller approximation error than its best competitors with similar size outputs, and (c) Scalable: successfully compressing a matrix with over 230 million non-zero entries.