I'd go with https://myservice.com/users/112358/contacts
.
If only because there may be resources "under" users that may at some point be viewable by other users. For example user X being able to see documents of user 112358.
Consistency in URI's is an advantage. Even if, using HATEOAS, consistency in URI's is not so much a concern on the outside, it will be helpful growing and maintaining the API's implementation.