# ADS: Approximate Densest Subgraph for Novel Image Discovery

arXiv: https://arxiv.org/abs/2402.08743 · HTML: https://mlsanity.com/paper/2402.08743/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 36 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 5 of 5)

- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Salient Object Detection in the Deep Learning Era: An In-Depth Survey](https://mlsanity.com/paper/1904.09146/) (2019)
- [Convergence of Stochastic Gradient Descent for PCA](https://mlsanity.com/paper/1509.09002/) (2015)
- [Defining Image Memorability using the Visual Memory Schema](https://mlsanity.com/paper/1903.02056/) (2019)
- [Is Image Memorability Prediction Solved?](https://mlsanity.com/paper/1901.11420/) (2019)

## Abstract (arXiv)

The volume of image repositories continues to grow. Despite the availability of content-based addressing, we still lack a lightweight tool that allows us to discover images of distinct characteristics from a large collection. In this paper, we propose a fast and training-free algorithm for novel image discovery. The key of our algorithm is formulating a collection of images as a perceptual distance-weighted graph, within which our task is to locate the K-densest subgraph that corresponds to a subset of the most unique images. While solving this problem is not just NP-hard but also requires a full computation of the potentially huge distance matrix, we propose to relax it into a K-sparse eigenvector problem that we can efficiently solve using stochastic gradient descent (SGD) without explicitly computing the distance matrix. We compare our algorithm against state-of-the-arts on both synthetic and real datasets, showing that it is considerably faster to run with a smaller memory footprint while able to mine novel images more accurately.