Model your data first using foreign keys, then if you have performance issues with specific queries consider ways of optimizing those queries.

Materializing that data in a graph may be one of those optimization candidates.

I've found an interesting slide show: http://de.slideshare.net/arangodb/domain-driven-design-frosc... explaining how to model your data based on techniques from domain driven design.

You have identify your entities and value objects.

Another good rule I tend to use is that if your queries will involve variable lengths of paths in your graph, it was probably a good idea to model using a graph. This is because another model would almost certainly need multiple joins, which can kill performance quite quickly.

I think if you are connecting the same type of objects (i.e. users) you should use graphs. If you have a 1:n relation between different types, you could as well use foreign keys. For n:m you again need graphs.

Having a 1:n relation which you might want to annotated with, for instance, "type of relation" it is also feasible to use the graph model, as edges can carry attributes.