Edge-Parallel Graph Encoder Embedding
Ariel Lubonja Cencheng Shen Carey Priebe Randal Burns
New algorithms for embedding graphs have reduced the asymptotic complexity of
finding low-dimensional representations. One-Hot Graph Encoder Embedding (GEE)
uses a single, linear pass over edges and produces an embedding that converges
asymptotically to the spectral embedding. The scaling and performance benefits
of this approach have been limited by a serial implementation in an interpreted
language. We refactor GEE into a parallel program in the Ligra graph engine
that maps functions over the edges of the graph and uses lock-free atomic
instrutions to prevent data races. On a graph with 1.8B edges, this results in
a 500 times speedup over the original implementation and a 17 times speedup
over a just-in-time compiled version.