Data Valuation for Graphs

We would like to thank the reviewer for the detailed comments. We appreciate you find our categorization clear and detailed, and the experiments varied. In the following we response to the comments.

W2) The cumulative runtime for all the experiments is already mentioned in the introduction. The runtime of each approach can be divided into two times: one needed to collect the utility across the subsets, and one needed to compute the values for the nodes. In the following table we report the sum of these two times:

SGC Computation times

---

GCN Computation times

---

GAT Computation times

Experiments are still running and we’ll update the tables as they finish. We added the tables in the manuscript (see Appendix D).

W1/Q1) As we explained in section 3, when we need to assess the value in the non-i.i.d. setting we have different scenarios that we need to take into account according to the downstream application. First of all, as also unlabeled nodes play a role in the prediction for others (via their structure), accounting only for the value of training examples (as done in the i.i.d. setting) might results in suboptimal attribution. We show this in our experiments, for example in Figure 9, we have a test node that is more influent than other training nodes for the prediction of a given node (this is also shown in Figures 13-14 where some test nodes is ranked earlier than some training node). Another underestimated aspect is the way the utility is computed: once we train the model on a subset, we can compute the utility either on the full graph (adding back the removed nodes) — that we address as learning signal — or keeping the subgraph — that we address as overall signal. We also added a new figure (Figure 19) that makes clear the distinction of these two settings. More generally, coming up with new graph-specific approaches might be tricky if we do not properly account for the baselines in the right setting. Indeed, as we show in our experiments, already state-of-the-art approaches for the i.i.d setting perform really well in the semi-supervised learning.

We would like to thank the reviewer for the detailed comments. We appreciate you find our work a good introduction to the field, and the evaluation of the approaches in downstream tasks varied. In the following we response to the comments.

W1) Thank you for pointing out this aspect. It is not clear to us what does it mean to remove a node but keep its edges. We are open to suggestions from the review. Nonetheless, we agree that is more clear to say that value we are computing is the value of the node and its associated edges. We updated the paper to reflect this (see lines 321-323).

W2) Our work focuses more in establishing a proper setting for data valuation in the graph domain. As a consequence of this, we believe that before developing ad-hoc strategies for the domain under investigation we should properly define the problem and correctly evaluate the baselines. Section 4 provides general insights about the functioning of graph neural networks and graph data rather than analysing already established approaches. For example, we pointed out how state-of-the-art approaches for the i.i.d. setting already perform better than ad-hoc graph methods (see Figure 3 and relative section). We showed the brittleness of GNNs where when just removing a few tens of nodes results in the model to mispredict most of the test nodes (see figure 4[left] and relative paragraph. We showed how baseline approaches are better in detecting poisoned nodes in the dataset than ad-hoc graph methods (see Figure 7 and relative paragraph). We also show how data values can transfer across models (Figure 8) and how values can be used to study how predictions are affected by the other nodes (see Figure 9 and 10).

An insight on why PCW fails in capturing meaningful values might be its similarity to data Shapley. Specifically, PCW restrict the possible permutations of Shapley such that it accounts for the graph structure ($k$-hop neighbors), and then scan these permutations as done in data Shapley. Then, as for data Shapley many evaluations are performed on degenerate subsets made of a very few nodes (each permutation is scanned in a progressive way). Instead, considering subsets controlled by a probability $\alpha$ of keeping a node — as for Datamodel and data Banzhaf, allows to use most of the evaluations for subsets of meaningful size. Another reason might be PCW’s inductive nature, as it was designed for inductive tasks. Indeed, we showed that in the transductive setting, maximixing the permutations (PCWP by increasing the truncation ratio for the 1- and 2-hop neighbors) benefits the final attribution. To verify this, we also implement the Banz and DM inductive variant to test the unlabeled node removal performance as in PCW. Preliminary results show that PCW in the inductive setting is better than DM and Banz.

W3) The sizes of the nodes in Figure 9 are according to the magnitude of its importance (larger nodes are more important than smaller). We explained this in the text when introducing the figure. However, we agree with the reviewer that a legend can simplify the understanding of the figure. We have included a legend in Figure 10 too, where (although already mentioned in the caption) explaining the meaning of the crosses. The value for the color is implicitly given by the color bar. Could you please mention other figures which should be clarified more?

W4) We agree with the reviewer that a dedicated section with the lesson learned and potential guidelines for the community is beneficial for the paper and we added it in the new revision (see Appendix A). We can integrate this section in the main body for the camera-ready version. Overall, the main insights can be summarized as:

1. It is not given that ad-hoc data valuation approaches for graphs work better than the current state-of-the-art in the i.i.d. setting. As we show, setting up and tuning the baselines indeed lead to better performance.
2. The Maximal Sample Reuse (MSR) adopted by data Banzhaf is a useful technique that provides better estimation because of the sample reuse. Moreover, we showed that this can be adopted with a binomial probability rather than uniform sampling and this empirically performs well.
3. GNNs are very brittle to structure modification — the removal of just a handful of nodes causes the model to mispredict most of the test nodes — and we showed this from a data attribution point of view, that is complimentary to adversarial perturbations.
4. Data values align more closely with true values when we can access a large number of subsets. However, this comes with increased computational costs. Developing more time-efficient methods is crucial for achieving more reliable data attributions. One potential approach is to leverage more efficient models, as data values are an intrinsic property of the data rather than the specific model used to compute them.

We would like to thank the reviewer for the detailed comments. We appreciate you find our evaluation comprehensive and the visualizations insightful. Please find below our response to the comments.

W1, W2) As we mentioned in the introduction, our focus is not on the technical novelty. Rather, our focus is more on testing the state-of-the-art data valuation approaches in the context of graphs. Indeed, as we show ad-hoc graph approaches (PCW) are not necessarily better when compared to these baselines in the transductive setting. In addition, we introduce the concepts of Learning vs Overall values which uniquely applies to semi-supervised setting and has not been studied so far.

W3) We already reported in the introduction the overall computation costs of running all the experiments included in the manuscript. However, computation costs of an approach can be split into two costs: one regarding the collection of the actual utility across the considered subsets, and then the cost of computing the value. In the following table we report the sums of these two costs for each approach with $50000$ subsets $\alpha = 0.1$. Overall, Banz is faster than DM across all settings.

SGC Computation times

---

GCN Computation times

---

GAT Computation times

Experiments are still running and we’ll update the tables as they finish. We added the tables in the manuscript (see Appendix D).

W4) While Citeseer and CoraML can be considered as “toy” datasets in the context of proposing new GNN architectures, they are still the main datasets when studying specific aspects of GNNs (adversarial robustness, explainability, oversmoothing, uncertainty quantification, etc.). Moreover, we have results for larger dataset too, like PubMed, Photo, Computers and CoPhysics. Computing existing data values on even larger graphs is computationally prohibitive. However, we agree with the reviewer that data valuation approaches need to scale and, as we pointed out in the conclusion, more effort is needed in this direction. Worth to mention, the largest graph in the only graph-specific baseline (PCW) is CoPhysics.

We would like to thank the reviewer for the detailed comments. We appreciate you find our work interesting and important for future investigation in the field. In the following, our response to the comments and questions.

Unlabeled data claims support We kindly point the reviewer to Figure 9 and Figure 13 for supporting claims in favor of unlabeled node values. In particular, in Figure 9 size of nodes corresponds to the magnitude of the importance value for the test node under investigation, and the incoming edge color represent if it’s a positive relevant node (green) or negatively relevant node (red). In the main subplot, a test node (represented by squares) has a higher positive importance than training nodes (represented as circle). We updated Figure 9 with a legend to clarify the different node types. Additionally, in Figure 13, we show the nodes ranked by their values computed by different approaches. Here, we can see that test nodes (green bars) come first in the ranking than training nodes (red bars). However we agree with the reviewer that these details are not emphasized, thus we’ll make sure to clarify these in the revised version.

Learning vs Overall We agree with the reviewer that the distinction between Learning and Overall signals might be difficult to digest. To account for this, we have include a new figure in the manuscript in appendix C.1 trying to make the distinction more clear. We remain open to any suggestion from the reviewer for a proper naming of the two settings. (See Figure 19).

Figure 1 fixes The colors in Figure 1 indicate the importance of each node as a result of the subsets scan. We agree with the reviewer that using real number might avoid confusion with the coloring of other figures (like in Figure 9 colors represent classes). For this reason, we changed our figure accordingly, keeping the coloring in the real numbers to convey the message of positive/negative influential or uninfluential nodes. Moreover, we included a legend for the colors in the other figure (see Figure 9).

Q1) All valuation methods we tested satisfy the linearity axiom. As pointed out in [1] (appendix E.3), the linearity allows to attribute the value of a group of datapoints as the sum of their values. For example, this is the core idea on which the brittle predictions experiment is based on — to find the smallest subset whose removal decreases the margins the most is equivalent to remove the top-k nodes according to their value. Anyhow, we agree with the reviewer that an interesting direction is going beyond the additive assumptions and develop approaches accounting for group influence.

Q2) High in-class influence means that most important nodes are within the same class. If you think of this in terms of the margin — which is the metric we used as the utility — adding nodes from the same class increase the margins, while adding nodes from other classes decreases the margins. In terms of robustness, this means that high in-class positive influence (green values) correspond to a low error. To verify this, we plot a confusion matrix of the model’s predictions over the heatmap of the average in-class influence (see updated Figures 17-18). Indeed, we can see that the highly positive influence corresponds to the classes where the model predicts less false positives and thus is more certain about its predictions.

Q3) The intuition behind the increasing performance of LOO when $\alpha$ increases is that the higher the $\alpha$ the more similar are the subsets wrt the ones LOO is trained on. In other words, $\alpha$ represents the probability of keeping a node in the subset. As we increase this probability the resulting subset will be more similar to just leave out one sample, namely LOO.

Q4) We agree with the reviewer that is interesting to draw similar conclusions for the supervised learning setting. Indeed, even in the i.i.d. setting the evaluation across approaches is not carefully performed. For example, there is no work comparing data Banzhaf and Datamodels in the i.i.d. setting. Only [2] makes a connection between the two approaches but no comparison is performed. We plan to investigate this further, but in the meantime to fill this gap, we performed a preliminary experiment on Cifar10 where we compare Datamodels, data Banzhaf and our adaptation $\alpha$-Banzhaf on the data pruning experiment. We tested the attribution performance considering only 25000 subsets and training a single model for each subsets, with values for $\alpha$ equal to $0.1$ and $0.5$ (to match data Banzhaf). From our preliminary experiment, we can draw similar conclusions: data Banzhaf outperforms Datamodels. Additionally, data Banzhaf is more computationally efficient, e.g. in this experiment for $\alpha$ equals $0.1$ computing datamodels took 30 mins while computing data Banzhaf took just 6 mins; for $\alpha$ equals 0.5 computing Datamodels took 4 hours while data Banzhaf took 30 mins.