Structural Fairness-aware Active Learning for Graph Neural Networks

Q2: My major concern is that the fairness definition in this paper is not very clear. We usually use demographic party (DP) or equal odds (EO) to measure fairness. However, this paper only uses the Standard Deviation (SD) and the Coefficient of Variation. Why do the authors consider them instead of DP and EO?

R2: The performance fairness issue that we focused on in this paper is caused by the label position bias. We would like to first provide the definitions:

Label Position Bias & Structural Fairness: In this paper, we use the notion of "Label Position Bias", a critical aspect of performance bias in GNNs. This bias arises when the performance of a GNN model varies for nodes based on their proximity to labeled nodes in the graph.[1] Formally, in a graph G, with the set of labeled nodes $V_L$, and unlabeled nodes $V_U$, a GNN model trained on $V_L$ may exhibit varying performance for two nodes $i, j \in V_U$ based on their "structural distance" to $V_L$. A key metric we use to measure this distance is the Label Proximal Score $LPS_{i} = \sum_{j \in V_L} P_{ij}$, where P is the personalized PageRank matrix. The LPS can well quantify the proximity of unlabeled nodes to labeled nodes and a higher LPS score typically correlates with better model performance for that node [1]. [1] also found the low variance of the LPS score, which indicates all the nodes have a similar "distance" to the labeled nodes, can mitigate the label position bias and improve the performance fairness of GNNs. As a result, we use the variance of the LPS score of each node as the measure of structural fairness.

Measuring Performance Fairness: To quantify performance fairness, we categorize nodes into different sensitive groups based on their LPS scores. For each group, we calculate the average accuracy of the GNNs and use metrics such as Standard Deviation to measure the performance disparity across these groups.

In fact, when considering multiple sensitive groups, the concepts of DP and SD are the same. If there are only two sensitive groups $i$ and $j$ with accuracy $a_i$ and $a_j$, the $DP = |a_i - a_j|$. However, if there are multiple sensitive groups, $DP = \sum_i |a_i - \bar{a}|$, where $\bar{a}$ is the average accuracy. Therefore, we use the Standard Deviation $SD = \sqrt{\sum_i (a_i - \bar{a})^2}$ to measure the fairness. In our paper, we use the Label Proximity Score to split the nodes into multiple sensitive groups. This realization aligns with your suggestion, and we will update our terminology about SD to reflect this more accurately in our revised paper. Additionally, we use the Coefficient of Variation (CV) because it normalizes the standard deviation by the mean, $CV = SD / \bar{a}$. This normalization is particularly useful for comparing the relative disparity in performance across models with different overall accuracy levels, allowing us to assess fairness in a way that accounts for differences in model performance.

Q3: Figure 6 and Figure 7 are also not very clear to me. The authors discussed that `SCARCE, which combines both SIS and LPS variance, SCARCE can not only elevate overall performance but also attain commendable fairness'. However, it is very hard to get this result from these two figures. I suggest the authors provide more details for examination.

R3: Thank you for your feedback on Figures 6 and 7, which might be uneasy to read. The proposed SCARCE combines two metrics, i.e., the LPS variance and SIS, to strategically select nodes for annotation. Figures 6 and 7 showcase the impact of these metrics on the Cora and CiteSeer datasets, respectively. For each figure, the left subfigure represents the accuracy, and the right subfigure represents the fairness (Standard Deviation) of using different metrics. From Figure 6 and 7, we can find:

• For accuracy, the proposed SCARCE, which combines both LPS variance and SIS, consistently achieves better accuracy compared to using either metric alone.
• For fairness, using the LPS variance alone tends to cause a low SD (better fairness). This finding is consistent with our motivation for leveraging the LPS variance to address the fairness issue. The SIS alone may lead to a higher SD. However, when combining these two metrics in SCARCE, we observe that the model maintains commendable fairness (lower SD).

Q4: This paper should focus on fairness instead of classification accuracy. However, Tables 1 and 2 provide more details about the classification accuracy. There should be a trade-off between accuracy and fairness. Only showing accuracy does not make any sense. In addition, how to balance the trade-off between accuracy and fairness in this paper. I do not find any implementation details related to this.

R4: We would like to clarify that the main focus of this paper is the active learning for the graph neural networks, which aims to maximize the model's performance within a labeling budget. We propose a unified framework that effectively combines different metrics in active learning. As discussed in R1, both active learning and mitigating label position bias are fundamentally related to the labeling of nodes in a graph. Besides, structure fairness (low LPS variance) is also related to the overall performance of GNNs, as demonstrated in the preliminary study. Therefore, we leverage structural fairness as one metric in active learning to maximize GNNs' performance. Meanwhile, we found this metric can also improve performance fairness, as shown in Figures 4 & 5 in our paper. Therefore, it is not a trade-off between accuracy and fairness. As demonstrated in Figures 6 & 7, incorporating the LPS variance can improve the model's overall performance and performance fairness. As a result, the proposed method bridges the gap between active learning and mitigating the label position bias in GNNs, proposing that addressing fairness can be synergistic with achieving high model performance.

We hope that we have addressed the concerns in your comments, and please kindly let us know if there is any further concern, and we are happy to clarify.

Dear Reviewer RKZS,

We appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns.

Q1: I suggest the existing work on fairness in GNN should be discussed. Otherwise, it is very hard to estimate the significance of this work.

R1: Thank you for your suggestions. It is important to clarify that the type of fairness our paper addresses differs significantly from the commonly studied attribute bias, which pertains to model performance disparity across different sensitive attribute groups, such as gender and race.

Our work concentrates on structural fairness, specifically tackling the issue of "Label Position Bias" in GNNs. This bias emerges due to the varying performance of a GNN model for nodes based on their "structural distance" to labeled nodes in the graph. Research [1] uses the Label Proximal Score (LPS) to quantify this proximity, with a higher LPS indicating a closer "distance" to labeled nodes and typically correlating with better model performance. They found the low variance of the LPS score, which means all the nodes have a similar "distance" to the labeled node, can mitigate the label position bias and improve the performance fairness of GNNs. Thus, we use the LPS variance to measure structural fairness. One natural way of reducing the LPS variance is to strategically select the labeled nodes based on their position in the graph.

The goal of active learning is to strategically select some nodes to label that can maximize the model's performance. Therefore, both active learning and mitigating the label position bias are fundamentally linked to the labeling of nodes in a graph. Our preliminary studies illustrate that structure fairness (Low LPS variance) is also related to the overall performance of GNNs, which is the central focus of active learning. Therefore, in this work, we use the LPS variance as one metric for active learning to select nodes to label. The proposed method not only improves performance but also addresses the fairness issue.

As for the existing works on fairness in GNNs, most of them focus on attribute fairness, which is not related to the selection of labeled nodes. Therefore, they are not related to labeling, which is the target of active learning. The pioneering work [1] identifies label position bias and proposes solving it by learning an unbiased graph structure. Our contribution differs as we approach the issue from a labeling perspective, offering an alternative solution to the problem.

Additionally, our method has the advantage of performing well even when node features are noisy or missing, as shown in the experiments in Appendix Section B.3 of our revised paper. For your convenience, we also present partial results here:

1. Noise feature setting: we add different levels of gaussion noise to the node features.

2. Missing feature setting: we use the one-hot ID as node features. |GCN||Cora|||CiteSeer|| |:---:|:---:|:---:|:---:|:---:|:---:|:---:| |Budget|5C|10C|20C|5C|10C|20C| |Random|44.76±5.83|56.47±2.30|64.03±1.74|28.41±2.69|34.78±3.06|40.58±2.61| |Degree|44.19±7.98|51.69±2.82|63.26±1.95|27.33±1.97|31.74±2.79|40.99±2.02| |Pagerank|39.19±3.55|47.95±3.94|63.93±3.85|24.03±1.96|32.83±2.21|40.35±2.02| |FeatProp|47.75±3.16|58.84±3.22|65.66±1.38|29.79±2.32|34.79±2.00|41.89±2.71| |GraphPart|55.37±4.06|57.40±4.24|67.60±2.61|38.27±2.08|37.40±2.56|43.61±3.15| |SCARCE|61.43±2.31|68.64±1.94|69.59±1.22|37.89±1.94|43.51±1.44|48.20±1.15|

From the above results, we can find that the feature-based active learning method, such as FeatProp, can't perform well when the noise level is high or all the features are missed. However, our proposed SCARCE can only leverage the graph structure and perform well on both scenarios.

[1] Towards Label Position Bias in Graph Neural Networks, NeurIPS'23

Dear Reviewer RKZS,

We would like to express our sincere gratitude to you for reviewing our paper and providing valuable feedback. Could we kindly know if the responses have addressed your concerns? If there are any further questions, we are happy to clarify. Thank you.

Best,

All authors

Q6: How does the proposed method solve the fairness issue from the theoretical aspect?

R6: In this work, we focus on the performance fairness issue caused by the labeling of nodes, which is different from the traditional fairness issue caused by some sensitive attributes, such as gender and race. To solve this performance fairness issue, we directly optimize the structure fairness (low LPS variance) by selecting the nodes for annotation (active learning). And we empirically demonstrate that the proposed method can mitigate the performance fairness issue, as demonstrated in Figures 4 and 5 of our paper. Besides, the LPS score of node $y$ is related to the influence score from labeled node $x$, defined as the absolute values of entries of Jacobian matrix $\left[\frac{\partial h_x^{(k)}}{\partial h_y^{(0)}}\right]$ [7], where $h_x^{(k)}$ is the representation of node $x$ in a $k$-th layer GNN. [1] found that a lower LPS variance suggests a more uniform influence of all labeled nodes to each unlabeled node across the graph, hinting at greater fairness.

[7] Representation Learning on Graphs with Jumping Knowledge Networks, ICML'18

Q7: Why do we use active learning to solve the fairness issue in graphs? What if we do not have access to the oracle?

R7: As mentioned in R1 and R3, both active learning and structure fairness issues are related to the labeling of nodes in a graph. Thus, we leverage the principles of active learning - strategic node selection for labeling - to improve structure fairness and thus solve the performance fairness issue of GNNs.

Regarding the concern about reliance on an oracle for annotations: in active learning, the oracle is typically a necessary component for providing labels for the selected samples. If we do not have access to the oracle, we might need some pre-trained model to do annotation. For example, we can use the Large Language Model as an annotator, like [8].

[8] Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs. Arxiv'23

We hope that we have addressed the concerns in your comments, and please kindly let us know if there is any further concern, and we are happy to clarify.

Q4: The paper does not provide any theoretical proof to support the findings or the motivations.

R4: We appreciate the concern regarding the lack of theoretical proof in our paper. Our research, focusing on the effectiveness of our approach in the context of active learning for GNNs, is primarily grounded in empirical evaluations. This decision is partly informed by the nature of active learning itself, which, as suggested by the No Free Lunch Theorem, does not subscribe to a one-size-fits-all strategy. Active learning metrics often vary significantly based on the specific datasets and contexts they are applied to. As a result, most active learning approaches use some heuristic metrics to select samples [2][3].

To illustrate this, let's consider the example of the FeatProp method, which is based on the assumption of linearity in GNNs. This method presupposes that the original features can represent the final node representations in GNNs. However, this assumption often falls short due to the inherent non-linearity of neural networks. As such, in scenarios where the original features are compromised – for instance, in the presence of noise or feature missing – the FeatProp method's performance can be significantly impacted, as shown in the experiments in Appendix Section B.3 of our revised paper. For your convenience, we also present partial results here:

1. Noise feature setting: we add different levels of gaussion noise to the original feature. |GCN|||Cora|||||CiteSeer||| |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| |Noise|0.1|0.3|0.5|0.7|0.9|0.1|0.3|0.5|0.7|0.9| |Random|64.52±4.50|51.76±4.19|44.76±4.12|40.54±4.12|38.65±3.33|49.16±8.22|36.36±5.71|29.53±4.38|27.05±2.07|26.34±1.85| |Degree|61.58±0.44|54.84±0.66|51.25±0.60|49.82±0.62|47.37±0.79|44.37±0.88|37.27±0.47|34.28±0.56|34.53±0.46|34.12±0.56| |Pagerank|60.77±1.16|43.22±2.59|34.96±2.23|32.86±0.94|32.76±1.27|49.34±2.77|33.40±2.49|27.99±1.22|25.41±1.95|25.08±1.74| |FeatProp|77.51±0.61|45.93±2.18|38.50±1.63|32.94±0.48|26.86±1.45|52.30±2.47|33.16±1.62|27.59±1.84|26.10±1.25|24.88±0.98| |GraphPart|79.22±0.48|62.17±1.24|51.80±0.85|45.01±1.05|40.83±1.56|52.37±1.13|44.63±1.05|38.91±0.66|35.59±0.92|34.42±1.51| |SCARCE|75.13±0.81|67.23±0.70|59.42±0.47|55.90±0.63|53.45±0.96|59.50±2.53|50.35±0.56|41.61±0.83|37.23±0.63|35.23±1.11|
2. Missing feature setting: we use the one-hot ID as node features. |GCN||Cora|||CiteSeer|| |:---:|:---:|:---:|:---:|:---:|:---:|:---:| |Budget|5C|10C|20C|5C|10C|20C| |Random|44.76±5.83|56.47±2.30|64.03±1.74|28.41±2.69|34.78±3.06|40.58±2.61| |Degree|44.19±7.98|51.69±2.82|63.26±1.95|27.33±1.97|31.74±2.79|40.99±2.02| |Pagerank|39.19±3.55|47.95±3.94|63.93±3.85|24.03±1.96|32.83±2.21|40.35±2.02| |FeatProp|47.75±3.16|58.84±3.22|65.66±1.38|29.79±2.32|34.79±2.00|41.89±2.71| |GraphPart|55.37±4.06|57.40±4.24|67.60±2.61|38.27±2.08|37.40±2.56|43.61±3.15| |SCARCE|61.43±2.31|68.64±1.94|69.59±1.22|37.89±1.94|43.51±1.44|48.20±1.15|

While we acknowledge the importance of theoretical backing in scientific research, our current focus has been on demonstrating the practical efficacy and adaptability of our approach in diverse and realistic settings. Moving forward, we aim to complement our empirical findings with theoretical analysis to provide a more holistic understanding of our approach's mechanics and its broader applicability.

[2] A Survey of Deep Active Learning, CSUR'21

[3] A Comparative Survey of Deep Active Learning, Arxiv'22

Q5: The relaxation used in the unified framework is also misleading. Why can we use the relaxation of the binary vector t to its convex hull?

R5: The relaxation of binary vectors to their convex hull is a well-established technique in combinatorial optimization [4], particularly when dealing with complex optimization problems that are otherwise computationally intractable. This approach allows for the application of more efficient, continuous optimization methods. This method is usually used in gradient-based attacks [5][6]. For example, [5] leverages this relaxation to do the topology attack on graphs.

[4] LP Relaxations for Combinatorial Relaxation

[5] Topology attack and defense for graph neural networks: An optimization perspective, Arxiv'19

[6] Probabilistic Categorical Adversarial Attack and Adversarial Training, ICML'23

Dear Reviewer tqC2,

We appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns.

Q1: The paper tries to solve the structure fairness problem using active learning. However, the connection between these two is weak, and the reviewer does not find any strong motivations to do so.

R1: Thank you for your feedback. We would like to clarify that the main focus of this paper is the active learning for graph neural networks, which aims to maximize the model performance within a labeling budget. There are two main reasons why we connect the structure fairness problem with active learning. First, the structure fairness discussed in our paper is based on the labeling. We explore "Label Position Bias" in GNNs, a critical performance fairness issue arising from varying performance based on nodes' "structural distance" to labeled nodes. The distance can be measured by the Label Proximity Score (LPS). Research [1] indicates that nodes closer to labeled nodes (higher LPS) typically perform better. They found the low variance of the LPS score, which means all the nodes have a similar "distance" to the labeled node, can mitigate the label position bias and improve the performance fairness of GNNs. Thus, we use the LPS variance to measure structural fairness. One natural way of reducing the LPS variance is to strategically select the labeled nodes based on their position in the graph. Meanwhile, the goal of active learning is to select proper nodes for annotation that can maximize the model performance. Thus, both problems are related to the labeling. Second, from our preliminary studies, we found that structural fairness (low LPS Variance) can improve the overall model performance. As a result, we use the LPS variance as one metric to help active learning. Meanwhile, as the structural fairness (low LPS Variance) can improve the performance fairness, we find that the proposed method can improve both the model performance and the performance fairness of GNNs.

[1] Towards Label Position Bias in Graph Neural Networks, NeurIPS'23

Q2: What is the formal definition of the structure bias in graphs, and how can we quantify it?

R2: Label Position Bias & Structural Fairness: Label Position Bias arises when the performance of a GNN model varies for nodes based on their proximity to labeled nodes in the graph.[1] Formally, in a graph G, with the set of labeled nodes $V_L$, and unlabeled nodes $V_U$, a GNN model trained on $V_L$ may exhibit varying performance for two nodes $i, j \in V_U$ based on their "structural distance" to $V_L$. A key metric we use to measure this distance is the Label Proximal Score $LPS_{i} = \sum_{j \in V_L} P_{ij}$, where P is the personalized PageRank matrix. The LPS can well quantify the proximity of unlabeled nodes to labeled nodes and a higher LPS score typically correlates with better model performance for that node [1]. We use the variance of the LPS score of each node as the measure of structural fairness.

Measuring Performance Fairness: To quantify performance fairness, we categorize nodes into different sensitive groups based on their LPS scores. For each group, we calculate the average accuracy of the GNNs and use metrics such as Standard Deviation to measure the performance disparity across these groups.

Q3: The goal of active learning is different from mitigating the bias in graphs and the ultimate goal of AL is to use as few as labeled nodes to achieve the best prediction performance. Therefore, the motivation of this work is totally unclear.

R3: The label position bias studied in this paper is different from the traditional attribute bias issue. It is unique for graphs and is related to the labeled nodes' position in the graphs. A natural solution to mitigate the label position bias is to select the nodes, that have proper positions in the graph, to label. Meanwhile, as you mentioned, the ultimate goal of AL is to select the proper nodes to label to achieve the best prediction performance. As a result, both active learning and mitigating the bias are fundamentally related to the labeling of nodes in a graph.

In the preliminary studies, we found that structure fairness (Low LPS variance), which can reflect the label position bias, is also related to the overall performance of GNNs. Therefore, we leverage the LPS variance as one metric in the active learning to improve the overall model performance. This bridges the gap between active learning and mitigating the label position bias in GNNs, proposing that addressing fairness can be synergistic with achieving high model performance.

Dear Reviewer tqC2,

We would like to express our sincere gratitude to you for reviewing our paper and providing valuable feedback. Could we kindly know if the responses have addressed your concerns? If there are any further questions, we are happy to clarify. Thank you.

Best,

All authors

R4 Continued: The results of the noise feature setting are shown below:

From the above results, we can have the following observations:

• With the level of noise increase in the features, the performance of the feature-based methods drops a lot. For example, the FeatProp performs even worse than random selection.
• The proposed SCARCE, which only leverages the graph structure in active learning, can outperform baselines by a large margin.

2. Missing Feature Setting: To further test the resilience of SCARCE under challenging feature conditions, we conducted experiments in a setting where all features are missing. In this scenario, we replaced the original node features with one-hot ID features. We conduct experiments on both Cora and CiteSeer datasets with labeling budgets of 5C, 10C, and 20C using both GCN and APPNP models. The results are shown below:

From the above results, we can have similar findings: While the feature-based methods, such as FeatProp, perform poorly under the missing feature setting, our proposed SCARCE can achieve good performance.

In summary, the proposed method SCARCE can perform as expected when the feature quality is low or missing, but the feature-based active learning methods may perform poorly.

We hope that we have addressed the concerns in your comments, and please kindly let us know if there is any further concern, and we are happy to clarify.

W3 & Q4: Only performing experiments on two GNN backbones undermines the superiority of the proposed framework.

R3: We appreciate your suggestions. We further add two representative GNNs: GAT[2], which leverages the attention mechanism, and GCNII[3], which is a deep GNN. For these two methods, we follow the hyperparameter settings in their original paper. Specifically, for GCNII, we adopt 64 layers. The results on the Cora and CiteSeer datasets with budgets of 5C, 10C and 20 C, are shown below:

From the above results, we can observe that the proposed SCARCE can also work well with both GAT and GCNII backbones. This result demostrate the proposed SCARCE can achieve generally good performance across different state-of-the-art GNN backbones.

[2] Graph attention networks. ICLR'18

[3] Simple and deep graph convolutional networks. ICML'20

Q3: In addition, one advantage of this paper lies in the applicability on featureless networks, which is not tested in this paper either.

R4: Thanks for your suggestion. To verify the effectiveness of the proposed method on low-quality feature cases, we conducted additional experiments in two distinct settings, i.e., Noise feature and Missing feature setting.

1. Noise Feature Setting: We introduced varying levels of standard Gaussian noise to the original features. Specifically, we modified the features as $X = X + k*\epsilon$, where $\epsilon \sim \mathcal{N}(0,1)$, and k takes values from the $[0.1, 0.3, 0.5, 0.7, 0.9]$. This experiment was conducted on the Cora and CiteSeer datasets with budget settings of 5C and 10C, where C represents the number of classes in the dataset. The results are shown in Appendix Section B.3 in our revised paper. For your convenience, we present the results of 5C budgets with GCN and APPNP backbones in Part 3.

Dear Reviewer UJDy,

Thank you for your insightful suggestions. We are pleased to provide detailed responses to address your concerns.

Q1 & W1: There lacks a formal introduction of the notion for fairness at the beginning of this paper. (I would suggest to add a formal introduction about the fairness notion studied in this paper in Section 2, and add a descriptive discussion in the Introduction accordingly.)

R1: In response to your valuable feedback, we have incorporated a comprehensive introduction of the structure fairness issue in both the Introduction and Section 2 of our revised paper. For your convenience, we present the formal introduction to the fairness issue discussed in our paper here:

Label Position Bias & Structural Fairness: In this paper, we use the notion of "Label Position Bias", a critical aspect of performance bias in GNNs. This bias arises when the performance of a GNN model varies for nodes based on their proximity to labeled nodes in the graph.[1] Formally, in a graph G, with the set of labeled nodes $V_L$, and unlabeled nodes $V_U$, a GNN model trained on $V_L$ may exhibit varying performance for two nodes $i, j \in V_U$ based on their "structural distance" to $V_L$. A key metric we use to measure this distance is the Label Proximal Score $LPS_{i} = \sum_{j \in V_L} P_{ij}$, where P is the personalized PageRank matrix. The LPS can well quantify the proximity of unlabeled nodes to labeled nodes and a higher LPS score typically correlates with better model performance for that node [1]. [1] also found the low variance of the LPS score, which indicates all the nodes have a similar "distance" to the labeled nodes, can mitigate the label position bias and improve the performance fairness of GNNs. As a result, we use the variance of the LPS score of each node as the measure of structural fairness.

Measuring Performance Fairness: To quantify performance fairness, we categorize nodes into different sensitive groups based on their LPS scores. For each group, we calculate the average accuracy of the GNNs and use metrics such as Standard Deviation to measure the performance disparity across these groups.

[1] Towards Label Position Bias in Graph Neural Networks, NeurIPS'23

Q2 & W2: Despite the discussion on scalability, this paper does not perform any experiments on large-scale network datasets.

R2: To verify the scalability of the proposed method, in addition to the OGB Arxiv dataset used in our paper, we have conducted extensive experiments on the OGB Products dataset, which contains over 2.4 million nodes. We conduct experiments with the labeling budgets of 5C, 10C, and 20C, where C is the number of classes. The results of the OGB Products dataset with GCN and APPNP backbones are shown below:

Please note the GraphPart method takes more than 24 hours, and we treat it as out of time (OOT).

The results from our experiments on the large-scale OGB Products dataset clearly demonstrate the efficacy of our proposed SCARCE method. Notably, SCARCE achieves high accuracy with significantly fewer labeled nodes compared to standard training splits. For instance, while the standard split typically uses around 200,000 nodes for training, SCARCE requires only 940 labeled nodes to attain accuracies of 74.43/(75.64) and 76.57/(76.62) for the GCN and APPNP models, respectively, where the value in the $(\cdot)$ represent the accuracy of the standard split. This underscores SCARCE's effectiveness in active learning, particularly in large-scale graph neural network applications.

Dear Reviewer UJDy,

We would like to express our sincere gratitude to you for reviewing our paper and providing valuable feedback. Could we kindly know if the responses have addressed your concerns? If there are any further questions, we are happy to clarify. Thank you.

Best,

All authors

Thanks for the detailed rebuttal. Most of my concerns have been addressed and I have my score raised.

R3 Continued: The results of the noise feature setting are shown below:

From the above results, we can have the following observations:

• With the level of noise increase in the features, the performance of the feature-based methods drops a lot. For example, the FeatProp performs even worse than random selection.
• The proposed SCARCE, which only leverages the graph structure in active learning, can outperform baselines by a large margin.

2. Missing Feature Setting: To further test the resilience of SCARCE under challenging feature conditions, we conducted experiments in a setting where all features are missing. In this scenario, we replaced the original node features with one-hot ID features. We conduct experiments on both Cora and CiteSeer datasets with labeling budgets of 5C, 10C, and 20C using both GCN and APPNP models. The results are shown below:

From the above results, we can have similar findings: While the feature-based methods, such as FeatProp, perform poorly under the missing feature setting, our proposed SCARCE can achieve good performance.

In summary, the proposed method SCARCE can perform as expected when the feature quality is low or missing, but the feature-based active learning methods may perform poorly.

We hope that we have addressed the concerns in your comments, and please kindly let us know if there is any further concern, and we are happy to clarify.

Dear Reviewer BDeb,

We appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns.

Q1: There are concerns regarding the fundamental motivation behind active learning. While the primary motivation for active learning lies in the difficulty of obtaining high-quality labels in real-world scenarios, the iterative addition of labels for learned target nodes during the optimization process raises doubts about the original motivation. This creates some contradiction as it suggests that labels for target nodes might be easy to obtain.

R1: Thank you for pointing out this concern. We would like to clarify that the fundamental motivation behind active learning is that we want to maximize the model's performance within a limited labeling budget. Due to the difficulty of obtaining high-quality labels, we usually assume the samples are labeled by human experts (often called “oracle”), which can be expensive and time-consuming. Therefore, we usually set a labeling budget to constrain the number of samples that can be labeled by human experts.

In active learning, there are primarily two settings: iterative [1][2] and one-step [3][4]. In the iterative setting, as you mentioned, we ask human experts to label a small number of samples and then train a model based on these samples in each iteration. Afterward, we use the learned model to select some new samples (for example, samples with low confidence based on the model) and ask human experts to label them. This process is repeated until the limited budget is reached. Conversely, in the one-step active learning setting, which is the focus of our work, all the labels are obtained at once within the set budget. This approach avoids the resource-intensive process of training the model multiple times. However, for both settings, the effects of human experts are the same as the number of labeled samples is the budget. Therefore, it does not imply that obtaining labels is easy.

[1] An analysis of active learning strategies for sequence labeling tasks.

[2] Active learning for graph embedding.

[3] Active learning for graph neural networks via node feature propagation.

[4] Partition-based active learning for graph neural networks.

Q2: The improvement compared to baselines seems not statistically significant.

R2: We have conducted the t-test between our proposed SCARCE and the best baseline model across each dataset and budget setting. The p-value less than 0.05 usually indicates that the improvement is statistically significant. In our paper, we have marked results that are statistically significant with a red asterisk (*) in Tables 1 and 2 for clear reference. For your convenience, we also present partial results of the GCN model here:

From the results, the majority of our improvements over baseline models are indeed statistically significant.

Q3: They argue that existing methods heavily rely on the quality of initial node features while the proposed framework can mitigate this problem. However, there lack of experimental support. The features of datasets seem typical, lacking any characteristics such as unavailability and noise. There is a need for a quantifiable evaluation to support this point.

R3: Thank you for this great suggestion. Following your suggestion, we conducted additional experiments in two distinct settings to demonstrate the superiority of the proposed SCARCE.

1. Noise Feature Setting: We introduced varying levels of standard Gaussian noise to the original features. Specifically, we modified the features as $X = X + k*\epsilon$, where $\epsilon \sim \mathcal{N}(0,1)$, and k takes values from the $[0.1, 0.3, 0.5, 0.7, 0.9]$. This experiment was conducted on the Cora and CiteSeer datasets with budget settings of 5C and 10C, where C represents the number of classes in the dataset. The results are shown in Appendix B.3 of our revised paper. For your convenience, we present the partial results of 5C budgets with GCN and APPNP backbones in Part 2.

Dear Reviewer BDeb,

We would like to express our sincere gratitude to you for reviewing our paper and providing valuable feedback. Could we kindly know if the responses have addressed your concerns? If there are any further questions, we are happy to clarify. Thank you.

Best,

All authors