Research map / Graph learning / GNN architectures
BANGS: Game-theoretic Node Selection for Graph Self-Training
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BANGS, a game-theoretic (k-bounded Banzhaf value) node selection method for graph self-training that scores candidate pseudo-labels by conditional mutual information estimated via PPR feature propagation.
Problem
Graph self-training selects pseudo-labeled nodes by ranking confidence independently, ignoring combinatorial dependencies between nodes and offering only a local view of the data distribution.
Approach
Formulate node selection as maximizing conditional mutual information between ground-truth and predicted unlabeled labels, estimate student predictions via personalized PageRank propagation of labeled/pseudo-labeled logits, and select nodes by k-bounded Banzhaf values computed with maximum sample reuse Monte Carlo, with a theorem on ranking robustness under noisy utility.
Key results
- On Cora, BANGS reaches 84.23±0.62% vs 83.72±0.52% for the second-best method CPL (GCN base, raw GCN 80.82%).
- On LastFM, BANGS reaches 83.27±0.48% vs 80.69±1.11% for CPL, the largest gain among the five datasets.
- With different base models on Cora, BANGS is best for GCN, GraphSAGE and GAT, and second-best for GIN (80.77% vs 81.35% for M3S).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BANGS instead of the strongest listed baseline | GCN graph self-training · Cora | accuracy (%): 83.72±0.52 -> 84.23±0.62* | Helped |
| use BANGS instead of the strongest listed baseline | GCN graph self-training · Citeseer | accuracy (%): 73.63±0.19 -> 73.96±0.29** | Helped |
| use BANGS instead of the strongest listed baseline | GCN graph self-training · PubMed | accuracy (%): 81.16±0.10 -> 81.60±0.34** | Helped |
| use BANGS instead of the strongest listed baseline | GCN graph self-training · LastFM | accuracy (%): 80.69±1.11 -> 83.27±0.48** | Helped |
| use BANGS instead of the strongest listed baseline | GCN graph self-training · Flickr | accuracy (%): 50.10±0.18 -> 50.23±0.25 | Helped |
| add Banzhaf-based node selection (ablation) | BANGS · Cora, Citeseer, PubMed, LastFM, Flickr | accuracy (%): 83.03±0.66 -> 84.23±0.62; 72.75±0.50 -> 73.96±0.29; 78.42±0.61 -> 81.60±0.34; 82.62±0.44 -> 83.27±0.48; 49.98±0.17 -> 50 | Helped |
| add confidence calibration (ablation) | BANGS · Cora, PubMed, LastFM, Flickr | accuracy (%): 83.73±0.43 -> 84.23±0.62; 80.13±0.34 -> 81.60±0.34; 80.77±1.10 -> 83.27±0.48; 50.01 ± 0.26 -> 50.23±0.25 | Helped |
| add confidence calibration (ablation) | BANGS · Citeseer | accuracy (%): 73.64±0.33 -> 73.96±0.29 | Helped |
| use calibrated rather than uncalibrated confidence for node selection | confidence-based selection · Cora, Citeseer, PubMed, LastFM, Flickr | accuracy (%): 83.70±0.56 -> 83.72±0.49; 73.74±0.19 -> 74.02±0.52; 80.00±0.36 -> 80.13±1.16; 80.69±1.11 -> 83.23±0.25; 50.02±0.22 -> 50 | Mixed |
Surprising findings
- Under 5% label noise, the method on Cora generalizes better than on clean labels, per the authors' observation.
- Ablation shows removing the Banzhaf component (top-k from top-(k+100) confident nodes) drops PubMed accuracy from 81.60% to 78.42%, below Conf(Cal).
Limitations
- Assumes pseudo-labels from earlier rounds are never updated and the teacher equals the previous student, a simplified self-training setting.
- Theoretical guarantees rely on assumptions (linear aggregation, ReLU, equal path activation probability) that do not strictly hold for GraphSAGE, GAT or GIN.
- Method is more sensitive to the number of selected nodes per iteration than baselines, per the authors.
Experimental setup
Datasets: Cora Citeseer PubMed LastFM Flickr
Benchmarks: Cora Citeseer PubMed LastFM Flickr
Metrics: node classification accuracy standard deviation over 10 seeds t-test significance
Baselines: Raw GCN M3S CaGCN DR-GST Random selection CPL
Builds on: CPL Banzhaf value GCN ETS calibration
Closest papers by meaning
- Self-Adaptive Graph Mixture of Models (AAAI 2026 · similarity 0.85)
- Decoupled Self-supervised Learning for Graphs (NeurIPS 2022 · similarity 0.85)
- Can Pseudo-Label Be More Reliable? A Simple yet Effective Topology-Aware Graph Self-Training Method (AAAI 2026 · similarity 0.85)
- Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks (NeurIPS 2024 · similarity 0.84)
- Uncovering the Redundancy in Graph Self-supervised Learning Models (NeurIPS 2024 · similarity 0.84)
- HGOT: Self-supervised Heterogeneous Graph Neural Network with Optimal Transport (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.