CaltechAUTHORS
  A Caltech Library Service

Beyond pairwise clustering

Agarwal, Sameer and Lim, Jongwoo and Zelnik-Manor, Lihi and Perona, Pietro and Kriegman, David and Belongie, Serge (2005) Beyond pairwise clustering. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005). Vol.2. IEEE , Piscataway, NJ, pp. 838-845. ISBN 0769523722 http://resolver.caltech.edu/CaltechAUTHORS:AGAieeecvpr05

[img]
Preview
PDF
See Usage Policy.

178Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:AGAieeecvpr05

Abstract

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.


Item Type:Book Section
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Publication Date: 20-25 June 2005. It is a pleasure to acknowledge our various discussions with Andrew Kahng, Fan Chung Graham, Ian Abramson, Josh Wills, Kristin Branson, Sanjoy Dasgupta and Satya Prakash Mallick. We also thank Henrik Wann Jensen and Craig Donner for giving us access to their cluster. Sameer Agarwal and Serge Belongie are supported by NSF-CAREER #0448615, DOE/LLNL contract no. W-7405-ENG-48 (subcontracts B542001 and B547328), and the Alfred P. Sloan Fellowship. Jongwoo Lim and David Kriegman are supported by NSF CCR 00-86094. Lihi Zelnik-Manor and Pietro Perona are supported by MURI award number SA3318 and by the Center of Neuromorphic Systems Engineering award EEC-9402726.
Subject Keywords:approximation theory; computer vision; graph theory; pattern clustering; hypergraph partitioning problem; pairwise clustering; spectral partitioning algorithm; weighted graph
Record Number:CaltechAUTHORS:AGAieeecvpr05
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:AGAieeecvpr05
Alternative URL:http://dx.doi.org/10.1109/CVPR.2005.89
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10815
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:13 Jun 2008
Last Modified:26 Dec 2012 10:05

Repository Staff Only: item control page