## Data compression for sparse labeled graphs

Shannon entropy, in its simplest interpretation, concerns data compression where the data is a long string from a finite alphabet: assuming a stationary source of entropy $$\mathcal{E}$$, a length-$$n$$ string can be coded as a binary string of length about $$\mathcal{E} n$$. Consider instead a sparse ($$O(1)$$ average degree) $$n$$-vertex graph, whose vertices are labeled by distinct length-$$O(\log n)$$ strings from a finite alphabet. The entropy of the graph structure and the entropy of the labels are typically both of order $$n \log n$$. Are there universal codes analogous to Lempel-Ziv for asymptotically optimal compression of such labeled graphs? We raised the question in this paper but made no progress.