# Most Influential Subset Selection: Challenges, Promises, and Beyond

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 81 references that are in the map.
- First posted on arXiv 25 Sep 2024.

## Builds on (most cited first, 30 of 42)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Estimating Training Data Influence by Tracing Gradient Descent](https://mlsanity.com/paper/2002.08484/) (2020)
- [Studying Large Language Model Generalization with Influence Functions](https://mlsanity.com/paper/2308.03296/) (2023)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Influence Functions in Deep Learning Are Fragile](https://mlsanity.com/paper/2006.14651/) (2020)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Representer Point Selection for Explaining Deep Neural Networks](https://mlsanity.com/paper/1811.09720/) (2018)
- [On the Accuracy of Influence Functions for Measuring Group Effects](https://mlsanity.com/paper/1905.13289/) (2019)
- [Fast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis](https://mlsanity.com/paper/1806.03884/) (2018)
- [If Influence Functions are the Answer, Then What is the Question?](https://mlsanity.com/paper/2209.05364/) (2022)
- [Why Is My Classifier Discriminatory?](https://mlsanity.com/paper/1805.12002/) (2018)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Dataset Pruning: Reducing Training Data by Examining Generalization Influence](https://mlsanity.com/paper/2205.09329/) (2022)
- [Scaling Up Influence Functions](https://mlsanity.com/paper/2112.03052/) (2021)
- [FastIF: Scalable Influence Functions for Efficient Model Interpretation and Debugging](https://mlsanity.com/paper/2012.15781/) (2020)
- [On Second-Order Group Influence Functions for Black-Box Predictions](https://mlsanity.com/paper/1911.00418/) (2019)
- [A Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1806.00550/) (2018)
- [Simfluence: Modeling the Influence of Individual Training Examples by Simulating Training Runs](https://mlsanity.com/paper/2303.08114/) (2023)
- [Interactive Label Cleaning with Example-based Explanations](https://mlsanity.com/paper/2106.03922/) (2021)
- [Interpreting Black Box Predictions using Fisher Kernels](https://mlsanity.com/paper/1810.10118/) (2018)
- [Intriguing Properties of Data Attribution on Diffusion Models](https://mlsanity.com/paper/2311.00500/) (2023)
- [Training Data Attribution via Approximate Unrolled Differentiation](https://mlsanity.com/paper/2405.12186/) (2024)
- [Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits](https://mlsanity.com/paper/2405.03875/) (2024)
- [An Automatic Finite-Sample Robustness Metric: When Can Dropping a Little Data Make a Big Difference?](https://mlsanity.com/paper/2011.14999/) (2020)
- [Understanding Instance-Level Impact of Fairness Constraints](https://mlsanity.com/paper/2206.15437/) (2022)

## Built on by (most cited first, 30 of 32)

- [Diffusion Attribution Score: Evaluating Training Data Influence in Diffusion Models](https://mlsanity.com/paper/2410.18639/) (2024)
- [OPUS: Towards Efficient and Principled Data Selection in Large Language Model Pre-training in Every Iteration](https://mlsanity.com/paper/2602.05400/) (2026)
- [Group-Level Data Selection for Efficient Pretraining](https://mlsanity.com/paper/2502.14709/) (2025)
- [A Snapshot of Influence: A Local Data Attribution Framework for Online Reinforcement Learning](https://mlsanity.com/paper/2505.19281/) (2025)
- [Better Training Data Attribution via Better Inverse Hessian-Vector Products](https://mlsanity.com/paper/2507.14740/) (2025)
- [TAROT: Targeted Data Selection via Optimal Transport](https://mlsanity.com/paper/2412.00420/) (2024)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankings](https://mlsanity.com/paper/2508.11847/) (2025)
- [Final-Model-Only Data Attribution with a Unifying View of Gradient-Based Methods](https://mlsanity.com/paper/2412.03906/) (2024)
- [Reasoning-Driven Synthetic Data Generation and Evaluation](https://mlsanity.com/paper/2603.29791/) (2026)
- [Taming Hyperparameter Sensitivity in Data Attribution: Practical Selection Without Costly Retraining](https://mlsanity.com/paper/2505.24261/) (2025)
- [Rescaled Influence Functions: Accurate Data Attribution in High Dimension](https://mlsanity.com/paper/2506.06656/) (2025)
- [Influence Functions for Edge Edits in Non-Convex Graph Neural Networks](https://mlsanity.com/paper/2506.04694/) (2025)
- [Concept-TRAK: Understanding how diffusion models learn concepts through concept-level attribution](https://mlsanity.com/paper/2507.06547/) (2025)
- [Toward Efficient Influence Function: Dropout as a Compression Tool](https://mlsanity.com/paper/2509.15651/) (2025)
- [Testing Most Influential Sets](https://mlsanity.com/paper/2510.20372/) (2025)
- [Aggregation Hides Out-of-Distribution Generalization Failures from Spurious Correlations](https://mlsanity.com/paper/2510.24884/) (2025)
- [SynQuE: Estimating Synthetic Dataset Quality Without Annotations](https://mlsanity.com/paper/2511.03928/) (2025)
- [Tree of Preferences for Diversified Recommendation](https://mlsanity.com/paper/2601.02386/) (2025)
- [Interaction-Aware Influence Functions for Group Attribution](https://mlsanity.com/paper/2605.15675/) (2026)
- [On the Accuracy of Newton Step and Influence Function Data Attributions](https://mlsanity.com/paper/2512.12572/) (2025)
- [A Unified Theory of Random Projection for Influence Functions](https://mlsanity.com/paper/2602.10449/) (2026)
- [DC-W2S: Dual-Consensus Weak-to-Strong Training for Reliable Process Reward Modeling in Biological Reasoning](https://mlsanity.com/paper/2603.08095/) (2026)
- [Training data attribution in diffusion models via mirrored unlearning and noise-consistent skew](https://mlsanity.com/paper/2605.17938/) (2026)
- [GUDA: Counterfactual Group-wise Training Data Attribution for Diffusion Models via Unlearning](https://mlsanity.com/paper/2601.22651/) (2026)
- [Is Data Shapley Not Better than Random in Data Selection? Ask NASH](https://mlsanity.com/paper/2605.10684/) (2026)
- [Constraint-Data-Value-Maximization: Utilizing Data Attribution for Effective Data Pruning in Low-Data Environments](https://mlsanity.com/paper/2605.11312/) (2026)
- [Convex Dataset Valuation for Post-Training](https://mlsanity.com/paper/2605.16704/) (2026)
- [Finding Most Influential Sets](https://mlsanity.com/paper/2606.05919/) (2026)
- [Influence Diagnostics in High-dimensional M-estimation: Precise Asymptotics](https://mlsanity.com/paper/2607.09250/) (2026)

## Abstract (arXiv)

How can we attribute the behaviors of machine learning models to their training data? While the classic influence function sheds light on the impact of individual samples, it often fails to capture the more complex and pronounced collective influence of a set of samples. To tackle this challenge, we study the Most Influential Subset Selection (MISS) problem, which aims to identify a subset of training samples with the greatest collective influence. We conduct a comprehensive analysis of the prevailing approaches in MISS, elucidating their strengths and weaknesses. Our findings reveal that influence-based greedy heuristics, a dominant class of algorithms in MISS, can provably fail even in linear regression. We delineate the failure modes, including the errors of influence function and the non-additive structure of the collective influence. Conversely, we demonstrate that an adaptive version of these heuristics which applies them iteratively, can effectively capture the interactions among samples and thus partially address the issues. Experiments on real-world datasets corroborate these theoretical findings and further demonstrate that the merit of adaptivity can extend to more complex scenarios such as classification tasks and non-linear neural networks. We conclude our analysis by emphasizing the inherent trade-off between performance and computational efficiency, questioning the use of additive metrics such as the Linear Datamodeling Score, and offering a range of discussions.