Many real-world data are naturally represented as a sparse reorderable matrix, whose rows and columns can be reordered without information loss. 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 sublinear in the number of non-zeros but still linear in the number of rows and columns. In this work, we propose \method for compressing a sparse reorderable matrix, regardless of its size, into a fixed amount of space. NeuKron updates the parameters so that a given matrix is approximated by the product, and NeuKron also reorders the rows and columns of the matrix to facilitate the approximation. Given an $n$-by-$m$ matrix with $p$ non-zeros, where $n \leq m$ without loss of generality, the above update steps, which take $O(m+p\cdot \log m)$ time, are repeated alternatively, and from the trained model, the approximate value of each entry is retrieved in $O(\log m)$ time. Through experiments on six real-world datasets, we demonstrate that NeuKron is (a) Compact: requiring five orders of magnitude less space than its best competitor with similar approximation errors, (b) Accurate: giving up to $10.1\times$ smaller approximation errors than its best competitor with similar space requirements, and (c) Scalable: compressing a matrix with about $230$ million non-zeros.
많은 실제 데이터는 재배열 가능한 희소행렬로 표현할 수 있다. 재배열 가능한 행렬은 정보의 손실 없이 행과 열의 순서를 바꿀 수 있는 행렬을 의미한다. 희소 행렬을 저장하는 기존 방법론들은 0이 아닌 원소의 개수에 비례하는 공간을 필요로 한다. 본 연구에서, 우리는 행렬의 크기에 상관 없이 고정된 크기의 공간으로 희소하고 재배열 가능한 알고리즘을 압축하는 NeuKron 를 제시한다. NeuKron 는 상수 개의 파라미터를 가진 recurrent neural network를 이용하여 크로네커 곱을 일반화한다. NeuKron 는 주어진 행렬이 곱에 의해 근사되도록 파라미터를 업데이트 하고, 또 근사를 더 잘하기 위해 행렬의 행과 열 순서를 바꾸어 준다. $n \times m$ 크기의 $p$개의 0이 아닌 원소를 가진 행렬이 주어졌을 때 (일반성을 잃지 않고 $n \leq m$으로 가정), 위의 업데이트 과정은 $O(m+p\cdot \log m)$ 정도의 시간이 걸리고 계속 반복된다. 학습된 모델에서 각 원소의 근사값을 계산하는 데 걸리는 시간은 $O(\log(m))$이다. 6개의 실제 데이터를 사용하여 우리는 NeuKron 가 아래 강점이 있음을 보였다. (a) 조밀함: 경쟁 알고리즘과 비슷한 근사 오류를 보일 때 $10^5$배 더 적은 공간을 필요로 한다, (b) 정확함: 비슷한 공간을 사용할 때 가장 좋은 경쟁 상대에 비해 $10.1$배 더 작은 근사 오류를 보인다, (c) 확장가능함: 2.3억개의 0이 아닌 원소를 지닌 행렬도 압축했다.
