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

Technical Program

Paper Detail

Paper IDD7-S2-T2.2
Paper Title A Universal Lossless Compression Method applicable to Sparse Graphs and heavy-tailed Sparse Graphs
Authors Payam Delgosha, University of Illinois, Urbana-Champaign, United States; Venkat Anantharam, University of California, Berkeley, United States
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 Graphical data arises naturally in several modern applications, including but not limited to internet graphs, social networks, genomics and proteomics. The typically large size of graphical data argues for the importance of designing universal compression methods for such data. In most applications, the graphical data is sparse, meaning that the number of edges in the graph scales more slowly than $n^2$, where $n$ denotes the number of vertices. Although in some applications the number of edges scales linearly with $n$, in others the number of edges is much smaller than $n^2$ but appears to scale superlinearly with $n$. We call the former sparse graphs and the latter heavy-tailed sparse graphs. In this paper we introduce a universal lossless compression method which is simultaneously applicable to both classes. We do this by employing the local weak convergence framework for sparse graphs and the sparse graphon framework for heavy-tailed sparse graphs.