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.
Code (0)
등록된 구현이 없습니다.
Tasks
hypergraph partitioningSimilar Papers 제목 키워드 기반
K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning
State-of-the-art hypergraph partitioners follow the multilevel paradigm that constructs multiple levels of progressively coarser hypergraphs that are used to drive cut refinement on each level of the hierarchy. Multileve…
Dimensionality Reductionhypergraph partitioningSupervised dimensionality reductionConsistency of Spectral Hypergraph Partitioning under Planted Partition Model
Hypergraph partitioning lies at the heart of a number of problems in machine learning and network sciences. Many algorithms for hypergraph partitioning have been proposed that extend standard approaches for graph partiti…
graph partitioninghypergraph partitioningStochastic Block ModelUniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
In a series of recent works, we have generalised the consistency results in the stochastic block model literature to the case of uniform and non-uniform hypergraphs. The present paper continues the same line of study, wh…
Clusteringhypergraph partitioningStochastic Block ModelHypergraph Partitioning using Tensor Eigenvalue Decomposition
Hypergraphs have gained increasing attention in the machine learning community lately due to their superiority over graphs in capturing super-dyadic interactions among entities. In this work, we propose a novel approach …
graph partitioninghypergraph partitioningBalanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy
We propose a balanced coarsening scheme for multilevel hypergraph partitioning. In addition, an initial partitioning algorithm is designed to improve the quality of k-way hypergraph partitioning. By assigning vertex weig…
hypergraph partitioning