Precedence-Constrained Winter Value for Effective Graph Data Valuation

Authors: Hongliang Chi, Wei Jin, Charu C. Aggarwal, Yao Ma
Primary area: learning on graphs and other geometries & topologies
Keywords: Data Valuation, Graph Learning, Graph neural network

Abstract:
Data valuation is essential for quantifying data’s worth, aiding in assessing data quality and determining fair compensation. While existing data valuation methods have proven effective in evaluating the value of Euclidean data, they face limitations when applied to the increasingly popular graph-structured data. Particularly, graph data valuation introduces unique challenges, primarily stemming from the intricate dependencies among nodes and the exponential growth in value estimation costs. To address the challenging problem of graph data valuation, we put forth an innovative solution, Precedence-Constrained Winter (PC-Winter) Value, to account for the complex graph structure. Furthermore, we develop a variety of strategies to address the computational challenges and enable efficient approximation of PC-Winter. Extensive experiments demonstrate the effectiveness of PC-Winter across diverse datasets and tasks.

Decision: accept (poster)
Reviewer scores: 6, 6, 5, 5

Reviews and discussion:
<thread>
creation date:
1730363552855

thread_type:
official_review

<thread_object>
creator: reviewer_8mde

<content>
summary:
This paper presents PC-Winter, a novel method for efficient graph data valuation. Additionally, it proposes a range of strategies to reduce computational complexity, allowing for the effective approximation of PC-Winter. Comprehensive experiments validate the practicality and effectiveness of PC-Winter across diverse datasets and tasks.

strengths:
S1: The valuation of data for nodes in graph-based tasks, particularly in Graph Neural Networks (GNNs), is a crucial and intriguing problem.
S2: This paper models the problem of graph data valuation as a distinctive form of a cooperative game.
S3: To address the computational challenges associated with calculating PC-Winter values, this paper introduces a set of strategies, such as hierarchical truncation and local propagation.

weaknesses:
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. This property is also demonstrated in both Figure 1 and Figure 2.
For example, as depicted in Figure 2, node v_0 has three child nodes {w_0, w_1, w_2} while node v_2 has two child nodes {w_3, w_4}, suggesting that these two sets of child nodes do not share any common nodes. Nevertheless, it is typical for these sets of descendants to exhibit some overlap or shared nodes.’
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. Furthermore, the correctness of this computational approach is not supported by any formal proof in the text.
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. This discrepancy warrants further explanation, as the paper does not clearly address why the PC-Winter approach would differ in computational complexity compared to the #P-completeness of the Shapley value in the sharded structure.
W4: The paper does not present any experimental results to demonstrate the scalability of the proposed algorithms.
Xia H, Liu J, Lou J, et al. Equitable data valuation meets the right to be forgotten in model markets[J]. Proceedings of the VLDB Endowment, 2023, 16(11): 3349-3362.

questions:
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.
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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730471828067

thread_type:
official_review

<thread_object>
creator: reviewer_627w

<content>
summary:
This paper presents a new method for graph data valuation based on precedence-constrained winter value. The proposed PC-winter value could help node classification tasks and allow efficient calculation. The experiments are conducted on several public datasets and the results showed that the proposed framework has outperformed mainstream solutions.

strengths:
S1: The research topic of data valuation for graph-structured data is important, which breaks the assumption of being independent and distributing.
S2: The proposed techniques in Section III are solid.
S3: The evaluation is comprehensive and results are promising.

weaknesses:
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.
W2. The length of the article is beyond the space limit.
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. 
W4. Baselines in the Experiment are not SOTA. Data Valuation is a hot spot recently and many solutions have been proposed. Since you focus on node classification tasks, the following paper should also be added:
Haocheng Xia, Xiang Li, Junyuan Pang, Jinfei Liu, Kui Ren, Li Xiong: 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.

questions:
Q1. There are many symbols in the paper, so it is recommended to provide a symbol table.
Q2. The Definition 1 needs further clarification. It is better to differentiate between Computation Tree and k-Computation Tree. That is, the name of Definition 1 should be k-Computation Tree.
Q3. The content in Table 2 is confused.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730641099918

thread_type:
official_review

<thread_object>
creator: reviewer_xxt4

<content>
summary:
This paper proposes a novel Precedence-Constrained Winter (PC-Winter) value to evaluate graph data, aiming to cover the complex graph structures and unbearable estimation costs. It transfers graph data valuation into a cooperative game theory with pruning strategies and approximation. Experiments show that the PC-Winter value does pick nodes with more contribution.

strengths:
S1: Interesting perspective. In this paper, the authors propose a novel view to transfer graph data valuation into a cooperative game theory, which gives the community a different insight into the problem.
S2: Sufficient motivation. Directly transferring existing data valuation methods to graph data is limited by the complex structures and dependencies between nodes. It is a valuable problem and a hot topic recently.
S3: Good organization. This paper has a sound representation and a reasonable layout.

weaknesses:
W1: Lack of necessary explanations. 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. 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. The absence of detail will not be able to prove the innovation of the design, which is not convincing enough.
W2: 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. 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. Please see more details in the Questions part.

questions:
Q1: As for W1, What is the essential difference between precedence-constrained PC-Winter and a fine-tuned multi-layer GNN?
Q2: As for W1, what is the basis for considering all duplicates? Does each duplicate contribute to the final score? 
Q3: As for W2, could you expand the categories of datasets? (e.g., bioinformatics, computer vision, etc.)
Q4: How does the hierarchical truncation work when it meets the long-range nodes interaction? For example, two similar nodes in two communities in more than K hops.
Q5: Could you explain the similarity between Data Shapley and PC-Winter on every plot? Especially for Figure 3, the plots of Data Shapley and PC-Winter are in a 'U' shape, and others are more like a '-' shape.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717932678

thread_type:
official_review

<thread_object>
creator: reviewer_zgxe

<content>
summary:
This paper tackles the problem of modeling and computing the value of data in learning, when graphs are the data modality. The work is the first to consider this important topic. 

The authors introduce the precedence constrained Winter value model (PC-Winter). 

They also describe how to approximately compute such values, for either nodes or edges in a graph. 

Experiments on an inductive node classification task are done, using 6 real world datasets. 

Baselines (Random value, Degree value, Leave-one-out (LOO) value, and Data Shapley value) are used as baselines, by either removing high value nodes or adding high value edges. 

Clearly, efficiency is a major challenge in this framework, as emphasized by the authors as well.  

Moreover, it would have been interesting to include another prediction task.

strengths:
First to study an important problem, data valuation for graphs. 

Clearly written paper. 

Clear development and description of the proposed valuation model. 

Reasonable experimental evaluation.

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

Efficiency remains a bottleneck for valuation on large graphs.

questions:
Can the authors comment on the data valuation performance based on other graph facets, such as graph density?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732504612314

thread_type:
official_comment

<thread_object>
creator: area_chair_auga

<content>
title:
[Urgent]: Please react to the authors' rebuttal

comment:
Dear Reviewers,

The authors have posted a rebuttal to the concerns raised. Please read the rebuttal and see if this changes your opinion on the work. We have only two days left. Hence, we urgently need your reactions to the rebuttal.

best,

AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1732681631475

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank You All for Your Feedback and Updates to the Paper Based on Your Guidance

comment:
We appreciate all reviewers for their valuable feedback. In response to your comments:

1. We've conducted additional experiments on the US election 2012 dataset for node regression tasks, demonstrating PC-Winter's superior performance in identifying crucial nodes with consistently better results than Data Shapley (**Appendix J**).

2. We've expanded our evaluation metrics by including class-balanced accuracy, showing PC-Winter's robust performance across different datasets in **Appendix K**. PC-Winter consistently demonstrates better identification of crucial nodes across all classes compared to Data Shapley. 

3. We've integrated P-Shapley's probability-based utility function with both PC-Winter and Data Shapley frameworks (**Appendix L**), showing PC-Winter maintains its advantages across different utility function choices. We've also added a description in **Appendix A.1 Related Work**.

4. We've added a new inductive graph split visualization and provided a new visual overview illustrating the PC-Winter value estimation procedure in **Appendix M** .

5. We've added a comprehensive notation table in **Appendix N**, organizing notations into distinct conceptual categories to facilitate better understanding of our methodology and theoretical framework.

6. We've provided additional explanation of the dataset statistics in **Table 2** and **Section G.2**.

7. We've clarified in **Appendix I.5** that while computing the exact PC-Winter value remains #P-complete (similar to traditional Shapley value), our approximation framework achieves polynomial-time efficiency through Monte Carlo permutation sampling.

8. We've carefully revised the manuscript to enhance readability and clarity, particularly in **Section 3** where we detail our methodology.


These updates provide more comprehensive validation of our method's effectiveness. We sincerely thank you for pointing out these areas for improvement. 

We welcome your further feedback on our rebuttal. With the extended discussion period, we now have more time to incorporate your insights. **Thank you for your time and valuable contributions in helping us improve this work!**
</content>
</thread_object>

</thread>
<thread>
creation date:
1732689079072

thread_type:
official_comment

<thread_object>
creator: area_chair_auga

<content>
title:
[Urgent]: Please respond to rebuttal

comment:
Dear Reviewers 627W and  8Mde,

The authors have posted a rebuttal and the deadline to revise the manuscript closes tomorrow. Since you are the reviewer, your reaction to the rebuttal is urgently needed. 

best, 

Area Chair
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents an algorithm to assess the utility of a data entity when the data is modeled as a graph. The paper introduces the idea of Precedence-Constrained Winter (PC-Winter) Value, which transfers graph data valuation into a cooperative game theory exercise. The reviewers are largely in support of this work, although some concerns on its scalability remain open.