  Graphs play an increasingly important role in various big data applications.
However, existing graph data structures cannot simultaneously address the
performance bottlenecks caused by the dynamic updates, large scale, and high
query complexity of current graphs. This paper proposes a novel data structure
for large-scale dynamic graphs called CuckooGraph. It does not require any
prior knowledge of the upcoming graphs, and can adaptively resize to the most
memory-efficient form while requiring few memory accesses for very fast graph
data processing. The key techniques of CuckooGraph include TRANSFORMATION and
DENYLIST. TRANSFORMATION fully utilizes the limited memory by designing related
data structures that allow flexible space transformations to smoothly
expand/tighten the required space depending on the number of incoming items.
DENYLIST efficiently handles item insertion failures and further improves
processing speed. Our experimental results show that compared with the most
competitive solution Spruce, CuckooGraph achieves about $33\times$ higher
insertion throughput while requiring only about $68\%$ of the memory space.
