Automatic and Aligned Anchor Learning Strategy for Multi-View Clustering

Huimin Ma, Siwei Wang, Shengju Yu, Suyuan Liu, Jun-Jie Huang, Huijun Wu, Xinwang Liu, En Zhu

TL;DR

This paper introduces 3AMVC, a novel multi-view clustering method that automatically selects high-quality anchors without requiring a predefined number of clusters. It then intelligently aligns these anchors across views, prioritizing the view with the best anchor quality, to achieve improved clustering performance and efficiency on large-scale datasets.

What Problem Does This Paper Address?

Traditional Multi-View Clustering (MVC) methods often struggle with large datasets due to their high computational complexity, typically scaling quadratically with the number of samples. Anchor-based approaches offer a solution by approximating the full dataset with a smaller set of "anchors." However, existing anchor-based MVC methods face several challenges:

  • Anchor Selection Overhead: They usually require a pre-selection of anchors, treating the number of anchors as a tunable parameter that needs extensive searching, adding computational burden.
  • Uniform Anchor Count: Most methods assume the same number of anchors across all views, which is restrictive and can limit the representational power of anchors in views with different data characteristics.
  • Suboptimal Alignment: Existing alignment strategies might not effectively leverage the best available anchor sets, potentially leading to suboptimal clustering if a low-quality view is used as a reference.

This paper aims to address these limitations by proposing a method that automatically determines the optimal number and quality of anchors for each view and then aligns them based on the most representative view.

Methods

The proposed method, 3AMVC, consists of three main modules:

  1. Adaptive Anchor Selection Module (Hierarchical Bipartite Neighbor Clustering - HBNC): This is the core innovation. HBNC is a hierarchical clustering approach that does not require a predefined number of clusters. It adaptively selects representative anchors within each view. The process involves iteratively dividing samples based on distance to a target sample and an optimized threshold, aiming to balance intra-cluster similarity and inter-cluster dissimilarity. This allows for flexible anchor selection that respects the inherent data structure, similar to K-means but without the need to specify 'k'.
  2. Cross-View Anchor Alignment Module: This module addresses the challenge of varying numbers of anchors across views. It first evaluates the quality of anchors in each view using an intra-cluster distance criterion (specifically, a summation-based metric that is more robust to varying anchor counts than averaging). The view with the highest anchor quality is designated as the "baseline view." Then, it aligns the anchor graphs of other views to this baseline view, allowing for one-to-many or many-to-one matching relationships. This is an improvement over previous methods that might use a fixed or arbitrary baseline.
  3. Fusion Module: After alignment, the anchor graphs from all views are fused into a single, consolidated anchor graph. This fused graph is then used for spectral decomposition and K-means clustering to obtain the final cluster assignments.

Datasets

The authors evaluated their method on five widely used multi-view benchmark datasets:

  • ForestTypes
  • Reuters
  • MFeat
  • Caltech256
  • VGGFace2

No new datasets were introduced.

Key Insights and Ideas

  • Anchor Selection without 'k': The most significant insight is the development of HBNC, which liberates anchor selection from the constraint of a predefined cluster number. This is crucial for real-world scenarios where the number of clusters is often unknown.
  • Quality-Driven Alignment: The idea of explicitly evaluating anchor quality across views and using the best one as a baseline for alignment is a key improvement. This ensures that the alignment process is grounded in the most representative data, leading to more robust results.
  • Handling Unequal Anchor Counts: The proposed alignment strategy effectively handles situations where different views yield a different number of anchors, a common occurrence with adaptive selection methods.
  • Parameter-Free Anchor Selection: The HBNC method offers a parameter-free approach to anchor selection, reducing the burden of hyperparameter tuning.

Key Results

  • Performance Improvement: 3AMVC consistently outperformed or achieved comparable results to nine state-of-the-art multi-view clustering methods across various metrics (ACC, NMI, Fscore) on the tested datasets. For instance, it showed significant improvements in ACC over the traditional alignment algorithm FMVACC, with gains ranging from 0.69% to 13.17%.
  • Efficiency: The paper highlights that 3AMVC has a lower running time compared to FMVACC, demonstrating its efficiency for large-scale scenarios. The complexity is shown to be approximately O(n), making it suitable for large datasets.
  • Ablation Studies: Experiments showed that both the automatic anchor selection (HBNC) and the quality-based baseline alignment strategies are crucial for 3AMVC's superior performance. Removing either component led to a noticeable drop in clustering quality.
  • Visualization: Visualizations confirmed that HBNC selects more representative anchors that better capture the graph structure compared to K-means, especially in scenarios with uneven sample distributions.

Limitations and Future Work

  • Parameter Sensitivity: While the anchor selection is parameter-free, the paper notes that the fusion parameters (β and λ) still require some tuning, although the influence is described as "not intensive." Figure 4 suggests that specific ranges of β and λ can further improve performance.
  • Computational Complexity: Although the overall complexity is O(n), the initial HBNC step on a single view can still be computationally intensive for extremely large views, with a complexity of O(nd) per layer. The paper mentions that subsequent layers have reduced complexity.
  • Future Work: The paper implicitly suggests that further exploration into optimizing the fusion process and potentially extending the HBNC framework to other clustering tasks could be valuable future directions. The robustness of the method to different types of data distributions and its scalability to even larger datasets could also be areas for future research.

Summary updated

Abstract

Multi-view Clustering (MVC) generally utilizes the anchor technique to decrease the computational complexity so as to tackle large-scale scenarios. Existing researches generally are supposed to select anchors in advance to complete the next clustering task. Nevertheless, the number of anchors cannot be predetermined and must be selected as a parameter, which introduces additional time consumption for parameter search. Moreover, maintaining an identical number of anchors across each view is not reasonable, as it restricts the representational capacity of anchors in individual views. To address the above issues, we propose a view adaptive anchor multi-view clustering called Multi-view Clustering with Automatic and Aligned Anchor (3AMVC). We introduce the Hierarchical Bipartite Neighbor Clustering (HBNC) strategy to adaptively select a suitable number of representative anchors from the original samples of each view. Specifically, When the representative difference of anchors lies in a acceptable and satisfactory range, the HBNC process is halted and picks out the final anchors. In addition, in response to the varying quantities of anchors across different views, we propose an innovative anchor alignment strategy. This approach initially evaluates the quality of anchors on each view based on the intra-cluster distance criterion and then proceeds to align based on the view with the highest-quality anchors. The carefully organized experiments well validate the effectiveness and strengthens of 3AMVC.
BibTeX
@inproceedings{ma2024automatic,
  author = {Huimin Ma and Siwei Wang and Shengju Yu and Suyuan Liu and Jun-Jie Huang and Huijun Wu and Xinwang Liu and En Zhu},
  title = {{Automatic and Aligned Anchor Learning Strategy for Multi-View Clustering}},
  booktitle = {ACM Multimedia},
  year = {2024},
  doi = {10.1145/3664647.3681273},
}
Figure