acceptodds
Under review as a conference paper at ICLR 2027

Learning Where to Read: Graph Classification under Observation Budgets

Abstract

Graph-level prediction typically assumes access to the complete input graph. However, when node information must be acquired through external queries or costly measurements, a predictor must decide what to observe within a limited budget. We study budget-limited active graph reading, where an agent sequentially reveals nodes and predicts the graph label from acquired evidence. Learning such a policy is challenging because graph labels provide no direct supervision for exploration actions, and the combinatorial space of reading trajectories makes unguided exploration difficult. We introduce BAGR, a budget-aware graph reader that combines sequential node selection with recurrent evidence accumulation. To guide exploration, we generate privileged teacher trajectories and filter them according to a pretrained classifier’s predictive performance on the revealed subgraphs. Imitation learning transfers these demonstrations into an observation-constrained policy, providing a task-informed initialization. On-policy reinforcement learning then refines the policy using classification-based rewards on its own trajectories, enabling task-driven exploration beyond the teacher demonstrations. We evaluate BAGR on CIFAR10 superpixels, COLLAB, and OGBG-PPA under explicit observation and node-budget constraints, and experimental results show gains over the evaluated fixed heuristics.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph classification, reinforcement learning, behavior cloning, graph neural networks, budget-limited decision making

Reviews

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

This paper studies the graph classification problem with limited observation budget - in where the learner/reader can only observe limited number of nodes (within the budget) sequentially, thus requiring a strategic node selection policy and a graph prediction policy. The authors propose a model to jointly output both policies. The model is trained through imitation learning and reinforcement learning with reward function defined by the authors. The authors demonstrate the the performance of the proposed method through experiments in various datasets and ablation studies.

Critical strengths

The paper is generally well written with clear structure and flow. The methods are natural and well motivated for the proposed setting. The results clearly demonstrate the improvement of the proposed method over the baselines.

Critical weaknesses

To the best of my knowledge, the authors did not describe what pretrained frozen classifier they use or how it is trained. Given that this pretrained classifier serves as a critical component for RL training, I believe missing a detailed introduction for it is a critical weakness. I’m particularly concerned with two things: 1, the data size and the data coverage assumption needed to train this classifier. 2, Can the data used to train such classifier already (or has the potential to) give a selection mechanism? Both questions can be answered by providing detailed descriptions of this pretrained classifier.

Questions for authors

The main question I have is about the motivation of this work. For example, in the image classification example the authors mentioned in the first graph of Introduction, why is running an image encoder on a certain crop costly, and more importantly, why can’t one use the whole image as the input, as I think this is the conventional setting for this task? I believe adding more illustrations on this budget-limited setting is essential for readers to understand the importance of the proposed method.

1 comment
AuthorsOpenReview ↗

Response to Reviewer phri

We thank the reviewer for the positive feedback on the paper's clarity, structure, and empirical gains, as well as the constructive questions on the pretrained frozen classifier and motivation.

W1. Detailed Specification of the Pretrained Frozen Classifier f^\hat f

All three frozen classifiers use a 5-layer GINE (hidden_dim = 300, dropout = 0.5), trained by cross-entropy strictly on the official/standard training split of each dataset (zero external data and zero validation/test leakage), and are discarded at deployment:

BenchmarkClassifier Architecture & Training SetupTraining Set (Val / Test Excluded)Full-Graph Val / Test (%)
CIFAR105-layer GINE + residual, scale-invariant meanmax pooling, 2-layer FFN head, label smoothing 0.150,000 official DGL train graphs (10,000 test held out)— / 60.50
COLLAB5-layer GINE + balanced class weights; full-graph pretraining then subgraph fine-tuning on the same train split4,000 train graphs from 80/10/10 split (499 val / 501 test held out)71.54 / 69.06
OGBG-PPA5-layer GINE with 7-dim edge encoders (37 classes)78,200 official OGB train graphs (45,100 val / 34,800 test held out)64.20 / 65.60
  1. Data size and coverage assumptions (and removing f^\hat f from RL):

    • No extra data: f^\hat f uses the exact same training graphs as standard supervised graph classification (offline training graphs are fully observed, whereas querying unseen test graphs at deployment is costly).
    • Weak or zero frozen classifier: Replacing f^\hat f on CIFAR10 with a weaker classifier (55.73% vs. 60.50%) still yields 20.68 / 23.59 / 25.35%, beating every fixed baseline (16.32 / 19.03 / 21.36%). Moreover, in a new controlled ablation removing f^\hat f from RL entirely (single-stage Reader-only RL rewarded solely by BAGR's own predictor), BAGR achieves 29.16 / 35.60 / 39.20% on CIFAR10, 55.99 / 54.69 / 56.89% on COLLAB, and 26.90% on PPA—and even Scratch-RL without BC reaches 27.11 / 32.30 / 34.79% on CIFAR10. Thus, f^\hat f is only an offline teacher-filtering aid rather than a bottleneck.
  2. Can f^\hat f or its training data directly provide a selection mechanism?

    • Offline (training time, full graph known) — Yes: On complete training graphs, f^\hat f scores node utility via input-gradient saliency or 1-step entropy reduction—which is precisely how we build offline BC teachers (§4.2).
    • Online (test time, unread features hidden) — No: Computing gradient saliency ∇xvf^\nabla_{x_v}\hat f or 1-step entropy reduction f^(G[St∪{v}])\hat f(G[S_t \cup \{v\}]) over v∈Ftv \in F_t requires observing hidden candidate features xvx_v beforehand, costing ∣Ft∣|F_t| feature queries per step and violating the budget. Masking unread features (xv=0x_v = \mathbf{0}) and scoring frontier nodes with a full-graph GNN instead reduces to our adapted SAGPool / Soft-Mask baselines, which trail BAGR by 15–21 pp on CIFAR10 (18.10% / 21.07% even under f^\hat f, vs. BAGR's 36.55–39.20%) because full-graph GNNs are not trained to route under masked attributes.

Q1. Motivation of Budget-Limited Reading and the Image-Crop Example

You raise a fair point about the Introduction's opening example:

  • Image example vs. CIFAR10's benchmark role: For standard low-resolution images (like 32×3232 \times 32 CIFAR10), encoding the whole image is cheap; we use CIFAR10 superpixels in §5 purely as a controlled benchmark where predictive signal lies in node attributes under regular topology. Sequential crop encoding is genuinely costly on gigapixel whole-slide pathology images (WSIs, 105×10510^5 \times 10^5 pixels with 104–10510^4\text{--}10^5 patches) or high-resolution satellite imagery, where encoding all patches exceeds GPU memory and latency budgets.
  • Revising §1 around native costly-acquisition graphs: To avoid confusion, we will revise §1 to clarify this distinction and lead with native graph tasks where observing each node incurs an explicit external cost:
    1. Financial anti-fraud & KYC / AML: Starting from a flagged account, querying external registries, counterparty records, or transaction payloads incurs per-call API fees, latency, or privacy budgets.
    2. Biomedical & clinical diagnosis: Ordering sequential lab/clinical assays or computing expensive 3D structural/docking features on demand from a seed protein or symptom set.
    3. Rate-limited web, citation, and social crawling: Fetching full profiles/documents via rate-limited APIs from a seed node, revealing node content and outgoing links step by step.
Reviewer_4jJNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes BAGR, a budget-aware graph reader to mitigate the computation overhead of inference on graphs. BARG is designed to jointly generate informative node sequences and predict the graph label from the entire trajectory of node observations. Node selector is a memoryless block which, at each time step, estimates which node to visit next, given a representation of a candidate node, remaining budget, and connections to the observed graph part. The predictor of graph labels operates on trajectories; a recurrent neural network (RNN) encodes the selected candidate node at each time stamp. The dot product attention allows the resulting node’s RNN representation to attend to previous nodal observations. The authors propose a custom on-policy RL training procedure. Imitation-based initialization is optionally included to aid convergence. Experimental results show good performance.

Critical strengths

The overall idea is clearly delivered. The motivation for avoiding the retrieval of features of frontier nodes is reasonable.

Critical weaknesses

Empirical: Performance of trainable baselines on CIFAR10 and OGBG-PPA is significantly lower than that of a random baseline. Moreover, the runtime and the memory consumption are not reported, which would allow us to evaluate the gains from the budget-aware sampling.

Theoretical: no results that would explain the advantages of the proposed method

Questions for authors

Why do trained baselines perform worse than a random heuristic?

What makes BAGR superior to other baseline methods? Is there an intuition? Could the authors provide an approximation guarantee for the proposed method’s policy relative to the optimal policy?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 4jJN

Thank you for the review. Below we resolve why trained baselines scored below Random in Table 3, report runtime and memory across all three benchmarks, and clarify our intuition and approximation limits.

Q1. Why Do Trained Baselines Perform Below Random in Table 3?

Trained baselines did not select worse nodes than Random; their full-graph-trained heads (Own) suffer covariate shift on 5–15% subgraphs, whereas Random in Table 3 used a frozen 5-layer GINE with scale-invariant meanmax pooling. Evaluating the same selected subgraphs under both heads confirms this:

MethodCIFAR10 OwnCIFAR10 Shared Clf.PPA (5%) OwnPPA Shared Clf. (5/10/15%)
Random—16.32/18.69/20.57—20.16/33.07/41.88
SAGPool10.92/12.52/13.8115.49/16.91/18.1010.0827.28/37.92/45.08
Soft-Mask12.88/15.34/17.3216.12/18.45/21.079.8821.88/33.89/42.00
AgentNet16.25/18.30/19.1116.25/18.88/21.589.4823.43/35.75/43.51
BAGR-Base (Clf.)—16.89/20.99/23.85—30.53/41.42/46.21
BAGR-RL (Own)27.79/33.84/36.55 (39.20 1-st.)15.50/16.76/18.6626.9020.73 (5%)

Under f^\hat f, all three baselines beat Random on PPA (21.88–27.28% vs. 20.16%) and Soft-Mask/AgentNet beat Random on CIFAR10 at 15% (21.07–21.58% vs. 20.57%). Own heads drop because SAGPool/Soft-Mask train on full graphs and AgentNet uses K=1K=1 agent under unit-step budgets (Martinkus et al., Thm. 12). BAGR co-trains its predictor on partial trajectories, and BAGR-Base beats all baselines under f^\hat f.

Q2. Runtime and Memory Consumption

At 10% budget (~9.6% nodes read, 1 seed, RTX 4060, batch 32 CIFAR10 / 16 COLLAB, PPA; BAGR-deploy drops f^\hat f):

DatasetSystemParamsModel / Step VRAM (MiB)Time (ms)Msg Edges (%)
CIFAR10Full-Graph2.18M8.37 / 186.80.8100.0
Learned Baselines0.14–0.57M0.55–2.17 / 0.24–3.31*58–10611.8–12.4
BAGR-deploy0.38M1.47 / 17.2781.212.5
COLLABFull-Graph1.82M6.97 / 1,952.13.4100.0
Learned Baselines0.14–0.53M0.55–2.03 / 1.4–272.5*73–1095.7–10.2
BAGR-deploy0.38M1.47 / 52.0398.611.0
PPAFull-Graph1.84M7.04 / 654.32.0100.0
Learned Baselines0.15–0.32M0.56–1.22 / 0.9–10.8*187–25146.5–56.6
BAGR-deploy1.53M5.85 / 91.14242.740.7

(*Baselines add 60–522 MiB terminal VRAM; Msg Edges = ∑t∣Evis(t)∣/(Lclf∣E∣)\sum_t |E_{\mathrm{vis}}(t)| / (L_{\mathrm{clf}}|E|).)

BAGR-deploy cuts peak VRAM by 7.2x–37.5x, queries ~90% fewer nodes, and uses 11.0%–40.7% of full-graph message-passing edges. On small RAM-resident graphs (74–24374\text{--}243 nodes), BB sequential Python/DGL steps (81–243 ms, matching SAGPool) carry host-loop overhead vs. one batched kernel (0.8–3.4 ms); when node queries incur external acquisition cost cacqc_{\mathrm{acq}} (APIs, assays, or patch encoders), saving 90% of queries dominates runtime alongside the 7x–37x VRAM savings.

Q3. Intuition over Baselines and Approximation Limits

  • Mechanism intuition: Poolers (SAGPool/Soft-Mask) apply static full-graph scorers to zero-masked frontiers and suffer readout shift on sparse subgraphs (Q1). Single-agent walks (AgentNet) only expand current neighbors N(vt)∖StN(v_t)\setminus S_t, getting trapped in suboptimal branches when N(vt)∖St≠∅N(v_t)\setminus S_t \neq \emptyset. BAGR scores the global frontier Ft=N(St)∖StF_t = N(S_t)\setminus S_t (cross-branch switching) while its LSTM + attention over StS_t connects distant read regions beyond the 2-layer GNN horizon and is trained on partial trajectories.
  • Approximation guarantee relative to π∗\pi^*:
    1. Worst-case impossibility: Without structural assumptions, no polynomial policy guarantees a worst-case constant-factor approximation to π∗\pi^*—under synergistic cues (XOR-like) or featureless bridges, any policy needs Ω(∣V∣)\Omega(|V|) queries in the worst case.
    2. Adaptive-submodular regime & role of RL: When expected entropy reduction g(S)=I(Y;o(S))g(S) = I(Y; \boldsymbol{o}(S)) is adaptive monotone and adaptive submodular with frontier-accessible informative nodes (e.g., dense 1-hop ego-nets), greedy 1-step info-gain guarantees (1−1/e) g(π∗)(1 - 1/e)\,g(\pi^*) (Golovin & Krause, 2011; or (1−1/e)g(π∗)−Bϵ(1 - 1/e)g(\pi^*) - B\epsilon under ϵ\epsilon-imitation, grounding our BC teacher). On multi-hop graphs with uninformative bridges, diminishing returns fails locally (matching Figure 3, where COLLAB step entropy briefly rises), stalling myopic rules and motivating BB-step trajectory RL to optimize terminal accuracy directly.
Reviewer_zJYVOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes BAGR, a framework for graph classification under limited observation budgets. It combines GNN-based node selection, recurrent evidence aggregation, imitation learning, and two-stage reinforcement learning to acquire informative nodes for graph-level prediction. Experiments on three benchmarks demonstrate improvements over existing baselines.

Critical strengths
  1. Well-motivated problem. The paper addresses graph classification under strict observation constraints, distinguishing active information acquisition from conventional graph pooling.

  2. Promising empirical results. BAGR achieves notable improvements on CIFAR10 superpixels and generally outperforms the evaluated baselines under limited observation budgets.

Critical weaknesses

W1. Limited methodological novelty and necessity. BAGR combines several established techniques without a clearly distinguished core algorithmic contribution. The comparable performance of RL without imitation initialization further questions the necessity of the full framework.

W2. Insufficient isolation of node-selection gains. The main comparisons use different predictors across methods, while the appendix shows substantial accuracy differences between predictors on identical subgraphs. This makes it difficult to attribute the improvements to the proposed node-selection policy.

W3. Insufficient justification for staged RL. The two-stage reward design lacks controlled comparisons with simpler alternatives, such as reader-only or reference-only rewards. Continued improvement after the reward switch does not establish the necessity of the proposed schedule.

Questions for authors

Please address each of the weaknesses mentioned above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer zJYV

Thank you for the incisive feedback. Following your suggestions, we ran held-out BC ablations, bidirectional predictor-isolation controls, and matched-epoch single-stage RL comparisons—allowing us to simplify BAGR's training pipeline in the revision.

W1. Core Contribution and Role of Imitation Initialization (BC)

  • Core contribution. Under hidden node attributes, active reading couples exploration with partial-graph prediction: selection alters the subgraph distribution seen by the predictor, while full-graph or immature predictors misjudge partial evidence. BAGR addresses this via (i) asymmetric frontier message passing (bidirectional in StS_t, one-way St→FtS_t \to F_t), (ii) decoupled LSTM + attention readout over StS_t (isolated from policy-gradient noise), and (iii) reader-aligned on-policy RL—which simplifies to single-stage RL after BC (W3).
  • Held-out test value of BC. Figure 2 (top) plotted training reward, where Scratch-RL overfitted training rollouts (63.7% train acc. on COLLAB). On held-out test sets at matched RL epochs, BC yields clear gains:
Dataset (Budgets)PipelineRL Ep.Test Acc. (%)
CIFAR10 (5/10/15%)Scratch-RL (no BC)1527.11/32.30/34.79
CIFAR10 (5/10/15%)BC + RL (2-stage, Table 3)1527.79/33.84/36.55
CIFAR10 (5/10/15%)BC + RL (1-stage Reader)1529.16/35.60/39.20
COLLAB (10/15/20%)Scratch-RL (no BC)1052.25/51.10/48.05
COLLAB (10/15/20%)BC + RL (Table 3)1051.90/53.44/55.74

BC improves CIFAR10 accuracy by up to +4.41 pp (39.20% vs. 34.79%) and prevents Scratch-RL on imbalanced COLLAB from collapsing to the ~51.9% majority prior (52.25%->48.05% vs. 51.90%->55.74%, +7.69 pp at 20%; under f^\hat f, Scratch-RL stays at 15.57% vs. BC+RL's 20.26%).

W2. Bidirectional Isolation of Node-Selection Gains

We isolate selection from predictor capacity via two fixed-predictor controls:

  1. Control A — Shared Frozen Classifier f^\hat f (BAGR-Base, no Evidence head): Training and evaluating BAGR's selector with f^\hat f beats every baseline on CIFAR10 (16.89/20.99/23.85% vs. AgentNet 16.25/18.88/21.58%) and PPA 5/10/15% (30.53/41.42/46.21% vs. best baseline SAGPool 27.28/37.92/45.08%). (We also fix Appendix Table 4: Table 3's epoch-6 CIFAR10 BAGR-RL scores 15.50/16.76/18.66% under f^\hat f rather than epoch-3's 16.68/19.78/22.98%.)
  2. Control B — Shared Frozen BAGR-RL Predictor: Feeding baseline trajectories into the frozen BAGR-RL predictor:
Selector (Fixed BAGR-RL Head)CIFAR10 (5/10/15%)COLLAB (10/15/20%)PPA (5%)
Random23.04/23.15/22.8454.44/55.89/56.0917.20
BFS / Max-FD (best)21.68/18.55/18.3154.49/56.09/55.4417.26
SAGPool24.98/22.78/20.2352.35/54.29/55.0418.41
AgentNet24.75/27.30/28.5053.99/55.59/55.74—
BAGR (Ours)27.79/33.84/36.5551.90/53.44/55.7426.90

Under the identical sequential predictor, BAGR's selector beats the best baseline selector by +3.04/+6.54/+8.05 pp on CIFAR10 and +8.49 pp on PPA (26.90% vs. 18.41%), while COLLAB gains stem mainly from overcoming full-graph readout collapse.

W3. Controlled Comparison of RL Reward Schedules

From the identical BC checkpoint (15 RL epochs on CIFAR10; 10 on COLLAB, val-selected), we compare single-stage vs. staged rewards:

RL ScheduleCIFAR10 Reader (%)CIFAR10 Clf. (%)COLLAB Reader (%)COLLAB Clf. (%)
Ref-only (classifier)25.43/29.35/31.3416.98/20.45/23.8255.99/54.84/57.3915.72/18.26/20.31
Blended-only (soft-both)——55.64/55.84/54.4415.72/18.21/20.21
Two-stage (Table 3)27.79/33.84/36.5515.50/16.76/18.66——
Reader-only (1-stage, no f^\hat f)29.16/35.60/39.2015.61/16.95/18.8655.99/54.69/56.8915.72/18.21/20.36
  1. Reader-only beats Ref-only by +3.73/+6.25/+7.86 pp on CIFAR10 (while Ref-only peaks on f^\hat f at 23.82%), confirming static full-graph classifiers impose a surrogate ceiling.
  2. Simplifying BAGR: Validating your critique, once BC warms up the predictor, single-stage Reader-only RL needs neither stage switching nor f^\hat f in RL, and surpasses two-stage (39.20% vs. 36.55%) by devoting all epochs to reader alignment (reference blending only aids cold-start Scratch-RL). (Audit note: Appendix A.3 inaccurately listed 10+5 uniformly; Table 3 CIFAR10 used 9+6, COLLAB classifier, and PPA 26.90% already used Reader-only.) We will streamline BAGR to BC -> single-stage Reader-RL and fix Appendix A.3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.