cs.LGJun 14, 2021

Improved Streaming Algorithm for Balanced Hypergraph Partitioning

Authors: Zhicheng Guo

Organizations: School of Artificial Intelligence Xidian University

Abstract

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

Explore similar work

Nov 3, 2026

FRESHPart: Feedback-Reshaped Spectral Embedding for Hypergraph Partitioning

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%ε=2\% and 25.21% at ε=20%ε=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.
Apr 21, 2026

Achieving the Kesten-Stigum bound in the non-uniform hypergraph stochastic block model

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 rr blocks, generated according to multiple symmetric probability tensors. In the case r=2r=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.
Jul 14, 2026

Graph Partitioning with Demands: Generalized Conductance and its Applications

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<ρ<η<10<ρ<η<1, we give a polynomial-time bi-criteria algorithm for GPD whose components have demand at most η⋅Wη\cdot W and cost at most Oρ,η(log⁡n)\mathcal{O}_{ρ,η}(\sqrt{\log n}) times the optimum cost for threshold~ρρ. This procedure can then be applied recursively to obtain an O(log⁡n)\mathcal{O}(\sqrt{\log n})-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+ε)(4+ε)-approximation in nO(1/ρ)n^{O(1/ρ)} time. Moreover, through previous reduction, these GPD algorithms yield a 4ee−1\frac{4e}{e-1}-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−ε2-ε by reduction from Vertex Cover, while HCD is hard to approximate within a factor of 1.07481.0748, by reduction from Min-Sum Vertex Cover.