Local Correlation Clustering with Asymmetric Classification Errors
Local Correlation Clustering with Asymmetric Classification Errors
复制标题
DOI：
--
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Jafar Jafarov;Sanchit Kalhan;K. Makarychev;Yury Makarychev
中科院分区：
文献类型：
--
作者：
Jafar Jafarov;Sanchit Kalhan;K. Makarychev;Yury Makarychev
在相关聚类问题中，我们为我们提供了一个完整的加权图$ g $，其边缘由嘈杂的二进制分类器标记为“相似”和“不同”。对于graph $ g $的群集$ \ mathcal {c} $，如果其终点属于不同的簇，则类似的边缘与$ \ Mathcal {C} $不同意；如果其端点属于同一群集，则与$ \ Mathcal {C} $不同的边缘与$ \ MATHCAL {C} $分歧。分歧向量，$ \ text {dis} $，是由$ g $的顶点索引的向量索引，以至于$ v $ - th坐标$ \ text {dis} _v $等于所有不同意的边缘的权重， V $。目标是产生一个聚类，以最大程度地减少$ p \ geq 1 $的分歧矢量的$ \ ell_p $ norm。我们在以下假设下研究$ \ ell_p $相关聚类的目标：每个类似的边缘的权重在$ [\ alpha \ alpha \ mathbf {w}，\ mathbf {w}]的范围内$ \ alpha \ mathbf {w} $（其中$ \ alpha \ leq 1 $和$ \ mathbf {w}> 0 $是缩放参数）。我们给出一个$ o \ left（（\ frac {1} {\ alpha}）^{\ frac {1} {2} {2} - \ frac {1} {2p}} {2p}} \ cdot \ cdot \ log \ frac {1} alpha} \ right）$近似算法此问题。此外，我们显示了几乎匹配的凸编程完整性差距。
In the Correlation Clustering problem, we are given a complete weighted graph $G$ with its edges labeled as"similar"and"dissimilar"by a noisy binary classifier. For a clustering $\mathcal{C}$ of graph $G$, a similar edge is in disagreement with $\mathcal{C}$, if its endpoints belong to distinct clusters; and a dissimilar edge is in disagreement with $\mathcal{C}$ if its endpoints belong to the same cluster. The disagreements vector, $\text{dis}$, is a vector indexed by the vertices of $G$ such that the $v$-th coordinate $\text{dis}_v$ equals the weight of all disagreeing edges incident on $v$. The goal is to produce a clustering that minimizes the $\ell_p$ norm of the disagreements vector for $p\geq 1$. We study the $\ell_p$ objective in Correlation Clustering under the following assumption: Every similar edge has weight in the range of $[\alpha\mathbf{w},\mathbf{w}]$ and every dissimilar edge has weight at least $\alpha\mathbf{w}$ (where $\alpha \leq 1$ and $\mathbf{w}>0$ is a scaling parameter). We give an $O\left((\frac{1}{\alpha})^{\frac{1}{2}-\frac{1}{2p}}\cdot \log\frac{1}{\alpha}\right)$ approximation algorithm for this problem. Furthermore, we show an almost matching convex programming integrality gap.