Parameterized Correlation Clustering in Hypergraphs and 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.
Code (1)
Tasks
ClusteringCommunity DetectionGraph ClusteringSimilar Papers 제목 키워드 기반
HyperSF: Spectral Hypergraph Coarsening via Flow-based Local Clustering
Hypergraphs allow modeling problems with multi-way high-order relationships. However, the computational cost of most existing hypergraph-based algorithms can be heavily dependent upon the input hypergraph sizes. To addre…
Clusteringhypergraph partitioningFinding Bipartite Components in Hypergraphs
Hypergraphs are important objects to model ternary or higher-order relations of objects, and have a number of applications in analysing many complex datasets occurring in practice. In this work we study a new heat diffus…
Convolutional Signal Propagation: A Simple Scalable Algorithm for Hypergraphs
Last decade has seen the emergence of numerous methods for learning on graphs, particularly Graph Neural Networks (GNNs). These methods, however, are often not directly applicable to more complex structures like bipartit…
Node ClassificationRetrievalSubmodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in clustering applications in which higher-or…
ClusteringClustering in graphs and hypergraphs with categorical edge labels
Modern graph or network datasets often contain rich structure that goes beyond simple pairwise connections between nodes. This calls for complex representations that can capture, for instance, edges of different types as…
ClusteringCommunity Detection