The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph

• URL: http://arxiv.org/abs/2410.12458v2
• Date: Mon, 26 May 2025 19:41:16 GMT
• Title: The Best of Both Worlds: Bridging Quality and Diversity in Data Selection with Bipartite Graph
• Authors: Minghao Wu, Thuy-Trang Vu, Lizhen Qu, Gholamreza Haffari,
• Abstract summary: We present GraphFilter, a novel approach that balances both quality and diversity in data selection.<n>GraphFilter iteratively selects sentences with the highest priority, removes covered n-grams from the bipartite graph, and recomputes priorities to reflect the changing data landscape.<n>We validate GraphFilter using three model backbones across six widely-used benchmarks, demonstrating that it outperforms nine existing baselines in both model performance and computational efficiency.
• Score: 45.51085356985464
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The performance of large language models (LLMs) is strongly influenced by the quality and diversity of data used during supervised fine-tuning (SFT). However, current data selection methods often prioritize one aspect over the other, resulting in suboptimal training outcomes. To address this, we formulate data selection as a set cover problem and present GraphFilter, a novel approach that balances both quality and diversity in data selection. GraphFilter models the dataset as a bipartite graph connecting sentences to their constituent n-grams, then employs a priority function that combines quality and diversity metrics multiplicatively. GraphFilter iteratively selects sentences with the highest priority, removes covered n-grams from the bipartite graph, and recomputes priorities to reflect the changing data landscape. We validate GraphFilter using three model backbones across six widely-used benchmarks, demonstrating that it outperforms nine existing baselines in both model performance and computational efficiency. Further analysis shows that our design choices lead to more effective subset selection, underscores the value of instruction diversity, and provides insights into how quality and diversity interact with different subset sizes.

Related papers

• Investigating the Impact of Data Selection Strategies on Language Model Performance [1.0013553984400492]
  This study explores the effects of different data selection methods and feature types on model performance. We evaluate whether selecting data subsets can influence downstream tasks, whether n-gram features improve alignment with target distributions, and whether embedding-based neural features provide complementary benefits.
  arXiv  Detail & Related papers  (2025-01-07T14:38:49Z)
• Unleashing the Power of LLMs as Multi-Modal Encoders for Text and Graph-Structured Data [42.18348019901044]
  Graph-structured information offers rich contextual information that can enhance language models. Existing methods for integrating graph and text embeddings are limited in their ability to fully exploit the heterogeneous nature of these modalities. We propose Janus, a framework that leverages Large Language Models (LLMs) to jointly encode text and graph data.
  arXiv  Detail & Related papers  (2024-10-15T03:40:20Z)
• Adapt-$\infty$: Scalable Continual Multimodal Instruction Tuning via Dynamic Data Selection [89.42023974249122]
  Adapt-$infty$ is a new multi-way and adaptive data selection approach for lifelong instruction tuning.<n>We construct pseudo-skill clusters by grouping gradient-based sample vectors.<n>We select the best-performing data selector for each skill cluster from a pool of selector experts.<n>This data selector samples a subset of the most important samples from each skill cluster for training.
  arXiv  Detail & Related papers  (2024-10-14T15:48:09Z)
• Diversify and Conquer: Diversity-Centric Data Selection with Iterative Refinement [8.509688686402438]
  Finetuning large language models on instruction data is crucial for enhancing pre-trained knowledge and improving instruction-following capabilities. This work addresses the question: How can we determine the optimal subset of data for effective training? Our method employs k-means clustering to ensure the selected subset effectively represents the full dataset.
  arXiv  Detail & Related papers  (2024-09-17T17:25:31Z)
• ScalingFilter: Assessing Data Quality through Inverse Utilization of Scaling Laws [67.59263833387536]
  ScalingFilter is a novel approach that evaluates text quality based on the perplexity difference between two language models trained on the same data. To assess the bias introduced by quality filtering, we introduce semantic diversity, a metric of utilizing text embedding models for semantic representations.
  arXiv  Detail & Related papers  (2024-08-15T17:59:30Z)
• TAGCOS: Task-agnostic Gradient Clustered Coreset Selection for Instruction Tuning Data [29.45013725650798]
  It is essential to extract a subset of instruction datasets that achieves comparable performance to the full dataset. We propose Task-Agnostic Gradient Clustered COreset Selection (TAGCOS) Specifically, we leverage sample gradients as the data representations, perform clustering to group similar data, and apply an efficient greedy algorithm for coreset selection.
  arXiv  Detail & Related papers  (2024-07-21T17:59:20Z)
• LESS: Selecting Influential Data for Targeted Instruction Tuning [64.78894228923619]
  We propose LESS, an efficient algorithm to estimate data influences and perform Low-rank gradiEnt Similarity Search for instruction data selection. We show that training on a LESS-selected 5% of the data can often outperform training on the full dataset across diverse downstream tasks. Our method goes beyond surface form cues to identify data that the necessary reasoning skills for the intended downstream application.
  arXiv  Detail & Related papers  (2024-02-06T19:18:04Z)
• Diversity Measurement and Subset Selection for Instruction Tuning Datasets [40.930387018872786]
  We use determinantal point processes to capture the diversity and quality of instruction tuning datasets for subset selection. We propose to measure dataset diversity with log determinant distance that is the distance between the dataset of interest and a maximally diverse reference dataset.
  arXiv  Detail & Related papers  (2024-02-04T02:09:43Z)
• DsDm: Model-Aware Dataset Selection with Datamodels [81.01744199870043]
  Standard practice is to filter for examples that match human notions of data quality. We find that selecting according to similarity with "high quality" data sources may not increase (and can even hurt) performance compared to randomly selecting data. Our framework avoids handpicked notions of data quality, and instead models explicitly how the learning process uses train datapoints to predict on the target tasks.
  arXiv  Detail & Related papers  (2024-01-23T17:22:00Z)
• D2 Pruning: Message Passing for Balancing Diversity and Difficulty in Data Pruning [70.98091101459421]
  Coreset selection 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. We propose a novel pruning algorithm, D2 Pruning, that uses forward and reverse message passing over this dataset graph for coreset selection. Results show that D2 Pruning improves coreset selection over previous state-of-the-art methods for up to 70% pruning rates.
  arXiv  Detail & Related papers  (2023-10-11T23:01:29Z)
• Challenging the Myth of Graph Collaborative Filtering: a Reasoned and Reproducibility-driven Analysis [50.972595036856035]
  We present a code that successfully replicates results from six popular and recent graph recommendation models. We compare these graph models with traditional collaborative filtering models that historically performed well in offline evaluations. By investigating the information flow from users' neighborhoods, we aim to identify which models are influenced by intrinsic features in the dataset structure.
  arXiv  Detail & Related papers  (2023-08-01T09:31:44Z)
• DiffusAL: Coupling Active Learning with Graph Diffusion for Label-Efficient Node Classification [1.0602247913671219]
  We introduce a novel active graph learning approach called DiffusAL, showing significant robustness in diverse settings. Most of our calculations for acquisition and training can be pre-processed, making DiffusAL more efficient compared to approaches combining diverse selection criteria. Our experiments on various benchmark datasets show that, unlike previous methods, our approach significantly outperforms random selection in 100% of all datasets and labeling budgets tested.
  arXiv  Detail & Related papers  (2023-07-31T20:30:13Z)
• Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
  We propose a novel unsupervised multi-view feature selection model based on graph learning. The contributions are threefold: (1) during the feature selection procedure, the consensus similarity graph shared by different views is learned. Experiments on various datasets demonstrate the superiority of the proposed method compared with the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-04-11T03:25:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.