With key-value, document, and column-family databases, I understand you can scale out with combinations of replication and sharding in the keyspace. But, with common graph operations like shortest path, etc. -- these don't really seem to gain any benefit from replication...and I can't see how you would shard a graph database without finding an independent subgraph (very difficult).
Are there graph databases that try to tackle this problem? What is the current research in this area?
ArangoDB is a multi-model graph database which scales horizontally like a document store also for graphs. It follows the hybrid-index approach to graphs.
With the SmartGraph feature, one can shard a graph dataset by a user defined sharding key (e.g. region, customer, category or any other property) and vertices as well as their edges get distributed to the same machine. The query engine then knows where the data needed for a given query resides, sends the request to the needed machines and executes the query locally. For many scale-out use cases, this can be a suitable solution .https://www.arangodb.com/why-arangodb/arangodb-enterprise/arangodb-enterprise-smart-graphs/
