Mining on Manifolds: Metric Learning without Labels

1. Introduction

• Deep metric learning commonly still uses class labels, while conventional manifold-learning methods are unsupervised but often lack an explicit mapping that generalizes to new data.The paper frames its approach as bridging these limitations.Source: §1 · p. 1
• The approach mines hard training examples from an unordered collection of task-relevant images and uses random-walk manifold similarity to exploit unlabeled data.The framework is described as fully unsupervised.Source: §1 · p. 1
• Manifold neighbors that are not Euclidean neighbors are positive examples, while Euclidean neighbors absent from the manifold neighborhood are negative examples.The learned representation attracts positives to the anchor and repels negatives.Source: §1 · p. 1
• The learned representation avoids the additional query-time computational and memory requirements of manifold-similarity estimation and generalizes to unseen queries and datasets.The paper states both benefits in comparison with using the estimated manifold similarity directly.Source: §1 · p. 2
• The method is applied to fine-grained classification and particular object retrieval, where its unsupervised fine-tuned models are on par with or outperform prior supervised models.The comparison includes prior models that use human supervision or additional domain-specific expertise.Source: §1 · p. 2

2. Related work

• Deep metric-learning methods use hard-negative mining, but sampling negatives from different labeled classes can introduce mislabeled images; later approaches still use labels during sampling.Semi-hard mining, distance-weighted sampling, and batch-level or global-distribution methods address aspects of sampling or loss design.Source: §2 · p. 2
• Instance-retrieval approaches use geometric matching to mine pairs, requiring costly local-feature preprocessing and training sets suited to that matching.The paper says its method requires neither those assumptions nor an additional computer-vision mining system, assuming instead multiple object instances in the training set.Source: §2 · p. 2
• Prior unsupervised deep metric-learning methods use clustering and dataset splitting without modeling the underlying manifold, while this method supports any loss requiring positive and negative samples.The cited approaches exploit mutual proximity or ranking in Euclidean space.Source: §2 · p. 2
• Pai et al. [37] encourage embedding-space Euclidean distances to equal graph geodesic distances; this method instead uses a more scalable manifold similarity and a relaxed objective compatible with most metric-learning formulations and loss functions.Li et al. is described as similar in using a graph-based mining approach; the paper reports that hard-example selection is essential and improves performance for its own approach.Source: §2 · pp. 2–3
• Fast spectral ranking on manifolds is dataset-specific and does not generalize to unseen images; iterative manifold embedding extends handling to queries but can be affected by larger datasets.The paper says that a larger dataset significantly affects the manifold structure in the iterative approach.Source: §2 · p. 3

3.1. Problem formulation

• The method starts from unlabeled items and available features, learning an embedding that places visually matching items nearby and separates non-matching items without requiring labels.The input features may come from the identity mapping, an initial model, or another model.Source: §3.1 · p. 3

3.2. Preliminaries

• Manifold similarity is computed by random walks on a reciprocal k-nearest-neighbor graph, providing a neighborhood measure alongside Euclidean similarity.The graph is sparse and symmetric, and its similarity matrix is dense but computed by columns as needed.Source: §3.2 · p. 3

3.3. Manifold-guided selection of training samples

• Positives are manifold neighbors absent from the Euclidean neighborhood, while negatives are Euclidean neighbors absent from the manifold neighborhood.The positive pool is ordered by manifold similarity and the negative pool by Euclidean similarity; k controls positive diversity and hardness.Source: §3.3 · p. 4
• Anchors are selected as high-probability local maxima of the graph’s stationary distribution, favoring relevant and diverse training anchors.The stationary distribution is estimated by power iteration, and a fixed number of local maxima with the greatest probability are retained.Source: §3.3 · p. 4

3.4. Training

• Training combines anchors and their mined pools in shared-weight network branches, using contrastive or triplet loss with positives sampled randomly and hard negatives sampled using the current embedding.The pools are computed once initially; a weighted loss can down-weight tuples whose positive is too hard, and the graph and pools may be updated iteratively.Source: §3.4 · pp. 4–5

4. Applications

• The method learns visual representations for fine-grained categorization and instance-based image retrieval, with both features and the initial model based on pretrained models and no labeled images assumed available.Source: §4 · p. 5

4.1. Fine-grained categorization

• On CUB200-2011, the method uses GoogLeNet features, a 64-dimensional embedding, triplet loss, and all 6,000 training images as anchors.The training split contains 100 bird species, with the remaining 100 reserved for testing.Source: §4.1 · p. 5

4.2. Particular object retrieval

• Particular-object retrieval uses 1 million sampled Flickr images and fine-tunes a VGG-based MAC representation with contrastive loss.The complete training pool has 50,000 images, with 1,000 anchors selected per epoch; mined positives span more challenging changes and mined negatives include visually similar different objects.Source: §4.2 · pp. 6–7

4.3. Implementation details

• Implementation uses a 30-neighbor graph, 50 positive neighbors, and at most 50 negatives per anchor, with negative-pool search sizes differing by task.Training runs for 100 epochs for fine-grained categorization and 30 for retrieval.Source: §4.3 · p. 7

5.1. Impact of positives, negatives, and anchors

• Without supervision, the method improves the pretrained network on both tasks, and weighted loss consistently helps.The experiments compare choices of anchors and positive and negative pools.Source: §5.1 · pp. 7–8
• CUB pool diagnostics report 40% true positives and 96% true negatives; oracle-positive and oracle-negative training yield Recall@1 of 46.7 and 36.5, respectively.The passage attributes the advantage of mined hard negatives over annotated hard negatives to 4.4% annotation error in CUB.Source: §5.1 · p. 8

5.2. Comparisons on fine-grained categories

• On CUB200-2011, the method competes with or outperforms fully supervised methods and surpasses the unsupervised competitor Li et al..Li et al. has a higher true-positive rate, but its positive pairs are mostly extremely similar and not challenging enough for training.Source: §5.2 · p. 8

5.3. Comparisons on retrieval

• The method improves over the pretrained network on every retrieval test set and outperforms Radenovic et al. except on Oxford5k.It also performs better on Holidays and Instre, where shows little improvement or is inferior to the pretrained network.Source: §5.3 · p. 8, Table 3 · p. 8

• The method learns fine-grained similarity without discrete category-level labels, avoiding expensive or nearly impossible manual annotation.Source: §6 · p. 8
• Manifold-aware sampling attracts points on the same manifold and repels points on different manifolds during metric learning.Source: §6 · p. 8
• The approach works with standard contrastive and triplet losses and is effective for fine-grained categorization and particular object retrieval.It competes with or surpasses fully supervised approaches.Source: §6 · p. 8