Beyond pairwise clustering

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.

• Publication year

  2005

• Venue

  Computer Vision and Pattern Recognition

• Publication date

  2005-06-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CVPR.2005.89
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A tensor decomposition for geometric grouping and segmentation

  2005cited by this paper
• Spectral grouping using the Nystrom method

  2004cited by this paper
• A new GPCA algorithm for clustering subspaces by fitting, differentiating and dividing polynomials

  2004cited by this paper
• An improved direct labeling method for the max–flow min–cut computation in large hypergraphs and applications

  2003cited by this paper
• A new graph-theoretic approach to clustering and segmentation

  2003cited by this paper
• On Spectral Clustering: Analysis and an algorithm

  2001cited by this paper
• From Few to Many: Illumination Cone Models for Face Recognition under Variable Lighting and Pose

  2001cited by this paper
• Computer Vision

  2001cited by this paper
• Clustering categorical data: an approach based on dynamical systems

  2000influential reference
• n-Semimetrics

  2000cited by this paper
• Stochastic image segmentation by typical cuts

  1999cited by this paper
• Multilevel k-way hypergraph partitioning

  1999cited by this paper
• Modern Multidimensional Scaling: Theory and Applications

  1999cited by this paper
• Comparing images under variable illumination

  1998cited by this paper
• Geometric motion segmentation and model selection

  1998influential reference
• What Is the Set of Images of an Object Under All Possible Illumination Conditions?

  1998cited by this paper
• Beyond the flow decomposition barrier

  1997cited by this paper
• Normalized cuts and image segmentation

  1997cited by this paper
• Pairwise Data Clustering by Deterministic Annealing

  1997cited by this paper
• Triadic Distance Models: Axiomatization and Least Squares Representation

  1997cited by this paper
• What is the set of images of an object under all possible lighting conditions?

  1996cited by this paper
• Numerical Methods for Least Squares Problems

  1996cited by this paper
• Recent directions in netlist partitioning: a survey

  1995cited by this paper
• Approximation Techniques for Hypergraph Partitioning Problems

  1995cited by this paper
• Three-way distances

  1995cited by this paper
• Modeling Hypergraphs by Graphs with the Same Mincut Properties

  1993cited by this paper
• Multidimensional scaling for n-tuples

  1991cited by this paper
• Finding Groups in Data: An Introduction to Cluster Analysis

  1990cited by this paper
• Computer Vision

  1988cited by this paper
• A Linear-Time Heuristic for Improving Network Partitions

  1982cited by this paper
• Generalizing the Hough transform to detect arbitrary shapes

  1981cited by this paper
• Two dimensional quantification based on the measure of dissimilarity among three elements

  1972cited by this paper
• Analysis of individual differences in multidimensional scaling via an n-way generalization of “Eckart-Young” decomposition

  1970cited by this paper
• An efficient heuristic procedure for partitioning graphs

  1970cited by this paper
• European Journal of Combinatorics

  year unknowncited by this paper

• Local community detection by random walk on hypergraphs

  2025cites this paper
• Consistent line clustering using geometric hypergraphs

  2025cites this paper
• Re-imagining Spectral Graph Theory

  2025cites this paper
• Deep hypergraph regularized Lp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{p}$$\end{document} smooth semi-nonneg

  2025cites this paper
• On Graph Representation for Attributed Hypergraph Clustering

  2025cites this paper
• The Complexity of Counting Small Sub-Hypergraphs

  2025cites this paper
• Partial Optimality in Cubic Correlation Clustering for General Graphs

  2025cites this paper
• Statistical Limits for Finite-Rank Tensor Estimation

  2025cites this paper
• Hypergraph Neural Sheaf Diffusion: A Symmetric Simplicial Set Framework for Higher-Order Learning

  2025cites this paper
• Random walks with resetting on hypergraph

  2025cites this paper
• Efficient Structural Clustering Over Hypergraphs

  2025cites this paper
• Community and hyperedge inference in multiple hypergraphs

  2025cites this paper
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks

  2024cites this paper
• Discriminating Tensor Spectral Clustering for High-Dimension-Low-Sample-Size Data

  2024cites this paper
• High-Order Local Clustering on Hypergraphs

  2024cites this paper
• SE3Set: Harnessing equivariant hypergraph neural networks for molecular representation learning

  2024cites this paper
• Deep Tensor Spectral Clustering Network via Ensemble of Multiple Affinity Tensors

  2024cites this paper
• Morse Theory for the k-NN Distance Function

  2024cites this paper
• A Lovász-Simonovits Theorem for Hypergraphs with Application to Local Clustering

  2024cites this paper
• Explaining Hypergraph Neural Networks: From Local Explanations to Global Concepts

  2024cites this paper
• Human Motion Prediction Based on a Multi-Scale Hypergraph for Intangible Cultural Heritage Dance Videos

  2023influential citation
• Modularity-based Hypergraph Clustering: Random Hypergraph Model, Hyperedge-cluster Relation, and Computation

  2023cites this paper
• CAT-Walk: Inductive Hypergraph Learning via Set Walks

  2023cites this paper
• PhyGCN: Pre-trained Hypergraph Convolutional Neural Networks with Self-supervised Learning

  2023cites this paper
• Linear Opinion Dynamics Model With Higher Order Interactions

  2023cites this paper
• Degree Heterogeneity in Higher-Order Networks: Inference in the Hypergraph β-Model

  2023cites this paper
• ClusterFormer: Clustering As A Universal Visual Learner

  2023cites this paper
• Low-Latency and Reliable Virtual Network Function Placement in Edge Clouds

  2023cites this paper
• Hypergraph motifs and their extensions beyond binary

  2023cites this paper
• Interpretable online network dictionary learning for inferring long-range chromatin interactions

  2023cites this paper
• Quantum Multi-Model Fitting

  2023cites this paper
• Architectures of Topological Deep Learning: A Survey on Topological Neural Networks

  2023cites this paper
• Partial Optimality in Cubic Correlation Clustering

  2023cites this paper
• From Hypergraph Energy Functions to Hypergraph Neural Networks

  2023cites this paper
• Uniform Tensor Clustering by Jointly Exploring Sample Affinities of Various Orders

  2023influential citation
• A Hybrid Quantum-Classical Algorithm for Robust Fitting

  2022influential citation
• Hypergraph matching via game-theoretic hypergraph clustering

  2022cites this paper
• Inferring Single-Molecule Chromatin Interactions via Online Convex Network Dictionary Learning

  2022cites this paper
• Comprehensive survey on hierarchical clustering algorithms and the recent developments

  2022cites this paper
• Higher-Order Multicuts for Geometric Model Fitting and Motion Segmentation

  2022cites this paper
• Finding Bipartite Components in Hypergraphs

  2022cites this paper
• Comparison among different Clustering and Classification Techniques: Astronomical data-dependent study

  2022cites this paper
• Core-periphery detection in hypergraphs

  2022cites this paper
• Hypergraph Simultaneous Generators

  2022cites this paper
• Generative hypergraph clustering: From blockmodels to modularity

  2021cites this paper
• Co-clustering Vertices and Hyperedges via Spectral Hypergraph Partitioning

  2021cites this paper
• Community Detection in General Hypergraph Via Graph Embedding

  2021cites this paper
• Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components

  2021cites this paper
• Sharp Impossibility Results for Hyper-graph Testing

  2021cites this paper
• Investigation of the effect of bars on the properties of spiral galaxies: a multivariate statistical study

  2021influential citation
• Community Detection in Hypergraphs with Application to Partitioning

  2021cites this paper
• Subsampling spectral clustering for stochastic block models in large-scale networks

  2021cites this paper
• You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks

  2021cites this paper
• MultiLink: Multi-class Structure Recovery via Agglomerative Clustering and Model Selection

  2021cites this paper
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons

  2021cites this paper
• Gaussian Processes on Hypergraphs

  2021cites this paper
• Communication Efficient Distributed Hypergraph Clustering

  2021cites this paper
• Robust High-Order Manifold Constrained Low Rank Representation for Subspace Clustering

  2021cites this paper
• Hypergraph-Supervised Deep Subspace Clustering

  2021cites this paper
• Hypergraph co-optimal transport: metric and categorical properties

  2021cites this paper
• Two metrics for attributed hypergraphs

  2021cites this paper
• Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning

  2020cites this paper
• Hypergraph partitioning using tensor eigenvalue decomposition

  2020cites this paper
• Robust Hypergraph Clustering via Convex Relaxation of Truncated MLE

  2020influential citation
• Spectral representation learning for one-step spectral rotation clustering

  2020cites this paper
• Localized Flow-Based Clustering in Hypergraphs

  2020cites this paper
• Robust non-negative matrix factorization with multiple correntropy-induced hypergraph regularizer

  2020cites this paper
• Hypergraph Cuts with General Splitting Functions

  2020influential citation
• Unsupervised Learning of Graph and Hypergraph Clustering

  2020cites this paper
• Hypergraph Clustering in the Weighted Stochastic Block Model via Convex Relaxation of Truncated MLE

  2020cites this paper
• Hypergraph motifs

  2020cites this paper
• Minimizing Localized Ratio Cut Objectives in Hypergraphs

  2020cites this paper
• Hypergraph clustering by iteratively reweighted modularity maximization

  2020cites this paper
• Spatial Constrained K-Means for Image Segmentation

  2020cites this paper
• Graph convolutional networks of reconstructed graph structure with constrained Laplacian rank

  2020cites this paper
• Parameterized Objectives and Algorithms for Clustering Bipartite Graphs and Hypergraphs

  2020cites this paper
• Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs

  2020influential citation
• Institutional Design and Complexity: Protocol Network Structure in Response to Different Collective-Action Dilemmas

  2020cites this paper
• Revisiting Nyström extension for hypergraph clustering

  2020cites this paper
• Hypergraph Clustering Based on PageRank

  2020cites this paper
• Studying full higher order affinity normalized cut

  2020cites this paper
• How Much and When Do We Need Higher-order Information in Hypergraphs? A Case Study on Hyperedge Prediction

  2020cites this paper
• GESAC: Robust graph enhanced sample consensus for point cloud registration

  2020cites this paper
• Clustering in Hypergraphs to Minimize Average Edge Service Time

  2020cites this paper
• A New Measure of Modularity in Hypergraphs: Theoretical Insights and Implications for Effective Clustering

  2019cites this paper
• Exact Partitioning of High-order Models with a Novel Convex Tensor Cone Relaxation

  2019influential citation
• Integrating Tensor Similarity to Enhance Clustering Performance

  2019cites this paper
• Computing Z-Eigenvalue Of Hankel Tensors

  2019cites this paper
• Robust ℓ2-Hypergraph and its applications

  2019cites this paper
• LDRD Final Report: Modeling Complex Relationships in Large-Scale Data using Hypergraphs.

  2019cites this paper
• Correntropy-Induced Robust Low-Rank Hypergraph

  2019cites this paper
• Community detection in the sparse hypergraph stochastic block model

  2019cites this paper
• Hypergraph Induced Convolutional Manifold Networks

  2019cites this paper
• Hypergraph Clustering Based on Intra-class Scatter Matrix for Mining Higher-order Microbial Module

  2019cites this paper
• Landing Probabilities of Random Walks for Seed-Set Expansion in Hypergraphs

  2019cites this paper
• Random Walks on Hypergraphs with Edge-Dependent Vertex Weights

  2019cites this paper
• Robust High-Order Manifold Constrained Sparse Principal Component Analysis for Image Representation

  2019cites this paper
• HS2: Active learning over hypergraphs with pointwise and pairwise queries

  2019cites this paper
• Hypergraph Optimization for Multi-Structural Geometric Model Fitting

  2019cites this paper
• Multi-view low-rank matrix factorization using multiple manifold regularization

  2019cites this paper