  Sampling random nodes is a fundamental algorithmic primitive in the analysis
of massive networks, with many modern graph mining algorithms critically
relying on it. We consider the task of generating a large collection of random
nodes in the network assuming limited query access (where querying a node
reveals its set of neighbors). In current approaches, based on long random
walks, the number of queries per sample scales linearly with the mixing time of
the network, which can be prohibitive for large real-world networks. We propose
a new method for sampling multiple nodes that bypasses the dependence in the
mixing time by explicitly searching for less accessible components in the
network. We test our approach on a variety of real-world and synthetic networks
with up to tens of millions of nodes, demonstrating a query complexity
improvement of up to $\times 20$ compared to the state of the art.
