I Spy with My Little Eye a Minimum Cost Multicut Investigation of Dataset Frames

Katharina Prasse, Isaac Bravo, Stefanie Walter, Margret Keuper

Introduction

In social science, "visual framing analysis" is a critical method used to understand how complex issues—from climate change to political movements—are visually represented in public discourse. Traditionally, this process is labor-intensive, often requiring human researchers to manually annotate tens of thousands of images. While automated clustering offers a solution, standard techniques like k-means are limited by the need to pre-specify the number of clusters ($k$), which can introduce significant researcher bias and obscure novel, unexpected frames.

This paper presents a novel approach that redefines image clustering as a Minimum Cost Multicut Problem (MP). By leveraging state-of-the-art vision foundation models, this method automatically discovers social categories without requiring manual labels or a pre-defined cluster count.

The Multicut Approach

The core of the proposed method is the formulation of clustering as a graph partitioning problem. Every image in a dataset is represented as a node in a fully connected graph, where edges are weighted based on the cosine similarity of their embeddings.

Figure 1: Plate diagram representing the probabilistic structure of the clustering problem, where individual image features $x_e$ influence edge labels $y_e$, ultimately determining the global partition $\mathcal{Y}$.

Unlike traditional algorithms, the MP objective naturally determines the optimal number of clusters. It seeks to "cut" edges to minimize total cost: positive weights (high similarity) encourage images to stay together, while negative weights (low similarity) encourage separation. This allows the data itself to dictate the granularity of the discovered frames.

Foundation Models and the "Narrow Cone" Effect

The effectiveness of the MP approach depends heavily on the underlying image embeddings. The authors evaluated several foundation models, including DINOv2 and ConvNeXt V2. A significant challenge identified is the "narrow cone" effect, where models produce embeddings that occupy a very small portion of the vector space, leading to artificially high similarity scores.

To counter this, the authors introduced a calibration term ($c$) to adjust the decision boundary of the edge weights. This calibration is essential for balancing cluster purity against over-segmentation.

Figure 5: Entropy analysis for ConvNeXt V2 (IN) showing the trade-off between cluster purity ($H(Class|Cluster)$) and class fragmentation ($H(Cluster|Class)$) across different calibration values $c$.

Key Insights and Results

The study revealed distinct "personalities" among vision models. DINOv2 excels at identifying broad, high-level categories like "nature" or "people." In contrast, ConvNeXt V2 demonstrates a higher sensitivity to fine-grained semantic differences, successfully distinguishing between "political speeches" and "protest crowds"—categories that often share similar visual elements but represent different social frames.

When applied to the ClimateTV dataset (images from Twitter/X regarding climate change), the MP approach successfully identified a wide array of frames, from renewable energy infrastructure to flood victims. Notably, the method's ability to operate without a fixed $k$ allowed it to surface "outlier" clusters—unique visual representations that might have been overlooked by human coders using a pre-defined schema.

Conclusion

By combining the mathematical rigor of the Minimum Cost Multicut Problem with the semantic power of vision foundation models, this research provides a robust tool for automated social science. While computational complexity remains a hurdle for very large datasets, the ability to discover frames without prior labels or cluster counts marks a significant step toward unbiased, large-scale visual discourse analysis. Future work will explore multi-stage clustering to combine the strengths of different model architectures.

Summary updated

Abstract

Visual framing analysis is a key method in social sciences for determining common themes and concepts in a given discourse. To reduce manual effort, image clustering can significantly speed up the annotation process. In this work, we phrase the clustering task as a Minimum Cost Multicut Problem [MP]. Solutions to the MP have been shown to provide clusterings that maximize the posterior probability, solely from provided local, pairwise probabilities of two images belonging to the same cluster. We discuss the efficacy of numerous embedding spaces to detect visual frames and show its superiority over other clustering methods. To this end, we employ the climate change dataset ClimateTV which contains images commonly used for visual frame analysis. For broad visual frames, DINOv2 is a suitable embedding space, while ConvNeXt V2 returns a larger number of clusters which contain fine-grain differences, i.e. speech and protest. Our insights into embedding space differences in combination with the optimal clustering - by definition - advances automated visual frame detection. Our code can be found at https://github. com/KathPra/MP4VisualFrameDetection.
BibTeX
@inproceedings{prasse2025i,
  author = {Katharina Prasse and Isaac Bravo and Stefanie Walter and Margret Keuper},
  title = {{I Spy with My Little Eye a Minimum Cost Multicut Investigation of Dataset Frames}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2025},
  doi = {10.1109/wacv61041.2025.00214},
}
Figure