Unsupervised Embedding Quality Evaluation

Anton Tsitsulin, Marina Munkhoeva, Bryan Perozzi

Abstract

Self-supervised learning (SSL) has revolutionized the training of deep neural networks, yet evaluating the resulting embeddings remains a significant challenge in the absence of ground-truth labels. Traditionally, researchers rely on "linear probes"—supervised classifiers trained on top of frozen representations—to gauge quality. However, this dependency on labels limits the utility of SSL in truly unsupervised or domain-shift scenarios. This paper addresses this gap by surveying and introducing a suite of unsupervised metrics based on numerical linear algebra and high-dimensional probability. Through extensive experiments across computer vision and graph embedding domains, we demonstrate that intrinsic geometric and statistical properties of the embedding space can robustly predict downstream performance without requiring any labeled data.

Introduction: The Evaluation Paradox

The success of Self-Supervised Learning (SSL) is predicated on the ability to learn meaningful representations from raw data. Yet, the standard method for assessing these representations—linear probing—requires a labeled dataset. This creates a paradox: if sufficient labels were available for evaluation, the motivation for unsupervised learning might be diminished. Furthermore, in real-world deployments, labels are often non-existent or expensive to acquire, leaving practitioners without a "compass" for model selection or hyperparameter tuning.

This research seeks to identify intrinsic properties of the embedding space that correlate with downstream task accuracy. By treating the embedding matrix as a high-dimensional object, we can apply tools from linear algebra and probability to quantify its quality.

Proposed Unsupervised Metrics

The study evaluates four primary metrics, categorized by their mathematical foundations:

1. The Linear Classifier Perspective: $\mu_0$-Incoherence

This metric is based on the premise that a good representation should be "well-spread" across the feature space. If embeddings are too closely aligned with the standard basis or are highly concentrated, finding a stable linear separator becomes difficult. $\mu_0$-incoherence quantifies how well the data is distributed, with lower coherence suggesting a more favorable geometry for linear classification.

2. The Numerical Linear Algebra Perspective

  • Pseudo-condition Number ($\kappa_2$): This measures the stability of the representation matrix. A high condition number indicates that the system is sensitive to small perturbations, which often correlates with poor generalization.
  • Stable Rank ($r$): Also known as effective rank, this metric measures the "intrinsic dimensionality" of the data. Unlike standard rank, which is sensitive to noise, stable rank provides a robust estimate of how many dimensions the model is actually utilizing.

3. The High-Dimensional Probability Perspective: SelfCluster

We introduce SelfCluster, a novel metric that estimates the degree of clustering relative to a perfectly uniform distribution on a high-dimensional sphere. By analyzing the norm of the pairwise dot product matrix, SelfCluster detects whether a model is "collapsing" its representations into a few clusters or maintaining a rich, discriminative structure.

These metrics are compared against established baselines such as RankMe (entropy of singular values) and NESum (eigenspectrum analysis).

Experimental Methodology

To ensure the robustness of these metrics, the authors conducted experiments across two distinct domains:

  • Computer Vision: Evaluation of over 1,000 pre-trained models from the timm repository on ImageNet. This provided a massive sample size to test how metrics correlate with standard benchmarks.
  • Graph Embeddings: Testing DeepWalk embeddings across 10 diverse datasets, including citation networks (Cora, Citeseer) and co-purchase graphs (Amazon PC).
  • Robustness Testing: The study introduced "corruption benchmarks" using graph sparsification to determine if the metrics could accurately track the degradation of embedding quality as the input data became increasingly noisy.

Key Insights and Results

The "No Free Lunch" Principle

The results indicate that no single metric is a universal winner. A metric that excels in deep vision models (like NESum) may not be as effective for shallow graph models. This suggests that practitioners should employ a suite of metrics to gain a holistic view of embedding quality.

Stability and Efficiency

Computational efficiency is a critical factor for real-time monitoring during training. The study found that Stable Rank and RankMe are highly stable and can be accurately estimated with relatively small batch sizes. For example, Stable Rank can be estimated on ImageNet with 95% accuracy using only 16,384 samples, making it a viable tool for large-scale training pipelines.

Performance in Graph Domains

In the graph domain, Coherence emerged as the most reliable indicator, achieving a near-perfect Spearman rank correlation ($\rho = 0.99$) with classification accuracy. Notably, Coherence and SelfCluster were the only metrics that remained consistent across different types of graph sparsification, whereas other metrics often reversed their correlation signs depending on the corruption method.

Conclusion and Future Directions

This work demonstrates that it is possible to evaluate the quality of machine learning embeddings without relying on labels. By leveraging the geometric and statistical properties of the embedding space, we can provide practitioners with the tools necessary for unsupervised model selection.

Future research will focus on two areas: optimizing the $O(n^2)$ complexity of the SelfCluster metric to handle larger datasets and exploring the integration of these metrics directly into loss functions. By using these metrics as regularizers, it may be possible to prevent "dimensional collapse" during the training process itself, leading to more robust and discriminative representations.

Summary updated

Abstract

Unsupervised learning has recently significantly gained in popularity, especially with deep learning-based approaches. Despite numerous successes and approaching supervised-level performance on a variety of academic benchmarks, it is still hard to train and evaluate SSL models in practice due to the unsupervised nature of the problem. Even with networks trained in a supervised fashion, it is often unclear whether they will perform well when transferred to another domain. Past works are generally limited to assessing the amount of information contained in embeddings, which is most relevant for self-supervised learning of deep neural networks. This works chooses to follow a different approach: can we quantify how easy it is to linearly separate the data in a stable way? We survey the literature and uncover three methods that could be potentially used for evaluating quality of representations. We also introduce one novel method based on recent advances in understanding the high-dimensional geometric structure of self-supervised learning. We conduct extensive experiments and study the properties of these metrics and ones introduced in the previous work. Our results suggest that while there is no free lunch, there are metrics that can robustly estimate embedding quality in an unsupervised way.
BibTeX
@inproceedings{tsitsulin2023unsupervised,
  author = {Anton Tsitsulin and Marina Munkhoeva and Bryan Perozzi},
  title = {{Unsupervised Embedding Quality Evaluation}},
  booktitle = {TAG-ML},
  year = {2023},
  url = {https://openreview.net/forum?id=6KOxzkLull},
}
Figure