Multilevel graph embedding
Abstract
The goal of the present paper is the design of embeddings of a general sparse graph into a set of points in $$\mathbb{R}^d$$ for appropriate d ≥ 2. The embeddings that we are looking at here aim to keep vertices that are grouped in communities together and keep the rest apart. To achieve this property, we utilize coarsening that respects possible community structures of the given graph. We employ a hierarchical multilevel coarsening approach that identifies communities (strongly connected groups of vertices) at every level. The multilevel strategy allows any given (presumably expensive) graph embedding algorithm to be made into a more scalable (and faster) algorithm. We demonstrate the presented approach on a number of given embedding algorithms and largescale graphs and achieve speedup over the methods in a recent paper.
 Authors:

 Northeastern Univ., Boston, MA (United States). Computer Science Dept.
 Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States). Center for Applied Scientific Computing; Portland State Univ., OR (United States). Dept. of Mathematics and Statistics
 Publication Date:
 Research Org.:
 Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
 Sponsoring Org.:
 USDOE National Nuclear Security Administration (NNSA)
 OSTI Identifier:
 1669230
 Alternate Identifier(s):
 OSTI ID: 1804605
 Report Number(s):
 LLNLJRNL777449
Journal ID: ISSN 10705325; 971424
 Grant/Contract Number:
 AC5207NA27344
 Resource Type:
 Accepted Manuscript
 Journal Name:
 Numerical Linear Algebra with Applications
 Additional Journal Information:
 Journal Volume: 28; Journal Issue: 3; Journal ID: ISSN 10705325
 Publisher:
 Wiley
 Country of Publication:
 United States
 Language:
 English
 Subject:
 97 MATHEMATICS AND COMPUTING
Citation Formats
Quiring, Benjamin, and Vassilevski, Panayot S. Multilevel graph embedding. United States: N. p., 2020.
Web. https://doi.org/10.1002/nla.2326.
Quiring, Benjamin, & Vassilevski, Panayot S. Multilevel graph embedding. United States. https://doi.org/10.1002/nla.2326
Quiring, Benjamin, and Vassilevski, Panayot S. Wed .
"Multilevel graph embedding". United States. https://doi.org/10.1002/nla.2326. https://www.osti.gov/servlets/purl/1669230.
@article{osti_1669230,
title = {Multilevel graph embedding},
author = {Quiring, Benjamin and Vassilevski, Panayot S.},
abstractNote = {The goal of the present paper is the design of embeddings of a general sparse graph into a set of points in $\mathbb{R}^d$ for appropriate d ≥ 2. The embeddings that we are looking at here aim to keep vertices that are grouped in communities together and keep the rest apart. To achieve this property, we utilize coarsening that respects possible community structures of the given graph. We employ a hierarchical multilevel coarsening approach that identifies communities (strongly connected groups of vertices) at every level. The multilevel strategy allows any given (presumably expensive) graph embedding algorithm to be made into a more scalable (and faster) algorithm. We demonstrate the presented approach on a number of given embedding algorithms and largescale graphs and achieve speedup over the methods in a recent paper.},
doi = {10.1002/nla.2326},
journal = {Numerical Linear Algebra with Applications},
number = 3,
volume = 28,
place = {United States},
year = {2020},
month = {9}
}
Works referenced in this record:
A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
journal, January 1998
 Karypis, George; Kumar, Vipin
 SIAM Journal on Scientific Computing, Vol. 20, Issue 1
Distributed Louvain Algorithm for Graph Community Detection
conference, May 2018
 Ghosh, Sayan; Halappanavar, Mahantesh; Tumeo, Antonino
 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software
journal, June 2014
 Jacomy, Mathieu; Venturini, Tommaso; Heymann, Sebastien
 PLoS ONE, Vol. 9, Issue 6
A Parallel Graph Coloring Heuristic
journal, May 1993
 Jones, Mark T.; Plassmann, Paul E.
 SIAM Journal on Scientific Computing, Vol. 14, Issue 3
Fast unfolding of communities in large networks
journal, October 2008
 Blondel, Vincent D.; Guillaume, JeanLoup; Lambiotte, Renaud
 Journal of Statistical Mechanics: Theory and Experiment, Vol. 2008, Issue 10
A Simple Parallel Algorithm for the Maximal Independent Set Problem
journal, November 1986
 Luby, Michael
 SIAM Journal on Computing, Vol. 15, Issue 4
Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
journal, September 1996
 Vaněk, P.; Mandel, J.; Brezina, M.
 Computing, Vol. 56, Issue 3
Adaptive Smoothed Aggregation ($\alpha$SA) Multigrid
journal, January 2005
 Brezina, M.; Falgout, R.; MacLachlan, S.
 SIAM Review, Vol. 47, Issue 2