Delving into Spectral Clustering with Vision-Language Representations

1. Problem Statement

Spectral Clustering (SC) is a powerful unsupervised technique that reformulates clustering as a graph partitioning problem, utilizing the spectrum of the graph Laplacian to find low-dimensional embeddings. However, existing SC methods face two critical limitations:

1. Single-Modality Constraint: Most approaches rely solely on visual features. When images are visually similar but semantically distinct (e.g., different breeds of dogs or different textures), visual-only affinity graphs fail to capture the true semantic structure, leading to sub-optimal clustering.
2. Ineffective Multi-Modal Integration: While Vision-Language Models (VLMs) like CLIP provide rich semantic representations, simply concatenating image and text features or using standard kernels (e.g., RBF) on these features does not sufficiently leverage the cross-modal alignment. Previous attempts (e.g., TAC) showed that naive feature-level incorporation yields performance comparable to K-Means, failing to improve the affinity graph structure required for effective spectral clustering.

Core Research Question: How can we effectively integrate textual semantics with visual similarities to construct a high-quality affinity matrix for spectral clustering in an unsupervised setting?

2. Methodology

The authors propose Neural Tangent Kernel Spectral Clustering (NTK-SC), a framework that leverages the Neural Tangent Kernel (NTK) to couple visual proximity with semantic overlap. The method consists of two main stages:

A. NTK-Based Affinity Construction

Instead of using standard distance metrics, the authors define the affinity between two images based on the interaction of their features with a set of "positive nouns" (semantic anchors) via the NTK.

1. Semantic Anchors: A set of positive nouns $\{\hat{c}_1, \dots, \hat{c}_N\}$ is selected from large-scale lexical databases (e.g., WordNet) that are semantically relevant to the dataset but do not require ground-truth class labels.
2. Proxy Network & NTK: A proxy network $g_\theta$ is defined using a log-sum-exp form to map image features to a scalar value based on the positive nouns. The weights of this network are anchored by the text embeddings of the positive nouns ($W$).
   $$g_{\theta_0}(f_X(x_i)) = \log \sum_{k=1}^N e^{w_k^\top f_X(x_i) / \tau}$$
3. Affinity Formulation: The affinity $A_{NTK}[i, j]$ between two images is computed as the NTK of the proxy network evaluated on their image features. Theoretical analysis shows this NTK decomposes into a multiplicative coupling of two terms:
   • Visual Proximity ($U_{ij}$): The dot product of image features in the CLIP space.
   • Semantic Overlap ($V_{ij}$): The product of softmax probabilities indicating how strongly each image aligns with the same subset of positive nouns.
     $$K_{\theta_0}(f_X(x_i), f_X(x_j)) \propto U_{ij} \cdot V_{ij}$$
     Mechanism: This multiplicative structure amplifies affinities for images that are both visually close and semantically aligned (high intra-cluster), while suppressing affinities for images that are visually close but semantically distinct (low inter-cluster), thereby sharpening the block-diagonal structure of the affinity matrix.

B. Regularized Affinity Diffusion (RAD)

To handle multiple prompt templates (e.g., "a photo of a {}", "art of a {}"), the method employs an adaptive ensemble mechanism rather than simple averaging.

• Objective: Learn optimal weights $\beta$ for multiple prompt-specific affinity matrices $A^{(b)}_{NTK}$ to construct a robust final affinity matrix $\hat{A}$.
• Optimization: The problem is formulated as a joint optimization of the ensemble weights and the diffusion process:
  $$\min_{\beta, \hat{A}} \sum_{b=1}^B \beta[b] \cdot \ell(\hat{A}, A^{(b)}_{NTK}) + \mu \|\hat{A} - E\|_F^2 + \frac{\lambda}{2} \|\beta\|_2^2$$
  where $\ell$ is the affinity diffusion loss, and $E$ is a regularization matrix (identity) to prevent over-smoothing.
• Solution: The non-convex problem is solved via an alternating iterative scheme:
  1. Fix $\beta$, optimize $\hat{A}$: Solved via a closed-form solution or efficient iterative solver involving Kronecker products.
  2. Fix $\hat{A}$, optimize $\beta$: Solved using a coordinate descent method (Lasso-style optimization).

3. Key Contributions

1. Novel Framework: Introduces the first spectral clustering method that explicitly leverages the Neural Tangent Kernel to integrate vision-language representations, moving beyond single-modal paradigms.
2. Theoretical Insight: Demonstrates that the NTK-based affinity formulation naturally creates a multiplicative coupling of visual and semantic signals, theoretically guaranteeing the suppression of spurious cross-cluster connections and the enhancement of block-diagonal structures.
3. Adaptive Ensemble: Proposes Regularized Affinity Diffusion (RAD), a principled method to adaptively ensemble multiple prompt-induced affinity matrices, outperforming naive averaging.
4. Comprehensive Validation: Extensive experiments on 16 benchmarks (including classical, large-scale, fine-grained, and domain-shifted datasets) demonstrate state-of-the-art performance.

4. Experimental Results

The method was evaluated against 20+ baselines (including TAC, SIC, SCAN, and various deep clustering methods) across diverse datasets.

• Classical Datasets: On ImageNet-Dogs, the method achieved 98.3% ACC and 84.9% ACC (NMI/ARI), outperforming the previous state-of-the-art TAC by 3.8% and 9.8% respectively. On STL-10, it achieved 95.8% NMI and 98.3% ACC.
• Challenging Datasets: On UCF-101 and ImageNet-1K, the method surpassed TAC by significant margins (e.g., +7.7% ACC on UCF-101, +6.3% ACC on ImageNet-1K).
• Fine-Grained & Domain Shift:
  • Fine-Grained: Outperformed TAC by 5.1% on the Pets dataset.
  • Domain Shift: Demonstrated superior robustness on ImageNet-C, ImageNet-V2, and ImageNet-S, maintaining higher performance than baselines under distribution shifts.
• Ablation Studies:
  • NTK vs. Standard Kernels: Replacing the NTK with RBF or Linear kernels on the same features resulted in significant performance drops, validating the necessity of the NTK formulation.
  • RAD Mechanism: The proposed RAD significantly outperformed both naive averaging and simple prompt ensembling (PE), confirming the value of adaptive weight learning.
  • Hyperparameters: The method remained stable across a wide range of temperature ($\tau$) and neighbor count ($q$) values.

5. Significance

This paper represents a paradigm shift in unsupervised image clustering by successfully bridging the gap between vision-language pre-training and spectral clustering.

• Theoretical Advancement: It provides a rigorous mathematical justification (via NTK) for why combining visual and textual modalities improves clustering, specifically by enhancing the graph structure's block-diagonal properties.
• Practical Impact: The method achieves state-of-the-art results without requiring labeled data or complex training loops for the clustering objective itself (relying on pre-trained CLIP and a lightweight optimization for affinity diffusion).
• Future Direction: It establishes a new baseline for multi-modal unsupervised learning, suggesting that leveraging the "semantic structure" of language models via kernel methods is a promising avenue for improving representation learning in computer vision.

Code Availability: The authors have released the source code to ensure reproducibility.