I spy with my little eye a minimum cost multicut investigation of dataset frames

Prasse Katharina, Bravo Isaac, Walter Stefanie, Keuper Margret

TL;DR

This paper introduces a novel approach to automate visual frame analysis in social science research by framing image clustering as a Minimum Cost Multicut (MP) problem. By leveraging powerful vision foundation models for image embeddings, they demonstrate a more robust and less biased method for identifying common themes in visual datasets, outperforming traditional clustering techniques.

What Problem Does This Paper Address?

Visual frame analysis is a crucial method in social sciences for understanding the recurring themes and concepts within visual data. However, manually annotating large image datasets is time-consuming and labor-intensive. While automated methods exist, they often rely on pre-defined frames, introducing bias. This paper tackles the challenge of automating visual frame detection in a way that is less biased, more efficient, and capable of discovering novel frames. They aim to bridge the gap between manual annotation effort and the need for scalable, data-driven insights from visual discourse.

Methods

The core of this work lies in formulating image clustering as a Minimum Cost Multicut (MP) problem. In this framework, each image is treated as a node in a graph, and the edges are weighted based on the similarity of image embeddings. The MP then finds a partitioning (clustering) of these nodes that minimizes a cost function, which is directly related to maximizing the posterior probability of the clustering.

Key methodological aspects include:

  • Minimum Cost Multicut (MP) Formulation: This probabilistic approach allows for clusterings that maximize the posterior probability without requiring manual hyperparameter tuning for the clustering itself.
  • Foundation Model Embeddings: The authors explore various powerful vision foundation models (e.g., DINOv2, ConvNeXt V2, CLIP ViT-B/32, ResNet-50) to generate image embeddings. The quality and characteristics of these embeddings significantly influence the clustering results.
  • Graph Construction: A fully connected graph is built where edge weights are derived from the cosine similarity of image embeddings. These similarities are then normalized and transformed to represent the likelihood of images belonging to the same cluster.
  • Solver Implementation: Efficient heuristics like Greedy Additive Edge Contraction (GAEC) and Kernighan-Lin (KL) algorithms are used to solve the MP problem.
  • Calibration Term (cal): A crucial step involves determining an optimal "calibration term" for each embedding space. This term helps to adjust the edge weights based on the distribution of cosine similarities, ensuring that the MP formulation accurately reflects the underlying data structure.

Datasets

The paper utilizes several datasets for training, validation, and evaluation:

  • ImageNette and ImageWoof: These datasets are used for determining the optimal calibration term (cal) for each embedding space. ImageNette is used for broad concepts, and ImageWoof for fine-grained concepts.
  • OmniBenchmark: This dataset is used to measure how many realms and concepts the assessed embedding spaces can distinguish between, providing insights into their generality.
  • ClimateTV: This dataset, collected from social media related to climate change, is the primary benchmark for demonstrating the effectiveness of their automated visual frame detection approach. It contains diverse images related to protests, conferences, climate solutions, and consequences.

Key Insights and Ideas

  • MP as a Probabilistic Clustering Framework: Framing clustering as an MP problem provides a theoretically sound way to maximize the posterior probability of a clustering, offering a principled alternative to heuristic methods.
  • Embedding Space Matters: The choice of embedding model has a profound impact on the resulting clusterings. Different models capture different aspects of visual information, leading to varying levels of granularity and semantic coherence in the clusters.
  • DINOv2 for Broad Frames, ConvNeXt V2 for Fine-Grained: DINOv2 embeddings are found to be suitable for identifying broad visual frames, while ConvNeXt V2 excels at capturing fine-grained differences, such as distinguishing between "speech" and "protest."
  • Narrow Cone Effect: Many embedding spaces exhibit a "narrow cone effect," where embeddings with high cosine similarity occupy a small portion of the embedding space. This phenomenon influences the choice of the calibration term.
  • Calibration Term is Crucial: The optimal calibration term (cal) is dependent on the embedding space's distribution. Models with more Gaussian-like distributions require less calibration, while those with more skewed distributions or narrow cones need higher cal values.
  • Multimodal Clustering Potential: While not the primary focus, the paper briefly explores multimodal clustering using image and text, suggesting future avenues for research.

Key Results

  • Automated Visual Frame Detection: The proposed MP-based clustering method successfully automates visual frame detection, providing meaningful clusters on the ClimateTV dataset.
  • Performance Comparison: The paper compares various embedding models, showing that DINOv2 and ConvNeXt V2 offer distinct advantages for different types of frame analysis (broad vs. fine-grained).
  • VI Metrics: Variation of Information (VI) is used to quantify the disagreement between clusterings. CLIP ViT-B/32 consistently shows the most distinct clustering results across datasets.
  • ClimateTV Cluster Characteristics: ClimateTV clusterings are diverse. ConvNeXt V2 produces clusters with specific semantic concepts, while DINOv2 captures broader themes. ResNet-50 embeddings show a shape bias.
  • Solver Efficacy: The combination of GAEC and KL solvers for the MP problem yields lower costs and fewer clusters, indicating improved efficiency.

Limitations and Future Work

  • Computational Cost: The MP formulation, especially with large datasets and complex embedding spaces, can be computationally intensive.
  • Modality Gap: The paper acknowledges the "modality gap" in multimodal clustering, where image and text embeddings might not be perfectly aligned.
  • Future Work: The authors suggest investigating inter- and intra-embedding model multi-stage clustering as a promising direction for further improving noise reduction and cluster quality. They also plan to explore the impact of different calibration strategies and embedding spaces more deeply.

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{katharina2025i,
  author = {Prasse Katharina and Bravo Isaac and Walter Stefanie and Keuper Margret},
  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