A strategy that I have found useful (if you have a field in your documents that you can use as a Primary Key field, such as "UserId") is to query for the user object you want to link to, and if it exists, create the edge/link. If it does not exists, then just create a "stub" vertex of type "User" with Id = <UserId>. That will give you something to link to. Later, when the actual User object shows up for insert into the database, you can just update the existing node with the rest of the User data, and you won't disturb your already-existing links. If you need to be able to specifically identify these "stub" nodes, you can always add a second property called "Temporary=true" or something like that, so you'll always be able to pick them out later if necessary.
Good luck,
Patrick