Condensation on Demand: Adaptive Budget Allocation for Graph Condensation

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.