Hybrid Affinity Propagation

Jingdong Wang, Hao Xu, Xian-Sheng Hua, Shipeng LiarXiv 2013 · arXiv

Abstract

This paper introduces Hybrid Affinity Propagation (H2MP), a novel algorithm designed to summarize large image collections by simultaneously leveraging visual features and associated text tags. By generalizing the classic Affinity Propagation algorithm to heterogeneous graphs and deriving a highly efficient scalar-message passing scheme, H2MP identifies "exemplars" that are both visually representative and semantically meaningful.

Introduction

As digital image collections on platforms like Flickr or Instagram continue to expand, providing a quick, representative overview becomes a major challenge. Existing summarization techniques typically fall into two categories: visual-only methods, which cluster images based on pixels but ignore semantic context, and text-only methods, which may select visually redundant or poor-quality images. While some joint methods exist, they often process visual and textual data sequentially, leading to information loss. H2MP addresses this by treating images and tags as interconnected entities in a single, simultaneous optimization framework.

Methodology

The authors build upon Affinity Propagation (AP), an algorithm that identifies "exemplars" within a dataset by passing messages between data points until a consensus emerges.

Heterogeneous Modeling

Unlike standard AP, which handles one type of data, H2MP models three distinct relationships: image-to-image similarity, tag-to-tag similarity, and image-to-tag associations. This structure is represented as a heterogeneous graph where nodes represent both images and semantic tags.

Message Reduction and Optimization

In a heterogeneous graph, standard message passing typically requires sending "vector" messages, which is computationally expensive. The core technical contribution of this paper is a mathematical derivation that reduces these complex vector messages into scalar messages (single numbers). This allows the algorithm to remain nearly as efficient as the original AP while handling much more complex data structures.

The message-passing framework for H2MP, enabling efficient scalar communication across image and tag nodes.

The algorithm seeks to maximize a "net similarity" that balances how well image exemplars represent the visual set, how well tag exemplars represent the semantic set, and how consistent the chosen image exemplars are with the chosen tag exemplars.

Experimental Setup

The researchers evaluated H2MP using a dataset of approximately 11,000 images crawled from Flickr across diverse queries such as "flower," "city," and "mountain." After filtering for noise, the study utilized 816 unique tags, with an average of 6.1 tags per image. Visual similarity was calculated using GIST scene descriptors, while semantic similarity between tags was determined using WordNet-based measures.

Key Results

  • Quantitative Performance: H2MP consistently outperformed standard AP, Bipartite Graph Partitioning (BGP), and Tripartite Graph Partitioning (TGP) in both "semantic exemplarness" and "visual exemplarness."
  • User Study: In a blind test with 20 participants, H2MP-generated summaries received an average score of 4.3/5, significantly higher than the next best method (3.9/5).
  • Automatic Textual Summarization: Because the algorithm identifies tag exemplars alongside image exemplars, it can automatically generate a text description for a collection. For example, for a "Great Wall of China" collection, it correctly identified specific sections like "Simatai" and "Mutianyu" as key semantic anchors.

Conclusion and Future Work

H2MP demonstrates that tags can serve as a powerful semantic bridge; if a specific tag is a strong representative for a semantic cluster, the images associated with that tag receive a "boost" in their likelihood of becoming visual exemplars. By optimizing for both modalities simultaneously, the algorithm avoids the pitfalls of sequential processing.

While the performance is dependent on the quality of underlying similarity metrics (GIST and WordNet) and user-provided metadata, the scalar reduction technique developed here holds potential for other heterogeneous data tasks, such as cross-modal retrieval or recommendation systems involving users, items, and reviews.

Summary updated

Abstract

In this paper, we address a problem of managing tagged images with hybrid summarization. We formulate this problem as finding a few image exemplars to represent the image set semantically and visually, and solve it in a hybrid way by exploiting both visual and textual information associated with images. We propose a novel approach, called homogeneous and heterogeneous message propagation ($\text{H}^\text{2}\text{MP}$). Similar to the affinity propagation (AP) approach, $\text{H}^\text{2}\text{MP}$ reduce the conventional \emph{vector} message propagation to \emph{scalar} message propagation to make the algorithm more efficient. Beyond AP that can only handle homogeneous data, $\text{H}^\text{2}\text{MP}$ generalizes it to exploit extra heterogeneous relations and the generalization is non-trivial as the reduction to scalar messages from vector messages is more challenging. The main advantages of our approach lie in 1) that $\text{H}^\text{2}\text{MP}$ exploits visual similarity and in addition the useful information from the associated tags, including the associations relation between images and tags and the relations within tags, and 2) that the summary is both visually and semantically satisfactory. In addition, our approach can also present a textual summary to a tagged image collection, which can be used to automatically generate a textual description. The experimental results demonstrate the effectiveness and efficiency of the roposed approach.
BibTeX
@misc{wang2013hybrid,
  author = {Jingdong Wang and Hao Xu and Xian-Sheng Hua and Shipeng Li},
  title = {{Hybrid Affinity Propagation}},
  year = {2013},
  eprint = {1307.7851},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1307.7851},
}
Figure