Я сам исследовал это. Есть ряд интересных графовых баз данных; однако Neo4j и OrientDB - единственные, для которых я нашел какой-либо Ruby API.
Хотя FlockDB не является истинной базой данных графов, она использует бэкэнд MySQL для имитации конструкций баз данных графов.
InfoGrid и HyperGraphDB выглядели интересно, но, к сожалению, без Ruby API.