Online Graph Classification with One-Bit Feedback: A Graph Convolutional Bandit Approach

We study online graph classification with one-bit feedback, where the learner observes only whether its predicted class is correct. We train a graph convolutional classifier using the selected-class Bernoulli likelihood and explore through upper confidence bound (UCB) or Thompson sampling (TS). As the graph encoder changes, the head's accumulated uncertainty can become inconsistent with the current features. Moment transport (MT) updates the joint head mean and covariance to account for this change. We establish prediction and decision invariance under invertible feature transformations, give a counterexample for stale uncertainty, and bound decision perturbations under approximate transport. Experiments verify exact invariance and show improved decision quality over stale covariance during learned GCN updates. On four real datasets, UCB-MT ranks among the top four of nineteen methods in mean online mistake rate. Comparisons with stronger variance fitting give mixed results, showing that the benefit depends on the uncertainty model and exploration rule.