All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD7-S2-T2.3
Paper Title Universal Graph Compression: Stochastic Block Models
Authors Alankrita Bhatt, University of California San Diego, United States; Ziao Wang, University of British Columbia, Canada; Chi Wang, Microsoft Research, Redmond, United States; Lele Wang, University of British Columbia, Canada
Session D7-S2-T2: Compression & Graphs
Chaired Session: Tuesday, 20 July, 22:20 - 22:40
Engagement Session: Tuesday, 20 July, 22:40 - 23:00
Abstract Motivated by the prevalent data science applications of processing large-scale graph data such as social networks, web graphs, and biological networks, as well as the high I/O and communication costs of storing and transmitting such data, this paper investigates universal compression of data appearing in the form of a labeled graph. In particular, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. A universal graph compressor is proposed, which achieves the optimal compression rate for a wide family of SBMs with edge probabilities from $O(1)$ to $\Omega(1/n^{2-\e})$ for any $0<\e <1$. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences with entropy linear in the number of variables. However, the adjacency matrix of SBM has complex two-dimensional correlations and sublinear entropy in the sparse regime. These challenges are alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. blocks. The blocks are then compressed by a Krichevsky-Trofimov compressor, whose length analysis is generalized to arbitrarily correlated processes with identical marginals.