acceptodds
Under review as a conference paper at ICLR 2027

Scalable Game-Theoretic Graph Data Valuation via Coordinated Structural Reuse

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph data valuation, Shapley value, cooperative game theory, coordinated sampling, graph neural networks, scalability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PDEfOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors propose SGVR, a graph data valuation framework that reuses shared graph structure to improve estimation efficiency and ranking reliability. It combines coordinated sampling, incremental propagation, and recursive model updates. Experiments on six benchmarks report improved unlabeled-node selection and speedups reaching two orders of magnitude over existing methods.

Critical strengths
  • This paper studies the high computational cost of graph data valuation, making it more practical to identify influential nodes without repeatedly performing expensive model training.

  • The proposed framework accounts for how nodes contribute through graph connections, allowing their value to reflect their role in supporting other nodes rather than only their own features.

  • Experiments on six datasets assess both node-removal AUC and runtime, showing whether computational savings are accompanied by useful rankings across different graph settings.

Critical weaknesses
  • The theoretical comparison assumes that PC-Winter estimates different players independently. However, its original procedure evaluates multiple players within each sampled traversal, which can introduce dependence between their estimates. Consequently, the assumed zero covariance may not represent the actual baseline.

  • The recursive update does not explain how an existing embedding’s contribution is removed before its replacement is added.

  • The theoretical analysis concerns comparisons between players sharing hierarchical contexts, whereas the experiments rank original nodes after aggregating their contributions across different contexts. Improved local comparisons therefore do not directly establish more reliable global node rankings.

  • The theoretical analysis focuses on comparisons between players sharing hierarchical contexts, but the final ranking aggregates contributions across different occurrences of each original node. The analysis does not directly establish how these local variance reductions affect the final node rankings.

  • The propagation complexity comparison is derived for regular graphs, where neighborhood growth is controlled by a common degree. In irregular graphs with highly connected nodes, an insertion can affect a much larger region, limiting how broadly the stated computational advantage applies.

Questions for authors

Please refer to the Critical Weaknesses.

6 comments

W1. We thank the reviewer for this careful observation. We agree that players under PC-Winter are not strictly independent, since several players are evaluated in the same permutation. To quantify this dependence, we measured the correlation between the estimates of sibling players over 10 runs at the 500K budget (table below). We report the correlation because, unlike the covariance, it is scale-invariant. Under PC-Winter, the correlation is within 0.01 of zero on all six datasets, which is the level of unrelated pairs. Under coordinated sampling, it is positive for siblings on every dataset, and it remains at zero for pairs that share no draws. A likely reason for the near-zero value under PC-Winter is truncation, which both methods apply with the same rates (0.85 to 0.985): each traversal evaluates only a small fraction of the children at each level, so two members of a group are rarely evaluated in the same traversal. Under uncoordinated sampling, this is the only way in which two siblings can share a context. Under coordinated sampling, the same upper-level context is reused for several lower-level draws, so siblings share it even when they are evaluated in different draws. The zero-covariance baseline in Theorem 2 is therefore an accurate approximation in practice. We added this analysis to the paper (Appendix D.4) and noted it where the baseline is introduced (Section 2.3). We also generalized the statement so that it no longer relies on a zero baseline: when the uncoordinated estimates are correlated, coordination reduces the pairwise variance if and only if 2(Covcoord−Covunc)>Δ2(\mathrm{Cov}^{\mathrm{coord}}-\mathrm{Cov}^{\mathrm{unc}})>\Delta, i.e., what matters is the covariance gained over the baseline (Theorem 2 and new Remark 2 in Appendix C.8). Finally, we compared the pairwise variance of Theorem 2 directly on these runs: the variance of the difference between two sibling estimates is lower under SGVR on all six datasets, with a median reduction of 6% to 57% (last two columns). This net change also includes the change in per-player variance.

DatasetCorr. siblings (PC-Winter)Corr. siblings (SGVR)Corr. unrelated (PC-Winter)Corr. unrelated (SGVR)Median reduction of sibling-difference varianceWilcoxon pp
Cora-ML0.0030.0030.0290.029−0.001-0.001−0.001-0.00129%<10−100<10^{-100}
CiteSeer−0.006-0.0060.0180.0180.0010.0010.0000.00018%1.5×10−1491.5\times 10^{-149}
PubMed0.0000.0000.0100.010−0.001-0.0010.0000.00011%7.1×10−1317.1\times 10^{-131}
Physics0.0080.0080.0470.0470.0000.0000.0000.00035%<10−100<10^{-100}
Photo−0.003-0.0030.0170.017−0.001-0.0010.0000.0006%3.0×10−63.0\times 10^{-6}
Computers−0.003-0.0030.0050.0050.0000.0000.0000.00057%<10−100<10^{-100}

Mean correlation between the estimates of two players over 10 runs (500K budget). Last two columns: median reduction of the variance of the sibling difference under SGVR relative to PC-Winter, and one-sided paired Wilcoxon test.

W2. We appreciate the reviewer's comment on this point. We agree that our wording in Section 2.5 (“changed embedding”) was unclear on this. We would like to clarify that we model every embedding change as the addition of the kk-th sample to a reusable training context (Pk−1,Θ^k−1)(P_{k-1}, \hat\Theta_{k-1}), so each update is rank-one. Specifically, the labeled node whose embedding changes is always the most recently added sample, and we store the training context (Pk−1,Θ^k−1)(P_{k-1}, \hat\Theta_{k-1}) from before this node was added. When an inserted unlabeled node changes this embedding, we add the new embedding xnewx_{\text{new}} as the kk-th sample to the stored context. The old embedding xoldx_{\text{old}} is therefore never part of the matrix we update, and no removal is needed. We revised Section 2.5 and Appendix C.10 to state this update rule explicitly.

W3 and W4. We thank the reviewer for raising this point, which helps us clarify the scope of our analysis.

What the analysis claims. A ranking is determined by the differences between values. This pairwise view is established in data valuation: Data Banzhaf [1] defines the robustness of a value notion through the value order of every pair of data points. Our analysis is stated for these pairwise differences. Coordination does not make a single value more accurate (Theorem 4). It lowers the variance of the difference between two players that share a context, whenever the covariance it adds outweighs the added per-player variance (Theorem 2).

From players to original nodes. The value of an original node aggregates the values of its duplicate players, so, by linearity, the covariance between two node values is the sum of the covariances between their players. Coordination adds a positive covariance to the terms whose players share a context and leaves the others unchanged: as the table in W1 shows, the correlation between unrelated players stays at zero. The comparison of two original nodes therefore follows the same trade-off as Theorem 2, with the covariance summed over their players, and the effect is concentrated on nodes that appear in the same groups. We added this as Remark 3 (Appendix C.8).

Evidence on original nodes. This is a statement on variance and not a guarantee on the global ranking, which we evaluate directly: all our experiments rank the original nodes. At the 500K budget, SGVR attains a lower or comparable AUC to PC-Winter on the six datasets (Figure 2). Its advantage grows with the budget (Figure 3) and is wider under injected heterophily (Figure 4).

[1] Jiachen T. Wang and Ruoxi Jia. Data Banzhaf: A Robust Data Valuation Framework for Machine Learning. AISTATS 2023.

Reviewer_zLy4OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors tackle the main limitation ot SOTA data valuations methods (Data Shapley and DataModels) which are designed for i.i.d settings. They also highlight two limitations of a SOTA framework for graph-aware valuation (PC-Winter): 1. its Monte Carlo estimator samples nodes without coordination within a labeled-node group. 2. while its algorithmic pipeline exploits some structural redundancy, substantial reuse opportunities remain unexploited in both signal propagation and classifier training.

The authors tackle these limitations by introducing their approach based on the Maximal Structural Reuse (MSR) which exploits structural commonalities across players. This is the SGVR which is a structure-aware estimator based on hierarchical coordinated sampling with an optimal propagation procedure with recursive least squares update rule.

Critical strengths
  1. The problem they tackle is very relevant: understanding the value of individual data points is increasingly critical. While graph-structured data represents a fundamentally richer modality than tabular or Euclidean data, encoding relational dependencies between entities that classical machine learning cannot directly exploit.

  2. Their solution to not need to rely on the i.i.d assumption is the coordinated sampling in which they reformulate the game-theoretic allocation in terms of the structural contexts that players share, and estimate it with a hierarchical Monte Carlo scheme. The authors provide a theoretical analysis, confirmed empirically across our benchmarks, showing that this contracts the estimation variance on intra-group pairwise differences, which essentially governs the ranking quality among contributors.

  3. The empirical benchmark seems to show that their proposed method outperforms the baselines considered.

Critical weaknesses
  1. I think there is a confusion around the speedup as reported in Table 1. The authors say in the caption that "with the speedup of the full SGVR in parentheses" so for example in the first row PC-Winter has 6m 50s (1.5X) and the SGVR w/o min. prop is 4m 43s (1X). The time of SGVR is less so if between parenthesis we have the speedup, I would have expected this number to be larger.

  2. I understand that in each benchmark per dataset there is no standard deviation or error reported. I would imagine that one can have folds and train and evaluate in different folds and with that report some statistics. I think this is needed in Figure 2 to make a robust conclusion of which is performing better.

Questions for authors
  1. how did you select the methods to use as baselines? how is it that this is an apples-to-apples comparison?

  2. why did you limit the analysis up to 1000 nodes in Figure 2? I would like to see if for the methods that keep the values high across the dropping of nodes does indeed show some decay.

  3. is there any expected decay in performance when removing nodes just because of having less number of nodes? why you did not include a curve for random removal? you can randomly remove nodes one by the time and assess performance and then you can average that, and report some error.

7 comments

W1. We appreciate the comment of the reviewer, which helps improve the presentation of our results. Each value in parentheses is the time of the method divided by the time of full SGVR, i.e., the speedup of full SGVR over that method, so a larger value means a slower method. We updated the caption of Table 1 in the manuscript to state this clearly.

W2. We appreciate the reviewer pointing to this. We updated the manuscript to include results on the datasets across multiple seeds and splits, and we report the mean and standard deviation over these runs to support a robust comparison among methods. We also extended the drop experiments to 2000 removed nodes to show the trend of the downstream node-drop performance, and updated Figure 2 accordingly. Figure 2 now shows, for all six datasets, the mean curve of each method with a shaded band for the standard deviation.

Q1. We thank the reviewer for the question. We followed the common protocol established in graph data valuation [1, 2] and compare against the methods evaluated under it: the i.i.d. valuation methods and PC-Winter [1], which is the only graph-aware valuation method in this setting. For a direct comparison, all budgeted methods share the same budget, and SGVR and PC-Winter use identical truncation rates.

During our survey we also found other graph valuation methods. They address different settings that do not match our study, namely valuation at inference time [3], heterogeneous graphs [4] and task-agnostic valuation [5], and we discuss them in the related work (Appendix B).

[1] Hongliang Chi, Wei Jin, Charu C. Aggarwal, and Yao Ma. Precedence-Constrained Winter Value for Effective Graph Data Valuation. ICLR 2025.

[2] Simone Antonelli and Aleksandar Bojchevski. Node-Level Data Valuation on Graphs. TMLR 2025.

[3] Hongliang Chi, Qiong Wu, Zhengyi Zhou, and Yao Ma. Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation. ICLR 2025.

[4] Xin Tang, Quanyan Gao, and Chao Li. LTSV: Layered Type-Constrained Shapley Value for Heterogeneous Graph Data Valuation. KDD 2026.

[5] Ali Falahati and Mohammad Mohammadi Amiri. Disentangled Structural and Featural Representation for Task-Agnostic Graph Valuation. arXiv:2408.12659, 2024.

Q2. We appreciate the interest of the reviewer in our work. In our initial submission, we limited the node-drop experiments to 1000 nodes due to computational cost and the saturating performance of the curves. As discussed in W2, we extended the results to 2000 removed nodes and report them over multiple seeds and splits. With the extended horizon, the methods that keep the performance high (RND, Degree, and the i.i.d. valuation methods) show little or no decay up to 2000 removed nodes. For SGVR and PC-Winter, the performance keeps decaying beyond 1000 nodes on PubMed, Physics, and Computers, and saturates on Cora-ML, CiteSeer, and Photo.

Q3. We thank the reviewer for raising this point. Random node removal is an important baseline that isolates the ranking quality from the effect of the dataset size. The RND curve in our initial submission (Figure 2) corresponds to removing nodes at random. Similarly, we include a degree-based baseline (Degree) to show that the node degree is not a direct measure of the value. As discussed in W2, all curves are now reported as the mean and standard deviation over multiple seeds and splits. To make the manuscript clearer, we updated Section 3.1 and the caption of Figure 2 to describe these baselines explicitly.

Reviewer_GT1rOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SGVR (Scalable Graph Data Valuation via Coordinated Structural Reuse), a framework for efficient game-theoretic data valuation on graphs. The work extends cooperative game-theoretic valuation to graph-structured data by incorporating hierarchical coalition structures and precedence constraints induced by graph computation trees. The proposed framework conssts three components: Hierarchical coordinated sampling, minimal propagation, and recursive model training. The performance of SGVR is evaluated on real-world graph benchmarks. The results demonstrate computational speedups over several existing valuation methods and improved valuation quality.

Critical strengths

Efficient graph data valuation is an important problem because conventional data valuation techniques do not directly account for the structural dependencies introduced by message passing. The computational expense is also an improtant concern for practical deployment.

The experiments investigate valuation performance across different computational budgets and datasets. The results for improved efficiency are convincing. The ablation study also indicate that both minimal propagation and recursive model training contribute to the overall speedup.

Critical weaknesses
  1. The main novelty therefore appears to be in adapting and integrating existing statistical and computational techniques into the PC-Winter framework, rather than developing new algorithms for each component. It would be helpful to better explain what is technically nontrivial about applying these techniques to the hierarchical coalition structure and what new insights can be obtained beyond the straightforward combination.

  2. Section 2.5 states that each incremental insertion changes at most one labeled node's embedding, allowing the normal matrix to be updated using a single rank-one correction. However, there is an important distinction between adding a new training sample and modifying an existing training sample's embedding. Suppose an existing labeled embedding changes from \x_{{old}} to x_{{new}}. The corresponding normal matrix changes according to: A_{new}= A_{old} -x_{old}x_{old}^\top +x_{new}x_{new}^\top. This is hence a rank-two modification, instead of a single rank-one addition. It is necessary to explicitly state the update rule corresponding to the actual modifications of the labeled feature matrix.

  3. The proposed computational optimizations rely heavily on Simplified Graph Convolution (SGC) and ridge regression. These choices simplify the learning problem compared with modern nonlinear GNN architectures

Questions for authors
  1. When inserting an unlabeled node changes an existing labeled node's embedding, how does the proposed RLS update account for the removal of the old embedding and the addition of the new one?

  2. What is the SGVR's benefits beyond SGC and ridge regression? Can coordinated sampling improve performance for nonlinear GNN architectures? Does its variance reduction still holds when utility is evaluated using nonlinear GNNs?

  3. Can minimal propagation provide comparable efficiency gains for architectures with nonlinear message passing and attention?

  4. How sensitive is the method to h_2 and h_3?

6 comments

W1. We thank the reviewer for this comment, which helps us state our contribution more clearly. SGVR adapts established tools, such as nested Monte Carlo sampling and recursive least squares, to address a limitation of existing graph valuation methods that, to the best of our knowledge, has not been identified before.

New insight. The reliability of a ranking depends on the differences between values, and its robustness to noise has been studied for i.i.d. data [1]. It is not directly addressed in existing graph valuation methods. PC-Winter samples its permutations independently, so two members of the same group are evaluated under different contexts, and their difference contains the variation of the context in addition to their relative worth. This mismatch is an artifact of how permutations are sampled, not a property of the value itself. It is unique to graph data valuation and does not arise in i.i.d. valuation, where the players form a flat set with no hierarchical context to align (we now state this in Section 2.2).

Why it is non-trivial. Removing the mismatch must not change the value that is estimated. We (i) show that the PC-Winter value can be written over the contexts that players share (Theorem 1), (ii) design a nested Monte Carlo estimator that draws each context once for all its players and remains unbiased (Section 2.3), and (iii) characterize exactly when this lowers the variance of a comparison (Theorem 2): coordination trades added covariance between group members against per-player variance.

Significance. The same shared structure is reused by minimal propagation and the recursive update, which are exact. SGVR is 1.5 to 3.5 times faster than PC-Winter and up to two orders of magnitude faster than the i.i.d. baselines (Table 1), with comparable or better ranking quality at the 500K budget (Figure 2). We believe our work lays the groundwork for better value estimation in the graph modality.

[1] Jiachen T. Wang and Ruoxi Jia. Data Banzhaf: A Robust Data Valuation Framework for Machine Learning. AISTATS 2023.

W2 and Q1. We appreciate the reviewer's comment on this point. The reviewer is right that modifying an existing sample in place is indeed a rank-two change, and our wording in Section 2.5 (“changed embedding”) was unclear on this. We would like to clarify that we model every embedding change as the addition of the kk-th sample to a reusable training context (Pk−1,Θ^k−1)(P_{k-1}, \hat\Theta_{k-1}), so each update is rank-one. Specifically, the labeled node whose embedding changes is always the most recently added sample, and we store the training context (Pk−1,Θ^k−1)(P_{k-1}, \hat\Theta_{k-1}) from before this node was added. When an inserted unlabeled node changes this embedding, we add the new embedding xnewx_{\text{new}} as the kk-th sample to the stored context. The old embedding xoldx_{\text{old}} is therefore never part of the matrix we update, and no removal is needed. We revised Section 2.5 and Appendix C.10 to state this update rule explicitly.

W3. We thank the reviewer for pointing this out. We would like to first clarify that the linear model (SGC with ridge regression) is used only for the valuation, i.e., to compute the node values. It is not the model on which the values are meant to be used: the resulting ranking remains effective for modern nonlinear GNNs, as we discuss and show below. We agree that the optimizations of our method rely on the linearity assumption, which enables the optimized training and propagation. We adopt linear models for the valuation for two reasons that are established in existing work.

First, efficiency. Data valuation requires a large number of training runs, so existing methods adopt models that are efficient to train. For example, Datamodels [3] rely on a lightweight architecture with an accelerated training pipeline [4], while graph valuation methods use SGC [1, 2].

Second, transferability. It is recognized in the relevant literature that values obtained with a simple model transfer to more complex models. For graph data, Antonelli and Bojchevski [2, Appendix C.7] show that node values computed with SGC transfer to GCN and GAT with nearly identical downstream-task performance. For i.i.d. data, Datamodels [3] report that their estimates remain largely accurate for a different architecture. Similar findings are reported for values and rankings obtained with proxy models [5, 6]. In other words, values computed with a simple model remain useful for modern nonlinear architectures.

Our transferability results (new Appendix D.2). We verified this for SGVR with a node-removal experiment similar to the one of Antonelli and Bojchevski [2, Appendix C.7]: we keep the node ranking computed with SGC and retrain a nonlinear model (GCN or GATv2) after each removal on Cora-ML, CiteSeer, and PubMed. The relative order of the methods observed with SGC is preserved under both models: the graph-aware methods (SGVR and PC-Winter) are ahead of or on par with DataModels, and all three are ahead of the Degree and random baselines. These trends are consistent with the findings of [2].

[1] Hongliang Chi, Wei Jin, Charu C. Aggarwal, and Yao Ma. Precedence-Constrained Winter Value for Effective Graph Data Valuation. ICLR 2025.

[2] Simone Antonelli and Aleksandar Bojchevski. Node-Level Data Valuation on Graphs. TMLR 2025.

[3] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Understanding Predictions with Data and Data with Predictions. ICML 2022.

[4] Guillaume Leclerc, Andrew Ilyas, Logan Engstrom, Sung Min Park, Hadi Salman, and Aleksander Madry. FFCV: Accelerating Training by Removing Data Bottlenecks. CVPR 2023.

[5] Ruoxi Jia, Fan Wu, Xuehui Sun, Jiacen Xu, David Dao, Bhavya Kailkhura, Ce Zhang, Bo Li, and Dawn Song. Scalability vs. Utility: Do We Have to Sacrifice One for the Other in Data Importance Quantification? CVPR 2021.

[6] Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via Proxy: Efficient Data Selection for Deep Learning. ICLR 2020.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.