FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning

Rongjian Liang; Zhuo Feng; Brucek Khailany

cs.LGNov 3, 2026

FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning

Authors: Rongjian Liang, Zhuo Feng, Brucek Khailany

Organizations: NVIDIA, Austin, TX, USA · Stevens Inst of Tech & NVIDIA, Hoboken, New Jersey, USA

Abstract

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 projection-based 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.

Figures & tables

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

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

Figure 3. PCA visualization of spectral embeddings for synthetic graph and hypergraph families at average vertex degree $\bar{d}=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	$\bar{d}\!\approx\!1.25$	$\bar{d}\!\approx\!5$	$\bar{d}\!\approx\!20$
random graph	0.802	0.754	0.567
random hyper (bi.)	0.833	0.806	0.624
random hyper (cl.)	0.866	0.751	0.566
mesh graph	0.759	0.826	0.826
mesh hyper (bi.)	0.814	0.825	0.825
mesh hyper (cl.)	0.830	0.823	0.826

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.

$\bar{d}$	$\alpha{=}0$	$0.5$	$0.6$	$1.0$	$1.5$	$2.0$
1.25	0.860	0.883	0.893	0.836	0.861	0.873
5	0.943	0.954	0.954	0.952	0.918	0.927
20	0.864	0.883	0.884	0.925	0.914	0.892

Table 2. Effect of hyperedge weighting

|e|^{-\alpha}

on the ray concentration of modular hypergraphs under the bipartite Laplacian.

Benchmark	Cut Size at $\epsilon=2\%$
Benchmark	hMETIS	SpecPart	MedPart	SHyPar	KaHyPar	TritonPart	mtK-min	mtK-mean	HySpecPro	FRESHPart
sparcT1 core	1066	1012	1067	974	974	1137	1099	1288	1091	1032
neuron	260	252	262	243	244	245	260	380	248	245
stereo vision	180	180	176	169	169	182	174	254	177	178
des90	402	402	372	379	380	382	389	477	380	371
SLAM spheric	1061	1061	1061	1061	1061	1061	1061	1083	1061	1061

Table 3. Bi-partitioning cut sizes on Titan23. The average improvement is normalized against hMETIS results.

Benchmark	$\|V\|$	$\|E\|$	Base Emb.	Geo. Emb.	Search Emb.	max of all
sparcT1 core	91,976	92,827	0.951	0.992	0.968	0.992
neuron	92,290	125,305	0.918	0.953	0.948	0.953
stereo vision	94,050	127,085	0.936	0.981	0.931	0.981
des90	111,221	139,557	0.853	0.946	0.921	0.946
SLAM spheric	113,115	142,408	0.879	0.955	0.930	0.955
cholesky mc	113,250	144,948	0.925	0.997	0.967	0.997

Table 4. Ray concentration of the base, Geometry Feedback, and Search Feedback embeddings on the Titan23 benchmarks.

Ray count $K_{r}$	$4$	$8$	$12$	$16$	$24$	$32$
Cut-size impr.% $\uparrow$	24.31	24.42	25.21	24.83	24.52	23.66

Table 5. Effect of ray-count selection at

\epsilon=20\%

. Cut-size improvement is measured relative to hMETIS.

Figure 6. Runtime comparison among partitioners.

Figure 7. Partition quality versus runtime for FRESHPart variants.

Graph Partitioning

See all 14 papers

EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
Apr 1, 2026Nikolai Merkel, Ruben Mayer, Volker Markl +1Graph Partitioning Graph Neural Networks
Technical University of Munich (TUM) · University of Bayreuth · TU Berlin, BIFOLD, DFKI +1
Neural Acceleration for Graph Partitioning
May 18, 2026Joshua Dennis Booth, Vishvam PatelGraph Partitioning Graph Clustering
Department of Computer Science University of Alabama in Huntsville Huntsville AL, USA
HyperFuse: Fast Self-Supervised Node Embeddings for Attributed Hypergraphs
Oct 2, 2026Megha P, Harshit Kumar, Srajan Agarwal +3Hypergraph Learning Hypergraph Neural Networks
School of Data Science, Indian Institute of Science Education and Research Thiruvananthapuram, Thiruvananthapuram, 695551, Kerala, India. · Department of Mathematics and Statistics, Indian Institute of Science Education and Research Kolkata, Mohanpur, 741246, West Bengal, India. · Institute of Computer Science, University of Rostock, Rostock, 18051, Germany. +1

Apr 1, 2026J/K move · Enter open · S save

EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training

Nikolai Merkel, Ruben Mayer, Volker Markl, Hans-Arno Jacobsen

Technical University of Munich (TUM) · University of Bayreuth · TU Berlin, BIFOLD, DFKI+1

Graph Partitioning Graph Neural Networks Distributed Training Graph Clustering

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) are widely used for learning on graph-structured data, but scaling GNN training to massive graphs remains challenging. To enable scalable distributed training, graphs are divided into smaller partitions that are distributed across multiple machines such that inter-machine communication is minimized and computational load is balanced. In practice, existing partitioning approaches face a fundamental trade-off between partitioning overhead and partitioning quality. We propose EmbedPart, an embedding-driven partitioning approach that achieves both speed and quality. Instead of operating directly on irregular graph structures, EmbedPart leverages node embeddings produced during the actual GNN training workload and clusters these dense embeddings to derive a partitioning. EmbedPart achieves more than 100x speedup over Metis while maintaining competitive partitioning quality and accelerating distributed GNN training. Moreover, EmbedPart naturally supports graph updates and fast repartitioning, and can be applied to graph reordering to improve data locality and accelerate single-machine GNN training. By shifting partitioning from irregular graph structures to dense embeddings, EmbedPart enables scalable and high-quality graph data optimization.

Abstract

Graph Partitioning

Explore similar work

EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training

Neural Acceleration for Graph Partitioning

HyperFuse: Fast Self-Supervised Node Embeddings for Attributed Hypergraphs