I think that one of the advantage of graph databases is to avoid heavyly join operation. This means traversal from a node to other connected nodes will more compactly. Some of graph databases has feature that schema free like Neo4j. Is it truly convenient storing nodes which don't belong any schema in case of many? To get high velocity of traverse (using property values) of data that has graph structure, I think design of graph databases basically have to constrain schema to nodes and edges. If this is not the case, I guess that the database probably doesn't emphasize about speed.
// Cyper MATCH (person:Person)-[knows:Knows]->(Person) WHERE knows.since > 2015 // ↑ The DB must one by one check see if the property 'since' exists and be comparable with '2015' before evaluating op '>'. RETURN id(knows)
Other hand, I agree with convenience of schemaless specification partially. For example, it's for data which historicall and fluctual. Because of schema migration sometimes cause break compatibilities with old records. I tried to use schemaless graph database in data series had such nature. One more case of my agree is for prototyping. However, enjoying these conveniences are only a fraction of the total time from start of product development to end of life. It seems a bit too expensive to compensate for the decide to choice to use Graph database rather than usual RDB.
Isn't it one of biggest purpose of use graph database that high velocity in traverse many edges?