PROJECT TITLE :

Hypergraph Partitioning With Embeddings

ABSTRACT:

In scientific computing, problems like distributing large sparse matrix operations have analogous formulations as hypergraph partitioning problems. These problems can be solved using computers. A traditional graph can be generalized into a hypergraph, which allows "hyperedges" to connect an unlimited number of nodes to each other. As a consequence of this, hypergraph partitioning is an NP-hard problem, meaning that its solution or approximation is difficult to achieve. The multilevel paradigm is followed by the state-of-the-art algorithms that are used to solve this problem. This paradigm begins by iteratively "coarsening" the input hypergraph to smaller problem instances that share key structural features. Once an approximate problem that is manageable enough to be solved directly has been identified, the solution to that problem can then be interpolated and refined to apply to the original problem. This strategy is sensitive to coarsening strategy despite the fact that it offers an excellent compromise between quality and running time. In this body of work, we propose making use of graph embeddings of the initial hypergraph in order to make certain that coarsened problem instances retrain important structural characteristics. Our strategy gives higher priority to coarsening within self-similar regions within the input graph, which ultimately results in significantly improved solution quality across the full spectrum of hypergraphs that are taken into consideration.