# Precedence-Constrained Winter Value for Effective Graph Data Valuation

arXiv: https://arxiv.org/abs/2402.01943 · HTML: https://mlsanity.com/paper/2402.01943/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 44 references that are in the map.
- First posted on arXiv 2 Feb 2024.

## Builds on (most cited first, 26 of 26)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms](https://mlsanity.com/paper/1908.08619/) (2019)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [Data Valuation using Reinforcement Learning](https://mlsanity.com/paper/1909.11671/) (2019)
- [LAVA: Data Valuation without Pre-Specified Learning Algorithms](https://mlsanity.com/paper/2305.00054/) (2023)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [Sampling methods for efficient training of graph convolutional networks: A survey](https://mlsanity.com/paper/2103.05872/) (2021)
- [A Survey on Data Pricing: from Economics to Data Science](https://mlsanity.com/paper/2009.04462/) (2020)
- [Data-OOB: Out-of-bag Estimate as a Simple and Efficient Data Value](https://mlsanity.com/paper/2304.07718/) (2023)
- [Data Valuation Without Training of a Model](https://mlsanity.com/paper/2301.00930/) (2023)
- [Deep Social Collaborative Filtering](https://mlsanity.com/paper/1907.06853/) (2019)
- [CS-Shapley: Class-wise Shapley Values for Data Valuation in Classification](https://mlsanity.com/paper/2211.06800/) (2022)
- [Characterizing the Influence of Graph Elements](https://mlsanity.com/paper/2210.07441/) (2022)
- [Item Graph Convolution Collaborative Filtering for Inductive Recommendations](https://mlsanity.com/paper/2303.15946/) (2023)
- [Simple and Powerful Architecture for Inductive Recommendation Using Knowledge Graph Convolutions](https://mlsanity.com/paper/2209.04185/) (2022)

## Built on by (most cited first, 6 of 6)

- [Disentangled Structural and Featural Representation for Task-Agnostic Graph Valuation](https://mlsanity.com/paper/2408.12659/) (2024)
- [LossVal: Efficient Data Valuation for Neural Networks](https://mlsanity.com/paper/2412.04158/) (2024)
- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation](https://mlsanity.com/paper/2503.18195/) (2025)
- [Explaining Graph Neural Networks for Node Similarity on Graphs](https://mlsanity.com/paper/2407.07639/) (2024)
- [Efficient Decentralized Multi-task Dataset Valuation via Model Merging](https://mlsanity.com/paper/2607.03346/) (2026)

## Abstract (arXiv)

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.