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.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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
Related URLs:
URLURL TypeDescription
Perona, Pietro0000-0002-7583-5809
Belongie, Serge0000-0002-0388-5217
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.
Funding AgencyGrant Number
Department of Energy (DOE)W-7405-ENG-48
Alfred P. Sloan FoundationUNSPECIFIED
NSFCCR 00-86094
Center for Neuromorphic Systems Engineering, CaltechUNSPECIFIED
Multidisciplinary University Research Initiative (MURI)SA3318
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10815
Deposited On:13 Jun 2008
Last Modified:08 Nov 2021 21:11

Repository Staff Only: item control page