FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning

FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning Rongjian Liang

rliang@nvidia.com NVIDIA Austin, TX, USA

Zhuo Feng

ACM Reference Format: Rongjian Liang, Zhuo Feng, and Brucek Khailany. 2027. FRESHPart: FeedbackReshaped Spectral Embedding for Hypergraph Partitioning. In 32nd Asia and South Pacific Design Automation Conference (ASPDAC ’27), January 25–28, 2027, Tokyo, Japan. ACM, New York, NY, USA, 7 pages. https://doi. org/10.1145/3840404.3848206

Introduction

Hypergraph partitioning [2, 16] is a fundamental optimization problem in VLSI physical design and many scientific computing applications. Given a hypergraph, the objective is to partition its vertices into balanced subsets while minimizing the number (or weight) of cut hyperedges. Scalable and high-quality partitioning algorithms are essential for modern large-scale applications.

This work is licensed under a Creative Commons Attribution 4.0 International License. ASPDAC ’27, Tokyo, Japan © 2027 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2923-2/2027/01 https://doi.org/10.1145/3840404.3848206

(a) Base Embedding

Geometry Guided Laplacian

Geometry Feedback Embedding

Search Solution

Search

Search

Feedback Embedding

Edge Reweight

Hypergraph partitioning, spectral methods, graph algorithms.

• Existing methods: Embedding is fixed • FRESHPart: Embedding is reshaped by feedback-guided Laplacian

Laplacian Solver

Keywords

Solution

Laplacian Solver

• Hardware → Partitioning and floorplanning; • Mathematics of computing → Hypergraphs; Spectra of graphs; Graph algorithms.

Search

Edge Reweight

CCS Concepts

Embedding

Laplacian Solver

With scalable Laplacian solvers now available, the next frontier is to exploit them more effectively for high-quality hypergraph partitioning. In this work, we revisit spectral hypergraph partitioning from the perspective of spectral embedding geometry. Through a systematic analysis of circuit hypergraphs and controlled synthetic (hyper)graphs, we identify a ray-like embedding structure that helps explain the effectiveness of projection-based partitioning. We further show that the geometry of spectral embeddings can be systematically influenced through Laplacian design and hyperedge reweighting. Guided by these insights, we propose FRESHPart, a feedback-reshaped spectral partitioning framework that refines the spectral embedding through Geometry Feedback and Search Feedback, producing embeddings that are better aligned with projectionbased partitioning. On the Titan23 benchmark, FRESHPart achieves average cut reductions over hMETIS of 13.09% at 𝜖 = 2% and 25.21% at 𝜖 = 20%, surpassing the strongest previously reported results (12.16% and 22.53%, respectively), while completing every benchmark in under 120 s on a single GPU.

Hypergraph

bkhailany@nvidia.com NVIDIA Austin, TX, USA

Laplacian Solver

arXiv:2611.05729v2 [cs.LG] 5 Nov 2026

Abstract

1

Brucek Khailany

zfeng12@stevens.edu Stevens Inst of Tech & NVIDIA Hoboken, New Jersey, USA

Search Guided Laplacian

(b)

Figure 1: Comparison of (a) workflow of prior spectral partitioners and (b) workflow of FRESHPart.

Spectral graph partitioning [1, 10, 11, 13, 23, 26, 31] has been studied for decades due to its strong theoretical foundations, but its practical adoption has been limited by two challenges: the high cost of computing spectral embeddings and partition quality inferior to the dominant multilevel paradigm [9, 15, 17, 24, 25]. Recent advances in Laplacian solvers [8, 12, 20, 27] have largely removed the computational bottleneck, making spectral methods practical for million-scale sparse graphs. Consequently, the primary challenge has shifted from computing spectral embeddings efficiently to exp- loiting them effectively. This motivates a fresh look at spectral hypergraph partitioning with the goal of surpassing state-of-the-art (SOTA) multilevel partitioners. Classical spectral partitioning typically clusters spectral embeddings using 𝐾-means, which favors compact Euclidean clusters and provides no direct mechanism for enforcing balance constraints [21, 28]. More recently, projection-based partitioning, exemplified by HySpecPro [19], has emerged as an effective alternative by directly searching for projection vectors in the spectral embedding space that optimize both cut quality and balance. Its success, however, has been supported largely by empirical evidence, raising two fundamental questions: What geometric properties of embeddings make projection-based partitioning effective, and what determines the geometry of spectral embeddings? To answer these questions, we systematically analyze spectral embeddings of both circuit hypergraphs and controlled synthetic (hyper)graphs using principal component analysis (PCA) visualization and a new ray concentration metric. Our study reveals that the ray structure provides a geometric explanation for the effectiveness of projection-based partitioning.

ASPDAC ’27, January 25–28, 2027, Tokyo, Japan

Moreover, we show that the geometry is determined not only by the structural properties of the underlying (hyper)graph, but also by the choice of Laplacian operator and hyperedge weighting. These findings demonstrate that spectral geometry is not merely an intrinsic property of the input hypergraph, but can be systematically shaped to improve partitioning quality. Motivated by these insights, we propose FRESHPart, a feedbackdriven spectral partitioning framework that treats the Laplacian as an adaptive lens for generating spectral embeddings. As illustrated in Figure 1, conventional spectral methods compute the Laplacian once and use it as a fixed lens throughout partitioning. If this lens is not well aligned with the partitioning objective, additional projection search can only explore the resulting embedding more thoroughly—it cannot correct the misalignment introduced by the lens itself. FRESHPart instead leverages both Geometry Feedback from the current embedding and Search Feedback from partitioning outcomes to reweight hyperedges and reshape the Laplacian, producing embeddings that are better aligned with the partitioning objective. Although this refinement requires additional Laplacian solves and projection searches, it preserves the linear runtime scalability of HySpecPro while delivering substantially larger gains than simply increasing the projection search budget. Our main contributions are summarized as follows: • We provide a geometric perspective on projection-based spectral hypergraph partitioning. Through systematic analysis of circuit hypergraphs and controlled synthetic (hyper)graphs, we identify a ray-like embedding structure that helps explain the effectiveness of projection-based partitioning, and show how graph structure, Laplacian design, and hyperedge reweighting influence spectral geometry. • We propose FRESHPart, a feedback-driven spectral hypergraph partitioning framework that reshapes the spectral embeddings according to both embedding geometry and partitioning outcomes. By reweighting hyperedges and recomputing the bipartite Laplacian, FRESHPart produces embeddings that are better aligned with the partitioning objective. • We demonstrate SOTA partitioning quality on the Titan23 benchmark suite. FRESHPart consistently outperforms existing multilevel and spectral partitioners, achieving the best reported cut quality while completing every benchmark in under 120 seconds on a single GPU.

2 Preliminaries 2.1 Problem Formulation A hypergraph is defined as 𝐻 = (𝑉 , 𝐸), where 𝑉 is the vertex set and 𝐸 is the set of hyperedges, with each hyperedge 𝑒 ⊆ 𝑉 connecting an arbitrary subset of vertices. Each vertex 𝑣 ∈ 𝑉 and hyperedge 𝑒 ∈ 𝐸 is associated with a nonnegative weight 𝑤 (𝑣) and 𝑤 (𝑒), respectively. The balanced hypergraph partitioning problem seeks to partition 𝑉 into 𝐾 disjoint blocks {𝑉1, . . . , 𝑉𝐾 } while minimizing the total weight of cut hyperedges subject to

max

1≤𝑘 ≤𝐾

∑︁ 𝑣 ∈𝑉𝑘

 𝑤 (𝑣) ≤

 ∑︁ 1 +𝜖 𝑤 (𝑣), 𝐾 𝑣 ∈𝑉

Rongjian Liang, Zhuo Feng, and Brucek Khailany

where 𝜖 specifies the allowable imbalance ratio. This work focuses on the bipartitioning problem (𝐾 = 2); extending the proposed framework to multi-way partitioning is left for future work.

2.2

Spectral Embeddings and Partitioning

Spectral partitioning relaxes the discrete partitioning problem into a continuous one by embedding vertices into a low-dimensional Euclidean space. The embedding is obtained from the eigenvectors associated with the smallest nontrivial eigenvalues of a normalized Laplacian, providing a continuous relaxation of the balanced minimum-cut problem [28]. Two Laplacian formulations [30] are widely used for hypergraphs. The clique expansion replaces each hyperedge 𝑒 with a weighted clique connecting all pairs of its incident vertices. Each
pairwise edge is assigned weight 𝑤 (𝑒)/ |𝑒2 | , where |𝑒 | denotes the degree of the hyperedge. Let 𝐴𝐶 and 𝐷𝐶 denote the resulting weighted adjacency and degree matrices. The normalized Laplacian is 𝐿𝐶 = 𝐼 − 𝐷𝐶−1/2𝐴𝐶 𝐷𝐶−1/2 . Although simple and computationally efficient, clique expansion reduces higher-order interactions to pairwise connections and may distort the original higher-order connectivity, particularly for large hyperedges. The bipartite representation instead preserves the incidence structure by introducing one node for each hyperedge. A bipartite edge connects a vertex 𝑣 to a hyperedge node 𝑒 with weight 𝑤 (𝑒)/|𝑒 | whenever 𝑣 ∈ 𝑒. Let 𝐴𝐵 and 𝐷 𝐵 denote the resulting adjacency and degree matrices. The normalized bipartite Laplacian is 𝐿𝐵 = 𝐼 − 𝐷 𝐵−1/2𝐴𝐵 𝐷 𝐵−1/2 . Classical spectral partitioning obtains partitions by clustering the embedded vertices using K-means. More recently, HySpecPro employs Covariance Matrix Adaptation Evolution Strategy (CMAES [14]) to optimize projection vectors in the spectral embedding space, assigning each vertex to the partition whose projection vector has the largest inner product. This projection-based framework directly optimizes cut quality under balance constraints while achieving linear runtime in the total hyperedge degree. Building on this framework, we investigate the geometry of spectral embeddings and propose a feedback mechanism that reshapes the embedding through hyperedge reweighting and Laplacian recomputation.

3

Spectral Geometry Diagnostics

We systematically investigate the geometry of spectral embeddings through two complementary studies. We first analyze the Titan23 benchmarks to understand why projection-based partitioning is effective. We then study controlled synthetic (hyper)graphs to identify what determines the geometry of spectral embeddings.

3.1

Diagnostic Tools

Two complementary diagnostic tools are introduced: PCA visualization for qualitative inspection and a new ray concentration metric for quantitative analysis. PCA Visualization. We construct spectral embeddings using both the normalized bipartite and clique Laplacians. After removing numerically trivial eigenmodes (eigenvalues below 10−6 ), we retain the first 𝑆 = 16 nontrivial eigenvectors 𝑢 1, . . . ,
𝑢𝑆 . The embedding of vertex 𝑣 is defined as 𝑥 𝑣 = 𝑢 1 (𝑣), . . . , 𝑢𝑆 (𝑣) . For visualization, the embeddings are projected onto two dimensions using PCA.

FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning SLAM spheric

denoise

0.010

0.004

0.002

0.005

0.005

0.002

0.010

0.004

0.015 0.020

0.002

0.000

0.000

0.000

ASPDAC ’27, January 25–28, 2027, Tokyo, Japan

Table 1: Ray concentration across synthetic graph families at different average vertex degrees. Hypergraph results are reported for both the bipartite (bi.) and clique (cl.) Laplacians.

0.002 0.004

0.006 0.020 0.015 0.010 0.005 0.000

mes noc

0.05 0.04 0.03 0.02 0.01 0.00

0.004 0.002 0.000 0.002 0.004

Figure 2: PCA visualization of bipartite spectral embeddings on representative Titan23 benchmarks. random graph

random hyper (bipartite)

random hyper (clique)

mesh graph

mesh hyper (bipartite)

mesh hyper (clique)

modular graph

modular hyper (bipartite)

modular hyper (clique)

hier graph

hier hyper (bipartite)

Ray Concentration. To quantify ray structure, we apply spherical 𝐾-means to the embedding. We first normalize each vertex embedding as 𝑥ˆ𝑣 = 𝑥 𝑣 /∥𝑥 𝑣 ∥ 2 , then cluster the normalized vectors into 𝐾𝑟 groups with unit-norm centers 𝑐 1, . . . , 𝑐 𝐾𝑟 . We define ray concentration as 1 ∑︁ max 𝑥ˆ ⊤𝑐 𝑗 . 𝑟 𝐾𝑟 (𝑋 ) = |𝑉 | 𝑣 ∈𝑉 1≤ 𝑗 ≤𝐾𝑟 𝑣 This measures the average cosine similarity to the nearest ray center. Higher values indicate that the embeddings align closely with a small number of rays. For the Titan23 benchmarks, we fix 𝐾𝑟 = 12, which captures the dominant ray structure without introducing overly fine-grained ray clusters. For the synthetic benchmarks, we fix 𝐾𝑟 = 8, matching the eight underlying modules in the synthetic graph generation.

3.2

Diagnostic of Titan23 Benchmarks

The Titan23 benchmark suite consists of real-world VLSI circuit hypergraphs. As shown in Figure 2, their bipartite spectral embeddings exhibit a pronounced ray-like structure, rather than the compact blob-like distributions typically assumed by classical 𝐾means clustering. This observation is further quantified in Table 4: the base embeddings achieve an average ray concentration of 0.922, indicating that ray-like spectral geometry is prevalent in real-world circuit hypergraphs. To examine whether the ray structure is associated with the effectiveness of projection-based partitioning, we compute the Pearson correlation between the ray concentration and the cut-size reduction achieved by HySpecPro over the widely used multilevel partitioner hMetis at 𝜖 = 2%. The resulting correlation coefficient

𝑑¯ ≈ 1.25 𝑑¯ ≈ 5 𝑑¯ ≈ 20

random graph random hyper (bi.) random hyper (cl.)

0.802 0.833 0.866

0.754 0.806 0.751

0.567 0.624 0.566

mesh graph mesh hyper (bi.) mesh hyper (cl.)

0.759 0.814 0.830

0.826 0.825 0.823

0.826 0.825 0.826

modular graph modular hyper (bi.) modular hyper (cl.)

0.802 0.836 0.886

0.941 0.952 0.943

0.910 0.925 0.872

hierarchical graph hierarchical hyper (bi.) hierarchical hyper (cl.)

0.745 0.840 0.821

0.731 0.925 0.926

0.567 0.955 0.947

Table 2: Effect of hyperedge weighting |𝑒 | −𝛼 on the ray concentration of modular hypergraphs under the bipartite Laplacian.

hier hyper (clique)

Figure 3: PCA visualization of spectral embeddings for synthetic graph and hypergraph families at average vertex degree 𝑑¯ = 20. Hypergraph embeddings are computed using both the normalized bipartite and clique Laplacians. Colors indicate the ground-truth modules used to generate the synthetic instances.

Family/operator

𝑑¯

𝛼=0

0.5

1.25 5 20

0.860 0.943 0.864

0.883 0.893 0.836 0.954 0.954 0.952 0.883 0.884 0.925

0.6

1.0

1.5

2.0

0.861 0.873 0.918 0.927 0.914 0.892

of 0.42 indicates a moderate positive correlation, suggesting that benchmarks with stronger ray structure tend to benefit more from projection-based partitioning. The correlation is not expected to be perfect, as partition quality is also influenced by factors beyond spectral geometry.

3.3

Diagnostic of Controlled Synthetic Graphs

To understand what determines the geometry of spectral embeddings, we study controlled synthetic (hyper)graph families. The goal is to isolate the effects of graph structure and Laplacian design on the ray structure observed in the Titan23 benchmarks. Controlled synthetic (hyper)graphs. We construct four graph families and their hypergraph counterparts to represent distinct connectivity patterns: random graphs with no global organization, mesh graphs with local geometric connectivity, modular graphs with community structure, and hierarchical graphs with multiscale organization. All instances contain 10,000 vertices. The graph families are generated using global random edges, local grid edges, an eight-block stochastic block model with 98% within-block and 2% cross-block edges, and an 8-ary recursive partition tree with leaf size at most 16, respectively. The corresponding hypergraphs preserve the same structural patterns through analogous hyperedge sampling. Hyperedge sizes are sampled uniformly from {2, . . . , 6}, yielding an average size of approximately 4 pins, consistent with the Titan23 benchmarks. To enable fair comparisons, we evaluate three average vertex degrees, 𝑑¯ ∈ {1.25, 5, 20}, over ten random seeds. For graphs, 𝑑¯ = 2|𝐸 | |𝑉 | , whereas for hypergraphs we use the average vertex incidence Í degree, 𝑑¯ = |𝑉1 | 𝑒 ∈𝐸 |𝑒 |. Main empirical findings. Figure 3 and Table 1 reveal three key observations. First, hypergraphs consistently exhibit stronger ray-like embeddings than their graph counterparts at the same density, particularly for structured families. Second, modular and hierarchical connectivity is an important source of persistent ray structure. Although sparse random graphs may also exhibit ray-like embeddings, this effect largely disappears as density increases. In contrast, modular and hierarchical hypergraphs maintain high ray concentration even at realistic densities,

4

Feedback-Reshaped Embeddings for Hypergraph Partitioning

Figure 1(b) illustrates the FRESHPart workflow. Guided by the geometric analysis in Section 3, we first compute a base embedding from the bipartite Laplacian. Geometry Feedback clusters this embedding into rays and reweights each hyperedge according to the number of rays it spans. Recomputing the Laplacian yields a geometry-guided embedding. CMA-ES projection search on the base and geometry-guided embeddings then produces diverse, highquality candidate partitions. Search Feedback uses their hyperedge cut frequencies together with the ray spans to construct a new set of weights. A further Laplacian solve yields the search-guided embedding for the second round of projection search. Reweighting changes only the embeddings used for search; candidate cuts and balance are evaluated on the original hypergraph. Before each search round, lightweight probes guide the allocation of the CMAES budget across candidate embeddings. The following subsections detail the two feedback signals and budget allocation.

4.1

Geometry Feedback

Motivated by the positive correlation between ray concentration and partitioning quality, FRESHPart reshapes the spectral geometry by emphasizing hyperedges that reinforce ray structure while suppressing those that blur it. Specifically, it first clusters the base embedding into rays using spherical 𝐾-means described in Section 3, and then counts the number of distinct rays 𝑅(𝑒) spanned by each hyperedge 𝑒 ∈ 𝐸. A simple monotonic cross-ray factor 𝑤𝑔 (𝑒) = 𝑏 (𝑒) 𝑅(𝑒) −𝛽 is adopted, as visualized in Figure 4. The term 𝑅(𝑒) −𝛽 suppresses hyperedges spanning multiple rays, as they tend to blur the ray geometry. Conversely, 𝑏 (𝑒) = 𝜌 > 1 if all vertices of 𝑒 lie on the same ray, and 𝑏 (𝑒) = 1 otherwise, providing a mild boost to ray-consistent hyperedges. We use 𝛽 = 1.0 and 𝜌 = 1.2. The cross-ray factor 𝑤𝑔 (𝑒) is mean-normalized for numerical stability. The final Geometry Feedback weight is then obtained by multiplying the normalized cross-ray factor with the standard bipartite normalization 𝑤 (𝑒)/|𝑒 |. Overall, the reweighting strengthens compact, ray-consistent hyperedges while suppressing cross-ray hyperedges, producing spectral embeddings with sharper ray geometry for projection-based search.

1.2

b(e) = 1.2

1.0

=1

0.8 0.6 0.4 0.2 1

2 3 4 5 6 7 8 9 10 11 12 R(e): number of rays touched by hyperedge e

Figure 4: Cross-ray factor.

4.2

cut-history factor ws(e)

suggesting that the observed geometry arises from coherent graph structure rather than sparsity alone. Third, the choice of Laplacian operator significantly influences embedding geometry. The bipartite Laplacian consistently preserves stronger ray structure than the clique-expansion Laplacian, consistent with the superior performance of projection-based partitioning under the bipartite formulation reported in [19]. Finally, we investigate the effect of hyperedge weighting by replacing the standard bipartite normalization, 𝑤 (𝑒)/|𝑒 |, with the generalized weighting scheme 𝑤 (𝑒)/|𝑒 |𝛼 , where 𝛼 ∈ {0, 0.5, 0.6, 1, 1.5, 2}. As shown in Table 2, moderate normalization strengthens the ray geometry, whereas overly aggressive normalization weakens it. This demonstrates that hyperedge reweighting provides an effective mechanism for influencing spectral geometry and motivates the feedback strategies introduced in the next section.

Rongjian Liang, Zhuo Feng, and Brucek Khailany Cross-ray factor b(e) R(e)

ASPDAC ’27, January 25–28, 2027, Tokyo, Japan

7 6 5 4 3 2 1 0 0.0

high-R edge: exp[ (f(e) low-R edge

f)]

f = 0.5

high-f but low-R edges kept neutral: w = 1 high-f and high-R edges are downweighted

0.2

0.4 0.6 Cut frequency f(e)

0.8

1.0

Figure 5: Cut-history factor.

Search Feedback

While Geometry Feedback relies solely on the spectral embedding, Search Feedback closes the optimization loop by allowing the partitioning result to reshape the next embedding. Instead of relying on a single partition solution, FRESHPart collects multiple diverse high-quality partitions. Hyperedges that are consistently preserved across these solutions likely represent stable connectivity, whereas those that repeatedly appear on cut boundaries reveal recurring separation regions. FRESHPart leverages this information to reweight hyperedges and construct a refined embedding that is better aligned with the partitioning objective. Let S = {𝑠 1, . . . , 𝑠𝑚 } denote the set of candidate bipartitions returned by the first round of projection search. To avoid collecting nearly identical solutions, we iteratively select the best partitions while enforcing a minimum Hamming distance between them, ensuring that S captures diverse high-quality cuts. We then define the cut frequency of a hyperedge 𝑒 as 𝑚 1 ∑︁ 1{𝑒 is cut by 𝑠𝑖 }, 𝑓 (𝑒) = 𝑚 𝑖=1 which measures how frequently 𝑒 appears on the boundaries of promising partitions. Based on the cut frequency and the ray span 𝑅(𝑒) computed from the base embedding, FRESHPart computes the cut-history factor ( 1, 𝑓 (𝑒) ≥ 𝜏 𝑓 and 𝑅(𝑒) < 𝜏𝜎 ,  𝑤𝑠 (𝑒) =
exp −𝛼 𝑓 (𝑒) − 12 , otherwise, followed by mean normalization and clipping for numerical stability. The final Search Feedback weight is the multiplication of the cuthistory factor and the standard bipartite normalization. As depicted in Figure 5, this rule strengthens hyperedges that are consistently preserved, encouraging their incident vertices to remain compact in the refined embedding. Hyperedges that are both frequently cut and span many rays are instead downweighted, as they are more likely to blur the embedding and interfere with high-quality partitions. In contrast, frequently cut hyperedges that remain geometrically compact are kept at neutral weight, since they may correspond to meaningful local boundaries rather than noisy global constraints. In our implementation, we set 𝛼 = 4, 𝜏 𝑓 = 0.5, and 𝜏𝜎 to the median ray span among high-frequency hyperedges, and clip the normalized weights to [0.2, 5.0]. Together with Geometry Feedback, Search Feedback enables FRESHPart to iteratively reshape the spectral embedding using both its geometric structure and information revealed by the partition search.

4.3

Adaptive Search Budget Allocation

FRESHPart adaptively allocates the CMA-ES search budget across candidate embeddings using inexpensive probe searches, improving runtime efficiency while maintaining partition quality.

FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning

For each Laplacian solve shown in Figure 1(b), we compute the first 36 nontrivial eigenvectors and generate four candidate embeddings by retaining the first 8, 16, 24, and 36 dimensions, respectively. These embeddings provide multiple search spaces with different spectral resolutions, which we empirically find helps projection search escape local optima. Before each round of CMA-ES search, FRESHPart performs a lightweight probe search to estimate the potential of each embedding. For every candidate embedding 𝑋 𝑗 , we evaluate a small set of random projection directions and record the best cut-and-balance 𝑞𝑗 objective value 𝑞 𝑗 . Let 𝑞 min = min 𝑗 𝑞 𝑗 , and 𝜌 𝑗 = 𝑞min , where a smaller 𝜌 𝑗 indicates a more promising embedding. For the base and Geometry Feedback embeddings, candidates with 𝜌 𝑗 ≤ 1.3 receive the full CMA-ES budget, those with 1.3 < 𝜌 𝑗 ≤ 2.0 receive a reduced budget, and the remaining candidates are discarded. Because Search Feedback uses partitions from the first search round, we instead compare its probe result with the best solution from that round. In our implementation, a full budget consists of five CMA-ES restarts, whereas a reduced budget uses at most three restarts. Each restart runs for at most 60 iterations with a population size of 2000, and terminates early if no improvement is observed for 5 consecutive iterations. This adaptive policy concentrates computation on the most promising embeddings.

4.4

Runtime Complexity

HySpecPro [19] establishes that both spectral embedding construction and CMA-ES-based projection search scale linearly with the total hyperedge degree (TotalDeg), yielding an overall runtime of 𝑂 (TotalDeg) when the embedding dimension, CMA-ES population size, and optimization iterations are treated as constants. Compared with HySpecPro, FRESHPart introduces two additional feedback stages. Geometry Feedback clusters the spectral embeddings using spherical 𝐾-means, computes the ray span of each hyperedge, and updates the hyperedge weights. Search Feedback computes hyperedge cut frequencies from a small set of high-quality partition solutions and performs another linear-time hyperedge reweighting pass. These operations require only linear passes over the embedding vectors and hyperedge incidences. FRESHPart performs a constant number of Laplacian solves to construct the base, Geometry Feedback, and Search Feedback embeddings. Although the CMA-ES search budget is adaptively allocated across candidate embeddings, the total search budget is bounded by a fixed constant independent of the hypergraph size. Therefore, the additional feedback affects only the constant factor, and the overall runtime of FRESHPart remains 𝑂 (TotalDeg), preserving the linear scalability of HySpecPro.

5

Experimental Results and Analysis

FRESHPart is implemented in Python. Spectral embedding construction is accelerated using CuPy [22]. Projection search uses the CMA-ES library [14], with batched solution evaluation accelerated by the Deep Graph Library [29]. The Geometry and Search Feedback computations are implemented using custom Python code. All experiments are conducted on a server with AMD EPYC 7742 CPUs and an NVIDIA V100 GPU. Our evaluation suite is the 22 Titan23 benchmarks, whose characteristics are shown in Table 4, run at

ASPDAC ’27, January 25–28, 2027, Tokyo, Japan

both the tight (𝜖=2%) and relaxed (𝜖=20%) balance constraints. We compare FRESHPart against the following SOTA partitioners: • hMETIS [15]: a widely used sequential multilevel partitioner; • SpecPart [6]: a refinement method that improves hMETIS using spectral embeddings; • MedPart [18]: a GPU-accelerated multilevel evolutionary differentiable partitioner; • KaHyPar [25]: a high-quality sequential multilevel partitioner with advanced refinement techniques; • SHyPar [24]: an extension of KaHyPar that incorporates spectral information during coarsening; it runs 9 configurations of KaHyPar in parallel; • TritonPart [4]: a leading multi-threaded partitioner; we use its official implementation [5] with default settings; • mtK-min [12]: a multi-threaded KaHyPar configuration (also named mtKaHyPar, 24 threads); we report the best cut and the total runtime over 100 runs; • mtK-mean [12]: the same configuration, reporting average cut size and runtime over 100 runs; • HySpecPro [19]: a leading GPU-accelerated spectral partitioner.

5.1

Partition Quality and Runtime

Table 3 summarizes the bi-partitioning cut sizes on Titan23. FRESHPart consistently outperforms both the leading multilevel and spectral partitioners, achieving the best reported cut sizes on 12 of the 22 benchmarks at 𝜖 = 20% and 8 of the 22 at 𝜖 = 2%. In terms of runtime, SpecPart reports an approximately 5× runtime overhead over hMETIS [7], while MedPart requires up to two hours on the largest Titan benchmarks [18]. Detailed runtime comparisons among SHyPar, KaHyPar, TritonPart, mtKaHyPar, HySpecPro, and FRESHPart are shown in Figure 6. FRESHPart is substantially faster than SHyPar, achieving more than an orderof-magnitude speedup on large benchmarks. Although FRESHPart is slower than KaHyPar, TritonPart, and mtKaHyPar on small hypergraphs, it consistently outperforms them on the largest benchmarks. Compared with the GPU-accelerated HySpecPro, FRESHPart achieves comparable runtime while consistently delivering higher partition quality. FRESHPart completes every Titan23 benchmark in under 120 s on a single GPU. The runtime breakdown of FRESHPart shows that CMA-ESbased projection search dominates the runtime, accounting for approximately 85% of the total execution time. The three Laplacian solves contribute about 10%, while I/O together with the Geometry and Search Feedback computations account for only about 5%.

5.2

Ablation Studies

What Each Feedback Channel Contributes. As shown in Table 4, both Geometry Feedback and Search Feedback increase the average ray concentration of the spectral embedding, producing embeddings better suited for projection-based partitioning. Correspondingly, Figure 7 shows that Geometry Feedback improves the average cut-size reduction over hMETIS by about 2%, while Search Feedback provides a further 2% improvement. Introducing the Geometry and Search Feedback embeddings increases the runtime by roughly 50% compared with searching only the base embedding. However, the resulting quality gain cannot be attributed simply to additional projection search. As shown in

Runtime (s)

ASPDAC ’27, January 25–28, 2027, Tokyo, Japan 2000 1500 1000 500 300

SHyPar (9 threads)

Rongjian Liang, Zhuo Feng, and Brucek Khailany

KaHyPar (single-thread)

TritonPart (multi-thread)

mtK-min (24 threads)

HySpecPro (GPU)

FRESHPart (GPU)

250 200 150 100 50 0 1 core neuroten reo vision sparcT s

des90AM spherihc olesky mgcmentatioitnonic mesh c b SL se

dart openCV stap qrd

LU23L0U NetworkarcT1 chip2 directritfcoin miner b sp

minrehsolesky bdti denoispearcT2 coregsm switch mes noc s c

Figure 6: Runtime comparison among partitioners. Table 3: Bi-partitioning cut sizes on Titan23. The average improvement is normalized against hMETIS results. FRESHPart

974 974 1137 1099 243 244 245 260 169 169 182 174 379 380 382 389 1061 1061 1061 1061 283 283 282 382 107 107 107 144 586 593 588 590 784 924 846 817 499 560 429 591 371 371 382 380 207 207 208 252 1156 1156 1197 1209 416 416 479 456 1183 1186 1310 1196 1621 1759 1496 2036 651 649 886 673 3602 4012 3426 3614 524 524 528 610 873 874 1043 911 632 646 576 662 1514 1576 1489 1523

1288 1091 380 248 254 177 477 380 1083 1061 756 283 256 128 671 589 1113 809 798 575 509 379 351 210 1792 1157 533 439 1301 1377 2789 1590 935 646 4390 3399 737 536 1196 903 731 506 1582 1651

1032 245 178 371 1061 285 107 582 813 429 373 210 1156 419 1251 1706 646 3298 524 878 498 1518

mtK-mean

mtK-min

TritonPart

KaHyPar

MedPart

1012 1067 252 262 180 176 402 372 1061 1061 285 283 126 114 585 594 807 805 510 635 399 386 215 215 1156 1161 416 516 1244 1319 1827 1714 634 699 3273 3452 525 550 899 1129 574 646 1297 1562

HySpecPro

1066 260 180 402 1061 285 136 614 844 511 399 215 1157 722 1273 5974 699 4070 550 1524 646 1570

SpecPart

hMETIS sparcT1 core neuron stereo vision des90 SLAM spheric cholesky mc segmentation bitonic mesh dart openCV stap qrd minres cholesky bdti denoise sparcT2 core gsm switch mes noc LU230 LU Network sparcT1 chip2 directrf bitcoin miner

SHyPar

Cut Size at 𝜖 = 2%

Benchmark

0 10.99 6.82 12.16 9.95 8.90 4.16 -28.00 9.42 13.09

Impro. % ↑

Table 4: Ray concentration of the base, Geometry Feedback, and Search Feedback embeddings on the Titan23 benchmarks. sparcT1 core 91,976 92,827 92,290 125,305 neuron stereo vision 94,050 127,085 111,221 139,557 des90 SLAM spheric 113,115 142,408 cholesky mc 113,250 144,948 138,295 179,051 segmentation bitonic mesh 192,064 235,328 dart 202,354 223,301 217,453 284,108 openCV stap qrd 240,240 290,123 minres 261,359 320,540 cholesky bdti 266,422 342,688 275,638 356,848 denoise sparcT2 core 300,109 302,663 gsm switch 493,260 507,821 mes noc 547,544 577,664 LU230 574,372 669,477 LU Network 635,456 726,999 sparcT1 chip2 820,886 821,274 directrf 931,275 1,374,742 bitcoin miner 1,089,284 1,448,151 –

mean

Impro. % ↑

903 206 91 358 1061 345 78 483 540 518 295 189 947 224 1245 1407 617 2677 524 783 295 1225

624 270 93 349 1061 281 78 493 549 554 287 181 1024 224 1081 1503 633 2720 528 877 317 1255

631 244 91 345 1061 479 78 506 539 473 275 191 848 220 918 1407 617 2923 524 757 295 1282

873 244 91 380 1061 591 78 493 549 554 287 181 1024 224 1081 1503 633 2720 528 877 317 1255

1016 1064 245 251 91 91 353 382 1061 1061 281 281 80 86 506 588 583 797 451 625 281 364 211 220 861 1245 231 340 1171 1192 1695 1641 623 634 3529 3586 529 526 939 847 295 385 1278 1232

1210 360 103 481 1076 671 148 675 1127 778 490 317 1680 436 1298 2201 860 4238 532 1028 531 1514

682 216 97 345 1061 281 82 489 667 534 276 182 858 284 999 1434 631 3017 542 735 318 1231

589 211 91 345 1061 281 78 483 598 428 275 181 857 226 973 1408 620 2858 524 678 306 1283

0 21.73 20.94 22.53 14.14 18.93 9.62 -17.26 21.48 25.21

Figure 7, allocating a large amount of search budget to the base embedding yields substantially smaller improvements. This indicates that the performance gains primarily arise from progressively refining the spectral embedding through the proposed feedback mechanisms, rather than from increased search effort alone.

0.992 0.953 0.981 0.946 0.955 0.997 0.868 0.921 0.967 0.863 0.983 0.923 0.980 0.886 0.982 0.836 0.864 0.990 0.968 0.930 0.877 0.883

0.968 0.948 0.931 0.921 0.930 0.967 0.878 0.868 0.937 0.936 0.984 0.955 0.934 0.972 0.966 0.990 0.854 0.985 0.956 0.958 0.955 0.956

0.992 0.953 0.981 0.946 0.955 0.997 0.878 0.921 0.992 0.936 0.984 0.955 0.980 0.978 0.982 0.990 0.864 0.990 0.968 0.958 0.972 0.962

0.922

0.934

0.943

0.961

4

8

12

16

24

32

24.31

24.42

25.21

24.83

24.52

23.66

Ray count 𝐾𝑟 Cut-size impr.% ↑

Average cut reduction over hMETIS (%)

1290 270 143 441 1061 667 141 590 603 554 295 189 1024 478 1972 5352 633 3276 528 1029 379 1255

–

0.951 0.918 0.936 0.853 0.879 0.925 0.858 0.857 0.992 0.872 0.948 0.903 0.867 0.978 0.929 0.976 0.826 0.988 0.949 0.952 0.972 0.962

Table 5: Effect of ray-count selection at 𝜖 = 20%. Cut-size improvement is measured relative to hMETIS.

Cut Size at 𝜖 = 20% sparcT1 core neuron stereo vision des90 SLAM spheric cholesky mc segmentation bitonic mesh dart openCV stap qrd minres cholesky bdti denoise sparcT2 core gsm switch mes noc LU230 LU Network sparcT1 chip2 directrf bitcoin miner

|𝐸 | Base Emb. Geo. Emb. Search Emb. max of all

|𝑉 |

Benchmark

26 25 24 23 22 21 20

+Geo+Search +Geo

Base-only 3× search

Base

Feedback-refined embeddings More search on base embedding

60

80

100

120

Average runtime per design (s)

140

Figure 7: Partition quality versus runtime for FRESHPart variants.

The Role of Adaptive Budget Allocation and Early Stopping. Our ablation study shows that disabling adaptive budget allocation and early stopping increases the average runtime by approximately 50 s per design, while yielding virtually no improvement in partition quality. The Impact of Ray Count Selection. The ray count 𝐾𝑟 affects both feedback stages, yet FRESHPart is relatively robust to its choice, as shown in Table 5. Our smooth cross-ray weighting and mean normalization may help limit sensitivity to 𝐾𝑟 . Transfer to ISPD98 Benchmarks [3]. FRESHPart outperforms TritonPart by 4.69% at 𝜖 = 2% and 7.06% at 𝜖 = 10%, respectively. Against HySpecPro, FRESHPart reduces mean cut by 6.00% and

FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning

6.19%, wins all 18 cases at both balance limits. FRESHPart is also faster than both methods. These results demonstrate that FRESHPart’s quality and efficiency transfer beyond Titan23.

6

Conclusion

This paper revisits spectral hypergraph partitioning from the perspective of spectral embedding geometry. We show that the effectiveness of projection-based partitioning is closely tied to a ray-like embedding structure, and that graph structure, Laplacian design, and hyperedge reweighting all influence this geometry. Motivated by these insights, we propose FRESHPart, a feedbackdriven spectral partitioning framework that refines spectral embeddings through Geometry Feedback and Search Feedback. Experiments on the Titan23 benchmark suite demonstrate that FRESHPart achieves SOTA partition quality while preserving runtime efficiency. We hope the proposed geometric perspective and feedback-driven framework will inspire further research on scalable embeddingaware hypergraph partitioning.

References [1] Charles J Alpert, Andrew B Kahng, and So-Zen Yao. 1999. Spectral partitioning with multiple eigenvectors. Discrete Applied Mathematics (DAM) 90, 1-3 (1999), 3–26. [2] Alain Bretto. 2013. Hypergraph theory - An introduction. Mathematical Engineering (Eng. Math.) 1 (2013). [3] Ismail Bustany, Grigor Gasparyan, Andrew B Kahng, Ioannis Koutis, Bodhisatta Pramanik, and Zhiang Wang. 2022. ISPD98 Hypergraph Benchmarks. https://github.com/TILOS-AI-Institute/HypergraphPartitioning (2022). [4] Ismail Bustany, Grigor Gasparyan, Andrew B Kahng, Ioannis Koutis, Bodhisatta Pramanik, and Zhiang Wang. 2023. An open-source constraints-driven general partitioning multi-tool for VLSI physical design. In Proceedings of International Conference on Computer Aided Design (ICCAD). 1–9. [5] Ismail Bustany, Grigor Gasparyan, Andrew B Kahng, Ioannis Koutis, Bodhisatta Pramanik, and Zhiang Wang. 2023. TritonPart Official Implementation. https: //github.com/ABKGroup/TritonPart [6] Ismail Bustany, Andrew B Kahng, Ioannis Koutis, Bodhisatta Pramanik, and Zhiang Wang. 2022. SpecPart: A supervised spectral framework for hypergraph partitioning solution improvement. In Proceedings of International Conference on Computer-Aided Design (ICCAD). 1–9. [7] Ismail Bustany, Andrew B Kahng, Ioannis Koutis, Bodhisatta Pramanik, and Zhiang Wang. 2023. K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems (TCAD) 43, 4 (2023), 1232–1245. [8] T-H Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. 2018. Spectral properties of hypergraph laplacian and approximation algorithms. Journal of the ACM (JACM) 65, 3 (2018), 1–48. [9] Magi Chen and Ting-Chi Wang. 2026. GenPart 2.0: Enhanced hypergraph partitioning with vertex weight handling using a generative model. ACM Transactions on Design Automation of Electronic Systems (TODAES) 31, 3 (2026), 1–24. [10] Chris HQ Ding, Xiaofeng He, Hongyuan Zha, Ming Gu, and Horst D Simon. 2001. A min-max cut algorithm for graph partitioning and data clustering. In Proceedings of International Conference on Data Mining (ICDM). 107–114. [11] Miroslav Fiedler. 1975. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical Journal (Czechoslov. Math. J.) 25, 4 (1975), 619–633. [12] Lars Gottesbüren, Tobias Heuer, Nikolai Maas, Peter Sanders, and Sebastian Schlag. 2024. Scalable high-quality hypergraph partitioning. ACM Transactions on Algorithms (TALG) 20, 1 (2024), 1–54. [13] Lars Hagen and Andrew B Kahng. 1992. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) 11, 9 (1992), 1074–1085. [14] Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. 2019. CMA-ES/pycma on Github. https://doi.org/10.5281/zenodo.2559634 [15] George Karypis. 1998. hMETIS 1.5: A hypergraph partitioning package. http://www.cs.umn.edu/metis (1998). [16] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. 1997. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of Design Automation Conference (DAC). 526–529. [17] Wan Luan Lee, Dian-Lun Lin, Cheng-Hsiang Chiu, Ulf Schlichtmann, and TsungWei Huang. 2025. HyperG: Multilevel GPU-Accelerated k-way hypergraph partitioner. In Proceedings of Asia and South Pacific Design Automation Conference

ASPDAC ’27, January 25–28, 2027, Tokyo, Japan

(ASP-DAC). 1031–1040. [18] Rongjian Liang, Anthony Agnesina, and Haoxing Ren. 2024. Medpart: A multilevel evolutionary differentiable hypergraph partitioner. In Proceedings of International Symposium on Physical Design (ISPD). 3–11. [19] Rongjian Liang, Zhuo Feng, and Haoxing Ren. 2026. HySpecPro: Scalable Hypergraph Partitioning via Spectral Projection Optimization. arXiv preprint arXiv:2607.00055 (2026). [20] Yang Liu, Yonghua Zhao, Zexin Wang, Rongfeng Huang, Dingye Zhang, and Xinyin Zhang. 2024. Efficient Implementation of the LOBPCG Algorithm on a CPU-GPU Cluster. In Proceedings of International Conference on Network and Parallel Computing (NPC). Springer, 65–76. [21] Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Vol. 14. [22] Royud Nishino and Shohei Hido Crissman Loomis. 2017. Cupy: A numpycompatible library for nvidia gpu calculations. Proceedings of Confernce on Neural Information Processing Systems (NeurIPS) 151, 7 (2017). [23] Alex Pothen, Horst D Simon, and Kang-Pu Liou. 1990. Partitioning sparse matrices with eigenvectors of graphs. SIAM journal on matrix analysis and applications (SIMAX) 11, 3 (1990), 430–452. [24] Hamed Sajadinia, Ali Aghdaei, and Zhuo Feng. 2025. SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD) (2025). [25] Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, and Christian Schulz. 2016. K-way hypergraph partitioning via n-level recursive bisection. In Proceedings of Workshop on Algorithm Engineering and Experiments (ALENEX). 53–67. [26] Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) 22, 8 (2000), 888–905. [27] Daniel A Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of Symposium on Theory of Computing (STOC). 81–90. [28] Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing (Stat. Comput.) 17, 4 (2007), 395–416. [29] Minjie Yu Wang. 2019. Deep graph library: Towards efficient and scalable deep learning on graphs. In Proceedings of International Conference on Learning Representations Workshop on Representation Learning on Graphs and Manifolds (ICLR). [30] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. 2006. Learning with hypergraphs: Clustering, classification, and embedding. In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), Vol. 19. [31] Jason Y Zien, Martine DF Schlag, and Pak K Chan. 1999. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems (TCAD) 18, 9 (1999), 1389–1399.

Related documents

• More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning#1490757
• More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning#1482965
• Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment#798274
• Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment#796861
• GPU-Accelerated Hypergraph Partitioning and Placement to Map SNNs on Neuromorphic Hardware#667990