Is there a rule of thumb, in which situation you would model your connection as foreign key and in which situation you would model it as graph? Or do you always use graphs?
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.
Materializing that data in a graph may be one of those optimization candidates.