Graph Data Compression: Practical Methods and Information Theoretic Limits
The basic idea of developing methods to efficiently encode data for storage and communication dates back to the days of the early Roman Republic, when the slave Tiro would use shorthand to capture speeches and debates for his master Cicero. The modern view of the problem really began with Morse’s famous code for telegraphy in the early 1800s, and the work of Shannon and Fano in the 1950s laid the foundations for the source coding theory we use to study data compression today. Conventionally, data sources are modeled as sequences of symbols that exhibit independence or, at most, weak dependence between distant symbols, which has given rise to many of the practical compression methods that are currently in use. Recently, however, the application of graph structures to capture complex dependencies in data has meant those standard models are not representative, rendering conventional compression methods suboptimal. This has led computer scientists and engineers to develop new methods of compressing graphs. In this talk, I will give an introduction to the developing field of graph compression. I will discuss the basic problems encountered in practice and some of the solutions that have been proposed. I will also present a few results detailing information-theoretic limits on compressing graphs.
Dr. Justin Coon
Professor, University of Oxford on March 21, 2025 at 10:15 AM in EB2 1231
Justin P. Coon received a BSc degree (with distinction) in electrical engineering from the Calhoun Honours College, Clemson University, USA and a PhD in communications from the University of Bristol, UK in 2000 and 2005, respectively. He held various research positions at Toshiba Research Europe Ltd. (TREL) from 2004 until 2013, including the position of Research Manager from 2010 to 2013, during which time he led all research on physical layer communications and network modelling at TREL. Dr. Coon was a Visiting Fellow with the School of Mathematics at the University of Bristol, UK from 2010 until 2012, and he held a position as Reader in the Department of Electrical and Electronic Engineering at the same university from 2012 to 2013. He joined the University of Oxford in 2013 where he is currently a Professor of Engineering Science and the Emmott Fellow in Engineering at Oriel College. Dr. Coon is the recipient of Toshiba’s Distinguished Research Award for his work on 4G systems and has received three “best paper” awards. He has published widely in IEEE and APS journals and conferences and is a named inventor on several dozen patents. He has served as an Editor for several IEEE journals and has chaired or co-chaired various IEEE conferences. His current research interests include graph compression, data privacy, and communications.
This lecture series features exciting and dynamic visiting and virtual speakers from across the range of ECE disciplines. Take some time every Friday morning to be inspired by these great scientists and engineers before heading into the weekend!