Hypergraph Partitioning With Embeddings

Justin Sybrandt

doi:10.1109/TKDE.2020.3017120

2022-06-01

Justin Sybrandt *

Ruslan Shaydulin

Ilya Safro

DOI：10.1109/TKDE.2020.3017120

原文链接

查看原文

摘要

En 中文

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.

Keyword:

Partitioning algorithms

Bipartite graph

Approximation algorithms

Machine learning

Message systems

Interpolation

Contracts