## AI 生成解读视频

AI抽取解析论文重点内容自动生成视频 ## AI 溯源

AI解析本论文相关学术脉络 ## AI 精读

AI抽取本论文的概要总结

For every pair of vertices u and v, the integer program has a variable xuv ∈ {0, 1}, which indicates whether u and v belong to the same cluster: we present an approximation algorithm for Correlation Clustering with Asymmetric Classification Errors

# Correlation Clustering with Asymmetric Classification Errors

ICML, pp.4641-4650, (2020)

EI

In the Correlation Clustering problem, we are given a weighted graph $G$ with its edges labeled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study ...更多

0

• In the Correlation Clustering problem, the authors are given a set of objects with pairwise similarity information.
• The authors study the Correlation Clustering problem on complete graphs with edge weights.
• The assumptions made by the Correlation Clustering on Complete Graphs model are too strong, since rarely do real world instances have equal edge weights.

• In the Correlation Clustering problem, we are given a set of objects with pairwise similarity information
• The pairwise information is represented as a weighted graph G whose edges are labelled as “positive/similar” and “negative/dissimilar” by a noisy binary classifier
• The goal is to find a clustering C that minimizes the weight of edges disagreeing with this clustering: A positive edge is in disagreement with C, if its endpoints belong to distinct clusters; and a negative edge is in disagreement with C if its endpoints belong to the same cluster
• Charikar, Guruswami, and Wirth (2003) and Demaine, Emanuel, Fiat, and Immorlica (2006) gave an O approximation algorithm, they showed that Correlation Clustering with Partial Noisy Information is as hard as the Multicut problem and, O is likely to be the best possible approximation for this problem
• We study the Correlation Clustering problem on complete graphs with edge weights
• For every pair of vertices u and v, the integer program (IP) has a variable xuv ∈ {0, 1}, which indicates whether u and v belong to the same cluster: we present an approximation algorithm for Correlation Clustering with Asymmetric Classification Errors

• The following examples show how the Correlation Clustering with Asymmetric Classification Errors model can help in capturing real world instances.
• If the authors were to use the state of the art algorithm for Correlation Clustering on Complete Graphs on the instance for Correlation Clustering with Asymmetric Classification Errors, the authors would get a Θ(max(w+/w−, w−/w+)) approximation to the MinDisagree objective.
• The authors present an approximation algorithm for Correlation Clustering with Asymmetric Classification Errors.
• There exists a polynomial time A = 3 + 2 loge 1/α approximation algorithm for Correlation Clustering with Asymmetric Classification Errors.
• There exists a polynomial time A = 6 + 2 loge 1/α approximation algorithm for Correlation Clustering with Asymmetric Classification Errors on complete bipartite graphs.
• The authors show a similar integraplity gap result for the Correlation Clustering with Asymmetric Classification Errors on complete bipartite graphs problem.
• The natural Linear Programming relaxation for Correlation Clustering has an integrality gap of Ω for instances of Correlation Clustering with Asymmetric Classification Errors on complete bipartite graphs.
• The log-likelihood function of the clustering C is, Throughout the paper, the authors denote the set of positive edges by E+ and the set of negative edges by E−.
• For every pair of vertices u and v, the integer program (IP) has a variable xuv ∈ {0, 1}, which indicates whether u and v belong to the same cluster: the authors present an approximation algorithm for Correlation Clustering with Asymmetric Classification Errors.

• Let them assign arbitrary lengths xuv, xvw, and xuw satisfying the triangle inequality to the edges uv, vw, and uw and run one iteration of the algorithm on the triangle uvw.
• Let them point out that Theorem 1.1 has dependence A = 3 + 2 loge 1/α because (i) f (x) must be equal to C − e−Ax or a slower growing function so that Claim 3.4 holds Theorem 3.1 requires that f (0) = 0, and the authors will need below that 1 − f
• Observe that the LP cost of a negative edge (u, v) (which is equal to α(1 − xuv)) is positive if and only if d(u, v) < 1/2 log3 n.

• In the Correlation Clustering problem, the authors are given a set of objects with pairwise similarity information.
• The authors study the Correlation Clustering problem on complete graphs with edge weights.
• The assumptions made by the Correlation Clustering on Complete Graphs model are too strong, since rarely do real world instances have equal edge weights.
• The following examples show how the Correlation Clustering with Asymmetric Classification Errors model can help in capturing real world instances.
• If the authors were to use the state of the art algorithm for Correlation Clustering on Complete Graphs on the instance for Correlation Clustering with Asymmetric Classification Errors, the authors would get a Θ(max(w+/w−, w−/w+)) approximation to the MinDisagree objective.
• The authors present an approximation algorithm for Correlation Clustering with Asymmetric Classification Errors.
• There exists a polynomial time A = 3 + 2 loge 1/α approximation algorithm for Correlation Clustering with Asymmetric Classification Errors.
• There exists a polynomial time A = 6 + 2 loge 1/α approximation algorithm for Correlation Clustering with Asymmetric Classification Errors on complete bipartite graphs.
• The authors show a similar integraplity gap result for the Correlation Clustering with Asymmetric Classification Errors on complete bipartite graphs problem.
• The natural Linear Programming relaxation for Correlation Clustering has an integrality gap of Ω for instances of Correlation Clustering with Asymmetric Classification Errors on complete bipartite graphs.
• The log-likelihood function of the clustering C is, Throughout the paper, the authors denote the set of positive edges by E+ and the set of negative edges by E−.
• For every pair of vertices u and v, the integer program (IP) has a variable xuv ∈ {0, 1}, which indicates whether u and v belong to the same cluster: the authors present an approximation algorithm for Correlation Clustering with Asymmetric Classification Errors.
• Let them assign arbitrary lengths xuv, xvw, and xuw satisfying the triangle inequality to the edges uv, vw, and uw and run one iteration of the algorithm on the triangle uvw.
• Let them point out that Theorem 1.1 has dependence A = 3 + 2 loge 1/α because (i) f (x) must be equal to C − e−Ax or a slower growing function so that Claim 3.4 holds Theorem 3.1 requires that f (0) = 0, and the authors will need below that 1 − f
• Observe that the LP cost of a negative edge (u, v) (which is equal to α(1 − xuv)) is positive if and only if d(u, v) < 1/2 log3 n.

• Table1: Approximation factors Athm and Aopt for different α-s

• Jafar Jafarov and Yury Makarychev were supported in part by NSF CCF-1718820 and NSF TRIPODS CCF-1934843
• Sanchit Kalhan and Konstantin Makarychev were supported in part by NSF TRIPODS CCF-1934931 Jafar Jafarov Sanchit Kalhan 0
{"ft_lang_label":"__label__en","ft_lang_prob":0.7767115,"math_prob":0.9472214,"size":10339,"snap":"2021-31-2021-39","text_gpt3_token_len":2699,"char_repetition_ratio":0.18016449,"word_repetition_ratio":0.56277055,"special_character_ratio":0.23899797,"punctuation_ratio":0.1753313,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99453557,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-19T02:00:17Z\",\"WARC-Record-ID\":\"<urn:uuid:657e2bf5-ab53-429e-83a9-f7cb76e7f9a0>\",\"Content-Length\":\"103563\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b2a8941d-2d35-4749-bcd0-693b10b9ef63>\",\"WARC-Concurrent-To\":\"<urn:uuid:ed75da7c-36bc-48aa-ac99-878d91516c18>\",\"WARC-IP-Address\":\"47.93.38.204\",\"WARC-Target-URI\":\"https://www.aminer.cn/pub/5ede0553e06a4c1b26a84175/correlation-clustering-with-asymmetric-classification-errors\",\"WARC-Payload-Digest\":\"sha1:QNVGAIM2IGKZNQ6TVORF3XFCC4KX72XP\",\"WARC-Block-Digest\":\"sha1:RFLYLUA2LPB2ZDEZ3QXSCUQ3Y3FIKYP4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780056656.6_warc_CC-MAIN-20210919005057-20210919035057-00506.warc.gz\"}"}