Hypergraph Partitioning With Embeddings
  Problems in scientific computing, such as distributing large sparse matrix
operations, have analogous formulations as hypergraph partitioning problems. A
hypergraph is a generalization of a traditional graph wherein "hyperedges" may
connect any number of nodes. As a result, hypergraph partitioning is an NP-Hard
problem to both solve or approximate. State-of-the-art algorithms that solve
this problem follow the multilevel paradigm, which begins by iteratively
"coarsening" the input hypergraph to smaller problem instances that share key
structural features. Once identifying an approximate problem that is small
enough to be solved directly, that solution can be interpolated and refined to
the original problem. While this strategy represents an excellent trade off
between quality and running time, it is sensitive to coarsening strategy. In
this work we propose using graph embeddings of the initial hypergraph in order
to ensure that coarsened problem instances retrain key structural features. Our
approach prioritizes coarsening within self-similar regions within the input
graph, and leads to significantly improved solution quality across a range of
considered hypergraphs. Reproducibility: All source code, plots and
experimental data are available at https://sybrandt.com/2019/partition.
