Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs
Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs
复制标题
DOI：
10.1145/3394486.3403238
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Nate Veldt;Anthony Wirth;D. Gleich
中科院分区：
文献类型：
--
作者：
Nate Veldt;Anthony Wirth;D. Gleich
受社区检测和稠密子图发现应用的启发，我们考虑超图和二分图中的新聚类目标。这些目标通过一个或多个分辨率参数进行参数化，以便在复杂数据中实现多样化的知识发现。对于超图和二分目标，我们确定相关的参数制度，相当于现有的目标，并分享他们的（多项式时间）近似算法。我们首先表明，我们的参数化超图相关聚类目标是有关的高阶概念的规范化切割和超图的模块化。它是进一步服从近似算法通过超边缘扩展技术。我们的参数化二分相关聚类目标概括了标准的未加权二分相关聚类，以及双聚类删除问题。对于某些参数的选择，它也与我们的超图目标有关。虽然在一般情况下，它是NP-难的，我们强调的参数制度的二分目标的问题减少到二分匹配问题，从而可以在多项式时间内解决。对于其他参数的设置，我们提出了几个近似算法使用线性规划舍入技术。这些结果使我们能够引入双簇删除的第一个常数因子近似，即删除最少数量的边以将二分图划分为不相交的二团的任务。在几个实验结果中，我们强调了我们的框架的灵活性和在不同参数设置下可以获得的结果的多样性。这包括跨一系列参数对二分图进行聚类，检测电子邮件网络和食品网络中的主题丰富的集群，以及在产品评论超图中形成与已知产品类别高度相关的零售产品集群。
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 hyperedge expansion techniques. Our parameterized bipartite correlation clustering objective generalizes standard unweighted bipartite correlation clustering, as well as the bicluster deletion problem. 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 several 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.