Maximum strong independent sets improve hypergraph clustering methods
Maximum Strong Independent Sets in Hypergraphs: Reductions, Bounds, and Greedy Certificates
Machine Learning
Summary
The paper looks at how to find the largest set of points in a network where each group of connected points contains at most one from the set. This problem is important when you want local information without assuming it spreads globally, like when deduplicating data from overlapping groups. The authors create tools and mathematical rules to simplify, estimate, and solve this problem with a step-by-step method that checks the quality of its solutions. They also describe when and how their method works best and provide examples to show the differences in how solutions can be certified.
What this means in practice
- •For data engineers: Identify largest consistent subsets in overlapping data clusters to enhance deduplication accuracy without global merges.
- •For database system developers: Improve query performance by applying incidence-local optimization for clustering tasks where linkage constraints are partial or local.
Authors
Yingquan, Wu, Jason Cong
Abstract
We study the maximum strong independent set problem in a finite hypergraph: find the largest vertex set that intersects every hyperedge in at most one vertex. This objective arises whenever each observed block is a local incompatibility constraint but transitive closure across overlapping blocks is not justified. A motivating example is multi-band LSH-MinHash deduplication, where each collision bucket gives local evidence, while connected-component contraction can impose spurious global equivalences. The paper develops an incidence-structural toolkit for this problem. We prove exact reductions for dominance, incidence twins, and weight-1 blocks; derive closed-form and low-weight upper bounds; introduce puncturing and covering certificates that sharpen those bounds; and analyze a layered greedy clustering algorithm driven by block weights and residual incidence. The algorithmic analysis includes feasibility, maximality, conditional optimality, a layered witness-matching upper bound, and incidence-local complexity bounds. The results give correctness, termination, fixed-point, and optimality certificates for broad incidence families, together with examples showing when different certificates separate or coincide.