LTSV: Layered Type-Constrained Shapley Value for Heterogeneous Graph Data Valuation

Abstract

Data valuation is essential for quantifying data worth in machine learning, especially in multi-party collaborations where incentives rely on fair contribution attribution. Although Shapley-value-based methods are effective for I.I.D. data, extending them to heterogeneous graphs remains challenging due to type-dependent node roles, cross-type dependencies, and prohibitive valuation costs. In this paper, we propose LTSV (Layered Type-Constrained Shapley Value, a framework that decomposes each node's value into three components: intra-type feature contribution, cross-type semantic bridging, and global structural support. Specifically, LTSV anchors the valuation in type-constrained subgames to ensure axiomatic fairness for within-type contributions while preserving the heterogeneous context. It further introduces meta-path-based value propagation to make the implicit contribution of unlabeled bridge nodes explicit and quantifiable. To scale valuation, we develop type-constrained Monte Carlo sampling with importance weighting. Experiments on DBLP, ACM, and IMDb show that LTSV more accurately identifies high-value nodes than state-of-the-art baselines under standard deletion/addition evaluations, while achieving favorable computational efficiency.