Beyond pairwise clustering
Research output: Contribution to journal › Conference article › Research › peer-review
Standard
Beyond pairwise clustering. / Agarwal, Sameer; Lim, Jongwoo; Zelnik-Manor, Lihi; Perona, Pietro; Kriegman, David; Belongie, Serge.
In: Proceedings - 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005, 2005, p. 838-845.Research output: Contribution to journal › Conference article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Beyond pairwise clustering
AU - Agarwal, Sameer
AU - Lim, Jongwoo
AU - Zelnik-Manor, Lihi
AU - Perona, Pietro
AU - Kriegman, David
AU - Belongie, Serge
PY - 2005
Y1 - 2005
N2 - We consider the problem of clustering in domains where the affinity relations are not dyadic (pairwise), but rather triadic, tetradic or higher. The problem is an instance of the hypergraph partitioning problem. We propose a two-step algorithm for solving this problem. In the first step we use a novel scheme to approximate the hypergraph using a weighted graph. In the second step a spectral partitioning algorithm is used to partition the vertices of this graph. The algorithm is capable of handling hyperedges of all orders including order two, thus incorporating information of all orders simultaneously. We present a theoretical analysis that relates our algorithm to an existing hypergraph partitioning algorithm and explain the reasons for its superior performance. We report the performance of our algorithm on a variety of computer vision problems and compare it to several existing hypergraph partitioning algorithms.
AB - We consider the problem of clustering in domains where the affinity relations are not dyadic (pairwise), but rather triadic, tetradic or higher. The problem is an instance of the hypergraph partitioning problem. We propose a two-step algorithm for solving this problem. In the first step we use a novel scheme to approximate the hypergraph using a weighted graph. In the second step a spectral partitioning algorithm is used to partition the vertices of this graph. The algorithm is capable of handling hyperedges of all orders including order two, thus incorporating information of all orders simultaneously. We present a theoretical analysis that relates our algorithm to an existing hypergraph partitioning algorithm and explain the reasons for its superior performance. We report the performance of our algorithm on a variety of computer vision problems and compare it to several existing hypergraph partitioning algorithms.
UR - http://www.scopus.com/inward/record.url?scp=24644523726&partnerID=8YFLogxK
U2 - 10.1109/CVPR.2005.89
DO - 10.1109/CVPR.2005.89
M3 - Conference article
AN - SCOPUS:24644523726
SP - 838
EP - 845
JO - Proceedings - 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005
JF - Proceedings - 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005
T2 - 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005
Y2 - 20 June 2005 through 25 June 2005
ER -
ID: 302055002