Parameter-Free Auto-Weighted Multiple Graph Learning: A Framework for Multiview Clustering and Semi-Supervised Classification

Feiping Nie, Jing Li, Xuelong Li

Introduction

In modern machine learning, data is frequently represented through multiple "views" or feature sets. For instance, an image can be characterized by its color distribution, texture, and shape, while a research paper can be defined by both its textual content and its citation network. Graph-based learning is a robust technique for integrating these diverse perspectives. However, a significant challenge remains: determining the optimal weight for each view. Traditional methods rely on manual hyperparameter tuning, which is computationally expensive and often impractical for unsupervised tasks like clustering.

The AMGL Framework

To address the "tuning tax," Feiping Nie and colleagues proposed Auto-weighted Multiple Graph Learning (AMGL). This framework automatically determines the optimal weights for different data views by reformulating the standard spectral learning objective function.

Mathematical Reformulation

Traditional multi-view methods typically minimize a weighted sum of graph Laplacians, governed by a regularization parameter $\gamma$. AMGL replaces this with a new objective function that utilizes a "square root" trick:

$$\min_{F \in \mathcal{C}} \sum_{v=1}^{m} \sqrt{Tr(F^T L^{(v)} F)}$$

By taking the derivative with respect to the indicator matrix $F$, a weight $\alpha^{(v)}$ emerges naturally, becoming inversely proportional to the square root of the trace of the $v$-th view's Laplacian. This ensures that "good" views (those with low trace values) are automatically assigned higher weights, while noisy views are penalized.

Optimization Strategy

The framework employs an alternating optimization strategy:

  1. Update $F$: With fixed weights, the problem reduces to a standard eigenvalue problem (for clustering) or a system of linear equations (for classification).
  2. Update Weights: With $F$ fixed, weights are re-calculated using the derived formula.
  3. Iterate: The process repeats until convergence. For semi-supervised classification, the authors prove this objective is convex, guaranteeing convergence to a global optimum.

Experimental Evaluation

The framework was evaluated on several real-world datasets, including MSRC-v1 (images), Handwritten Numerals (HW), CiteSeer (documents), and NUS-WIDE (large-scale images).

Key Results

AMGL consistently matches or exceeds the performance of state-of-the-art methods that require manual tuning. On the CiteSeer dataset, AMGL demonstrated superior classification accuracy across various labeling ratios ($\tau$).

Table 4: Classification accuracy comparison on CiteSeer (%). AMGL consistently outperforms or matches tuned models like Label Propagation (LP) and AMMSS.

In clustering tasks on MSRC-v1, AMGL achieved a Normalized Mutual Information (NMI) of 0.7432, surpassing Multi-view Spectral Clustering (MVSC) which reached 0.7197.

Robustness and Parameter Sensitivity

The most significant advantage of AMGL is its robustness. While traditional methods like MVSC or SMGI are highly sensitive to the regularization parameter $\gamma$, AMGL's performance remains stable because it effectively "finds" the optimal configuration automatically.

Sensitivity analysis of Purity and NMI on MSRC-v1 and NUS-WIDE datasets. AMGL (red lines) provides a stable, high-performance baseline compared to the parameter-dependent MVSC (blue lines).

Conclusion

AMGL represents a major step toward automated graph-based learning. By eliminating the need for manual hyperparameter tuning, it provides a "plug-and-play" solution that is both robust and high-performing. Future work may focus on optimizing the computational complexity for massive, web-scale datasets.

Summary updated

Abstract

Graph-based approaches have been successful in unsupervised and semi-supervised learning. In this paper, we focus on the real-world applications where the same instance can be represented by multiple heterogeneous features. The key point of utilizing the graph-based knowledge to deal with this kind of data is to reasonably integrate the different representations and obtain the most consistent manifold with the real data distributions. In this paper, we propose a novel framework via the reformulation of the standard spectral learning model, which can be used for multiview clustering and semisupervised tasks. Unlike other methods in the literature, the proposed methods can learn an optimal weight for each graph automatically without introducing an additive parameter as previous methods do. Furthermore, our objective under semisupervised learning is convex and the global optimal result will be obtained. Extensive empirical results on different real-world data sets demonstrate that the proposed methods achieve comparable performance with the state-of-the-art approaches and can be used more practically.
BibTeX
@inproceedings{nie2016parameter,
  author = {Feiping Nie and Jing Li and Xuelong Li},
  title = {{Parameter-Free Auto-Weighted Multiple Graph Learning: A Framework for Multiview Clustering and Semi-Supervised Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure