Amortized Edge Sampling
share
We present a sublinear time algorithm that allows one to sample multiple edges from a distribution that is pointwise ϵ-close to the uniform distribution, in an amortized-efficient fashion. We consider the adjacency list query model, where access to a graph G is given via degree and neighbor queries. The problem of sampling a single edge in this model has been considered by Eden and Rosenbaum (SOSA 18). Let n and m denote the number of vertices and edges of G, respectively. Eden and Rosenbaum provided upper and lower bounds of Θ^*(n/√(m)) for sampling a single edge in general graphs (where O^*(·) suppresses poly(1/ϵ) and poly(log n) dependencies). We ask whether the query complexity lower bound for sampling a single edge can be circumvented when multiple samples are required. That is, can we get an improved amortized per-sample cost if we allow a more costly preprocessing phase? We answer in the affirmative. We present an algorithm that, if one knows the number of required samples q in advance, has an overall cost of O^*(√(q)·(n/√(m))), which is strictly preferable to O^*(q· (n/√(m))) cost resulting from q invocations of the algorithm by Eden and Rosenbaum. More generally, for an input parameter x>1, our algorithm has a preprocessing phase with O^*(n/(x· d_avg)) cost, which then allows an O(x/ϵ) per-sample cost, where d_avg denotes the average degree of the graph.
READ FULL TEXT