Balanced hypergraph partitioning is an essential task for massive hypergraph analysis in distributed computing. Existing methods usually use the entire hypergraph to obtain structural information before the assignment process. However, many applications require online partitioning, motivating the development of streaming algorithms. In the streaming order, vertices are assigned in real time and their ownership does not change. Therefore, partitioning the streamed vertices under the balance constraint is challenging. In this paper, we propose a method for balanced hypergraph partitioning in the streaming mode. By defining a modularity function under the Erdos-Renyi random hypergraph model, we build the Erdos-Renyi Hypergraph Modularity Greedy. We approximate the hypergraph as a uniform hypergraph and optimize the modularity function with lower computational complexity. Compared with other modularity functions, our modularity function is more suitable for streaming algorithms. Finally, we design a data structure to reduce the execution time for finding the block with minimum capacity. Overall, our method achieves the state-of-the-art performance when evaluated with the cut-net metric.
Figures & tables
k
ε
Method
newblue1
newblue2
newblue3
newblue4
newblue5
newblue6
newblue7
adaptec5
128
0.02
MinMax
221204
293945
314900
418659
799410
828412
1618596
542646
MinMax-N2P
221630
294037
315602
417448
791263
821130
1604143
536567
LDG
222678
293435
314705
424297
819067
839793
1665980
545792
FREIGHT
174359
244416
270071
351898
624033
687946
1337701
452261
ERHMG (ours)
164478
234456
257072
336125
578171
649263
1238699
420540
128
0.03
MinMax
219520
291042
311635
416182
795729
824653
1615429
538928
Table 1. Comparison of the cut-net metric for different methods evaluated on the ISPD2006 Benchmark.
k
ε
Method
newblue1
newblue2
newblue3
newblue4
newblue5
newblue6
newblue7
adaptec5
128
0.02
MinMax-N2P
0.26746
0.372049
0.41452
0.557474
1.14421
1.47229
2.63953
0.771279
FREIGHT
0.182589
0.252773
0.280897
0.394436
0.815751
0.920045
2.0712
0.547697
ERHMG (ours)
0.17449
0.246399
0.277025
0.375782
0.798038
0.91843
2.06382
0.527916
128
0.03
MinMax-N2P
0.264269
0.372244
0.404298
0.556723
1.25123
1.2563
2.66163
0.761262
FREIGHT
0.176584
0.254742
0.283716
0.388509
0.92126
0.91199
2.06574
0.55499
ERHMG (ours)
0.172555
0.251349
0.271746
0.376282
0.871494
0.900867
1.97415
0.534898
Table 2. The running time (second) for streaming algorithms with different data structures executed on ISPD2006 Benchmark.
Name
∣V∣
∣E∣
Average hyperedge size
Average vertex degree
newblue1
330474
329688
3.5489
3.5405
newblue2
441509
452200
3.6058
3.6931
newblue3
494010
530830
3.3139
3.5609
newblue4
646132
629778
3.731
3.6366
newblue5
1233057
1249244
3.7316
3.7805
newblue6
1255038
1274355
3.9183
3.9786
Table 3. Statistics of 8 hypergraphs in ISPD2006 Benchmark.
Method
k=128
k=256
ε=0.02
ε=0.03
ε=0.02
ε=0.03
MinMax
375201
373746
382500
378732
MinMax-N2P
374944
373447
382322
378720
LDG
383172
383172
384946
384946
FREIGHT
343385
343385
344560
344560
ERHMG (ours)
339084
337818
339850
338575
Table 4. Average cut-net metric for different methods evaluated on the MLCAD2023 Benchmark with 140 hypergraphs.
k
ε
MinMax-N2P
FREIGHT
ERHMG
128
0.02
0.557854
0.390243
0.384195
128
0.03
0.562774
0.393786
0.385878
256
0.02
0.579528
0.391928
0.384821
256
0.03
0.581045
0.394432
0.386922
Table 5. Average running time (second) for streaming algorithms with different data structures executed on MLCAD2023 Benchmark (140 hypergraphs).
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.
Rongjian Liang, Zhuo Feng, Brucek Khailany
NVIDIA, Austin, TX, USA · Stevens Inst of Tech & NVIDIA, Hoboken, New Jersey, USA
We study the community detection problem in the non-uniform hypergraph stochastic block model (HSBM), where hyperedges of varying sizes coexist. This setting captures higher-order and multi-view interactions and raises a fundamental question: can multiple uniform hypergraph layers below the detection threshold be combined to enable weak recovery? We answer this question by establishing a Kesten--Stigum-type bound for weak recovery in a general class of non-uniform HSBMs with r blocks, generated according to multiple symmetric probability tensors. In the case r=2, we show that weak recovery is possible whenever the sum of the signal-to-noise ratios across all uniform hypergraph layers exceeds one, thereby confirming the positive part of a conjecture in (Chodrow et al., 2023). Moreover, we provide a polynomial-time spectral algorithm that achieves this threshold via an optimally weighted non-backtracking operator. For the unweighted non-backtracking matrix, our spectral method attains a different algorithmic threshold, also conjectured in (Chodrow et al., 2023). Our approach develops a spectral theory for weighted non-backtracking operators on non-uniform hypergraphs, including a precise characterization of outlier eigenvalues and eigenvector overlaps. We introduce a novel Ihara--Bass formula tailored to weighted non-uniform hypergraphs, which yields an efficient low-dimensional representation and leads to a provable spectral reconstruction algorithm. Taken together, these results provide a principled and computationally efficient approach to clustering in non-uniform hypergraphs, and highlight the role of optimal weighting in aggregating heterogeneous higher-order interactions.
Manuel Fernandez, Ludovic Stephan, Yizhe Zhu
Department of Mathematics, University of Southern California · Univ Rennes, Ensai, CNRS, CREST-UMR 9194, F-35000 Rennes, France
We study various graph partitioning tasks subject to general demands. In Graph Partitioning with Demands (GPD), the goal is to delete minimum cost supply edge set so that each remaining component contains at most a prescribed fraction of the total demand. In the hierarchical analogue of this problem, Hierarchical Clustering with Demands (HCD), the goal is to build a hierarchy of clusters, charging each supply edge by the demand in the smallest cluster containing its endpoints. Our main general-graph results are approximation algorithms for GPD and HCD. For every fixed 0<ρ<η<1, we give a polynomial-time bi-criteria algorithm for GPD whose components have demand at most η⋅W and cost at most Oρ,η(logn) times the optimum cost for threshold~ρ. This procedure can then be applied recursively to obtain an O(logn)-approximation for HCD. The algorithm for GPD itself uses a crucial subproblem called Generalized Conductance (GC), a new generalization of the Sparsest Cut. On supply trees, we show that GC can be solved exactly in polynomial time. We also give bi-criteria algorithms for GPD based on anchored-LP rounding and separator recursion, as well as a single-criterion (4+ε)-approximation in nO(1/ρ) time. Moreover, through previous reduction, these GPD algorithms yield a e−14e-approximation for HCD on trees. We also prove that HCD and GPD and GC are SSEH-hard to approximate within any constant factor. On trees, assuming the Unique Games Conjecture (UGC), GPD is hard to approximate within a factor of 2−ε by reduction from Vertex Cover, while HCD is hard to approximate within a factor of 1.0748, by reduction from Min-Sum Vertex Cover.