Neo4J has clojure'ey bindings here and here and here
you can get the leiningen and maven config for each of these from clojars
allegrograph is another similar graph data store that is widely supported in clojure. so there is some evidence that the answer may be yes!
graph stores lend them selves well to immutable trees which may be an even better fit to Clojure than sets but this is all fairly subjective. The most objective answer I can give is to point to existing use of graph-stores/triple-stores.
Mark Watson's book (free pdf version: http://www.markwatson.com/opencontent/book_java.pdf), a lesser known Clojure book he self-published last year, covers some useful graph technology, mainly allegrograph.
I myself don't have much experience with graph db libraries, but the above-cited book mentions that neo4j is optimized to traverse graphs, whereas allegrograph is optimized for subgraph matching. So the choice will likely depend on your specific application.
If you go with allegograph, the author of that book waives the AGPL license on his wrappers for production use if you buy copies of his book, and of course can be used under the conditions of the license freely https://github.com/mark-watson/java_practical_semantic_web
The clojure-neo4j wrapper library exists, though it's unclear if it would be code-rotted or ready for use given the last commit date https://github.com/JulianMorrison/neo4j-clojure. The most recently updated fork, by mattrepl, however was not that long ago: https://github.com/mattrepl/clojure-neo4j.git
