The Taub Faculty of Computer Science Events and Talks

We introduce a new family of clustering problems, which we denote by Hyper Correlation Clustering, that takes into account higher-order structures. Our new family captures multiple classic graph cut problems, e.g., Min s-t Cut, Multiway Cut, and Multicut, in addition to disagreement minimization on general weighted graphs in Correlation Clustering, as well as other studied hypergraph clustering problems.

In Hyper Correlation Clustering we are given a hypergraph H=(V,E) whose every hyperedge e is labeled by + or -, where + (-) indicates similarity (dissimilarity) of vertices in e. Each hyperedge is associated with an agreement function, that depends on its label, which quantifies the agreement of the hyperedge as a function of the number of times it is cut.

The goal is to find a clustering that minimizes the total disagreement of hyperedges. While no reasonable approximation is possible for arbitrary agreement functions, we present a polylogarithmic approximation for general weighted hypergraphs and a natural class of agreement functions.

Our algorithm is based on the combination of a combinatorial greedy approach and an approximation algorithm for a hypergraph cut problem that is closely related to both Sparsest Cut with general demands and Min Ratio Steiner Cut in which: (1) cost is over hyperedges as opposed to edges; and (2) demands are given over large subsets of vertices as opposed to pairs of vertices. We believe this hypergraph cut problem might be of independent interest.