An Effective Augmented Lagrangian Method for Fine-Grained Multi-View Optimization

Yuze Tan, Hecheng Cai, Shudong Huang, Shuping Wei, Fan Yang, Jiancheng Lv

Abstract

Multi-view clustering (MVC) aims to group data points by integrating information from multiple sources. Traditional methods often employ a "coarse-grained" approach, assigning a single weight to an entire view. This paper introduces ALMOND (Augmented Lagrangian MethOd for fiNe-graineD), a framework that shifts to a "fine-grained" sample-level weighting strategy. By utilizing the Augmented Lagrangian Method (ALM), ALMOND achieves a self-consistent optimization that avoids heuristic intermediate variables, leading to state-of-the-art performance across diverse datasets.

Introduction

The goal of multi-view clustering is to leverage complementary information from various sources—such as image pixels, text descriptions, and metadata—to improve clustering accuracy. However, most existing MVC methods are "coarse-grained," treating each view as a monolithic entity with a single importance weight.

This approach is fundamentally limited. In practice, a view might be highly informative for certain data points while being noisy or irrelevant for others. Furthermore, many optimization algorithms rely on "inexplicable intermediate variables" to simplify complex objective functions, which can compromise the model's self-consistency and lead to sub-optimal results. ALMOND addresses these challenges by introducing sample-wise weighting and a robust optimization framework.

Methodology: Fine-Grained Fusion and ALM

ALMOND proposes a unified objective function that integrates multi-view subspace learning with a sample-wise graph fusion strategy.

Fine-Grained Fusion

Unlike traditional methods that assign one weight per view, ALMOND assigns a unique weight vector to every individual sample across all views. This allows the model to capture local structural coherence more effectively, as illustrated in the comparison below.

Comparison between coarse-grained and fine-grained (ALMOND) fusion strategies.

Self-Consistent Optimization via ALM

The model avoids the typical two-stage "learn then fuse" pipeline. Instead, it simultaneously learns subspace representations, sample weights, and a consensus graph. Because these variables are highly coupled, standard alternating optimization is difficult. ALMOND employs the Augmented Lagrangian Method (ALM), introducing an auxiliary variable and a penalty term to decouple the variables. This allows for closed-form solutions for each sub-problem, maintaining a "pure" mathematical model without heuristic shortcuts.

Experimental Evaluation

The researchers evaluated ALMOND on seven benchmark datasets, including face image sets (Yale, ORL), citation networks (Citeseer, Cora), and news documents (BBC).

Performance Results

ALMOND consistently outperformed nearly a dozen state-of-the-art (SOTA) methods, including MVCTM, LMVSC, and MCGC, across metrics such as Accuracy (ACC) and Normalized Mutual Information (NMI).

  • Cora Dataset: ALMOND achieved an ACC of 73.00%, a significant improvement over the next best method's 64.16%.
  • Citeseer Dataset: ACC improved by over 3% compared to previous benchmarks.

Parameter Sensitivity

The model's performance is relatively stable across a wide range of hyperparameters ($\alpha, \beta, \lambda$). However, sensitivity increases if these parameters are pushed to extreme ranges.

NMI performance across various hyperparameter settings ($\alpha, \beta, \lambda$).

Discussion and Conclusion

The core innovation of ALMOND lies in its focus on local vs. global consistency. While different views are heterogeneous globally, they often share a common local structure. By focusing on the intersection of views at the sample level, ALMOND preserves cross-view consistency more effectively than view-wise weighting.

Despite its success, the authors noted that clustering performance can become unstable when the Lagrangian penalty parameter grows too large. Additionally, the objective function loss may not drop smoothly in early iterations due to initial conflicts between capturing global subspace information and local structures. Future work will explore adaptive learning schemes for graph fusion to further mitigate parameter sensitivity.

Summary updated

Abstract

The significance of multi-view learning in effectively mitigating the intricate intricacies entrenched within heterogeneous data has garnered substantial attention in recent years. Notwithstanding the favorable achievements showcased by recent strides in this area, a confluence of noteworthy challenges endures. To be specific, a majority of extant methodologies unceremoniously assign weights to data points view-wisely. This ineluctably disregards the intrinsic reality that disparate views confer diverse contributions to each individual sample, consequently neglecting the rich wellspring of sample-level structural insights harbored within the dataset. In this paper, we proposed an effective Augmented Lagrangian MethOd for fiNe-graineD (ALMOND) multi-view optimization. This innovative approach scrutinizes the interplay among multiple views at the granularity of individual samples, thereby fostering the enhanced preservation of local structural coherence. The Augmented Lagrangian Method (ALM) is elaborately incorporated into our framework, which enables us to achieve an optimal solution without involving an inexplicable intermediate variable as previous methods do. Empirical experiments on multi-view clustering tasks across heterogeneous datasets serve to incontrovertibly showcase the effectiveness of our proposed methodology, corroborating its preeminence over incumbent state-of-the-art alternatives.
BibTeX
@inproceedings{tan2024effective,
  author = {Yuze Tan and Hecheng Cai and Shudong Huang and Shuping Wei and Fan Yang and Jiancheng Lv},
  title = {{An Effective Augmented Lagrangian Method for Fine-Grained Multi-View Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i14.29449},
}
Figure