  Many modern applications involve accessing and processing graphical data,
i.e. data that is naturally indexed by graphs. Examples come from internet
graphs, social networks, genomics and proteomics, and other sources. The
typically large size of such data motivates seeking efficient ways for its
compression and decompression. The current compression methods are usually
tailored to specific models, or do not provide theoretical guarantees. In this
paper, we introduce a low-complexity lossless compression algorithm for sparse
marked graphs, i.e. graphical data indexed by sparse graphs, which is capable
of universally achieving the optimal compression rate in a precisely defined
sense. In order to define universality, we employ the framework of local weak
convergence, which allows one to make sense of a notion of stochastic processes
for sparse graphs. Moreover, we investigate the performance of our algorithm
through some experimental results on both synthetic and real-world data.
