Some people build "graph databases" on top of storage backends that are ill suited for such workloads. e.g you can build a "graph database" (or K/V store) on top of MySQL, but the performance is terrible - http://java.dzone.com/articles/mysql-vs-neo4j-large-scale

a "native graph database" is one that is actually designed for the task.

Basically for me, it has two aspects: first the storage engine is designed to handle all models natively. second you have a common query language which is supported by the database storage engine.

There are different approaches, which are used in other products and which can also work well. For example, you can restrict the database engine to a pure key/value store and add different personalities to it. Or you have a client which implements a common query language for different products.

I think the idea with "native multi-model" is that Arango was explicitly designed to do k/v, documents and graphs rather than it being something that is bolted on afterwards.