Conference Proceedings

Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs

Nate Veldt, Anthony Wirth, David F Gleich

Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining | ACM | Published : 2020

Abstract

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 relevant 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 h..

View full abstract

Funding Acknowledgements

This research was supported by NSF IIS-1546488, CCF-1909528,NSF Center for Science of Information STC, CCF-0939370, DOEDESC0014543, NASA, the Sloan Foundation, and the MelbourneSchool of Engineering.