Continual Learning on Graphs via Gradient-free Condensation

Continual Graph Learning (CGL) must adapt to arriving graph data while retaining past knowledge, under strict memory and computation budgets. Memory replay is the dominant strategy, and recent methods show that replaying condensed graphs is particularly effective. However, existing condensation-based approaches violate the basic requirements of streaming data processing: they rely on gradient- based optimization with repeated passes over the data, assume prior knowledge of future class statistics, and permit the condensed memory to grow with the stream. We propose STREAMCGL, a replay-based framework that performs streaming graph condensation under strict single-pass and fixed-memory constraints. Rather than learning synthetic nodes against a reference model, STREAMCGL condenses in the continuous Weisfeiler-Leman feature space—the space that bounds what any message-passing GNN can extract—which reduces condensation to distortion minimization over an edge-free point set and admits a gradient-free, one-pass algorithm with an O(log n log k) approximation guarantee. Across three class-incremental protocols spanning chronological, imbalanced, and recurrent class arrivals, STREAMCGL attains the best average accuracy rank among all methods, condenses up to two orders of magnitude faster than state-of-the-art condensation baselines, and scales to streams on which they exhaust memory or time.