BANGS: Game-theoretic Node Selection for Graph Self-Training
Authors: Fangxin Wang
Kay Liu
Sourav Medya
Philip S. Yu
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Semi-supervised Learning
Graph Self-training
Game Theory Application
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a game-theoretic node selection framework for graph self-training.

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.

Published as a conference paper at ICLR 2025
BANGS: GAME-THEORETIC NODE SELECTION FOR GRAPH SELF-TRAININ
Fangxin Wang, Kay Liu, Sourav Medya, Philip S. Yu
Department of Computer Science
University of Illinois Chicago fwang51, zliu234, medya, psyuêuic.edi edu
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 confi- dent nodes has proven effective for self-training, this pseudo-labeling strategy ignores the combinatorial dependencics between nodes and suffers from a lo- cal view of the distribution. To overcome these issues, we propose BANGS, novel framework that unifies the labeling strategy with conditional mutual in- formation as the objective of node selection. Our approach-groundeeee grounderrdddddd in game theory-selects nodes in a combinatorial fashion and provides theoretical guar- antees for robustness under noisy objective. More specifically, unlike traditional methods that rank and select nodes independently. BANGS considers nodes as collective set in the self-training process. Our method demonstrates superior performance and robustness across various datasets, base models, and hyperpa- rameter settings, outperforming existing techniques. The codebase available on https: / /et:://gitttt github........ com fwwpxfancxiiao wawggg/nnwng////noo BANGS
INTRODUCTION AND RELATED WORK
Self-training is a widely adopted strategy in semi-supervised graph learning (Lee et al., 2013) to transform weak initial model into stronger one (Frei al. 2022). This approach enhances the base model's performance with reduced labeling effort and ensures the model's robustness against noisy or drifting data (Carmon et al. 2019 Wei et al., 2020). The iterative method is common tech- nique in self-trand foff-traiingg, where an initial teacher model trained on labeled data generates pseudo- labels for the unlabeled data. A student model is then trained to minimize empirical risk using both the labeled and pseudo-labes labeled data. Subsequently, the student model takes the role of the teacher, updating the pseudo-labels for the unlabeled data. This iterative process is repeated multiple times to progressively improve the final student model.
Existing research in graph self-training mainly focuses on solving three different aspects of the prob- lem. First, confirmation bias, which refers to the phenomenon where the model overfits to incorrect pseudo-labels, is considered the main reason for the underperformance of naive self-training (Arazo) let al.] 2020). To tackle this issue in graph setting, current works generally rely the confidence, ie.. probabilities of the most likely class, to select nodes for pseudo-labels. Common strategies include selecting the top nodes (Sun al., 2020 Botao al., 2023), nodes with confidence surpassing a given threshold (Wang et al. 2021; Liu et al.) 2022a). Second, confidence calibration refers to aligning the confidence of model predictions with the actual likelihood of those predic- tions being correct. Due to the neighborhood aggregation mechanism of Graph Neural Networks (GNNs), GNNs are often under-confident (Wang al., (021), which may lead to nodes with cor- rectly predicted labels being excluded from the selection set. Therefore, GNN self-training is an important downstream task of GNN calibration, and the self-training performance is utilized as an evaluation metric of calibration (Liu et al. 2022b Hsu et al. 2022 Li et al. 2023). Third, infor- mation redundancy, a concept from active learning (Li al. 2024). has an important role in graph self-training. Nodes selected solely based on high confidence often carry similar information, which can lead to slow convergence and biased learning in the student model, even when the labels are cor-
rectly predicted. To address this, Liu et al. (2022a) select and pseudo-label high-confidence nodes

---

Published as a conference paper at ICLR 2025
but reduce the weight of low-information nodes in the training loss to mitigate the redundancy in post-hoc process. Similarly, as a pre-processing step. Li et al. (2023) employs mutual information maximization (Velickovic al. 2019) to select more representative unlabeled nodes from their local neighborhoods.
All the works described above suffer from few key limitations.
(1) Non-unified methods: Graph self-training is a sequential decision problem with multiple compo- nents, e.g., the selection and label criterion, the design of the teacher and the student model training framework. Due to the complexity of self-training problem, current works tend to treat these issues by proposing individual frameworks with different focuses.
(2) Independent and iterative selection: The self- self-training strategies require to use set of points for pseudolabels. Most current graph self-training strategies only select nodes by ranking them in- dependently based on some value such as confidence. The node selection process is a combinatorial problem, where the dependency between the candidate nodes is important in graphs.
(3) Local view of distribution: In each iteration, the student models learn from only labeled and pseudo-labeled data. Generalization over the entire distribution is hampered by the noisy or incor- rect pseudo-labes and possible distribution shifts.
Our contributions. Towards this end, we address these limitations by designing a framework that unifies several key insights for self-training Our contribution can be summarized as follows.
Novel formulationn To systematically address the graph self welf-training problem, we propose a novel objective for node selection based on the conditional mutual information. We demon- strate that this objective can be approximated using predictions on unlabeled samples, and leverage the feature influence from already labeled nodes estimate the predictions of the student model for unlabeled samples.
Novel framework with theoretical support. We introduce a game-theoretic framework, BANGS, which incorporates our designed objective as utility function and select nodes in a combinatorial manner. We also show the limitations and non-optimality of independent selection, meanwhile providing theoretical support that BANGS can optimally select node sets even under a noisy utility function.
Experiments. Experimental results validate the effectiveness of BANGS across various datasets and base models. By theoretically linking random walk and feature propagation, we enhance the scalability of our approach. Additionally, we demonstrate the effectiveness of BANGS under noisy labels and varying portion of training data.
PROBLEM DEFINITION
Consider graph containing a size-N node set V where vú denotes the i-th node in G. X and A denote the feature and adjacency matrix respectively in G, where 2, represents the feature vector of the i-th node. Ar,; the i-th row and j-th column element A, represents whether i-th node and j-th node is connected by an edge. We consider three different sets of nodes based on the labels: labeled nodes V', pseudo-labeled nodes V", and unlabeled nodes V". We denote the ground truth and labels of node 2; as y and ÿJ respectively. The node labels are from a set of C' classes, i.e. Vi, 9: E 21, 2, ..., C). Table 4 provides an overview of the frequently used notations in this paper along with their corresponding explanations.
Self-training. In the iterative self-training procedure, the idea is to start with training teacher model fo (at O-th step) with g = Initially, at 0-th step, the set of nodes with pseudo labels is empty, i.e., V2 0. The teacher model Jo generates pseudo-labels for all nodes in Vy At each iteration r E {1,... Rt). a subset of the unlabeled set 7リ- in the previous step, Vp' is selected based on specific criteria. Thus, the pseudo-labeled set at r-the step becomes VP = U'''' and unlabeled set V = Vy Ve The pseudo-labels for these newly added samples are decided by the teacher model f. Subsequently, at the r- step, the augmented V along with the originally labeled nodes y are used to train a new student model fr. which uses additional pseudo-labels to improve its performance. In our setting, the student model fr in the r-th step is utilized as the teacher model in the (r + 1)-th step, allowing the framework to iteratively refine pseudo-labele based on the student model's improved understanding. We use step, round, and iteration interchangeably.
where y denote the ground truth labels of V c V.
2

---

Published as a conference paper at ICLR 2025
In previous self- self-training procedures, the goal for the student model f. round is to minimize the loss function C, U 1 This loss captures the classification error of fr in predicting only the currently available labels, including y' for V and -ー for V Note that y' is the ground-truth labels, while Dy' C .ーー is predicted and determined by the corresponding teacher model Ss for all S r-11. Minimizing this loss function is considered as an approximation of the original goal which to compute the prediction loss over the entire data distribution i... (V), V ~ V. However, the existing self-training frameworks use (V" UVP-1) 1) as an intermediate approximate loss which often deviates from L, due to two major reasons: (i) the noisy pseudo-labels yf- * U.- and (ii) the non-random label selection strategy where the distribution of labeled nodes V U U.V gradually shifts from the underlying distribution V. To mitigate these, we design a framework where the student model learns from the pseudo-labels that not only correct but also help in reducing the uncertainty of the model over the entire data distribution.
Entropy measure of uncertainty. Shannon Entropy H(-) is commonly used measure the Pc log Pe. where Pe the probability of class on S. Besides node set, we also use Entropy to measure the uncertainty of D P. lo Pe. where Pe is the probability for the label of o; being class e (Wang et al., 2024 Zou et al., 2025b). When Pe of unlabeled nodes is estimated from the model predictions rather than being accessed from the ground-truth, H(s)) is refereed to the individual prediction entropy of node 04
uncertainty in a set of labeled nodes S and denoted as: (S) = -
single node Uy: (v;)
Our problem. We aim to quantify the following: After selecting pseudo-label node set in the r-th iteration, how much information do we gain about the unlabeled data? Formally, let [(x1; = H (xx)) H (x1 (x2) denote the expected mutual information (information gain) between variables x1 and X2. In the r-th round, we choose only k nodes to allocate pscudo-labels, Our aim is to select a node set wy of size k. such that the future pseudo-labels (U,') maximize information between 1. the ground-truth labels of unlabeled nodes and the prediction D.- by the student model fr. Mathematically, considering yー-1 and 1²"1 the ground-truth and prediction distribution of the unlabeled data respectively, our goal is as follows:
y.-1,
max VE' CVH
1: V.. S.L. |VP| = k.
(1)
Lemma 2.1. Maximizing the muiual information between unlabeled data distribution and its pre- diction distribution is roughly equivalent to simultuneously maximizing entropy over the unlabeled dataset and minimizing the sum of individual prediction entropy over all unlabeled nodes.
This lemma allows us estimate unknown distribution with samples from data. Therefore, our new objective-whit depends on entropy becomes the following:
max VE' CVH_1
0
H
9. HO" 1997 V 9.),
NEVE
s.t.
VPl k. 1.-1
Σ 11-
VV-1
The proof is in Appendix B.I In other words, to let predicted labels have more information about ground-trutt the first term demands confident prediction on each sample, while the second term encourage diversity of prediction label distribution of unlabeled data. Solving this objective is non- trivial and has specific challenges as follows.
C1. The ground-truth distribution of labels y²-1 is unknown for estimating the problem objective in Equation] [ We estimate it with the unlabeled samples by Equation 2
C2. At the r-th round, we only have the predictions on the unlabeled data from the teacher model, f--1. In Equation? 2 Dー- represents the predictions made by the student model fr. which may be inconsistent when compared to the teacher model's predictions. f, since the teacher model has
not been trained on the newly added labels, i Thus, a key challenge is to estimate the student model's predictions based on the current teacher model efficiently and accurately (Section [.
C3. How do we account for the dependency between D nodes that are being selected during each round? This dependency comes from the combinatorial nature of the objective and the graph how much information the selected nodes collectively provide about the unlabeled ones (Section 3.2
3

---

Published as a conference paper at ICLR 2025
3
OUR METHOD: BANGS
Initialization Model
V V
Teacher Model f
When 3, Banzhaf utility sample set
0c )
0
D
0C
}
A(S) a (1 - (1 +)
2 $
Student Model f
Figure 1: The workflow of BANGS. We utilize the teacher model's predictions to propagate fea- tures from both labeled nodes and candidate set S, estimating the logits of unlabeled nodes and the Banzhaf value of set & (Equation 3.. For simplicity, only the first step of feature propagation is shown. Using Banzhaf values we rank the individual contributions of unlabeled nodes and add the top k into the pseudo-label set. The student model is subsequently retrained using this updated set.
In this section, we introduce our framework BANGS (BAnzhaf value-based Node-selection for Graph Self training), which consists of three major components unifying several concepts for self-training. First, we propose measure the mutual information between labels and predictions through feature propagation from currently available labels and pseudo-labels to all the unlabeled nodes. Second, apply Banzhaf values (Owen 1975) from the co-operative game theory literature to compute the pseudo-label contribution for our self seff-training objective, taking into account the combinatorial dependencies of the nodes (Medya et al.) (2020). Third, provide scalability design and complexity analysis of BANGS. The pseudo-code and implementation details are in Appendix
and E
3.1 FEATURE ESTIMATION WITH PROPAGATION
major challenge in selecting node at round is having access only the teacher model fr-1 but not the student model fr- An alternative is to estimate the true utility (information gain) of selecting the node set v/ train fr using the predictions from f--1- First, we introduce a feature propagation mechanism to estimate the unknown student model predictions accurately and efficiently.
In a L-layer GNN, labeled node en can propagate its label information to l-hop neighbors, / ' L (Wang & Leskovec, 2020 Zou et al. 2025a). Therefore, pseudo-labeling node will influence the distribution and entropy of its neighbor nodes. In ceessage-passing GNNs (Kipf & Welling 2016 Velickovic et al.) 2017). the influence of node
its neighbor v; depends on the graph structure. We measure the influence by computing how much the change in the input feature of node
U/s xz affects the learned hidden feature of node Uy. i.e., xy after 1-step propagation (Xu et al. 2018b).
Definition 3.1 (Feature influence distribution). The influence score of node en on node Ui after step propagation, Ty(i j. 1), is defined as the sum of the absolute values of the expected Jacobian 0x Om: (0) II]. The feature influence distribution of node vy is defined by normalizing over all
matrix
[|E]
nodes that affect node v follows: 1ş(i + j.() E. 1((x)111)
4

---

Published as a conference paper at ICLR 2025
Under certain assumptions, the feature influence magnitude depends only the graph structure and independent of the GNN model architecture, and it can be estimated via random walks.
Assumption 1. The L-layer GNNs have linear and graph structure dependent aggregation mecha- nism, and ReLU activation. All paths in the computation graph of the model are activated with the same probability of success.
Theorem 3.1 (Feature influence computation via random walk). With Assumption ! I + J. L), the influence distribution of any node v, V is nearly equivalent, in expectation to, the L-step random walk distribution on G starting at node Vy.
The proof is in Appendix B.4 Theorem 3.1 implies that the more likely vj walks to v; after
(0) steps, the stronger features z; will influence the final representation z; in L-layer GNN. During the forward propagation, node features are distributed across L steps by the L-layer GNN, while the GNN is also trained via backpropagation. In this process, the gradient flows through the propagation mechanism, effectively accounting for an infinite number of neighborhood aggregation layers during the weight update. When L + oo, the random walk distribution is equivalent to personalized PageRank (PPR) (Gasteiger et al. 2018 2022). Next, using PPR, we estimate the student model output by summing up the feature influence of all labeled Vi, pseudo-labeled nodes and the new selection set Vp at round r.
Definition 3.2 (Output feature estimation with propagation). With Vy' selected, the student model fr logit estimation (V!') = ax II(I(() (1- where a E (0, 1] is a teleportation probability, and E IR NxN is the normalized adjacency matrix with added self-loop. Further, X E IR NxC is matrix that stores prediction logits of the teacher model fr-1: for Uy WUUVP U Vp the j-th
row Xj: stores logits of f--1 for By; otherwise, X,: 0.
We only propagate labeled and pseudo-labeled node logits to simulate back pack-propagation, as the loss function involves only the already labeled nodes in our framework. A theoretical case study on I-layer GNN is provided in Appendix B.5 Based on this definition, we derive the final output feature estimation for the unlabeled nodes by student model fr. which is subsequently processed through the softmax function (Equation (6) followed by the entropy function to produce the final entropy. Then, can easily estimate the conditional mutual information between 0²-1 and y²"1 through Equation 2 This estimation captures the contribution of pseudo-labels to all unlaheled data, providing global perspective and fast approximation without requiring model retraining. Relying on the relation between the PPR and the random walk, the output feature estimation can be implemented efficiently. A detailed complexity analysis is provided in Section
3.2 MODELING INTERDEPENDENCIIE THROUGH BANZHAF VALUES
To select a potentially good labeling set of nodes for self-training, it is crucial to compute the im- portance of the set based on the individual contribution of the nodes towards the final classification objective. However, the confidence of node computed by the model might be dependent on the confidence of other nodes (Liu et al. 2022b). Intuitively, as a generalization, adding a pseudo- labeled node to the labeling set would affect the contribution of its neighborhood nodes. We show that the independent node selection procedure does not provide the optimal solution for Equation both theoretically (Appendix B.2 and empirically (Section
To capture the combinatorial dependency of the contributions of the nodes, we adopt a game theory- based measure, namely Banzhaf value (Wang & Jia 2023 Chhablani et al. 2024).. It assesses the contribution of each player (node) to the success of coalition (node set), by measuring how pivotal their presence is for achieving a specific outcome, i.e., accuracy improvement the next round. As
we only select a set of size k, we define a variant of Banzhaf values where we consider the coalitions of size up to k:
Definition 3.3 (k-Bounded Banzhaf value). The k-Bounded Banzhaf value for node E Vy_ with urility function US)) is defined as:
(bi; U, VH = =
V (U(S - US)).
(3)
where n. Eh
1|-1 denotes the number of all possible coalitions up size k.
5

---

Published as a conference paper at ICLR 2025
Here 8 is subset of nodes of v excluding node v, SUJ, denotes the union set of S and node 24- (S) denotes the utility function of S, which maps the set & to an importance score of the subset S. Breaking down into individual nodes, the value of ( U, 1=-1) measures the marginal contribution of node V/ and can be used to ranks all the candidate nodes.
Designing utility function. Next, we design relevant utility function measure the total contribu- tion of pseudo-labels in S. A common choice for the utility function (S) is the prediction accuracy on random hold-out subset of labeled nodes, which an approximation of the contribution of subset S to the overall accuracy on V (Wang & Jia, 2023). However, this utility function is often neither effective nor efficient. First, the self teafniraining task allows for only a few labels for validation; and second, accessing accuracy requires either retraining the model or approximating the influence function, which time-consuming due to the exponential number of possible combinatorial sets.
To reflect the contribution of a subset to the overall performance in the next round of the self-training procedure, we follow the definition from the previous section. Specifically,
(()) OSSofbmart H (8)) Lcr(Sof Softrar H (V))),
where in the first term, O is illustrated in Equation 2 and prediction logits of unlabeled nodes are estimated through Def 3.22 The second term captures the cross-entropy loss (see LCE in Table between estimated probability and true label for all labeled data, preventing the confirmation bias. The ground-truth utility function (S) is defined in the same form, except using ground-truth student model logits X and not H. Ú()) measures the total information propagated to unlaheled nodes by already labeled nodes V/ U V. and pseudo-labels of sampled set S.
Robust ranking under noisy utility function. Ideally method should preserve the optimal ranking order of nodes even with noisy utility function (-)). Here, the noise arises due to the difference between our estimation H (S) and the ground-truth student model logits X. Let é and & denote the Banzhaf values from the ground truth utility U.) and the approximated (or noisy) utility Ü(), respectively. In the following, we prove that our computation of Banzhaf values preserve the ranking of nodes under noisy utility function (.).
According Def. 3.3 the difference between the Banzhaf value of node v; and bj is given by (U) = ((((1) o(j)), U and Ú will produce reverse order of Banzhaf value for node e and by if and only if D;, (U) < O. We can view U E IR" as vector that maps all coalitions corresponding utility values. Further, using the definition of 6 in Def. 3.3 we can rewrite the following:
k-1
V - 2
Di)(U) =
Σ Thi
A (m)) (U),
(5)
m -
m=1
U(S U vy)] represents the average distinguishability between any unlabeled node v, and By on size m selection sets using the
where A (m)) bi (U)
11 sgv M1 UU us) -
original utility function U.
In the next theorem, we show that when the value of utility between adding e; and uy is sufficiently large, and the estimation error in our utility function is moderate, the ranking of and vy remains
robust even under noisy utility estimation Ü. The proof is in Appendix B.6
Theorem 3.2. When the distinguishability of ground-truth utility between vs and vy on coali- 2 T, and the perturbation util-
tions less than size lo is large enough, minmms-11 (m))
(U)
ity functions small such that || u||, T Em= (6(1) (O)) - x())) 2 O.
k-
( then (is(U)Dez(U)
m-1
Ranking nodes for self-training selection. Recall that our goal is to select a set of k nodes approximated by our utility function Ú. Next we guarantee that our selection of top-k nodes even with Ò is within an enror bound. Let us de- note Top( k) as the top Ao node set ranked with Φ. Based on our objective, we only require
that maximizes the objective Equation 2

---

Published as a conference paper at ICLR 2025
D.,(U)Da,(0) 0 for top-k node v and non-top-k node ey- According to Theorem 3.2 be-
sides 1 S V m=1 (9r m-1 ), we only need minmsk A (m) 4. (U) T for node pairs in Top(o, ,, k). This is a less stricter
{(v, by)lo E Top k), & Top(o, k)} to ensure Top(o, A) condition, which only requires the utility function to distinguish between selected nodes and non- selected nodes, instead of any two nodes.
In conclusion, our Banzhaf value is tailored for the node self-training setting: 1) it adjusts the threshold for the size of coalitions based the number of pseudo-labels to add, and 2) it relaxes the condition for ranking preservation without requiring comparison between all pairs of nodes.
3.3 COMPLEXITY ANALYSIS
We use Maximum Sample Reuse (MSR) Monte Carlo estimation (Wang & Jia 2023) to calculate Equation 3 to speed up node selection. In expectation, (i; U, n, ([s[U((LL;)
(S)),, where S ~ S C - [S = m 1. Draw B samples of node sets independently from distribution, denoted as S {S ..., S.).. In terms of node vt, the samples could be catego- rized into two classes: the samples including 0i Se: {s E S
E 8): and the sam- ples not containing v/, S4i = (S E 0, E S}. Then o(i;U, V) can be approximated by (Msn(;;U,) = [SEi] Esese, US) [ee Eses U(S).
Further, the utility function design involves PPR matrix. The computation of inverse A-1 Def. 3.2 is difficult in space for large graph. We instead use H-step power iteration, Xb) = (1 A A (h-1) + (0) for h S H, which is initialized by x0) = X. The L-layer representation HVV)) = ( is the final estimation.
Total Time and Space Complexity. We provide a detailed analysis in Appendix C The final running time mainly depends on the selection of GNN architecture (e.g.. type, the number of layers) in model retraining, along with Banzhaf sampling number and selected node set size. In practice, the model retraining step usually will take more time than the node selection step. Given I self-training rounds, the total complexity is (VV) the PPR power iteration number, the sample number, and the number of layers, hidden units, and training epochs in training model. We also provide running time analysis in Appendix E
where H, B, L, nu ne denote
The space bottleneck mainly lies in storing and multiplying À with intermediate state (h-1), Since the final logits are added influence from every available labels, it is suitable for batch computing. Further, by storing with sparse matrix, the space complexity at most O [[E"|("*))) at the r-th iteration, where n means the batch of labeled nodes, and E denotes edges connected to / in A.
EXPERIMENTS
In this section, we conduct experiments on 1) comparing our methods and baselines on the base GNN model across different datasets; 2) ablation studies; 3) hyperparameter analysis the number of candidate and selected nodes; 4) robustness under noisy labels, different portions of training data, and different base GNN models. The experimental results demonstrate the effectiveness of our framework, particularly the integration of Banzhaf values and calibration.
4.1 SETTINGS
We test bascline methods and our method on five graph datasets: for Cora, Citeseer, and PubMed YYang et al. 2016), we follow their official split; as for LastFM (Rozemberczki & Sarkar 2020), Flickr (Zeng et al. 2019), we split them in similar portion that training, validation, and test data take 5%, 15%, and 80%, respectively. The base model set to Graph Convolutional Network (GCN) (Kipf& & Welling 2016) by default, while we also include results for other GNN models. The performance is evaluated on the best prediction accuracy of official test data; otherwise, we use all of the 80% unlabeled test data for evaluation. For each experiment, select 10 different seeds and display their mean and standard deviation values. The best and second-bess results are emphasized in bold and with underlines, respectively. More implementation details are in Appendix D

---

Published as a conference paper at ICLR 2025
Table 1: Node classification accuracy (%) with graph self-training strategies on different datasets. Mean, standard deviation, and single-side t-test on our method and second-best methods are demon- strated. Significance levels of 0.10 and 0.05 are indicated by "*" and "**"
Baselines
Dataset
BANGS
Raw
M3S
CaGCN
DR-GST
Random
CPL
Cora
80.82+0.1 14
81,40+0.29
83.06=0.11
83.04+0.38
83.16+0.10
83,72+0.52
84.23=0.62*
Citeseer
70.18=0.27
72.00a0.21
72.84+0.07
72.50:0.26
73.3820.13
73.63+0.15 19
73.96:0.2294
PubMed
78.40=0.11
79.21=0.17
81.1620.10
78.10=0.39
79.48=0.32
81.00+0.24
81.60=0.344*
LastFM
78.07=0.31
79.4920.43
19.60=1.02
79.31
79.42+0.07
10.69
83.27=0.489
Flickr
49.53=0.11
49.73+0.20
49.81=0.28
49.67=0.10
50.10=0.18
50.02=0.22
50.23+0.25
Baselines. We compare our methods with the following baselines.
1) Raw GNN is the base model without self-training: 2) M3S (Sun et al.
2020)
uses deep-clustering
to label nodes and selects top & confident nodes; 3) CaGCN (Wang et al. and selects nodes surpassing a pre-defined threshold; 4) DR-GST (Liu et al.
2021
calibrates confidence
2022a) selects nodes
surpassing a given threshold and reweights pseudo-labels in the loss of training student models with information gain; 5) Random selection shares the same hyperparamters with [BL, et al. 2023) and the nodes are selected randomly; 6) CPL (Botao et al.] 2023) computes the multi-view confidence with dropout techniques and selects the top k confident nodes. We employ cross entropy loss Cover et al. (199T) on the already pseudo-labeled and labeled data as the loss function in model re-training for all methods. For a fair comparison, we select the suggested hyperparameters for all baseline methods, especially in the node selection criterion. For instance, we use the suggested confidence threshold by CaGCN, e.g., 0.8 for Cora and 0.9 for Citeseer. We set the max iteration number as 40, and use validation data to early stop. For node selection, we sample 500 times for calculating Banzhaf values. The two varying hyperparameters are the number of candidate nodes K and selected nodes k in each iteration. The value of k is set as 100 for small-scale graphs, i.e., Cora, Citeseer and PubMed, and 400 for other larger graphs; K ++1100 100.
Calibration. Confidence calibration refers aligning the confidence with the prediction accuracy, such that high confidence nodes have correct labels a high probability. Before node selection, we apply confidence calibration to reduce noise in pseudo-labels and alleviate confirmation bias (Wang eet al.) 2021;; Radhakrishnan et al.) 2024). Further, calibration estimation, which is based on output logits propagation. Here, we use ETS (Zhang et al. 2020) for calibration, except CaGCN for PubMed. We also provide case study on calibration in App.
reduce noise in utility function
4.2 PERFORMANCE EVALCATION
We select a 2-layer GCN as the base model and compared the node classification accuracy using various strategies. Notably, previous methods do not clearly define stopping criterion, instead us- ing the number iterations as a hyperparameter. Therefore, we provide two fair comparisons. (1) Table presents the best test accuracy achieved within the same 40 iterations for all methods. (2) In Table of Appendix I we also report the final test accuracy in the last round based on the number of suggested iterations for baselines. For method, present the test accuracy obtained by early stopping using validation data. Additionally, we performed a t-test to determine whether the mean accuracy of our methods is significantly greater than that of the recond-best method. Significance levels of 00 and 0,05 are marked with "*" and "**" respectively. Our methods consistently outper- form other confidence- based methods across most the datasets. This supports that our framework, BANGS especially combining Banzhaf value and information gain is effective in practice.
4.3 ABLATION STUDIES
In this set of experiments, we explore how different parts of node selection design help enhance per- formance in Table Note that for a fair comparison, all experiments are under the same self-training framework and parameter. We compare with 1) Random selection, and 2) Conf(Uncal)) selecting the top most confident ones using uncalibrated confidence. To show that our performance gain does not depend only confidence calibration, jet al.) (2021) and 4) CoTS) (Hsu et al.] 2022), which also select top confident & nodes but calibrate confidence with CaGCN and GAT, respectively. Compared with CaGCN, GATS advances
compare with both 3) Conf(CaGCN) (Wang
8

---

Published as a conference paper at ICLR 2025
Table 2: Ablation study of prediction accuracy (%) on different datasets.
Dataset
Random
Conf(Uncal)
CaGCN))
ConfIGATS)
BANGS(Uncal)
BANGS(No Banzhaf)
BANGS
Cora
83.1620.10
83.7010.56 56
83.72:0.49
83.7640.1
83.7340.43
83,03=0.66
84.23:0.62
Citeseer
73.38
73.7440.19
74.0240.52
74.18200.38
73.64
72.75=0.50
73.96=0.299
PubMed
79.48:0.32
80.0010.16
80.13411.6
80.25:0.37
80.13++0.34
78.42=0 61
81.60=0.34
LastFM
79.42s0.07
80.6941111
83.2340.25
80.3140.78
80.77&1.10
82,6240.44
83.27=0.48
Flickr
50.10=0.18
50.0240.22
50.00#0.25
49.90=0.32
50.01 + 0.26
49.98=0.17
50.23=0.25
graph calibration method through identifying and addressing multiple miscalibration-relate factors.
Though GATS is not designed for graph self-traning task, we adapt it to the same framework similar Conf(CaGCN); We also explore whether each component contributing to the final combination by removing each component respectively: 4) BANGS(Uncal); our strategy without calibration; 5) BANGS(No Banzhaf): directly selecting the top ie informative nodes from top + 100 confident ones; and 6) BANGS, the proposed strategy.
Banzhaf value is an indispensable part of our methods: without it, the overlap in information propa- gated by previously selected nodes would be ignored. This is supported by our theoretical evidence (please see Appendix [B2 and [366) and the significant decrease in performance our experiments. On the other hand, calibration is effective in lifting the accuracy of both confidence-basee methods and our methods, preventing noisy pseudo-labels from misguiding the training process. Except in Citeseer, method benefits from calibration in getting correct and informative pseudo-labels.
4.4 HYPERPARAMETES ANALYSIS
Figure 2a show analysis of two hyperparameters collectively. In the first set of experiments, we set k. the number of nodes selected in iteration as 0, 5, 20, 50, 100, 200, 300, 400, 500, respectively, where O equals to raw GCN. The candidate nodes for & smaller than 100 is set as 2k, otherwise + 100. The best number of added labels is around 50, with a balance between exploit and explo- ration fewer nodes discourages student model from effectively and efficiently learns pseudo-label information, while more nodes tend to bring noisy and biased information to misguide model before generalizes well. Though our method is more sensitive to the number of selected nodes in each iteration, the performance always outperform raw GCN. In the second set, we fixed as 100, and K 100, 125, 150, 175, 200, 250, 300, 400, 500. The more candidate nodes allows more possibly informative nodes to be included, while also have the risk of including noisy labels. This concern seems unnecessary in our experiments on Cora on one hand, nodes generally have high confidence and therefore high accuracy after calibration; on the other hand, though including some more in- correct pseudo-labels, our selected correct nodes can effectively propagate maximized information benefiting both current and future iterations.
4.5 ROBUSTNESS
Noisy Data. We randomly select a portion of the training and validation nodes, and flip each label another uniformly sampled different labels. The test accuracy of raw GCN, CPL (confidence only), and our methods on Cora are shown in Figure 2b Though the initial performance is close, our methods significantly remain more robust on more noisy data. Interestingly, with a small portion (5%) of noise, our model would generalize better than on clean labels.
Different Portions of Data. In this of experiments, we randomly select 3% portion of training data and 15% validation data and show the test accuracy of raw GCN, CPL, and our methods. Different from official split that selects equal number of labels across all classes, uniform sampling leads to imbalanced labels and decreased performance. In this case, information redundancy is more of a problem confidence based methods tend to select majority class to pseudo-label. As shown in Figure 2c our methods consistently outperform other methods, especially with fewer training labels.
Different Base Models. Note that we have assumed the base model to be a L-layer GNN with a graph structure dependent linear aggregation mechanism and ReLU activation. Besides GCN, this assumption is often not strictly satisfied, but we demonstrate that our strategy can still preserve its validity. as shown in Table Specifically, The aggregation mechanism of GraphSAGE (Hamilton ct al. 2017) sums neighboring node features followed by normalization based on the degree of the nodes. GAT (Velickovic et al. 2017) places different weights on neighbors during aggregation

---

Published as a conference paper at ICLR 2025
Namber Candicate Nodes
300
Rea
LPL
$4.2
Clans
Tost Accurccy (N)
Raw
50
Label
(a) Impact #selected #candi- date nodes
(b) Impact of noisy labels
(c) Impact training labels
Figure 2: Plots of hyperparameter and robustness analysis on Cora dataset. Our method retains the validity and superiority over baselines under different settings and hyperparameters.
Table 3: Test accuracy (%) on Cora dataset with different base models. Our method outperforms the baselines across different GNN models in most settings.
Base Model
Baselines
BANGS
Raw
M3S
CaGCN
DR-GST
Random
CPL.
GCN
80.82+0.14
81.40#0.29
83.06#0.11
83.04=0.38
83.16#0.11 160
83.72=0.52
84.23+0.62
GraphSAGE
81.50+0.03
82.86+0.72
83,04#0.36
83.50#0.21
83,01=0.38
83,43=0.15
83,94=0.32
GAT
81.1320.32
22.8041.85
81.70 28
83.33+1.14
83.1020.22
83.6520.35
83.86+0.50
GIN
77.47=0.57
81.3520.21
80.7520.44
78.5620.55
78.7220.37
80.01=0.51
80.7720.68
cording to self-attention. Despite non- non-linearity of aggregation in GraphSAGE and GAT, our method preserves its best performance compared baselines. With the base model GIN (Xu et (018a) with max aggregation, our method demonstrates the second-best performance.
5 CONCLUSIONS
In this paper, we have addressed the limitations in graph self-training by introducing comprehen- sive framework that systematically tackles the node selection problem using a novel formulation with mutual information. We have proposed BANGS which is a game theory-based method with the utility function based on feature propagation. While BANGS exploits the combinatorial structure among the nodes, we have demonstrated the suboptimality of independent selection both theoreti- cally and empirically. Additionally, we have shown that BANGS able to preserve correct ranking with noisy utility function. Extensive experiments validate the effectiveness and robustness of BANGS across different datasets, base models, and hyperparameter settings. These findings under- score the potential of our approach advance graph-based learning models.
Limitations and Future Work. The setting of current self-training methods including ours has sim- plified assumptions. For example, the pseudo-labels selected in previous rounds are considered to updated, and the teacher model in the next round are the same as the student model in the previous round. An interesting future direction would be designing methods under more general or different settings, c.g., on heterophilic (Chen et al. (025) and large-scale graphs. Another future direction is improve the efficiency of the utility function. One potential solution is through the use of influ- ence functions, which, in current research, have been primarily explored on specific networks, e.g., GCNs (Chen et al. 2019 Kang et al. (0022). We believe extending this approach more complex GNNs could lead us more efficient framework.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work supported in part by NSF under grants II1-2106758, and POSE-2346158.
REFERENCES
Eric Arazo, Diego Ortego, Paul Albert, Noel O'Connor, and Kevin McGuinness. Pseudo-labeling and confirmation bias in deep semi-supervised learning. In 2020 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2020.
David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel. Remixmatch: Semi-supervised learning with distribution alignment and augmenta- tion anchoring. arXiv preprint arXiv: (tf:::9911.999900 1,09785, 2019.
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 Infor- mation Processing Systems, 2023.
John Bridle, Anthony Heading, and David MacKay. Unsupervised classifiers, mutual information and' phantom targets. Advances in neural information processing systems, 4, 1991.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy S Liang. Unlabeled data improves adversarial robustness. Advances neural information processing systems, 32, 2019.
Yankai Chen, Taotao Wang, Yixiang Fang, and Yunyu Xiao. Semi-supervised node importance estimation with informative distribution modeling for uncertainty regularization. In Proceedings of the ACM on Web Conference 2025, pp. 3108-3118, 2025.
Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. In The Eleventh International Conference on Learning Representations, 2019.
Chirag Chhablani, Sarthak Jain, Akshay Channesh, Ian A Kash, and Sourav Medya. counterfactual explanation for graph neural networks. In Proceedings the 2024, pp. 503-514, 2024.
the ACM Web Conference
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial intelligence and statistics, pp. 192-204, PMLR, 2015.
Thomas M Cover, Joy A Thomas, et al. Entropy, relative entropy and mutual information. Elements of information theory, 2213: 1991.
Matthias Fey and Jan Lenssen. Fast graph representation learning with Py Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Spencer Frei, Difan Zou, Zixiang Chen, and Quanquan Gu. Self-training converts weak learners to strong learners in mixture models. In International Conference on Artificial Intelligence and Statistics, pp. 8003-8021, PMLR, 2022.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Johannes Gasteiger, Chendi Qian, and Stephan Günnemann. Influence-based mini-batching for graph neural networks. In Learning on Graphs Conference, pp. 9-1. PMLR, 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Hans Hao-Hsu Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neural networks miscalibrated? Advances in Neural Information Processing Systems, 35:13775- 13786, 2022.
11

---

Published as a conference paper at ICLR 2025
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 1122211--2133, 2020.
Jian Kang, Qinghai Zhou, and Hanghang Tong. Jurygen: quantifying jackknife uncertainty on graph convolutional networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 742-752, 2022.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2016.
Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges representation learning, ICML, volume 3, pp. 896. Atlanta, 2013.
Dongyuan Li, Zhen Wang, Yankai Chen, Renhe Jiang, Weiping Ding, and Manabu Okumura. A survey on deep active learning: Recent advances and new frontiers. IEEE Transactions on Neural Networks and Learning Systems, 2024.
Yayong Li, Jie Yin, and Ling Chen. Informative pseudo-labeling for graph neural networks with few labels. Data Mining and Knowledge Discovery, 37(1):228-2544 2023.
Hongrui Liu, Binbin Hu, Xiao Wang, Chuan Shi, Zhiqiang Zhang, and Jun Zhou Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference 2022, pp. 1248-1258, 2022a.
Tong Liu, Yushan Liu, Marcel Hildebrandt, Mitchell Joblin, Hang Li, and Volker Tresp. On calibra- tion of graph neural networks for node classification. In 2022 International Joint Conference Neural Networks (IJCNN, pp. 1-8. IEEE, 2022b.
Sourav Medya, Tiyani Ma, Arlei Silva, and Ambuj Singh. A game theoretic approach for core resilience. In International Joint Conferences on Artificial Intelligence Organization, 2020.
Guillermo Owen. Multilinear extensions and the banzhaf value. Naval research logistics quarterly, 22(4):741 1975.
Aswathnarayan Radhakrishnan, Jim Davis, Zachary Rabin, Benjamin Lewis, Matthew Scherreik, and Roman Ilin. Design choices for enhancing noisy student self-training. In Proceedings of the JEEE/CVF Winter Conference on Applications of Computer Vision, pp. 1926-1935, 2024.
Benedek Rozemberczki and Rik Sarkar. Characteristic Functions Graphs: Birds of Feather, from Statistical Descriptors to Parametric Models. In Proceedings of the 29th ACM International Conference Information and Knowledge Management (CIKM '20), pp. 1325 1334. ACM, 2020.
Ke Sun, Zhouchen Lin, and Zhanxing Zhu. Multi-stage self-supervised learning for graph convo- lutional networks on graphs with few labeled nodes. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 5892-5899, 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Ben- gio, et al. Graph attention networks. star, 1050(20): 48-55550, 2017.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3)44 2019.
Mai Vu. Entropy and mutual information. lect 01. pdf 2024.
https: www. ece. www.tt.ft..edi.. 194NT/
Fangxin Wang, Yuging Liu, Kay Liu, Yibo Wang, Sourav Medya, and Philip S Yu. Uncertainty in graph neural networks: survey, arXiv preprint arXiv:2403.07185, 2024.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propa- gation. arXiv preprint arXiv:2002.0675, 2020.
12

---

Published as a conference paper at ICLR 2025
Jiachen T Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In International Conference on Artificial Intelligence and Statistics, pp. 6388-6488 6421. PMLR. 2023.
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. Advances in Neural Information Processing Systems, 34:23768 11-23768-23779.0
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In International Conference on Learning Representations, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 3453-5462 PMLR, 2018b.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint arXiv: 1907.0491,, 2019.
Jize Zhang, Bhavya Kailkhura, and T Yong-Jin Han. Mix-n-match: Ensemble and compositional methods for uncertainty calibration deep learning. In International conference on machine learning, pp. 11117-11128 PMLR, 2020.
Zhen Zhao, Meng Zhao, Ye Liu, Di Yin, and Luping Zhou Entropy-based optimization on in- dividual and global predictions for semi-supervised learning. In Proceedings of the 31st ACM International Conference Multimedia, pp. 1445--355, 2023.
Ziang Zhou, Jieming Shi, Shengzhong Zhang, Zengfeng Huang, and Qing Li. Effective stabilized self-training on few-labeled graph data. Information Sciences, 631:369-384, 2023.
Henry Peng Zou, Zhengyao Gu, Yue Zhou, Yankai Chen, Weizhi Zhang, Liancheng Fang, Yibo Wang, Yangning Li, Kay Liu, and Philip Yu. Testnuc: Enhancing test-time computing ap- proaches through neighboring unlabeled data consistency. arXiv preprint arXiv:2502. 19163, 2025a.
Henry Peng Zou, Siffi Singh, Yi Nian, Jianfeng He, Jason Cai, Saab Mansour, and Hang Su. Glean: Generalized category discovery with diverse and quality-enhanced Umm feedback. arXiv preprint 18414 2025b.
13

---

Published as a conference paper at ICLR 2025
A
NOTATION TABLE
Table Frequently used notations and their explanations
Notation
Explanation
g
Graph, (A, X, y'}
A
Adjacency matrix of graph g
X
Feature matrix of nodes Iteration round number Set of labeled nodes Set of all pseudo-labeled nodes Set of unlabeled nodes in r-th round
V
VP
VY
VE
Set of newly added pseudo-labeled nodes in r-th round Ground-truth Labels of labeled, pseudo-labeled and unlabeled nodes in r-th round Student model r-th round, also equivalent to the teacher model at (r + 1)-th round Influence propagation step number
y' a yr
fr
15(i + i.0) H(v))
The feature influence of node on node vy after (-steps Entropy (uncertainty) of (in) a node v;
O(V))
The goal of self-training with VP' selected in the r-th round Sampled node set
8
U())
The noiseless utility function The estimated utility function Banzhaf value of node v in candidate set V The number selected nodes in each round
Ú())
6li,U,))
k
K
The number of candidate nodes in each round
CCE(Ú.3
The cross-entropy loss between ý and y. calculated by - En Eg Vie log(Dr,))
B
PROOFS
B.1
MUTUAL INFORMATION ESTIMATION
This section proves Lemma 2.1 Denote the distribution of unlabeled data and its prediction
Following Bridle a.. (199T); Berthelot al. (2019); Zhao semi-supervised learning is formalized
(2023), the objective of
P(U, u) /ʃ plu. u) log p(y)p(u)
I(y: u)
dydu
(6)
/ ply)dy / p(uly) log J ((())puuyydd du.
pluly)
Given we have N samples. Writing with integrals, we obtain
I(y: u) =Byl p(ul)) log p(uly) dul (Taking expectation over y)
E. [u(p))
= Eyy D p(uily) log p(u:l)) (Taking expectation over u)
Ey (p((())))))
(7)
= -Eny Σ pl u. (u) log (ogp(ull)))
Σ
(p(ll))) (ylp(u)l)) [w) (Log rule)
(E, (E,
In the last line, the first term is entropy of the unlabeled dataset prediction distribution, and the second term equals to the of individual prediction entropy.
14

---

Published as a conference paper at ICLR 2025
Next, connect this lemma with our objective function design. In the r 1 round, u. is the prediction distribution of teacher model fr-1, previous works that employ Equation | to optimize parameters of teacher prediction model f--1 in the current round. In our model, is the student model prediction distribution. While we fix the teacher model, and use Equation 7 to select nodes, such that the student model f, in the next round is improved. In nutshell, do not aim optimize the current model but to let student model learn maximal mutual information about unlabeled data.
According to Equation the goal can be approximated by an average over the unlabeled data set:
T 1i 10
13 9P-199)
C
V 1l H 9- H H0
C
I 1
1
(u) log f+(u)
fu) log(
Σ
fr(w)
V v4-11 ==1
(8)
p-1
VE F-1
where 0--1 El fo (u), is approximated by unlabeled data.
B.2 WIIY INDEPENDENT SELECTION NOT OPTIMAL?
In this section, we prove that independent selection is not optimal from two perspectives: the non- submodularity of the optimization problem, and the inequality of information gain.
By conditional information, our objective can be converted to
T(uM-1:87 0" 0F 1.
-1(y"- D7 9) 1w0"-1 92' 91))
Non-submodularitt, Interestingly, this objective function does not satisfy submodularity property, thus, greedy algorithm does not guarantee approximation via submodularity. In graph learning, the logits are predicted by GNN fitted on node features, labels, and graph structure. Submodularity requires that for each S T and every node T, USSU)) US) > (T - (T). We can provide a simple counterexample to prove that the objective function is not submodular. Consider graph with node 02,,2, and edge between (U1. (02, 0y), and (uz, va). Node v2 have two neighbors, Node U1 and Vy For simplicity, consider binary classification, node V1, U2, 24y belong to class 0, and 23 is class 1. Suppose an initial model can predict each node to the right class with 0.8. Let S = 2, T = {wi }. and e 03. When adding 03 of class 1, the uncertainty over all other nodes will increase. This is because most GNNs have homophily assumption, and the other nodes
from
a different class as Therefore, (S U v) U(T) will be negative. When we have T = {ur }. adding a 03 from class 1 would still raise uncertainty over the unlabeled v2 and U4. But since GNNs aggregate information from neighbors, the influence from of different class is partially offset by U1 of the correct class. Therefore, (T U) UTT) US U(S).
Inequality of Information. Denote the pseudo-labels of n nodes in V as (op' .... chain rule of mutual information, the first item
.... 0 According
I1 0" oe 9) =I 1: 0: D ... D2 1 19 9)
=I( of 3. 10 9) + T T(0) V/ Vr 1--1 lop' . -.-1 +...
+ I 100"111 0h y 1 J.-1. 9)
(10)
While previous independent selection usually implictly optimize for different goal:
I( ; ッ 1 9) + 105h -, 1" + 16 17--119-1199
max FP CV
(11)
15

---

Published as a conference paper at ICLR 2025
or, considering the correlation with other labels,
max VV"CVz [(00-1: Di 1- 13.-116711.97 +000-11 : 11 +...
(12)
+ 1(0 P2 1,--110,-111
Specifically, the matched items in Equation I0 and I1 or 12 usually do not equal to each other. Take the j-th item and one node vú VP an example. Their difference, namely interation information in information theory, is formulated as
A = (1r-1: DJ Ur- 11 ... 1. T(W"-,,0f 30 1
(13)
Nonetheless, by the non-monotonicity of conditional mutual information, conditioning can either increase, preserve, or decrease the mutual information between two variables (Vu, 2024). This the case even when random variables are pairwise independent.
Similarly, we can derive the interaction information for the second item Equation that:
= - Vr .......-- 19-1181111
:2 10"
(14)
Only when (4} A3) O, independent selection provides the optimal estimation of goal. However, this is not guaranteed in practice without further assumption. Therefore, combinatorial selection method would be more effective than the independent selection procedure.
B.3 PRELIMINARY: GRAPH NEURAL NETWORKS
To start proof, we first formally formulate Graph Neural Networks (GNN), For node o, GNNs utilize its feature æ; E IRP of D size the initial embedding x, (0) and adjacency matrix between is and its neighborhood nodes Nr. Similarly, GNNs use At, to create inital edge embedding e (")
Denote the embedding in layer 7 (i.e., after 1-th propagation) as aq (1) and its value the d'th position as a id Commonly, GNNs can be described through:
2 (1) = -nade (at!
(1)(11) .0(1-1) Aig))),
(15)
(1) Sedge (x) a e ((-1))-.
Here, AGG|-] is function to aggregate the node and its neighborhood embeddings, and fnoder fedge and fmag functions, which be linear layers models with skip connections.
Deonote the output logit value at dimension d in the last L layer as ".d" The final predicted proba- bility class is often calculated through softmax function:
(1)
P., = Soffmax(f/))ooooo (2)
(I)
(16)
Ee
In semi-supervised setting, we have access to ground-truth labels y' of few nodes V In back propagation, the labels influence the weight and bias of frode and fedge through gradient descent.
B.4 CONNECTION BETWEEN FEATURE INFLUENCE AND RANDOM WALK
Proof. In general neural network with ReLU activation, the d -th output logit can be written as (L)
Fr XL 1173 Eg Ed, ad2 IL
w()
di (Coromaaska al. 2015). is constant related
16

---

Published as a conference paper at ICLR 2025
to the size of neural network, and L is the hidden layer number. Here, & denotes the total number of paths, 24 E O, 1 denotes whether computational path is activated, Id,.9 represents the imput feature used in the q-th path of logit d1, and W is the used entry of weight matrix layer By d1:9 assuming equal activation probability of p. get:
(L) 4 de
II
(17)
X XL-11//
1)/2
di.q"
1=1
Under Assumption 1 the / layer feature updating equation in Equation 15 can be rewritten as
x ! ReLU(W(()) AGG [msg (w) (o) an 1-11) Az5))).
(18)
where ( is trainable weight matrix in the I-th layer of GNN.
According to Gasteiger et (2022). from the view of path, the feature of starting node is influ- enced by ending node j by all activated paths through the acyelic computational graph struc- ture, derived from the GNN structure. The activation status of path depends on ReLU function. Therefore, i.d the d-th logit of x!!) could also be expressed as
I. II
x j.d A(L-1)/2
Σ
2 d. P. Lidd
w(O) i.p d.g
(19)
p=
Here, introduce data-based graph path 9. which is decided by G. 2i.d.p.g E {0, 1) is indicator of whether the graph path is active with the ReLU in the computational graph. Note that is counted to separately for each combination of the output(ending) node u; logit position d and the computational graph path Similarly, define Vr,d,p. is the input feature of v2 used in the q-th computational path, for graph path p at output logit d. a.p denotes the normalized graph-dependent aggregation weights of edges, parameter of AGG[-). w(( weight matrix W. decided by the GNN structure.
is the entry for layer and logit in the d.q
According to Definition 3.1 the L-step influence score of node i on uy is computed by
Ou (T)
ΣΣ (
j.ds
(20)
Or.
(0)
dj
d2
s,l2
Under a L-layer GNN, we calculate the derivative of Equation 19
(.) j.d.
XL1-1)/2
2i p.
II
@ (()) a digg 1=1
(21)
j,da
where the 2 j,d, represents the output feature Uy at d, position, x x represents the input feature of 0; de position. øi denotes the number of computational paths related input dimension d2 and output dimension d1. In Assumption[] [ all paths in the computation graph of the model are activated with the same probability of success i.c., E[z.di.p.o] = p. then the expectation of Equation 21
(L)
(!) be written follows. The second line in this equation holds, a only depends the path in graph G, independent of ((l). d.g'
17

---

Published as a conference paper at ICLR 2025
Oa (L)
1
j.d.
1
w diaa
B
Ox .2
(0)
X 11/2
(22)
P
d
A(L-1)/2
p=11=1
Here, item Ep= I Cip sums over probabilities of all possible paths of length L from node by to 2/s which is also the probability that a random walk starting at 02 and ending at vy after taking L steps. Denote this probability as PE- Since this random walk item is independent of feature dimension dj and d2, summing up Equation 22
we get another expression Equation 20
1 ) X
PL
EE d2 9=11=1
(23)
d1
Note that W(),, as trainable weight matrix layer I, shares the same value for all nodes. Except P/- all other items are independent on nodes. Therefore, the expectation [ + j. L). the influence distribution of any node e; V is in proportion the expectation of L-step random walk
1,(++),L) is normalized over all distribution on G starting at node Vj. Since Tf(i - j. I.) Σr,ev (=-
nodes, the influence distribution is equivalent in expectation to random walk distribution. Formally, Equation can be simplified to
+ Pi P
(24)
Theorem proved.
B.5 CASE STUDY: 1-LAYER GNN
B.5.1 BOUNDING ESTIMATION ERROR OF ENTROPIES BY LOGITS
Lemma B.1. Given two distributions Pi = [pI.a] and P- = {P2.d), the probabilities are obtained
from logits using the softmax function Equation T6 and assume the difference logits Fı,d F2 + Cj for every dimension d. Then the final probability distribution Pt is reweighted version of P2:
e4
P1. Exege e P2.j.
Proof. To make Pi and Pg identical, we require Pı,j P25 for all E C. This implies:
1 Etec 6
2 Ekec E
Taking log on both sides:
F1,j Σ2 some constant
This shows that ø1,y and ø2.j must differ by the same constant across all classes j, i.e., for all E C, where c is a constant independent of j.
Now, if the difference between the logits æi,j and Ø2.j is not constant but depends on the class j as Cj then we have:
18

---

Published as a conference paper at ICLR 2025
Li = 22,j +
In this case, the probabilitiess Pı, can be expressed
e
P1J
Exec e
ExEO
tt
Σkec ea
P2.5
Thus, the final probability distribution Pi a reweighted version of P2, where each probability pa.j is scaled by a factor e and then normalized across all classes C.
When Cj in Lemma B. is small enough, and for any class i, le - cgl S 6, then the absolute entropy difference between Pi and Ps:
Lemma B.2.
8
H(P) H((P)) S 2
Proof. According definition of Shannon entropy,
H(P)) - = Σ
Pis log +
Σ
P2.
log P2.5
jEC
jEC
By substituting with relationship between Pı, and P2.j in Lemma B.I
we get
H(P))-H(P)) =-E
(E p2.))
e
cj
log Σ
ch
-
EPis'
PiJ C3 -ollog log Σ e
jEC
REC
JEC
REC
For small cj, an approximation could be:
H(P)) H(22)
Σ jEC
Pi. (cj -
where é is the average of ej. This shows that the entropy difference is weighted sum of deviations of eg from its mean, weighted by the probabilities Pi.j
Further, if for any class i, i, egl S 6, then
6 2
10j - c
Therefore, the entropy estimation error
5
8
8
H(()) H(2)) <
Σ
Pı,j
Σ
Pı.j
2
jEC
jEC
B.5.2 PREDICT THEN PROPAGATE
Comparing with Equation 22 we are interested in the logit value B[x (2) J. instead of derivative
Therefore, the computational paths are not only those connected to input feature dimen-
00 L0 sion at d2 position and output d1. but all activated computational paths that output d1. Thus, from Equation 21, we get:
L
EL j.dy
II
① w a
(25)
1)--11/2
di.g
V.EV pm
Further, we assume E[zi.d.... .p.gl = Xes.g- which means the expectation of input feature only depends output position dj and computational path q. Thus, Equation 25 is converted to:
19

---

Published as a conference paper at ICLR 2025
E| j.d1
P
Xoza
w
11/2
p dia
v.EV p=l 9=1
Xdi II
W
EI p=11=1
Xl1-11/2 1)/2
WVEY q=1
(26)
P
Xaya II PP.
1LL-11/2 11/2
NE
Σ
Blr 1% P/
The final line is due to B[x,,,] = Xi 1372 1372 E Ka.. I W di.g" and P/- 0 for any node except neighborhoods of ug. NG).. E[x'2,] is the expectation of final output for node v; at dimension dj by standard neural network, without neighborhood information aggregation as in GNNs. This means each node's 's features are processed independently through the layers.
By Definition 3.2 and Theorem 3.1 random walk:
estimate x (T.) with hs,da, which can be calculated through j.d:
(LL) Hdd (VP))
Emeru
(L) pi-ti Ldd
(27)
where (LL) enote the output logit by trained teacher model fr-1, while hj,d, denotes our estimation
for (LL) "idd" the true logit by the untrained student model f,- As defined, compared with Equation 26
we only estimate with logits of labeled or pseudo-labeled nodes in Equation 27
As all logits will go through Equation [6 which convert them to class probabilities by softmax (L)
function. By Lemma B.1 the logit estimation error, 85.4, = x "jah - h j.d, (VP"), small for all
(L)
dimensions d1, then the final probabilities computed from (2) probabilities. Thus, the entropy estimation of node by is still accurate.
j.d, (VP') are not far from ground-truth
B.5.3 LAYER GNN
Now we consider 1 I-layer GNN, such that L 1. Recall Equation 17 the output for node by by standard neural network (NN) without aggregation be represented as:
(1) 3.4
Fj.dh
W dg.g"
(28)
Now, since only I layer is employed, we simply the notation to distinguish variables from (r 1)- th and r-th round. Denote xh and a''d, as the output logits by standard NN at (r- 1)-th and r-th round, and similarly, WT-1 Wi.g for weights at (r 1)-th round and W for r-th round. Since we assume initial feature Xay. only depends on and d1, and input feature Ca is fixed, the expectation of output "!, is
E
Σ
Xis
W d,.9"
(29)
q=1
20

---

Published as a conference paper at ICLR 2025
where right-hand item is related with node j. Similarly, the expectation of output r/ is
1 J.d. = Σ Kds W
(30)
In Definition 3.3 the sampled nodes are in set S. Denote Tij.d (S) the logit estimation error of node V/ at di using S. Note that by softmax conversion, for any C dimensional variable ((X) ((X)) where a constant for every dimension. Let a Exje, P Then
expanded by Equation 26 the logit estimation error of node v; at dimension d1:
B|o (S)] B[x j,d] a
(S)
jidi
B[ - a Σ
B[a()) (
1pi+s
NEV.U -- US
= E
Blc di PP
Σ
pi+ Σ
El
- 1
(31)
wEN()
NEVIUR - L6
(LEN()
EnERUVY JUB Emerive
Pi-í
E
Po
The first to third line expansion by prior definitions. The fourth line according to Equa- tion 29 that feature expectation only depends on output dimension d,, and Σ,,Ng)) p/-+i
Σ EVXEN(() Ph 1. Assume that activation paths remain the same in both round,
Emjeviorg_ Pj++i Pi-+1
B( (S)
Σg
X Wr-1
Enjeviurp p)+1 Σ Ndr WT W
d1.9
(32)
EmEVviUP ,UB .B
PJ++
p
Xdi d9.9
(WT-1
Σ P
Wr W.
Though can initialize network weights the same, the loss function is computed differently, resulting difference in W and W Therefore, we need to further discuss the weight update equation. The loss function, e.g., cross-entropy loss, set as the sum of prediction error on each labeled sample. That for samples, we have the loss at dimension dj:
Ld. = =E Lidd (Widd Di.d)) Dr.d, = Softmaa (x
(33)
where L is the loss d, position.
Therefore, consider the classic gradient descent with one step we can update initial weight W W in (r 1)-th round through:
21

---

Published as a conference paper at ICLR 2025
WT-1 d19
Wh.
OWa1.
Σ
(Eq. 33
OWd.9
Ox OWa..
(34)
Σ
(chain rule)
0xi
AEV.
DLid
Σ
Ti (Eq. 28
dr
drgdd q=1
LEVILUP
Similarly, we derive weight update for r-th round:
aLd
W7, = Wdn
aW dWa.
d.14
OL',
OL
Σ
OWd.4
OWd..
(35)
MIEV US
Σ
=
Oz sd q=1
Di,d
US
Note that both equations initialized with the same weight matrix W and activation path, ahid
according to Equation 28, "id -==1'' = ='''.- Further, since labels are fixed for Vi VPP11= so dw; is also the same. Therefore, in the final line of both equations, we remove or 1 from the superscripts. Substituting Equation 34land 33 into 32 we get:
OL
Enjeviurr_uu
P/++i (W 7) WWa
0L'
Blō5,d, (S) P
Xdy (W
"WWng
Emeriuur P
Pi-i
p
Xdi
WWan
EmeV.Ne
q=1
dLig Drkgds
TTpp
Xdis
AEV.
Σ En,EVhoVe
Pj-Vi
dLidi Dr'idd
Σ
Xdrig)l
Pl
N.V.RRY
,8
9=1
(36)
According to Lemma B.2 when 87.d, (8) estimation is bounded.
Sj (S) is small for any dj and d2, the final entropy
22

---

Published as a conference paper at ICLR 2025
Bl (8) (g,ds(5) (S)
P
(Blahaa - -xjinal Emerive U8 PJ-t
EesEViUBp Pott Elujdd j.d - -250b211
Emeriuve uB PS+
(Nazo Wain - Wdg.gWWand
(Rid d1i9 - Xaz.n W )
E EnsEVIUVe_ P
0Li,1
Adz. (Wd1.9 1]
Σ
OW d:
(37)
NEVI J8
aLi,dz
-d2. (W (W 11
Σ
OWd2.9 )
MEVIUV UB
EnEVUUy ,8
Pi+ti
Edia (Wdr -1
EmERiUA: Dd-vi
q=1
NEV.LUP m-1
OLi,da )}
(d -
Σ
WW dz.9
NEVIUVP
This is to say, the entropy estimation is accurate when the predicted output logits difference between dj and d2 by student model fr. E(
27 "j,22 is in proportion to the difference by teacher model
j.d,
F.., j.dy - 43 ]. i.e., E Si 3id En,e9,ug ju Pa-
J.
E Enserjuu P This is aligned with the gradient
3.4 3dd
of W" and W V. V.U. US and Vi UU
B.6 ROBUSTNESS OF K-BOUNDED BANZHAF VALUE
In this section, we recall conditions in Theorem 3.2 the distinguishability of ground-truu -ttthhhhrthhhho utility
between U; and vy on coalitions less than size & is large enough, min ( (m)) (U) 2 т, and the
utility perturbation small such that Ü U ||, S TV -
( m-1
11-))
Proof. We begin by recalling the definition of A (m) (U) and Di.j as:
A (m)) (U) (U)
= |/7-1 m - (Vi--1-2) 2)
Ensve > U
Ui - U (SU,)))
(38)
and
--1
V | 1i-1l-2 2
(U)
A (m) (U).
(U)
(39)
m -1
m=1
Then, we rewrite (Ū) as a dot product of and a column vector a R":;
(i) = aT, TT,
(40)
where each entry of corresponds to subset S. Then,
= (a (a -a -a) an U2 AÚ.
(41)
23

---

Published as a conference paper at ICLR 2025
Thus, since AA (aa")(aa)) aaaaaaaaaaaa "aa"aaa" (a"a)aad (a" a) then
IUT AU
UT AU
IUT AU
UTT AU a a
(42)
|UTA]]
VUT AAU
va a U0 AU
As the weight of Banzhaf value is the same for all subset, and by assumption that m A (mm)
UUAUU a²a as
(U) 2 T, we can rewrite
Σ B11sk-2
E 1
(U Uv;) US (1, -
&1 1.cVv-M(a0
Escr= v2 1
18|5k-2 E
E (U(SUU)) - U(S)))))
SCV Mffiest
ny
Escr" Me k2
1
1 k-1
lt (17 1-2 -1
Σ 1m
(U(SUm)) - U(SU
m-1
m-
SCV (m:n)) m
k-1 1 )²
2m=1
m-1
k-1
1 7-1
11
(m)
(U))
m=1
m-1
T1
1.
Σ A-1
k )
m=1
m
k-1
(V 11-2) k. 2
m=1
1-1
(197-1 1-2 k
m=1
m-11
n,
[Vy-1l 2)
m - ?
(43)
UTAU AU
k-1 (12 .1-2) T. Further, since the utility perturbation small such
Therefore,
Em=1 m-1
a²a a
that | -
ΣE-1 (8-=-l-9). and by Equation 42 then
Ü U
UT AU aaa
S
TV
S
10a AUl 1/T All,"
1 A(Ú - UU) s ||0e ||uTA|le |i 0/] < <IUT "AU by triangle inequality.
which equals Finally, with Equation 41
(E,(U)D,, = (0(1) - (())((0)) -0))))00000))))0))0))0)))) U- AÙ U AQT - U) +)) 2 0.
(44)
C ALGORITHM FORMULATION
In this section, we provide pseudo-code in Algorithm and pipeline figure in Figure 3 for our method, BANGS.
C.I TIME COMPLEXITY
Line 1: Add self- takes O(VV)), and row normalization takes O(IV12).
Line 2: This depends on model selection. Consider simple GNN model with number of layers L and hidden units n., and train ne epochs. The time complexity is OL VV?).
Line 5: Softmax activation takes OCCVV), C. is the number of classes.
24

---

Published as a conference paper at ICLR 2025
Algorithm BANGS
Input: Graph including A, X and y', Iteration Number R. Candidate Node Number K, Selection Node Number k, Sample Size & and Number B, Confidence Calibration Model fe
1: Calculate Á by A. with added self-loop and row normalization.
2: Train the initial teacher model fu- [.. do 4: Employ fr-1 as teacher model.
3: for Every iteration
5: Calculate confidence for all nodes V with maximum softmax output of fr-1-
6:
Calibrate confidence with fc-
7: Select the top confident nodes as candidate node Sk V. Store the initial logits propagated by current labeled nodes U Vp r-1 Sample B times candidate 8 V
8:
9:
10:
for Every $ do
Add initial logits by the new logits propagated by S. Get entropy and calculate utility function (S) by Eq.
12:
end for
14:
Calculate Banzhaf value (i;; U, 7 for every vs accordingly.
15:
Select top nodes of highest Banzhaf value from K candidate nodes to label Vp, and get
Sh. the predicted label of V/ by fr-1,
16:
Train student model fr on y and y..
17:
end for
Line 6: The calibration process also depends the selection of claibration model. Consider Temperature Scaling with nrs iterations. This takes (ITrsCIVI)
Line 7: Top-K node takes O(V7"_llog((1)_
Line 8: This step only propagates from V = V V. Consider propagate H
times. So it takes V[
Line 9: Sampling takes O(B(VH-1)).
Line 10 -13: Similarly, line 11 takes OHHV))KC), and line 12 takes O(kC). For sam- ples, the total running time is OBBVV
Line 14: Using MSR, this could be done in a linear time to sample num O(B).
Line 15: The Top-A ranking is no longer than Top-K, as K k.
Line 16: Same as line 2, takes De
In summary, the initialization takes O(Ln, VI2). In each round, 1) confidence estimation takes Ofnr)CVV); 2) node selection takes O ( (VVV + Bk)C); 3) retraining also takes O[ (V) Given R self-training rounds, the total complexity roughly O (H +
Bk)C n. (Vi)) The final running time mainly depends the selection of GNN structure, alongwith Banzhaf sampling number and size.
C.2 SPACE COMPLEXITY
We have provided illustration in Sec. 3.3 The bottleneck in loading graph and utility function computation. We can control space complexity to O(E""IVV"C)) at the r-th iteration, where p means the batch of labeled nodes, and E denotes edges connected to 4 in Á. Nonetheless, the tradeoff between space and time complexity needs consideration. For smaller graphs whose influ- matrix can be stored, takes shorter time first compute influence matrix for all nodes, and query values during node selection.
D IMPLEMENTATION DETAILS
D.1 DATASETS AND CODE
The statistics of datsets are listed in Table D.I Datasets used in this paper could be found in:
25

---

Published as a conference paper at ICLR 2025
Self-Training r-th Iteration
Confidence Estimation:
Calculate Softmax Confidence with fr
Input: Graph G, Calibration Model for Self-training Iteration Number
2) Calibrate Confidence with f:
Node Selection:
1) Select Top K confident Nodes as Candidates
2) Sample Candidate Subsets B Times, and Calculate
Initialization:
Utility Function Using Feature Influence Calculate Banzhaf Value for Each Candidate
1) Train Initial Teacher Model fo
2) Calculate Feature Influence Matrix
Nodes, Select Top Highest Ones
Model Training: Add Selected Nodes with Predicted Label and Train Student Model
R-th
Output: Prediction by
Figure 3: Pipeline of BANGS
Cora, Citeseer and PubMed Yang et al.
2016)
(https://githu.com
S.miyoong//paantoiig
LastFM
(Rozemberezki
& Sarkar
2020
htttps://githb.com
benedakkrozemberrrzk FFAATHER)
Flickr (Zeng et al. 2019) http://///gtttooooooo/o//aaaaaaa
We employ the re- re-packaged datasets datasets from PyG (Fey Lenssen 2019
(https://githhmt com/
pyg-teaam/pyttorch_geemeeet
version 2.5.2).
Baseline methods:
M3S (Sun et al. 2020
httTps///itabb.ccm//tttt///// We use the repro-
duced version in CPL:
CaGCN (Wang et al.
2021)
GATS Hsu et al.
2022
httt::///ghhhb..ccmmmmmassssss//
DR-GST (Liu al.
2022a) hatear//ggtuuu.ccmm////aaaaaa/-. We
use the reproduced version in CPL;
CPL [Botao al. 2023
Dttps:///gituub..cm//BBBBBB
All code and datasets used in this paper, if presented, are open- sourced under MIT license.
Table 5: Dataset statistics.
Dataset
Cora
Citeseer
PubMed
LastFMAsia
Flickr
#Nodes
2,708
3,317
19,171
7,624
89,250
#Links
10,556
9,104
88,648
5,5612
899,756
#Features
1,433
3,703
500
128
500
#Classes
7
6
3
18
7
Our codes provided
26

---

Published as a conference paper at ICLR 2025
D.2 COMPUTING RESOURCES
The experiments are mainly running in machine with NVIDIA GeForce GTX 4090 Ti GPU with 24 GB memory, and 80 GB main memory. Some experiments of small graphs are conducted on MacBook Pro with Apple M1 Pro Chip with 16 GB memory.
E EXPERIMENT DETAILS
E. ADDITIONAL EXPERIMENT RESULTS
In this section, we include and analyze additional experiment results.
Table 6: Node classification accuracy (%) with graph self-training strategies on different datasets. Baseline methods report final test accuracy, our method reports test accuracy by early stopping.
Base Model
Baselines
BANGS
Raw
M33
CaGCN
DR-GST
Random
CPL
Cora
80.82+0.1
81.38+0.75
83.0620.11 11
82.0340.93
82.43+0.21
83.00+0.57
83,4720.54
Citeseer
70.18+0.27
68 08.8300.53
72.84=0.07
71.10+0.88
72.50=0.52
72.45+0.54
73.23=00700*
PubMed
78.40=0.11
79. 19.1000.28
81.16+0.10
77.42+0.60
78.93=0.47
79.37+0.63
81,03+0,56
LastFM
78.07=0.31
78.32+0.81
79.60=1.02
79.92+0.44
79.13=0.11
80.56+1.22
82.6620.439*
In Table 6 we include test accuracy that is early stopped by validation accuracy. Our methods are the best second best across all datasets. Nonetheless, it is worth noticing that though CPL tends to achieve best test accuracy in the self-training iteration, CaGCN tends to perform better with early- stopping criterion. This is because the confidence of test data calibrated using validation data in CaGCN, such that test accuracy is high using with validation accuracy.
Table 7: Total running time (seconds) comparison for BANGS and CPL datasets with GCN or GAT as base models.
Dataset
BANGS (GCN)
CPL (GCN)
BANGS (GAT)
CPL (GAT)
Cora
201.82
118.64
288.54
326.62
Citeseer
242.40
184.48
422.88
432.39
Pubmed
423,40
320.22
954.87
929.13
LastFM
325.62
209.80
725.54
697.88
Table Iteration block average running time comparison (s) on Cora.
Base Model
Method
Sample Size
Confidence Estimation
Node Selection
Model Training
GCN
CPL
NA
0.04
0.00
3.45
GCN
Ours
100
2.45
0.80
4.08
GCN
Ours
200
1.33
3.69
GAT
CPL
NA
0.06
0.00
11.20
GAT
100
0.16
0.80
10.20
GAT
Ours
200
1.31
10.76
In Table 7 we use GCN with simple network structure, our methods are slower than CPL: while using GAT that takes longer inference time, our methods is comparable CPI.. In Table 8. we further show the running times in seed to compare with the CPL.
Table we compare running time and test performance of our method with the raw model and best baseline, CPL, the same setting as described in Section 4 We test on Flickr dataset with ~90k nodes and the additional obgn-arxiv (Hu et al. 2020) dataset with ~170k nodes. We observe that graph self-training methods often exhibit comparatively smaller improvements larger datasets. To address this problem, additional techniques, such as contrastive sampling (Zhou et al.) 2023), may be incorporated as future direction. The total running time of our algorithm also
27

---

Published as a conference paper at ICLR 2025
Table 9: Running time and accuracy comparison on larger datasets.
Dataset
Methods
Running Time (8)
Accuracy (%)
Flickr
GCN
15.16
49.53.10.11
CPL
633.35
50.02.10.22
BANGS
1189.48
50.23.1 0.25
obgn-arxiv
GCN
30.81
63.82:10.12
CPL
1287.57
63.81=0.177
BANGS
1668.98
63.8610018
exhibits increase larger graphs, largerly due to computation involves adjacency matrix in PPR calculation. In this case, mini-batching PPR (Gasteiger al. 2022) is a good choice.
E.2 CASE STUDY: CONFIDENCE CALIBRATION
To motivate the integration of calibration, perform a case study. In Figure we predict labels of PubMed data, which have only classes and exhibits high confidence. The other hyperparameters except node selection criterion our framework sets the top K = 200 confident nodes as candidates and selects the highest Banzhaf value (Definition 3.3). Selecting nodes with the highest confidence, denoted by Conf (Uncal), would bring slightly better performances compared with the raw GCN predictions. Surprisingly, calibrating the same with CaGCN (Wang et al. 202Tp. denoted by Conf (cal), pro- duces worse performance under raw GCN. In contrast, with uncalibrated confidence, our framework produces comparable or better results than Conf (Uncal). However, with calibrated confidence, our framework exhibits a significant improvement. In the experiments (Section 4.3 we observe similar trends for most datasets.
fixed. To select informative nodes from highly confident ones,
100 nodes with
0.82
0.80
Test Accuracy
0.76
Raw
Conf(UnCal)
Cont(Caa)
0.72
Unrs(UnCall
Oull(Cal)
0.70
5
10 15 20
Iteration Round
Figure 4: The test accuracy of PubMed data with different node selection criteria in self-training iteration with 40 rounds. In each round, 100 nodes are selected pseudo-label. Our method with confidence calibration outperforms others.
28


Reviews:
[{"review_id": "wcM2W8yOeU", "reviewer": "Reviewer_A5dG", "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.\n\n---\nAfter rebuttal, I raise my rating from 5 to \"6: marginally above the acceptance threshold.\"", "questions": "See the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n\nDoes submodular optimization apply to the formation of the node set in this paper? Why this approach is advantageous?\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CnOcnB20fR", "reviewer": "Reviewer_ehCo", "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.", "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?\n2. 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?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YEiAvKbMeZ", "reviewer": "Reviewer_g53d", "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\nutility function based on feature propagation.", "questions": "Given the improvement, how significant is the problem solved?\n\nIs this work straightforward extension of the referenced work of (Wang & Jia, 2023)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The writing is clear. \n\nThe 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. \n\nThe 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5pGlFXfDdC", "reviewer": "Reviewer_V2uF", "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.", "questions": "Please refer to the Weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. It is interesting to introduce techniques from the co-operative game theory into graph self-tranining, taking into acount the combinatorial.\n2. The paper is well-organized and literature review is conducted well.\n3. 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.\n2. 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].\n\n[1] Geom-GCN: Geometric Graph Convolutional Networks, ICLR 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tG9dDDOPIM", "reviewer": "Reviewer_oNSD", "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.", "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.\n\n**Q2.** Comparison with consistency regularization approaches, such as [3], is highly recommended, as the current baselines are all pseudo-labeling methods.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper's motivation is clear and well-presented.\n- The introduction of Banzhaf values to incorporate node interdependencies is novel and unique.\n- 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.\n\n**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.\n\n**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.\n\n---\n**References**\n\n[1] Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration, NeurIPS 2021\n\n[2] What Makes Graph Neural Networks Miscalibrated?, NeurIPS 2022\n\n[3] Graph random neural networks for semi-supervised learning on graphs, NeurIPS 2020", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)