While previous paper presented such a randomized resuction, the current work presents a deterministoic reduction as well as other reductions that fit other contexts (e.g., the dynamic graph contents).
For $n$-vertex graphs that are $d$-regular, it suffices to connect the input graph to $n$ auxiliary vertices by using a $d$-regular bipartite expander. A natural generalization to non-regular graphs would require a construction of bipartirte expanders for any desired degree sequences. While proving such a construction may be of independent interest, the authors take an alternative path. Specifically, they connect the input graph to $n$ intermedaite vertices (by using a load balancing scheme) and place a $2m/n$-regular bipartite expander between these intermediate vertices and $n$ auxiliary vertices, where $m$ denotes the number of edges in the original graph. This is done by increasing the degree of each original vertex by a factor of two and having $2m/n$ edges from each intermediate vertex to the original vertices.
Expansion from the original vertices is guaranteed by the edges to the intermediate vertices, and expansion from other vertices is guaranteed by the bipartite expnader.