acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
reinforcement learning
Keywords:
Online classification, graph neural networks, contextual bandits, uncertainty quantification, moment transport

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dxoQOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies online graph classification with correctness-only feedback: upon selecting a class, the learner observes only whether the prediction was correct, with an incorrect prediction providing no information regarding the true class. The proposed method combines a Graph Convolutional Network (GCN) encoder with a joint multinomial head trained via the selected-class Bernoulli likelihood. Exploration is driven by an Upper Confidence Bound (UCB) or Thompson Sampling (TS) strategy utilizing a fitted Fisher-based covariance.

To mitigate representation drift, the paper proposes Moment Transport (MT), which fits an invertible map between old and new anchor features following an encoder update, transforming both the head mean and covariance accordingly.

The main contributions are as follows:

  1. A selected one-bit graph classifier featuring joint class uncertainty and uncertainty reconciliation during representation learning.
  2. Analytical guarantees including exact prediction and decision invariance, sequential equivalence under equivariant updates, a stale-uncertainty counterexample, local approximate-transport bounds, and conditional regret bounds.
  3. Empirical results demonstrating competitive performance on real-world datasets and synthetic improvements over stale covariance baselines, alongside mixed comparisons against experience replay and refined variance fitting.

The evaluation encompasses four real-world graph datasets, synthetic topology teachers, covariance ablations, exact feature-rescaling experiments, and supplementary aggregation and covariance-correction studies. The assessment below covers the appendices, and numerical comparisons have been verified against the reported tables.

Critical strengths
  1. The selected-bit likelihood handles incorrect predictions without inventing an alternative label. The identified multinomial head and joint sampling rule provide a coherent treatment of dependent class predictions. The paper distinguishes fitted Fisher information from a calibrated posterior and specifies assimilation before encoder transport.

  2. Theorem 1 transports the entire uncertainty state, including the regularizer. Corollary 2 separately requires compatible subsequent updates. The stale-precision example is correctly identified as a linear-bandit construction, and the regret results explicitly require additional calibration and sampling conditions.

  3. In the refined study, MT reduces mean regret relative to stale covariance from 550.50 to 451.73 for UCB and from 894.58 to 687.42 for TS, approximately 17.9% and 23.2%; the reported adjusted p-values are 0.045 and 0.00366. Separate same history substitutions on heldout diagnostic graphs show immediate reward gains of 4.805 and 3.665 %. Independent confirmation seeds, paired streams, and declared multiplicity families strengthen this evidence. The unsuccessful aggregation and correction extensions are informative rather than suppressed.

Critical weaknesses
  1. The joint selected-bit multinomial formulation is distinct from earlier neural-linear methods, but the inverse mean mapping and covariance congruence have direct precedents in the cited likelihood-matching literature (https://arxiv.org/pdf/1901.08612v2, https://proceedings.mlr.press/v139/nabati21a/nabati21a.pdf). The paper does not clearly distinguish its advances over this construction in terms of preserved quantities, treatment of the learning state, or analytical conclusions. The reported results also leave the specific benefit of the joint selected-bit extension insufficiently explained.

  2. The analysis explains exact coordinate changes, but does not establish when approximate transport is reliable during nonlinear representation learning. The acceptance test checks invertibility and conditioning, whereas Proposition 4 depends on prediction-weighted residuals relative to decision margins. Neither the regret assumptions nor the empirical analysis connects these criteria to observed encoder updates. Consequently, the conditions under which transport is dependable or likely to fail remain unclear. This limits the theory’s algorithm-specific insight; the explicitly conditional theorems remain valid.

  3. The experiments support MT over stale covariance, but provide a less complete account of when it is preferable to stronger variance fitting or replay. This leaves its comparative value less well established, although the paper’s mixed-results claim is supported. In the refined study, MT-minus-variance-fit regret is −45.09 for UCB, with adjusted p = 1.000. For TS, variance fitting has lower mean regret, 548.72 versus 687.42; the difference is 138.70, with adjusted p = 0.05004 by Monte Carlo and 0.05014 by exact sensitivity analysis. Both local reward comparisons have adjusted p = 0.427 (Tables 8–9, pp. 28–29). These results establish neither general MT superiority nor equivalence.

Questions for authors
  1. Beyond the analytical mean and covariance transformation in Zahavy and Mannor (Deep neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. 2019), what substantive advance does the joint selected-bit formulation provide, and which theoretical or empirical result best demonstrates it?

  2. For accepted nonlinear encoder updates, how informative are the prediction weighted residuals and decision margins in Proposition 4 on graphs excluded from anchor fitting? Do the existing diagnostics show when transport preserves decisions and when it fails?

2 comments

Thank you for the comparison with likelihood matching. The mean mapping and covariance congruence have precedents in Zahavy and Mannor (2019) and Nabati et al. (2021). Generally, we do not mean to claim the algebraic transformation is novel.

The contribution concerns its role in a different learning problem. At each round, the learner receives a graph, predicts one class, and observes only whether that class is correct. The selected-class Bernoulli likelihood uses an incorrect prediction without assigning an unobserved alternative label. A single multinomial head represents the class probabilities and their joint uncertainty, which is used in the UCB and TS decisions. The analysis then separates exact preservation of predictions and decisions, sequential equivalence under compatible subsequent updates, stability under approximate transport, and regret under additional calibration and sampling conditions. The selected-bit formulation and these distinctions, together with the learned-update experiments, are what we claim beyond the earlier mean and covariance transformation.

For nonlinear GCN updates, Proposition 4 depends on prediction-weighted residuals relative to decision margins. Algorithm 1 checks invertibility and conditioning, which do not establish that condition. On eight independently drawn, non-anchor graphs per accepted update, the saved same-history diagnostic gives UCB action disagreement of 2.31% for MT versus 16.91% with stale covariance, and coupled TS disagreement of 2.58% versus 14.27%. This shows that MT more often preserves the pre-update decision on the tested graphs. It does not establish Proposition 4’s sufficient condition for every graph, nor does preserving a decision establish that it is optimal.

The stronger uncertainty-update comparisons limit the empirical claim. MT improves over stale covariance in the independent refined study. Its UCB comparison with refined variance fitting is inconclusive; fitting has lower TS mean regret (548.72 versus 687.42), with an adjusted MT–fitting p=0.05004p=0.05004 that establishes neither significance at the declared threshold nor equivalence. On real data, UCB replay has fewer mean mistakes on three of four datasets but takes about 1.9–2.5 times MT’s learner time. We report these policy-dependent differences rather than claiming that MT generally dominates fitting or replay.

Thank you for the clear response. One of my questions (the contribution concern) remains partly open. The response points to the experiments with learned updates, but every setting in those experiments uses the same GCN, selected bit mean update and mean transport. So they test how the covariance is updated, not what the joint selected bit formulation adds to the mean and covariance transformation of Zahavy and Mannor (2019).

Otherwise, I am satisfied with the authors' answers to my questions. I will keep my score.

Reviewer_GeqtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies online graph classification using only correctness feedback. It combines a GCN and a joint multinomial head with UCB or Thompson sampling, and transports the head mean and covariance after encoder updates. The paper establishes transport invariance and conditional regret bounds, with experiments on synthetic graphs and four real datasets.

Critical strengths

S1. The paper shows that moment transport preserves joint predictive uncertainty and UCB/TS decisions under exact feature transformations.

S2. The paper demonstrates lower synthetic regret than stale covariance through controlled experiments with independent evaluation seeds.

Critical weaknesses

W1. The paper proves decision invariance when feature changes follow an invertible linear map, but learned GCN updates need not satisfy this condition. The regret bounds also assume reliable confidence estimates, which are not established for the learned model.

W2. The paper shows small gains over stale covariance on most real datasets, while UCB-replay makes fewer mistakes on three of four. The real data comparison fixes exploration scales and does not include refined variance fitting.

Questions for authors

Q1. How often do the confidence bounds contain the true class probabilities in the synthetic experiments?

Q2. How accurately does the fitted linear map capture GCN feature changes on graphs outside the anchor set?

Q3. Do the gains remain when each method’s exploration scale is tuned on the real datasets?

Q4. How do MT and refined variance fitting compare in mistake rate and runtime on the real datasets?

2 comments

Thank you for the four concrete questions!

Q1: Coverage of the generating probabilities. At the experimental UCB multiplier b=16b=16, the one-sided probability upper bound covered every true class probability on 106,925 of 163,840 synthetic rounds (65.3%). Coverage of the Bayes-optimal class was also 65.3%, and coverage of the selected class was 71.5%. No complete trajectory had coverage on every round. The stronger, two-sided condition in Equation (18), evaluated with ηt=0\eta_t=0, held for all classes on 20.7% of rounds and on no complete trajectory. These posthoc checks replayed the original trajectories and reproduced their regret exactly. The generating probabilities were used only for evaluation. The measurements do not establish a different deterministic confidence envelope, so the experiment does not verify Theorem 6’s assumption.

Q2: Accuracy beyond the anchors. An invertible, well-conditioned fitted map need not reproduce the nonlinear GCN change on an unseen graph. The saved refined-study diagnostic evaluates eight independently drawn graphs per accepted update. On a common pre-update history, UCB action disagreement was 2.31% for MT and 16.91% for stale covariance; coupled TS disagreement was 2.58% and 14.27%. This directly measures the resulting decision change outside the fitting set. It is not a measurement of raw feature-map approximation error, and the saved summaries do not pair each graph’s prediction-weighted residual with its margin. We therefore cannot report how often Proposition 4’s sufficient condition holds.

Q3: Separate real-data tuning. The complete-method synthetic experiment used equal development tuning budgets and independent evaluation seeds. The real-data comparison followed the fixed exploration protocol stated in the paper. We have not separately tuned each method’s exploration scale on each real dataset. The observed real-data rankings apply to the reported protocol; their persistence under another tuning protocol remains untested.

Q4: Mistakes and runtime. On the four real datasets, UCB replay has a lower mean mistake rate than UCB-MT on three, whereas TS-MT has a lower mean than TS replay on all four. Replay requires about 1.9–2.5 times MT’s learner time in this comparison. Refined variance fitting was evaluated in a separate independent synthetic study, where it has lower TS mean regret than MT. There is no matched real-data mistake-rate and runtime comparison with that fitter. The real-data results therefore describe an MT–replay quality–time trade-off, not a ranking of all three updates.

Thanks to the authors for the response. Q1 is resolved, and Q2 and Q4 are partly addressed. However, Q3 has not been tested, and for Q4 the real-data comparison with refined variance fitting is still missing. I appreciate the careful discussion of the limitations, and I will keep my score.

Reviewer_TUdAOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online graph classification when feedback reveals only whether the predicted class is correct. The method combines a GCN encoder with a joint multinomial logistic head, learns from the selected class's Bernoulli likelihood, and explores using UCB or Thompson sampling. When the encoder changes the representation, moment transport (MT) transforms the head mean, covariance, and precision to maintain consistent uncertainty. The analysis establishes decision invariance under invertible linear feature transformations, gives a stale-precision counterexample, bounds decision perturbations under approximate transport, and derives regret bounds conditional on calibration and sampling assumptions. Experiments cover four real graph datasets, synthetic streams, exact rescaling interventions, and several covariance controls. UCB-MT is competitive overall, while comparisons with replay and stronger variance fitting depend on the policy and setting.

Critical strengths
  1. The uncertainty-consistency problem is precisely identified and formalized. Equation (12) transforms the full covariance, precision, and regularizer as well as the mean. Theorem 1, Corollary 2, and Appendix C.10 specify when decisions and subsequent updates remain equivalent. Theorem 3 illustrates how stale precision can produce linear regret, while clearly distinguishing that linear-bandit construction from a lower bound for the proposed multinomial model. This careful separation of claims strengthens the theoretical contribution.

  2. The experimental controls and statistical reporting are substantial, including evidence against stronger claims. The studies use paired streams, separate development and confirmation seeds, declared multiple-comparison families, and a distinction between immediate substitutions on a common history and cumulative regret under separately deployed policies. Appendix D.4 revisits the comparison with a stronger variance-fitting solver, and Appendix D.7 reports that improving covariance fitting does not necessarily improve decisions. Table 1 also provides meaningful finite-horizon evidence: UCB-MT has average synthetic pseudo-regret of 385.5 versus 766.0/762.9 for the FastCB-PLL/SquareCB adaptations.

Critical weaknesses
  1. The regret analysis does not yet establish the required conditions for the proposed learner. Theorem 6 assumes simultaneous calibration in Equation (18), while Theorem 7 additionally assumes concentration and sufficient optimism for the optimal class. Both require a Fisher-weight lower bound and controlled information growth. The map acceptance test bounds individual condition numbers, not cumulative transport growth, and nonlinear encoder updates do not ensure calibration. Appendices A.2–A.3 acknowledge this accurately. Consequently, the strongest established theoretical contribution is coordinate consistency and perturbation analysis, rather than a convergence rate derived for the learned GCN itself. A sufficient condition in a clearly specified restricted setting, or empirical diagnostics of calibration and transport growth, would better connect the theory to the algorithm.

  2. The incremental benefit over the most direct uncertainty-update alternatives is not consistently established. In real-data Table 5, UCB-replay has a lower mean mistake rate on three of four datasets, and TS-MT is close to TS-stale in most settings. In the refined synthetic study, TS variance fitting has mean regret 548.72 versus 687.42 for MT; the adjusted comparison narrowly misses the declared significance threshold, which does not establish equivalence. Replay is more expensive, but comparisons with external adaptations also involve different losses, posterior models, and optimization procedures, so their full performance differences cannot be attributed to MT. The evidence supports MT as a useful, relatively inexpensive option, rather than a generally superior replacement for uncertainty reconstruction or matching.

Questions for authors

These questions concern the scope of the current conclusions and could affect my assessment.

  1. Applicability of the theory: Can the calibration error in Equation (18), or the information-growth condition, be derived in a restricted setting that still includes representation updates? Otherwise, do existing runs provide diagnostics of log-odds coverage, Fisher weights, and cumulative transport singular values indicating whether the assumptions are practically meaningful?
  2. Net benefit on real data: Could direct MT, stale, replay, and refined variance fitting be compared under a common tuning protocol with paired mistake-rate differences, intervals, and runtime? Statistical comparisons of the aggregation extensions do not resolve this primary comparison. If MT mainly offers a runtime advantage, please characterize the corresponding quality–time trade-off.
  3. Approximate transport in practice: On graphs excluded from map fitting, how do feature residuals relate to classification margins and action changes? Equation (13)'s acceptance rule checks invertibility and conditioning; does adding a residual threshold change the results? This would connect Proposition 4 more directly to learned nonlinear encoder updates.
1 comment

Thank you for the careful reading! The distinction between exact transport and the assumptions of the regret bounds is central to the paper.

When does the theory apply? Theorem 1 includes a restricted form of representation change: an exact invertible transformation of the graph features preserves the fitted probabilities, predictive uncertainty, and coupled UCB/TS decisions at a fixed history. Corollary 2 extends this equivalence through later rounds when the subsequent learning updates transform compatibly. Theorems 6–7 require more. In particular, neither the fitted-map acceptance rule nor Theorem 1 proves calibration for a nonlinear GCN trained from selected-bit feedback, and per-update conditioning does not control cumulative map growth.

We checked the calibration condition on the synthetic trajectories using the generating probabilities, which the learner never observes. The replay reproduced the recorded regret in every run. At the experimental UCB multiplier b=16b=16, with ηt=0\eta_t=0, Equation (18) held for all classes on 20.7% of rounds and on none of the 40 full trajectories. This does not exclude other theoretical envelopes, but it does not verify the regret assumptions for the experimental learner. Accordingly, the exact transport result describes a specified class of representation changes; the conditional regret results identify further requirements; and the learned-GCN experiments measure performance without assuming those requirements hold.

What does MT add relative to stronger updates? The independent refined covariance study reports the following mean cumulative pseudo-regret:

PolicyMTStale covarianceRefined variance fitReplay
UCB451.73550.50496.82544.02
TS687.42894.58548.72702.27

MT improves over stale covariance for both policies (six-test Holm-adjusted p=0.045p=0.045 and p=0.00366p=0.00366). The refined fitter has lower TS mean regret; its adjusted comparison with MT is p=0.05004p=0.05004, so the declared test establishes neither a difference nor equivalence. On real data, UCB replay has fewer mean mistakes on three of four datasets, while TS-MT has fewer than TS replay on all four. Replay takes about 1.9–2.5 times MT’s learner time. These results establish a benefit over stale uncertainty and a policy-dependent comparison with replay and fitting. The refined fitter was not included in a matched real-data study, so the synthetic ranking cannot be transferred to those datasets.

What happens after an approximate map? The refined study also saved a same-history comparison on eight graphs drawn independently of the map-fitting anchors at each accepted update. Average UCB action disagreement was 2.31% for MT and 16.91% for stale covariance; coupled TS disagreement was 2.58% and 14.27%. Thus MT more often preserved the prior decision on these fresh graphs. Proposition 4 gives a sufficient residual-to-margin condition for such stability, but the saved records do not establish how often that condition holds graph by graph. A residual threshold would change which encoder updates are accepted and hence later learning histories. We have not run that online ablation, so the current results do not determine whether it would improve performance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.