How to represent recursive relationships in a graph database

I think you are making a fairly common mistake here by selecting NoSQL technologies in order to be "future-proof" without understandng the tradeoffs. If in doubt start with PostgreSQL and figure you can always set up a graph db or other NoSQL db on the side as you need it. Also you can do graph traversal in PostgreSQL but keep in mind you are working with sets and so that's very, very different from a graph db with different benefits and drawbacks.

Your basic tradeoff is between flexibility of data entry and an ability to flexibly utilize data on output. NoSQL db's (including graph db's) sacrifice the latter for the former and because very often you need an ability to run ad hoc queries on sets of data you probably want an RDBMS somewhere. This means if you have a good data model, you should be able to add adjunct db servers to your environment for special purposes of your RDBMS won't handle it.

Nonetheless, there are a couple specific reasons why if you are thinking at some point of adding various NoSQL solutions why I would recommend starting with PostgreSQL instead of MySQL and these have to do with performance of NoSQL-friendly database structures and the fact that PostgreSQL supports WITH RECURSIVE common table expressions. This approach (WITH RECURSIVE CTE's) allows things like hierarchies and graphs to be traversed using recursive SQL statements which can repeatedly traverse paths. These are also relatively efficient for a set-based approach, and so if you end up with a lot of part/subpart modelling problems you may be able to do that directly in PostgreSQL without too much work. If this doesn't work however, you can also more easily represent the data in a way which is easier to import into your NoSQL db. So it gets you further and it integrates better. You may even be able to set up foreign "tables" against your NoSQL db and run queries against it from inside Pg!

More on the Tradeoff 1

Graph databases arose from a need to do binary traversal quickly over large sets of information. The obvious example might be a social network site like LinkedIn which might want to tell you quickly how far removed you are from another user (in simple terms this means essentially they are designed to play "six degrees of Kevin Bacon"). Typically on a graph database you are essentially traversing nodes using what are often described as "three word sentences" which represent the graphs. In this regard you are looking at essentially something like "John friended Jane" and traversing this way. Typically the API is relatively navigational.

A relational database is really designed to work with sets of information. Typically when giving up on relational databases, one is giving up on set operations too. This can be a big deal. Often it is faster both operationally and in terms of development time to be able to do set operations rather than navigate, aggregate, and report. This is a huge difference and if your use case fits a relational workflow, I have trouble imagining that a graph db will help you.

More on the tradeoff 2: Consistency Models

A second thing to investigate and keep in mind is the question of what consistency model your database uses. Even with "ACID-Compliant" RDBMS's there is a range of consistency models based on different levels of transaction isolation that can be used to prevent problems. If your data is important, the standard RDBMS consistency models are going to fare much better than most of the NoSQL models because they make more guarantees both to the DBA and to the application. Graph databases are a relatively large field, and each vendor may have some differences in their consistency model. This isn't necessarily something that will rule the use out, but it is something to be cautious about when looking at the solutions as a whole.

Note that schema flexibility is both a blessing and a curse in the NoSQL world and this also affects graph databases. It is a blessing because you can get up and running in the initial stages faster, but it is a curse because the set operation strengths of an RDBMS depend on a fixed schema, and those that relax that to some extent (Informix, for example, supports jagged rows in return sets) require programmer knowledge of the places where those requirements have been relaxed.

How can I model this in a graph database like Neo4j?

Modeling neo4j graphs from relational data is quite simple:

1. Decide your vertexes (nodes, objects) and edges (relationships).
2. Convert relational data to cypher, declaring all items and all relationships explicit.

Note: Mapping from relational to graph could take only selected entities from relational model, and single table rows can explode into multiple vertexes and multiple edges.

Is this the right way to structure this data in a graph database?

Yes, it looks OK. Assuming that file, author, company, user, and image are nodes, and date is only an attribute, this

file: 11425646.pdf
  author: bob
  company: abc co
  date: 1/1/2011
  mentioned_users: [alice,sue,mike,sally]
  images: [1958.jpg,535.jpg,35735.jpg]

should convert to this

MERGE (f :File {name:'11425646.pdf', date:'1/1/2011'})
MERGE (a :Author {name:'bob'})
MERGE (c :Company {name:'abc co'})
MERGE (u1 :User {name:'alice'})
MERGE (u2 :User {name:'sue'})
MERGE (u3 :User {name:'mike'})
MERGE (u4 :User {name:'sally'})
MERGE (i1 :Image {name:'1958.jpg'})
MERGE (i2 :Image {name:'535.jpg'})
MERGE (i3 :Image {name:'35735.jpg'})
MERGE (f)-[:WRITTEN_BY]->(a)
MERGE (f)-[:FROM_COMPANY]->(c)
MERGE (f)-[:MENTIONS]->(u1)
MERGE (f)-[:MENTIONS]->(u2)
MERGE (f)-[:MENTIONS]->(u3)
MERGE (f)-[:MENTIONS]->(u4)
MERGE (f)-[:HAS_IMAGE]->(i1)
MERGE (f)-[:HAS_IMAGE]->(i2)
MERGE (f)-[:HAS_IMAGE]->(i3)

Useful links: data modeling guide and Cypher reference