As I like to point out, for two decades DARPA has offered to pay many millions of dollars to anyone who can demonstrate a graph database that can handle a sparse trillion-edge graph. That data model easily fits on a single machine. No one has been able to claim the money.
Inexplicably, major advances in this area 15-20 years ago under the auspices of government programs never bled into the academic literature even though it materially improved the situation. (This case is the best example I've seen of obviously valuable advanced research that became lost for mundane reasons, which is pretty wild if you think about it.)
I wonder why no one has claimed it. It's possible to compress large graphs to 1 byte per edge via Graph reordering techniques. So a trillion scale graph becomes 1TB, which can fit into high end machines.
Obviously it won't handle high write rates and mutations well. But with Apache Arrow based compression, it's certainly possible to handle read-only and read-mostly graphs.
Also the single machine constraint feels artificial. For any columnar database written in the last 5 years, implementing object store support is tablestakes.
> There are some additional optimizations that are specific to graphs that a relational DBMS needs to incorporate: [...]
This is essentially what Kuzu implemented and DuckDB tried to implement (DuckPGQ), without touching relational storage.
The jury is out on which one is a better approach.