If you want to go faster, here are a couple of possible approaches. They both involve some hacking. :)
(1) Modify KNeighborhoodFilter to give you a version in which you traverse edges with some probability p.
A generalization of this is in which you specify a probability for each hop, i.e., use one probability for the first hop, one for the second hop, etc.
A further generalization would use separate probabilities for each edge, possibly based on some property of the nodes/edges involved (e.g., maybe you want to follow edges more or less often if the target has high degree).
Note that this solution involves giving some serious consideration to what kind of random sampling is appropriate in your case. If what you really want is a uniform random sampling of the nodes that would have been in the full result, then you basically need to generate the full result and then filter it.
This is probably the easiest solution; it wouldn't involve much work at all, really.
(2) Create a modified version of KNeighborhoodFilter that divides the work up among different processors. You're probably running this on a machine with > 1 core, so you could create multiple threads and let Java allocate them to different machines; if you really want to speed this up (and you have an appropriate setup) then you could farm it out to different machines, MapReduce-style.