TL;DR
Standard contrastive learning relies on pairwise metrics that struggle when data is heavily class-imbalanced, leading to high intra-class variance and blurry decision boundaries for rare classes. The SCoRe (Submodular Combinatorial Representation Learning) framework reformulates metric learning through set-based submodular information measures (such as Facility Location, Graph-Cut, and Log-Determinant), ensuring clusters remain tight, diverse, and well-separated. This approach yields gains of up to 7.6% on imbalanced classification benchmarks and up to 19.4% on real-world road object detection.
What Problem Does This Paper Address?
In real-world visual recognition tasks—such as autonomous driving and medical diagnostics—data distributions are rarely balanced; a few "head" classes dominate, while critical "tail" classes appear infrequently.
Standard cross-entropy loss degrades under severe imbalance. Deep metric and contrastive learning methods (e.g., SupCon, Triplet loss) attempt to fix this by pulling positive pairs together and pushing negative pairs apart. However, because these objectives operate almost exclusively on pairwise similarities, they cannot guarantee that entire class representations form compact, globally disjoint clusters. As a result, abundant classes spread out (high intra-class variance), while rare classes get crowded and misclassified (high inter-class bias).
Methods
Instead of scoring pairs, SCoRe treats all representations of a class as a discrete set $A_k$ within a global ground set $V$. It leverages submodular set functions—mathematical functions exhibiting diminishing returns—to optimize diversity, coverage, and mutual information across clusters:
- Total Submodular Information ($S_f$) and Correlation ($C_f$): Formulates objectives using either the sum of set evaluations $\sum f(A_k)$ or the correlation across sets $\sum f(A_k) - f(\bigcup A_k)$ to simultaneously maximize intra-class compactness and inter-class separation.
- Novel Submodular Objectives:
- Facility Location (FL): Minimizes the similarity between a class set and its hardest negative features while implicitly discovering class centroids.
- Graph-Cut (GC): Jointly minimizes inter-class edge weights and maximizes intra-class edge weights.
- Log-Determinant (LogDet): Minimizes the volume spanned by samples in class $A_k$ (shrinking cluster size) while maximizing the volume across the entire dataset $V$ (expanding overall representation diversity).
- Submodular Reformulations of Existing Losses: The authors prove that common contrastive losses (Triplet, SNN, SupCon) are mathematically not submodular due to set-size normalization factors or sign conventions. By dropping or modifying these terms, they derive submodular variants: Submod-Triplet, Submod-SNN, and Submod-SupCon.
- Training Pipeline: A standard two-stage protocol: Stage 1 trains a ResNet backbone using the submodular loss; Stage 2 freezes the backbone and trains a linear classifier using cross-entropy. For object detection, the losses are integrated into the Faster-RCNN classification head.
Datasets
- CIFAR-10 (Imbalanced Variants):
- Pathological Longtail: Sample frequencies exponentially decay with a 1:10 ratio.
- Pathological Step: Exploits the superclass hierarchy by heavily subsampling animal classes relative to vehicle classes.
- MedMNIST (Naturally Imbalanced):
- OrganAMNIST: 11 distinct organ classes from 2D axial CT slices.
- DermaMNIST: 7 pigmented skin lesion categories from dermatoscopic images.
- Object Detection Benchmarks:
- India Driving Dataset (IDD): Unconstrained autonomous driving footage with severe natural tail distributions (e.g., autorickshaws, bicycles).
- LVIS (v1.0): 1,203 categories over MS-COCO images characterized by extreme class imbalance.
- Synthetic 2D Dataset: A toy 4-cluster dataset used to visualize cluster separation under changing kernel functions.
Key Insights and Ideas
- Classes are sets, not pairs: Pairwise metrics miss global set properties. Submodular functions capture cluster coverage and mutual information, providing stronger theoretical guarantees for cluster separation.
- Natural reweighting for tail classes: Facility Location inherently benefits minority classes because the negative complement set $V \setminus A_k$ is much larger for tail classes than for head classes, naturally penalizing rare-class errors more heavily without manual weighting.
- Fixing normalizations fixes representations: The normalization factor $\frac{1}{|A_k|}$ in standard Supervised Contrastive Loss (SupCon) breaks submodularity. Simply removing this normalization recovers submodularity (Submod-SupCon) and boosts accuracy across the board.
Key Results
- Imbalanced Image Classification:
- On CIFAR-10 Step, Facility Location achieves 87.49% top-1 accuracy compared to 78.10% for SupCon and 74.49% for Cross-Entropy.
- On CIFAR-10 Longtail, FL achieves 91.80% (vs. 89.96% for SupCon).
- On DermaMNIST, FL reaches 73.77% (vs. 72.12% for SupCon and 71.32% for CE).
- Reformulated submodular losses (Submod-SupCon, Submod-Triplet, Submod-SNN) consistently beat their standard counterparts by 3.5% to 4.1%.
- Real-World Object Detection:
- On IDD, Faster-RCNN + Facility Location scores 36.3 mAP (a 19.4% relative improvement over standard Faster-RCNN + FPN at 30.4 mAP, and outperforming SupCon at 31.2 mAP). Rare categories like bicycle gained up to +6.4 mAP.
- On LVIS, FL reaches 19.1 mAP vs. 14.4 mAP for SupCon and 14.2 mAP for baseline Faster-RCNN.
- Qualitative Cluster Structure:
- Confusion matrix analysis shows overall confusion on CIFAR-10 drops from ~22% with SupCon to 8.2% with Facility Location, specifically resolving semantic overlap between animal classes.
Limitations and Future Work
- Computational Overhead of Set Operations: Computing combinatorial measures like Log-Determinant matrices ($\log \det$) over large sets scales poorly with massive batch sizes.
- Hyperparameter Sensitivity: Graph-Cut performance relies heavily on tuning $\lambda$ (which must satisfy $\lambda \ge 1$ to maintain submodularity).
- Two-Stage Requirement: The framework currently relies on a decoupled two-stage training strategy (feature pretraining followed by linear probing), adding wall-clock training overhead compared to end-to-end classification.
- Domain Scope: Evaluation is limited to 2D image classification and bounding-box detection; multimodal (vision-language) and sequential data remain unexplored.
Summary updated