Shapley-Guided Utility Learning for Effective Graph Inference Data Valuation
Authors: Hongliang Chi
Qiong Wu
Zhengyi Zhou
Yao Ma
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Learning
Data Valuation
Graph Neural Networks
Data-centric AI
Primary area: learning on graphs and other geometries & topologies

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

Published as a conference paper at ICLR 2025
SHAPLEY-GUDEE UTILITY LEARNING FOR EFFECTIVE GRAPH INFERENCE DATA VALUATION
Hongliang Chi', Qiong Wu', Zhengyi Zhou?, Yao Ma
'Rnsssllerr Polytechnic Institute, Troy, NY, United States 2 AAT&T Chief Data Office, Bedminster, NJ, United States ichih3@rpi.ede qw65470att. com,
com, mayl30rpi. edu)
ABSTRACT
Graph Neural Networks (GNNs) have demonstrated remarkable performance in various graph- machine learning tasks, yet evaluating the importance of neighbors of testing nodes remains largely unexplored due to the challenge of assessing data importance without test labels. To address this gap, we propose Shapley-Guided Utility Learning (SGUT.,, a novel framework for graph inference data valuation. SGUL. innovatively combines transferable data-specific and model- specific features to approximate test accuracy without relying ground truth labels. By incorporating Shapley values as a preprocessing step and using fea- ture Shapley values as input, our method enables direct optimization of Shapley value prediction while reducing computational demands. SCUL overcomes key limitations of existing methods. including poor generalization unseen test-time structures and indirect optimization. Experiments on diverse graph datasets demon- strate that SGUL consistently outperforms existing baselines in both inductive and transductive settings. SGUL offers an effective, efficient, and interpretable approach for quantifying the value of test-time neighbors.
INTRODUCTION
Data valuation, the task of quantifying the value of individual data points for machine learning (ML. tasks, has gained significant attention in recent years. As ML models and datasets continue to grow in scale and complexity, understanding the contribution of each data point becomes crucial
for fair compensation, dataset curation, and business strategymmaking (Peil 2020 Sim al. 2022
DalleMule & Davenport (017)) Concurrently. Graph Neural Networks (GNNs) (Kip' & Welling
al.] [017]] Wu et al., 2019 Klicpera et al. 2018 have demonstrated remarkable performance in various graph- basedased machine learning tasks, including social network analysis (Fan
2016||
jet al. 2019b Goldenberg. 202T), recommendation systems (Fan al. [019a] Xu et al. 2020), and
molecular property prediction (L.i et al. [022] Wu et al. 2023). Notably, the success of GNNs, like
other ML methods, heavily relies on informative data.
Unlike Euclidean data, graph data is characterized by its non-independent and identically distributed (non-lID) nature, where nodes influence each other according to the graph structure. This property necessitates specialized data valuation methods for graph data. Addressing this necessity, recent work has extended data valuation methods to graph data, introducing the concept of graph data valuation to assess the contribution of graph structures (Chi et al., 2024a). For general data valuation, game theoretic approaches (Ghorbani & Zou 2019; K woo & Zoul 2021 Wang & Jia 2023] Chi et al.) 2024 have been widely adopted. As with other game theoretie methods, the value of graph structure is derived from its marginal contributions to different subsets of the dataset. These marginal contributions are quantified by a utility function, which measures how the model's performance changes with or without particular graph structure. Specifically, the utility function maps from set of players (training graph structures) to their joint contribution to the model's performance, typically measured using accuracy on labeled validation nodes. Data values are then computed based on how the utility function's 's results change across different subsets of graph structures.
Part of this work was done while the first author intern AT&T CDO. Code released httpt::///// ///1 thub. com/ Frankh chi httt/innfadddaaaaaaaaaaaaaaaaaae va luat

---

Published as a conference paper at ICLR 2025
Importantly, graph structures can contribute not only during training but also during inference, thus possessing inherent value. Recent work (Yang et al. 2023) has further emphasized the importance of graph structures at test-time, demonstrating that utilizing only testing graph information can achieve performance comparable to full GNNs. In real-world applications, such as GNN-based recommender systems, real-time recommendations often rely dynamic graphs derived from social networks or item interactions. In these scenarios, assessing the value of inference- time graph data is crucial for optimizing user experience. While evaluating inference-time graph data is key for GNN performance improvement and real-world applications, most existing methods focus on training data valuation, leaving the value of inference graph structures, especially test node neighbors, largely unexplored.
However, designing data valuation methods for graph inference structures faces fundamental chal- lenges: 1. Lack of test labels: Traditional game-theoretic approaches rely on labeled validation data as proxy for model performance on testing data. In the case of graph inference data valuation, aceuracy on test nodes directly represents model performance. However, the ground truth labels are unavailable for test nodes. 2. Limitations of existing utiliiyy learning methods: While surrogate models could potentially approximate utility functions for test-time structures, current methods (Wang& et al. 2021) are inadequate for graph inference data valuation due to two primary issues: (a) Inaplicaaiility to unseen test-time structures: Existing models are typically trained on mappings from training data subsets to validation accuracy. This approach fails when applied to different set of players, such as test node neighbors. (b) Indirect and inefficient optimization: Current methods often use accuracy as the utility learning objective. This approach does not directly optimize the fitted Shapley values against ground truth Shapley values, which is the ultimate goal of data valuation. Fur- thermore, this indirect approach necessitates processing and storing large amounts of accuracy-level data, leading to increased memory requirements. This inefficiency becomes particularly problematic when dealing with large-scale graphs.
To address these challenges and enable effective graph inference data valuation, we propose Shapley- Guided Utility Learning (SGUT.), novel interpretable and efficient framework for estimating graph inference data value without relying on test labels. Our key contributions are as follows:
We are the first to formulate the graph inference data valuation problem. This addresses a significant gap in the field, where the importance of test-time graph structures has been recognized but not quantified through data valuation methods.
We propose SGUL, novel utility- lelint-leerning framework for graph inference data valuation that addresses the challenge of valuation without test labels. Our approach introduces a transferable feature extraction method that transforms player-dependent inputs into general features.
We develop a chaaply--uidde optimization method that enables direct optimization of Shapley values, improving computational efficiency and model effectiveness.
We conduct extensive experiments on various graph datasets, demonstrating that SGUL consistently outperforms baseline methods in graph inference data valuation tasks
2
PRELIMINARY STUDY
2.1 GHEEREHEOI DATA VALUATION
Data valuation, the task of quantifying the contribution of individual data points to machine learning (ML) tasks, has gained significant attention in recent years. tume-theoretic approaches, particularly those based on cooperative game theory, have emerged as a prominent framework for data valuation (Ghorbani & Zou| 2019 Kwon & Zou 2021 Wang & Jia 2023). In this context, i.i.d training data points are treated as players in a cooperative game, where they can form coalitions to contribute collectively model performance.
The Shapley value, a solution concept from cooperative game theory, has been widely adopted for fair allocation of value among players. For a player in a set of players D. its Shapley value defined as: (D, U) = [ī] Σ Exen(D) [U (DF U (i}) - U (DF) where II(D) is the set of all permutations of D. DF is the set of players that appear before i in permutation म, and U is the utility function. The Shapley value (D, U) represents the average marginal contribution of data point i across all possible coalitions. In practice, reduce computational complexity, we often estimate Shapley values by sampling a subset of permutations rather than considering all possible permutations (Ghorbani & Jia et al. 2019). Central to these approaches is the utility function, which quantifies the
Zou 2019
2

---

Published as a conference paper at ICLR 2025
contribution of subset of players to the overall performance. Formally, define the utility function as: U 2n + R where 2D represents the power set of D. For any subset - D, (S) measures the performance achieved by this subset.
The representative work of Data Shapley (Ghorbani & Zou 2019) first introduced Shapley value for data valuation. In this framework, well as in subsequent game-theoneee approaches (Kwon & Zou 2021: Wang & Jia 2023), training samples are treated as players, and the utility function is typically defined based on the model's performance on a validation set: (S) Acc(Js, Dmmt) where S C Dr is a subset of the training dataset, [s denotes a model trained on subset S, and Dval is a validation set used evaluate the model's performance. This formulation allows us to quantify the contribution of different subsets of training data to the model's 's predictive accuracy.
2.2 GRAPH DATA VALUATION
While Data Shapley and subsequent methods (Ghorbani & Zou 2019 Kwon Zou 2021 Wang
& Jia 2023) have been effective for i.i.d. data, they face significant challenges when applied to graph-structured data. A key challenge is capturing the hierarchical and dependent relationships among graph elements. In GNNs, node's contribution to model performance is intricately linked to its position within the computation tree and its relationships with other nodes. Traditional Shapley value calculations, which treat all players (nodes) independently, fail account for these crucial dependencies, potentially leading to inaccurate valuations. To address these challenges, recent work has proposed more granular approach to graph data valuation (Chi et al.) 2024a). This approach introduces two key constraints to the Shapley value calculation: the Level Constraint and the Precedence Constraint. These constraints capture the hierarchical and dependent relationships among graph elements. For detailed discussion of these constraints, please refer to Appendix D.2
3 METHODOLOGY
3.1 GRAPH INFERENCE DATA VALUATION PROBLEM
GNNs have demonstrated remarkable performance across various real-world applications, where the k-hop neighbors of key nodes provide essential context for predictions. For example, in protein- protein interaction networks, traffic systems, and social networks, neighhoring nodes play vital roles in predicting properties of nodes of interests (Jha et al. 2022 |aan et al. [0222] Liu et al. (021). Therefore, quantifying the importance of test-time neighboring structures becomes critical challenge for improving GNN performance, particularly for applications requiring real-time inference.
Given these considerations, we formally introduce the graph inference data valuation problem:
Input Setup: (1) Training graph GT: (VT., &Tr X1.) with labeled nodes Di, C >/,, and labels YT- and fixed trained GNN model f(:): (2) Validation graph Gval = (Vval. Evals Xva) with labeled nodes Va and labels Y vari (3) Test graph Gr: = (Vre, ETc, XTe) with target nodes V, but no labels.
With this setup, we define the graph inference data valuation problem as follows:
Definition 1 (Graph Inference Data Valuation). Given set of target test nodes V Vie. their neighborhood N (V2),, and a downstream task T, the goal of graph inference data valuation is to learn a calue-assignment function é : (V.). + R that assigns scores to the neighbors of V2 based on their contribution to the performance of f(-) on task T.
Graph inference data valuation problem primarily focuses on (N,)), the k-hop neighborhood of target nodes V4, where k typically equals the number of GNN layers L. This choice naturally aligns with GNNs' message passing mechanism, ensuring we capture all nodes that influence target nodes' predictions through the network's 's receptive field.
3.2 STRUCTURE-AWAR SHAPLEY VALUES FOR GRAPH INFERENCE DATA VALUATION
To address the graph inference data valuation problem. we adopt the Structure-Awwe Shapley value formulation with connectivity constraints (Chi et al. (2244)). Unlike PC-Winter (Chi et al. (024a) which defines players as individual nodes in computation trees, our test-time valuation focuses solely on test node neighbors. This fundamental difference in player definition naturally leads to use only
3

---

Published as a conference paper at ICLR 2025
the Precedence constraint, which ensures connectivity between added nodes during value calculation, as the Level constraint from training-tima valuation becomes inapplicable to our setting.
Formally, given set of target test nodes Va C. Vts and their collective neighborhood (V))), define the Structure-Awart Aware Shapley value for each neighbor as follows:
(N(()) = (((A((I TE((((2))
E (NTOMM (NT(()
(I)
where U 2 + R is utility function mapping from the power set of (V;) (all possible subsets of neighbors) to real numbers, ((N(VV)) is the set of all permissible permutations that satisfy the graph connectivity constraints, and N3 (V)) is the set of neighbors that appear before in permutation x.
As shown above, the utillity function (--) is the most critical input for data value formulation. In traditional data valuation scenarios, as discussed in Section 2. the utility function typically maps subsets of training data their performance where fs is model trained on subset S, and Dval is a validation set. In our graph inference data valuation context, the utility function should ideally map subsets of test neighbors to their collective contribution to the GNN's performance on target nodes. While this formulation provides a theoretically sound approach to graph inference data valuation, we face significant challenge: for test nodes, the absence of ground truth labels makes it impossible to directly measure accuracy and define an appropriate utility function.
validation set. For instance, US) = Ace(fs. Dva)).
4 THAPLEY-GUIDER UTILITY LEARNING (SGUL)
As shown in the prior section, the critical challenge in solving the graph inference data valuation problem lies obtaining an appropriate utility function without testing labels. To address this issue, propose approach to learn the utility function that effectively value test node neighbors.
4.1 UTILITY LEARNING IN DATA VALUATION
Despite the crucial role of utility functions in data valuation, as introduced in Section accessing these functions can often be costly or even impossible. For instance, the utility function we previ- ously discussed for training data valuation requires model retraining, which can be computationally expensive for large datasets. To address this challenge, utility learning methods have been introduced.
Utility learning aims to approximate the true utility function in a data-driven way. The general formulation of utility learning can be expressed as: Ú(S) = h(g(S)) where S is subset of data points. 9(-) is a feature extractor that captures relevant characteristics of the subset, and h(.) is learnable function that maps these characteristics to an estimated utility value. This approach differs from the original utility function by avoiding direct model retraining for each subset, instead learning to predict utility based on subset features. To train this approximation function, we construct a dataset of utility samples. Each sample consists of subset of data points and its corresponding value, obtained by evaluating the original utility function on a limited number of subsets.
utility
A notable instance of utility learning is the approach for training data valuation proposed by Wang ct al. 22221) This method efficiently estimates model performance on various subsets of the training data without repeated model retraining. represents subsets as binary vectors g(S), where each element corresponds to a specific data point in the training set, indicating its presence or absence. The method uses regression model Ürran approximate the ground truth utility function U 2D + R, where USS) = Aco D. Here, Js denotes model trained on the subset S C Dir, and Deal is the validation set. The regression model is trained difference between predicted and true utility values.
set of utility samples to minimize the
While this approach is effective for training data, it faces significant challenges when applied to graph inference data valuation: 1. Player Dependence: The input of Ünain using player-specific dummy variables, is tied a specific set of players (data points) and cannot be directly transferred to new player sets games. In the context of graph inference data valuation, this limitation becomes
4

---

Published as a conference paper at ICLR 2025
particularly problematic. While we have access to the labels of the validation graph Gvat, allowing us to compute the validation accuracy for different subsets of neighbor nodes on labeled validation nodes, the utility function learned on S C vaa E Gval cannot be directly applied to test nodes in GTe. This is because the test nodes represent a new set of players from (V;),, which were not present during the utility function learning process. 2. Indirect optimization: As discussed in Section [. the utility function is a crucial imput for data valuation solutions. Following this logic, current utility learning approaches employ a two-stage process: learning the utility function with sampled training subsets and corresponding validation accuracy, then estimating Shapley values with the fixed learned utility. This indirect method has two main drawbacks: (a) requires handling computationally expensive accuracy-level data, and (b) optimizing for accuracy prediction doesn't t necessarily lead to optimal Shapley value estimation.
val)
4.2 SHUDLEY-GUIDED UTILITY LEARNING
To address the challenges of player dependence and indirect optimization in graph inference data valuation, we propose Shapley-Guie Guided Transfcrable Utility Learning (SGUL). This novel approach focuses on two key aspects: (1) Transferable Feature Extraction: We introduce method that transforms player-dependent inputs into transferable, performance-rekkee reeaatte features. These features capture both graph structure and model behavior without relying test labels, enabling our utility learning model to generalize across different player sets and graphs. (2) Shapley-guided Optimization: We develop method that enables direct optimization of Shapley values, addressing the limitations of indirect optimization approaches.
4.2.1 TRANSFERABLE FEATURE EXTRACTION
As mentioned Section 4.1 traditional utility learning approaches often use player-specific binary vectors as input (Wang et al. 2021). While effective for training data, this method faces limitations when applicd to graph inference data valuation, particularly due to its inability to transfer to new player sets. To overcome the limitations of traditional utility learning approaches, we propose a novel feature extraction method that transforms player-depente related features. This approach builds upon the general utility learning formulation introduced in Equation (4.1). focusing on designing a transferable feature extractor gS)). Specifically, our proposed g(S) aims capture both structural and model-specific characteristies of the graph data. The input S is a set of neighboring nodes of target test nodes. As discussed in Section 2.2, we also employ a permutation sampling process for estimating Structure-Awar Shapley value. During this process, we incrementally add neighboring nodes to target test nodes following permissible permutations. This generates a series of test subgraphs Grb = (Vsub: Esab; sab)) each including the added neighhoring nodes and target test nodes. The function g(-) maps the current neighbor node set $ E Vsab to d-dimensional feature vector x E IRd, which encapsulates the characteristics of the subgraph induced by S as derived from the permutation. These features serve as proxies for model accuracy, capturing both graph structure and GNN behavior without relying on true labels.
inputs into transferable, performance-
Our feature vector x comprises two main categories: data-specific and model-specific features. Data-specific features capture graph structure and test node relationships to the training set, including edge cosine similarity, representation distance, and classwise representation distance. Model-specific features assess prediction confidence and uncertainty using the GNN model's output. These include maximum predicted confidence, target class confidence, propagated confidence measures, negative entropy, and confidence gap. By combining these features, we create a comprehensive representation of GNN performance on test subgraphs without relying on true labels. This approach allows to estimate the utility function effectively, even in the absence of ground truth information for test nodes. detailed description and mathematical formulation of each feature is provided in Appendix [
4.2.2 SGUL AND ITS LEARNING PROCESS
With our transferable feature extraction approach, we adapt traditional utility learning methods to create an sccuracy-oriented variant of our method. Following (Wang et al. 2021), we can apply these features directly in standard regression framework. This base model, termed SGUL-Accuracy, serves as an important comparison point for our proposed Shapley-guided method in Section 4.2.3 For detailed description of AGUL.-Accura training process, please refer Appendix B
5

---

Published as a conference paper at ICLR 2025
4.2.3 SHAPLEY-GUDDE UTILITY LEARNING (SGUL)
Having established our transferable utility learning framework and selected features, we now address the challenge of efficiently optimizing our utility function. Traditional accuracy-based approaches we seen in Section 4.1 employ a two-stage optimization process: first learning a utility function to predict model accuracy. then using this function to estimate Shapley values. However, this indirect accuracy-basee method has significant limitations. It is computationally expensive due to the large amount of accuracy-level data required, especially for large-scale graphs. More importantly, the optimization process in these accuracy-oriente methods is misaligned with the ultimate goal of data valuation. While the first stage focuses accurately predicting model accuracy, it doesn't 't directly minimize the difference between predicted Shapley values (derived from the learned utility function) and true Shapley values (calculated using actual accuracy). Our aim is to develop a method that directly optimizes for accurate Shapley value prediction, ensuring that the learned utility function could produce Shapley values that closely match those derived from true accuracy measurements.
Through theoretical analysis of the Shapley value definition, we discover a key insight: the Shapley value calculation is deterministic linear transformation of the utility function. This insight is formalized in the following theorem:
Theorem 1 (Shapley Value Decomposition). Given a linear utility function U(S) = w x(S). where E Rdd is a parameter vector and x(S) E Red is feature vector representing subset S, the Shapley value of player i with respect to U can be expressed as a linear combination of Feature Shapley Values:
([(U)=
(2)
where ub; = (.):(U)),,.U))). Tx((S) the utility function considering only the k-th feature.
is the vector of Feature Shapley Values, and Us(S)
The proof of this theorem is provided in Appendix C This theorem establishes direct link be- tween learnable parameters and fitted Shapley values: (T) w uh,, where (U) is the fit- ted Shapley value for i, w is our learnable parameter vector, and Φb, is the Feature Shapley vec- tor for i. Unlike previous decoupled accuracy- oriented optimization that solve (Ū) subject to (S)- arg min (S), (S)) (C is the loss), our approach directly optimizes the fitted Shapley values from learned utility function with the help of this theorem.
Building on this, we propose Shapley-Guided Transferable Utility Learning (SGUL), which integrates our transferable utility learning framework with a Shapley- -uideed optimization method. To learn the optimal parameter vector w, we formulate the following optimization problem:
min Σ (di(U)) w Tob,) A/|w|11
Here, Vai represents the set of labeled validation nodes, and (-)-) denotes the set of neighbors for given node set. The regularization parameter controls the trade-off between fitting the data and model complexity. This optimization problem is designed to find the optimal weight vector that quantifies the importance of each feature in the utility function. The input features are the Feature Shapley Values vb for each neighbor i, computed a preprocessing step. The target variable the true Shapley value (U)), which we can compute using the known accuracy on the validation set.
By solving this optimization problem, we obtain the optimal parameter vector w* that minimizes the difference between predicted and true Shapley values across all validation nodes and their neighbors. This direct optimization approach contrasts with traditional methods that focus on predicting accuracy rather than Shapley values. The inclusion of L, regularization (I[w]]]) in the objective function promotes sparsity in the learned weights, effectively identifying the most relevant features for Shapley value estimation and helping prevent overfitting. Importantly, the learned coefficients are interpretable, as our proposed features are theoretically positively correlated with accuracy. To ensure this interpretability, we constrain the parameters to be non-negative during the learning process. Once we have obtained the optimal parameter vector w", we can apply SGUL to estimate Shapley values proposed methods with different optimization
for neighbors of test nodes. When comparing protocols, we refer to the one optimized using our Shapley-guie -guided method as SGUL-Shapley, which differs from AGOI.AAccuracy optimized for accuracy as mentioned in Subsection 4.2.2

---

Published as a conference paper at ICLR 2025
5
RELATED WORK
Data Valuation Methods. Data valuation approaches based on cooperative game theory, including Data Shapley (Ghorbani & Zoul 2019) and its variants (Kwon & Zou 2021 Wang & Jia 2023). have established effective frameworks for quantifying individual data contributions. Recent innovations include dearning-agnostic frameworks (Just et al., 2023) and training-free frreeng-g-erreeee methods (Nohyun et al.) 2022). For graph-specific valuation, Winter value- methods (Chi et al. (022a) and task-agnostic frameworks (Falahati & Amiri (2244) address the unique challenges of interconnected data. Data utility learning (Wang et al. (021)) enhances valuation efficiency by predicting model performance on data subsets without repeated training, improving methods like Shapley value calculations.
Graph Neural Networks. Graph Neural Networks (GNNs) have revolutionized graph-structure data analysis since the introduction of spectral convolutions (Bruna al., 2013). with architectures like Graph Convolutional Networks (GCN) (Kipf & Welling (016)) and attention based variants (Veličković al., (017) gaining wide adoption. Central GNNs' success the message-passinn mechanism (Xu et al. 2018), enabling effective information propagation across the graph. While traditionally viewed as crucial for both training and inference, recent research highlights its particular importance during testing. The introduction of PMLPs (Yang al. 2023), which are identical to standard MLPs in training but adopt GNN's architecture with message passing in testing, reveals the critical role of testing-time time structure in graph-based based models' performance.
Model Evaluation Without Labels. Several approaches have been developed for model evaluation without test labels. Label-free model evaluation methods (see Appendix (D.4) estimate model accuracy through confidence scores and distribution metrics. ATC (Garg et al.] 2022) learns confidence thresholds and DoC (Guillory al. (02II) measures confidence shifts between validation and test sets. These methods have been extended to graph domain through GNNEvaluator (Zheng et al. 2024b), which uses discrepancy attributes to train GCN regressor for accuracy prediction. However, these methods focus on single-accurayy estimation rather than data value assessment. Recently, retraining- based approaches (see Appendix (.5) have emerged as an alternative strategy. Projection Norm (Yu et al., 2022) predicts performance by analyzing parameter changes after pseudo-label retraining, which has been adapted to graphs through LEBED (Zheng et al., 2024a). However, their computational demands make them impractical for evaluating multiple subgraph configurations required in our setting. While test-time adaptation methods (see Appendix (.6) such as GTRANS (Jin et al., 2022b) and IGT3 (Pi et al.) also operate unlabeled test data, they focus on the one-time performance maximization through graph transformation or parameter adaptation. For the graph- inference data valuation problem requiring evaluation across numerous subgraph configurations, only non-retraining label-free model evaluation methods serve as suitable surrogate utility functions, as they enable efficient prediction across multiple subgraphs.
For a more detailed discussion on related work, please refer to Appendix D
EXPERIMENTS
6.1 DATASETS AND EXPERIMENTAL SETUP
We evaluated our proposed SGJL framework seven diverse real-world graph datasets, covering both homophily and heterophily scenarios. Our experiments focus primarily on the inductive node classification task, with additional evaluations in the transductive setting. We employed different fixed GNN models for each setting to highlight the importance of testing structures. For detailed description of the datasets and experimental setup, please refer to Appendix B
6.2 EVALUATION PROCESS AND METRICS
To evaluate proposed SGUL framework, we design comprehensive assessment protocol con- sisting of utility learning and data valuation phases. During utility learning, we follow the process detailed in Algorithm[]] which involves generating permutations on the validation graph to learn our utility function. This standardized process is applied identically across all methods to ensure fair comparison. In the data valuation phase, we apply the learned utility functions to the test graph Gre to
7

---

Published as a conference paper at ICLR 2025
predict accuracies for target nodes Vg These predicted accuracies serve as utility function outputs (-) for calculating Shapley values following Algorithm 2
To assess the quality of data values produced by SGUL, we employ a node dropping experiments that targets high-valus nodes in the graph. This experiment is one of the most common and widely used
evaluation methods in data valuation research (Ghorbani & Zou 2019 Jiang al. 2023 Kwon & Zou 2023
Chi et al. 2024a). By sequentially removing nodes ranked according to their assessed values, can observe node dropping performance curve, which visually represents how the model's performance degrades as important nodes are removed. A good data valuation method should result curve that shows rapid and sharp decline in model performance. This corresponds identifying a crucial data subset, whose removal would significantly affect performance. Moreover, the decrease in performance caused by our method should not only be substantial but also persistent throughout the node-dropping process, ensuring that the importance identification is highly consistent (Ghorbani & Zou 2019 Jiang et al., 2023 Chi et al.) 2024a). To quantify the effectiveness of valuation method, we use the Area Under the Curve (AUC) metric of these node dropping performance curves. The AUC provides a single numerical value that captures the overall behavior of the node dropping process, reflecting both the initial rapid decline and the sustained performance drop. A lower AUC indicates a better valuation method, as it represents a more rapid and sustained decline in model accuracy when high-value nodes are removed. For detailed implementation of this evaluation protocol, please refer to Algorithm
6.3 BASELINES
To evaluate the effectiveness of our proposed SGUL framework, we compare it with several alternative utility learning methods. All these baselines aim to approximate the true utility function for graph inference data valuation, but differ in their specific techniques. The baselines we consider are: i. Average Thresholded Confidence (ATC): ATC (Garg et al. 2022) estimates accuracy by learning threshold the model's confidence scores. We implement two variants: ATC-MC (Maximum Confidence) and ATC-NE (Negative Entropy). ii Difference of Confidence (DoC): DoC (Guillory) al.) 2021) measures the difference in average confidence between the validation and test to predict accuracy change. iii. GNNEvaluator: GNNEvaluator (Zheng et al. (024b) is a novel method designed assess GNN performance on unseen graphs without labels. iv. Natural Confidence- basclines:
(a) Maximum Confidence: This uses the highest confidence score across all nodes and classes in the subgraph. (b) Class Confidence: This calculates the average confidence score of the predicted class for each test node, using the full test graph as input. We ensure a fair comparison by using the same overall framework for all methods, including identical sampling procedures for validation and test permutations. For complete description of those methods and corresponding training process, please see Appendix D.3 and Appendix respectivvel.
Based Baselines: We also include two straightforward confidence-baste
6.4
MAIN RESULTS AND ANALYSIS
To evaluate the effectiveness of our proposed SGUL framework, we conducted comprehensive experiments on various graph datasets using both SGC and GCN models in the inductive and Transductive setting. Our analysis focuses on two key aspects: the detailed behavior of node removal across different datasets and the overall performance of SCUL compared to baselines.
6.4.1 INDUCTIVE NODE REMOVAL. ANALYSIS
To provide a nuanced understanding of how different methods perform as nodes are progressively removed, we present accuracy curves for node dropping experiments. Figures I and 2 show these curves for SGC and GCN models, respectively, across various datasets. Figure illustrates the accuracy curves for node dropping experiments using SGC models across various datasets. These results reveal two key characteristics of our SGUL method. Firstly, SGUL consistently demonstrates a steeper initial drop in accuracy when removing the first few nodes, particularly evident in datasets like Cora and Citeseer. This rapid initial decline indicates SCUL's 's superior ability to identify the most critical nodes in the graph structure. Secondly, as more nodes are removed, SGUL maintains a more stable accuracy curve compared to other methods. This long-term stability is especially pronounced in larger datasets such as CS and Physics, suggesting more robust and consistent
8

---

Published as a conference paper at ICLR 2025
AC
ATC
DNC
Closs Cantacenee
SUBL
Clooset
0.50
Popoing Woschmmer
Pryplca
Noopre Number
Aroutnreingg Driperts Node Numier Bateneanrgy
0.75
0.750
0.72
0.55
0.513
7000
2000 EEOR
Drigiin Mose Kumber
NJ
Orvepinn Mode Numderr
Drigeing Nece Marber
Figure I: Accuracy curves for node dropping experiments using the SGC model on various datascts in the inductive setting. Our proposed SGUL method consistently maintains higher accuracy as nodes are removed, indicating its effectiveness in identifying important nodes. Note that GNNEvaluator is shown for the larger datasets Out Memory (OOM) errors.
ranking of node importance throughout the removal process. The performance of SGUL varies across datasets, showcasing its adaptability different graph structures. For instance, in the Cora dataset, SCUL exhibits clear advantage throughout the entire node removal process. In the Amazon-rating, dataset, which presents a more challenging heterophily scenario, SGUL consistently outperforms other methods, particularly in the latter stages of node removal. Similar performance patterns are observed when using GCN models, demonstrating that SGUL's effectiveness not limited to specific GNN architecture. For detailed results of the GCN experiments, please refer to Appendix F Additionally, to demonstrate scalability on much larger graphs, we conducted experiments on the ogbn-arxiv dataset, with results showing consistent improvements over baselines (see Appendix
6.4.2 TRANSDUCTIVE NODE REMOVAL ANALYSIS
To further validate the effectiveness of our SGUL framework, we extended our evaluation to the transductive setting using the Cora, Citeseer, and Pubmed datasets. This setting allows us to assess how our method performs when the entire graph structure known during both training and inference. Our results show that SGUL consistently maintains higher accuracy as nodes are removed across all datasets for both SGC and GCN models. This performance is particularly notable the Pubmed dataset, where SGUL shows significant advantage over other methods throughout the node removal process. For detailed analysis of the transductive setting experiments, including accuracy curves for node dropping experiments and AUC results, please refer to Appendix G
6.5 ABLATION STUDIES
To further validate the effectiveness of proposed Shapley-guich approach and provide deeper insights into its performance, we conducted a series ablation studies. These studies aim to compare Shapley-guides method SUGUL-Shaples with accuracy-based optimization approach AGGUL-Accurase across different aspects performance and efficiency.
6.5.1 IN-SAMPLE ERROR COMPARISON SHAPLEY AND ACCURACY OPTIMIZATION
To empirically validate our theoretical arguments from Section 4.2.3 we compared the perfor- mance of Shapley-guided optimization (SGUL-Shapley) against accuracy- optimization (SGUI-Accuracy). We conducted in-sample Mean Squared Error (MSE) comparisons across various datasets in the inductive setting with the SGC model. Our results show that SGUL- Shapley consistently achieves lower MSE across all datasets, with statistically significant differences 0.05). These findings provide strong empirical support for our theoretical analysis, demonstrating that directly optimizing for Shapley values leads to more accurate estimation of data value compared to the accuracy-based approach. For a detailed description of the experimental setup and full results, please refer Appendix

---

Published as a conference paper at ICLR 2025
6.5.2 DROPPING NODE COMPARISON OF OPTIMIZATION OBJECTIVES
We conducted an ablation study comparing Shapley value optimization (SCUL-Shapley) and aceuracy-based optimization (SGUL-Accurac))
node dropping experiments. Our results show that SGUI--Shap ey generally outperforms SGUT.- SGUI.-Accuracy across most datasets and models, achieving better results in 10 out of 14 dataset-model combinations. The improvement is particularly noticeable for larger and more complex datasets such CS, Physics, and Amazon-rating These findings demonstrate that directly optimizing for Shapley values leads to more accurate and robust inference data valuation. For detailed experimental setup and full results, please refer to Appendix
6.5.3 EFFICIENCY ANALYSIS OF SHAPLEY AND ACCURACY OPTIMIZATION
To complement our effectiveness analysis, we also evaluated the computational efficiency of Shapley value optimization (SGUI-Shapless compared to accuracy-based optimization (SUUL-Acuuracy) This analysis helps validate the practical applicability of our method, es- pecially for large-scale graph applications. We recorded the fitting time and memory usage for both methods under the OLS setting deseribed in the In-Sample Error Comparison. The implementation used Py Torch with learning rate of 0.001 for both methods. We ran each fitting process 10 times and averaged the results, with each run consisting of 1000 epochs. Table T summarizes our findings:
Setting
Dataset
Shapley Optimization
Accuracy Optimization
Time
Memory (MB)
Time (s)
Memory (MB)
Cora
0.63
16.28
0.66
29.58
Citeseer
0.64
16.28
1.54
28.59
Pubmed
0,56
16,49
0,67
87.60
Inductive
CS
0.52
16.53
0.50
44.19
Physics
0.44
16.71
0.55
39.05
Amazon-ratings
0.64
16.59
0.67
115.62
Roman-empire
0.53
16.37
0.65
50.25
Cora
0.59
16.35
0.75
65.77
Transductive
Citeseer
0.51
16.35
0.59
61.28
Pubmed
0.53
16.81
0.67
72.22
Table 1: Comparison of training time and peak memory usage between Shapley-guided (SGUI.Shapley) accuracy-hase (SGUL, Accuracy))))) optimization approaches using the SGC model.
The results demonstrate that SGUL-Shapley consistently outperforms SGUL-Accuracy in terms of computational efficiency. SCUL-Shapley achieves faster training times for most datasets, with notable improvements for larger datasets like Citeseer and Pubmed. More significantly, SGUL-Shaph ey shows substantial reduction in memory usage across all datasets, often using less than half the memory required by SGUL.AAcuuracy This efficiency advantage particularly pronounced for larger datasets such Amazon-ratings, where SGUL SSUL-Sh uses only about 14% of the memory consumed by SGUL-Accuracy.
These findings indicate that SGUL- Shapley only provides more accurate node importance estimations but also offers significant computational benefits. The reduced memory footprint and faster training times make SCUI-Shapley particularly suitable for large-scale graph applications where resource efficiency is crucial. This combination of effectiveness and efficiency underscores the practical value of our Shapley-guided approach in real-world graph inference data valuation tasks.
7 CONCLUSION
This paper introduces Shapley-Guided Utility Learning (SGUL), a pioneering framework for valuing graph inference data without test labels. SGUL uniquely integrates transferable feature extraction with Shapley-guider optimization, addressing the challenges of generalization to unseen structures and computational efficiency in graph data valuation. Our comprehensive experiments across diverse datasets consistently demonstrate SGUL's 's superiority over existing methods in both inductive and transductive settings.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
The research is supported by the National Science Foundation (NSF) under grant numbers NSF2406647 and NSF-2406648.
REFERENCES
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V Chawla. Graph barlow twins: A self-supervised representation learning framework for graphs. Knowledge-Baud Based Systems, 256: 2022.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint 13/ 2013.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint arXiv:/705.000
2017.
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 666,4665222 2024.
Hongliang Chi, Wei Jin, Charu Aggarwal, and Yao Ma. peccedence-constranee winter value for effective graph data valuation. arXiv preprint arXiv:2402.0/943, 2024a.
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, 2024b.
Leandro DalleMule and Thomas H Davenport. What's your data strategy. Hurvard business review, 95(3):112-122 2017.
Ali Falahati and Mohammad Mohammadi Amiri. Disentangled structural and featural representation for task-agnostic graph valuation. arXiv preprint DrXiv:2408.12655 2024.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In WWW, 2019a.
Wenqi Fan, Yao Ma, Dawei Yin, Jianping Wang, Jiliang Tang, and Qing Li. Deep social collaborative filtering. In Proceedings of the 13th ACM RecSys, 2019b.
Dominik Fuchsgruber, Tom Wollschläger, Bertrand Charpentier, Antonio Oroz, and Stephan Günne- mann. Uncertainty for active learning graphs. arXiv preprint 4rX1v:2405.01662, 2024.
Saurabh Garg, Sivaraman Balakrishnan, Zachary C Lipton, Behnam Neyshabur, and Hanie Sedghi. Leveraging unlabeled data to predict out-of-distribution performance. arXiv preprint arXiv:2201.04234. 2022.
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.
Dmitri Goldenberg. Social network analysis: From graph theory to applications with python. arXiv preprint a0Xiv:2102. 10014, 2021.
Shengbo Gong, Mohammad Hashemi, Juntong Ni, Carl Yang, and Wei Jin. Scalable graph condensa- tion with evolving capabilities. arXiv preprint 1rX.:22502.17644 2025.
Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt. Predicting with confidence on unseen distributions. In Proceedings of the IEEE/CVF international conference computer vision, pp. 1 1134 144, 2021.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.

---

Published as a conference paper at ICLR 2025
Shengding Hu, Zheng Xiong, Meng Qu, Xingdi Yuan, Alexandeer Côté, Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. Advances in Neural Information Processing Systems, 33:10174-10185 2020a.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 53:22118-22111 2020b.
Kanchan Jha, Sripama Saha, and Hiteshi Singh. Prediction of protein-protein interaction using graph neural networks. Scientific Reports, 12(1), 2022.
Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based the shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1167-1176. PMLR, 2019.
Kevin Jiang, Weixin Liang, James Zou, and Yongchan Kwon. Opendataval: a unified benchmark for data valuation. Advances in Neural Information Processing Systems, 36, 2023.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliiag Tang, and Neil Shah. Graph condensation for graph neural networks. arXiv preprint 100.05500, 2021.
Wei Jin, Xianfeng Tang, Haoming Jiang, Zheng Li, Danqing Zhang, Jiliang Tang, and Bing Yin. Condensing graphs via one-step gradient matching. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 720-730, 2022a.
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. arXiv preprint arX1v:2210.03561, 2022b.
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 arXiv:2305.00054 2023.
Jian Kang, Qinghai Zhou, and Hanghang Tong. Jurygen: quantifying jackknife uncertainty on graph convolutional networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 742-752, 2022.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks.
arXiv preprini 1xXXvv:609.02220 2016
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:18100005997, 2018.
Yongchan Kwon and James Zou. Beta shapley: unified and noise-reduced data valuation framework for machine learning. arXiv preprint arXiv:2/ 10.4499 2021.
Yongchan Kwon and James Zou. Data-oob: Out-of-bag estimate as a simple and efficient data value. In International Conference on Machine Learning, pp. 18 18135-18152. PMLR, 2023.
Ting Wei Li, Qiaozhu Mei, and Jiaqi Ma. A metadata-drrien approach to understand graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Zhen Li, Mingjian Jiang, Shuang Wang, and Shugang Zhang. Deep learning methods for molecular 2022.
representation and property prediction. Drug Discovery Today,
Juncheng Liu, Yiwei Wang, Bryan Hooi, Renchi Yang, and Xiaokui Xiao. Lscale: latent space clustering-based active learning for node classification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 55-70. Springer, 2022.
Yujia Liu, Kang Zeng, Haiyang Wang, Xin Song, and Bin Zhou. Content matters: A gnn-based model combined with text semantics for social network cascade prediction. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pp. 728-740. Springer, 2021.
12

---

Published as a conference paper at ICLR 2025
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34:1048- 1108--06,,40 2021.
Qian Ma. Hongliang Chi, Hengrui Zhang, Kay Liu, Zhiwei Zhang, Lu Cheng, Suhang Wang, Philip S Yu, and Yao Ma. Overcoming pitfalls in graph contrastive learning evaluation: Toward comprehensive benchmarks. arXiv preprint arXiv:2402. 15680, 2024.
Ki Nohyun, Hoyong Choi, and Hye Won Chung. Data valuation without training of a 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 4604448664688,00688 2020.
Li Pi, Jiaxing Li, Lei Song, Guanyu Yang. Yang Chen, and Youyong Kong. Test-time training with invariant graph learning for out-of-distribution generalization. Available at SSRN 4886269.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint arXiv:2302.116400 2023.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al magazine, 29(3):93-92) 2008
Murat Sensoy, Lance Kaplan, and Melih Kandemir. Evidential deep learning to quantify classification uncertainty. Advances in neural information processing systems, 31, 2018.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05860 2018.
Rachael Hwee Ling Sim, Xinyi Xu, and Bryan Kian Hsiang Low. Data valuation in machine 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 202/ Workshop on GTRL, 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: 193:116463, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua 2017.
Bengio. Graph attention networks. arXiv preprint
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
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.
Luzhi Wang, Dongxiao He, He Zhang, Yixin Liu, Wenjie Wang, Shirui Pan, Di Jin, and Tat-Seng Chua. Goodat: Towards test-time graph out-of-distribution detection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 15537-15545, 2024.
Tianhao Wang, Yu Yang, and Ruoxi Jia. Improving cooperative game theory-based data valuation via data utility learning. arXiv preprint urXiv:2107.0633) 2021.
Yang Wang, Jin Zheng. Yuqi Du, Cheng Huang, and Ping Li. Traffic-ggnn: predicting traffic flow via attentional spatiall-emporal gated graph neural networks. IEEE Transactions on Intelligent Transportation Systems, 18(13) 2022.
Felix Wu. Amauri Souza, Tianyi Zhang, Christopher Fifty. Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In /CML. PMLR, 2019.
13

---

Published as a conference paper at ICLR 2025
Zhenxing Wu, Jike Wang, Hongyan Du, Dejun Jiang, Yu Kang, Dan Li, Peichen Pan, Yafeng Deng, Dongsheng Cao, Chang- Yu Hsich, et al. Chemistry-intuittyy explanation of graph neural networks for molecular property prediction with substructure masking, Nature Communications, 14(1):2585, 2023.
Jun Xia, Lirong Wu, Ge Wang. and Stan Z. Li. Progel: contrastive learning. In International conference on machine learning. PMLR, 2022.
Rethinking hard negative mining in graph
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.0060 2018.
Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates. Graphsail: Graph structure aware incremental learning for recommender systems, In Proceedings of the 29th ACM International CIKM, 2020.
Chenxiao Yang, Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging GNNs and MLPs. In The Eleventh International Confer- ence on Learning Representations, 2023. URL httpp::///pp/eeeeee http:s:://penreveww.eeoe net/ wttp://wwwwweeeeootmmmmmm.. forum?id
dgrNWWom2L6.
Yaodong Yu, Zitong Yang, Alexander Wei, Yi Ma, and Jacob Steinhardt. Predicting out-of-distribution error with the projection norm. In International Conference on Machine Learning, pp. 25721- 25746. PMLR, 2022.
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 I international conference on management of data, pp. 2366-2374, 2021a.
Wentao Zhang, Yexin Wang, Zhenbang You, Meng Cao, Ping Huang, Jiulong Shan, Zhi Yang, and Bin Cui. Rim: Reliable influence-based active learning on graphs. Advances neural information processing systems, 012777777779999 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: 102.00211...00000001 2021c.
Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, and Irwin King. Costa: covariance-preservie feature augmentation for graph contrastive learning. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 2524 2534, 2022.
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 on Artificial Intelligence, volume 37, pp. 1289-11297, 2023.
Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering. In Proc. IJCAI, pp. 3440, 2021.
Xin Zheng, Dongjin Song, Qingsong Wen, Bo Du, and Shirui Pan. Online gnn evaluation under test-time graph distribution shifts. arXiv preprint arXiv:2403.09953. 2024a.
Xin Zheng, Miao Zhang, Chunyang Chen, Soheila Molaei, Chuan Zhou, and Shirui Pan. Gnnevaluator: Evaluating gnn performance on unseen graphs without labels. Advances in Neural Information Processing Systems, 36, 2024b.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020a.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propaga- tion. 2002.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.041. 2020b.
14

---

Published as a conference paper at ICLR 2025
A SELECTED FEATURES FOR ACCURACY PREDICTION
When performing Graph Inference Data Valuation, we incrementally add neighboring nodes to the target test nodes following permissible permutations. This process generates a series of test subgraphs. Let Ssub (Vsub. Sub. Xuub) denote the current sub-test graph, which includes the added neighboring nodes and target test nodes. Our goal is to identify features that reflect the performance of the fixed GNN model Fsuh without relying model-specific features that correlate with GNN performance. These features are designed to capture both the structural properties of the graph and the behavior of the GNN model on the test nodes.
true labels. To this end, propose set of data-specific and
Data-specific features: Our data-specific features focus on graph homophily and distance measures:
1. Edge Cosine Similarity (5.): This feature measures the homophily level of the current subgraph. For graph neural networks, it recognized that performance is strongly correlated with the graph's 's homophily level, where connected nodes tend to share similar characteristics (Zuu al. 22200a Li al. 2024). A higher homophily level often leads better GNN performance.
8c
cos(x;, Xj)
Esuhi
(l.)
where x; and X, the feature vectors of nodes and j. respectively, and Esub is the set of edges the current subgraph. This measure accurately captures the average cosine similarity between connected nodes, reflecting the homophily of the subgraph structure.
2. Representation Distance (drep): This feature quantifies the overall dissimilarity between test nodes and the training set, which has been shown be related to GNN performance (Ma et al. 2021). A smaller feature distance typically indicates that the test nodes are more similar to the training data, which often correlates with better GNN performance these test nodes.
drep
Σ cos (hy, prann) VEV.
[VA
where h, is the aggregated feature vector of the target test node and hgain is the mean aggregated feature vector of training nodes.
3. Classwise Representation Distance (delass): This feature provides a more fine- mne-grained measure of the distance between test nodes and training data, by considering class-specific prototypes. It captures how well the test nodes align with the class representations learned from the training data.
delass
Σ min cos (h,, he) DE
[V
aEC'
where C is the set of classes, he is the mean aggregated feature vector of training nodes in class c, and Ve is the set of target test nodes. This feature complements the overall representation distance by providing class-specific information, which be particularly useful in multi-class classification tasks.
Model-specific features: Our model-specific features leverage the output of the fixed GNN model f(-) to compute confidence scores and uncertainty measures:
4. Maximum Predicted Confidence (Cmax): The confidence of model predictions has been shown to be strongly correlated with model accuracy (Guo et al.) 2017 Guillory et al.) 2021 Garg et al.) 2022). This feature captures the average maximum confidence score for target test nodes when the current subgraph is input the fixed GNN model.
1
Cmax
max (Sub))
[V
NEy
15

---

Published as a conference paper at ICLR 2025
5. Target Class Confidence (Curgat: To mitigate the impact of changing predictions add nodes to the test subgraph, we fix the predicted label for each node based on the full test graph. This feature represents the average confidence score of these fixed predicted classes for the target test nodes.
Σ Sg. (9sub) NEV.
Curret
[iel
where D. arg maX fy (Ite) is the predicted class for node using the full test graph GTe-
6. Propagated Maximum Confidence (Crup max): Label propagation (Zhu & Ghahramani 2002) has proven effective in graph- based classification tasks. We first predict distribution for each node in the current subgraph using only their features, then propagate these distributions over the graph structure.
Σ VEVI
max (9(um)) yEY
Gprop
Dil
where fy (Gubb) = (G Do. I = (Vsub. 0, sab)
sub) is the subgraph with empty edge set, (9 (ubb) is the initial prediction for node v using only its features, and LP(-) denotes the label propagation operation on Gsuh-
7. Propagated Target Confidence (arop_argee):: This feature captures the average confidence of the fixed predicted class after label propagation, using the same process in Propagated Maximum Confidence.
1
Σ (9 LEV.
Gprop_ Jarget
M
where Du is the predicted class for node using the full test graph, as defined earlier, and Jy. (Qma)) the propagated probability for class ÿn of node
8. Negative Entropy (Hosg): Recent research has shown that negative entropy effectively measures uncertainty in machine learning models and is highly correlated with accuracy (Sensoy et al. 2018 predictions.
Garg et al. 2022). Higher negative entropy indicates more certain
H
Σ "EV, NEY
Σ
(9sub) log fog.yyloooooo (9
[Vdl
9. Confidence Gap (Ac): This feature measures the average difference between the highest and second-highed confidence scores for the target test nodes. It can be viewed another uncertainty measure, where a larger confidence gap suggests more certain predictions and potentially higher accuracy.
Ac
1 MV
Σ VEV.
max (9sub) yEY
max
for (Asub)y)
VE
where G. arg max fy (Gub), is the predicted class for node
These model-specifie features, combined with the previously described data-specific features, provide a comprehensive representation of the GNN's performance on the sub-test graph G.ub without relying on true labels. By capturing various aspects model confidence and uncertainty, these features serve effective proxies for model accuracy in our utility learning framework.
B SGUL-ACCURACY AND BASELINE MODEL TRAINING PROCESS
Our proposed transferable feature extraction method SCUL-Accuracy addresses the challenge of lacking test labels by providing set of proxy features that capture both graph structure and model behavior. To implement this approach in the context of utility learning for graph inference data valuation, follow general procedure:
16

---

Published as a conference paper at ICLR 2025
1. Generate permutations: We create set of permutations the validation graph Ival. following the structure-aware Shapley value formulation (Equation (T)) Each permutation results in series of subgraphs neighboring nodes are incrementally added.
2. Extract features: For each subgraph, apply our feature extractor g(S) to obtain the transferable, performance-related features x Rd.
3. Obtain ground truth utilities: We imput these validation subgraphs into the fixed GNN model f()) to obtain ground truth accuracy scores. These scores serve as the target values for our utility learning method.
4. Learn utility function: Traditional approaches typically the feature-utility pairs ob- tained from steps 2 and 3 to train a model that minimizes the difference between predicted and true utility values (or accuracies). This is often formulated as regression problem:
min - ha()))))
where US) is the ground truth utility (accuracy) for subgraph S, g(S) is our feature extractor, and hg a learnable function parameterized by B.
This procedure allows us to create a dataset of feature-utility pairs, which can be used to learn utility function that generalizes to unseen test structures. It's worth noting that this general framework can accommodate various transferable feature extraction methods. While we have proposed a specific design for our feature extractor (SS), other approaches could potentially be integrated into this framework, as long as they produce transferable, performance-relate features x E Rd.
Interestingly, this training procedure can be identically applied to label-free model evaluation methods (Garg et af. 2022 Guillory et al.] 2021] Zheng et al.) 2024b) which serve as baselines our unlabeled data by leveraging various proxy metrics or transferable features. The key difference lies in the ultimate goal: while label-free model evaluation methods focus on estimating overall model performance, our approach extends this concept to the more granular task of valuing individual graph elements for inference.
experimental part. These methods aim assess model performance
C PROOF OF SHAPLEY VALUE DECOMPOSITION THEOREM
Here we provide the proof for the Shapley Value Decomposition Theorem stated in Section 4.2.3
Theorem 2 (Shapley Value Decomposition). Given linear utility function U(S) =w w T x(S), where E Rdd a parameter vector and x(S) E Rdd a feature vector representing subset S, the Shapley value of player i with respect to U can be expressed linear combination of Feature Shapley Values:
where bb; = (U)) (S) the utility function considering only the ke-th feature.
TT is the vector of Feature Shapley Values, and UL(S)
Proof. We begin by recalling the definition of the Shapley value for player i with respect to utility function U:
[S | 1)!
Σ
((S
n!
SCAVO
where N is the set of all players and n W. Given the linear utility function U(S) = w x(S). we can substitute this into the Shapley value definition:
17

---

Published as a conference paper at ICLR 2025
[S - 1)!
(.(0)=
E
[w X(SU (8)) w -xx(S)
n!.
SCNTE
[
|S| - 1)!
Σ
[x(SU (i}) x(S)
n2!
SENADI
[S
1S| - 1)!
w
Σ
(SSU(UU (8)) - x(S)
n!
SCMMO
Now, let's consider the k-th component of the feature vector x(S). which we denote as xy (S). We define a utility function USx(S) Iz (S) that considers only this k-th feature. The Shapley value for player with respect to Ug is:
S S - 1)!
n!! IZn (S (SU (i)) xx)(
SENVOR
Comparing this with the last line of our previous derivation, we can see that:
(0(U) = w T (U)( (U(U)) (((,)))...,;((UA)))) (Ua)) = w bb;
where 3b; = [dx (UZ)) (Ua)] is the vector of Feature Shapley Values.
This completes the proof of the Shapley Value Decomposition Theorem.
This theorem demonstrates that for a linear utility function, the Shapley value can be decomposed into linear combination of Feature Shapley Values derived from Appendix A This decomposition forms the theoretical foundation for our Shapley-Guided Generalizable Utility Learning (SGUL) method, allowing us efficiently learn utility function parameters by optimizing for Shapley values directly.
D EXTENDED RELATED WORK
D. DATA-EIFICIENT LEARNING GRAPHI
Data-efficien learning on graphs primarily uses two approaches to address limited labeled data. Graph self-supervised learning develops representations without labels, where contrastive learning methods like Deep Graph Infomax (Velickovic et al. (019) and GRACE (Zhu et al. 2020b) contrast different graph views, while non-contrastive methods such as BGRL (Thakoor et al. 2021 and Graph Barlow Twins (Bielak et al., 2022) achieve strong performance without negative samples. Recent works address sampling bias (Zhao et al. [021 Xia et al. 2022) and develop feature augmentation techniques Zhang al. (2022 2023). Chi & Ma (202)) enhance contrastive learning through node similarity while Ma al. (Ma al. 2024) establish comprehensive benchmarks for evaluation. Mean- while, graph active learning optimizes node selection for labeling, with methods like AGE (Cai et al.) 2017) combining multiple selection metrics, GPA (Hu et al. 2020a) using sequential decision-making and GRAIN (Zhang al. 2021cc/RIM (Zhang et al. 2b reformulating selection as influence max- imization. Advanced techniques include LSCALE (Liu et al. (022) exploiting labeled and unlabeled representations, ALG (Zhang et al., 2021a) considering both representativeness and informativeness. and GALclean (Chi et al. (024b) addressing active learning for graphs with noisy structures. Recent works have also explored uncertainty quantification on graphs, with JuryGCN (Kang et af. 2022) providing deterministic uncertainty estimates through jackknife confidence intervals and Inuhhsggubbe ctt al. (2024) establishing principled approaches to uncertainty sampling for active learning on graphs. Another promising direction is graph condensation, which aims to distill large graphs into smaller synthetic versions that preserve training performance. Jin et al. (202T) introduce this problem by matching GNN training trajectories through gradient matching, while their follow-up work (in ct al. 2022a) accelerates the process with one-step gradient matching. Recent advances by Gong
al. (Gog et al. 2025) address scalability challenges for evolving graph data through class-wise
18

---

Published as a conference paper at ICLR 2025
clustering on aggregated features, achieving significant speedups while maintaining comparable performance. These data-efficient approaches complement graph inference data valuation, extending efficiency principles from training to the test-time inference phase.
D.2 GRAPH TRAINING DATA VALUATION
While Data Shapley and subsequent methods (Ghorbani & Zou 2019 Kwon & Zou 2021 Wang &
Jia 2023) have been effective for i.i.d. data, they face significant challenger when applied to graph- structured data. A key challenge is capturing the hierarchical and dependent relationships among graph elements. In Graph Neural Networks (GNNs), a node's contribution to model performance is intricately linked to its position within the computation tree and its relationships with other nodes. Traditional Shapley value calculations, which treat all players (nodes) independently, fail to account for these crucial dependencies, potentially leading to inaccurate valuations.
To address these challenges, Chi et al. (2024a) proposed a more granular approach to graph data valuation. This approach considers individual nodes within the computation tree as the basic units for valuation, allowing for more nuanced assessment of each element's contribution to GNN perfor- mance. Building upon the Shapley value formulation, this method introduces two key constraints to the set of permutations II(D):
This constraint ensures that nodes within the same subtree of the computation graph are grouped together in the permutation. Formally, for node v in the computation tree and its descendants D (()), the constraint can be expressed as:
Level Constraint:
T [+] - +bill s (P()).. D(j
where T denotes the position node in permutation x. This preserves the hierarchical structure of the computational graph and prevents evaluation bias that could occur when players from the same group are placed at widely separated positions in the permutation.
This constraint guarantees that node appears in the permutation only after its ancestors. For a node and its ancestor set A(v), the constraint can formulated as:
Precedence Constraint:
π [a] < π Tu], Va E A(v)
This reflects the dependency structure GNNs, where node's contribution contingent on the presence of its ancestors in the computation tree.
These constraints allow for a more accurate valuation of graph data by respecting the inherent structure and dependencies within GNNs.
D.2.1 DISCUSSION ON THE DIFFERENCE BETWEEN PC- PC-WINTER AND SGUL
While PC-Winter pioneered the exploration of graph data valuation by introducing constraints to capture hierarchical dependencies, our work focuses specifically on the challenging scenario of test-time graph inference valuation, where ground truth labels are unavailable. Specifically, PC- Winter addresses training data valuation by defining hicrarchical elements within computation trees as the data valuation objects (players), applying both Level and Precedence Constraints capture structural dependencies. In contrast, our work (Section 4.2.3) focuses on quantifying the importance of neighbors for test nodes during inference time. We adopt the Precedence Constraint from PC- Winter while omitting the Level Constraint, as explained in Section 3.2] This design choice reflects distinct nature of test-time neighbor relationships, which lack the clear hierarchical groupings present in training data computation trees. The Precedence Constraint proves valuable in capturing the dependencies between nodes in the message- saassaggg process during inference.
A key technical distinction lies in approach to utility function design. While PC-Winter leverages validation accuracy as their utility measure, the absence of test labels our setting necessitates a novel solution. As detailed in Section we introduce transferable data-specific and model-specific features that can effectively approximate model performance without ground truth labels. This innovation enables the evaluation of neighbor importance during inference time.
Our work complements PC- Winter by extending graph data valuation to test-time scenarios, partic- ularly crucial for applications like real-time recommendation systems and dynamic graphs where
19

---

Published as a conference paper at ICLR 2025
Table 2: Comparison between PC-Winter and our Structure-aware Shapley Value with SGUL
Aspect
PC-Winter
Structure-aware Shapley with SGUL
Valuation Target
Training graph elements
Test-time neighbors
Constraints Used
Level and Precedence Constraints Hierarchical dependencies
Precedence only No test labels
Primary Challenge
Utility Function
Validation accuracy
Learned test accuracy
test-time structure evaluation is essential. Table highhlights the key differences between our work and PC- Winte:::::
In experimental analysis, further demonstrate the effectiveness of our approach in identifying influential test-time graph structures. Through comprehensive node-dropping experiments (Section 6 we show that our method consistently outperforms baselines in terms of Area Under the Curve (AUC) scores and accuracy curve characteristics across various datasets and model architectures. These results validate the practical value of our test-time graph inference valuation framework, complementing the contributions of PC-Winter in the training data valuation setting.
D.3 LABEL FREE MODEL EVALUATION BASELINES
In this section, we provide detailed descriptions of the baselines used for comparison in our study, These baselines represent state-of-the-at methods for label-free model evaluation, which is crucial for assessing model performance on unseen data without access to ground truth labels. The baselines consider are:
D.3.1 AVERAGE THRESHOLDED CONFIDENCE (ATC)
ATC, introduced by Garg et al. (2022), estimates accuracy by learning threshold on the model's confidence scores. We implement two variants:
(a) ATC-MC (Maximum Confidence):
[ieu Σ
I max Imma CEc
ATC-MC
(n(Grest)ne m.c
This equation counts the fraction of test nodes where the maximum confidence exceeds threshold t. Here, fo (iees)) is the confidence score for class c on test node v, and is determined using the validation set.
(b) ATC-NE (Negative Entropy):
So(Grres) log (o(Grest) |
ATC-NE
Σ De
I
Σ CEC
D
Vini
This variant uses negative entropy of predicted probabilities as the confidence measure, counting nodes where it exceeds the threshold.
D.3.2 DIFFERENCE OF CONFIDENCE (DoC)
DoC, proposed by Guillory et al.
202 measures the difference in average confidence between the validation and test sets to predict accuracy change:
DoC = A.c(cf Gva) + 3 (ōre Eval)
where ōval Pwall Every max,ec f(V). and ēт - Enery maxesc f(V) are the average maximum confidences on validation and test sets respectively, Ace(f. aee(f.vvl) is the accuracy on the validation graph, and is learned through linear regression the validation set.
20

---

Published as a conference paper at ICLR 2025
D.3.3 GNNEVALUATOR
GNNEvaluator, introduced by Zheng et al. (2024b), is designed to assess GNN performance on unseen graphs without labels. It employs a two-stage approach:
constructs DiseGraph set, leveraging validation subgraphs from sample permutations meta- graphs. For each meta-graph it computes discrepancy attributes by comparing GNN embeddings and predictions between the meta-graph and original training graph.
2. A two-layer GCN regressor is trained on the DiscGraph set to estimate node classification accuracy, The regressor learns map the discrepancy attributes to expected model performance.
For inference, GNNEvaluator computes discrepancy attributes for the unseen test graph using the fixed pre-trained GNN, then applies the trained regressor estimate accuracy without requiring labels.
D.3.4 NATURAL CONFIDENCE- BBSEE BASELINES
We also include two straightforward confidence- based baselines:
(a) Maximum Confidence: This uses the highest confidence score across all nodes and classes in the subgraph.
(b) Class Confidence: This calculates the average confidence score of the predicted class for each test node, using the full test graph as input.
We ensure a fair comparison by using the same overall framework for all methods, including identical sampling procedures for validation and test permutations.
D.4 BASELINE METHODS AND THEIR DISTINCTIONS TO SGUL
Recent advances in label-free model evaluation have produced several notable approaches. Average Thresholded Confidence (ATC) (Garg al., [222]] estimates model accuracy by learning appropriate thresholds on confidence scores. The method operates by computing the fraction of examples where model confidence exceeds learned threshold, with variants utilizing either maximum confidence (ATC-MC) or negative entropy (ATC-NE) as the underlying metric. Difference of Confidence (DoC) Guillory et al., (202T) takes comparative approach, measuring the discrepancy in average confidence between validation and test sets to predict accuracy changes. This method leverages the observation that shifts in model confidence often correlate with performance degradation. GNNEvaluator (Zheng et al., 2024b) introduces a more sophisticated framework specifically designed for graph neural networks, employing two-stage approach that first constructs DiscGraph set to capture distribution discrepancies and then trains a GCN regressor to estimate node classification accuracy without requiring labels.
While these methods represent significant advances in label-free model evaluation area, they funda- mentally differ from our graph inference data valuation framework in both objectives and operational mechanisms. The primary distinction lies in the granularity and scope of evaluation. Traditional label-free methods focus on estimating overall model performance on a fixed test graph, essentially treating the evaluation analysis by evaluating numerous subgraph configurations to quantify each structural component contribution model performance. This decomposition- approach enables us to understand not just how well a model performs, but also which graph structures are crucial for that perfor- mance. The computational demands of our approach also create unique challenges while methods like GNNEvaluator work well for one-time evaluation, they become computationally prohibitive when applied the many subgraph permutations required for Shapley value computation, often encountering memory limitations on medium-sise datasets. Our SGUL framework addresses these challenges through specialized optimization techniques and efficient feature extraction methods that enable scalable evaluation across multiple subgraph configurations. Furthermore, the architecture of existing methods is not optimized for repeated utility assessment across permutations, as they were designed for single-pane pass evaluation rather than the iterative valuation process required for computing druccure-awarc Shapley values. Through our experimental validation, we demonstrate that SGUL not only provides more detailed structural insights but also achieves superior accuracy in estimating the
single-point estimation problem. In contrast, SGUL performs fine-grained
21

---

Published as a conference paper at ICLR 2025
importance of individual graph components, outperforming these adapted baseline methods in the specific context of graph inference data valuation.
D.5 RETRAINING-BASED LABEL-FREE MODEL EVALUATION METHODS
Notably, recent label-free model evaluation researches for predicting model test performance have explored retraining- bangg approaches, which offer novel perspectives but face limitations in our graph inference data valuation context. Projection Norm (Yu et al. (022) predicts dittr--distribution performance by analyzing model parameter changes after retraiming with pseudo-labels generated from test samples. The method demonstrates strong theoretical guarantees for linear models by measuring the distance between original and retrained model parameters as indicator of distribution shift. Simultaneously, LEBED (Zheng et al. (024a) approaches test-time graph distribution shifts by quantifying discrepancies in learning behaviors between training and test graphs through a GNN retraining strategy with parameter-free optimality criteria that capture both node prediction and structure reconstruction aspects.
While these methods present innovative solutions for general test accuracy prediction, they encounter fundamental constraints in our graph inference data valuation framework. The primary challenge stems from our need to evaluate [V(N(())) x [VV) different subgraphs for computing structure- aware Shapley values. Each subgraph configuration would demand separate retraining process under these approaches, rendering them computationally infeasible at scale. Moreover, methods like LEBED require access to the original training graph for comparative analysis an assumption that may not hold in practical deployment scenarios where training data access is restricted due to privacy concems. These inherent limitations motivate our adoption of more computationally efficient approaches that can evaluate subgraph utilities without model retraining, as detailed in Section D.3
D.6 TEST-TIME TRAINING AND AUGMENTATION METHODS
Recent works have explored various test-time adaptation techniques for graph neural networks to address distribution shifts and OOD generalization. These methods can be broadly categorized based on their mechanisms and objectives: GTRANS (Jin et al. 2022b) takes data-centric approach by performing test-time graph transformation through unsupervised feature and structure augmentation. While also focusing data adaptation, GTRANS aims to find single optimal modified test graph that maximizes model performance, rather than evaluating the importance of individual elements. This fundamentally differs from our objective of quantifying each node's 's marginal contribution through structure-aware Shapley values. GOODAT (Wang et al. 2024) addresses test-time graph OOD detection as a binary classification problem by determining whether subgraphs align with the training distribution. The method employs graph masker to compress informative subgraphs for distinguishing ID and OOD samples. However, GOODAT focuses solely on detecting OOD graphs without considering the contributions of individual nodes to model performance. IGT3 (Pi et al.) proposes a two-stage training paradigm that combines test-time training with invariant graph learning to improve OOD generalization. The method adapts model parameters through multi-level graph contrastive learning while preserving graph structure information. In contrast to our data-centric valuation framework, IGT3 modifies the model itself to adapt distribution shifts.
While these methods present innovative solutions for improving test-time performance and OOD generalization, they differ fundamentally from graph inference data valuation framework in both objectives and mechanisms. Our framework maintains fixed model parameters while systematically evaluating the contribution of individual nodes, enabling flexible value-based data selection for various downstream applications from performance maximization to denoising. This generality and composability of data values distinguish our approach from methods focused solely on improving overall model performance through data or model adaptation.
E DETAILED DATASETS AND EXPERIMENTAL SETUP
E DATASETS
To evaluate the effectiveness of our proposed Shapley-Guided Utility Learning (SGUL) framework. conducted extensive experiments seven diverse real-world graph datasets. These datasets
22

---

Published as a conference paper at ICLR 2025
include Cora, Citeseer, Pubmed (Sen et al. 2008), Coauthor CS,, Soauthoo-Physstie (Shchur et al. 2018). Roman-empire, and Amazon- (Platonov et al. 2023). Our dataset provides excellent coverage of both homophily and heterophily in graphs. The first four datasets are characterized by homophily, where connected nodes tend to share similar features or labels. In contrast, Roman-empire and Amazon-ratings exhibit heterophily, presenting more challenging scenario where connected nodes often have different characteristics.
E.2 EXPERIMENTAL SETUP
Our experiments primarily focus on the inductive node classification task, which more closely resembles real-world applications where models must generalize unseen graph structures (Hamilton сt al. 2017 Van Belle et al. 2022). In this setting. we partition each dataset into three distinct graph structures: Training Graph, Validation Graph, and Testing Graph.
To provide a comprehensive evaluation, we also extend our experiments to the transductive setting, where the entire graph structure known during training, but only a subset of training and validation nodes has labeled data. This allows us to compare the performance of our method across different learning paradigms.
To better highlight the importance of testing structures, we employ different fixed GNN models for inductive and transductive settings:
Inductive Setting:
We utilize Parameterized MLPs (PMLPs) (Yang et al. 2023 which train as standard MLPs but adopt GNN-like message passing during inference. This ap- proach emphasizes the crucial role of testing-time graph structures in model performance. During inference, PMIPPs employ either Simplified Graph Convolutions (SGCs) or Graph Convolutional Networks (GCNs) (Kipf & Welling 2016) (Wu al., 2019) for message passing, allowing us to evaluate the impact of different aggregation schemes on our graph inference data valuation task.
Transductive Setting:
We use full Graph Neural Network (GNN) models, specifically GCNs and SGCs, leveraging the complete graph structure available during both training and inference. This setting allows us assess method's performance when the entire graph topology is known and utilized throughout the learning process.
F GCN MODEL INDUCTIVE SETTING RESULTS
In addition to the SGC model results presented in the main text, we also conducted experiments using Graph Convolutional Network (GCN) models. Figure shows the accuracy curves for node dropping experiments using GCN models across various datasets. The results for GCN models closely mirror those observed for SGC models. SGUL consistently outperforms other methods across various datasets, demonstrating both steeper initial accuracy drop and better long-tew stability. This consistency across different GNN architectures further validates the robustness and wide applicability of our Chapley-Guides Utility Learning framework in graph inference data valuation tasks.
G TRANSDUCTIVE SETTING RESULT ANALYSIS
To provide a comprehensive evaluation of our SGUL framework, we extended our experiments to the transductive setting using the Cora, Citeseer, and Pubmed datasets. In this setting, the entire graph structure known during both training and inference, allowing us to assess our method's performance when the full graph topology is utilized throughout the learning process.
G.1 EXPERIMENTAL SETUP
For the transductive setting. we used full Graph Neural Network (GNN) models, specifically Graph Convolutional Networks (GCNs) and Simplified Graph Convolutions (SGCs). These models leverage the complete graph structure available during both training and inference.
23

---

Published as a conference paper at ICLR 2025
0.74
0.72
D.75
0.70
0.74
0.68
0.50
0.66
0:73
0.64
0.56
200
400
100
200
300
460
1060
2003
5000
4000
Dropping
Dropging
Dropping
Physics
Amazan-ratings
Remanemmpiee
0.850
0.92
0.40
0.825
Mocurecy
0.800
0.90
0.38
0.50
0.88
0.750
0.86
0.36
0.45
0.725
2,00
4000
2000 4000
6000 8000
0.34
4000 6000
5:00
1000 1500 2000
Droppinn Node Number
Gropping Node Number
Dropping Node Number
Dropping Node Number
Figure 2: Accuracy curves for node dropping experiments using the GCN model on various datasets in the inductive setting. Similar to the SGC results, our proposed SGUL method demonstrates superior performance in maintaining higher accuracy as nodes are removed. Note that GNNEvaluator is not shown for the larger datasets due to Out of Memory (OOM) errors.
GRNEval.alor
Corfidence
Confidance
0.70
0.80
0.80
0.78
AccurCy
0.78
0.68
0.76
0.86
0.74
0.64
0.72
0.72
0.62
Dropping Node Number
Dropping Node Number
Dropping Node Number
ATC-MC
DoC
Mac Corfisence
Claxs Confdence
9.GL
Core
Clleseer
Ribmedd
0.80
0.72
0.78
0.76
Accuracy
0.70
0.74
0.76
0.69
0.72
0.68
0.74
0.70
0.67
0.72
500
1000
1500
200
1000
15:0
0.68
2500 5000
7500
1000012500
Dropping Number
Dropping
Dropping
Figure 3: Accuracy curves for node dropping experiments using the SGC (above) and GCN models (below) in the transductive setting.
G.2 NODE DROPPING EXPERIMENTS
We conducted node dropping experiments similar to those in the inductive setting. Figures 3 show the accuracy curves for node dropping experiments using SGC and GCN models respectively in the transductive setting.
According to these figures, our SGUL method consistently maintains higher accuracy as nodes are removed across all datasets for both SGC and GCN models. This performance is particularly notable in the Pubmed dataset, where SCUL shows a significant advantage over other methods throughout the node removal process.
For more detailed quantitative analysis, including Area Under the Curve (AUC) results for both inductive and transductive settings, please refer Appendix
24

---

Published as a conference paper at ICLR 2025
H DETAILED QUANTITATIVE ANALYSIS
To provide a more comprehensive evaluation of our SGUL method, we present here a detailed quantitative analysis using the Area Under the Curve (AUC) metric for the node dropping process. lower AUC score indicates superior performance, representing a more rapid decline in model accuracy when high-value nodes are removed.
H.1 INDUCTIVE SETTING RESULTS
Table 3 presents the AUC results for node dropping experiments in the inductive setting, comparing our SGUL method with several baselines across different datasets and models.
Table 3: AUC results for node dropping experiments in the inductive setting. Our proposed Shap Lasso method consistently delivers competitive performance across various datasets and models. OOM refers to Out of Memory error.
Dataset
Model
ATC-MC
ATC-NE
GNNEvaluator Max Confidence Class Confidence
SGUL
SGC
382.87
399.23
393.73
393.83
384.35
374.22
368.46
Cora
GCN
377.29
384.54
397.35
389.21
384.83
365.48
361.19
SGC
269.84
270.44
273.14 14
271.21
269.17
262.43
257.55
Citeseer
GCN
262.94
266.65
269.02
267.00
265.05
258.69
253.29
SGC 3098.02
3112.55
3136.00
3139.11
3118.71
3111.39
3068.07
Pubmed
GCN
3109.80
3104.37
3147.28
3184.00
3121.70
3131.80
3080.99
SGC 3879.30
3937.35
4023.95
0OM
3690.63
3694.78
3605.92
GCN
4041.18
4134.89
4329.54
0OM
3984.78
3926.17
3896.88
SGC
8007.06
8138.48 48
7802.27
0OM
7802.27
7817.30
7797.74
Physies
GCN
8085.59
8149.07
8328.46
0OM
7818.78
7800.91
7735.92
SGC
2513.36
2577.81
2557.59
0OM
2557.58
2466.70
2401.77
Amazon-ratings
GCN
2508. 83
2562.55
2551.39
0OM
2458.66
2368.
2352.09
SGC
927.38
944.23
907. 65
OOM
907.65
1023.01
159998
Roman-empire
GCN
985.70
997.63
978.04
0OM
978.04
1061.69
935.10
As evident from Table 3 our proposed SGUL method consistently achieves competitive performance across different datasets and models. In many cases, it outperforms the baseline methods, particularly for datasets with heterophily such as Amazon-ratings and Roman-empire. This quantitative compari- son aligns with our observations from the accuracy curves, further demonstrating the effectiveness of our Chapley-Guided Utility Learning approach in capturing the importance of nodes in graph structures, even in challenging scenarios where connected nodes may have different characteristics. The superior performance of SGUL, as reflected in both the accuracy curves and AUC scores, can be attributed its ability to capture the complex interactions and dependencies among nodes the graph, leveraging the Shapley value concept assign importance scores. By incorporating both graph structure and node features, SGUL provides a more comprehensive and accurate assessment of node importance compared to the baselines, which rely on simpler metrics such confidence scores or average differences.
H.2 TRANSDUCTIVE SETTING RESULTS
Table 4 presents the AUC results for node dropping experiments in the transductive setting.
In the transductive setting, SCUL consistently outperforms all baseline methods across all datasets and models. The performance gap is more pronounced compared the inductive setting, particularly for larger datasets like Pubmed. These results further corroborate the effectiveness of our approach across different experimental settings.
25

---

Published as a conference paper at ICLR 2025
Table 4: AUC results for node dropping experiments in the transductive setting
Dataset
Model
ATC-MC
ATC-NE
DoC
GNNEvaluator Max Confidence Class Confidence
SGC
1219.90
1237.21
1251.55
1235.32
1237.00
1207.45
1180.11
Cora
GCN
1216.45
1238.17
1261.80
1246.09
1228.15
1207.03
1180.95
SGC 1157.87
1165.03
1172.98
1157.19
1155.54
1127.22
1123.12
Citeseer
GCN
1201.37
1213.33
1241.40
1221.27
1213.03
1197.15
1171.49
SGC
10271.50
10495.00
10622.11 11
10450.98
10302.39 9814.49
10217.91
9894.75
Pubmed
GCN
9959.40
10262.38
10500.21
10417.29
9648.27
9547.61
I IN-SAMPLE ERROR COMPARISON OF SHAPLEY AND ACCURACY OPTIMIZATION
To empirically validate our theoretical arguments from Section 2
compared the perfor- mance of Shapley-guided optimization (SGUL-Shapley) against accuracy- optimization (SUUL-Accuracy) We used identical validation permutation data for both methods, described in Section 2.2 To isolate the effect the optimization objective, we employed an Ordinary Least Squares (OLS) setting, excluding regularization terms and cosss-alidation. All other aspects, includ- ing the feature set, remained constant between approaches.
We fitted both models using 10 permutations
observation for in-sample Mean Squared Er- ror (MSE) comparison. A Wilcoxon signed-rank test was conducted to assess the statistical sig- nifieance of the difference in MSE for Shapley value prediction between SGUL-Shaples and SGUL-Accuracy.
Table 5 presents the mean in-sample MSE on the validation for both approaches across various datasets in the inductive setting, using the SGC model.
Table lample validation MSE comparison between SCUL- and SCUL-Accuracy datasets using the SGC model in the inductive setting.
Dataset
SGUL-Shapley MSE
SCUL-Accuracy MSE
p-value
Cora
1.35 10
1.40 10-6
1.00 10
Citeseer
6.08 x 10
6.47 x 10
1.00 x 10-12 12
Pubmed
2.70 x 10
2.73 x 10-5
9.31 10-7
CS
5.48 x
5.67 10
9.77 10
Physics
1.95 x 10
2.02 x 10
3.13 10
Amazon-ratings
3.22 10
3.26 10-6
9.31 10-7
Roman-empire
7.59 x 10-6
7.66 x 10
9.31 10-7
The results in Table show that SGUL- SGUL-Shapley consistently achieves lower MSE across all datasets, with statistically significant differences (.05, as determined by the Wilcoxon signed- rank test. The performance gap is particularly notable for larger datasets like CS and Physics, demonstrating SGUL--Shapl ey's scalability and effectiveness across various graph structures.
These findings provide strong empirical support for theoretical analysis in Section 4.2.3 They demonstrate that directly optimizing for Shapley values leads to more accurate estimation of node importance compared the accuracy-based approach.
J DROPPING NODE COMPARISON OF OPTIMIZATION ORJECTIVES
To further evaluate the effectiveness of our proposed Shapley-guided optimization approach, conducted an ablation study comparing two different objective functions: Shapley value optimization SOOLL-Shapley and accuracy-bart cates our main experimental setting and goals, as described in Section 4.2.3 but with a key difference used the same form
optimization (SGUL-Accuracy) This experiment repli-
in the optimization target for SGUI.-Accuracy For SGUL.
26

---

Published as a conference paper at ICLR 2025
proposed method but fitted it accuracy-level data from all validation permutations. We then used this model to perform node dropping experiments, following the same procedure as in main experiments. It's worth noting that this comparison may be influenced by factors such as cross-validattin and the specific characteristics of accuracy-level data, which could introduce some variability in the results. Table presents the AUC results for node dropping experiments using both methods across various datasets and models in the inductive setting.
Table 6: Comparison of AUC results for SGUL Shul-Shapley and SGUL AGUL-AAcO Accuracy in the inductive setting. Lower AUC indicates better performance, and our proposed Shapley- -uidded optimization ShaU--Shaplen generally outperforms the accuracy-basee optimization (SGUL-Accuracy) in terms of AUC results across most datasets.
Cora
Citeseer
Pubmed
CS
Physies
Amazon-ratings Roman-empire
SGC
GCN
SGC
GCN
SGC
GCN
SGC
GCN
SGC
GCN
SGC
OCN
SGC
GCN
SGUT--Shapley 368.46 361.19 287.58 253.29
3068.07 3080,99 3605.92
3896.8
7797.74
7735.92
2401.77 2352.09
851.98
935.10
SSUL-Accuracy 369.74 362.66 257.66
252.87
3078.77
3090.29
3651.12
4140.17
7980.06
7707.45
2405.30
2463.65 852.29 924.64
The results show that SGUL-Shaples Shapley generally outperforms SGUL-Accuraa Accuracy across most datascts and models. Specifically, SBSL--Shaple achieves better results in 10 out of 14 dataset- model combinations. The improvement is particularly noticeable for larger and more complex datasets such as CS, Physics, and Amazon-rating This suggests that the Shapley-guided approach is more effective at identifying critical nodes the graph structure, especially for datasets with more intricate relationships between nodes. These findings align with our theoretical expectations and earlier in-sample error comparisons. They demonstrate that directly optimizing for Shapley values leads to more accurate and robust inference data valuation.
Table 7: Feature importance coefficients for data-specific features across datasets and models
Feature Name
Dataset
GCN
SGC
Cora
0
0
Citeseer
0.007
Pubmed
0
0.002
Edge Cosine Similarity
CS
0.031
0.061
Physics
0.003
0.068
Amazon-ratings
0.025
0
Roman-empire
0
Cora
0.174
0,316
Citeseer
0
0 0.040
Pubmed
0
Representation Distance
CS
0
0
Physics
0
Amazon-ratings
0.285
0.032
Roman-empire
0
Cora
0
0 0.128
Citeseer
0
Pubmed
0.548
0.383
Classwise Rep. Distance
CS
0.195
Physics
0
0
Amazon-ratings
0
Roman-empire
0
K ABLATION STUDY ON FEATURE CONTRIBUTIONS
To investigate the separate contributions of data-specific and moeelfspeeific features, we performed comprehensive analysis of feature importance across different datasets and model architectures
27

---

Published as a conference paper at ICLR 2025
Table 8: Feature importance coefficients for model-specific features across datasets and models
Feature Name
Dataset
GCN
SGC
Cora
Citeseer
0,452
0.291
Pubmed
Maximum Predicted Confidence
CS
0.027
0.465
Physics
0
Amazon-ratings
0
Roman-empire
0.221
0.273
Cora
0.464
0.159
Citeseer
0.193
0,230
Pubmed
0.179
0.227
Target Class Confidence
CS
0.236
0.033
Physics
0.738
0.626
Amazon-rating
0.298
0.606
Roman-empire
0
Cora
0.194
0.114
Citeseer
0.343
0.271
Pubmed
0.147
0.176
Negative Entropy
CS
0.147
0.183
Physics
0.252
0.222
Amazon-ratings
0.166
0.361
Roman-empire
0.227
0.191
Cora
0.168
Citeseer
0.005
0.079
Pubmed
0.110
0.173
Propagated Maximum Confidence
CS
0.216
0.258
Physics
0
0.083
Amazon-rating
0.133
Roman-empire
0.553
0.477
Cora
0
0.057
Citeseer
0
Pubmed
Confidence Gap
CS
0. 148
Physics
0.007
Amazon-
0.092
Roman-empire
0 0.059
(GCN and SGC on inductive setting). Our feature coefficients were obtained through I.1 L.Irreullriiedd optimization, where each coefficient represents the feature's contribution to the utility function. To ensure fair comparison, normalized these coefficients within each dataset-model combination so they sum to allowing us to compare relative importance across different settings.
The detailed results for data-specific features are presented in Table 7 and the detailed results for model-specific features are shown in Table g
To quantify the overall feature importance, further examine the feature selection frequency. For each feature, we count its appearance (non-zero coefficient) across datasets and normalize by the total number of datasets, providing insight into how consistently each feature is selected by L1-regularized optimization. The summary of feature selection frequencies is presented Table
The analysis reveals several key patterns in feature importance. Model-specific features exhibit higher and more consistent selection rates across datasets, with Negative Entropy being selected in all datasets and Target Class Confidence appearing in 85.7% of datasets for both architectures. This
28

---

Published as a conference paper at ICLR 2025
Table 9: Feature selection frequency across datasets for GCN and SGC models
Feature Type
Feature Name
GCN
SGC
Edge Cosine Similarity Representation Distance
0.429
0,429
Data-specific
0.286
0,429
Classwise Rep. Distance
0.286
0.286
Maximum Predicted Confidence
0,429
0,429
Target Class Confidence
0.857
0.857
Model-specific
Negative Entropy
1.000
1.000
Propagated Maximum Confidence
0.714
0.714
Confidence Gap
0.429
0.286
suggests that model-specifie features capture fundamental aspects of model behavior independent of dataset characteristics.
On the other hand, data-specific features show more selective usage, with frequencies ranging from 0.286 to 0.429, indicating that they may be more dataset-dependent. The varying selection patterns suggest that data-specific features capture dataset-specific characteristics that complement the more universal model-specific features.
Interestingly, the selection patterns are remarkably consistent between GCN and SGC architectures, with only minor differences in selection frequencies. This consistency across architectures suggests that our feature design successfully captures fundamental aspects of graph inference quality rather than architecture-speeeee specific characteristics.
These findings support our feature design choices and demonstrate the complementary roles of data-specific and model-specific features in utility estimation. While model-specific features provide universal basis for assessing model performance, data-specific features allow the utility learning model to adapt to the unique characteristics of each dataset. Notably, even for heterophilous graphs where GNNs typically perform worse, data-specific features like edge cosine similarity can still be selected, shown in the ablation study tables for the Amazon-rating This highlights the ability of our utility learning framework to capture the nuanced relationship between graph homophily and test accuracy.
L LARGE-SCALE EVALUATION ON OGB-ARXIV
To demonstrate the scalability and effectiveness of our SGUL framework large-scale graph datasets, we conducted additional experiments on the ogbn-arxiv dataset (Hu et al. 20206). This dataset represents citation network consisting of 169,343 nodes and 1,166,243 243 edges, where each node represents an aiXiv paper and each directed edge indicates citation.
L.1 EXPERIMENTAL SETUP
For this experiment, we randomly sampled 10% nodes from each original train/val/test split and used 50 permutations for utility learning and permutations for testing valuation. This resulted in substantial evaluation set of over 27, ,,000 testing neighbor nodes to the best of our knowledge, this represents the first attempt graph data valuation of this magnitude.
1.22 NODE DROPPING RESULTS
Following the same evaluation protocol described in Section 6 conducted node dropping experi- ments on the ogbn-arxiv dataset. The results are shown Figure and Table 10
Table 10 presents the performance key points during the node dropping process:
The results demonstrate SGUL's superior performance on large-scale graphs. achieves the lowest AUC score (12834.35), significantly outperforming traditional approaches like ATC-MC (12989.56)
29

---

Published as a conference paper at ICLR 2025
ATC-MC ATC:NE
DoC GNNEualutoor
Max Confidence
SUGL
Class Confidence
ogon-arxiv
482.5
480.0
477.5
Accuracy
475.0
472.5
470.0
467.5
465.0
462.5
5000
10000
15000
20000
250000
Dropping Node Number
Figure 4: Accuracy curves for node dropping experiments the ogbn-arxiv dataset using the SGC model in the inductive setting. Our proposed SGUL method demonstrates superior performance, achieving steeper decline in accuracy as high-value nodes are removed.
Table 10: Performance across the node dropping process ogbn-arxiv dataset
Method
Start (idx
5K nodes
10K nodes
15K nodes
20K nodes
End (idx 27421)
AUC
ATC-MC
0.4832
0.4760
0.4748
0.4730
0.4726
0.4672
12989.56
ATC-NE
0.4832
0.4776
0.4755
0.4738
0.4731
0..4622
13013.93
DoC
0,4832
0.4730
0.4710
0,4708
0.4704
0.4672
12923.52
Max Confidence
0.4832
0,4730
0.4710
0.4708
0.4704
0.4672
12923.55
Class Confidence
0,4832
0.4705
0.4690
0.4684
0.4684
0.4672
12864.68
SGDT.
0,4832
0.4698
0.4680
0.4678
0.4668
0.4672
12834.35
and ATC-NE (13013.93). Note that GNNEvaluator encounters Out-of-Memory (OOM) errors on this large dataset, further highlighting the efficiency advantage our approach.
M DETAILED ALGORITHM DESCRIPTION AND EVALUATION PROTOCOL
To provide a comprehensive understanding of our framework's ' implementation and evaluation, we present detailed description through three key components: (1) Shapley-Guider Utility Learning (SGUT. for learning utility functions from validation data, (2) Test-time Structure Value Estimatiin for inference without ground truth labels, and (3) Node Dropping Evaluation Protocol for empirical validation. These components collectively implement and evaluate the methodology introduced in Section of our paper.
M.1 TRAINING PHASE: SHAPLEY-GUIDED UTILITY LEARNING
Algorithm T Timplements our end-to-end optimization framework graph inference data valuation. The algorithm takes as input validation graph Gvat, training graph GT,, fixed trained GNN model f(-). the number permutations M, and a regularization parameter X. As introduced in Section 4.1, the framework begins by initializing data structures V and Ob to store Feature Shapley vectors and true Shapley values respectively, enabling systematic accumulation of value estimates across validation nodes.
30

---

Published as a conference paper at ICLR 2025
Algorithm 1 Shapley-Guided Utility Learning (SGUL)
Input: Validation graph Gy = (Vvat, Eval, Xvai,, Training graph GTy, Fixed trained GNN model f(-), Number of permutations M, Regularization parameter À
Output: Optimal parameter vector w
1: Initialize:
2: V 4-0
Feature Shapley matrix b True Shapley values
3: 4 -
4: for each node i (VV do
5: Generate M valid permutations {Tm Tmmm ((v(((v))))
L.M
6: for each permutation Tm do
Construct subgraph sequence (Tm, ()}E=1 8: Extract features x(S) for each subgraph
7:
9:
Compute utility values (S)) using validation accuracy
Compute feature Shapley vector 4/;
11:
for each feature & do
(U&) M7 Em
(N (1)) U&(NNT)))
13:
V1 (Ui (. (U2), (, (U,))
14:
Compute true Shapley value (i
V V UUU (wb)
16:
4 (o)
17:
Optimize parameter vector:
18:
w +- arg minl Eien(vaa) (o:(U) w Tw))) + +//ww//
19:
Return w*
he core computation occurs in Step 2, implementing the feature extraction and value computation process detailed Section 4.2.1. For each node in the validation graph neighborhood (VVv..). the algorithm generates M valid permutations through Algorithm 4 that respect graph connectivity constraints. Each permutation Tm produces a sequence of subgraphs {Gsus(TT }) through incremental node addition. For each subgraph, extract comprchensive features x x(S) spanning both data-specific measures (edge cosine similarity, representation distance) and model-specific measures (confidence scores, entropy values), with validation accuracy establishing ground truth utility values US)).
Following Section 4.2.2, the algorithm constructs Feature Shapley vectors s/; by computing individual Shapley values (U&) for each feature type k. This process captures each node's contribution across multiple utility metrics, creating rich representation incorporating both graph topology and model behavior. The framework concludes with the optimization step described in Section 4.2.3, where parameter vector is optimized through our objective function directly minimize Shapley prediction error while promoting sparsity through I.1 regularization.
M.2 INFERENCE PHASE: TEST-TIME STRUCTURE VALUE ESTIMATION
Algorithm demonstrates our test-time structure valuation process. Given test graph Gre. target nodes Ve, and the learned parameter vector w from Algorithm 1, we estimate Structure-aware Shapley values for test neighbor nodes without requiring ground truth labels.
The test-time algorithm follows similar permutation sampling and feature extraction pipeline as training, but crucially operates without access to ground truth labels. For each neighbor node ((V),, we generate valid permutations using Algorithm respecting graph connectivity and construct corresponding subgraph sequences. We extract same transferable features established in training phase, computing predicted utility USS) through the learned linear combination w' Tx()). These predicted utilities enable Structure- -waree Shapley value estimation through permutation sampling, effectively quantifying each neighbor's contribution during inference.
Together, these algorithms form complete framework for graph inference data valuation, enabling both efficient training of the utility function and rapid value estimation during test time. The framework's key innovation lies in its ability to learn utility functions without test labels while
31

---

Published as a conference paper at ICLR 2025
maintaining computational efficiency through structured feature extraction and direct Shapley value optimization.
Algorithm 2 Test-time Structure Value Estimation
Input: Test graph GT. = (Vre, XTe), Target nodes V, C VTe. Learned parameter vector w Number of permutations M, Fixed trained GNN model f(-)
Output:
Estimated Structure-Aware Shapley values (EVV))) for neighbor nodes
Initialize:
2: + 4-0
Estimated Structure-Aware Shapley values set
3: for each node i E (V.))
4: Generate . valid permutations {Tm mm= (V))
5: for each permutation 7m do
6: Construct subgraph sequence
t)
7:
Extract transferable features ((5)
8:
Compute predicted accuracy (SS) w x(S)
9:
Estimate Structure-Awwet Shapley value:
6
Em=1 [ÚTT U (i)) (NTT))
11:
b
12:
Return
M.3 NODE DROPPING EVALUATION PROTOCOL
To empirically validate the effectiveness of our structure-aware Shapley values, we conduct com- prehensive node dropping experiments. This evaluation protocol measures how model performance degrades as we sequentially remove nodes ranked by their estimated importance, providing a direct assessment of our valuation framework's 's ability to identify critical graph structures.
Algorithm 3 outlines the node dropping evaluation process. Given test graph Gre. target nodes Vt, and the Structure-an aware Shapley values (eN,)) computed using Algorithm we rank the nodes in descending order of their estimated importance. We then iteratively remove nodes following this ranking and measure the model's s prediction accuracy after each removal. The accuracy curve and Area Under the Curve (AUC) metric are used to quantify the effectiveness of our valuation method.
A lower AUC score indicates superior performance, as it represents a more rapid and sustained decline in model accuracy when high-value nodes are removed. This aligns with our goal of accurately identifying influential graph structures removing truly important nodes should significantly impact model performance. As demonstrated in Section 6.4, SGUL consistently achieves lower AUC scores compared to baseline methods, validating its effectiveness in identifying critical graph structures.
Furthermore, the shape of the accuracy curve provides additional insights into our method's behavior. An ideal curve should show a sharp initial drop. indicating the removal of highly influential nodes, followed by consistent downward trend, suggesting stable and reliable importance rankings. Our experimental results in Section 6.4 demonstrate that SGUL'S 's node dropping curves exhibit these desirable characteristics across various datasets and model architectures.
M.4 SAMPLING PERMISSIVE PERMUTATIONS
The structure-aware Shapley value in our framework is formally defined as:
(N(()))) = ((((())
Σ
(ES(N(()))
This be viewed expectation that approximate through Monte Carlo sampling under precedence constraints. Specifically, we approximate the Shapley value using M random permuta- tions:
32

---

Published as a conference paper at ICLR 2025
Algorithm 3 Node Dropping Evaluation
Input: Test graph Gre = (VTer Ere: XTe). Target nodes V22 C VTe. Structure-aware Shapley values (EN())))) Fixed trained GNN model f(--
Output: Accuracy curve {Acee Area Under the Curve (AUC)
1: Rank nodes in (V,) by {áiliEN(V)) in descending order
2: K + [N(VV
3: for k = K do
4: Remove top-k ranked nodes from GTe to obtain Gk
5:
Compute accuracy: Acc; [Va] Evev, I(f(Gx)(v) yo)
6: Compute AUC: AUC R Σ Ek=1 AccE
7: Return {Accs Ik=1, AUC
M -U( -
(N()) = M I
To implement this approximation while respecting graph structure constraints, we employ Algorithm
4
Algorithm 4 Precedence-Constrrinee Permutation Sampling
Input: Test graph G = (V,EXX) Target nodes V/ C V, Number of samples M, Number of hops & Output: Set of valid permutations { Jm=
for m = M
2: Initialize: Veisited f- Vi
3: Vactive f (u E NG (V/) & Vvisted)
4: while \Vectivll > 0 and Vristeed & do
5: Sample v from Vactive
6: Update Vvisined <- Viisited U ff}
7: Vnew &- {u E EN) u Viisied)
8:
Vactive V Vactive U Vi Vnow {v)
9: Return (Tm mmm
M
This algorithm ensures each sampled permutation satisfies the precedence constraint by maintaining connectivity. Starting from target nodes Vt, we iteratively sample nodes from their active neighbors (those not yet visited) while preserving graph connectivity. This sampling process guarantees that each permutation respects the structural dependencies inherent in the message-passing process, as demonstrated through our comprehensive experimental results Section 6
33


Reviews:
[{"review_id": "Pl0m4NqyNe", "reviewer": "Reviewer_PSYo", "summary": "The paper has studied the graph inference data valuation problem by developing a new data-driven utility function and providing theoretical insights to enable direct optimization through the Shapley value decomposition. Extensive experiments on public datasets were provided in terms of multiple evaluation protocols.", "questions": "While it is interesting and novel to connect utility learning and Shapley value prediction through a linear projection, the training process of the data-driven utility function and how to obtain feature Shapley values ($\\psi_i$) remain unclear to me. \n- How to obtain/initialize $\\psi_i$?\n- Can `Theorem 1` be applied to general domains other than graph-structured data? \n- Is there any limitation or assumption for `Theorem 1`?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- A new definition of the structure-aware Shapley value has been introduced to facilitate graph data valuation. \n- The paper has extensively discussed the limitations of applying Shapley values on graph-structured data from the utility estimation and indirect optimization perspectives, resulting in the proposed SGUL framework. \n- The experiment is well designed to comprehensively access both utility estimation and data valuation, covering different graph structures, downstream tasks, and multiple evaluation protocols.", "weaknesses": "- While the proposed method seems novel and technically sound to me, it would be better to involve a more detailed comparison and discussion with existing works (e.g., [Chi et al., 2024]) in the main text and experimental analysis. \n- It remains unclear if the proposed SGUL is scalable to large graph benchmarks, such as Open Graph Benchmark (Hu et al., 2020), due to the introduction of an $\\ell_1$ penalty in eq (3).\n- The methodology is somewhat hard to follow and less self-contained. An illustration framework or outline algorithm would be much helpful.", "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": "rjpDv2QkKc", "reviewer": "Reviewer_u5np", "summary": "The paper proposes a novel framework called Shapley-Guided Utility Learning for the graph-structured data valuation problem. The proposed method tackle with two problems associated with graph-structured data valuation: lack of test labels and indirect optimizaiton of utility function.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and organized.\n2. The method is well motivated and justified.\n3. The experimental results shows promising performance.", "weaknesses": "1. The details of permuation sampling process is not clear. Could authors elaborate on the sampling process?\n2. The proposed data-specific features, such as edge cosine similarity, appear to favor graph homophily. When applying this framework to heterophilous graphs, it raises the question of whether these features would still be effective.  How is edge cosine similarity adapted for both homophilous and heterophilous graphs? Additional discussion on this point could be valuable.\n3. It seems that the ablation study on the investigation of the seperate contribution of data-specific features and model-specific feature is missisng.", "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": "3zmGz7ctZZ", "reviewer": "Reviewer_KEdX", "summary": "In this paper, the authors design a shapely-guided unility learning framework for graph inference data valuation, which termed SGUL. SGUL combines transferable data-specific and model-specific features to test data without relying on labels.", "questions": "Please see weakness.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The author has provided the code to ensure the reproducibility of the paper’s results.\n\n2. The author has supplied partial theoretical proofs to support the claims made in the study.", "weaknesses": "1.  In Figure 1, the author has chosen a comparison method that only includes one paper from 2024. Please incorporate more recent comparative experimental methods.\n\n\n2. The results of the comparative experiments by the author are perplexing. Why does SGUL consistently perform the worst across all datasets? The author explains that SGUL can identify important nodes in the graph structure. However, could it be that the design methodology is ineffective, leading to the model’s poor performance?\n\n\n3. In the field of graph neural networks, test-time training methods are widely used to address distribution shift issues in test data[1,2,3,4]. These methods also do not require labels. How does your approach compare to test-time training-based graph methods, and what advantages does it offer?\n\n\n4. In Theorem 1, why is the variable U suddenly linear when it was previously described in exponential form (as in Equation 1)? The transition lacks a clear explanation, even though the author provides a proof based on the linear function.\n\n5. There are typographical errors, such as consecutive “for instance” phrases in line 206.\n\n6. The advantages in terms of time and space efficiency are not clearly demonstrated and need to be supported by experimental evidence.\n\n[1] Jin W, Zhao T, Ding J, et al. Empowering graph representation learning with test-time graph transformation[J]. arXiv preprint arXiv:2210.03561, 2022\n\n[2]Wang L, He D, Zhang H, et al. GOODAT: Towards Test-Time Graph Out-of-Distribution Detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2024, 38(14): 15537-15545.\n\n[3]Zheng X, Song D, Wen Q, et al. Online GNN Evaluation Under Test-time Graph Distribution Shifts[J]. arXiv preprint arXiv:2403.09953, 2024.\n\n[4]Pi L, Li J, Song L, et al. Test-Time Training with Invariant Graph Learning for Out-of-Distribution Generalization[J]. Available at SSRN 4886269.", "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": "SXk07bRypM", "reviewer": "Reviewer_cyJv", "summary": "This paper is well-written. It combines transferable data-specific and modelspecific features to approximate test accuracy without relying on G-T labels.", "questions": "1. Is there any experiment to show the importance of  the structure-aware Shapley value?\n\n\n2. Since you are the first to formulate the graph inference data valuation problem, what's the main different between your work and GNNEvaluator[1]?It seems that both of you are methods for verifying GNN performance without  labels.\n\n3. In your code, Which part of the paper does 'data_without_edges' correspond to? Why remove the graph structure for testing？\n\n\n\n[1] GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels, arxiv 2310.14586", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This work introduces a transferable feature extraction method that transforms player-dependent inputs into general features.\n\n2. Authors claim that they are the first to formulate the graph inference data valuation problem.\n\n3. Code is open-source and readable.", "weaknesses": "1. Lack of comparison with other works. GNNEvaluator, DoC, ATC are the compared baseline in your experiment, but readers are not yet clear about the main differences between these baselines and your method. I noticed that there is an introduction in the appendix, but there is a lack of comparison.\n\n2. The method in this work has special optimization in structure(Sec 3.2), but lacks experimental verification of this optimization.", "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)