Shapley-Based Data Valuation for Weighted $k$-Nearest Neighbors
Guangyi Zhang, Qiyu Liu, Aristides Gionis
Data valuation quantifies the impact of individual data points on model performance, and Shapley values provide a principled approach to this important task due to their desirable axiomatic properties,albeit with high computational complexity. Recent breakthroughs have enabled fast computation of exact Shapley values for unweighted $k$-nearest neighbor ($k$NN) classifiers. However, extending this to weighted $k$NN models has remained a significant open challenge. The state-of-the-art methods either require quadratic time complexity or resort to approximation via sampling.In this paper, we show that a conceptually simple but overlooked approach - data duplication - can bridge this gap.However, the increased data size due to duplication incurs prohibitive computational and memory costs.We develop an efficient algorithm that avoids materializing the duplicated dataset by exploiting the structural properties of weighted $k$NN models,reducing the complexity to near-linear time in the original data size.Besides, we establish theoretical foundations for this approach through axiomatic characterization of the resulting values,and empirically validate its effectiveness and efficiency.