2020/06/04 by Alankrita Bhatt, Bhatt, Alankrita, Wang, Ziao +2
Computer Science · Physics and Astronomy · #Algorithms and Data Compression #Complex Network Analysis Techniques #Databases (cs.DB) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #Information Theory (cs.IT) #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2006.02643
openalex publication_date 2020/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Motivated by the prevalent data science applications of processing large-scale graph data such as social networks and biological networks, this paper investigates lossless compression of data in the form of a labeled graph. Particularly, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. An information-theoretic universal compression framework is applied, in which one aims to design a single compressor that achieves the asymptotically optimal compression rate, for every SBM distribution, without knowing the parameters of the SBM. Such a graph compressor is proposed in this paper, which universally achieves the optimal compression rate with polynomial time complexity for a wide class of SBMs. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences. However, the adjacency matrix of SBM has complex two-dimensional correlations. The challenge is alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. submatrices. The sequence of submatrices is then compressed by a Krichevsky--Trofimov compressor, whose length analysis is generalized to identically distributed but arbitrarily correlated sequences. In four benchmark graph datasets, the compressed files from competing algorithms take 2.4 to 27 times the space needed by the proposed scheme.