Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation

Authors: Hongliang Chi, Qiong Wu, Zhengyi Zhou, Yao Ma
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Learning, Data Valuation, Graph Neural Networks, Data-centric AI

Abstract:
Graph Neural Networks (GNNs) have demonstrated remarkable performance in various graph-based machine learning tasks, yet evaluating the importance of neighbors of testing nodes remains largely unexplored due to the challenge of assessing data importance without test labels. To address this gap, we propose Shapley-Guided Utility Learning (SGUL), a novel framework for graph inference data valuation. SGUL innovatively combines transferable data-specific and modelspecific features to approximate test accuracy without relying on ground truth labels. By incorporating Shapley values as a preprocessing step and using feature Shapley values as input, our method enables direct optimization of Shapley value prediction while reducing computational demands. SGUL overcomes key limitations of existing methods, including poor generalization to unseen test-time structures and indirect optimization. Experiments on diverse graph datasets demonstrate that SGUL consistently outperforms existing baselines in both inductive and transductive settings. SGUL offers an effective, efficient, and interpretable approach for quantifying the value of test-time neighbors.

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

Reviews and discussion:
<thread>
creation date:
1730114669641

thread_type:
official_review

<thread_object>
creator: reviewer_cyjv

<content>
summary:
This paper is well-written. It combines transferable data-specific and modelspecific features to approximate test accuracy without relying on G-T labels.

strengths:
1. This work introduces a transferable feature extraction method that transforms player-dependent inputs into general features.

2. Authors claim that they are the first to formulate the graph inference data valuation problem.

3. Code is open-source and readable.

weaknesses:
1. Lack of comparison with other works. GNNEvaluator, DoC, ATC are the compared baseline in your experiment, but readers are not yet clear about the main differences between these baselines and your method. I noticed that there is an introduction in the appendix, but there is a lack of comparison.

2. The method in this work has special optimization in structure(Sec 3.2), but lacks experimental verification of this optimization.

questions:
1. Is there any experiment to show the importance of  the structure-aware Shapley value?


2. Since you are the first to formulate the graph inference data valuation problem, what's the main different between your work and GNNEvaluator[1]?It seems that both of you are methods for verifying GNN performance without  labels.

3. In your code, Which part of the paper does 'data_without_edges' correspond to? Why remove the graph structure for testing？



[1] GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels, arxiv 2310.14586
</content>
</thread_object>

</thread>
<thread>
creation date:
1730375334067

thread_type:
official_review

<thread_object>
creator: reviewer_kedx

<content>
summary:
In this paper, the authors design a shapely-guided unility learning framework for graph inference data valuation, which termed SGUL. SGUL combines transferable data-specific and model-specific features to test data without relying on labels.

strengths:
1. The author has provided the code to ensure the reproducibility of the paper’s results.

2. The author has supplied partial theoretical proofs to support the claims made in the study.

weaknesses:
1.  In Figure 1, the author has chosen a comparison method that only includes one paper from 2024. Please incorporate more recent comparative experimental methods.


2. The results of the comparative experiments by the author are perplexing. Why does SGUL consistently perform the worst across all datasets? The author explains that SGUL can identify important nodes in the graph structure. However, could it be that the design methodology is ineffective, leading to the model’s poor performance?


3. In the field of graph neural networks, test-time training methods are widely used to address distribution shift issues in test data[1,2,3,4]. These methods also do not require labels. How does your approach compare to test-time training-based graph methods, and what advantages does it offer?


4. In Theorem 1, why is the variable U suddenly linear when it was previously described in exponential form (as in Equation 1)? The transition lacks a clear explanation, even though the author provides a proof based on the linear function.

5. There are typographical errors, such as consecutive “for instance” phrases in line 206.

6. The advantages in terms of time and space efficiency are not clearly demonstrated and need to be supported by experimental evidence.

[1] Jin W, Zhao T, Ding J, et al. Empowering graph representation learning with test-time graph transformation[J]. arXiv preprint arXiv:2210.03561, 2022

[2]Wang L, He D, Zhang H, et al. GOODAT: Towards Test-Time Graph Out-of-Distribution Detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2024, 38(14): 15537-15545.

[3]Zheng X, Song D, Wen Q, et al. Online GNN Evaluation Under Test-time Graph Distribution Shifts[J]. arXiv preprint arXiv:2403.09953, 2024.

[4]Pi L, Li J, Song L, et al. Test-Time Training with Invariant Graph Learning for Out-of-Distribution Generalization[J]. Available at SSRN 4886269.

questions:
Please see weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730871773650

thread_type:
official_review

<thread_object>
creator: reviewer_u5np

<content>
summary:
The paper proposes a novel framework called Shapley-Guided Utility Learning for the graph-structured data valuation problem. The proposed method tackle with two problems associated with graph-structured data valuation: lack of test labels and indirect optimizaiton of utility function.

strengths:
1. The paper is well written and organized.
2. The method is well motivated and justified.
3. The experimental results shows promising performance.

weaknesses:
1. The details of permuation sampling process is not clear. Could authors elaborate on the sampling process?
2. The proposed data-specific features, such as edge cosine similarity, appear to favor graph homophily. When applying this framework to heterophilous graphs, it raises the question of whether these features would still be effective.  How is edge cosine similarity adapted for both homophilous and heterophilous graphs? Additional discussion on this point could be valuable.
3. It seems that the ablation study on the investigation of the seperate contribution of data-specific features and model-specific feature is missisng.

questions:
see weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1731465682174

thread_type:
official_review

<thread_object>
creator: reviewer_psyo

<content>
summary:
The paper has studied the graph inference data valuation problem by developing a new data-driven utility function and providing theoretical insights to enable direct optimization through the Shapley value decomposition. Extensive experiments on public datasets were provided in terms of multiple evaluation protocols.

strengths:
- A new definition of the structure-aware Shapley value has been introduced to facilitate graph data valuation. 
- The paper has extensively discussed the limitations of applying Shapley values on graph-structured data from the utility estimation and indirect optimization perspectives, resulting in the proposed SGUL framework. 
- The experiment is well designed to comprehensively access both utility estimation and data valuation, covering different graph structures, downstream tasks, and multiple evaluation protocols.

weaknesses:
- While the proposed method seems novel and technically sound to me, it would be better to involve a more detailed comparison and discussion with existing works (e.g., [Chi et al., 2024]) in the main text and experimental analysis. 
- It remains unclear if the proposed SGUL is scalable to large graph benchmarks, such as Open Graph Benchmark (Hu et al., 2020), due to the introduction of an $\ell_1$ penalty in eq (3).
- The methodology is somewhat hard to follow and less self-contained. An illustration framework or outline algorithm would be much helpful.

questions:
While it is interesting and novel to connect utility learning and Shapley value prediction through a linear projection, the training process of the data-driven utility function and how to obtain feature Shapley values ($\psi_i$) remain unclear to me. 
- How to obtain/initialize $\psi_i$?
- Can `Theorem 1` be applied to general domains other than graph-structured data? 
- Is there any limitation or assumption for `Theorem 1`?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732506773623

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank You All and Paper Updates

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

1. We've expanded the discussion on  **label-free model evaluation methods, retraining-based methods, and test-time training & augmentation methods** in **Appendices D.3, D.4, and D.5**. A summary of these discussions has been added to the **Related Work** section in the main text.

2. To better understand feature contributions, we've included coefficient tables (**Table 1 in Appendix L**) and also conducted an ablation study (**Appendix L**), showing how data-specific and model-specific features contributes to our utility learning framework.

3. We've provided a description of the training process for our accuracy-based variant and baselines in **Appendix B**.

4. To clarify our methodology, we've introduced four algorithms in **Appendix M**:

   - Algorithm 1: Shapley-Guided Utility Learning (our proposed SUGL method)

   - Algorithm 2: Test-time Structure Value Estimation (estimate structure-aware Shapley values/testing neighbor data values)

   - Algorithm 3: Node Dropping Evaluation Protocol (experimental validation protocol)

   - Algorithm 4: Precedence-Constrained Permutation Sampling (generate valid permutations)

5. We have carefully revised the manuscript to enhance readability and correct typos. 

These updates aim to make our work more accessible. We sincerely thank you for pointing out these issues.

 **We welcome your further feedback on our rebuttal. Thank you for your time and insights in helping us improve this work！**
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper presents a new Shapley-Guided Utility Learning for the graph-structured data valuation problem. Reviewers agreed the paper is well written and clearly organized. The paper introduces a new definition of the structure-aware Shapley value, which will be helpful for graph data valuation. In addition, the experiments are well designed, and the results are extensive and convincing. Meanwhile, reviewers raised some concerns about scalability, details of sampling process, missing ablation studies, and complexity analysis. The authors have provided detailed responses to address these concerns during the rebuttal and discussion period.