Scalable Game-Theoretic Graph Data Valuation via Coordinated Structural Reuse

As large-scale graph data becomes increasingly prevalent, assessing the quality and value of individual data points is critical for model developers and data marketplaces alike. Existing SOTA data valuation methods, such as Data Shapley and DataModels, are designed for i.i.d. settings and fail to capture the structural dependencies inherent in graph data. Precedence-Constrained Winter Value (PC-Winter) represents the first SOTA framework for graph-aware valuation; however, two shortcomings limit its effectiveness. First, its Monte Carlo estimator samples nodes without coordination within a labeled-node group, producing context-misaligned estimates that inflate the noise on intra-group members and harm ranking-based tasks. Second, while its algorithmic pipeline exploits some structural redundancy, substantial reuse opportunities remain unexploited in both signal propagation and classifier training. We address both shortcomings under a unifying principle, Maximal Structural Reuse (MSR), which exploits the structural commonalities across players at every component of the pipeline. Accordingly, we introduce SGVR (Scalable Graph Data Valuation via Coordinated Structural Reuse), built on three contributions: i) a structure-aware estimator based on hierarchical coordinated sampling across the members of each labeled-node group; we derive its exact variance when comparing nodes within the same group, which contracts in proportion to the covariance that coordination induces through shared context, and confirm this contraction empirically; ii) an optimal propagation procedure that updates only the nodes affected by each incremental change; and iii) a recursive least squares update rule that incrementally refines reusable model weights at negligible cost. Experiments on six standard benchmarks confirm that SGVR outperforms existing baselines on the unlabeled node selection task, with speedups that grow with graph size and reach two orders of magnitude on the largest benchmarks. Code and experiments will be publicly released upon publication.