OrientDB is a NoSQL DBMS which can store 150,000 documents per second on common hardware. Even with a document-based database, the relationships are managed as in graph databases, with direct connections among records. You can traverse entire or parts of trees and graphs of records in a few milliseconds. It supports schema-less, schema-full, and schema-mixed modes, has a strong security profiling system based on users and roles, and supports SQL between the query languages. Thanks to the SQL layer, it's straightforward to use for people skilled in the relational world.
Neo4j is a graph database, a fully transactional database that stores data structured as graphs. A graph is a flexible data structure that allows for a more agile and rapid style of development. You can think of Neo4j as a high-performance graph engine with all the features of a mature and robust database. The programmer works with an object-oriented, flexible network structure rather than with strict and static tables, yet enjoys all the benefits of a fully transactional, enterprise-strength database. The community edition is GPLv3 licensed, while the advanced and enterprise editions are AGPLv3 licensed.