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. Multilevel partitioners are subject to two limitations: (i) hypergraph coarsening processes rely on local neighborhood structure without fully considering the global structure of the hypergraph; and (ii) refinement heuristics risk entrapment in local minima. In this paper, we describe K-SpecPart, a supervised spectral framework for multi-way partitioning that directly tackles these two limitations. K-SpecPart relies on the computation of generalized eigenvectors and supervised dimensionality reduction techniques to generate vertex embeddings. These are computational primitives that are fast and capture global structural properties of the hypergraph that are not explicitly considered by existing partitioners. K-SpecPart then converts the vertex embeddings into multiple partitioning solutions. K-SpecPart introduces the idea of ''ensembling'' multiple solutions via a cut-overlay clustering technique that often enables the use of computationally demanding partitioning methods such as ILP (integer linear programming). Using the output of a standard partitioner as a supervision hint, K-SpecPart effectively combines the strengths of established multilevel partitioning techniques with the benefits of spectral graph theory and other combinatorial algorithms. K-SpecPart significantly extends ideas and algorithms that first appeared in our previous work on the bipartitioner SpecPart. Our experiments demonstrate the effectiveness of K-SpecPart. For bipartitioning, K-SpecPart produces solutions with up to 15% cutsize improvement over SpecPart. For multi-way partitioning, K-SpecPart produces solutions with up to 20% cutsize improvement over leading partitioners hMETIS and KaHyPar.
Code (0)
등록된 구현이 없습니다.
Tasks
Dimensionality Reductionhypergraph partitioningSupervised dimensionality reductionSimilar Papers 제목 키워드 기반
Self-Supervised Image Representation Learning: Transcending Masking with Paired Image Overlay
Self-supervised learning has become a popular approach in recent years for its ability to learn meaningful representations without the need for data annotation. This paper proposes a novel image augmentation technique, o…
Contrastive LearningImage AugmentationRepresentation LearningSelf-Supervised LearningAoI Minimization in Energy Harvesting and Spectrum Sharing Enabled 6G Networks
Spectrum sharing is a method to solve the problem of frequency spectrum deficiency. This paper studies a novel AI based spectrum sharing and energy harvesting system in which the freshness of information (AoI) is guarant…
Class Knowledge Overlay to Visual Feature Learning for Zero-Shot Image Classification
New categories can be discovered by transforming semantic features into synthesized visual features without corresponding training samples in zero-shot image classification. Although significant progress has been made in…
General Classificationimage-classificationImage ClassificationTriplet+2Semantica: Decentralized Search using a LLM-Guided Semantic Tree Overlay
Centralized search engines are key for the Internet, but lead to undesirable concentration of power. Decentralized alternatives fail to offer equal document retrieval accuracy and speed. Nevertheless, Semantic Overlay Ne…
Minimum cost polygon overlay with rectangular shape stock panels
Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. This has a number of applications …