Precedence-Constrained Winter Value for Effective Graph Data Valuation
Authors: Hongliang Chi
Wei Jin
Charu C. Aggarwal
Yao Ma
Venue: ICLR 2025 Poster (2025)
Keywords: Data Valuation
Graph Learning
Graph neural network
Primary area: learning on graphs and other geometries & topologies

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.

Published as a conference paper at ICLR 2025
PRECEDENCE-CONSTRAANE WINTER VALUE FOR EF- FECTIVE GRAPH DATA VALUATION
Hongliang Chi', Wei Jin", Charu Aggarwal,, Yao Ma' Rensselaer Polytechnic Institute, Troy, NY, United States *Emory University, Atlanta, GA, United States SIBM T. J. Watson Research Center, Yorktown Heights, NY, United States (chih3erpi. eddu, wei. jingemory. edu, charu@us iim. com, may13erpi.edu
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 graph-structured data. Particularly, graph data valuation introduces unique challenges, primarily stemming from the intricate dependencies among nodes and the growth value estimation costs. To address the challenging problem of graph data valuation, we put forth an innovative solution, Precedene-Constrained
Precedence- Constrained Winter (PC-Winted graph structure. Furthermore, we develop variety of strategies to address the computational challenges and enable efficient approximation PC-Winted Ex- tensive experiments demonstrate the effectiveness of CC-Winte across diverse datasets and tasks.
Value, to account for the complex
INTRODUCTION
The abundance of training data has been a key driver of recent advancements in machine learning (ML) (Zhou al. 2017). As models and the requisite training data continue expand in scale,
data valuation has gained significant attention due to its ability to quantify the usefulness of data
for ML tasks and determine fair compensation (Peil 2020 [Sim et al., 2022). Notable techniques in this field include Data Shapley (Ghorbani & Zou 2019) and its successors (Kwon & Zou| 2021
Wang & Jial 2023 Schoch et al., 2022), which have gained prominence in assessing data value. Despite the promise of these methods, they primarily designed for Euclidean data, where samples are often assumed to be independent and identically distributed (i.i.d.). Given the prevalence of graph-structured data in the real world (Fan et al.) 2019) Shahsavari & Abbeel 2015 Li et al.), there arises a compelling need to perform data valuation for graphs. However, due to the interconnected nature of samples (nodes) on graphs, existing data valuation frameworks not directly applicable to addressing the graph data valuation problem.
In particular, designing data valuation methods for graph-structured data faces several fundamental challenges: Challenge I: Graph machine learning algorithms such as Graph Neural Networks (GNNs) (Kipf & Welling 2016 Veličković al. 2017;) Wu al.) 2019) often involve both labeled and unlabeled nodes in their model training process. Therefore, unlabeled nodes, despite their absence of explicit labels, also hold intrinsic value. Existing data valuation methods, which typically assess a data point's 's value based on its features and the associated label, do not readily accommodate the valuation of unlabeled nodes within graphs. Challenge II: Nodes graph contribute to model performance in an interdependent and complex way: (1) Unlabeled nodes, while not providing direct supervision, can contribute to model performance by potentially affecting multiple labeled nodes through message- paasagg...ssngg..... (2) Labeled nodes, the other hand, contribute by providing direct supervision signals for model training, and similarly to unlabeled nodes, they also contribute by affecting other labeled nodes through peessage-passing Challenge III: Traditional data valuation methods are often computationally expensive due to repeated retraining of models (Ghorbani & Zou 2019). The challenge is magnified in the context of graph-structured data, where samples contribute
Code released https::////............tt. wwg.tt....... com raanh chi wwwphhhhhhhhhhheeeeee wawaaaaionnn

---

Published as a conference paper at ICLR 2025
model performance in multifaceted manners. Additionally, the inherent meesage - mechanism in GNN models further amplifies the computational demands for model re- re-training.
In this work, make the first attempt to explore the challenging graph data valuation problem, to the best of our knowledge. In light of the aforementioned challenges, we propose the Precedence- Constrained Winter (CCWWnttrr) Value, a pioneering approach designed to intricately unravel and analyze the contributions nodes within graph structures, thereby offering a detailed perspective on the valuation of graph elements. Our key contributions are as follows:
We formulate the graph data valuation problem as a unique cooperative game (Von Neumann & Morgenstern 2007) with special coalition structures. Specifically, we decompose each node in the graph into several "players" within the game, each representing a distinct contribution to model performance. We then devise the PC-Winter address the game, enabling the accurate valuation of all players. The P PC-Winter values of these players can be conveniently combined to generate values for nodes and edges.
To tackle the computational challenges of calculating PC FC-Winter values, we develop set of strategies including hierarchical truncation and local propagation. These strategies together enable efficient approximation of PC-Winter values.
Extensive experiments on various datasets and tasks, along with detailed ablation studies and parameter analyses, validate the effectiveness of P PC-Wint and provide insights into its behavior.
PRELIMINARY AND RELATED WORK
In this section, delve into some fundamental concepts that are essential for developing methodology. More extensive literature exploration can be found in Appendix A For ease of reference, a comprehensive table of notations used throughout this paper is provided Appendix N
2.1 COOPERATIVE GAME THEORY
Cooperative game theory explores the dynamics where players, or decision-makers. can form alliances, known as coalitions, to achieve collectively beneficial outcomes (Branzei et al. 2008 Curiel 2013). The critical components of such game include player set P consisting of all players in the game and a utility function U(.. which quantifies the value or payoff that each coalition of players can attain. Shapley Value (Shapley al. 1953) is developed to fairly and efficiently distribute payoffs (values) among players.
Shapley value. The Shapley value (P(PUU) for player i E P can be defined on permutations of P as follows.
6. (P(PUU)
Σ
(P: U (i)) (P.))
(I)
[I(P) TEl(())
where II(P) denotes the set of all possible permutations of P with [I[()] denoting its cardinality, and P. is predecessor set of i, i.e, the set of players that appear before player in permutation n:
p.a = (j E x(f) < (())
(2)
The Shapley value considers each player's contribution every possible coalition they could be a part of. Specifically, in (I) for each permutation π, the marginal contribution of player is calculated as the difference the utility function U when player is added to an existing coalition P. The Shapley value d; (P, U) for i is the average of these marginal contributions across all permutations in II(P). The Shapley value has been widely applied in ML for various tasks such as data valuation (Ghorbani & Zou, 2019: 2019 Jia et al., 2019) and model explanation (L.iu et al.) 2022b Frye et al.) 2020). In the context of graph MI,, it has been primarily used for GNN explainability (Duval & Malliaros 202T Yuan et al. |021 Mastropictro et al.) 2022 Akkas & Azad 2024). A more detailed discussion Shapley Value on graph ML can be found in Appendix|A.3. A.3
Winter Value. The Shapley value is to address cooperative games, where players collaborate freely and contribute on an equal footing. However, in many practical cases, cooperative games, exhibit Level Coalition Structure (Niyato al.) [001]] Vasconcelos al. 2020 Yuan et al. 2016), reflecting a hierarchical organization. For instance, consider a corporate setting where different tiers of management and staff contribute to project in varying capacities and with differing degrees of
2

---

Published as a conference paper at ICLR 2025
decision-make making authority. Players within such game are hierarchically categorized into nested The outermost and largest ellipse represents the entire coalition and each of the smaller ellipse within the largest ellipse symbolizes a "sub-coaliation" at various hierarchical levels. Collaborations originate within the smallest sub-coalitions at the base level (illustrated by the innermost ellipses in Figure [
coalitions with several levels, as depicted in Figure [1]
These base units are then integrated into the next level, facilitating inter-coalition collaboration and enabling contributions ascend to higher levels. This bottom-up flow of contributions continues, with each layer consolidating and passing on inputs the next, cul- minating in multi-leveled collaborative contribution to the final objective of the entire coalition. To accommodate such complex Level Coalition Structure, Winter value (Winter 1989) was intro- duced. Winter value follows similar permutation based definition as Shapley Value (II) but with only a specific subset of permutations that respect the Level Coalition Structure. In these permutations, members of the same sub-coalition, regardless of the level, must appear in unbroken sequence without interruptions. This ensures that the value attributed to each player is consistent with the level structure of the coalition. A formal definition of the Winter value can be found in Appendix B
Figure 1: Level Coalition Struc- ture
2.2
DATA VALUATION AND DATA SHAPLEY
Data valuation quantifies the contribution of data points for machine learning tasks. The seminal work (Ghorbani & Zou 2019) introduces Data Shapley, applying cooperative game theory to data valuation, where training samples are the players P. and the utility function functinn U assesses a model's performance subsets of these players using validation set. With p and U, data values can be
calculated with (T). However, Data Shapley and subsequent methods (Ghorbani & Zou 2019 K Kwon & Zou| 2021 Wang & Jial (023) primarily focus on i.i.d. data, overlooking potential coalitions or dependencies among data points.
2.3 GRAPHS AND GRAPH NEURAL NETWORKS
Consider graph g = [V,E} where V denotes the set of nodes and È denotes the set of edges. Each node U; E V carries feature vector x; E IRd, where d is the dimensionality of the feature space. Additionally, each node is associated with label yı from set of possible labels C. We assume that only a subset Vi2 C V are with known labels.
GNNs (Kipf & Welling 2016 Veličković et al. 2017 Wu et al. 2019) are prominent models for graph ML tasks. Specifically, from local perspective for node 64, the k-th GNN layer generally performs feature averaging process as (1)
Σ Wh Wh((t))) (k-1) where W is the parameter By (e,)
deg(se)
matrix, deg(w;) and (w:) denote the degree and neighbors of node U; respectively. After total of
K layers, h (K) are utilized as the learned representation of ug. Such a feature aggregation process
can be also described with a K-level computation tree (Jegelka 2022) rooted on node i;-
Definition (Computation Tree). For a node v, E V, its K-level computation tree corresponding to K -layyer GNN model is denoted as T.K with v; as its root node. The first level of the tree consists of the immediate neighbors of Vú, and each subsequent level is formed by the neighbors of nodes in the continues, expanding through successive levels of
level directly above. This pattern of branching neighboring nodes until the depth of the tree grows to K.
The feature aggregation process in a K -layerr GNN can be regarded as a bottom-up feature propagation process in the computation tree, where nodes in the lowest level are associated with their initial features. Therefore, the final representation h (K) of node i; is affected by all nodes within its K-hop neighborhood, which referred to as the receptive field of node v,. The GNN model is trained
using the (l) yt) pairs, where each labeled node v; in Vi is represented by its final representation and corresponding label. Thus, in addition to labeled nodes, those unlabeled nodes that are within the receptive field of labeled nodes also contribute model performance.
3

---

Published as a conference paper at ICLR 2025
3 METHODOLOGY
Machine learning models designed for Euclidean data traditionally assume independent and identically distributed (i.i.d)) samples, where the contribution of each labeled sample model performance manifests through direct supervision signals. In contrast, graph-structured data presents fundamentally different contribution patterns due the interdependencies between nodes. Specifically, as discussed in Section 2.3 both labeled and unlabeled nodes are involved in the training stage through the feature aggregation. Next, we discuss how these nodes contribute to GNN performance.
Observation 1. Unlabeled nodes influence GNN performance by affecting the final representation of labeled nodes. On the other hand, labeled nodes can contribute to GNN performance in two ways: (1) they provide direct supervision signals to GNN with their labels, and just just like unlubeled nodes, they can impact the final representation of other labeled nodes through feature aggregation. Note that both labeled nodes and unlabeled nodes can affect the final representations of multiple labeled nodes, as long as they lie within the receptive field of these labeled nodes. Hence, a single node can make multifaceted and heterogeneous contributions to GNN performance by affecting multiple labeled nodes in various manners.
3.1 THE GRAPH DATA VALUATION PROBLEM
Based on Observation 1 due to the heterogeneous and diverse effects of labeled and unlabeled nodes, it is necessary to perform fine-grained data valuation on graph data elements. In particular, propose to decompose a node into distinct "duplicates" corresponding to their impact on different labeled nodes. The fundamental objective is to quantify the value of these duplicates in a way that captures their unique roles in the message-passingg process. Following existing literature (Ghorbani &
Zou 2019) Wang & Jia [023 Yan & Procaccia 2021p, we approach the graph data value problem through a cooperative game.
Definition 2 (Player Set). The player set P in a graph data valuation game is defined as the union of nodes in the computation trees of labeled nodes. Duplication of nodes may occur within single computation tree T. or across different labeled nodes' computation trees. In the graph data valuation game, these potential duplicates are treated as distinct players, uniquely identified by their paths to the corresponding labeled node. We define the player set P as the set of all these distinct players across the compulation trees of all labeled nodes in Vi.
Definition 3 (Utility Function). Given subset S C P, we first generate a node-induced graph (S) using their corresponding edges in the computation trees. Then, a GNN model A is trained on the induced graph (S). Its performance is evaluated on a held-out validation set to serve as the utility of S, calculated as (S) ace( (c (S))), where acc measures the accuracy of the trained GNN model A(Gin(8)) on a held-out validation set.
The goal of the graph data valuation problem is to assign a value to all players in P with the help of the utility function U. When calculated properly, these values are supposed to provide detailed understanding of how players in P contribute to the GNN performance in a fine-graine ane-grained manner. Furthermore, these values can be flexibly combined to generate higher-level values for nodes and edges, which will be discussed in Section 3.5
3.2 PRECEDENCE PRECEDENCE-CONSTRAINDD WINTER VALUE
As discussed in Section 2.3 the final representations of a labeled node v; come from the hierarchical collaboration of all players in the computation tree T.K. These labeled nodes with the updated representations then contribute to the GNN performance through the training objective. Such contribution process forms a hierarchical collaboration between the players in P, which can be illustrated with contribution tree as shown in Figure 2a In particular, the contribution tree T is constructed by linking the root nodes of the computation trees of all labeled nodes with a dummy node representing the GNN training objective O. In Figure 2a] for the ease of illustration, we set K T==2 2, include only 2 labeled nodes, i.e, co, U1. and utilize wi, u; to denote the nodes in the lower level. The subtree rooted at a labeled node U E V is the corresponding computation tree T,2. With this, we observe the following about the coalition structure of the graph data valuation game.
Observation 2 (Level Coalition Structure). As shown in Figure 2a the players in P hierarchically collaborate to contribute. At the bottom level, the players are naturally grouped by their parents.
4

---

Published as a conference paper at ICLR 2025
Specifically, players with common parent such as ug. u1, U2 with their parent wo, establish foundation sub-coalition. This sub-coalition is clearly depicted in Figure Moving up the tree, these parent nodes, like Wn. serve as "delegates" for their respective sub-coalitions, further engaging in collaborations with other sub-coalitions. This interaction forms higher-level sub-coalitions, such as the one between wo, W1, W2, and Un in Figure 2b indicating inter-coalition cooperation. This ascending process of coalition formation continues until the root node O is reached, which represents the objective of the entire coalition consisting of all players. The depicted hierarchical collaboration process aligns with the Level Coalition Structure discussed in Section 2.7
While the contribution tree shares similarities with the Level Coalition Structure illustrated in Section 2.1 pivotal distinction lies in the representation and function of "delegates" (high- lighted in red in Figure 2b) within each coali- tion. the traditional Level Coalition Structure, contributions within a sub-coalition are made collectively, with each player or lower-level sub- coalition participating on equitable basis. In contrast, the contribution tree framework distin- guishes itself by designating "delegate" within each sub-coalition, player that represents and advances the collective contributions, establishing directed and tiered flow of influence, hence forming Unilateral Dependency Structure.
Contribution Tree
(b) Coalition Structure
Figure 2: Graph Data Valuation Game Structure
Observation 3 (Unilateral Dependency Structure). In the contribution tree framework, player p E P contributes to the final objective through a hierarchical pathway facilitated by its ancestors (its "delegates" at different levels). Therefore, the collaboration between players in P exhibits Unilateral Dependency Structure, where a player p's 's contribution is dependent on its ancestors.
According to these two observations, the players demonstrate unique coalition structures in the graph data valuation game. We aim to propose a permutation-based valuation framework similar to (I to address the cooperative game with both Level Coalition Structure and Unilateral Dependency Structure. In particular, instead of utilizing all the permutations as in (I. only the permissible permutations aligning with such coalition structures are included in the value calculations. As we
described in Section 2.1 cooperative games with Level Coalition Structure have been addressed by the Winter value (Winter) 1989; Chantreuil] 2001). Specifically, a permutation respecting the Level Coalition Structure must ensure that players in the same cooa-)ccalition, regardless of its level, are grouped together without interruption from other players (Winter 1989). In our scenario, any subtree of the contribution tree corresponds to ensure that for any player E P. the player p and its descendants in the contribution tree should be grouped together in the permutation. For example, the players Wo, un U1 U2 should present together as a group in the permutation with potentially different orders. On the other hand, to ensure the Unilateral Dependency Structure, a permutation must maintain partial order. Specifically, for any player p in the permutation, its descendants must present in later positions in the permutation than p. Otherwise, the descendants of cannot make non-trive con-trivial contributions, resulting in 0 marginal contributions.
sub-coalition as demonstrated in Figure Hence, we need
We formally define the permissible permutations that align with both Level Coalition Structure and Unilateral Dependency Structure utilizing the following two constraints.
Constraint (Level Constraint). For any player p P, the set of its descendants in the contribution tree is denoted as D(p). Then, a permutation π aligning with the Level Coalition Structure satisfies the following Level Constraint: [ T < [P(p),, Vi,j D(p) Up, Vp P, where ा T[i denotes the positional rank of the i in n.
Constraint 2 (Precedence Constraint). A permutation π aligning with the Unilateral Dependency Structure satisfies the following Precedence Constraint: -|p) < n πl0, vi e D(p), Vp E P.
We denote the set of permissible permutations satisfying both Level Constraint and Precedence Constraint Ω. Then, define the Trecedence-Coonstrained Constrained Winter (PC-Winter) value for
5

---

Published as a conference paper at ICLR 2025
player p E P with the permutations in Ω2 as follows.
(P
Σ
(U, Up) (P,)),
FER
where (T-) is the utility function (see Definition and Pj denotes the predecessor set of p in æ as defined in
3.3 PERMISSIBLE PERMUTATIONS FOR PC-WINTER
To calculate PC-Winter value, is required to obtain all permissible permutations. straightfor- ward way is to enumerate all permutations and only retain the permissible permutations. However, such an approach is extremely computationally intensive and typically not feasible in reality. In this section, address this challenge, propose novel method directly generate these permutations by traversing the contribution tree with Depth-First Search (DFS). Specifically, each DFS traversal results in a preordering. which a list of the nodes (players) in the order that they were visited by DFS. Such preordering naturally defines a permutation of P by simply removing the dummy node in the contribution tree from the preordering. By iterating all possible DFS traversals of the contribution tree, we can obtain all permutations in Ω2 which is demonstrated in the following theorems.
Theorem 1 (Specificity). Given contribution tree T with a set of players P. any DFS traversal over the T results permissible permutation of P that satisfies both the Level Constraint and Precedence Constraint.
Theorem (Exhaustiveness), Given a contribution tree T with a set of players P, any permissible permutation π E Q can be generated by corresponding DFS traversal of
The proofs for two theorems be found in Appendix C Theorem T demonstrates that DFS traversals specifically generate permissible permutations. On the other hand, Theorem ensures the exhaustiveness of generation, which allows to obtain all permutations in Ω by DFS traversal. Together, these two theorems ensure to exactly generate the set of permissible permutations Ω.
Notably, the calculation of PC-Winter value involves two steps: 1) generating Ω with DFS traversals; and 2) calculating the PC- Ciniieeer value according to (3). Nonetheless, it can be done in a streaming way while we perform the DFS traversals. Specifically, once we reach player p in a DFS traversal, we can immediately calculate its marginal contribution. The PC-Winted values for all players are computed by averaging their marginal contributions from all possible DFS traversals.
3.4 EFFICIENT APPROXIMATION OF PC-WINTER
Calculating the PC-Winter value for players in is infeasible due to computational intensity, arising from: 1) The exponential growth in the number of permissible permutations with more players, rendering exhaustive enumeration intractable; 2) The necessity to re-train the GNN within the utility function for each permutation, process repeated [P] times to account for every player's marginal contribution; and 3) The intensive computation involved in GNN re-training, requiring feature aggregation over the graph that increases in complexity with the graph 's size. These challenges necessitate an efficient approximation method for PC PC-Winter valuation in practical applications. We propose three strategies to address these computational issues.
3.4.1 PERMUTATION SAMPLING
Following Data Shapley (Ghorbani & Zou 2019 we adopt Monte Carlo (MC) sampling randomly sample a subset of permissible permutations denoted as Ω This sampling approach maintains the structural properties of permutations while significantly reducing computational overhead. Then, utilize Q2 to replace Ω in (3) for approximating PC- PC-Winter value.
3.4.2 HIERARCHICAL TRUNCATION
While permutation sampling reduces the number of evaluations, the computational cost for each evaluation remains substantial. GNN models often demonstrate phenomenon of neighborhood saturation, i.c, these models achieve satisfactory performance even when trained on a subgraph using only small subset of neighbors, rather than the full neighborhood (Hamilton et al. 2017

---

Published as a conference paper at ICLR 2025
Liu et al. 2021 Ying et al. 2018 Chen al. 2017), indicating diminishing returns from additional neighbors beyond a certain point. This indicates that for a player p in a permissible permutation ' generated by DFS over the contribution tree, the marginal contributions of its late visited child players are insignificant. Thus, we propose hierarchical truncation for efficiently obtaining the marginal contributions by directly approximating insignificant values O.
Specifically, during the DFS traversal, given a truncation ratio r, we only compute actual marginal contributions for players in the first 1 portion of each node's child subtrees, approximating the marginal contributions of players in the remaining subtrees as O. For example, in Figure 2a given a truncation ratio 2/3, when DFS reaches player Vo. we only calculate marginal contributions for players in the subtree rooted at Wi. Furthermore. in the subtree rooted at wo, due to the hierarchical truncation, only the marginal contribution of un is evaluated, those for node un and u2 are set to O.
This approach is further optimized by adjusting truncation ratios based on the tree level, accommodat- ing varying contribution patterns across levels. particular, we organize the pair of truncation ratio as 71-12, indicating we truncate 7ı (or 72) portion of subtrees (or child players) of (or w:). We show how the hierarchical truncation helps tremendously reduce the model re-training in Appendix
3.4.3 LOCAL PROPAGATION
To enhance scalability, we leverage SGC (Wu et al. 2019) in our utility function, which simplifies GNNs by aggregating node features before applying an ML.P According to the Level Constraint (Constraint the players within the same computation Therefore, the induced graph of any coalition P defined by permissible permutation consists of set of separated computation trees (or partial computation tree corresponding the last visited labeled node in P.).
are grouped together in the permutation.
key observation that the feature aggregation process for the labeled nodes can be done indepen- dently within their own computation trees. Hence, instead of performing the feature propagation for the entire induced graph. we propose perform local propagation only on necessary computation trees. In particular, the aggregated representation for labeled node is fixed after we traverse its entire computation tree in DFS. Therefore, for evaluating a player p's marginal contribution, only the partial computation tree of the last visited labeled node requires local propagation, minimizing feature propagation efforts.
To summarize, the PC-Winter values for all players are efficiently approximated using combina- tion of three strategies in a streaming manner. particular, we randomly traverse the contribution tree with DFS for [2,] times. During each DFS traversal, the marginal contributions for all players in P are efficiently obtained with the help of hierarchical truncation and local propagation. The marginal contributions calculated through these [2, DFS traversals averaged to approximate the PC-Winter value for all players. In Appendix L.3 we provide a detailed complexity analysis of the PC- PC-Winter algorithm. More details of the PC Winter framework, including its visual overview of its approximation procedure, are presented in Appendix M
3.5 FROM PC-WTNTER TO NODE AND EDGE VALUES
The PC- SC-Winter values for players in P can be flexibly combined obtain the values for elements in the original graph. This section illustrates how to derive both node-level and edge-level valuations from our player-centric framework.
As discussed in Section 3.1 multiple "duplicates" of a node E V in the original graph may potentially present P. To capture node's overall contribution, we define the node value for node by summing the So-Winter values of all its "duplicates" in P. This aggregation naturally combines the different roles a node plays in contributing to model performance.
From a structural perspective, each player (except for the rooted labeled players) in P corresponds to an "edge" in the contribution tree, identified by the player and its parent. For instance, in Figure the player uo corresponds to the "edge" connecting un and wp. Through this lens, DFS traversals generate permutations not just for players, but implicitly for these "edges" as well. The marginal contribution calculated for player p through DFS traversal can thus be interpreted the marginal contribution of its corresponding edge, viewing the process as gradually adding "edges" to connect the players in P.
7

---

Published as a conference paper at ICLR 2025
Similar nodes, edge E E in the original graph may have multiple "duplicates" in the contribution tree, each representing a different pathway of influence. Therefore, we define the edge value for e E & by taking the summation of the FC-Winter value for all its "duplicates" in the contribution tree. This aggregation captures the total impact of each edge in facilitating information flow across the graph.
EXPERIMENT
Datasets and Settings. We assess the proposed approach on six real-world benchmark datasets: Cora, Citeseer, and Pubmed (en al. (2008), Amazon- Photo, Amazon- Computer, and Coauther-Physse Shehur et al. (2018). The detailed statistics of datasets are summarized in Table 2 Appendix G Our experiments focus the inductive node classification task. The detailed setup of the inductive setting can be found in Appendix G. To obtain the PC-Wi winter values, we run permutations in a streaming way described in Section 3.4 This process terminates with convergence criterion as detailed in Appendix G.4 PC-Winted er typically terminates with a different number of permutations for different datasets. The other hyper-parameteen are detailed in Appendix G.5
4.1 DROPPING HIGH- VALUE NODES
In this section, we aim evaluate the quality of data values produced by PC-Winter via dropping high-value nodes from the graph. Dropping high-value nodes is expected to significantly diminish performance, and thus the performance observed after removing high-value nodes serves as a strong indicator of the efficacy of graph data valuation. Notably, PC-Winter values values are calculated as described in Section 3.5
To demonstrate the effectiveness of PC-Winter, we include Random value, Degree value, Leave-one-out (LOO) value,
Digree
Recurrayy 1%0 Prediction Arcuner (80)
Citeseer
and Data Shapley value as baselines. A
a 850
more detailed description of these baselines
is included in Appendix [.66] To conduct
0.65
0. 625-
node-dropping experiments, nodes by their assessed values for each method and removed sequentially from the training graph Gr. After each removal, we train a GNN model based on the remaining graph and evaluate its performance on the testing graph Gte- Performance changes are depicted through
ranked
300 Number Node Removed
200
200
200
300
400
Number of Node Removed
Prediction Accurazy
0.75
Pubmed
Amazon-Photo
0.70
0.65-
0.8-
1000
2000
1000
2000
3000
4000
curve that tracks the model's accuracy nodes are progressively eliminated. Labeled nodes often contribute more significantly to model performance than unlabeled nodes because they directly offer supervision. Thereby, with accurately assigned node values, labeled nodes should be prioritized for removal over unlabeled nodes. We empirically validate this hypothesis in Figure 6 discussed in Appendix Specifically, in nearly all datasets, our observations reveal that the majority of labeled nodes are removed prior the unlabeled nodes by both PC-Wints nter and Data Shapley. This leads to a plateau in the latter portion of the performance curves since a GNN model cannot be effectively trained with only unlabeled nodes. Consequently, this scenario significantly hampers the ability assess the value of unlabeled nodes. Therefore, we propose to conduct separate assessments for the values of labeled and unlabeled nodes. Here, only inleude the results for unlabeled nodes, while the results for labeled nodes presented in Appendix FF]
Number Node Removed
Number of Node Removed
Arazzen-Compulles
Coauther-itysirs
Predicton Accurey
0.7
0.92
0.6-
0.90
0.5
0.88
2000
4000
6000
4000 Number of Node Removed
2000
Number Node Removed
Figure 3: Dropping High-Value Value Nodes
Results and Analysis. Figure illustrates the performance comparison between PC-Winter and other baselines across various datasets. From Figure B, we make the following observations. First, the removal of high-value unlabeled nodes identified by PC-Winted consistently results
8

---

Published as a conference paper at ICLR 2025
in the most significant decline in model performance across various datasets. This is particularly evident after removing a relatively small fraction (10%-20%) of the highest-value nodes. This trend underscores the importance of high-value nodes. Notably, in most datasets PC-Winter outperforms the best baseline method, Data Shapley, by a considerable margin, highlighting its effectiveness. Second, the decrease in performance caused by our method is not only substantial but also persistent throughout the node-dropping process, further validating the effectiveness of PC-Winter. Third, the performance curves of PC-Winter and Data Shapler eventually rebound towards the end. This rebound corresponds to the removal of unlabeled nodes that make negative contributions. Their removal aids in improving performance, ultimately reaching the MLP performance when all nodes are excluded. This upswing not only evidences the discernment of PC-Winter and Data Shapley ey in ascertaining node values but also showcases the particularly acute precision of PC-Winter: These insights collectively affirm the capability of PC-W w nteer in accurately assessing node values. For a detailed quantitative analysis of these results, including minimum and mean accuracies across all datasets, please refer to Tables 4 and S in Appendix H Furthermore, we extend our evaluation to regression tasks and class-balancee accuracy metrics in Appendices and K respectively, demonstrating the effectiveness of PC-Wi nt across different learning scenarios.
4.2 ADDING HIGH- VALUE EDGES
In this section, we explore the impact of adding high-value elements a graph, providing an alternative perspective to validate the effectiveness of data valuation. Notably, adding high-value nodes to graph typically involves the concurrent addition of edges, which complicates the addition process. Thus, we target the addition of high-value edges, providing a complementary perspective to our analysis. As described in Section 3.5 the flexibility of PC-Winter allows for obtaining edge values without a separate "reevaluation" process for edges.
Here, we keep all nodes in Gir and sequen- tially add edges according to the edge values in descending order, starting with the highest- valued ones. Similar to the node-dropping ex-
Prediction Aecuraryy (Ka Preditiinn Recuuacy (8a Prodictign moalicton Acqurzzy (56
Core
Citeseer
periments, the effectiveness of the edge addi-
8.725
0.675
tion is shown through performance curves. We
0.700
0.656
include Random value, Edge-Betweenee Leave-one-our (LOO) as baselines. Notably, here, Random and LOO specifically pertain to edges, and while we use the same terminology as in the prior section, they are distinct methods, which are detailed in Appendix G.6
8,675
0.600
200
400
230
600
600
Pubmed
0,776
0.8
0.2
Results and Analysis. Figure 4 illustrates that the Random, LCO, and Edge Bdge-Betweenee baselines achieve only linear performance im- provements with the addition of more edges, failing to discern the most impactful ones for sparse yet informative graph. In contrast, the
3000 Amarer Computers
1.00
2000
10000 20000 10080
Coauthon-PPyysiis
3.80
8.75
0.70
40000 60000 Number Edge Added
20000
2000 4000 6000 2000 Number Edg
inclusion of edges based on the PC-Wints Winntee value results in a steep performance climb, af-
firming the PC-Wint ex's 's efficacy in pinpoint- ing key edges. Notably, the Cora dataset reaches full-graph performance using merely 8% of the edges selected by PC- Winter. Moreover, with just 10% of PC- -i--ee-steeeeeeeed edges, the accuracy climbs to 72.9%, outperforming the full graph's 's 71.3%, underscoring PC-Winter's capability to identify valuable edges. This trend is generally consistent across other datasets as well. A comprehensive quantitative analysis of the edge addition results, including maximum and mean accuracies for all methods and datasets, can be found in Tables and 7 Appendix
Figure 4: Adding the High-Value Value Edges

---

Published as a conference paper at ICLR 2025
4.3 ABLATION STUDY, PARAMETER AND EFFICIENCY ANALYSIS
In this section, we conduct an ablation study, parameter analysis, and efficiency analysis to gain deeper insights into PC-Winter using node-dropping experiments.
Ablation Study. We conduct an ablation study to understand how the two constraints in Section 3.2 affect the effectiveness of PC-Winter. We introduce two variants of PC-Winter by lifting one of the constraints for the permutations. In particular, we define PC- "C-Winter-LL using the permutations satisfying the Level Constraint. Similarly, PC-Winter-P is defined with permutations only satisfying Precedence Constraint. As shown in Figure [ PC-Winter value outperforms the PC-Winter and PC PC- Winter-P on both datasets, which demonstrates that both constraints are crucial for PC-Winter. Additional results on other datasets are provided in Appendix L.1
Parameter Analysis. We conduct parame- ter analyses to investigate the impact of per- mutation number and truncation ratios on PC-Winter's performance. The results reveal that PC-Wintez achieves robust performance with significantly reduced number of per-
PC-Witerd
PC-Witer+
PCAWetee
Cora
Amazon Amazon-Phato
Prediction Accuracy
6.70
0.85-
0.7
0.6
mutations and high truncation ratios. Detailed findings are presented in Appendix 1.2 and Ap- pendix 1.3 respectively.
0.80.
100
200
300
1000
2000
3000
4000
Number of Node Removed
Number of Node Removed
Figure 5: Ahlation Study
Efficiency Analysis. We compare the efficiency of PC-Winter and Data Shapley. Anal- ysis of converged permutation count and time per permutation across datasets underscores PC-Winter's significantly higher efficiency. A comprehensive breakdown is available in Ap-
pendix 1.4
CONCLUSION
In this paper, we introduce PC-Winter, an innovative approach for effective graph data valuation. The method is specifically designed for graph graph-structured data and addresses the challenges posed by unlabeled elements and complex node dependencies within graphs. Furthermore, we introduce a set of strategies for reducing the computational cost, enabling efficient approximation of PC-Wi nter. Ex- tensive experiments demonstrate the practicality and effectiveness of PCPP-W Winter in various datasets and tasks. While PC-Winter demonstrates improved efficiency compared to Data Shapley, we eeknowledge that further efficiency enhancements are crucial to fully unlock the potential of graph data valuation in real-world applications. Our work can be seen as foundation for future research in this direction.
ACKNOWLEDGMENTS
We thank Prof. Lirong Xia from Rutgers University for his valuable discussions and insights that helped improve this work. The research is supported by the National Science Foundation (NSF) under grant numbers NSF2406647 and NSF-2406648.
REFERENCES
Selahattin Akkas and Ariful Azad. Gnnshap: Scalable and accurate gnn explanation using shapley values. In Proceedings of the ACM on Web Conference 2024, pp. 827-838, 2024.
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V Chawla. Graph barlow twins: A self-supervised representation learning framework for graphs. Knowledge-Baut Based Systems, 256:10 2022.
Rodica Branzei, Dinko Dimitrov, and Stef Tijs. Models in cooperative game theory, volume 556. Springer Science Business Media, 2008
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint ar 2013.
10

---

Published as a conference paper at ICLR 2025
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint arXiv: I 700.05085, 2017.
Frédéric Chantreuil. Axiomatics of level structure values, Power Indices and Coalition Formation, pp. 45-62, 2001.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710110566, 2017.
Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. arXiv preprint arXlv:2210.07441, 2022.
Hongliang Chi and Yao Ma. Enhancing contrastive learning on graphs with node similarity. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 456-465, 2024.
Hongliang Chi, Cong Qi, Suhang Wang, and Yao Ma. Active learning for graphs with noisy structures. In Proceedings of the 2024 SIAM International Conference on Data Mining (SDM), pp. 262-270. SIAM, 2024.
Imma Curiel. Cooperative game theory and applications: cooperative games arising from combina- torial optimization problems, volume 16. Springer Science Business Media, 2013.
Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM web conference 2022, pp. 2259-1269)
2022a.
Yushun Dong, Song Wang, Yu Wang, Tyler Demr, and Jundong Li. On structural explanation of bias in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 316-326. 2022b.
Yushun Dong, Song Wang, Jing Ma, Ninghao Liu, and Jundong Li. Interpreting unfairness in graph neural networks via training node attribution. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp. 7441- 7441-7449, 2023.
Alexandre Duval and Fragkiskos Malliaros. Graphsvx: Shapley value explanations for graph neural networks. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part II 21, pp. 302-318. Springer, 2021.
Edoardo D' Amico, Khalil Muhammad, Elias Tragos, Barry Smyth, Neil Hurley, and Aonghus Lawlor. Item graph convolution collaborative filtering for inductive recommendations. In European Conference on Information Retrieval, pp. 249-263, Springer, 2023.
Wenqi Fan, Yao Ma, Dawei Yin, Jianping Wang, Jiliang Tang, and Qing Li. Deep social collaborative filtering. In Proceedings of the 13th ACM RecSys, 2019.
Christopher Frye, Damien de Mijolla, Tom Begley, Laurence Cowton, Megan Stanley, and Ilya Feige. Shapley explainability on the data manifold. arXiv preprint arXiv:2006.01222 2020.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint
2018.
Amirata Ghorbani and James Zou. Data shapley: Equitable valuation of data for machine learning. In International conference on machine learning, pp. 2242-2251, PMLR, 2019.
Shengbo Gong, Mohammad Hashemi, Juntong Ni, Carl Yang, and Wei Jin. Scalable graph condensa- tion with evolving capabilities. arXiv preprint arXiv:2502. 2025.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Shengding Hu, Zheng Xiong, Meng Qu, Xingdi Yuan, Mare- Alex-nle Côté, Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. Advances in Neural Information Processing Systems, 33:10174-101855 2020.
11

---

Published as a conference paper at ICLR 2025
Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2022.
Theis E Jendal, Matteo Lissandrini, Peter Dolog, and Katja Hose. Simple and powerful architecture for inductive recommendation using knowledge graph convolutions. arXiv preprint arXiv:2209.04185. 2022.
Junteng Jia and Austion Benson. Residual correlation in graph neural network regression. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 588-598, 2020.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. arXiv preprint arXiv: 1908.08619 2019.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 66-74, 2020.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation 2021.
for graph neural networks. arXiv preprint
Hoang Anh Just, Feiyang Kang, Jiachen T Wang. Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. Lava: Data valuation without pre-specified learning algorithms. arXiv preprint 000044 2023.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02000 2016.
Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation framework for machine learning. arXiv preprint arXiv:21 10. /4049, 2021.
Yongchan Kwon and James Zou. Data-oob: Out-of-bag estimate as a simple and efficient data value. arXiv preprint arXiv:2304.0777 2023.
Pengyong Li, Jun Wang, Yixuan Qiao, Hao Chen, Yihuan Yu, Xiaojun Yao, Peng Gao, Guotong Xie, and Sen Song. effective self-supervised framework for learning expressive molecular global representations to drug discovery. Briefings in Bioinformatics.
Xin Liu, Mingyu Yan, Lei Deng. Guoqi Li, Xiaochun Ye, and Dongrui Fan. Sampling methods for efficient training of graph convolutional networks: A survey. JEEE/CAA Journal of Automatica Sinica, 9(2):005-234, 2021.
Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, and Shirui Pan. Towards unsupervised deep graph structure learning. Proceedings of the ACM Web Conference 2022, pp. 1392-1403, 2022a.
Zelei Liu, Yuanyuan Chen, Han Yu, Yang Liu, and Lizhen Cui. Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning, ACM Transactions Intelligent Systems and Technology (TIST), 13(4):1-21, 2022b.
Qian Ma, Hongliang Chi, Hengrui Zhang, Kay Liu, Zhiwei Zhang, Lu Cheng, Suhang Wang, Philip S Yu, and Yao Ma. Overcoming pittalls in graph contrastive learning evaluation: Toward comprehensive benchmarks. arXiv preprint 24X. 2024.
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM international conference on information & knowledge management, pp. 1202-1211, 2021.
Andrea Mastropietro, Giuseppe Pasculli, Christian Feldmann, Raquel Rodríguez-Pére Pérez, and Jürgen Bajorath. Edgeshaper: Bond-centric shapley value- explanation method for graph neural networks. Iscience, 25()0), 2022.
12

---

Published as a conference paper at ICLR 2025
Dusit Niyato, Athanasios V Vasilakos, and Zhu Kun. Resource and revenue sharing with coalition formation of cloud providers: Game theoretic approach. In 2011 11th IEEE/ACM International Symposium Cluster, Cloud and Grid Computing, pp. 215 -244. IEEE, 2011.
Ki Nohyun, Hoyong Choi, and Hye Won Chung. Data valuation without training of model. In The Eleventh International Conference on Learning Representations, 2022.
Jian Pei. A survey on data pricing: from economics to data science. IEEE Transactions on knowledge and Data Engineering. 34(10):4586-4608 2020.
Stephanie Schoch, Haifeng Xu, and Yangfeng Ji. Cs-shapley: Class-wise shapley values for data
valuation in classification. Advances in Neural Information Processing Systems, 35:34574-34585,
2022.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93- 93, 2008
Behrooz Shahsavari and Pieter Abbeel. Short-term traffic forecasting: Modeling and learning spatio- temporal relations in transportation networks using graph neural networks. University of California at Berkeley, Technical Report No. UCB/EECS-201S-222 2015.
Lloyd S Shapley et al. A value for n-person games. 1953.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 181 I. 1005668, 2018
Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine "ingeedintn" strategies, and open challenges. In Proc. IJCAI, pp. 5607-5614, 2022.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. In ICLR 2021 workshop on geometrical and topological representation learning, 2021.
Rafaël Van Belle, Charles Van Damme, Hendrik Tytgat, and Jochen De Weerdt. Inductive graph representation learning for fraud detection. Expert Systems with Applications, 193: 16463, 2022.
Vítor V Vasconcelos, Phillip M Hannam, Simon A Levin, and Jorge M Pacheco. Coalition-struccuuee governance improves cooperation to provide public goods. Scientific reports, 10(1):9194, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10900,, 2017.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (poster), 2(3):4, 2019.
John Von Neumann and Oskar Morgenstern. Theory of games and economic behavior (60th Anniver- sary Commemorative Edition). Princeton university press, 2007.
Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pp. 6388 6421. PMLR, 2023.
Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr. Improving fairness graph neural networks via mitigating sensitive attribute leakage. In Proceedings of the 28th ACM SIGKDD conference knowledge discovery and data mining, pp. 1938-1948, 2022.
Yu Wang, Kaize Ding, Xiaorui Liu, Jian Kang, Ryan Rossi, and Tyler Derr. Data quality-aware graph machine learning. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pp. 5534 5537, 2024.
Eyal Winter. A value for cooperative games with levels structure of cooperation. International Journal of Game Theory, 18:227-240, 1989.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty. Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICML. PMLR, 2019.
13

---

Published as a conference paper at ICLR 2025
Haocheng Xia, Jinfei Liu, Jian Lou, Zhan Qin, Kui Ren, Yang Cao, and Li Xiong. Equitable data valuation meets the right to be forgotten in model markets. Proceedings of the VLDB Endowment, 16(11):3349-3362, 2023.
Haocheng Xia, Xiang Li, Junyuan Pang, Jinfei Liu, Kui Ren, and Li Xiong. P-shapley: Shapley values on probabilistic classifiers. Proceedings of the VLDB Endowment, 17(7):1337-7500, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018.
Tom Yan and Ariel D Procaccia. If you like shapley then you'll love the core. In Proceedings the AAAI Conference on Artificial Intelligence, volume 35, pp. 5751-5759, 2021.
Ziyuan Ye, Rihan Huang, Qilin Wu, and Quanying Liu. Same: Uncovering gnn black box with structure-ans aware shapley- based multipiece explanations. Advances in Neural Information Processing Systems, 36, 2024.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 974 983, 2018.
Jinsung Yoon, Sercan Arik, and Tomas Pfister. Data valuation using reinforcement learning. In International Conference Machine Learning, pp. 10842-10851. PMLR, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On cxplainability of graph neural networks via subgraph explorations. In International conference on machine learning, pp. 12241- 12252. PMLR, 2021.
Pu Yuan, Yong Xiao, Guoan Bi, and Liren Zhang. Toward cooperation by carrier aggregation in heterogeneous networks: A hicrarchical game approach. IEEE Transactions on Vehicular Technology, 66(2):1670-1685) 2016.
Liangliang Zhang, Haoran Bao, and Yao Ma. Extending graph condensation to multi-labe datasets: A benchmark study. arXiv preprint arXiv:2412.17961 2024.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mips new tricks via distillation. arXiv preprint arXiv:2110.08727, 2021a.
Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang. and Bin Cui. Alg: Fast and accurate active learning framework for graph convolutional networks. In Proceedings of the 2021 international conference on management of data, pp. 2366-2374, 2021b.
Wentao Zhang, Zhi Yang, Yexin Wang. Yu Shen, Yang Li, Liang Wang, and Bin Cui. Grain: Improving data efficiency of graph neural networks via diversified influence maximization. arXiv preprint arXiv:2 008.002// 19, 2021c.
Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Spectral feature augmentation for graph contrastive learning and beyond. In Proceedings of the AAAI conference artificial intelligence, volume 37, pp. 1129--1229, 2023.
Xin Zheng, Yixin Liu, Zhifeng Bao, Meng Fang, Xia Hu, Alan Wee-Chung Liew, and Shirui Pan. To- wards data-centric graph machine learning: Review and outlook. arXiv preprint 1XXx:2339.11079 2023.
Lina Zhou, Shimei Pan, Jianwu Wang, and Athanasios Vasilakos. Machine learning on big data: Opportunities and challenges. Nearocompuring, 237:350-333 361, 2017.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint 200i 13, 2020.
Yaochen Zhu, Jing Ma, Liang Wu, Qi Guo, Liangjie Hong, and Jundong Li. Path-specific counterfac- tual fairness for recommender systems. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3638-3649, 2023.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORK
This section presents extended review of related works, offering broader and more nuanced exploration of the literature surrounding Data Valuation and Graph Neural Networks.
A.1 DATA VALUATION
Data Shapley is proposed in (Ghorbani & Zou 2019) which computes data values with Shapley values in cooperative game theory. Beta Shapley (won & Zou| 2021) is further generalization of Data Shapley by relaxing the efficiency axiom of the Shapley value. Data Banzhaf (Wang & Jia (023)
offers data valuation method which is robust to data noises. Data Valuation with Reinforcement Learning is also explored by (Yoon et al. 2020). KNN- ENN-Shapley (Jia et al. (219)) estimates the shapley Value for the K-Nearest Neighbours algorithm in linear time. CS-Shapley (Schoch al.) (002))
provides a new valuation method that differentiate in-class contribution and out-class contribution. Data-OOB (Kwon & Zou| 2023) proposes a data valuation method for bagging model which leverages the out-of-bag estimate. Just, Hoang Anh, et al (Just et al. (2023) introduce learning- agnostic data valuation framework by approximating the utility of dataset according to its class-wise Wasserstein distance. Another training-free free data valuation method utilizing the complexity -app score proposed at the same time (Nohyun et al., 2022).
However, these methods are primarily designed for traditional i.i.d. data, assuming independence and identical distribution among data points, and are not specifically designed to evaluate graph data. The latter presents higher complexity due to the interconnections and dependencies among individual nodes. P-Shapley (Xia et al., 2024) extends Shapley values by leveraging probabilistic classifier outputs, proposing alternative utility function that replaces standard accuracy metrics. While this innovation improves valuation accuracy for traditional i.i.d. data, it remains orthogonal to the structural challenges in graph data valuation.
A.2 GRAPH NEURAL NETWORKS
Graph Neural Networks (GNNs) generate informative representations from graph-structured data and facilitate the solving of many graph-related tasks. Bruna al. (Bruna et al. 2013) first apply the spectral convolution operation to graph-structuret data. From the spatial perspective. the spectral convolution can be interpreted to combine the information from its neighbors. GCN (Kipf & Welling 2016) simplified this spectral convolution and proposed many other attention- based, sampling-bast baased and simplified GNN variants which follow the same neighborhood aggregation design have been proposed (Veličković al., 2017 Hamilton et al., 2017]] Gasteiger et al.] 2018 Wu et al., 2019). Theoretically, those Graph neural networks typically enhance node representations and model expressiveness through meessage-passing mechanism, efficiently integrating graph data into the learning of representations (Xu et al. 2018
first-order approximation. Since then,
A.3 SHAPLEY VALUE IN GRAPH MACHINE LEARNING
The Shapley value has found several applications in graph machine learning, primarily in the domain of explainability for Graph Neural Networks. GraphSVX (Duval & Malliaros 202T) is one of the early works that utilizes the Shapley value to explain the predictions of GNNs. It identifies influential nodes and features for a particular prediction by treating them as players in a cooperative game. However, GraphSVX focuses on local explanations for individual predictions of a fixed GNN, SubgraphX (Yuan et al. 2021) takes a different approach by explaining GNN predictions through identifying important subgraphs, rather than individual nodes or edges. It uses Monte Carlo tree search to efficiently explore different subgraphs and proposes to use Shapley values as a measure of subgraph importance. EdgeSHAPer (Mastropietro et al.) (022) is another method that assesses edge importance for GNN predictions using the Shapley value concept. It is particularly relevant for molecular graphs where edges represent chemical bonds. GNNShap (Akkas & Azad 2024) extends upon previous Shapley value based GNN explanation methods by providing explanations for edge, leading to better fidelity scores and faster explanations. SAME (Ye et al.) (2024) proposes structure-awee aware Shapley-base multipiece explanation method for GNNs that can identify important substructures and provide explanations composed of multiple connected components.
15

---

Published as a conference paper at ICLR 2025
In addition to explainability, Shapley has also been widely adopted for data valuation for conventional
machine learning methods as discussed in Section 2 However, it has rarely been utilized for data valuation on graph data. In this work, pioneer the exploration of graph data valuation, challenging and previously unexplored problem. Although a recent survey (Zheng et al. 2023) inadvertently refers to GraphSVX as a graph data valuation method, it does not align with the traditional definition
of data valuation. We clarify the key differences between graph data valuation (such as our method) and graph explainability (such GraphSVX) as follows.
1. In general, data valuation (such as our method) aims to understand how graph elements contribute to the model training process, while explainability methods (such as GraphSVX) provide post-hoc explanations for a fixed, pre-trained model.
2. Specifically, our method differs from GraphSVX in several aspects:
(a) GraphSVX focuses on the explainablity of a local prediction for a single sample, while our method aims to quantify the global contribution of graph elements to the overall model performance.
(b) GraphSVX operates post hoc, analyzing the contributions of features and nodes in the testing graph to the predictions of an already- GNN model, while our approach focuses on the global contribution of each data element in the training graph to the
GNN model's training process.
(c) GraphSVX employs the standard Shapley value formulation, which assumes free collaboration among players, while our work introduces the PC-Winter value to handle the unique hicrarchical coalition structures inherent in graph data valuation.
To the best of our knowledge, our investigation constitutes the first foray into graph data valuation, pioneering research in this previously uncharted domain.
A.4 DATA-CENTRIC LEARNING ON GRAPHS
Data-centric graph learning encompasses various approaches, with data valuation and data-efficient learning sharing similar motivations but distinct methodologies. Data-efficient learning on graphs primarily addresses the challenge of limited labeled data through two main paradigms. Graph self- supervised learning develops rich representations without relying on extensive labels. Within this approach, contrastive methods like Deep Graph Infomax (Velickovic et al., 2019) and GRACE (Zhu) eet al. 2020) learn by discriminating between different views of the same graph, while more recent non-contrastive techniques including BGRL (Thakoor et al. 2021) and Graph Barlow Twins (Bielak et al. (022) achieve competitive performance without requiring negative samples. Contemporary research has focused on developing sophisticated feature augmentation strategies Zhang et al. (2023). Chi & Ma (2024) propose enhancing contrastive learning through node similarity metrics, while Ma et al. (2024) establish comprehensive evaluation frameworks. The alternative paradigm, graph active learning, optimizes the selection of nodes for labeling to maximize model performance with minimal annotation effort. Representative approaches include AGE (Cai et al.) (017). which combines multiple selection criteria, GPA (Hu et al. 2020), which reformulates selection as sequential decision- making, and GRAIN (Zhang et al. 2021c which treat selection as influence maximization problems. More sophisticated techniques have emerged, such as ALG (Zhang et al. both representativeness and informativeness, and GALclean (Chi et al. 2024h, which addresses active learning challenges in graphs with structural noise. In addition to these data-efficient learning strategies, another key aspect of data-centric graph learning lies in understanding and mitigating biases in GNNs. Fairness-focused studies investigate how GNNs may exhibit biased predictions towards certain demographic subgroups resulted from certain input graph components. For example, recent works have explored to attribute the unfairness exhibited by GNNs to input graph components, such as specific training nodes (Dong al., (202)) edges (Zhu al. 2023 Dong al.) [202a)), and subgraphs (Dong et al.) 2022b: Wang et al. 2022). Beyond these approaches, data-centric graph learning also encompasses other important branches such as graph structure learning (Jin et al. 2020 Ma et al., 2021 Liu et al., (222a), which focuses on jointly learning optimal graph structures and node representations; graph condensation (Jin et al. 2021 Zhang et al. 2024 Gong et al.. 2025), which aims to distill large-scale graphs into smaller yet information-presstt
2021b). which balances
counterparts for efficient training; and data quality- aware learning (Wang et al., 2024). which develops techniques to identify and mitigate the effects of noisy corrupted graph data model performance. In contrast to these approaches that focus on either maximizing performance with limited data or addressing faimess concerns, our work graph data valuation addresses the fundamental challenge
16

---

Published as a conference paper at ICLR 2025
of quantifying the contributions of graph data elements model performance through novel cooperative game-theoretic framework.
B
MATHEMATICAL FORMULATION OF WINTER VALUE
The Shapley value offers a solution for equitable payoff distribution in cooperative games, assuming that players cooperate without any predefined structure. In reality, however, cooperative games often have inherent hierarchical coalitions. To accommodate these structured coalitions, the Winter value (Winter 1989) extends Shapley value to handle this extra coalition constraints.
Specifically, considering level structures B, with B Bu...., B, representing a sequence of player partitions. Here, partition, Bm, subdivides the player set P into of disjoint, non-empty subsets Ti, Ti,T.,... Tи. These disjoint subsets satisfy the condition that their union reconstructs the original player set P. which means Ti U UT2 J... UT, P. This partition sequence forms hierarchy where Bo represents individual players as the leaves of the structure and B, functions as the root of this hierarchy.
We then determine (2))), the set of all permissible permutations, starting with single partition Bm: () = {Tr E (I(P): VT E Bm, Vi, and & E P, if (1) < π (lk) +()) then & E T).
!(B) can be further defined as the set of permutations which satisfy all constraints of all levels, (( = N== Q (B.).
A permissible permutation x from the set 22(33 requires that players from any derived coalition of B must appear consecutively. Given the defined of permissible permutations Q(B)). the Winter value & for player is calculated as:
$ (P,UU,
1
Σ
(U, U UP?))
[BB
TEA(S)
where P. [j N +() x()) is the set of predecessors of the permutation a and the utility function in the cooperative game.
C PROOFS OF THEOREMS
Theorem (Specificity). Given contribution tree T with a set of players P. any DFS traversal over the T results permissible permutation of that satisfies both the Level Constraint and Precedence Constraint.
Proof. We validate the theorem by demonstrating that a permutation obtained through pre-order traversal on T meets Level Constraints and Precedence Constraints. (1) Level Constraints: During pre-order traversal of T, a node and its descendants D(p) are visited sequentially before moving another subtree. Thus, in the resulting permutation π, the positions of p and any i, D(p) are inherently close to each other, satisfying the condition [-]]] π < [D(p)] This contiguous traversal ensures that all descendants and the node itself form a continuous sequence in n, meeting the Level Constraint. (2) Precedence Constraints: In the same traversal, each node is visited before its descendants. Therefore,
π, the position of p always precedes the positions of its descendants, i.e. T [p] < x xii for all E Dpp). This traversal pattern naturally embeds the hierarchy of the tree into the permutation, ensuring that ancestors are positioned before their descendants, line with the Precedence Constraint.
Theorem 2 (Exhaustiveness), Given contribution tree T with set of players P, any permissible permutation æ E Ω can be generated by corresponding DFS traversal T.
Proof. To prove the theorem of exhaustiveness, consider contribution tree T with set of players P and any permissible permutation π E Q. We apply induction on the depth of T. For the base case, when T has depth of 1, which means there no dependencies among players, any permissible
17

---

Published as a conference paper at ICLR 2025
permutation of players is trivially generated by DFS traversal since there are constraints on the order of traversal. For the inductive step, assume the theorem holds for contribution trees of depth k. For contribution tree of depth k + 1 Tk+1, consider its root node and subtrees of depth lc rooted at the child nodes of the root node. For any given permissible permutation и corresponding to the Tk+11 according the Level Constraint, it is direct composition of the permissible permutations corresponding to the subtrees of depth & rooted at the child nodes of the root node. Now we can construct DFS traversal over the contribution tree T that can generate æ. Specifically, the order of composition defines the traversal order of the child nodes of the root node. Furthermore, by the inductive hypothesis, any permissible permutations corresponding to the subtrees can be generated by DFS traversal over the subtrees. Hence, at each child node of the root node, we just follow the corresponding DFS traversal of its corresponding tree. This DFS traversal can generate the given permutation æ, which completes the proof.
D HIERARCHICAL TRUNCATION
In Table [ we present data comparing the number of model re-trainings on the all six dataset with and without the application of truncation. For the Citeseer dataset, the truncation ratios are defined as hst-hop: 0.5 and 2nd-hop: 0.7. For the remaining datasets, the truncation ratios are set at 1st-hop: 0.7 and 2nd-hop: 0.9. The results clearly indicate that the number of model re re-trainings is substantially reduced when truncation is applied. For instance, focusing on the Citeseer dataset the application of truncation significantly reduces the number of retrainings from 1388 to 535. This significant decrease, especially in larger datasets like Amazon-Phote and Amazon-Computer where retraining instances decrease from 147664 6258 and from 317959 12139 respectively, can be attributed to the substantial number of 2-distance neighbors present in these datasets. The application of truncation effectively reduces the computation by omitting a considerable portion of these neighbors. This finding also implies that overall training time is decreased while still maintaining the ability to accurately measure the total marginal contribution.
Table 1: Retraining Number Comparison Per Permutation
Dataset
Truncation
w.t. Truncation
Cora
2241
756
Citeseer
1388
535
Pubmed
3683
887
Amazon-Phood
147664
6258
Amazon- Amazon-Computeer
317959
12139
Coauther- Physics
11178
852
E MIXED NODE DROPPING EXPERIMENT
As mentioned in the experiment, labeled nodes will dominate the performance curve when both labeled nodes and unlabeled nodes. The corresponding experiment result is shown in the Figure 6 This experiment validates the assumption that a effective data valuation method would naturally rank labeled nodes for earlier removal over their unlabeled counterparts. For instance, in the Cora dataset, we can observe that the initial drop in accuracy is significant, indicating the removal of high-value labeled nodes. As the experiment progresses and more nodes are removed, the accuracy barely changes, reflecting the removal of unlabeled nodes which has a minimal impact on performance when most labeled nodes are unavailable. The observed pattern across all datasets is consistent: there a substantial drop in performance at the beginning, followed by a plateau with minimal changes. This suggests that the initial set of nodes removed, predominantly high-value labeled nodes, those critical to the model's 's performance, whereas the subsequent nodes show less influence on the outcome.
18

---

Published as a conference paper at ICLR 2025
Data Shapley
PC-Wintr
Cora
Citeseer
Pubmed
prodiction Accuracy 88
Prodiction Accuracy (%6
Prodiction Accuracy
0.5
24
0.4
0.2
0.2
0.2
0.0
0.0
0.0
220
Number Mixed Node Removed
Number Mixed Node Removed
Number Mixed Node Removed
Amazzon-Phote
Amazon-Computern
Coauthor-Physii Phyyics
Predictonn Acuracy 190
Accuracy (%)
2.6
Prediction Accuracy
0.5
0.4-
0.4
0.2
022
1000
2000
1000
4006
2000
4000
8003
1000
2000 3000
<200 so00
Number Mixed Node Remnoeed
Number of Mixed Node Removed
Number of Mixed Node Removed
Figure 6: Mixed Node Dropping Experiment
F LABELED NODE DROPPING EXPERIMENT
Here, we perform node dropping experiment employing the aggregated value define in the main-body of paper, demonstrate that PC-Wi nter can capture the heterogeneous influence of labeled nodes. As shown in the Figure 7 both PC-Winted and Data Shapley demonstrate effectiveness in capturing the diverse contributions of labeled nodes the model's performance. Particularly in the datasets, PC-Wa Winter exhibits better performance compared to Data
Pubmed and Amazon-Phoot Shapley. other datasets, such as Cora, Citeseer, and Coauthor-Phyy -hhssccs, PC-Winter shows results that are par with Data Shapley.
Shapley
PC-Winter
Cora
Citeseer
Pubmed
Prediction Accursicy (98)
0.6
Prodictinn Accuraccy
8.6
Prediction Accuracy 196)
0.6
0.4
0.2
0.2
50
100
25
30
100
20
50
Number of Node Removed
Number of Node Removed
Number of Node Removed
Amaazon-Phote
Camazon-Compulee
Coauthor-Physice
Prediction Accurery (96)
0.8
Acqurcyy (86)
2.6
0.8
0.6
Prodiction Accuracy
0.6
2.4
0.4
0.2
Figure 7: Labeled Node Dropping Experiment
19

---

Published as a conference paper at ICLR 2025
G EXPERIMENTAL DETAILS
G.1 INDUCTIVE SETTING
Our experiments focus on the inductive node classification task, which aims to generalize a trained model to unseen nodes and is commonly adopted in real-world graph applications (Hamilton et al.) 2017 Van Belle et al., 2022; Jendal et al.) 2022, D D'Amico et al. (023). Unlike the transductive setting (Kipf & Welling 2016) which incorporates the test nodes in the model training process, the inductive setting separates them apart from the training graph. Such a separation allows us to measure the value of the graph elements in the training graph solely based on their contribution to GNN model training. Following (Hamilton et al. 2017), we split each graph & into 3 disjoint subgraphs: training graph Gtr, validation graph 9va. and test graph Gte. The training graph Gtr constructed without any nodes from the validation or test set. Correspondingly, edges connecting to validation node or testing node are also removed from the training graph. For the validation graph Vma and the testing graph Vee, only edges with both nodes within the respective node sets are retained, which is aligned with the inductive setting in prior work (Zhang et al. 2222a)) We utilize Gor to train the GNN model, which is evaluated on Vea for obtaining the data values for elements. The test graph Vie is utilized to evaluate the effectiveness of the obtained values.
G.2 DATASETS
We assess the proposed approach on six real-world benchmark datasets. These include three citation graphs, Cora, Citeseer and Pubmed (Sen et al. 2008) and two Amazon Datasets, Amazon Photo and Amazon-Computer, and Coauther-Physics (Shchur et al., 2018). The detailed statistics of datasets are summarized in T
The statistics presented in Table characecaaa both the structural properties and experimental settings of each dataset. The first four columns present basic graph statistics: the total number of nodes (# Node), edges (# Edge), classes (# Class), and node feature dimensions (# Feature). These statistics together provide a comprehensive view of each dataset's s scale and complexity. The last column (# Train/Val/Test) specifies we split the nodes into three mutually exclusive sets: training. validation, and testing nodes. For example, in the Cora dataset (140/500/1,000) (,000), we select 140 nodes for training, 500 for validation, and 1,000 for testing. The training graph G.v is constructed using only training nodes and their 2-hop neighbors, explicitly excluding any validation testing nodes. Separate subgraphs Guu and G.o created using only validation and testing nodes respectively, maintaining strict separation between splits. This inductive setting ensures no information leakage between splits, the graph elements (nodes and edges) are mutually exclusive between training, validation, and testing graphs A detailed visualization of this split setting can be found in Section M which illustrates both the inductive graph split and the PC-Wi nter value estimation procedure.
experimental setup following the inductive learning setting, where
Table 2: Dataset Summary
Dataset
# Node
# Edge
Class
# Feature
# "Train/Va/Tess
Cora
2,708
5,429
7
1,433
140 / 500 1,000
Citeseer
3,327
4.732
6
3,703
120 / 500 1,000
Pubmed
19,717
44,338
3
500
60 / 550/ / 1,000
Amazon- Photo
7,650
119,081
8
745
160 / 20% 20%
Amazon-Compurt
13,752
245,861
10
767
200 / 20% 20%
Coauthor- Physics
34,493
247,962
8
745
100 / 20% 20%
G.3 DATASET SPLIT
In the conducted experiments, we split each graph G into 3 disjoint subgraphs: training graph Ger validation graph Sea. and test graph Gte. The training graph Gtr is constructed without any nodes from the validation test set. Correspondingly, edges connecting node are also removed from the training graph. For the validation graph V., and the testing graph Vie, only edges with both nodes within the respective node sets retained, which is aligned with
validation node testing
20

---

Published as a conference paper at ICLR 2025
the inductive setting in prior work (Zhang al.) 2021a). We utilize Gtr train the GNN model, which is evaluated on Vea for obtaining the data values for elements. The test graph Vie is utilized to evaluate the effectiveness of the obtained values. In the case of the specific split for each dataset, for the citation networks, we adopt public train/val/test splits in our experiments. For the remaining datasets, randomly select 20 labeled nodes per class for training, 20% nodes for validation and 20% nodes as the testing set.
G.4 CONVERGENCE CRITERIA
Convergence Criterion. For permutation-basel data valuation methods such as Data Shapley and PC Wiin-iiter we follow convergence criteria similar to the one applied in prior work (Ghorbani & Zou 2019) to determine the number of permutations for approximating data values:
1
T1
1-20 1/S
0.05
72
where of is the estimated value for the data element using the first & sampled permutations.
Time Limit. For larger datasets, sampling a sufficient number of permutations for converged data values could be impractical in time. To address this and to stay within realistic scope, cap the computation time at 120 GPU hours on NVIDIA Titan RTX, after which the calculation is terminated.
G.5 TRUNCATION RATIOS AND SYPPE-PPARAMETE
Table 3 includes the typer-parameters and truncation ratios used for value estimation.
Table 3: Truncation Ratios and Hyper- parameterss
Dataset
Truncation Ratio
Learning Rate
Epoch
Weight Decay
Cora
0.5-0.7
0.01
200
5e-4
Citeseer
0,5-0.7
0.01
200
Se-4
Pubmed
0.5-0.7
0.01
200
5c-4
Amazon-Phoo Phozoo
0,7-0.9
0.1
200
0
Amazon-Computt
0.7-0.9
0.1
200
0
Coauthor Coauthor-Physics
0.7-0.9
0.01
30
5e-4
PC-WintanL
PCWWstss
PCWWinter
(N)
Cora
Prodict Accuracy (S)
Citeseer
Prediction Accurcyy (N)
Pubmed
0.700
0.700
0.60
2.12
0.575
0.225
0.550
0.600
150
500
2000
2500
Number Node Removed
Removed
Number Node Removed
Amazon-Photo
Amazon-Computerrs
Coauther-Physics
Prediction Accurary (96)
0.7
Preditton Accuracy
0.8
Preduction Accuracy
0.7
3.50
65
0.6
2.00
3000
4000
1000
4000
40c0 5003 Number Node Bemoved
2010 1:00
Number Node Removed
Number Node Removed
Figure 8: Ablation Study
21

---

Published as a conference paper at ICLR 2025
G.6 BASELINES
G.6.1 DROPPING HIGHI- NODES
Here, we introduce the baselines used for comparison to validate the effectiveness of the proposed method in the dropping node experiment:
Random Value: It assigns nodes with random values, which leads to random ranking without
any specific pattern or correlation the node's features.
Degree basedd Va uue: A node is assigned its degree as its value, assuming that a node's importance in the graph is indicated by its degree.
(LOO) This method calculates a node's value based its marginal contri- bution compared to the rest of the training nodes. Specifically, the value vtt) assigned to each node i is its marginal utility, calculated as v(i) = U (Gtr) - U (9tr") where 9 denotes the training graph excluding node The utility function U measures the model's 's validation performance when trained on the given graph. In essence, the drop in performance due to the removal of node is treated as the value of that node.
heave-one-e
Data Shapley: The node values are approximated with the Monte Carlo sampling method of Data Shapley (Ghorbani Zou 2019) by treating both labeled nodes and unlabeled nodes as players. Notably, we only include those unlabeled nodes within the 2-hop neighbors of labeled nodes in the evaluation process. There are two approximation methods: Truncated Monte Carlo approximation and Gradient Shapley in (Ghorbani & Zou 2019). We adopt the Truncated Monte Carlo approximation as it consistently outperforms
other variants in various experiments.
Notably, there is a recent work (Chen et al. (022) that aims at characterizing the impact of elements on model performance. Their goal to approximate LOO value. Thus, we do not include baseline as LOO is already included.
G.6.2 ADDING HIGH VALUE EDGES
Here are the detailed descriptions on the baselines applied in the edge adding experiment.
Random Value: it assigns edges with random values, reflecting baseline where no information are used for diffcrentiating the importance of edges. Edge-Bet
the Edge- weeness of an edge e is the the fraction of all pairwise shortest paths that go through e. This classic approach assesses an edge's importance based on its role in the overall network connectivity.
Leave owwoouoeoe (LCO): This method calculates edge e's value v(e) based its marginal contribution compared to the rest of the training graph. In specific, v(e) = U (Grr) - U (9i7"
Here, e E Ger represents edge in the training graph Gtr, and Gi, refers to the training graph excluding the edge e.
H DETAILED QUANTITATIVE RESULTS
This appendix presents detailed quantitative results for the node dropping and edge addition experi- ments discussed in the main text. To provide more rigorous evaluation of method's effectiveness, we introduce four key metrics that quantify the insights from Figures 3 and in the main text:
For the node dropping experiment:
Minimum Accuracy:
The lowest accuracy reached during node removal.
Mean Accuracy: The average accuracy across all node removal steps.
For the edge addition experiment:
Maximum Accuracy: The highest accuracy reached during edge addition.
Mean Accuracy: The average accuracy across all edge addition steps.
The rationale behind these metrics is as follows: (1) For node dropping, the Minimum Accuracy refers to the lowest accuracy reached during node removal. A lower value for this metric indicates better
22

---

Published as a conference paper at ICLR 2025
identification of the most critical nodes, whose removal causes the largest performance drop. This metric designed to capture the method's ability to identify the most influential nodes in the graph. Similarly, the Mean Accuracy measures the average accuracy across all node removal steps. A lower mean accuracy suggests the method consistently identifies important nodes throughout the removal process, maintaining lower performance overall. This reflects the method's ability to consistently pinpoint valuable nodes across different stages of the removal process, (2) For edge addition, the Maximum Accuracy corresponds to the highest accuracy achieved during edge addition. A higher value for this metric signals better identification of the most valuable edges, whose addition results in the largest performance improvement. This metric captures the method's s capacity to identify edges that significantly enhance the graph's information content. The Mean Accuracy measures the average accuracy across all edge addition steps, with a higher mean accuracy suggesting that the method consistently identifies important edges throughout the process, maintaining higher performance overall. This reflects the method's s ability to recognize valuable edges across different stages of the addition process. These metrics allow to quantitatively assess each method's effectiveness in identifying high-value graph elements. They provide concrete measures of how well each method causes the accuracy curve drop deeply and consistently in node dropping experiments, and how quickly and sustainedly it raises the accuracy curve in edge addition experiments.
Tables and 5 show the minimum and mean accuracies for the node dropping experiment, while Tables and 7 present the maximum and mean accuracies for the edge addition experiment. These results provide comprehensive quantitative basis for evaluating the performance of our PC-Winter method compared to other baselines across various graph datasets.
Table 4: Node Dropping Minimum Accuracy
Method
Cora
Citeseer
Pubmed
Amazon-Photo
Amazon-Computers
Coauthor-Plysles
Random
(16600
0.6130
0.7110
0,7176
0.5676
0.9164
Degrve
0.6600
0.6040
0.6990
0.6752
0.5625
0.9135
1.00
0.6580
0.6130
0.6920
0.6778
0,5582
0.90039
Data Shapley
0.6200
0.5910
0.6230
0.6255
0.4891
0,8863
PC Winter
0,5990
0.5870
0.6150
0,5340
0.4207
0,8710
Table 5: Node Dropping- Mean Accuracy
Method
Cora
Citeseer
Pubmed
Amazon-Phoot
Mmazon-Cooputers
Coauthor-Physiee
0.6903
0.6411
0.7294
0.8140
0.6807
Degree
0.6814
0.6354
0.7156
0,7377
0.6637
0.9215
100
0.6832
0.6349
0.7020
0.7296
0.6012
0.9197
nata Shapley
0.6124
0.6437
0.7049
0.5467
PC-Winter
0.6248
0.6034
0,6362
0,6306
0,5075
0,8793
Table 6: Edge Addition Maximum Accuracy
Method
Cora
Citeseer
Pubmed
Amazon-Photo
Amazon-Computers
Coauthor-Physiss
Randon
0.7160
0.6550
0.7410
0.8621
0.7975
0.9266
Edge Retwaenness
0.7220
0.6630
0.7470
0.8791
0.7996
0.9255
LOO
0.7140
0.6610
0.7350
0.8582
0.7953
0.9243
PC-Winter
0.7310
0.6750
0.7600
0.8739
0.8145
0.9297
The results in 5
that FC-Winter consistently achieves the lowest minimum and mean accuracies across all datasets in the node dropping experiment. This indicates that PC-Winter is more effective at identifying critical nodes whose removal significantly impacts model performance. The performance gap is particularly notable in larger and more complex datasets AunazonnCooppuorre
such as Amazon-Photo and Amazon-Computerr,
For the edge addition experiment, Tables 6 and 7 show that PC-Winter achieves the highest maximum and mean accuracies across all datasets. This suggests that PC-Winter is superior at identifying valuable edges whose addition leads to the most significant performance improvements. The ad advantage of PC-Winter is consistent across different graph structures and sizes, from smaller networks like Cora to larger ones like Seaautho-PPhssice
23

---

Published as a conference paper at ICLR 2025
Table 7: Edge Addition Mcan Accuracy
Method
Cora
Citeseer
Pubmed
Amazon-
Compuen-Compieers
Coanthor-Pyyan
Randon
0.6330
0.9226
Edge Betwsenness
0.6855
0.6217
0.7287
0.8475
0.7752
0.9202
0.9186
PC FC-Kinter
0.7197
0,6616
0.7511
0,8640
0,8023
0.9266
These quantitative results corroborate the visual trends observed in Figures LandresBanddP 4 of the main text. They provide strong evidence for the effectiveness of PC-Winter in both identifying critical nodes for removal and valuable edges for addition, outperforming other baseline methods across various graph datascts.
I ABLATION STUDY AND PARAMETER ANALYSIS
1.1 ABLATION STUDY
This Appendix Section offers an in-depth ablation analysis across full six datasets to investigates the necessity of both Level Constraint and Precedence Constraint in defining an effective graph value. The results, as shown in Figure 8 consistently demonstrate across all datasets that the absence of either constraint leads to a degraded result when compared to the one incorporating both. This underscores the importance of both two constraints in capturing the contributions of graph elements to overall model performance.
1.2 THE IMPACT OF PERMUTATION NUMBER
This part expands upon the permutation analysis presented in the main paper. It provides comprehen- sive results across various datasets, illustrating how different numbers of sample permutations impact the accuracy of PC-Winted The results of full datasets shown in Figure 9
The results reveals
Data Sha play
50 perms
100 perms
Converged PC-Winter
Citeseer
Pubmed
Pretitiin ecturecy P80
ouoe
666-
0.68
666
0.66
082
0.64
080
590
Number Node Removed
Number of Node Removed
Number Node Ramoved
Amazor-Phato
Amazon- Compuutrs
Coauthor-Physice
6.6%
0.75
0.55
0.50
6.70
0.50
6.6-
0.09
0.66
1850
5202
Number Node Ramoved
Number of Node Ramoved
Number Node Ramoved
Figure 9; The Impact of Permutation Numbers
that increasing the number of permutations generally improves the performance and accuracy of the valuation. PC-Winter also show robust results even with a limited number permutations, high- lighting its effectiveness. The phenomenon is consistent across all datasets where approach with just 50 to 100 permutations manages to compete closely with the fully converged Data Shapley, emphasizing the efficiency of PC-Winter various settings.
24

---

Published as a conference paper at ICLR 2025
1.3
THE IMPACT OF TRUNCATION RATIOS
Our approach involves truncating the iterations involving the first and second-hop neighbors of labeled node during value estimation. Here, we investigate the impact of truncation proportion on overall performance, using the same number of permutations in our primary node-dropping experiment. As shown in Figure [0 we adjusted the truncation ratios for the Citation Network datasets. The ratios ranged from truncating 50% of the first-hop and 70% of the second-hop neighbors (0.5-0.7), up to 90% truncation for either first-hop (0.9-0.7) or second-hop (0.5-0.9) neighbors. For the Cora and Citeseer datasets, increasing truncation the first-hop level had minimal impact on performance, and PC-Winter still significantly outperformed Data Shapley. In the case of the Pubmed dataset, more extensive truncation the first-hop level notably reduced performance. Regarding large datasets such as the Amazon, while truncation at either the first or second- levels had a marginal negative effect on performance, PC PC-Winter 's estimated data values generally remained superior to results of Data Shapley.
In addition, we provide detailed analysis of our truncation strategy across other datasets. It includes results not presented in the main text, focusing the impact of limiting model retraining times to the first and second-hop -hop neighbors in value estimation. We investigate the impact of truncation proportion overall performance, using the same number of permutations as in our primary node-dropping experiment. The findings on full datasets are illustrated in Figure 10 Specifically, findings reveal that in datasets like Cora and Citeseer, adjusting truncation primarily at the first-hop level has a negligible impact on the accuracy of node valuation, with PC-Winter still maintaining a considerable advantage and Coauther-PPe Coauther-Physics, while truncations had a marginal negative effect on performance, SC-Winter 's estimated data values generally remained better than Data Shapley. This analysis indicates that PC-Wi nter can afford to employ larger truncation, enhancing computational efficiency without substantially sacrificing the quality of data valuation.
Data Shapley. For large datasets such the Amazon-
Photo,
Data Shapley
0.-00.7 Truncation
0.9.0.7 Truncation
0.5-0.3 Truncation Pubmed
Cora
Citeseer
Prediction Accuraty (8)
Prediction Accuracy (S0
Accuracy (S)
0.70
0.8
0.64
0.62
8.6
0.2-
0.50
0.62
150
200
300
400
100
300
400
500
1000
1500
2000
2500
Number Node Removed
Number of Node Removed
Number of Node Removed
Shapley Amazon-Phato
Truncation Coauthor-Physics
Amazon-Computers
PettiinnAccceee Accurscy (8)
0.65
0.93
0.80
PreditionnA Accurcy
Prediction Accurecy
0.92
0.75
0.80
Prefition
0.20
0.60
0.5
0.55
0.50
0.45
0.90
0.58
0.59
035
Number Node Removed
Numbier Removed
Number Removed
Figure 10: The Impact of Truncation Ratios
25

---

Published as a conference paper at ICLR 2025
Table 8: Permutation Number and Time Comparison
Dataset
Truncation
PC-Winter
Data Shapley
Perm Number
Perm Time (hrs)
Perm Number
Perm Time (hrs)
Cora
0.5-0.7
325
0.013
327
0.024
Citeseer
0.5-0.7
291
0.018
279
0.037
Pubmed
0,5-0,7
316
0.025
281
0.285
Amazon-Phoo
0.7-0.9
418
0.211
109
1.105
Amazon-Compa
0.7-0.9
181
0.662
33
3.566
Coauthor- Physics
0.7-0.9
460
0.119
45
2.642
1.4 EFFICIENCY ANALYSIS
Here, we compare the computational efficiency our proposed method PC-Winter and the Data Shapley approach in terms of permutation number and time per permutation. As detailed in Table the results indicate that PC-Winter requires significantly less time to compute each permutation across various datasets. Specifically, for the Cora dataset, PC-Winter completes each permutation in approximately half the time required by Data Shaples ey. Moving to larger datasets, the efficiency of PC-Winter becomes even permutation time is only a fraction of what is required by Winter takes slightly over half an hour per permutation whereas Dat Shapley exceeds three and a half hours. This consistent reduction in permutation time demonstrates the computational advantage of PC-Winter, particularly when handling large graphs. Combining the insights from the Permutation Analysis shown in Figure 9 with the Permutation Comparison T we observe that for datasets such as Cora, Citeseer, Amazon- Photo, and Amazon mrazoon-Computer, around 50 permutations are sufficient for PC-Wi nteer to achieve performance comparable to that Data Shapley. Simple calculations demonstrate that our method significantly faster than Data Shapley in achieving similar performance levels. For instance, in the Cora dataset, the speedup factor is 327x0.024 = 12.07, and for the Citeseer dataset, 0.970.037 = 11.47. The 50x0.013
ey.
pronounced. For instance, in the
Amazon-Computer dataset, PC-Winter" p
Data Shapley -PC --t----CCCeeeeeee
50x0.018
speedup factors for Amazon-Photo and Amazon-Computee are 109x11100 50x0.221 11.42, and 33x3.566
50x0.662
3.57, respectively. For Coauthor-Physics, it takes about 100 permutations for PC-Winter to match the performance Data Shapley, which implies a speedup factor of 45x2.642 10.00. 100x0.119
In conclusion, PC-Winter can achieve stronger performance than Data Shapley using the same or even less time. Furthermore, it takes PC-Winter much less time to achieve comparable performance Data Shapley. Notably, though PC PC-Winter is significantly more efficient than Data Shapley, its scalability is still limited, and future work in further improving its efficiency is desired.
1.5 COMPLEXITY ANALYSIS
We analyze the complexity of the PC-Winter. For convenience, we assume that we are dealing with a d-regular graph. There are a total of labeled nodes the graph. As described in the paper, deal with GNN model with 2 layers. Without loss of generality, the dimensionality of node representations each layer. We assume the number of classes in the dataset is C. For hierarchical truncation, is consistent with the description in Section 3.4. Then, the number of nodes in a computation tree d2, With hierarchical truncation, the number of nodes in the for any labeled node is Nuai = 1 truncated computation tree is Nerun = 1 d. r1 + d² (1- 11-rr -ri -2)). When the truncation ratios are large, Nerun Njuut For instance, when r1 = 72 0.9, Ntran could be less than 5Time Complexity Analysis: We now analyze the time complexity of a single permissible permutation of the PC-Wi nter algorithm. We begin by examining the time complexity of generating a single permissive permutation. Then, we investigate the complexity of single model retraining and provide the total retraining number for a single permutation. Finally, we combine these analyses to derive the overall time complexity for generating one permissible permutation and going through for calculating the marginal contributions. Time complexity of generating a single permissive permutation: The time complexity of traversing the truncated contribution tree generate single permissive permutation is OLL-Nmm) Numn). J. In particular, there are L- NNNuu + nodes the contribution tree (including the dummy node). Hence, the cost of DFS traversal over the contribution tree is
use F' to denote
assume adopt a truncation ratio of r2, which
26

---

Published as a conference paper at ICLR 2025
O(L Nurn +1+ -NLnN (L Nuun). Time complexity of one model retraining: As described in Section 3.4, with local propagation, for each model retraining, we only need to perform feature aggregation single partial computation tree. The size of a partial computation tree is, on average, Nu,, Therefore, the feature aggregation complexity for each retraining step is O( Man F)., where F 2
2 is the dimension of node features. The feature transformation complexity for each model retraining is O(F F + F ()=)(F where C' is the output dimension (number of classes) of the GNN model. Therefore, the total time complexity of single retraining is ( FF F²). Without local propagation, the feature aggregation complexity for each model retraining would be much larger, since the propagation needs be performed the entire graph. The number of model retraining in single permutation: In a permissible permutation, we need to perform retraining for each node in the truncated contribution tree, which has L Nuun nodes in total. Therefore, L .Nrrnn model retrainings are needed for a single permutation. Total time complexity for single permissible permutation: With local propagation and hierarchical truncation, the total time complexity of single permissible permutation in PC- wic-wiiee nt is: OL LL-Nuun' ( F+))
OOL-Nuum (1+ Myt. F2))
OLL Nuun NN F+ F²)). Notably, the time complexity of generating a permissible permutation negligible compared to the cost of model retraining. The proposed strategies, hierarchical truncation, and local propagation, help reduce the overall time complexity of the PC-Winter algorithm. In particular, hierarchical truncation makes Numn much smaller than Nimt, greatly decreasing the total number of model retraining required for a single permutation. On the other hand, Local propagation reduces the feature aggregation complexity, greatly reducing the cost of each retraining.
The proposed strategies, hierarchical truncation, and local propagation, help reduce the overall time complexity of the "C-Winter algorithm. In particular, hierarchical truncation makes Nerun much smaller than Nfall, greatly decreasing the total number of model retraining required for a single permutation. On the other hand, Local propagation reduces the feature aggregation complexity. greatly reducing the cost of each retraining.
worth noting that, similar to traditional Shapley value computation and its variants such as S S-Shapley, computing the exact PC-Wi Wineerr value remains #P-complete (Xia et al. (023). Our analysis above specifically describes the time complexity of our approximation framework, which achieves polynomial-time efficiency through Monte Carlo permutation sampling, hierarchical trunca- tion, and local propagation. This approach is aligned with the polynomial-time permutation-base approximation methods in the literature (Xia et al. 2023
J ADDITIONAL REGRESSION TASK EVALUATION
To validate our method's effecctiveness beyond classification tasks, conducted additional exper- iments on node regression using the US election 2012 dataset from (Jia & Benson] (020).. We employed 2-layer SGC model in inductive setting, sampling 30% of nodes in the training graph as labeled nodes.
US- US-Election Dataset
-0.12
Negative
-0.4
Duta Shapley
PC/Minter
200
400
500
800
10000
Number Node Removed
Figure 11: Comparison of PC-Winter and Data Shapley node regression task. The y-axis shows negative MSE (higher is better) as nodes are progressively removed based on their computed values.
27

---

Published as a conference paper at ICLR 2025
For rigorous comparison, configured both PC-Winter and Data Shapley under consistent experimental settings. PC-Winter was implemented with truncation ratio of 0.5-0.7, while both methods used 50 permutations for value computation. The evaluation protocol involved dropping unlabeled training nodes sequentially based on their computed values, from most to least important, assess each method's ability to identify influential nodes.
We evaluated performance using negative MSE, calculated as the negative the mean squared error between predicted and actual values. This metric choice serves dual purposes it maintains consistency with our classification experiments where higher values indicate better performance, while enabling direct interpretation of performance drops. When removing crucial nodes. we expect to see decline in negative MSE, with steeper declines indicating better identification of important nodes.
Figure 11 shows the comparative results between PC-Winter and Data Shapley. PC-Winter achieves better mean negative MSE of -0.1147 compared to Data Shapley's -0.0993, The steeper drops in PC- Winter's curve demonstrate its superior ability to identify nodes crucial for model performance. This performance advantage remains consistent across different stages of node removal, indicating robust valuation quality throughout the evaluation process.
This regression task evaluation strengthens our original findings several significant ways. First, validates method's effectiveness continuous-valle classification setting. Second, the inductive setup tests the method's generalization capability. Third, the successful application with SGC architecture demonstrates robustness across different model types. Together with our classification results, this comprehensive evaluation provides compelling evidence for both the effectiveness and generality of our approach in graph data valuation.
predictions, extending beyond the discrete
K BALSSBB ACCURACY ANALYSIS
To provide a more comprchensive evaluation perspective, we analyze PC- CC-WWitte's performance using Bass-balanced accuracy. This metric helps assess whether our method can effectively identify important nodes across all classes without bias. Class-balanced accuracy is particularly important for datasets with imbalanced class distributions, as gives equal weight to each class regardless of its size.
0.0
213
Figure 12: Class-balanced accuracy comparison between PC-Winter- and Data Shapley across different datasets. The x-axis shows the number of nodes removed, and the y-axis shows the class- balanced accuracy. From left to right: (a) Cora, (b) Citeseer, (c) Pubmed.
Figure 12 presents the comparison between PC-Winter and Dat Shapley using class-balanced accuracy on three benchmark datasets. On the Cora dataset, PC-Winter demonstrates a more substantial drop in balanced accuracy from 0.72 to 0.64, compared to Data Shapley more gradual decline, indicating better identification crucial nodes across all classes. Similar patterns observed on Citeseer, where DC-Winter' balanced accuracy drops from 0.62 to 0.57, showing consistent performance across different class distributions. For Pubmed, CC-Winter achieves a significant drop from 0.74 to 0.65, further validating its effectiveness in identifying important nodes without class bias.
The steeper drops in balanced accuracy across all datasets demonstrate that PC-Winter effectively identifies nodes crucial for model performance while maintaining fairness across different classes. This analysis complements main results by showing that PC-Wi nter's superior performance
28

---

Published as a conference paper at ICLR 2025
extends to class-balanced metries, suggesting its robustness and applicability in scenarios where class balance is particularly important.
L INTEGRATION WITH P-SHAPLEY
Recent work by Xia et al. 2024) proposed P-Shapley, which innovates on utility function design by utilizing probabilistic classifier outputs. We investigate how this fiility-oouued innovation interacts with our structural approach to graph data valuation by integrating P-Shapley's probability- utility function with both Data Shapley and PC- Weee frameworks.
Cras Boteet
Choaer Ddlest
P.ree Pateett
6.55
0.00
0.50
20-3 Number UrEaeeic
Mrlaeeii Aurooad
Number Uriaeiic
Figure 13: Performance comparison using different utility functions. The results show PC-Winter maintains its advantages regardless of utility function choice, while demonstrating complementary benefits from P-Shapley's 's probability-bas utility. From left to right: (a) Cora, (b) Citeseer, (c) Pubmed.
Our experimental results, shown in Figure 13 reveal several important insights about the relation- ship between structural innovations and utility function design in graph data valuation. Most no- tably,PC- Caneectnneeee er consistently outperforms Data Shapley regardless of utility function choice. On the Cora dataset, PC-Winter achieves minimum accuracies of 0.599 and 0.608 with standard and P-Shapley utilities respectively, compared to Data Shapley's 0.620 and 0.625. This pattern holds across datasets, though with varying magnitudes.
The consistent performance advantage demonstrates that PC-Winter's core innovation its precedence- precedence-constrrineed formulation for handling graph dependencies provides fundamental benefits independent of utility function design. The steeper performance drops in PC-Wi -Winter variants indi- cate more effective identification of crucial nodes, validating that our structural approach addresses fundamental challenges in graph data valuation.
Interestingly, P-Shapley's probability-based utility function shows complementary benefits that vary by dataset. On Cora and Citeseer, integrating P-Shapley's utility with PC- OC-Winter leads to slightly improved node importance identification, while on Pubmed, the standard accuracy utility performs better. This dependent behavior suggests that while both structural and utility- innovations offer benefits, they operate different aspects of the data valuation problem.
These findings highlight the modularity of innovations data valuation: improvements in handling graph structure (like PC-Winter) can be effectively combined with advances in utility function design (like P-Shapley). While both approaches contribute to better data valuation, our results suggest that addressing the structural challenges of graph data provides consistent benefits across different evaluation frameworks.
M PC-WINTER FRAMEWORK OVERVIEW
Figure 14 presents an overview of the PC-Winter framework for graph data valuation. The framework operates inductive setting, where the input graphs divided into three mutually exclusive structures: the Training Graph, the Validation Graph, and the Testing Graph.
The Training Graph contains the elements to be evaluated and is the main focus of the PC-Winter algorithm. Within this graph, nodes labeled as (l. 4 represent labeled nodes, nodes labeled as w (wo- W3) represent I-distance neighbors of labeled nodes, and nodes labeled as (wn 146) represent
29

---

Published as a conference paper at ICLR 2025
Input Graphs (Inductive Setting)
181
Mutuslly Exclusive
Muturlly Exclusive
14g
Training Graph (Elements to be evaluated)
Validation Graph (Accuracy as Utility Function)
Testing Graph For downstream tasks)
PC-Winter Value Estimation Steps
in
Me
to
us
Nierarchical truncations on
2. Retrieve permissive Pormuatation π
Computational Tree
marginal contribution
player validation accuracy difference
Avorago
averaging marginal
player over multiple permutations
Figure 14: PC-Winter Framework Overview
2-distance neighbors of labeled nodes. This hicrarchical structure aligns with the concept of the Computation Tree introduced in Definition 1 (Section 2.3).
The Validation Graph is used for calculating the accuracy of the GNN model, which serves as the utility function in the PC-Winter framework (Definition 3, Section 3.1). The Testing Graph is reserved for downstream tasks, such as the node dropping experiments conducted in Section 4.2.
PC-Winter Value Estimation Steps:
Perform a Preorder Traversal with hierarchical truncations on the Computational Tree T. This step generates permissible permutations that respect the Level and Precedence Constraints (Section 3.3, Theorems and 2). The hierarchical truncation strategy (Section
3, 3.4.2) is applied to reduce computational complexity while maintaining valuation quality.
2. Retrieve permissive Permutation π from the Preorder Traversal. Each permutation repre- sents a unique ordering of the players (nodes) in the Training Graph.
3. Calculate the marginal contribution of each player based the validation accuracy differ- ence. This step involves retraining the GNN model on subgraphs induced by the permutation and measuring the change in accuracy when player is added (Definition 3, Section 3.1). D The local propagation strategy (Section 3.4.3) is employed to efficiently compute these marginal contributions.
4. Estimate the PC-Winter Value by averaging the marginal contributions of each player over multiple permutations. The permutation sampling strategy (Section 3.4.1) is used to approximate the PC -Winter value (Equation 3, Section 3.2) by considering a subset of permutations.
The FC-Winter framework provides a comprehensive approach to graph data valuation by incor- porating graph-specife constraints and efficient approximation strategies. The framework's 's design allows for the accurate quantification of the importance of individual graph elements (nodes and
30

---

Published as a conference paper at ICLR 2025
edges) while considering their complex interdependencies and contributions to the GNN model's performance.
Table 9: Key Notations Used in the Paper
Notation
Definition
Description
(V.
Graph
Original graph with node set and edge set Set of nodes with known labels
Vi C V P
Labeled Node Set
Player Set
Union nodes from computation trees of all la- beled nodes (Definition 2)
T.K
K-level Computation Tree
Computation tree of depth K rooted at node 2s (Definition 1)
D(p)
Descendants
Set of descendants of player p in the contribution tree
Ω
Permissible Permutations
Set of permutations satisfying both Level and Precedence constraints
Pf
Predecessor Set
Set of players appearing before player in permu- tation π
U()
Utility Function
Model performance validation set (Definition
3)
(P,UU)
PC-Winter Value
Value of player p based on permissible permuta-
tions
r1-12
Truncation Ratios
Hierarchical truncation ratios for first and second- hop neighbors A node in the original graph G
Node
Node Features
Feature vector of node v/s
yi
Node Label
Label of node t; Set of possible labels for nodes Dimensionality of node feature vectors
C
Label Set
Feature Dimension
(I))
Node Representation
Learned representation of node v, the k-th GNN layer
W
Weight Matrix
Learnable weight matrix in GNN layers Set of neighboring nodes of node Number of edges connected to node 1/2 Graph induced by a subset of players P Graph Neural Network model trained on given graph
N(s)))
Neighbors
deg(v;)
Node Degree
(S)
Node-Induced Graph
A(-)
GNN Model
acc(-)
Accuracy Function
Function measuring the accuracy of a trained GNN model
T
Contribution Tree
Tree structure representing hierarchical contribu- tions of players
II(P)
Permutations
Set of all possible permutations player set A specific permutation of players
Permutation
[i]
Permutation Rank Sampled Permutations
Positional rank of player in permutation π A subset of permissible permutations sampled for approximation
Ω
N NOTATION TABLE
To facilitate better understanding of our methodology and theoretical framework, present comprehensive table of notations at Table 9 used throughout this paper. The notations cover various aspects of our work, including graph structures, neural network components. computational trees, and permutation-relate concepts. This systematic organization notations aims to help readers track and understand the mathematical formulations and algorithmic components effectively.
31

---

Published as a conference paper at ICLR 2025
Additionally, provide detailed descriptions for each notation to ensure clarity and precision in mathematical expressions.
The notations organized into several conceptual categories. The first category includes basic graph structural elements (g. V. 8) and node attributes (zt, yz). The second category covers computation tree-related notations (T,K, D())), which are essential for understanding our hierarchical valuation framework. The third category encompasses permutation-
notations (Ω, я, P(),, which are crucial for the PC-Wi n value computation. Finally, we include model-specific notations (h1*), W) and evaluation metrics (U(-), acc(-)) that are used throughout our theoretical analysis and experimental validation.
32


Reviews:
[{"review_id": "jFLzPLh4in", "reviewer": "Reviewer_zGxE", "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. \n\nThe authors introduce the precedence constrained Winter value model (PC-Winter). \n\nThey also describe how to approximately compute such values, for either nodes or edges in a graph. \n\nExperiments on an inductive node classification task are done, using 6 real world datasets. \n\nBaselines (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. \n\nClearly, efficiency is a major challenge in this framework, as emphasized by the authors as well.  \n\nMoreover, it would have been interesting to include another prediction task.", "questions": "Can the authors comment on the data valuation performance based on other graph facets, such as graph density?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "First to study an important problem, data valuation for graphs. \n\nClearly written paper. \n\nClear development and description of the proposed valuation model. \n\nReasonable experimental evaluation.", "weaknesses": "A second prediction task would have been a good addition to the experimental framework. \n\nEfficiency remains a bottleneck for valuation on large graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6DE7nCXCTw", "reviewer": "Reviewer_xxT4", "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.", "questions": "Q1: As for W1, What is the essential difference between precedence-constrained PC-Winter and a fine-tuned multi-layer GNN?\nQ2: As for W1, what is the basis for considering all duplicates? Does each duplicate contribute to the final score? \nQ3: As for W2, could you expand the categories of datasets? (e.g., bioinformatics, computer vision, etc.)\nQ4: 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.\nQ5: 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\nS2: 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.\nS3: 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.\nW2: 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ooYTBA7Jmh", "reviewer": "Reviewer_627W", "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.", "questions": "Q1. There are many symbols in the paper, so it is recommended to provide a symbol table.\nQ2. 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.\nQ3. The content in Table 2 is confused.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "S1: The research topic of data valuation for graph-structured data is important, which breaks the assumption of being independent and distributing.\nS2: The proposed techniques in Section III are solid.\nS3: 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.\nW2. The length of the article is beyond the space limit.\nW3. 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. \nW4. 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:\nHaocheng 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)\nI suggest authors should supplement more related baselines in the experiment and discuss them in the Related Work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9vmRP6mnw5", "reviewer": "Reviewer_8Mde", "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.", "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.\nQ2: 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.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1: The valuation of data for nodes in graph-based tasks, particularly in Graph Neural Networks (GNNs), is a crucial and intriguing problem.\nS2: This paper models the problem of graph data valuation as a distinctive form of a cooperative game.\nS3: 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.\nFor 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.’\nW2: 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.\nW3: 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.\nW4: The paper does not present any experimental results to demonstrate the scalability of the proposed algorithms.\nXia 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)