Your last sentence is perfect. Each chosen internal representation has time/space-tradeoffs its making. Users needs to pick a graph database based on the tradeoffs they can live with for their application.