The most common and relevant difference is that a graph database has a storage engine that is optimized for graph traversal. For example, in a RDBMS, another row is referenced via a foreign key which involves a lookup to an indexed column, while in a graph database, a node is often referenced by its storage location. This makes graph traversals much cheaper, and is also something that an RDBMS is unable to optimise for because of conflicts with the relational model.

Similarly, the query language is optimised for graph traversal types of queries, in a way that would not be possible in an RDBMS due to the relational model constraints, and also because some of the query operations would be extremely inefficient in an RDBMS storage engine.

> That sounds like graphs but Rethink is not a graph database (compared to Neo4j, GUN, Orient, Arango, etc).

With regards to the listed databases, some are, but the rest are not (and do not claim to be) graph databases.

Note: It's different people replying to you.