acceptodds
Under review as a conference paper at ICLR 2027

Condensation on Demand: Adaptive Budget Allocation for Graph Condensation

Abstract

Graph condensation constructs a compact synthetic graph for efficient GNN training, yet existing methods typically prescribe class-wise synthetic budgets from label frequencies before condensation. This implicitly treats class size as a proxy for representational demand, although frequency alone does not indicate where additional synthetic capacity is most useful. We instead formulate budget allocation as a sequential intra-class refinement problem, in which, beyond a minimum class-coverage requirement, each additional synthetic node is assigned according to region-level refinement utility. We develop AUA, an analytic allocator that scores feasible refinements by the reduction of a decomposable representation-and-semantic residual potential, providing explicit geometric and predictive interpretations. We further introduce LUA, a task-grounded extension that reranks analytically promising refinements using lightweight supervision of their predictive marginal gains. Each terminal region defines one synthetic node, while mass-preserving weights keep each class's total supervised training mass independent of its allocated resolution. Experiments on six graph benchmarks show that adaptive allocation improves the use of limited synthetic capacity. AUA enables efficient allocation with low condensation overhead, while LUA builds on AUA's analytic proposals to deliver consistent gains across non-saturated settings and strong performance on large-scale benchmarks and across architectures.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Condensation, Graph Neural Networks, Graph Learning

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_zqRvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper attempts to solve the problem of fixed allocation of synthetic nodes across classes based on class frequencies in graph condensation, which can lead to inefficient budget utilization. The authors propose two adaptive allocation methods, AUA and LUA, to dynamically allocate nodes based on the actual needs of different regions, thereby improving the effectiveness and efficiency of graph condensation.

Critical strengths
  1. The authors propose a new approach of dynamically allocating synthetic nodes based on actual needs, rather than fixed allocation based on class sizes.
  2. The AUA method performs graph condensation much faster than the compared methods, and the classification performance is also competitive.
  3. The LUA method further improves graph condensation performance while remaining relatively fast, showing good performance across different neural network architectures.
Critical weaknesses
  1. The methodological novelty is limited, as CGC (WWW 2025) already explored class-wise clustering for graph condensation, while C2TC (ICDE 2026) introduced adaptive allocation of condensed samples across classes.
  2. There is a lack of direct evidence to prove that the regions selected by the algorithm can indeed bring better classification results.
  3. Some experimental results are not as good as those of existing methods, some have small improvements, and the gains lack statistical testing.
  4. It has only been tested in the authors' own graph condensation process and has not yet been proven to be applicable to other graph condensation methods.
Questions for authors
  1. Can you provide direct evidence to prove that the regions prioritized by the algorithm can indeed bring greater classification benefits?
  2. Can statistical significance tests be provided to demonstrate the reliability of small performance improvements? How do you explain the fact that some results are not as good as those of existing methods?
  3. Can AUA and LUA be combined with other graph condensation methods such as GCond and SimGC while maintaining performance advantages? Is there experimental support?
2 comments
AuthorsOpenReview ↗

Author Response to Reviewer

We thank the reviewer for the constructive feedback and for recognizing the motivation behind adaptive budget allocation, AUA's efficiency, and LUA's competitive performance. We appreciate the concerns regarding methodological novelty, downstream benefits, statistical reliability, and generalizability. We address them below, drawing on additional controlled experiments and candidate-level analyses.


W1. Novelty Relative to CGC and C2TC.

We appreciate the reviewer highlighting these closely related studies. CGC advances efficient graph condensation through class-partitioned distribution matching, while C2TC jointly optimizes class-adaptive cluster allocation and clustering quality for tabular condensation.

Our work investigates a more fine-grained allocation formulation: which currently represented region should receive the next unit of synthetic-node capacity? Each refinement adds one synthetic node, allowing class-wise budgets to emerge from sequential region-level decisions.

Within this formulation, AUA estimates refinement utility through reductions in class-normalized representation and semantic residuals, with an explicit global-potential interpretation. LUA further learns task-grounded refinement preferences to improve alignment with downstream predictive gains.

The controlled experiments provide evidence for both aspects of this design. Under the same splitter and condensation pipeline, Table 5 shows that AUA improves over the stronger static allocation on four of six benchmarks, including +3.6 percentage points on Flickr and +1.4 on ogbn-arxiv. Furthermore, compared with random selection from the same AUA Top-8 proposal pool, LUA achieves paired improvements of +0.40 ± 0.19, +0.30 ± 0.21, and +0.10 ± 0.28 points on Flickr, Reddit, and ogbn-products, respectively.

These results support the value of both utility-guided budget allocation and learned regional refinement preferences.


W2 & Q1. Do Prioritized Regions Yield Greater Downstream Classification Benefits?

We agree that reductions in analytic residuals or proxy losses do not necessarily translate into downstream GNN improvements.

We therefore conducted an additional candidate-level analysis on Flickr, Reddit, and ogbn-products. For each dataset, we evaluated eight refinement states with eight candidate refinements per state, using five paired student seeds. We compared the rankings produced by AUA, the ridge probe, and LUA against actual marginal accuracy improvements under GCN and SGC.

Table Z1. Alignment with actual downstream GNN marginal gains. Spearman correlations are averaged over eight refinement states. Selected gains represent average one-step accuracy improvements in percentage points (pp). Each entry compares AUA → LUA.

DatasetGCN SpearmanGCN gain (pp)SGC SpearmanSGC gain (pp)
Flickr.18 → .40+.06 → +.18.16 → .36+.04 → +.15
Reddit.14 → .35+.04 → +.13.12 → .32+.03 → +.11
ogbn-products.11 → .24+.03 → +.08.10 → .19+.02 → +.05

LUA achieves stronger ranking alignment than AUA across all six dataset–architecture settings, and its selected refinements consistently yield larger average GNN marginal gains. LUA also exceeds the ridge probe in five of six settings.

These findings provide direct empirical support that the proposed refinement criteria identify regions with greater downstream predictive benefits. While the correlations are moderate and vary across datasets, they establish positive alignment between estimated refinement utility and observed GNN improvements.

Importantly, actual GNN marginal gains are used exclusively for offline diagnostic evaluation, not for training LUA or determining allocation decisions.

W3 & Q2. Statistical Reliability and Comparisons with Existing Methods.

We acknowledge that some performance improvements are modest and that our methods do not outperform every existing approach across all settings.

Our primary contribution is to investigate adaptive synthetic-budget allocation as an additional design dimension in graph condensation. This perspective also yields strong empirical competitiveness, particularly on the larger benchmarks. AUA provides an efficient alternative with competitive accuracy, while LUA further improves performance through task-grounded refinement.

Regarding statistical reliability, the main experiments report means and standard deviations over five runs. We further examined paired accuracy differences using the Random@Top-8 control, which shares LUA's candidate proposal mechanism and condensation pipeline.

Table Z2. Paired LUA–Random@Top-8 comparisons over five runs. Differences are in percentage points. The reported p-values are approximate, uncorrected two-sided paired t-test results computed from the rounded paired-difference summaries.

DatasetLUA–Random (pp)Positive runsApprox. p-value
Flickr+.40 ± .195/5.009
Reddit+.30 ± .214/5.033
ogbn-products+.10 ± .283/5.469

The paired comparisons provide additional evidence for the benefits of learned refinement, particularly on Flickr and Reddit. On ogbn-products, the incremental gains from learned reranking are smaller in these controlled settings, while the complete LUA framework still achieves the best performance across all three condensation ratios in Table 1. We interpret small paired differences cautiously, without extending statistical significance claims to comparisons with external baselines.

For Cora and Citeseer, the standard public splits contain only 20 labeled training nodes per class, making frequency-based and uniform allocations effectively equivalent. Together with the limited synthetic budgets, this reduces the opportunities for beneficial cross-class redistribution and may partly explain the smaller gains on these datasets.

Overall, the controlled allocation experiments, candidate-level evaluations, and paired comparisons support the effectiveness of adaptive refinement, particularly on larger graphs with heterogeneous representational demands, while indicating where its benefits remain modest.


W4 & Q3. Generalizability to Other Condensation Methods.

We appreciate this suggestion and share the reviewer's interest in extending adaptive allocation across different graph condensation frameworks. This was also a direction we considered during the initial design.

Such integration requires additional consideration because condensation methods differ in their objectives and in how synthetic node attributes and graph structures are generated. From a black-box perspective, evaluating alternative allocations would require repeated condensation and downstream evaluation, potentially introducing substantial overhead. From a white-box perspective, integrating refinement decisions requires method-specific adaptation to the underlying feature and topology optimization processes.

Consequently, allocation transfer across heterogeneous condensation pipelines involves more than replacing a predefined class-wise budget.

Our present experiments establish the effectiveness of adaptive allocation within a controlled condensation pipeline (Table 5), while the cross-architecture evaluations (Table 3) support transferability across downstream GNNs. These results do not establish direct integration gains for GCond or SimGC, which remains an important limitation and a promising direction for future investigation.


We thank the reviewer again for the constructive suggestions. We hope the additional downstream-utility analysis, controlled comparisons, and discussion of empirical scope help clarify the contributions and limitations of our approach. We have also incorporated relevant clarifications and additional empirical evidence into the revised manuscript, particularly regarding the distinction from existing methods and the alignment with downstream GNN improvements.

Reviewer_yecJOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This work points out that existing GC methods focus primarily on the matching process while overlooking the label assignment of each condensed node, which limits the class capacity of the condensed graph. To address this issue, the authors propose a hierarchical class assignment strategy called AUA, and further derive LUA, a proxy-model-based diagnostic method. Experimental results demonstrate the effectiveness of the proposed methods.

Critical strengths

1.The method is simple and easy to understand. LUA introduces additional features and trains a proxy model, which is a novel idea.

  1. Since the proposed method is GNN-training-free, it demonstrates outstanding efficiency.
Critical weaknesses
  • The biggest issue is that the research problem addressed is too restricted. First, the proposed method relies on class labels and cannot adapt to tasks such as node regression. Moreover, there has already been considerable research on self-supervised GC, where methods learn assignment matrices to adapt to various downstream tasks and labels [1] [2]. These approaches are far more flexible than the strategy proposed by the authors.
  • Another concern of mine lies in the novelty of AUA. In essence, it is nothing more than hierarchical clustering. Although LUA has some novelty, it is still not substantial enough to stand alone as an independent contribution. In addition, the authors ultimately synthesize condensed nodes through the assignment matrix, which essentially yields cluster centers. The ablation study also fails to demonstrate significant performance gains from any module or strategy, as removing each module results in only marginal performance degradation.
  • A writing issue. The notation is not standardized, which may make the paper difficult to understand for readers from other fields. For instance, the set GG, VV, the matrices AA, HH, XX, and the scalars CC, BB are all uniformly typeset in italics. However, in Eq. (21), the matrix Q\mathbf{Q} is typeset in Bold Roman.

[1] Towards Pre-trained Graph Condensation via Optimal Transport. NeurIPS 2025. [2] Contrastive graph condensation: Advancing data versatility through self-supervised learning. KDD 2025

Questions for authors
  • Could the authors explain the reason for the significant performance improvement on Flickr? Is it because the clustering is essentially based on similarity, which amplifies homophily? If so, would this cause the condensed graph to fail to inherit the heterophily properties of the original graph?
  • Please refer W1-W3
5 comments
AuthorsOpenReview ↗

Author Response to Reviewer

We thank the reviewer for the thoughtful feedback and for recognizing the simplicity and efficiency of our approach. We appreciate the concerns regarding task generality, methodological novelty, and presentation. Below, we clarify the motivation for adaptive budget allocation and provide additional evidence on learned refinement preferences and structural properties on Flickr.


W1. Scope and Relation to Task-General Graph Condensation.

We agree that our current framework focuses on supervised node classification and does not directly cover regression or label-free settings. This is a limitation of the present formulation.

PreGC and CTGC make valuable contributions toward task-general graph condensation. Our work examines a complementary design question: how to distribute a fixed synthetic-node budget according to regional representational and predictive demand. Existing condensation methods often prescribe class-wise budgets from label frequencies. We investigate whether allocating this capacity through sequential, utility-guided refinement can improve condensation quality.

The controlled comparisons in Table 5 demonstrate the importance of this allocation dimension under an otherwise identical condensation pipeline. Furthermore, the cross-architecture results in Table 3 support the transferability of our allocation criteria across different GNN architectures, although they remain task-informed.

We share the reviewer's interest in broader applicability. Extending adaptive refinement to regression or self-supervised condensation would require suitable utility criteria and refinement constraints, and offers a promising direction for future work.

W2. Methodological Novelty and Interpretation of Ablations.

Adaptive allocation beyond hierarchical clustering.

We appreciate the reviewer's observation. AUA indeed employs hierarchical partitioning, while its key design lies in how refinement opportunities are selected across classes under a shared synthetic-node budget.

Each additional synthetic node represents a unit of limited capacity. AUA compares feasible regional refinements using class-normalized representation distortion and predictive-semantic residual reduction, with the resulting allocation decisions corresponding to decreases in a decomposable global potential. Mass-preserving prototype weights further ensure that additional resolution does not automatically increase a class's total supervision weight.

Table 5 provides a controlled evaluation of this allocation mechanism. Ratio-driven, uniform, and AUA use the same deterministic splitter and AUA-based within-class refinement priority. Their differences therefore isolate cross-class budget allocation. As summarized in Table Y1, AUA outperforms the stronger static allocation on four of six datasets, including gains of 3.6 percentage points on Flickr and 1.4 points on ogbn-arxiv, with small decreases on Citeseer and Reddit.

Table Y1. Controlled allocation improvements from Table 5 (percentage points). AUA–Best Static compares AUA against the stronger of ratio-driven and uniform allocation. LUA–AUA reflects the combined effects of learned cross-class allocation and within-class refinement selection.

DatasetAUA–Best StaticLUA–AUA
Cora+0.5+1.1
Citeseer−0.3+2.1
ogbn-arxiv+1.4+0.6
Flickr+3.6+0.6
Reddit−0.3+0.6
ogbn-products+0.4+0.7

These results show that cross-class budget allocation has a measurable impact even with an unchanged hierarchical refinement mechanism.

Contribution of LUA and ablation evidence.

LUA extends the analytic allocation criterion by learning refinement preferences from task-grounded probe supervision. Its motivation is that analytic residual reduction does not always align with downstream predictive gains.

We conducted additional evaluations to examine this relationship. Using actual GNN marginal gains as the reference, LUA achieves higher mean Spearman correlations than AUA across all six dataset–architecture settings, and LUA-selected refinements yield larger average GNN marginal gains.

We also introduce Random@Top-8, which randomly selects among the same AUA-generated proposals available to LUA. This controls for the benefit of departing from greedy analytic selection.

Table Y2. Learned refinement preferences. Spearman correlations are evaluated against actual GNN marginal gains over eight refinement states. LUA–Random reports paired final-accuracy differences (mean ± std., percentage points) over five runs; parentheses indicate positive runs.

DatasetGCN Spearman (AUA → LUA)SGC Spearman (AUA → LUA)LUA–Random@Top-8
Flickr.18 → .40.16 → .36+.40 ± .19 (5/5)
Reddit.14 → .35.12 → .32+.30 ± .21 (4/5)
ogbn-products.11 → .24.10 → .19+.10 ± .28 (3/5)

Although random selection itself can improve upon AUA, LUA achieves higher accuracy in 12 of 15 paired comparisons, supporting the value of learned refinement preferences. The improvement is more modest on ogbn-products.

We agree that some individual ablations in Table 4 show moderate gains. These results complement the controlled allocation comparisons in Table 5 and the additional ranking experiments above. Together, they examine the contributions of individual components, adaptive budget allocation, and learned refinement selection. The evidence supports both the allocation perspective and the additional predictive value of LUA.

W3. Notation Consistency and Presentation.

We appreciate this observation and agree that the notation can be more consistent. We have revised the notation in the updated manuscript, including Eq. (21), to improve consistency.


Q1. Flickr Performance and Homophily Preservation.

We thank the reviewer for this insightful question. To examine whether the improvements on Flickr arise from amplified homophily, we conducted an additional structural analysis over five seeds using the same synthetic budget and topology recovery protocol.

Table Y3. Homophily and class-mixing analysis on Flickr. Results are mean ± standard deviation over five seeds. All statistics exclude self-loops. Weighted homophily and class-mixing divergence use degree-normalized adjacency weights.

GraphEdge Hom.Adjusted Hom.Weighted Hom.JS Div. ↓
Original.3310.1033.3257—
Ratio-driven.2877 ± .0045.0688 ± .0038.3621 ± .0049.0021 ± .0003
Uniform.1787 ± .0037.0114 ± .0050.2692 ± .0059.0229 ± .0012
AUA.1658 ± .0033−.0005 ± .0019.2586 ± .0050.0272 ± .0021
LUA.2403 ± .0291.0450 ± .0123.3156 ± .0243.0098 ± .0061

The results do not support homophily amplification as the explanation for the Flickr improvements. Both AUA and LUA exhibit lower edge homophily than ratio-driven allocation (.1658 and .2403 versus .2877), with consistent trends in adjusted and weighted homophily.

The accuracy improvements are consistent with the benefits of allocating synthetic capacity according to regional representational and predictive demand, although this analysis does not establish a unique causal explanation.

We also examined the preservation of cross-class connectivity. All 21 original cross-class label pairs remain connected in the recovered graphs. However, their relative connection frequencies are not perfectly preserved. The Jensen–Shannon divergences from the original class-mixing distribution are .0272 for AUA and .0098 for LUA, compared with .0021 for ratio-driven allocation.

These findings indicate that adaptive allocation can improve predictive performance without increasing graph homophily, while also highlighting that downstream accuracy and structural-distribution preservation are distinct considerations.


We thank the reviewer again for the constructive comments. We hope the controlled comparisons and additional analyses help clarify the contribution of adaptive budget allocation and the role of task-grounded refinement in improving graph condensation. We have also updated the revised manuscript to better distinguish adaptive allocation from hierarchical partitioning and to improve notation consistency.

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

This paper studies how to allocate a limited synthetic-node budget in graph condensation. Rather than prescribing class-wise budgets from label frequencies, it allocates each additional node by splitting a class-pure region. The analytic allocator, AUA, scores candidate splits by their reductions in representation dispersion and predictive disagreement. LUA then learns to rerank analytically promising candidates using supervision from held-out ridge-probe improvements. Each terminal region becomes a synthetic node, with weights that preserve each class's total supervised training mass regardless of its allocated node count. Experiments cover six benchmarks and include controlled allocation comparisons, runtime measurements, ablations, and cross-architecture evaluation.

Critical strengths
  1. The paper addresses a concrete question that is often left implicit in graph condensation: where should additional synthetic capacity go? Class frequency alone does not necessarily answer this question. Sequential regional refinement provides a reasonable way to make allocation depend on the structure within each class.

  2. AUA is mathematically interpretable. Its utility decomposes into reductions in within-region distortion and separation between the predictive distributions of the two children. The appendix also states the limits of the analysis clearly: monotone descent of the residual potential does not guarantee better downstream predictive performance.

  3. Table 5 provides a useful controlled comparison. The allocation policies share the representation, splitter, graph construction, training weights, and evaluation protocol. LUA achieves higher mean accuracy than both static policies on all six datasets. This supports the complete allocation policy under a common construction pipeline, although the contributions of cross-class allocation and within-class refinement selection remain to be separated.

Critical weaknesses
  1. The relationship between estimated utility and downstream GNN gains needs more direct examination. LUA learns from immediate reductions in ridge-probe squared loss, whereas the final evaluation measures GNN classification accuracy on a reconstructed graph. The potential-descent analysis and descriptive allocation trajectories do not establish whether candidate rankings predict these downstream gains. On a small set of refinement states, the authors could compare AUA scores, probe marginals, and learned rankings against actual GNN marginal improvements. Rank correlation or overlap among the highest-ranked candidates would make this comparison concrete.

  2. Table 5 does not distinguish the effects of cross-class allocation and within-class refinement selection. This does not undermine the comparison of complete policies, but it leaves the source of the improvement unclear. Two controls would help: evaluate learned within-class selection under fixed class budgets, and compare cross-class allocation rules under a shared deterministic within-class refinement priority.

  3. The paper already includes representation-only AUA through the "w/o Sem." ablation in Table 4 and compares LUA against AUA. A useful additional control would randomly select a region from the same AUA top-mm proposal set. This would test whether the improvement depends on the learned ordering rather than simply on departing from greedy analytic selection.

  4. LUA's additional cost deserves a more detailed breakdown. Table 2 reports condensation times approximately 13 to 52 times those of AUA, alongside a reported average accuracy improvement of 0.76 percentage points across the non-saturated settings. Reporting supervision collection, reranker training, and final allocation time separately would make this trade-off easier to assess. Experiments varying proposal size mm and the number of supervision states could also show whether a cheaper LUA configuration retains most of the gain.

  5. Some details needed to reproduce LUA remain unclear. Table 6 provides default hyperparameters, but the number of supervision splits, the number and sampling schedule of supervision states, and the reranker's early-stopping criterion need clarification. Sensitivity to λsem\lambda_{\mathrm{sem}} and to the quality of the cross-fitted predictor would help assess robustness.

Questions for authors

Please see the weaknesses.

3 comments
AuthorsOpenReview ↗

Author Response to Reviewer

We thank the reviewer for the thoughtful and constructive feedback. We have carefully examined the concerns and provide additional evidence on downstream utility alignment, allocation decisions, learned reranking, computational efficiency, and reproducibility. Our point-by-point responses follow.


W1. Relationship between Estimated Utility and Downstream GNN Gains.

We agree that analytic residual reduction does not necessarily translate into downstream GNN improvements. As clarified in Appendix B.5, our theoretical analysis establishes monotone residual descent rather than guarantees on downstream predictive performance. This distinction motivates LUA, which learns refinement preferences from held-out ridge-probe marginal gains.

To directly examine this relationship, we conducted an additional candidate-level analysis on Flickr, Reddit, and ogbn-products using GCN and SGC. For each dataset, we sampled eight refinement states and evaluated the same eight AUA-proposed candidates per state using five paired student seeds. We compared AUA, ridge-probe, and LUA rankings against actual GNN marginal accuracy improvements.

As shown in Table R1, LUA achieves higher mean Spearman correlations than AUA in all six dataset–architecture settings and than the ridge probe in five of six. LUA-selected refinements also yield higher average GNN marginal gains than AUA-selected refinements across all six settings, with a mean advantage of 0.08 percentage points. These findings complement the improvements in Table 5 and LUA's average gain of 0.76 percentage points across 16 non-saturated settings in Table 1. While correlations remain moderate, the results provide direct evidence that task-grounded reranking improves alignment with downstream GNN gains, without assuming that surrogate utility perfectly predicts downstream performance.

Table R1. Alignment of estimated refinement utilities with actual GNN marginal gains. Spearman correlations are reported as mean ± std. over eight refinement states, each with eight AUA-proposed candidates evaluated using five paired student seeds. Selected gains denote average one-step GNN accuracy improvements in percentage points (pp).

DatasetGNNAUA (ρ)Probe (ρ)LUA (ρ)AUA gain (pp)LUA gain (pp)
FlickrGCN.18 ± .19.30 ± .16.40 ± .14+.06+.18
FlickrSGC.16 ± .18.27 ± .17.36 ± .15+.04+.15
RedditGCN.14 ± .18.26 ± .16.35 ± .15+.04+.13
RedditSGC.12 ± .18.23 ± .17.32 ± .16+.03+.11
ogbn-productsGCN.11 ± .19.22 ± .17.24 ± .18+.03+.08
ogbn-productsSGC.10 ± .19.20 ± .18.19 ± .18+.02+.05

W2. Disentangling Cross-Class Allocation and Within-Class Refinement Selection.

We agree that cross-class allocation and within-class refinement selection should be distinguished.

The requested cross-class control is already implemented in Table 5. As specified in Appendix F.4, ratio-driven, uniform, and AUA share the same deterministic splitter and prioritize the highest-AUA-utility region within each selected class. Their comparison therefore isolates cross-class allocation effects under a fixed within-class refinement rule. As summarized in Table R2, AUA outperforms the stronger static policy on four of six benchmarks, with gains of up to 3.6 percentage points, while showing small decreases on Citeseer and Reddit.

For LUA, learned reranking can influence both cross-class allocation and within-class refinement selection. Table 5 evaluates their combined effect. Notably, Appendix G (Table 9) shows that AUA and LUA differ in final class-wise budgets by only 2.2% on Flickr and 3.6% on ogbn-products, yet LUA improves accuracy by 0.6 and 0.7 percentage points, respectively. Although this does not independently isolate within-class selection, it suggests that learned region-level decisions can be beneficial without substantial changes in class-wise budgets. This distinction is now clarified in Appendix F.4 of the revised manuscript.

Table R2. Accuracy differences (percentage points) from Table 5. The first two comparisons isolate cross-class allocation under a shared within-class refinement rule, while LUA–AUA reflects both effects.

DatasetAUA–RatioAUA–UniformLUA–AUA
Cora+0.5+0.5+1.1
Citeseer−0.3−0.3+2.1
ogbn-arxiv+1.4+10.6+0.6
Flickr+3.6+6.6+0.6
Reddit−0.3+1.4+0.6
ogbn-products+0.4+5.6+0.7

W3. Contribution of Learned Reranking versus Random Selection.

We agree that the LUA–AUA comparison alone cannot distinguish learned ordering from simply departing from greedy analytic selection.

We therefore introduce Random@Top-8, which uniformly samples a refinement from the AUA Top-8 proposals at each allocation step, using the same proposal mechanism as LUA. The splitter, synthetic budget, graph construction, and evaluation protocol remain unchanged.

As shown in Table R3, Random@Top-8 improves mean accuracy over AUA on all three benchmarks, suggesting that non-greedy selection can itself be beneficial. However, LUA further outperforms Random@Top-8 by 0.40, 0.30, and 0.10 percentage points on Flickr, Reddit, and ogbn-products, respectively, with higher accuracy in 12 of 15 paired runs. Although the gain is smaller on ogbn-products, these results, together with the ablations in Table 4, support the additional predictive value of learned refinement preferences beyond random selection within the same analytic proposal mechanism.

Table R3. Learned reranking versus random selection within AUA Top-8 proposals. Accuracy is reported as mean ± std. over five paired runs. LUA–Random denotes paired accuracy differences (pp); Positive counts runs where LUA achieves higher accuracy.

DatasetAUARandom@Top-8LUALUA–Random (pp)Positive
Flickr (0.50%)49.2 ± 0.249.4 ± 0.249.8 ± 0.3+0.40 ± 0.195/5
Reddit (0.10%)92.9 ± 0.293.2 ± 0.293.5 ± 0.2+0.30 ± 0.214/5
ogbn-products (0.05%)68.4 ± 0.269.0 ± 0.369.1 ± 0.5+0.10 ± 0.283/5

W4. Computational Cost and Accuracy–Efficiency Trade-off.

We acknowledge LUA's substantially higher condensation cost relative to AUA and that its average accuracy improvement of 0.76 percentage points across 16 non-saturated settings must be weighed against this overhead. We therefore examine its cost breakdown and lower-cost configurations.

Table R4 provides a runtime breakdown across all six datasets. Reranker training accounts for approximately 87–94% of LUA's total condensation time, while final allocation accounts for only 2.8–6.4%. On Flickr, for example, reranker training takes 136.0 seconds out of 144.6 seconds, compared with 4.0 seconds for final allocation. All costs are already included in Table 2.

We further evaluate lower-cost LUA configurations (Table R5). Using 50% of the supervision states reduces runtime by 34%, with an average accuracy change of only −0.02 ± 0.06 percentage points. Reducing proposal size from 8 to 4 saves 20% of runtime with a change of −0.04 ± 0.07 points, while increasing it to 16 raises runtime by 35% for a gain of only +0.03 ± 0.08 points.

These results indicate that LUA's computational cost can be substantially reduced with small average accuracy changes. AUA remains preferable when efficiency is paramount, while LUA offers an accuracy-oriented alternative with adjustable computational cost.

Table R4. Runtime breakdown across six benchmarks. Times are in seconds (mean over five runs); total condensation times match Table 2.

DatasetAUA totalLUA supervisionLUA trainingLUA allocationLUA otherLUA total
Cora (2.60%)1.20.813.51.00.315.6
Citeseer (1.80%)1.51.118.61.30.421.4
ogbn-arxiv (0.25%)6.25.2124.64.81.7136.3
Flickr (0.50%)2.84.0136.04.00.6144.6
Reddit (0.10%)5.13.567.43.91.576.3
ogbn-products (0.05%)41.224.0468.032.013.6537.6

Table R5. Accuracy–efficiency trade-offs of LUA configurations relative to the default (m = 8). Runtime changes are percentages; accuracy changes are in percentage points (pp).

ConfigurationRuntime changeAccuracy change (pp)
50% supervision states−34%−0.02 ± 0.06
Proposal size m = 4−20%−0.04 ± 0.07
Proposal size m = 16+35%+0.03 ± 0.08

W5. Reproducibility and Robustness of LUA.

Regarding reproducibility, LUA uses one stratified 90/10 fitting–calibration supervision split per seed and five-fold cross-fitted predictions, recomputed within each fitting subset to prevent calibration-label leakage. Supervision states are collected at every feasible refinement step (sampling interval = 1), yielding Bsup−C+B_{\mathrm{sup}}-C_+ states per rollout, where Bsup=min⁡(B,∣Vfit∣)B_{\mathrm{sup}}=\min(B,|V_{\mathrm{fit}}|). At the reported middle budgets, this gives 216, 112, and 1,177 states for Flickr, Reddit, and ogbn-products, respectively. Supervision is first collected along an AUA trajectory and augmented with one learned-policy rollout. The reranker is trained for at most 200 epochs, with early stopping based on the mean validation loss (listwise cross-entropy plus 0.05 Smooth-L1 loss) over 15% held-out refinement states, using patience 30. These details are now included in Appendix C of the revised manuscript.

Regarding robustness, Table R5 shows limited sensitivity to proposal size: changing mm from 8 to 4 or 16 yields average accuracy changes of −0.04 ± 0.07 and +0.03 ± 0.08 percentage points, respectively. We also examine cross-fitted predictor regularization (Table R6). As the ridge coefficient decreases from 0.1 to 0.01 and 0.001, held-out NLL decreases from 0.94 to 0.85 and 0.79, while Spearman correlation with actual GCN marginal gains increases from 0.24 to 0.40 and 0.44. These results suggest that better predictive estimates are associated with stronger refinement-ranking alignment, while LUA remains relatively stable across the tested proposal sizes.

Table R6. Sensitivity of LUA refinement ranking to cross-fitted ridge regularization. We vary the OOF ridge coefficient, measuring predictor quality by held-out NLL and alignment with actual GCN marginal gains by Spearman correlation.

OOF ridge coefficientHeld-out NLL ↓Spearman ↑
λ = 0.10.940.24
λ = 0.01 (default)0.850.40
λ = 0.0010.790.44

We have also incorporated the corresponding clarifications and supporting analyses into the revised manuscript, including additional results on downstream marginal gains, random selection, and computational overhead.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.