- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies replay-based continual graph learning (CGL) for node classification under what it calls streaming constraints: a fixed, user-specified memory budget, single-pass access to each snapshot, and no prior knowledge of class counts or stream length. StreamCGL precomputes ℓ-hop propagated features Z = (D'^{-1/2}(A+I)D'^{-1/2})^ℓ X, presented as a "continuous Weisfeiler–Leman" space, and then discards the edges. For each class it maintains a weighted streaming k-means summary: online k-means (Liberty et al., 2016) with center weights, followed by weighted k-means++ compression. The per-class budget is ⌊b/|C(t)|⌋ and is recomputed whenever a new class appears, and the GNN is trained on the resulting edge-free set of centroids. The theory shows that the two-stage procedure (Alg. 2) achieves an expected O(log n log k) approximation of the k-means cost, using the composition result of Ailon et al. (2009). Experiments cover Time-IL and two new protocols (Recurrent class-IL, Mixed-IL) on six datasets. The paper reports the best average rank and up to 111× faster condensation than CaT/PUMA.
Making condensation-based replay cheap and budget-bounded is a worthwhile goal, and the method is simple and fast. However, the paper has five main problems:
- The framing presents efficiency properties as requirements of CGL itself.
- The core recipe is already established in training-free graph condensation (CGC, GECC): SGC-style propagation, class-wise clustering, edge-free centroids, and incremental centroid reuse. These works are either not compared or not cited.
- The theory does not cover the algorithm used in the experiments.
- The memory accounting excludes the method's own intermediate summary, while the baselines are handicapped by ad-hoc adaptations.
- In the original class-IL setting, the CaT/PUMA numbers are far below those reported in the PUMA paper at the same budget.
Critical strengths
Strengths
- The motivation is practical. Condensation cost and memory growth in CaT/PUMA are real bottlenecks, and a gradient-free, budget-bounded alternative is useful.
- The method is simple and fast. Condensation is 3–111× faster than CaT/PUMA, and the method runs on Products, where PUMA runs out of memory on the same hardware.
- Unknown class counts and recurring classes are handled natively, without knowledge of task boundaries or class statistics.
- Linking condensation to the streaming-clustering literature gives a clean bicriteria analysis for Alg. 2. Lemma 3 also gives a monotone budget–distortion knob.
- The three protocols vary how classes arrive. In Mixed-IL, StreamCGL shows much smaller forgetting than all baselines (AF −2.2 on arxiv and −1.0 on mag).
Critical weaknesses
Major Weaknesses
- The framing turns efficiency advantages into requirements of CGL.
- The abstract states that CGL "must adapt ... under strict memory and computation budgets." Is this "must" justified by the definition of CGL? Standard definitions (e.g., Zhang et al., 2024b, cited by the paper) ask for learning a task sequence while mitigating forgetting. Bounded memory and computation are desirable properties, not part of the definition.
- Single-pass access and a fixed memory budget are efficiency advantages of this method. They do not make CaT/PUMA or other replay methods invalid CGL methods. Statements such as "violate core tenets of streaming data processing" (L53) and "Owing to these unrealistic design strategies" (L61) should be rephrased as efficiency and scalability comparisons.
- Conversely, some assumptions the paper relies on are not stated in the problem definition. Problem 1 omits that snapshots share no edges (§4.1), and this is what makes single-pass condensation possible (see W4). Def. 4 says every snapshot "corresponds to the same node classification task," which contradicts the growing label space in all three protocols.
- The overlap with training-free condensation (CGC, GECC) is not acknowledged, and the novelty claims are too strong.
- CGC (Gao et al., WWW 2025) works as follows:
- It pre-propagates features with Â^K X.
- It partitions each class by clustering and uses the cluster representatives as condensed nodes.
- It has a graph-free variant (CGC-X) with identity adjacency.
- It bounds its matching loss by ‖Θ‖² times a least-squares representation term.
- GECC (Gong et al., 2025) works as follows:
- It runs class-wise k-means on SGC-aggregated features, with identity adjacency.
- It bounds the prediction gap by a representation distance plus a parameter distance.
- It supports evolving data by reusing previous centroids as initial centers.
- StreamCGL's components coincide with these: Â^ℓ X (renamed "continuous WL"), class-wise k-means distortion, edge-free centroids, and Lemma 2.
- CGC appears in only one sentence, described as "static," and is not compared. GECC is not cited. Two claims should be revised: that "this connection between graph condensation and streaming clustering has not previously been exploited" (App. A) and that this is "the first approximation guarantee for the CGL setting" (L84).
- The remaining contribution should be isolated: single-pass, fixed-budget summarization, and its evaluation under class-incremental streams. Requested:
- (a) CGC-X and GECC applied per snapshot under the same budget.
- (b) A simple merge-and-reduce baseline. At each step, it runs weighted class-wise k-means on the b weighted memory centroids together with the current snapshot's Z, then reduces back to b. This baseline is already single-pass and fixed-memory. If it matches StreamCGL, the streaming machinery adds little in practice.
- (c) Condensation time compared against these training-free methods, not only against gradient-based CaT/PUMA.
- CGC (Gao et al., WWW 2025) works as follows:
- The theory is disconnected from the experiments and adds limited insight.
- Lemma 1 is near-trivial: with an empty edge set, the propagation operator is the identity.
- Lemma 2 bounds how much the output of a fixed linear readout changes when z is replaced by its centroid. It does not bound the gap between a model trained on the condensed set and a model trained on the full data, which is the objective of Problem 1 (compare the parameter-distance term in GECC). The paper claims this "implies a bounded gradient divergence, ensuring the condensed optimization trajectory asymptotically tracks that of the full dataset" (L237–238), but this is not proved.
- The O(log n log k) guarantee is taken directly from Liberty et al. (2016), Ailon et al. (2009), and k-means++, and it holds for Alg. 2 with a fixed k. The experiments use Alg. 3 instead (threshold merge, capacity K, reduction to K/m), which has no guarantee. In addition, the per-class budget k = ⌊b/|C(t)|⌋ shrinks whenever a new class arrives, and the paper does not analyze how repeated re-compression affects the guarantee.
- The "training equivalence" in Lemma 3 requires the centroid weights to be used during training. The paper does not say whether training uses the weights w.
- The setting removes most graph structure, and the backbone-agnostic claim is weak.
- Structure is used only once per snapshot, to compute Z. Alg. 1 (line 6) then trains only on the edge-free centroid set, so the GNN never sees edges during training.
- Snapshots are induced subgraphs with no inter-task edges. In class-IL this follows CaT/PUMA, but the other protocols remove much more:
- In Time-IL and Mixed-IL on citation graphs (arxiv, mag), most citations point to earlier years, so they are dropped.
- Recurrent class-IL also keeps only a random half of each class, which in expectation retains about 1/4 of the edges within each class pair.
- Mixed-IL removes all cross-class edges within a year. Isolated nodes get Z = X. The paper reports neither the fraction of edges retained nor the fraction of isolated nodes.
- The no-inter-task-edge assumption is what makes single-pass condensation feasible. If new nodes had edges to old ones, computing Â^ℓ X for the new nodes would require features of old neighbors that have already been discarded. The old nodes' Z, and therefore the stored centroids, would also go stale. This limitation should be stated and discussed.
- Training GCN, SAGE, GAT, or SGC on identity adjacency reduces each of them to an MLP-like model on Z, so Table 6 says little about "generalization across GNN backbones." Table 6 also uses the original class-IL setting at a 1% budget rather than the main protocols. The paper does not specify how test nodes are evaluated: with Z and identity adjacency, or with X and A.
- Requested: per-protocol statistics on edge retention and isolated nodes; an ablation with ℓ = 0 and an MLP-on-X baseline; a setting with inter-task edges; an explicit description of the inference procedure.
- The memory budgets are not matched, and the baseline adaptations disadvantage CaT/PUMA.
- The per-class summarizer stores K tuples (c, p, w), i.e., O(|C|·K·d) memory. The paper says it is "never exposed to model training," and it is not counted in b. K is never reported. If K > b/|C|, StreamCGL holds more information than the baselines.
- When a new class arrives, StreamCGL re-compresses from its K-sized summary, whereas CaT/PUMA (App. E.3) must uniformly subsample their b condensed nodes, which loses information irreversibly. CaT/PUMA are also forced to split each recurring class into two disjoint batches. Both changes systematically hurt the baselines, exactly in the Recurrent and Mixed settings.
- The budget is counted in nodes, not bytes, and nodes cost different amounts across methods: SSM stores sparsified subgraphs, ER-GNN stores raw nodes, and the condensation methods store edge-free vectors.
- The regularization and distillation baselines (EWC, MAS, TWP, LwF, Bare) are not constrained by b at all, and GEM's memory size is not specified. Table 1 ranks them together and assigns OOM/OOT the worst rank, which inflates the "best average rank" claim. In class-IL, these methods collapse for structural reasons.
- The main budget (10%) is 20× the default used by CaT/PUMA (0.5%). At that size, replay is much less of a bottleneck.
- Requested:
- Byte-level accounting for all methods (summarizer, subgraphs, Fisher matrices, old model copies), plus peak GPU/CPU memory.
- Either count |C|·K·(2d+1) within b, or give the baselines an equal-byte reservoir of raw nodes.
- The values of K, ℓ, r₀, α, and m, and a sensitivity study on K, especially at K = b/|C|.
- Re-condensation instead of uniform subsampling for CaT/PUMA.
- Separate rankings for each method family.
- Compute is not matched, and the baselines appear under-reproduced.
- "Time(s)" is not defined: does it cover condensation only, or the whole run? Training epochs per task, early stopping, and baseline hyperparameter tuning are not reported. StreamCGL trains on at most b edge-free points, which costs about as much as an MLP. PUMA's OOM/OOT results may reflect the 15 GB T4 GPU rather than the method.
- In the original class-IL setting (Fig. 2), CaT and PUMA reach only about 48% AP on CoraFull at a 0.5% budget. At the same 0.5% budget, the PUMA paper (Liu et al., 2024, Table 2) reports 68.5 for CaT and 77.9 for PUMA. Similar gaps appear on Arxiv (about 55–57 here vs. 64.9/67.0) and Products (CaT about 67 here vs. 71.1); values here are read from Fig. 2. With the originally reported numbers, PUMA would outperform StreamCGL (about 72/61/68) on CoraFull, Arxiv, and Products. Please explain the discrepancy, e.g., whether the original backbones, hyperparameters, and training epochs were used.
- In Time-IL, StreamCGL trails Bare, EWC, GEM, LwF, and TWP on ogbn-mag (19.5 vs. 20.9–24.3), and trails EWC and GEM on Elliptic (87.0 vs. 91.7/92.8). The claim that it "remains strong on most settings" (L446) should be qualified.
- Requested: separate condensation and training times; the same training epochs and early stopping for all replay methods; Pareto curves of accuracy vs. time and accuracy vs. memory; and an equal-time comparison, e.g., CaT/PUMA with fewer condensation epochs.
Minor Weaknesses
- The abstract uses O(log n log k) before n and k are defined. It would be better to describe the result qualitatively, e.g., a poly-logarithmic approximation factor with sub-linear intermediate memory.
- Fig. 1 (pipeline) and Table 6 (the only evidence for RQ3) are in the appendix but are referenced as main results. They should be moved to the main text.
- The notation is inconsistent: K (summarizer capacity), k (number of centers), b, and b_y are used loosely. In Alg. 3, reduction is triggered at |S| = K, but the text says "exceeds."
- Recurrent class-IL and Mixed-IL are new protocols. Their design choices should be justified, including the half/half hold-out and the 3- and 5-way splits. Table 1's relative-gap metric and ranking rules look post hoc. Results use only three seeds.
- Typos: "G_s = (V_s, E_x, X_s)" in Def. 3; "guaranties" (L67); "Contributions.Our" (L68); "a sample drawn over from the held-out set" (L379); "psuedocodes" (App. C).
References
- Gao et al., "Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition" (CGC), WWW 2025: Â^K X propagation, class-wise clustering, and a graph-free variant.
- Gong et al., "Scalable Graph Condensation with Evolving Capabilities" (GECC), arXiv:2502.17614, 2025: class-wise clustering on aggregated features with incremental centroid inheritance for evolving data.
- Liu et al., "PUMA: Efficient Continual Graph Learning for Node Classification with Graph Condensation," 2024: class-IL results for CaT/PUMA at a 0.5% budget (Table 2).
Questions for authors
- What are K, ℓ, r₀, α, and m? How much memory does the summarizer use relative to b?
- How does StreamCGL compare with CGC-X, GECC, and a merge-and-reduce k-means baseline under the same budget and timing?
- Why are the CaT/PUMA results in Fig. 2 much lower than those reported in the PUMA paper at the same budget?
- What fraction of edges is retained, and how many nodes are isolated, under each protocol? How would the method handle edges between snapshots?
- Are the centroid weights used during training? How is inference performed on test nodes?
- What does "Time(s)" include, and how many training epochs does each method use per task?
- Where is the code?
6 comments
Weakness of the backbone-agnostic claim due to the GNN training on edge-free centroid sets. Clarification on graph structure retention. Need for discussion on the implicit assumption that snapshots share no inter-task edges, which is required for single-pass feasibility but limits the model. Ambiguity regarding the evaluation of GNN backbones and the specific inference procedure used for test nodes (using Z with identity adjacency vs. X with A).
Response> First, we must clarify the inference procedure: while the training phase is performed on the edge-free condensed centroids to satisfy the streaming constraints, inference is performed using the original graph structure (nodes X and adjacency A). The goal of the condensation is to produce a set of parameters that, when applied to the full graph structure during testing, yield high performance. Therefore, the GNNs are not merely acting as MLPs; they are being evaluated on their ability to utilize the graph topology during the actual task of node classification. While our training process is designed to be efficient, the evaluation specifically tests the model's capacity to generalize to the structural dependencies present in the test set.
Regarding the backbone-agnostic claim, we do not claim that the condensation process itself is invariant to the architecture. Rather, we demonstrate that our condensation mechanism provides a sufficiently high-fidelity representation that various GNN architectures (GCN, GraphSAGE, GAT) can successfully leverage it during inference. We acknowledge that if the full graph structure were available during training, the performance gap between non-linear architectures might be more pronounced; however, our setting focuses on the practical reality of streaming data where such structural access is unavailable.
The assumption of no inter-task edges makes a single-pass condensation computationally feasible. If we were to account for edges between old and new nodes, we might be forced to maintain node features in memory, violating the core sub-linear memory constraint of the streaming model. We will add a discussion to the draft acknowledging this as a potential direction for future work (e.g., by assuming specific temporal edge properties).
Finally, regarding the subgraph selection, we clarify that all baselines are evaluated on the same induced subgraphs. This ensures a fair and consistent comparison. The fact that these subgraphs are sparser than the full graph actually serves as a "stress test" for the methods, as they must learn from a more constrained set of structural information. We will include additional statistics regarding edge retention and isolated nodes in the revised appendix to provide full transparency.
Memory budget ambiguity and baseline adaptations
Response> Regarding memory accounting, we clarify that the intermediate per-class summarizer is a deliberate design choice to maximize resource efficiency; it allows us to maintain a high-fidelity summary without exceeding the final training budget. We believe that using available resources to their full potential is an advantage of our method, not a violation of fair comparison.
Regarding the adaptation of CaT/PUMA, we argue that uniform sampling is the most principled way to maintain their fixed budget. Since these methods learn latent embeddings via an encoder, their resulting representation space is often non-linearly separable. Applying a clustering-based re-compression (like k-means) to such a complex manifold could inadvertently destroy the learned structure. Therefore, uniform sampling—which is distribution-agnostic—serves as the most unbiased and fair baseline for comparison.
Furthermore, we contend that increasing the intermediate memory for CAT/ PUMA would not resolve the comparison issue for two reasons. First, from a sampling perspective, uniform sampling is scale-invariant: selecting k1 nodes from a subset of k2 nodes is mathematically equivalent to selecting k1 nodes directly from the original n nodes. Second, for learned embeddings, a larger intermediate buffer can actually be counterproductive. If an encoder is trained to represent a distribution using a very large set of nodes, the subsequent uniform sub-sampling to meet a fixed budget may result in a final set that is a poor representation of the learned manifold. In contrast, training on a smaller, more concentrated set of representatives can lead to a more cohesive and stable representation for the final budget.
Thank you for the detailed response, which clarifies the inference procedure and the no-inter-task-edge assumption; however, my main concerns remain 1) the intermediate summarizer is still excluded from the memory budget, 2) the experiments use unweighted Alg. 3 rather than the analyzed algorithm, 3) there is no comparison with training-free condensation methods such as CGC/GECC, and 4) the gap between the CaT/PUMA results and those reported in the PUMA paper is not explained. I will maintain my score.
Response> Regarding Lemma 1, while the result may appear intuitive, it serves as a necessary formal bridge to demonstrate that feature aggregation via an identity adjacency matrix is mathematically equivalent to the feature propagation in Linear GNNs on the original graph structure. This establishes the foundational premise that structural information is preserved within the feature space, even when operating on edge-free condensed representations.
Regarding Lemma 2, we have updated the lemma to directly address the reviewer's concern. It now bounds the generalization gap between a model trained on the full-scale dataset and one trained on the condensed set. This provides a formal, concrete relationship between clustering quality (distortion) and the resulting validation loss, addressing the distinction between output differences and training dynamics.
We provide both emperical support as well as a theretical intuition as to why the repetated compression doesnt create unbounded approximation. Additionally, the emperical results match or outperform in favor of the practical algorithm with clear advantage in accuracy and time.
Algorithm 3 provides a practical implementation of Algorithm 2; GNN training on the resulting condensed graphs was conducted for 250 epochs.
The theoretical intuition is provided in Appendix D.1
Furthermore, the shrinking per-class budget is an unavoidable consequence of the fixed-memory constraint in a non-stationary environment. Without prior knowledge of the total number of future classes, allocating the entire budget to current classes is the most principled approach; we then dynamically re-allocate space to accommodate new classes as they arrive to ensure system stability.
Regarding the use of weighted centroids, we note an important tension between density-accurate condensation and balanced training. While the weights are mathematically essential in our theoretical proofs (Lemma 2) to accurately capture the underlying data distribution, our empirical results indicate that incorporating these weights into the loss function can lead to a model that is overly biased towards the training set distribution. This can result in poor generalization if the test distribution does not perfectly match the density prior established during condensation. Consequently, to ensure empirical robustness and a more balanced representation of the class structure, we utilize the unweighted version in our experiments, while maintaining the weighted formulation to provide the necessary theoretical bounds.