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

Authors: Fangxin Wang, Kay Liu, Sourav Medya, Philip S. Yu
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Semi-supervised Learning, Graph Self-training, Game Theory Application

Abstract:
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://github.com/fangxin-wang/BANGS.

Decision: accept (poster)
Reviewer scores: 6, 5, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1730483444352

thread_type:
official_review

<thread_object>
creator: reviewer_onsd

<content>
summary:
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.

strengths:
- 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.

weaknesses:
**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

questions:
**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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730645003336

thread_type:
official_review

<thread_object>
creator: reviewer_v2uf

<content>
summary:
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.

strengths:
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.

weaknesses:
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

questions:
Please refer to the Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699180426

thread_type:
official_review

<thread_object>
creator: reviewer_g53d

<content>
summary:
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.

strengths:
The writing is clear. 

The discussion is comprehensive.

weaknesses:
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?

questions:
Given the improvement, how significant is the problem solved?

Is this work straightforward extension of the referenced work of (Wang & Jia, 2023)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730720945243

thread_type:
official_review

<thread_object>
creator: reviewer_ehco

<content>
summary:
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.

strengths:
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.

weaknesses:
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.

questions:
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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721082111

thread_type:
official_review

<thread_object>
creator: reviewer_a5dg

<content>
summary:
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.

---
After rebuttal, I raise my rating from 5 to "6: marginally above the acceptance threshold."

strengths:
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.

weaknesses:
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.

questions:
See the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732078669377

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank the reviewers for their valuable feedback, insightful comments, which have helped us further clarify and enhance our work. A comprehensive point-by-point response to the reviewers' comments is presented below.  The *major additional changes* are listed below.

* **Additional experiments:** We have incorporated all of the additional experiments requested by the reviewers. These include running time and performance on larger graphs, and comparisons with additional baseline methods.
* **Other discussions:** We have undertaken a series of discussions, which include the following aspects: 
    1. The non-submodularity nature and the necessity of considering dependencies in the node selection problem.
    2. Clarifications on experimental settings, the role of the calibration method, and other details.
    3. Discussion on extended application in other settings, e.g., large-scale graphs and heterophilic graphs.

We hope these will satisfactorily address the concerns raised by the reviewers and elevate the overall quality of our work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes BANGS, a novel framework that unifies the labeling strategy with conditional mutual information for graph self-training. The problem is interesting. The experiments are comprehensive and solid. Sufficient theoretical analysis is provided. The presentation is good. Several issues need to be addressed to improve the paper, such as unclear motivation, a lack of sufficient discussion of existing work (Wang & Jia, 2023), and marginal improvement. Reviewers are generally positive about this work.