Precedence-Constrained Winter Value for Effective Graph Data Valuation

W3: "In a unilateral dependency structure, a player's contribution depends on its ancestors, resembling the sharded structure setting in [1]. However, in [1], computing the exact Shapley value remains #P-complete despite the presence of the sharded structure. In contrast, the time complexity of PC-Winter, as mentioned in I.5, appears to be polynomial."

Q2:"Why can the computation of PC-Winter be done in polynomial time, whereas calculating the original Shapley value remains #P-complete? Further clarification and justification of this distinction would be helpful to understand the computational efficiency of PC-Winter in comparison to the traditional Shapley value calculation."

A.3 We appreciate the reviewer's insightful question about computational complexity. We would like to clarify that computing the exact PC-Winter value or other list-constrained Winter values is indeed #P-complete, similar to the original Shapley value computation and its variants. We apologize if our presentation in Section I.5 caused any confusion on this point. What we describe in the paper is a polynomial-time approximation approach based on permutation sampling, not the exact computation. This is similar to the sampling-based approximation methods mentioned in [1]. Specifically, our method achieves polynomial time complexity through three key approximation strategies (detailed in Section 3.4): Monte Carlo permutation sampling, Hierarchical truncation and Local propagation.

The time complexity analysis in Section I.5 pertains to this approximation framework, not the exact computation. We thank the reviewer for bringing up [1], which indeed uses similar sampling-based approaches for efficient approximation. We have revised our presentation in Section I.5 to make this distinction between exact computation and approximation more explicit, and properly acknowledge the connection to existing approximation methods in the literature [1]. The updated section now clearly states that while computing exact PC-Winter value remains #P-complete, our approximation framework achieves polynomial-time efficiency through the aforementioned strategies.

[1] Xia H, Liu J, Lou J, et al. "Equitable data valuation meets the right to be forgotten in model markets." Proceedings of the VLDB Endowment, 2023.

W4: "The paper does not present any experimental results to demonstrate the scalability of the proposed algorithms."

A.4 We appreciate the reviewer's concern about scalability evidence. We have provided detailed efficiency analyses in both Section 4.4 and Appendix I.4. Specifically, Table 8 in Appendix I.4 presents comprehensive scalability results across datasets of varying sizes, showing significant efficiency improvements over Data Shapley. Additionally, Appendix I.2 demonstrates that PC-Winter can achieve competitive performance with a limited number of permutations, making it practical for real-world applications.

We believe that we have responded to and addressed all your concerns and questions — in light of this, we hope you consider raising your score. Feel free to let us know in case there are outstanding concerns, and if so, we will be happy to respond.

W1: "This paper introduces a concept known as a 'Level Coalition Structure,' which represents a hierarchical organization, as illustrated in Figure 1. However, it imposes the constraint that, at the same level, the data are mutually disjoint...Nevertheless, it is typical for these sets of descendants to exhibit some overlap or shared nodes."

A.1 Thank you for the insightful observation about overlapping nodes in graph structures! This overlapping nature actually inspired our design approach. In PC-Winter, we consider not just the nodes themselves, but their different roles in affecting labeled nodes through various computation paths. As we describe in Section 3.1 (Definition 2), the player set $p$ in our framework is defined as the union of nodes from the computation trees of all labeled nodes.

We would like to clarify that while nodes in the original training graph can indeed overlap and be shared, when we transform these nodes into players in our framework, we explicitly consider their distinct roles in different computation trees. When a node appears in multiple computation trees or at different positions within the same tree, each occurrence ("duplicate") represents a unique contribution pathway - either passing features to different labeled nodes or serving as a labeled node itself. These duplicates, by the nature of how GNN computation trees are constructed, are mutually disjoint in their roles, which naturally addresses the disjointness requirement of the Level Coalition Structure while preserving all information about node interactions in the original graph.

W2: "In this paper, as outlined in Definition 2, the duplication' referred to in W1 appears to be handled by decomposing it into distinct players, termed 'duplicates'. However, it remains unclear whether the Shapley value of the original node is simply the sum of the values of these duplicates, as the paper does not explicitly address this point."

Q1: "Does the assumption of decomposing a node into distinct duplicates hold? Please provide further evidence or proofs to support this assumption, as it is currently unclear whether this decomposition accurately reflects the original structure."

A.2 Thank you for this important question about duplicates. We'd like to clarify a couple of key points:

(1) First, we would like to like clarify that PC-Winter is not actually exact Shapley value. It is a graph-specific valuation framework that respects both Level and Precedence constraints inherent in graph structures (Section 3.2). Our design motivation stems from a fundamental observation about how graphs contribute to GNN training: nodes influence model performance through multiple pathways. As discussed in Section 3.1:

"Unlabeled nodes influence GNN performance by affecting the final representation of labeled nodes. On the other hand, labeled nodes can contribute in two ways: (1) providing direct supervision signals, and (2) just like unlabeled nodes, they can impact other labeled nodes' representations through feature aggregation."

Based on this observation, we define our valuation objects as nodes in the contribution tree, which naturally captures these diverse influence pathways. Each "duplicate" represents a specific instance where a node contributes - either through feature propagation to a labeled node, direct supervision, or both.

(2) Regarding value aggregation (Does the assumption of decomposing a node into distinct duplicates hold?), while we do not make theoretical claims about this decomposition, our experimental results strongly support this design choice. As shown in Section 4.1, removing nodes with high aggregated values (sum of their duplicates' values) leads to the most significant performance drops across all datasets. This empirically demonstrates that each duplicate captures meaningful and distinct contributions to model performance, and their combined value effectively quantifies a node's overall importance. The effectiveness of our approach is further validated in Figure 4 (Section 4.2), where PC-Winter outperforms baselines in edge addition tasks, showing that our framework successfully captures how nodes contribute to model performance through multiple pathways.

Hi Reviewer 8Mde, thank you for your helpful feedbacks! as the deadline for the author and reviewer discussion period approaches, we'd like to kindly check in and ask for your thoughts on our responses to your questions. Please feel free to let us know if there are any lingering concerns or if you find our answers satisfactory. We truly value the time and effort you've dedicated to reviewing our paper and are eager to address any remaining questions or concerns you may have.

Hi Reviewer 8Mde, as today (December 3rd) marks the final day of the discussion period, we wanted to send a gentle reminder regarding our previous responses. While we regret not having had the opportunity for direct dialogue, we sincerely hope our detailed responses have adequately addressed your thoughtful concerns about our paper. We greatly appreciate your time and consideration throughout this review process.

W1: "The organization of this paper could be improved. Section III could be shorten and most of the less related contents should be stated in natural language. For example, in Section3.4, the analysis of Fig2(a) can be split into separate segments."

A1. Thank you for these valuable suggestions about improving the paper's organization. In the revised version, we have restructured Section 3.4 by separating the analysis of Fig 2(a) into distinct segments and adopting more natural language description. Additionally, we have revised other sections by introducing clearer segmentation and adopting more concise, natural language descriptions.

W2: "The length of the article is beyond the space limit."

A2: Thank you for noting the paper length - we confirm that our submission adheres to ICLR 2025's updated guidelines which require main text to be between 6-10 pages, with additional technical details appropriately placed in the appendix.

W3: "The methodology in Section 3.3 needs further justification. The application of MC is not well-motivated. 'Following Data Shapley Ghorbani & Zou (2019), we adopt Monte Carlo (MC) sampling to ...'. SHAP uses MC in its implementation, but holds different assumptions with this paper."

A3: The adoption of Monte Carlo sampling is theoretically justified by our formulation of PC-Winter value. As defined in Equation 3 of our paper: $\psi_p(\mathcal{P}, U) = \frac{1}{|\Omega|} \sum_{\pi \in \Omega} [U(P^\pi_p \cup p) - U(P^\pi_p)]$ This formulation represents an expectation over permissible permutations $\Omega$ under a uniform distribution - each permissible permutation has equal probability $\frac{1}{|\Omega|}$ of being sampled. This uniformity is crucial as it ensures unbiased estimation of node contributions across all valid permutation orderings that satisfy both our Level and Precedence constraints.

For large graphs, exact computation becomes intractable as $|\Omega|$ grows exponentially with graph size. Monte Carlo sampling provides a standard statistical approach to approximate such expectations. By maintaining uniform sampling over $\Omega$ through our DFS-based generation process (as proved in Theorems 1 and 2), we obtain an unbiased estimator of the true PC-Winter value. This makes Monte Carlo sampling a natural choice regardless of the different structural assumptions between our work and Data Shapley.

W4.1: "Baselines in the Experiment are not SOTA. Data Valuation is a hot spot recently and many solutions have been proposed."

A4: We appreciate the reviewer's comment about recent advances in data valuation. To the best of our knowledge, PC-Winter is the first work specifically addressing data valuation for graph-structured data. While data valuation has seen significant developments, these methods (e.g., Beta-Shapley[1], Data-OOB [2] and Data Banzhaf [3] ) are designed for i.i.d. data settings and cannot be directly applied to graphs due to the inherent node dependencies and message-passing mechanisms (as discussed in Section 1).

Therefore, rather than exhaustively adapting various i.i.d. data valuation methods to graphs (which would require detailed modifications to handle graph-specific challenges), we chose to focus on establishing a strong foundation for graph data valuation. We compared with Data Shapley as it represents the fundamental game-theoretic approach to data valuation, allowing us to clearly demonstrate how our graph-specific adaptations improve upon the basic framework. Following your suggestion, we expand our related work Appendix A.1 section to include a more comprehensive discussion of recent data valuation methods and clarify why their direct application to graphs is challenging. We welcome future survey or benchmarking work that comprehensively evaluates various approaches in this emerging field of graph data valuation. Such work would be valuable for the community as this research direction continues to develop.

[1] Kwon, Yongchan, and James Zou. "Beta shapley: a unified and noise-reduced data valuation framework for machine learning." arXiv preprint arXiv:2110.14049 (2021).

[2] Kwon, Yongchan, and James Zou. "Data-oob: Out-of-bag estimate as a simple and efficient data value." International Conference on Machine Learning. PMLR, 2023.

[3] Wang, Jiachen T., and Ruoxi Jia. "Data banzhaf: A robust data valuation framework for machine learning." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

W4.2: Since you focus on node classification tasks, the following paper should also be added: P-Shapley: Shapley Values on Probabilistic Classifiers. Proc. VLDB Endow. 17(7): 1737-1750 (2024) I suggest authors should supplement more related baselines in the experiment and discuss them in the Related Work.

A.5 We appreciate the reviewer pointing out the P-Shapley work and have expanded our related work section to include a more detailed discussion of P-Shapley at Section A.1.

To further examine the potential synergy between P-Shapley's innovation on utility functions and our structural approach, we conducted additional experiments integrating P-Shapley's probability-based utility function (with square calibration) into both PC-Winter and Data Shapley frameworks. The results, presented in Figure 3 and Appendix L, reveal that PC-Winter maintains its performance advantages across different utility function choices. For example, on the Cora dataset, PC-Winter achieves a lower minimum accuracy of 0.599 (indicating better identification of crucial nodes) compared to Data Shapley's 0.620 when using the standard accuracy utility. Similarly, with P-Shapley's utility function, PC-Winter reaches 0.608 versus Data Shapley's 0.625.

This consistent performance advantage demonstrates that PC-Winter's capabilities in handling graph dependencies provide fundamental benefits independent of the utility function design. The results also highlight the complementary nature of the two approaches - while P-Shapley innovates on the utility function, PC-Winter addresses the structural challenges specific to graph data valuation.Integrating these two orthogonal innovations could potentially lead to further enhancements in graph data valuation. For instance, incorporating P-Shapley's probability-based utility within PC-Winter's precedence-constrained framework may offer a better measure of node contributions.

We thank the reviewer for this valuable suggestion, as it not only helped validate the robustness of our method across different evaluation frameworks but also gave promising directions for future research in graph data valuation.

Q1: "There are many symbols in the paper, so it is recommended to provide a symbol table."

A.6 We appreciate this suggestion for improving clarity. Here are the key notations used throughout our paper:

Hello Reviewer 627W, thank you for you constructive reviews! As the discussion period between authors and reviewers is coming to a close, we just wanted to check in with you to see if our responses have addressed your questions. If there’s anything still unclear or any concerns left, please don’t hesitate to let us know! We truly appreciate the time and effort you’ve put into reviewing our paper, and we’re more than happy to further address any remaining feedback. Thank you so much again!

Hello Reviewer 627W, thanks again for your feedback! We noticed that the score update is not yet reflected in the OpenReview system. As the extended discussion period ends soon and we may not be able to post messages on OpenReview, would you mind updating it when convenient?

Hi Reviewer 627W,

As today (December 3rd) marks the final day for author communications on OpenReview, we wanted to send one last gentle reminder about updating the review score that you kindly indicated in your previous response. We noticed that the score update is not yet reflected in the OpenReview system.

You can update your review by locating your original review (search for "Official Review of Submission6724 by Reviewer 627W") and clicking the "Edit" button next to it. This will allow you to update the score to reflect your revised assessment (6).

We greatly appreciate your thoughtful engagement with our work throughout the discussion period.

Best regards,

Authors

W1.1: "For example, the concept of precedence-constrained calculates DFS along the contribution tree. By definition, the contribution tree is just a tree split of the message-passing mechanism. There seems to be no difference in the fine-tuned multi-layer GNN message passing."

"What is the essential difference between precedence-constrained PC-Winter and a fine-tuned multi-layer GNN?"

A1: Thank you for this insightful question. Let us clarify the fundamental difference between PC-Winter and multi-layer GNNs. It is totally correct that contribution trees utilize message-passing mechanisms similar to multi-layer GNNs. However, while they may seem alike, contribution trees and PC-Winter serve a fundamentally different purpose than fine-tuning GNN architectures.

(1) Contribution trees (details in Section 3.2) and PC-Winter take a data-centric perspective, focusing on how individual data elements and their interactions influence model outcomes. Contribution trees naturally represent the feature propagation process in the training graph, as successful message-passing depends on graph connectivity. They capture how unlabeled node features propagate through the graph to influence labeled nodes. PC-Winter defined with contribution trees efficiently quantifies the performance contribution of each element in the training graph. It does this by calculating marginal contributions - how model performance changes when nodes are included or excluded from message-passing subgraphs. By averaging these marginal contributions across different subgraphs, PC-Winter derives a precise value for each data element.

This approach enables PC-Winter to support tasks that require evaluating individual data elements' contributions. For example, it can help modify input graphs based on the importance of graph elements, as demonstrated in our edge addition experiments. It also enables practical applications like making fair data purchase decisions under budget constraints by identifying the most valuable data points.

(2) In contrast, multi-layer GNNs and their fine-tuning processes take a model-centric view. They focus on learning node representations at a layer-wise granularity, aiming to improve overall model performance by adjusting layer architectures. Fine-tuning GNNs typically assumes access to all data and operates at a coarser level compared to PC-Winter's fine-grained, per-element analysis.

While both contribution trees and multi-layer GNNs involve message-passing mechanisms, their purposes and granularity differ significantly. PC-Winter's data-centric perspective and marginal contribution-based valuation set it apart, making it a valuable tool for understanding and leveraging the importance of individual graph data elements. These capabilities complement traditional GNN architecture optimization techniques. In summary, PC-Winter and contribution trees provide a novel, data-centric approach to graph analysis that enables fine-grained evaluation of data elements' contributions, supporting applications beyond the scope of model-centric GNN fine-tuning.

W1.2: "In another example, the authors argue that we need a fine-grained distinction between whether a node is labeled. However, in section 3.5, the authors sum the PC-Winter values of all duplicates to get the final value. It is contrary to the separation of labeled/unlabeled, which goes back to the aggregation of graph neural networks."

A2: Thank you for this insightful observation. Let us clarify these two key aspects of our approach:

The necessity for granular data elements: Our approach recognizes that nodes contribute to model performance in different ways. As we note in Section 3.1. To accurately capture the complex dependencies in graph data, we need to represent nodes' contributions at a granular level. Treating each node's role in influencing different labeled nodes as distinct "duplicates" allows us to properly incorporate the graph structure and message-passing mechanisms into our valuation framework. Without this fine-grained representation, the interdependencies between original nodes would prevent us from defining the necessary graph constraints.

Remapping to original data values: While the "duplicate"-based representation is crucial for capturing graph dependencies during valuation, it's equally important to map these granular values back to the original nodes for practical applications. By aggregating the values of duplicates (Section 3.5), we provide a comprehensive measure of each node's total influence on model performance. This remapping aligns with the core goal of data valuation - quantifying a data point's overall impact. Our experiments validate the effectiveness of this granular representation and aggregation approach. In node dropping experiments (Section 4.2), removing nodes with high aggregated values leads to the most significant performance drops.

W2.1: "Flaws in the experimental settings. Firstly, datasets only contain certain types. Please increase the dataset types to evaluate the adaption ability of PC-Winter, such as OGB (bioinformatics) and Flickr (computer vision), which also need to implement graph data evaluation."

Q3: "Could you expand the categories of datasets? (e.g., bioinformatics, computer vision, etc.)"

A3: We appreciate the reviewers' suggestion about dataset variety. Our response has two parts:

First, our current evaluation uses widely-adopted benchmark datasets that cover diverse graph types and applications - from citation networks (Cora, Citeseer, Pubmed) to co-purchase networks (Amazon-Photo, Amazon-Computer) and co-authorship networks (Coauthor-Physics). These datasets exhibit different characteristics in terms of density and feature distributions, demonstrating PC-Winter's broad applicability.

Regarding OGB bioinformatics datasets: While these are valuable, most OGB Biology datasets (like ogbg-molhiv) are designed for graph-level tasks rather than node-level tasks. Our current focus is on node-level evaluation since it allows for more fine-grained analysis of data value distribution. Nevertheless, extending PC-Winter to graph-level tasks is an interesting direction for future work.

As for the Flickr dataset, recent research[1] has actually shown that graph structure provides limited benefits for vision-based graph datasets in terms of downstream task performance. For instance, Yang et al. (2022) demonstrated that MLPs without graph structure can match or outperform GNNs on such datasets. We conducted additional experiments to verify this finding: We performed 100 random splits (140/1000/1000 for train/val/test) comparing SGC (with graph structure) versus MLP (without graph structure): SGC: 38.87% ± 2.44% (test accuracy) and MLP: 41.57% ± 2.00% (test accuracy). This empirical evidence suggests that for vision-based graphs like Flickr, the graph structure may not be essential for the learning task. Therefore, graph data valuation on such datasets may not provide meaningful insights about the contribution of graph elements.

Following the reviewer's advice about expanding evaluation tasks, we have extended our experiments to include node regression tasks using the US election 2012 dataset (details in Appendix J). The results show that PC-Winter achieves better mean negative MSE (-0.1147) compared to Data Shapley (-0.0993), with steeper performance drops demonstrating its superior ability to identify crucial nodes. This regression task evaluation complements our classification experiments by validating our method's effectiveness on continuous-valued predictions and different model architectures.

Given these considerations, we believe our current benchmark suite provides a robust evaluation of PC-Winter across genuinely graph-structured data where the topology meaningfully impacts model performance. We appreciate the suggestion and welcome future graph data valuation research to other graph tasks such as graph classification.

[1]. Yang, Chenxiao, et al. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mlps.

W2.2: "Secondly, the evaluation matrix may be biased. The authors propose fine-grained data valuation in this paper but adopt a relatively general matrix of the average. Please provide a more comprehensive perspective, such as for labeled/unlabeled classification performance, balanced accuracy (b-Acc), etc."

A4: We appreciate the reviewer's suggestion about evaluation metrics. Following this advice, we have expanded our evaluation to include class-balanced accuracy (b-Acc) alongside the standard accuracy metric. As detailed in Appendix K, PC-Winter demonstrates consistent superior performance under class-balanced accuracy across different datasets.

Specifically, on the Cora dataset, PC-Winter achieves steeper performance drops compared to Data Shapley, with the balanced accuracy decreasing from 0.72 to 0.64, indicating better identification of crucial nodes across all classes. Similar patterns are observed on Citeseer, where PC-Winter's balanced accuracy drops from 0.62 to 0.57, and Pubmed, with a drop from 0.74 to 0.65. These results demonstrate that PC-Winter effectively identifies important nodes without bias toward any particular class. Furthermore, as shown in Figures 3 and 4 of the main paper, we provide separate evaluations for labeled and unlabeled nodes to capture their distinct contributions to model performance. These comprehensive evaluations validate that PC-Winter's effectiveness is robust across different evaluation perspectives.

Q1: "A second prediction task would have been a good addition to the experimental framework."

A1. We appreciate the reviewer's suggestion about expanding the prediction tasks. Following this advice, we have extended our evaluation to node regression tasks using the US election 2012 dataset from [1]. Specifically, we conducted experiments in an inductive setting, sampling 30% of nodes in the training graph as labeled nodes and employing a 2-layer SGC regression model. We compared PC-Winter against Data Shapley, evaluating their performance by dropping unlabeled training nodes in order of their computed data values, from most to least important.

For evaluation, we use negative MSE as our metric. The negative transformation serves two purposes. First, it maintains consistency with our classification experiments, where higher values indicate better performance. Second, it allows us to interpret performance drops similarly to our classification setting - when we remove nodes crucial to the model, we expect to see a decline in negative MSE (becoming more negative). The steeper this decline, the more effectively a method identifies important nodes.

Mean negative MSE serves as a global numeric assessment that measures model performance degradation throughout the entire node dropping process. This metric is calculated by averaging the negative MSE values across all steps as we progressively remove nodes from most to least important. A lower (more negative) mean value indicates that the valuation method consistently identifies nodes whose removal leads to larger performance drops, and thus more crucial to the model's performance. The results (detailed in Appendix J) show that PC-Winter achieves better mean negative MSE (-0.1147) compared to Data Shapley (-0.0993), with steeper performance drops demonstrating its superior ability to identify crucial nodes. This regression task evaluation complements our classification experiments by validating our method's effectiveness on continuous-valued predictions and different model architectures.

[1] Jia, J., & Benson, A. R. Residual Correlation in Graph Neural Network Regression.

Q2: "Efficiency remains a bottleneck for valuation on large graphs."

A2: We appreciate the reviewer's concerns regarding efficiency challenges. While PC-Winter demonstrates improved efficiency over Data Shapley through our innovations (Hierarchical Truncation and Local Propagation) - which led to 10-12x speedups in our experiments (detailed in Appendix I.4) - we acknowledge that scalability to very large graphs remains challenging.

For this paper, our focus was on establishing the core algorithmic foundations for graph data valuation. The efficiency challenge remains an important future direction that could be addressed through complementary approaches such as influence functions [1] for faster parameter estimation or utility learning [2] for quick utility approximation, though these often trade accuracy for speed. This is a fundamental challenge requiring broader community efforts. We view exploring such combinations while maintaining valuation quality as important future work.

[1] Jia et al. Towards Efficient Data Valuation Based on the Shapley Value.

[2] Wang et al. Improving cooperative game theory-based data valuation via data utility learning.

Q3: "Can the authors comment on the data valuation performance based on other graph facets, such as graph density?"

A3: Our experiments demonstrate that PC-Winter maintains robust performance across graphs with varying densities. To quantify graph density, we use the average degree (edges per node) as shown in Table 2 - from sparse citation networks like Citeseer (1.42 edges/node) to denser networks like Amazon-Computer (17.88 edges/node).

The higher density in networks like Amazon-Computer poses computational challenges due to larger computation trees. We address this through our hierarchical truncation strategy (Section 3.4, Appendix D). By adaptively adjusting truncation ratios (r1, r2), we effectively reduce computation overhead in dense regions while maintaining valuation accuracy. For example, in Amazon-Computer (our densest dataset), we achieve strong performance with truncation ratios 0.7-0.9, reducing computation time by ~85% while still outperforming baselines in accuracy (Figure 3 in the manuscript).

These results demonstrate PC-Winter's ability to effectively handle graphs across different density levels through our efficient truncation mechanism.

We believe that we have responded to and addressed all your concerns — in light of this, we hope you consider raising your score. Feel free to let us know if there are outstanding ones!

thank you for your answers, which clarify the issues / questions that were raised.