D2 Pruning: Message Passing for Balancing Diversity and Difficulty in
  Data Pruning
Adyasha Maharana Prateek Yadav Mohit Bansal
Analytical theories suggest that higher-quality data can lead to lower test
errors in models trained on a fixed data budget. Moreover, a model can be
trained on a lower compute budget without compromising performance if a dataset
can be stripped of its redundancies. Coreset selection (or data pruning) seeks
to select a subset of the training data so as to maximize the performance of
models trained on this subset, also referred to as coreset. There are two
dominant approaches: (1) geometry-based data selection for maximizing data
diversity in the coreset, and (2) functions that assign difficulty scores to
samples based on training dynamics. Optimizing for data diversity leads to a
coreset that is biased towards easier samples, whereas, selection by difficulty
ranking omits easy samples that are necessary for the training of deep learning
models. This demonstrates that data diversity and importance scores are two
complementary factors that need to be jointly considered during coreset
selection. We represent a dataset as an undirected graph and propose a novel
pruning algorithm, D2 Pruning, that uses forward and reverse message passing
over this dataset graph for coreset selection. D2 Pruning updates the
difficulty scores of each example by incorporating the difficulty of its
neighboring examples in the dataset graph. Then, these updated difficulty
scores direct a graph-based sampling method to select a coreset that
encapsulates both diverse and difficult regions of the dataset space. We
evaluate supervised and self-supervised versions of our method on various
vision and language datasets. Results show that D2 Pruning improves coreset
selection over previous state-of-the-art methods for up to 70% pruning rates.
Additionally, we find that using D2 Pruning for filtering large multimodal
datasets leads to increased diversity in the dataset and improved
generalization of pretrained models.