Hypergraph partitioning is an important problem in machine learning, computer
vision and network analytics. A widely used method for hypergraph partitioning
relies on minimizing a normalized sum of the costs of partitioning hyperedges
across clusters. Algorithmic solutions based on this approach assume that
different partitions of a hyperedge incur the same cost. However, this
assumption fails to leverage the fact that different subsets of vertices within
the same hyperedge may have different structural importance. We hence propose a
new hypergraph clustering technique, termed inhomogeneous hypergraph
partitioning, which assigns different costs to different hyperedge cuts. We
prove that inhomogeneous partitioning produces a quadratic approximation to the
optimal solution if the inhomogeneous costs satisfy submodularity constraints.
Moreover, we demonstrate that inhomogenous partitioning offers significant
performance improvements in applications such as structure learning of
rankings, subspace segmentation and motif clustering.

提出了一种新的超图聚类技术，称为不均匀超图划分，其将不同的代价分配给不同的超图切割，证明了如果不均匀代价满足次模性约束，则不均匀划分产生了最优解的二次近似，并证明了在许多应用中可以获得显着的性能改进。