[Vulkum]

I think the random walk is incorporating the "hidden" knowledge which clusters the nodes in the graph together. As they use inference to create the links between the nodes, that will (I believe) incorporate the knowledge forming a local neighbourhood of data which when traversed randomly will expose that knowledge.

Moving forward from the sparse to dense conversion (which is pretty clever) I think it would be interesting to look at learning properties of vertices or clusters from random walks on surrounding clusters. This would enable someone to capture information which might not be directly available (silly example: activity of a hidden facebook group, based on the activities/profiles of its members).