Performance in graph databases is critical, and would need improvements of several orders of magnitude, rather than tens of percent points. Many algorithms are impractical in real world graphs because they are often O(n^2) or more, and in practice we have to resort to approximated algorithms instead (like pagerank and all the likes).