RE:extremes, we see graph DBs OK for small time series (ex: 2 nodes with a bunch of event multiedges), but not full blown time series... where we'd use a tsdb. Some vendors demo this, but always felt like wrong tool.
The many-hop case is interesting! We don't see 1K-hops typically, and I get nervous even at 10-20 on graph DBs we've used. I can imagine in logistics or sciences that happening more, or maybe even some rdf systems. Partition keys start mattering fast, whether a kvdb or a mpp, but I don't have an intuition here. Probably easier to differentiate on, but too niche?
1k hops is also not something we see on a regular basis in our old business, which is much about people moving houses and transactional data from payment service providers. Ppl with money issues seem to move a lot more often and also fraud cases often have a lot of hops.
The response times provided in the article are for the whole process of searching and returning the entity. The indexes themself are obviously a lot faster - to be precice we are using DynamoDB for storing the indexes, which most times return results in <10ms. Compared to other databases this may still sound slow, but we know that we won't run into scaling issues in this way and that's kind of what matters currently most for us.
Hope that somehow makes sense what I wrote.