For instance in the last.fm example, the document entity is the user. If user A and user B (amongst others) both like the same 5 bands, then Graph will show user A connected to these 5 bands and user B connected to these same 5 bands, so there is an implicit connection between user A and user B. Since it is also known how many bands user A likes and how many bands user B likes, all the necessary information is their to build a (weighted) connection. Could this connection also be made explicit?
Given the structure of the docs in this example the best way to find the most-related user to a given user would be to use a "more like this" query not a graph query.
I think a graph where nodes are users would be less cohesive than a graph where nodes are bands. Users tend to have varied tastes and when chaining userA->userB->userC you can quickly go "off the scent" whereas individual bands tend to be more single-focused in their genre and reinforced in their connections by the listening habits of thousands.