Storing and querying large graphs efficiently is a central challenge in data processing. While compression with fast queries has been well-studied for texts and trees, graph compression often targets specific applications and rarely provides data structures to support operations on them.

We present a data structure that compresses more when the input graph is more compressible, while still supporting efficient queries without decompressing the graph. For graphs generated by the Barabási–Albert model, we achieve instance-optimal space, and for arbitrary graphs, our space usage matches that of an entropy-compressed edge list.