Graph clustering objective functions with tunable resolution parameters make it possible to detect different types of clustering structure in the same graph. These objectives also provide a unifying view of other non-parametric objectives, which often can be captured as special cases. Previous research has largely focused on parametric objectives for standard graphs, in which all nodes are of the same type, and edges model pairwise relationships. In our work, we introduced parameterized objective functions and approximation algorithms specifically for clustering bipartite graphs and hypergraphs, based on correlation clustering. This enables us to develop principled approaches for clustering datasets with different node types (bipartite graphs) or multiway relationships (hypergraphs). Our hypergraph objective is related to higher-order notions of modularity and normalized cut , and is amenable to approximation algorithms via hypergraph expansion techniques. Our bipartite objective generalizes standard  bipartite correlation clustering, and in a certain parameter regime is equivalent to bicluster deletion, i. e., removing a minimum number of edges to separate a bipartite graph into disjoint bicliques. The problem in general is NP-hard, but we show that in a certain parameter regime it is equivalent to a bipartite matching problem , meaning that it is polynomial timesolvable in this regime . For other regimes, we provide approximation guarantees based on LP-rounding. Our results include the first constant factor approximation algorithm for bicluster deletion . We illustrate the flexibility of our framework in several experiments . This includes clustering a food web and an email network based on higher-order motif structure, detecting clusters of retail products in  product review hypergraph, and evaluating our algorithms across a range of parameter settings on several real world bipartite graphs .
Motivated by applications in community detection and dense subgraph discovery, we consider new clustering objectives in hypergraphs and bipartite graphs. These objectives are parameterized by one or more resolution parameters in order to enable diverse knowledge discovery in complex data. For both hypergraph and bipartite objectives, we identify parameter regimes that are equivalent to existing objectives and share their (polynomial-time) approximation algorithms. We first show that our parameterized hypergraph correlation clustering objective is related to higher-order notions of normalized cut and modularity in hypergraphs. It is further amenable to approximation algorithms via hyperedge expansion techniques. Our parameterized bipartite correlation clustering objective generalizes standard unweighted bipartite correlation clustering, as well as bicluster deletion. For a certain choice of parameters it is also related to our hypergraph objective. Although in general it is NP-hard, we highlight a parameter regime for the bipartite objective where the problem reduces to the bipartite matching problem and thus can be solved in polynomial time . For other parameter settings, we present approximation algorithms using linear program rounding techniques. These results allow us to introduce the first constant-factor approximation for bicluster deletion , the task of removing a minimum number of edges to partition a bipartite graph into disjoint bi-cliques. In several experimental results, we highlight the flexibility of our framework and the diversity of results that can be obtained in different parameter settings . This includes clustering bipartite graphs across a range of parameters, detecting motif-rich clusters in an email network and a food web, and forming clusters of retail products in a product review hypergraph, that are highly correlated with known product categories .
R
Graph clustering objective functions with tunable resolution parameters make it possible to detect different types of clustering structure in the same graph. These objectives also provide a unifying view of other non-parametric
Motivated by applications in community detection and dense subgraph discovery, we consider new clustering objectives in hypergraphs and bipartite graphs. These objectives are parameterized by one or more resolution parameters in order to enable diverse knowledge discovery in complex data. For both hypergraph and bipartite
R
which often can be captured as special cases. Previous research has largely focused on parametric objectives for standard graphs, in which all nodes are of the same type, and edges model pairwise relationships. In our work, we introduced parameterized objective functions and approximation algorithms specifically for clustering bipartite graphs and hypergraphs, based on correlation clustering. This enables us to develop principled approaches for clustering datasets with different node types (bipartite graphs) or multiway relationships (hypergraphs). Our hypergraph
we identify parameter regimes that are equivalent to existing objectives and share their (polynomial-time) approximation algorithms. We first show that our parameterized hypergraph correlation clustering
R
modularity and normalized cut , and is
normalized cut and modularity in hypergraphs. It is further
R
hypergraph
hyperedge
R
bipartite
parameterized bipartite correlation clustering
A
unweighted
R
and in a certain parameter regime is equivalent to bicluster deletion, i. e., removing a minimum number of edges to separate a bipartite graph into disjoint bicliques. The problem in general
as well as bicluster deletion. For a certain choice of parameters it is also related to our hypergraph objective. Although in general it
R
but we show that in a certain parameter regime it is equivalent to a
we highlight a parameter regime for the bipartite objective where the problem reduces to the
R
, meaning that it is polynomial timesolvable in this regime
and thus can be solved in polynomial time
R
regimes, we provide approximation guarantees based on LP-rounding. Our results include the first constant factor approximation algorithm
parameter settings, we present approximation algorithms using linear program rounding techniques. These results allow us to introduce the first constant-factor approximation
R
. We illustrate
, the task of removing a minimum number of edges to partition a bipartite graph into disjoint bi-cliques. In several experimental results, we highlight
R
in several experiments
and the diversity of results that can be obtained in different parameter settings
R
a food web and
bipartite graphs across a range of parameters, detecting motif-rich clusters in
R
based on higher-order motif structure, detecting
and a food web, and forming
A
a
R
and evaluating our algorithms across a range of parameter settings on several real world bipartite graphs
that are highly correlated with known product categories