BANGS: Game-theoretic Node Selection for Graph Self-Training

Q1. CaGCN is not considered a SOTA calibration model. Could the authors compare the performance between BANGS and GATS [2]? While GATS does not include a self-training experiment, it could likely be adapted to a pseudo-labeling framework, similar to CaGCN. Q2. Comparison with consistency regularization approaches, such as [3], is highly recommended, as the current baselines are all pseudo-labeling methods.

Response: Thank you for useful suggestion. We have conducted the experiments as per your suggestions, and presented the results in Table 2, with best result in bold, and the second best italicised.

We have adapted GATS [2] for self-training in our framework like Conf(Cal). The hyperparameters are set as the same as others. Though GATS is a more advanced technique than CaGCN and ETS, it performs well on Citeseer but does not outperform BANGS in other datasets. This again shows that, though calibrated confidence is an important part in our framework, our selection strategy plays a significant role as well. We also add the consistency regularization approach GRAND[3]. We use the default hyperparameters from their codebase in github. Our method outperforms GRAND in most of the settings.

Table 2. Comparsion of our method with additional baselines.

Thank you for your detailed reviews and suggested experiments. We have addressed them below.

W1. BANGS requires a confidence calibration model, which further increases the computational costs. Additionally, the authors do not provide a running time analysis on the Flickr, a large-scale dataset; the results are selectively reported on small- or medium-sized datasets. Although the method is theoretically well-founded, its practical utility seems to be limited due to the high computational burden.

Response: Thanks for the suggestions. In the table below, we compare running time and test performance of our method with the raw model and best baseline, CPL, on the same setting as described in Section 4.1. The setting are the same as described in the main paper. We test on Flickr dataset with ~90k nodes and obgn-arxiv [a] dataset with ~170k nodes. We recognize that graph self-training methods often exhibit comparatively smaller improvements on larger datasets. To address this problem, additional techniques, such as contrastive sampling [b], may be incorporated as a future direction.

Table 1. Running Time and Accuracy Comparsion of Flickr and obgn-arxiv Dataset.

[a] Wang, K., Shen, Z., Huang, C., Wu, C. H., Dong, Y., & Kanakia, A. (2020). Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1), 396-413.

[b] Zhou, Z., Shi, J., Zhang, S., Huang, Z., & Li, Q. (2023). Effective stabilized self-training on few-labeled graph data. Information Sciences, 631, 369-384.

W2. The most concerning part is the marginal empirical performance. This is particularly noticeable in the ablative study, where the performance gap between Conf (Cal) and BANGS (Uncal) is minimal. Since the calibration model is not this paper's contribution, it is difficult to acknowledge the method's distinct efficacy. This calls into question about whether the high computational complexity of BANGS justifies the gains. Furthermore, the use of calibration model is somewhat hidden from the reader, only becoming clear in the experimental setting paragraph. For a paper that emphasizes empirical performance, it is critical to clearly identify the impactful components in the main text.

Response: We understand your concern. Admittedly, confidence calibration is an important componement that could further enhance the performance of framework. We put it into a section in experiment part for the following reasons: 1) first, we want to keep a clear storyline in the methodology part -- caliration methods are not the main contribution of our work; 2) moreover, we think graph calibration is a general and foundamental problem in graph learning, due to unmatched prediction probability estimation.

We argue that the close performance of Conf (Cal) and BANGS (Uncal) can not undermine the contribution of our framework. It only justify that both calibration and game-theoretic selction are indispensible part of our method. Specifically, our utility function estiamtion $\hat{U}$, entropy over all unlabeled nodes, is closer to ground-truth $U$, when prediction probability is accurate. That is why removing confidence calibration can lead to significant performance drop. Furthermore, Conf (Cal) is nearly equivelant to the best baseline methods CPL, but calibrated. It still cannot outperform our method in most datasets, and a case study is provided in Appendix E.2.

W3. The authors’ claim that "previous approaches all suffer from independent selection" (in introduction) may be overstated. For instance, CaGCN [1] propagates node confidence across the graph structure, reflecting combinatorial interactions through multi-hop neighbor consideration during calibration.

Response: Thank you for pointing this out. We will improve the sentence as follows:

"Most of the previous approaches suffer from independent selection."

Thank you for the interesting comments and positive reviews.

1. Considering the reported standard deviation of the experimental results, the improvements on some datasets appear to be marginal, such as on the Flickr dataset.

Response: Thank you for pointing this out! Note that our method achieves best results in most of the setting.

In the table below, we have performed additional experiments. We compare running time and test performance of our method with the raw model and best baseline, CPL, on the same setting as described in Section 4.1. The setting are the same as described in the main paper. We test on Flickr dataset with ~90k nodes and obgn-arxiv [a] dataset with ~170k nodes. We observe that graph self-training methods often exhibit comparatively smaller improvements on larger datasets. To address this problem, additional techniques, such as contrastive sampling [b], may be incorporated as a future direction.

Running Time and Accuracy Comparsion of Flickr and obgn-arxiv Dataset.

[a] Wang, K., Shen, Z., Huang, C., Wu, C. H., Dong, Y., & Kanakia, A. (2020). Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1), 396-413.

[b] Zhou, Z., Shi, J., Zhang, S., Huang, Z., & Li, Q. (2023). Effective stabilized self-training on few-labeled graph data. Information Sciences, 631, 369-384.

2. Experiments are conducted only on homophilic graph datasets. It would be better if the performance of the method on heterophilic graph datasets could be provided, such as Cornell, Texas, and Wisconsin [1].

Response: This is a good point. The current utility function is based on Personalized Pagerank (Definition 3.2), which operates on the assumption that importance is passed along edges. This assumption performs well in homophilic graphs, where similar nodes tend to cluster together. We will consider adapting our method to heterophilic graphs as an interesting future direction.

Thank you for your excellent point about submodularity.

1.One main concern is the rationale behind forming a node set for graph self-training from a submodular optimization perspective. The paper argues that pseudo-labels should be evaluated and fed into the model as a set, contrasting with most existing self-training strategies that evaluate each pseudo-label individually. The justification of the traditional strategy is that adding pseudo-labels to the training set satisfies submodularity, allowing for the use of a greedy strategy to achieve an optimal solution.Does submodular optimization apply to the formation of the node set in this paper? Why this approach is advantageous?

Response: Thank you for this interseting question. Unfortunately, our objective function does not satisfy submodularity property. In graph learning, the logits are predicted by GNN fitted on node features, labels, and graph structure.

Submodularity requires that for each $S \subset T$ and every node $v \notin T$, $U(S \cup v)-U(S) > U(T \cup v)-U(T)$. We can provide a simple counter example to prove that the objective function is not submodular. Consider a graph with node $v_1$,$v_2$,$v_3$,$v_4$, and edge between $(v_1,v_2)$, $(v_2,v_3)$, and $(v_3,v_4)$. Node $v_2$ have two neighbors, Node $v_1$ and $v_3$. For simplicity, consider binary classification, node $v_1$, $v_2$, $v_4$ belong to class 0, and $v_3$ is class 1. Suppose an initial model can predict each node to the right class with 0.8. Let $S = \varnothing$, $T = \{v_1\}$, and $v = v_3$. When adding $v_3$ of class 1, the uncertainty over all other nodes will increase. This is because most GNNs have homophily assumption, and the other nodes are from a different class as $v_3$. Therefore, $U(S \cup v)-U(T)$ will be negative. When we have $T = \{v_1\}$, adding a $v_3$ from class 1 would still raise uncertainty over the unlabeled $v_2$ and $v_4$. But since GNNs aggregate information from neighbors, the influence from $v_3$ of different class is partially offset by $v_1$ of the correct class. Therefore, $U(T \cup v)-U(T) > U(S \cup v)-U(S)$.

Since the objective function is not submodular, our combinatorial solution is more beneficial than independent selection, and the proof is provided in Appendix B.2.

2. In the experiments, the number of pseudo-labels k is fixed. This setting may not be fair for comparisons across different methods. Allowing each baseline to obtain an optimal number of pseudo-labels as they required would provide a more equitable evaluation and potentially yield more insightful results.

Response: To clarify, we have chosen the optimal number of $k$ for baseline methods according to the suggestions provided in the corresponding papers. Current methods either fix the number of nodes selected, or determine the confidence threshold, i.e., selecting nodes with confidence surpassing a given threshold into pseudo-labeled set in each iteration.

• Baseline M3S and DR-GST do not explicitly provide their hyperparameters, so we use their configurations implemented by [1]. The threshold is predetermined for each dataset, e.g., 0.5 for Cora, 0.2 for Citeseer.
• Similarly, for CaGCN, We use their suggested threshold, e.g., 0.8 for Cora, 0.9 for Citeseer. CPL specifies their number of selected nodes, e.g., top 100 for Cora, top 80 for Citeseer.

In conclusion, we belive we have a fair comparion with the baselines with their suggested optimal parameters.

[1] WANG Botao, Jia Li, Yang Liu, Jiashun Cheng, Yu Rong, Wenjia Wang, and Fugee Tsung. Deep insights into noisy pseudo labeling on graph data. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.

Dear Reviewer A5dG,

We would like to kindly follow up and reiterate that we have responded to your concerns regarding submodularity and the problem setting. Specifically, we clarified that our problem is non-submodular. Additionally, we have ensured that all baselines adopt the optimal setting with respect to the number of $k$.

As the discussion phase is nearing its conclusion, we would sincerely appreciate it if you could let us know whether our clarifications and rebuttal have satisfactorily addressed your concerns.

Thank you once again for your valuable time and feedback.

Best regards,

Authors

I still believe that adding pseudo-labels satisfies submodularity in contributing useful information to the model. In other words, incrementally adding pseudo-labels using a greedy strategy is optimal. The issues highlighted in this paper, as you mentioned, likely stem from the imbalanced quantity or distribution of labels, which introduces additional challenges in model training. These challenges could potentially be addressed through constraints or simple adjustments.

In summary, if the relevant statements can be clearly clarified, particularly the reason behind “pseudo-labels should be fed into the model as a set”, I think this paper holds merit and would like to increase my rating score.

Thank you for your positive reviews.

1. The novelty of the studied problem is limited - the authors studied the node selection problem using a novel formulation with mutual information. Given the improvement, how significant is the problem solved?

Reponse: Thank you for raising this point. Our proposed formulation is particularly well-suited for the graph node classification setting. Maximizing mutual information between predicted and ground-truth labels on unlabeled data is a natural and widely recognized objective in graph semi-supervised learning. Moreover, the loss function in graph node classification typically minimizes cross-entropy loss, which can be interpreted as a method to maximize our target: the mutual information between model predictions and true labels. Building on this formulation, we designed a utility function and introduced a scalable, effective approach to achieve this objective. Our experimental results demonstrate notable improvements, underscoring the significance of the problem addressed.

2. The paper relies on a lot on (Wang & Jia, 2023) technically. It would be good to demonstrate the authors' unique contribution in the context of (Wang & Jia, 2023) - is it a straightforward extension of the referenced work? Is this work straightforward extension of the referenced work of (Wang & Jia, 2023)?

Response: The main difference is that, we only consider coallitions of less than size $k$. This is tailered for our setting, as we select $k$ nodes in an iteration. Since we do not need to calculate utility of large coallitions, bounding size also significantly cut sampling cost.

Further, the utility function is tailored for graph. The original utility function in (Wang & Jia, 2023) is the prediction accuracy on test dataset. This is extremely time-consuming, as it requires to add each coallition to psuedo-label set and retrain the model. Our utility function, as shown in Table 7 and 8 in our paper, allows the alogrithm to reach better performance within comparable time with other baselines.

Thank you for your detailed reviews and interesting points. We have clarified the points below.

1. The motivation of the article is unclear and not strong enough. The core work of self-training is to select suitable nodes and assign pseudo-labels. This article focuses on the combinatorial dependencies in node selection; however, the impact of such information on the model's performance is not discussed in depth and lacks supporting experiments.

Response: We agree that the core work of self-training is to select suitable nodes and assign pseudo-labels; and our goal is to select the optimal $k$ nodes. In order to select the suitable node set, dependencies between nodes needs to be considered. We have the followings in the paper to emphasize this point:

• Theoretical justification: We provide a proof regarding why dependency must be considered to select optimal nodes in Appendix B.2.
• Emperical Justification: Moreover, we provide ablation studies in Table 2. Without using Banzhaf value, we observe a significant performance drop for the proposed algorithm. This can jusify the importance of considering combinatorial dependencies in node selection.

Before going to details of our method (Sec 3.1), to emphasize the motivation we will add a discussion based on the above as well as the answer for the next point.

2.Furthermore, I do not see self-training as an interesting research direction; it seems more like a variant of data augmentation to me. Assigning labels to some nodes based on existing information intuitively seems difficult to understand, as it does not clearly lead to new information.

Response: This is a good point. There is a fundamental difference between self-training and data augmentation. Though both can improve model robustness and generalization, self-training is not a variant of data augmentation. Data augmentation focuses on generating new variations of the existing labeled data. Self-training focuses on leveraging the unlabeled data to make the model more effective by adding new labeled examples through its own predictions. There is also research which proves that self-taining can improve upon the initial model with sufficicient unlabeled data [1]. Empirically, we have observed that the prediction accuracy on the test set exhibits an increasing trend across self-training iterations (see Figure 4 in the Appendix).

[1] Zhang, S., Wang, M., Liu, S., Chen, P. Y., & Xiong, J. (2022, April). How does unlabeled data improve generalization in self-training? A one-hidden-layer theoretical analysis. In International Conference on Learning Representations.

3. The article has designed a k-Bounded Banzhaf value to measure the marginal contribution of a node. Does it still satisfy the properties of the Banzhaf value, such as symmetry, additivity, and so on?

Response: Banzhaf value is a semivalue. The only difference between Banzhaf value and our adapted $k$-bounded version one is that we only allow colliations less than size $k$. We still satisfy dummy player, symmetry and linerity as the original Banzhaf value.

4. In Section 3.2 of the paper, the ground-truth utility function and the noisy utility function are mentioned. How is the ground-truth utility function calculated?

Response: Thank you for pointing this out. The ground-truth utility is the information gain (reduced uncertainty) over all unlabeled nodes with ground-truth student model logits $\tilde{X}$, i.e., $\hat{U}$(S) = O(Softmax($\tilde{X}$(S))), similar to Equation 4.