NegativeSampler - axkoro/graph-impute GitHub Wiki

The NegativeSampler builds an alias table in $O(n)$ to efficiently draw negative samples from a discrete distribution (such as the node frequencies in our random walks) in $O(1)$ time.

It uses Vose's algorithm for building the table.

See here for an extremely good and intuitive explanation on how this works.