A Co-training Approach for Multi-view Spectral Clustering

Abhishek Kumar, Hal Daumé IiiICML 2011 · OpenReview

TL;DR

This paper introduces a novel spectral clustering algorithm designed for "multi-view" data—datasets where each point is described by multiple independent sets of features (e.g., a video’s audio and its images). By adapting the "co-training" philosophy from semi-supervised learning to an entirely unsupervised setting, the authors create a method that iteratively forces the clusterings of different views to agree with one another, resulting in significantly better performance without requiring any manual hyperparameter tuning.

What Problem Does This Paper Address?

In many real-world scenarios, data comes from multiple sources or "views." For example, a webpage can be represented by the text on the page and the anchor text of links pointing to it. Standard clustering techniques usually handle this by either picking the "best" single view or simply concatenating all features into one giant vector.

However, these approaches often ignore the underlying structure: if two points belong to the same cluster, they should ideally be close to each other in all views. The challenge is how to mathematically enforce this "agreement" across views during the clustering process, especially when we have no labels to guide the algorithm.

Methods

The authors propose Co-trained Multi-view Spectral Clustering. Their approach is inspired by the co-training algorithm used in semi-supervised learning, where two classifiers teach each other by labeling unlabeled data.

Since clustering has no labels, the authors use the spectral embedding (the top eigenvectors of the graph Laplacian) as a proxy for labels. The algorithm works as follows:

  1. Initial Embedding: Compute the standard spectral clustering eigenvectors for each view independently.
  2. Iterative Refinement: Use the eigenvectors from View A to "filter" or modify the similarity graph of View B, and vice versa.
  3. Specifically, they project the similarity matrix of one view onto the subspace spanned by the top eigenvectors of the other view.
  4. This process effectively "glues" points together in View B if View A believes they belong in the same cluster, while smoothing out noise that doesn't align across views.
  5. Final Clustering: After a few iterations, the views converge toward a shared clustering structure. A final $k$-means step is performed on the refined embeddings.

What’s new: Unlike previous multi-view methods that require complex weight parameters or specific bipartite graph constructions, this method is "mathematically clean" and parameter-free.

Datasets

The authors evaluated their approach on five diverse datasets:

  • Synthetic Data: A three-view dataset generated from Gaussian mixture models.
  • Reuters Multilingual Data: Documents written in English, French, and German (each language is a view).
  • UCI Handwritten Digits: Images represented by two views: Fourier coefficients and profile correlations.
  • BBC and BBCSPORTS: News articles segmented into two random parts to simulate multi-view data.

Key Insights and Ideas

  • The Power of Agreement: The core "aha moment" is that the top eigenvectors of a graph Laplacian contain the most discriminative information for clustering. By projecting one view's similarity matrix onto another view's eigenvectors, you essentially "keep the signal and toss the noise."
  • Low-Rank Efficiency: The modified similarity matrices produced during the iterations are low-rank (specifically rank $2k$, where $k$ is the number of clusters). This makes the algorithm computationally efficient for large-scale problems because SVD (Singular Value Decomposition) is much faster on low-rank matrices.
  • No Hyperparameters: One of the biggest headaches in unsupervised learning is tuning parameters (like weights for different views). This algorithm requires none, making it highly practical for real-world deployment.

Key Results

The co-training approach consistently outperformed several strong baselines, including Feature Concatenation, Kernel Addition, and Canonical Correlation Analysis (CCA).

Performance comparison across methods
  • Accuracy/NMI: On the Reuters dataset, the co-trained approach achieved an NMI (Normalized Mutual Information) of ~0.38, significantly higher than the best single view (~0.28) or feature concatenation (~0.29).
  • Convergence: The algorithm converges very quickly. In most experiments, the biggest performance gain happened in the very first iteration, and the scores stabilized within 4 to 20 iterations.
NMI score convergence over iterations
  • Robustness: Even when one view was significantly "noisier" than the others, the co-training process helped the weaker view improve by leveraging the structure of the stronger view.

Limitations and Future Work

  • The Compatibility Assumption: The algorithm relies on the assumption that all views share the same underlying cluster structure. If the views represent fundamentally different ways of grouping the data (e.g., clustering people by "language spoken" vs. "geographic location"), this method might struggle.
  • Missing Data: The current framework assumes every data point is present in every view. The authors suggest that missing views could be handled by averaging similarities from available views, but this wasn't tested extensively in the paper.
  • Theoretical Convergence: While the algorithm performs well empirically, the authors note that it isn't mathematically guaranteed to converge to a global optimum (a common trait among co-training style algorithms). Further theoretical analysis is flagged as a direction for future research.

Summary updated

Abstract

We propose a spectral clustering algorithm for the multi-view setting where we have access to multiple views of the data, each of which can be independently used for clustering. Our spectral clustering algorithm has a flavor of co-training, which is already a widely used idea in semi-supervised learning. We work on the assumption that the true underlying clustering would assign a point to the same cluster irrespective of the view. Hence, we constrain our approach to only search for the clusterings that agree across the views. Our algorithm does not have any hyperparameters to set, which is a major advantage in unsupervised learning. We empirically compare with a number of baseline methods on synthetic and real-world datasets to show the efficacy of the proposed algorithm.
BibTeX
@inproceedings{kumar2011co,
  author = {Abhishek Kumar and Hal Daumé III},
  title = {{A Co-training Approach for Multi-view Spectral Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2011},
  url = {https://openreview.net/forum?id=ryVFpqbObr},
}
Figure