- 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
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 -th sample to a reusable training context , 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 from before this node was added. When an inserted unlabeled node changes this embedding, we add the new embedding as the -th sample to the stored context. The old embedding 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.
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)>Δ, 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.
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.