Research map / Graph learning / Graph self-supervised learning
Precedence-Constrained Winter Value for Effective Graph 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 PC-Winter, a precedence-constrained Winter-value data valuation for graph nodes and edges that uses DFS-enumerated permissible permutations with truncation and local propagation to approximate values efficiently.
Problem
Data valuation for graph-structured data is hard because nodes (labeled and unlabeled) affect GNN performance through message passing with interdependencies, and exact Shapley-style valuation requires exponentially many permutations and repeated GNN retraining.
Approach
Model the GNN training as a cooperative game whose players are computation-tree duplicates of nodes, organized by a contribution tree; restrict Shapley-style permutations to those satisfying a Level Constraint and a Precedence Constraint, generate them via DFS, and approximate with hierarchical truncation, local propagation, and SGC-based utility.
Key results
- Dropping high-value unlabeled nodes identified by PC-Winter causes the largest accuracy decline, typically outperforming the best baseline Data Shapley by a considerable margin after removing 10-20% of nodes.
- On Cora, adding 10% of PC-Winter-selected edges reaches 72.9% accuracy, above the full graph's 71.3%.
- Hierarchical truncation reduces model re-trainings on Amazon-Photo from 147664 to 6258 and on Amazon-Computer from 317959 to 12139.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PC-Winter rather than Data Shapley to rank unlabeled nodes for removal | GNN node valuation · Cora, Citeseer, Pubmed, Amazon-Photo, Amazon-Computer, Coauthor-Physics | test accuracy after dropping high-value unlabeled nodes | Helped |
| select edges by PC-Winter value rather than Random, LOO, or Edge-Betweenness | GNN edge valuation · Cora and other datasets | accuracy as edges are added | Helped |
| use 10% of PC-Winter-selected edges instead of the full graph | GNN edge addition · Cora | accuracy: 71.3% -> 72.9% | Helped |
| add the Level Constraint to PC-Winter permutations (ablation) | PC-Winter graph data valuation · Cora and Amazon-Photo; also reported across all six datasets | node-dropping performance | Helped |
| add the Precedence Constraint to PC-Winter permutations (ablation) | PC-Winter graph data valuation · Cora and Amazon-Photo; also reported across all six datasets | node-dropping performance | Helped |
| increase the number of sampled permutations (ablation) | PC-Winter · Cora, Amazon-Photo, and other datasets | node-dropping performance | Helped |
| use 50 to 100 permutations instead of converged sampling (ablation) | PC-Winter · Cora and Amazon-Photo | node-dropping performance versus Data Shapley: 50 and 100 permutations | No clear effect |
| increase first-hop truncation to 0.9 (ablation) | PC-Winter hierarchical truncation · Cora and Citeseer | node-valuation performance: 0.9-0.7 | No clear effect |
| increase first-hop truncation to 0.9 (ablation) | PC-Winter hierarchical truncation · Pubmed | node-valuation performance: 0.9-0.7 | Hurt |
| increase truncation at either first- or second-hop level (ablation) | PC-Winter hierarchical truncation · Amazon datasets and Coauthor-Physics | node-valuation performance: 0.9-0.7; 0.5-0.9 | Hurt |
| apply hierarchical truncation (ablation) | PC-Winter value estimation · Citeseer | model retrainings: 1388 -> 535 | Helped |
| apply hierarchical truncation (ablation) | PC-Winter value estimation · Amazon-Photo | model retrainings: 147664 -> 6258 | Helped |
Limitations
- Scalability still limited, as acknowledged by the authors.
- Restricted to homogeneous graphs.
- Node-level evaluation of labeled nodes is reported separately from unlabeled nodes.
Experimental setup
Datasets: Cora Citeseer Pubmed Amazon-Photo Amazon-Computer Coauthor-Physics
Benchmarks: Cora Citeseer Pubmed Amazon-Photo Amazon-Computer Coauthor-Physics
Metrics: test accuracy under node dropping test accuracy under edge addition
Closest papers by meaning
- Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation (ICLR 2025 · similarity 0.82)
- KAIROS: Scalable Model-Agnostic Data Valuation (NeurIPS 2025 · similarity 0.82)
- Generalized Priority-Aware Shapley Value (NeurIPS 2026 · similarity 0.81)
- DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation (NeurIPS 2024 · similarity 0.81)
- No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets (ICML 2025 · similarity 0.81)
- What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions (NeurIPS 2025 · similarity 0.80)
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.