Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2005 | Published
Book Section - Chapter Open

Beyond pairwise clustering

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.

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.

Attached Files

Published - AGAieeecvpr05.pdf

Files

AGAieeecvpr05.pdf
Files (183.1 kB)
Name Size Download all
md5:553c0c1bb3cdea91746315fcd97f8005
183.1 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023