Attention-based Graph Coreset Labeling for Active Learning

Dear Reviewer,

We would like to express our sincere gratitude for the time and effort you have dedicated to reviewing our work. Below, we provide a detailed response to your comments.

Q1. In the introduction, the authors fail to adequately explain why traditional active learning methods developed for CNNs cannot be directly applied to GNNs, which might diminish the novelty and motivation for the proposed method.

A1. We appreciate your feedback on the introduction. To address your concern, we will revise the introduction to provide a more comprehensive explanation of why traditional active learning methods developed for CNNs are not directly applicable to GNNs.

Traditional active learning (AL) strategies are designed for models that operate on independent and identically distributed (i.i.d.) data. As a result, these methods fail to capture both the graph structure and node features, leading to suboptimal performance when applied to GNNs [1, 2]. Therefore, it is essential to develop graph-based active learning methods that are capable of selecting the most informative samples by considering both node features and the graph structure.

[1] Li Gao, et al. Active Discriminative Network Representation Learning. IJCAI 2018.

[2] Kaushalya Madhawa and Tsuyoshi Murata. 2020. Active Learning for Node Classification: An Evaluation. Entropy 22, 10 (2020), 1164.

Q2. The authors aim to select "truly informative data points" in graph-structured data but do not provide a clear definition or criteria for what makes a data point "informative." A more precise definition of informativeness, with concrete criteria or theoretical support, would be helpful.

A2. The theoretical analysis in the paper aims to support the coreset selection strategy, which focuses on selecting the most informative data that minimizes the loss in the representation space. An informative sample can be defined as follows:

Definition. (Informative Sample) Given the whole sample $\mathcal{V}$ drawn from $\mathcal{G}$, labeled pool $\mathcal{V}_l$ and

unlabeled pool $\mathcal{V}_u$.

We consider the data point $s$ is the most informative sample in $\mathcal{V_u}$ based on the existing labeled pool $\mathcal{V_l}$,

if $\sum_{i \in \mathcal{V}} l (f_{\mathcal{M}(\mathcal{V}_l \cup \{s\} )} (i))$

$< \sum_{i \in \mathcal{V}} l (f_{\mathcal{M}(\mathcal{V}_l \cup \{k\}}(i))$

$< \sum_{i \in \mathcal{V}} l (f_{\mathcal{M}(\mathcal{V}_l }(i))$

when training on GNN model $\mathcal{M}$. Where $l(\cdot)$ is the loss function, $k \in \mathcal{V}_u \setminus \{s\}$. This condition ensures that the model trained with the labeled pool $\mathcal{V}_l$ augmented by the most informative sample $s$ results in the smallest loss, compared to any other unlabeled sample $k \in \mathcal{V}_u$.

Q3. The proposed method uses attention coefficients to capture global influence between labeled and unlabeled nodes. However, I question the reliability of these coefficients, given that initial labels may not provide sufficient supervision for accurate training. Could the authors clarify how they ensure the attention coefficients' accuracy under limited labeled data?

A3. Thank you for pointing out this question. Under the constraint of limited labeled data, achieving reliable attention coefficients is indeed challenging. To address this issue, AGCL introduces new method to select the initial labeled pool through a systematic search.

Structure and Feature-based Initial Pool Selection.

Considering both the features and graph structure, we propagate features among nodes with the layer-wise propagation rule:

$

{\boldsymbol{H}}^{(l+1)}=\hat{\mathbf{A}} {\boldsymbol{H}}^{(l)},

$

where $\hat{**A**}=\hat{\mathbf{D}}^{-1 / 2}(**A**+**I**) \hat{\mathbf{D}}^{-1 / 2}$ is a symmetric normalized adjacency matrix, $\mathbf{I}$ is the identity matrix, $\hat{\mathbf{D}}$ is the corresponding degree matrix of $\mathbf{{A}}+\mathbf{I}$, and $\boldsymbol{H}^{(l)}$ is the hidden node representation in $l^{th}$ layer with ${\boldsymbol{H}}^{(0)}= \mathbf{{X}}$. After $k$ iterations of aggregation, the representation of a node $h_i^k$ captures the structural information within its $k$-hop neighborhood. Then, we select $k$ nodes into the initial pool using the k-medoids method.

Hyperparameter Search for Initial Labels: For the number of initial labels $|s^0|$, we perform a hyperparameter search for each dataset to further achieve reliable attention coefficients. In our experiments, we observed that setting $S^0 = 0.3*B$ is effective for commonly used datasets, enabling the selection of a representative coreset from the unlabeled data.

Dear Reviewer,

We sincerely appreciate your acknowledgment of our efforts to address your initial concerns. We would like to further clarify and expand on the points you raised.

1. The reliability of the attention coefficients.

In our paper, AGCL introduces a Structure and Feature-based Initial Pool Selection method, accompanied by a hyperparameter search strategy, to select initial labels. This approach is grounded in the principle that less but high-quality data can lead to reliable training—an idea encapsulated in the adage "less is more".

This principle has been validated across various domains and tasks. For instance:

• In large language models (LLM), fewer high-quality data points have been shown to suffice for effective pretraining [1, 2] and fine-tuning [3].

• In graph-based domains, studies [4] have demonstrated that a smaller subset of graph data can yield excellent performance for node classification tasks.

In our experiments, AGCL consistently achieves superior performance compared to other graph active learning methods. As shown in Figure 2 (Appendix A.6), AGCL rapidly boosts accuracy in the early stages of training and consistently outperforms baselines as the number of labeled nodes increases.

These results suggest that the attention coefficients in AGCL are indeed reliable for selecting informative samples. AGCL benefits from combining heuristic-based initial label selection with a learned measure for coreset selection, ensuring effective and robust performance.

2. Recent methods.

In the experiments, we compare the proposed AGCL with nine baselines, including recent and widely adopted graph active learning (AL) methods in the graph domain. The effectiveness of AGCL is demonstrated through extensive experiments across diverse data types (homophily and heterophily) and data scales (same-scale and large-scale). Furthermore, we evaluate AGCL against four baselines in the image domain, further highlighting its evident advantages in coreset selection.

We have actively sought to compare AGCL with more recent works, such as Bayesian uncertainty sampling [5] and DOCTOR, which applies the Expected Model Change Maximization (EMCM) principle to GNNs [6]. However, we could not obtain official code for these works, limiting our ability to reproduce their results in the time available. Additionally, these methods still rely on query heuristics, which 1) lack a direct correlation with the expected prediction performance on unlabeled nodes in the final task, and 2) mainly focus on the local graph structure (we will add more discussion in the Related Work section).

If you are aware of additional recent methods related to our study, we would greatly appreciate your recommendations. We are eager to explore further comparisons and discussions to strengthen our work.

Once again, we thank you for your valuable feedback and hope this response adequately addresses your concerns.

[1] Marion, Max, et al. "When less is more: Investigating data pruning for pretraining llms at scale." arXiv preprint arXiv:2309.04564 (2023).

[2] Gunasekar, Suriya, et al. "Textbooks are all you need." arXiv preprint arXiv:2306.11644 (2023).

[3] Zhou, Chunting, et al. "Lima: Less is more for alignment." Advances in Neural Information Processing Systems 36 (2024).

[4] Fu, Sichao, et al. "Finding core labels for maximizing generalization of graph neural networks." Neural Networks 180 (2024): 106635.

[5] Fuchsgruber, Dominik, et al. "Uncertainty for Active Learning on Graphs." arXiv preprint arXiv:2405.01462 (2024).

[6] Song, Zixing, et al. "No change, no gain: empowering graph neural networks with expected model change maximization for active learning." Advances in Neural Information Processing Systems 36 (2024).

Dear reviewer,

We deeply appreciate the time and effort you have dedicated to reviewing our work. Below, we address each of the concerns and questions you raised.

Q1. While the paper demonstrates the method's effectiveness on benchmark datasets, it may not fully address the challenges posed by more complex real-world graphs, which often involve dynamic, evolving structures or noisy data. More diverse, real-world testing would be needed to validate its robustness in various practical settings.

A1. We further demonstrate the robustness of the proposed method on noisy data. Specifically, we simulate noisy data by randomly removing a certain percentage (10%) of the graph node features.

As shown in the table below, we observe that AGCL continues to select informative data to achieve strong performance, especially on the Cora and Citeseer datasets, even in the presence of noise. This demonstrates the method's robustness and its ability to perform well in settings that might better resemble real-world, noisy data scenarios.

Table: The performance of GCN on three citation datasets with different training sets (noise and clear).

Q2. While the theoretical analysis in the paper aims to support the coreset selection strategy by minimizing the loss in the representation space, it doesn't fully explore how the attention mechanism or the architecture of the proposed Attention-based Graph Coreset Labeling (AGCL) model specifically affects these theoretical guarantees.

A2.

Exploring the Intuition Behind AGCL: A Theoretical and Methodological Analysis.

Theoretically, Proposition 4.1 shows that for two testing samples, the one with a smaller distance to the training sample has better prediction performance.

In Lemma 4.1, we extend Proposition 4.1 to the entire dataset and demonstrate that, for two training/labeled sets, a model trained on the set with closer distances to the remaining/testing/unlabeled data—indicating a smaller covering radius—exhibits better performance.

Lemma 4.2 shows the connection between coreset analysis and the attention-based score, specifically, demonstrating the benefit of selecting the coreset based on an explicit metric (representation scores) between the labeled and unlabeled pools in improving expected prediction accuracy.

Building on Lemma 4.1 and Lemma 4.2, Theorem 4.1 states that in data selection, we need to explore samples in the unlabeled pool that have the maximum representation difference from the existing labeled pool in the well-defined representation space.

According to Theorem 4.1, 1) we need to explicitly show the relationship/distance/influence of unlabeled data and labeled data through a measure that relates to final prediction performance, and 2) the measure function needs to capture both feature and complex graph structural information from a global perspective.

Based on our theoretical ananlysis, we propose AGCL, a method that directly explores the correlations between labeled and unlabeled data in the embedding space using an attention-based message-passing strategy. Aside from considering the local structure of the graph, attention-based networks also incorporate global structural information. By learning the influence between one node in the labeled pool and another in the unlabeled pool and mapping it to the attention matrix, we can intuitively select nodes according to attention scores from a global view.

Dear Reviewer,

Thank you for your constructive comments and suggestions. They have been invaluable in helping us enhance the quality and clarity of our paper. Please find our point-by-point responses to your concerns below.

Q1. In the abstract, authors should consider introducing more background information for their research so that readers outside the field can better understand it.

A1. Thank you for your valuable suggestion. We have revised the abstract and the introduction to include additional background information, which will help readers outside the field better understand the context and motivation behind our research.

Q2. Figure 1 can be further improved. Currently, we cannot see a clear model structure and the information that can be expressed is limited.

A2. Thank you for your feedback on Figure 1. We have made adjustments to the figure to improve its clarity and enhance the model structure representation. We will include the updated version in the revised manuscript.

Q3. Do the authors discuss the computational complexity of the proposed strategy in detail (not just a brief discussion) and analyze the time and memory consumption of the model in the experiments?

A3. Table 4 in the paper reports the training time of various graph active learning (AL) methods on the Cora, Citeseer, and Pubmed datasets. From the results, we observe that AGCL achieves significantly faster training times compared to several existing graph AL methods, demonstrating its computational efficiency.

Specifically, AGCL delivers a 3x speedup in training time over AGE on the Cora dataset, and a 2x speedup compared to ACL on the Citeseer dataset. This improvement can be attributed to the streamlined node selection process in AGCL, which effectively reduces the computational overhead associated with more complex selection strategies.

In terms of memory usage, AGCL shows memory consumption of 1034.45 MB and 1496.38 MB on the Cora and Citeseer datasets, respectively. Some methods, such as those based on query heuristics like diversity or density, generally require lower memory usage but tend to incur higher time costs and achieve lower performance. AGCL strikes a balance between memory efficiency and training speed, making it a more scalable solution for various datasets.

Q4. The datasets used by the authors are limited in size, and the only relatively large dataset has only 160,000+ nodes. This does not require experiments, but I hope the author can further explain what problems the proposed strategy will encounter when facing large-scale datasets, or what benefits it will bring?

A4. For large-scale datasets with a large number of graph nodes, connecting each node in the labeled pool to nodes in the unlabeled pool can lead to high memory and computational costs, especially when performing operations like attention mechanisms. The challenge arises from the fact that the complexity of such operations scales with the size of the graph.

To address these computational challenges in large-scale datasets, we propose an approach where the dataset is split into subgraphs or subsets. By partitioning the dataset, we can apply the attention-based core set labeling method within each subset, which allows for more efficient data selection while managing resource consumption. This method helps us handle large-scale datasets without overwhelming computational resources.

Additionally, in Appendix A.6, we demonstrate the application of our selection method on randomly selected subsets of unlabeled images for image classification tasks, further showcasing the scalability of our approach.

Dear Reviewer,

We sincerely appreciate the your time and effort in providing valuable feedback. Below, we have addressed each of the concerns and questions raised.

Q1. While the paper provides a comprehensive experiments over many datasets, as I am not an expert of active learning field, I found it rather confusing to use hyperparameter to search for an initial set S0. From my perspective, the initial labeled set S0 should be within part of the budget B. If hyperparameter search is allowed for S0, I think that implicitly provides exceeding budget to the proposed methods. I assume only the proposed method has such hyperparameter and therefore this leads to a unfair comparison and makes me doubt if the experimental advantage comes from the exceeding budget.

A1. Please allow us to clarify the setting of initial set $S^0$:

1. Initial Set Within Budget: It is correct that the initial labeled set $S^0$ should be part of the overall budget $B$. In our experiments, although we perform a search to determine $S^0$, we ensure that its size remains smaller than the final budget $B$. This ensures consistency across all baseline methods, where the same size of the training set is used to enable a fair comparison.

2. Purpose of Initial Set Search: The search for the initial set $S^0$ is specifically designed to facilitate effective training for the subsequent coreset selection process, i.e., attention-based message-passing and data selection. The initial labels in $S^0$ are chosen to provide sufficient supervision for early training stages, ensuring that reliable attention coefficients are obtained. These coefficients are essential for capturing the global influence between labeled and unlabeled nodes, guiding the selection of informative data points from the unlabeled pool. In our experiments, we observed that setting $S^0 = 0.3*B$ is effective for commonly used datasets, enabling the selection of a representative coreset from the unlabeled data.

Q2. I am not really convinced on the theoretical analysis. In the original CNN paper regarding coreset analysis, the paper explicitly mentioned the data is iid, which is not the case for the graph data as the paper discussed in the introduction. Graph data is non-iid and there is no attempts on resolving such issue in the theoretical analysis. Proof of the proposition 4.1 is also not satisfying. for d(h,hv)<d(h',hv)<rv, what exactly do we know about h and h' in this case. Simply saying that h' = h+d doesn't provide any useful information for obtaining Eq 11. One can simply consider otherwise h = h'+d and obtain a reversed relation for Eq 11. Also, the paper states according to assumption 1, the dL/dh part is basically 0, then Eq 11 really doesn't provide any information from what I understand.

A2. We appreciate the opportunity to clarify the points raised regarding theoretical analysis, especially Proposition 1 and its implications. Below, we provide further explanations to resolve any misunderstandings:

1. Applicability of Proposition 1 to Non-i.i.d. Graph Data:

Proposition 1 is formulated for abstract points in the embedding space, where the distances $d\left(u, v\right)$ and $d\left(u^{'}, v\right)$ are calculated based on the learned embeddings.

Importantly, because Proposition 1 operates in the embedding space, it is agnostic to whether the original data is i.i.d. or non-i.i.d. In the case of graph data, the embeddings encode dependencies arising from graph structures. Thus, while the input graph data is non-i.i.d., the results of Proposition 1 remain valid, as they are based on the transformed embedding space, which already incorporates graph-specific information.

We will explicitly mention in the revised manuscript that Proposition 1 is suitable for both i.i.d. data and non-i.i.d. graph data, as it relies on the embedding space rather than the raw input data.

2. Clarification of the Constraints $h = h' + d$: Based on the condition $d(h, h_v) \leq d(h', h_v) \leq r_v$, we deduce that $h$ is closer to $h_v$ in the embedding space, with $h_v$ as the center. This implies that $h' = h + d$, where $d > 0$ represents a positive perturbation along the distance metric.

The reversed case, $h = h' + d$, is not valid in this context because it would contradict the ordering of distances, i.e., $d(h, h_v) < d(h', h_v)$. We will explicitly add the constraint $d > 0$ to avoid ambiguity and clearly explain why the relationship $h' = h + d$ holds under this condition.

Dear Reviewer,

Thank you once again for your thoughtful and constructive feedback.

In the updated manuscript, we have revised the proof of Proposition 4.1 and included additional experimental results on other GNN models (highlighted in blue). We hope these updates address your concerns and provide further clarity.

As the discussion deadline approaches, we would greatly appreciate any additional suggestions you might have for improving our work. Your feedback is invaluable, and we sincerely welcome your guidance.

If our responses have sufficiently addressed your concerns, we kindly hope you might reconsider the rating. Thank you again for your insightful review and thoughtful consideration.

Best regards,

The Authors