LP-based pivoting algorithm for higher-order correlation clustering
LP-based pivoting algorithm for higher-order correlation clustering
复制标题
DOI：
10.1007/s10878-018-0354-y
复制
发表时间：
2018-07
影响因子：
1
通讯作者：
Takuro Fukunaga
中科院分区：
文献类型：
--
作者：
Takuro Fukunaga
相关聚类是一种从给定的成对信息中对一组对象进行聚类的方法。在这种方法中，给定的成对信息通常由一个无向图表示，该图的节点对应于对象，其中图中的每条边都被分配了一个非负权重，以及正或负标签。然后，通过求解一个优化问题，找到一个分区的节点集，最大限度地减少分歧或最大限度地与成对信息的协议，获得聚类。在本文中，我们扩展了相关聚类与分歧最小化，以处理由超图表示的高阶关系。我们给出了两个枢算法的基础上的线性规划松弛的问题。一个实现了一个近似，其中是节点的数量，是具有负标签的超边的最大大小。该算法可以应用于任意权值的超边。另一个是具有一致权的完全部超图的O（r）-逼近。这类超图产生于相关聚类的共聚类设置。
Correlation clustering is an approach for clustering a set of objects from given pairwise information. In this approach, the given pairwise information is usually represented by an undirected graph with nodes corresponding to the objects, where each edge in the graph is assigned a nonnegative weight, and either the positive or negative label. Then, a clustering is obtained by solving an optimization problem of finding a partition of the node set that minimizes the disagreement or maximizes the agreement with the pairwise information. In this paper, we extend correlation clustering with disagreement minimization to deal with higher-order relationships represented by hypergraphs. We give two pivoting algorithms based on a linear programming relaxation of the problem. One achieves an-approximation, wherenis the number of nodes andkis the maximum size of hyperedges with the negative labels. This algorithm can be applied to any hyperedges with arbitrary weights. The other is anO(r)-approximation for completer-partite hypergraphs with uniform weights. This type of hypergraphs arise from the coclustering setting of correlation clustering.