BANGS: Game-theoretic Node Selection for Graph Self-Training
Graph Semi-supervised Learning;Graph Self-training;Game Theory Application
Yes
No ethics review needed.
See the weaknesses.
This paper introduces a new direction in graph self-training by integrating conditional mutual information into the pseudo-labeling process. The proposed method may have the potential to improve the effectiveness of semi-supervised learning on graphs, particularly in scenarios where node dependencies play a significant role. The empirical studies are solid.
This paper investigates the problem of graph self-training, which is a main strategy in semi-supervised graph learning. The study specifically addresses the combinatorial dependencies between nodes for pseudo-label selection. To tackle this challenge, the authors propose a novel framework that unifies the labeling strategy with conditional mutual information to guide the selection of pseudo-labels. Unlike traditional approaches that provide a sorted list of labels, the proposed method forms a node set for graph self-training. The proposed method is validated on many real-world datasets.
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?

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.
Yes
No ethics review needed.
1. 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?
2. 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?
The structure of this article is clear and easy to understand. The experiments are detailed, and the analysis of the results is also quite clear. Moreover, the code has been made publicly available.
This paper focuses on the problem of graph self-training and argue that the combinatorial dependencies between nodes have a very strong relationship with the pseudo-labeling strategy which has been ignored now. To overcome this problem. this paper propose a novel framework that unifies the labeling strategy with conditional mutual information as the objective of node selection. This method grounded in game theory selects nodes in a combinatorial fashion and provides theoretical guarantees for robustness under noisy objective.
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.

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.
Yes
No concerns.
No ethics review needed.
Given the improvement, how significant is the problem solved?

Is this work straightforward extension of the referenced work of (Wang & Jia, 2023)?
The writing is clear. 

The discussion is comprehensive.
The authors addressed the limitations in graph self-training by introducing a comprehensive framework that systematically tackles the node selection problem using a novel formulation with mutual information. The proposed BANGS is a game theory-based method with the
utility function based on feature propagation.
The novelty of the studied problem is limited - the authors studied the node selection problem using a novel formulation with mutual information. 

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?
Yes
N/A
No ethics review needed.
Please refer to the Weaknesses.
1. It is interesting to introduce techniques from the co-operative game theory into graph self-tranining, taking into acount the combinatorial.
2. The paper is well-organized and literature review is conducted well.
3. The paper provides a theoretical analysis of the proposed method.
To address the issue that existing pseudo-labeling strategy ignores the combinatorial dependencies between nodes, this paper introduces a framework that unifies the labeling strategy with conditional mutual information as the objective of node selection, instead of predicting pseudo labels.
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.
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].

[1] Geom-GCN: Geometric Graph Convolutional Networks, ICLR 2020
Yes
No ethics review needed.
**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.
- The paper's motivation is clear and well-presented.
- The introduction of Banzhaf values to incorporate node interdependencies is novel and unique.
- BANGS is grounded in a profound theoretical foundation, which makes the proposed method more solid.
This paper presents a new node selection method for graph self-training. The authors leverage PPR-based feature propagation to estimate a utility function aimed at information gain. To address node interdependencies in graph-structured data, the authors employ Banzhaf values, allowing for combinatorial modeling of node influence during the node selection phase.
**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.

**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.

**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.

---
**References**

[1] Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration, NeurIPS 2021

[2] What Makes Graph Neural Networks Miscalibrated?, NeurIPS 2022

[3] Graph random neural networks for semi-supervised learning on graphs, NeurIPS 2020
We propose a game-theoretic node selection framework for graph self-training.
@inproceedings{
anonymous2024bangs,
title={{BANGS}: Game-theoretic Node Selection for Graph Self-Training},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=h51mpl8Tyx},
note={under review}
}
Graph self-training is a semi-supervised learning method that iteratively selects a set of unlabeled data to retrain the underlying graph neural network (GNN) model and improve its prediction performance. While selecting highly confident nodes has proven effective for self-training, this pseudo-labeling strategy ignores the combinatorial dependencies between nodes and suffers from a local view of the distribution.
To overcome these issues, we propose BANGS, a novel framework that unifies the labeling strategy with conditional mutual information as the objective of node selection. Our approach---grounded in game theory---selects nodes in a combinatorial fashion and provides theoretical guarantees for robustness under noisy objective. More specifically, unlike traditional methods that rank and select nodes independently, BANGS considers nodes as a collective set in the self-training process. Our method demonstrates superior performance and robustness across various datasets, base models, and hyperparameter settings, outperforming existing techniques. The codebase is available on https://anonymous.4open.science/r/BANGS-3EA4.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Graph Semi-supervised Learning Graph Self-training Game Theory Application
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/9ac1945f127c2def70a591660284c6f05c5b4484.pdf
learning on graphs and other geometries & topologies
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
BANGS: Game-theoretic Node Selection for Graph Self-Training
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission