- 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:
- A selected one-bit graph classifier featuring joint class uncertainty and uncertainty reconciliation during representation learning.
- 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.
- 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
-
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.
-
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.
-
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
-
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.
-
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.
-
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
-
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?
-
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 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.
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.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.