Research map / Graph learning / GNN architectures
Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SGUL, a label-free utility-learning framework for valuing test-time neighbors in GNN graph inference, using transferable data/model features and directly optimizing fitted Shapley values.
Problem
Valuing the neighbors of test nodes for GNN inference is unexplored because test labels are unavailable, and existing utility-learning methods don't transfer to new player sets and optimize accuracy rather than Shapley values.
Approach
Replace player-dependent binary inputs with transferable data-specific and model-specific features computed on test subgraphs, and use feature Shapley values (via a linear-utility decomposition theorem) as inputs so the regression directly fits Shapley values rather than accuracy.
Key results
- SGUL-Shapley achieves lower in-sample MSE than SGUL-Accuracy across all inductive datasets with SGC (p < 0.05).
- SGUL-Shapley outperforms SGUL-Accuracy in 10 of 14 dataset-model combinations in node dropping experiments.
- SGUL-Shapley uses about 14% of the memory of SGUL-Accuracy on Amazon-ratings (16.59 MB vs 115.62 MB).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive node dropping, 14 dataset-model combinations | node-dropping performance: 10 out of 14 | Helped |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive datasets with SGC | in-sample MSE | Helped |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive, Citeseer | Time (s): 0.64 -> 1.54 | Helped |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive, Amazon-ratings | Memory (MB): 16.59 -> 115.62 | Helped |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive, CS | Time (s): 0.52 -> 0.50 | Hurt |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Transductive, Citeseer | Time (s): 0.51 -> 0.59 | Hurt |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive and transductive datasets | Memory (MB) | Helped |
| use Shapley-guided instead of accuracy-based optimization (ablation) | SGUL · Inductive node dropping, larger datasets and models | node-dropping performance | Helped |
| rank nodes using SGUL rather than baseline valuation methods | SGUL · Inductive node dropping, Cora and Citeseer | accuracy during node removal | Helped |
| rank nodes using SGUL rather than baseline valuation methods | SGUL · Inductive node dropping, Amazon-ratings | accuracy during node removal | Helped |
| rank nodes using SGUL rather than baseline valuation methods | SGUL · Transductive node dropping, Cora, Citeseer, and Pubmed | accuracy during node removal | Helped |
Limitations
- Relies on handcrafted homophily, distance, and confidence features whose correlation with accuracy is assumed rather than proven.
- Non-negativity and L1 constraints are imposed for interpretability and sparsity, which may limit expressiveness.
- Evaluation limited to SGC and GCN with node dropping metrics on node classification.
Experimental setup
Datasets: Cora Citeseer Pubmed CS Physics Amazon-ratings Roman-empire ogbn-arxiv
Benchmarks: Cora Citeseer Pubmed CS Physics Amazon-ratings Roman-empire ogbn-arxiv
Metrics: AUC of node dropping accuracy curves in-sample MSE fitting time peak memory
Baselines: ATC-MC ATC-NE DoC GNNEvaluator Maximum Confidence Class Confidence SGUL-Accuracy
Builds on: Data Shapley PC-Winter GNNEvaluator Average Thresholded Confidence
Closest papers by meaning
- Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks (ICLR 2025 · similarity 0.87)
- GOAt: Explaining Graph Neural Networks via Graph Output Attribution (ICLR 2024 · similarity 0.86)
- Generalized Priority-Aware Shapley Value (NeurIPS 2026 · similarity 0.85)
- DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.85)
- Rethinking Data Shapley for Data Selection Tasks: Misleads and Merits (ICML 2024 · similarity 0.85)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.