Regression-based Hypergraph Learning for Image Clustering and Classification

Sheng Huang, Dan Yang, Bo Liu, Xiaohong ZhangarXiv 2016 · arXiv

Abstract

Hypergraph learning is a powerful tool for modeling high-order relationships in data, yet its effectiveness is often limited by construction methods based on simple Euclidean distance. This paper introduces the Regression-based Hypergraph (RH) framework, which leverages robust regression models—specifically Sparse Representation (SR) and Collaborative Representation (CR)—to identify meaningful correlations between data points. By constructing hyperedges from samples that best reconstruct a target centroid, the RH model effectively filters noise and captures semantic group structures. Experimental results across six benchmark datasets demonstrate that RH significantly outperforms traditional hypergraph methods in both unsupervised clustering and semi-supervised classification, especially in environments with significant noise or occlusions.

Introduction

In machine learning, graphs are fundamental for representing data relationships. While standard graphs connect pairs of vertices, hypergraphs allow edges (hyperedges) to connect multiple vertices, capturing complex, high-order structures. However, the traditional "k-nearest neighbor" (k-NN) approach to hypergraph construction is highly sensitive to noise and often fails to reflect true semantic relationships. To address these limitations, the authors propose a regression-based approach that bridges the gap between robust reconstruction models and hypergraph learning.

Methods

The core of the proposed framework is the Regression-based Hypergraph (RH) model. Instead of relying on physical distance, the model determines neighbors by solving a regression problem: which other samples can best reconstruct a given sample?

  1. Correlation Estimation: For each sample, the model calculates coefficients using either $L_1$-norm (Sparse Representation) or $L_2$-norm (Collaborative Representation). These coefficients represent the semantic correlation between the target sample and its peers.
  2. Hyperedge Construction: A hyperedge is formed by a "centroid" sample and its $m$ most correlated samples.
  3. Weighting: Hyperedge weights are derived from the mean correlation among members, providing a natural measure of group cohesion.
Regression coefficients and corresponding face samples used for hyperedge construction.

The authors instantiate two versions: $L_1H$ (based on SR) and $L_2H$ (based on CR), applying them to spectral clustering (RHSC) and transduction (RHT).

Experimental Evaluation

The researchers evaluated the RH models on six diverse image databases, including AR, ORL, COIL20, ETH80, Scene15, and Caltech256. These datasets provide a range of challenges, from varying lighting and expressions to complex object categories and significant occlusions.

Sample images from the AR dataset, illustrating the challenges of facial expression and "disguise" (sunglasses and scarves).

Key Results

  • Clustering Performance: On the AR dataset, the $L_2$HSC model achieved 73.43% accuracy, more than doubling the performance of traditional methods like NHSC (36.71%).
  • Robustness to Occlusion: In tests involving "disguised" faces (sunglasses or scarves), the $L_2$HT model maintained a low error rate of 4.00%, whereas standard hypergraph methods largely failed (errors > 90%).
  • Noise Tolerance: The RH framework demonstrated superior stability as pixel noise was added to the COIL20 dataset, outperforming k-NN based methods which showed rapid performance degradation.

Conclusion

The Regression-based Hypergraph framework offers a robust alternative to traditional distance-based hypergraph construction. By inheriting the noise-filtering properties of SR and CR, RH models provide superior discriminative power for image analysis tasks. Future work will focus on reducing computational complexity and developing adaptive methods for hyperparameter tuning.

Summary updated

BibTeX
@misc{huang2016regression,
  author = {Sheng Huang and Dan Yang and Bo Liu and Xiaohong Zhang},
  title = {{Regression-based Hypergraph Learning for Image Clustering and Classification}},
  year = {2016},
  eprint = {1603.04150},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1603.04150},
}
Figure