On the second day of Orchard Harvest one of the hackathon groups explored the idea of using graph databases, specifically Neo4j, in Orchard. I followed up on the topic and researched on how graph databases can play along in an Orchard module.
You can see the progress from the discussion I've opened. I've searched for .NET graph databases but couldn't really find any up-to-date project, even .NET drivers for graph databases are scarce. Neo4j seemed indeed like the best way to explore further: it's a very popular graph database and exposes a RESTful API so other pieces of software can use it even when they don't run on Java like the Neo4j itself. Fortunately Tatham Oddie and his team developed Neo4jClient, a .NET wrapper that provides a nice interface to interact with Neo4j through its web services.
It turns out that using Neo4jClient from Orchard is quite simple.