Edge-Parallel Graph Encoder Embedding
<|reference_start|>Edge-Parallel Graph Encoder Embedding: 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.<|reference_end|>
@article{lubonja2024edge-parallel,
    title={Edge-Parallel Graph Encoder Embedding},
    author={Ariel Lubonja (1), Cencheng Shen (2), Carey Priebe (1) and Randal
  Burns (1) ((1) Johns Hopkins University, (2) University of Delaware)},
    journal={arXiv preprint arXiv:2402.04403},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.04403},
    primaryClass={cs.DC cs.LG}
}