I haven't tried Titan, but I've played around with neo4j a little bit in the past and found it a little frustrating to get started with.

The good part is the ACID transactions and the (beautiful) browser based interface to it. The bad part is that it was far too easy to get the database in a locked state when you perform a bad query (which you tend to do a lot as you're learning).

Graph databases are extremely powerful and will likely change the way you look at structuring a lot of data mining problems. I'd recommend trying one of them out if you ever get the chance!