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.