Guided Similarity Separation for Image Retrieval

Chundi Liu, Guang Wei Yu, Maksims Volkovs, Cheng Chang, Himanshu Rai, Junwei Ma, Satya Krishna GortiNeurIPS 2019 · OpenReview

This NeurIPS 2019 paper from the team at Layer6 AI introduces a novel approach to image retrieval that moves beyond simple descriptor matching and hand-tuned refinement techniques. By combining Graph Convolutional Networks (GCNs) with a clever unsupervised loss function, the authors demonstrate how to "learn" a better search space that significantly outperforms existing state-of-the-art methods.

TL;DR

The paper proposes Guided Similarity Separation (GSS), an unsupervised method that uses Graph Convolutional Networks to bake neighborhood information directly into image descriptors. By applying a novel "separation" loss that pushes similar images closer and dissimilar ones further apart, GSS creates a refined descriptor space that achieves up to a 24% relative improvement in retrieval accuracy while remaining highly efficient for large-scale search.

What Problem Does This Paper Address?

Image retrieval—finding images in a database that are "the same" as a query image—is notoriously difficult because of variations in lighting, camera angles, and occlusions.

Standard systems usually work in two stages:

  1. Initial Retrieval: Convert images into compact vectors (descriptors) and find the nearest neighbors using simple math (inner products).
  2. Refinement: Use the "manifold structure" of the data. If Image A is similar to B, and B is similar to C, then A and C are likely related even if they look different. Techniques like Query Expansion (QE) or Diffusion are typically used here.

The Gap: Most refinement techniques are "hard-coded" heuristics with hand-tuned parameters. They don't learn from the data; they just traverse a pre-defined graph. This limits their representational power and often makes them slow or difficult to scale to millions of images.

Methods

The authors introduce two main components to bridge this gap:

1. GCN-based Descriptor Encoding

Instead of treating images as isolated points, the authors use a Graph Convolutional Network (GCN). The GCN takes the initial image descriptors and an adjacency matrix (representing the $k$-nearest neighbors) as input. This allows the model to "smooth" descriptors by aggregating information from their neighbors, effectively learning how to perform a more sophisticated version of Query Expansion.

2. Guided Similarity Separation (GSS) Loss

This is the "secret sauce." The authors propose an unsupervised loss function designed to polarize similarities.

  • The Logic: They assume that if two images have a high initial similarity, they are likely a "match," and if they have low similarity, they are likely "non-matches."
  • The Loss: They define a similarity threshold ($\beta$). The loss function is a quadratic curve centered at $\beta$.
  • Pairs with similarity above $\beta$ are pushed even closer together.
  • Pairs with similarity below $\beta$ are pushed further apart.
  • Pairs near $\beta$ (the "uncertain" ones) receive very little gradient, meaning the model focuses on its most confident predictions first.
Similarity separation at epoch 300, demonstrating how the GSS loss pushes matches (orange) and non-matches (blue) apart.

3. Efficient Inference

Running a GCN over a database of millions of images for every query would be too slow. The authors developed an approximate inference procedure that only considers the first and second-order neighbors of a query. This keeps the computational cost low and independent of the total database size ($n$).

Datasets

The model was evaluated on several standard, challenging benchmarks:

  • ROxford & RParis: Revised versions of the classic Oxford and Paris buildings datasets, featuring "Medium" and "Hard" evaluation protocols.
  • INSTRE: A large-scale dataset for instance-level object retrieval (toys, products, etc.).
  • ROxford-1M: A version of ROxford padded with 1 million "distractor" images to test scalability.

Key Insights and Ideas

  • Learning the Manifold: Unlike Diffusion, which just walks the graph, GSS reshapes the descriptor space. This means that after training, you can perform a simple, lightning-fast inner product search in the new space and get the benefits of complex manifold traversal.
  • Baking in Spatial Verification: Spatial verification (matching local features like corners/edges) is very accurate but incredibly slow. The authors show they can use spatial verification offline to build a better training graph. The GCN then "learns" these relationships, allowing the model to benefit from spatial verification at query time without actually performing it.
  • The Power of Polarization: By forcing the model to be more "confident" (pushing similarities toward 0 or 1), the GSS loss effectively clears out the noisy "middle ground" of the similarity distribution, making the retrieval task much cleaner.

Key Results

  • Accuracy: GSS consistently outperformed leading baselines. On the ROxford Hard dataset, it achieved a mean Average Precision (mAP) of 57.5, compared to 38.5 for the base GeM descriptors and 40.5 for the popular DFS (Diffusion) method.
  • Relative Gain: The authors reported up to a 24% relative improvement over the best-performing baselines.
  • Speed: On the 1M image dataset, GSS added only a constant overhead of ~140ms. In contrast, traditional Diffusion methods see their processing time grow significantly as the database size increases.

Limitations and Future Work

  • Initial Quality Dependency: The GSS loss relies on the initial descriptors being "reasonably good." If the starting point is too noisy, the model might confidently push the wrong images together (though the authors' initialization strategy helps mitigate this).
  • Hyperparameters: While it reduces the need for manual tuning compared to QE, it still introduces new hyperparameters like the threshold $\beta$ and the neighborhood size $k$.
  • Future Directions: The authors suggest exploring supervised versions of this loss (where labels are available) and further investigating how this approach could integrate with more complex manifold learning techniques.

Full Paper Citation: Liu, C., Yu, G., Chang, C., Rai, H., Ma, J., Gorti, S. K., & Volkovs, M. (2019). Guided Similarity Separation for Image Retrieval. 33rd Conference on Neural Information Processing Systems (NeurIPS 2019).

Summary updated

Abstract

Despite recent progress in computer vision, image retrieval remains a challenging open problem. Numerous variations such as view angle, lighting and occlusion make it difficult to design models that are both robust and efficient. Many leading methods traverse the nearest neighbor graph to exploit higher order neighbor information and uncover the highly complex underlying manifold. In this work we propose a different approach where we leverage graph convolutional networks to directly encode neighbor information into image descriptors. We further leverage ideas from clustering and manifold learning, and introduce an unsupervised loss based on pairwise separation of image similarities. Empirically, we demonstrate that our model is able to successfully learn a new descriptor space that significantly improves retrieval accuracy, while still allowing efficient inner product inference. Experiments on five public benchmarks show highly competitive performance with up to 24\% relative improvement in mAP over leading baselines. Full code for this work is available here: https://github.com/layer6ai-labs/GSS.
BibTeX
@inproceedings{liu2019guided,
  author = {Chundi Liu and Guang Wei Yu and Maksims Volkovs and Cheng Chang and Himanshu Rai and Junwei Ma and Satya Krishna Gorti},
  title = {{Guided Similarity Separation for Image Retrieval}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=eNJcd0tfAS},
}
Figure