acceptodds
Under review as a conference paper at ICLR 2027

Continual Learning on Graphs via Gradient-free Condensation

12 views

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Machine Learning, Continual Learning, Data Condensation

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_dnVoOpenReview ↗
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

  1. The motivation is practical. Condensation cost and memory growth in CaT/PUMA are real bottlenecks, and a gradient-free, budget-bounded alternative is useful.
  2. 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.
  3. Unknown class counts and recurring classes are handled natively, without knowledge of task boundaries or class statistics.
  4. Linking condensation to the streaming-clustering literature gives a clean bicriteria analysis for Alg. 2. Lemma 3 also gives a monotone budget–distortion knob.
  5. 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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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
  1. What are K, ℓ, r₀, α, and m? How much memory does the summarizer use relative to b?
  2. How does StreamCGL compare with CGC-X, GECC, and a merge-and-reduce k-means baseline under the same budget and timing?
  3. Why are the CaT/PUMA results in Fig. 2 much lower than those reported in the PUMA paper at the same budget?
  4. What fraction of edges is retained, and how many nodes are isolated, under each protocol? How would the method handle edges between snapshots?
  5. Are the centroid weights used during training? How is inference performed on test nodes?
  6. What does "Time(s)" include, and how many training epochs does each method use per task?
  7. Where is the code?
6 comments

Justification of the necessity of Lemma1. Clarification on the claims of Lemma 2 Ambiguity regarding the O(lognlogk) guarantee, specifically concerning the use of Algorithm 3 and the impact of shrinking per-class budgets. Clarification on Lemma 3 regarding the use of centroid weights

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.

ARXIVMetricAlgo2Algo3
TimeAP44.4 +/- 0.847.9 +/- 0.6
AF-10.4 +/- 1.0-3.2 +/- 1.1
TotTime11736.3
MixedAP43.6 +/- 0.441.8 +/- 0.8
AF-8.5 +/- 0.4-2.2 +/- 1.0
TotTime173.377.5
ClassRAP60.5 +/- 0.160.9 +/- 0.6
AF-7.3 +/- 0.2-7.1 +/- 0.5
TotTime141.958.9
Dataset / TaskMetricAlgo2Algo3
Ogbn-mag
TimeAP12.3 +/- 0.319.5 +/- 0.5
AF-2.6 +/- 0.3-0.6 +/- 0.3
TotTime417.7113.2
MixedAP12.1 +/- 0.220.0 +/- 0.2
AF-4.1 +/- 0.2-1.0 +/- 0.2
TotTime845.6303.6
Corafull
ClassRAP69.8 +/- 1.068.9 +/- 0.6
AF-5.9 +/- 0.7-6.3 +/- 0.7
TotTime126161.9

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.

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.

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

This paper proposes STREAMCGL, a gradient-free graph condensation framework for continual graph learning under strict streaming constraints, including single-pass data processing, fixed memory budgets, and no prior knowledge of future data distributions. The key idea is to transform graph condensation into a clustering problem in the continuous Weisfeiler–Leman feature space, enabling efficient and model-independent memory construction. The authors further develop a streaming condensation algorithm with theoretical approximation guarantees and a practical fixed-memory implementation. Extensive experiments across different continual learning settings demonstrate that STREAMCGL achieves competitive predictive performance, mitigates catastrophic forgetting, and substantially reduces computational costs compared with existing methods.

Critical strengths

1 The paper addresses an important limitation of existing graph condensation methods for continual learning, namely their reliance on multiple optimization passes, prior knowledge of stream statistics, and potentially growing memory requirements. By explicitly considering single-pass processing, fixed memory budgets, and unknown future class distributions, STREAMCGL provides a practically relevant formulation that better aligns with real-world streaming scenarios.

2 The proposed gradient-free condensation framework effectively transforms graph condensation into a clustering problem in the continuous Weisfeiler–Leman feature space. This design eliminates expensive gradient-based condensation and enables efficient memory updates. The experiments cover multiple continual learning protocols and demonstrate competitive accuracy, reduced catastrophic forgetting, and substantial computational improvements over existing condensation baselines, particularly on large-scale graphs.

Critical weaknesses
  1. Although the paper establishes an O(log⁡nlog⁡k)O(\log n\log k) approximation guarantee, this result applies to the theoretical streaming clustering algorithm rather than the practical fixed-memory implementation used in experiments. The latter introduces heuristic compression and parallel processing without a corresponding approximation guarantee. Furthermore, the theoretical connection between representation distortion and downstream prediction quality is primarily established for linear readouts, leaving its applicability to nonlinear message-passing GNNs insufficiently justified. These gaps weaken the theoretical support for the proposed framework.

  2. The experiments primarily employ memory budgets defined as percentages of the overall stream size, which appears difficult to reconcile with the stated assumption that the total stream length is unknown. Moreover, the evaluation lacks a systematic investigation of how performance changes with increasing stream length, growing numbers of classes, and different intermediate memory capacities. Such analyses are important for validating the claimed fixed-memory scalability and robustness under realistic streaming conditions.

Questions for authors

1 Can the authors clarify whether the O(log⁡nlog⁡k)O(\log n\log k) approximation guarantee extends to the practical fixed-memory algorithm?

2 Since the experiments use budgets proportional to the overall stream size, does this introduce information about future data that would not be available in a strictly online setting?

3 comments

Ambiguity regarding the applicability of representation distortion bounds to non-linear message-passing GNNs.

We have updated Lemma 2 to explicitly address the generalization gap and its relationship to the quality of the condensation process. The revised lemma now provides a formal theoretical bound on the difference in classification probabilities between a GNN trained on the full-scale dataset and one trained on the condensed set. By bounding this discrepancy, we establish a formal link between the fidelity of the condensation and the resulting predictive performance. Although our theoretical guarantees focus on linear models, empirical results support their applicability to non-linear GNNs. The theoretical extension is non-trivial because, unlike linear models where propagation can be pre-computed, non-linear GNNs necessitate edge access during the propagation process. We identify it as a promising direction for future theoretical investigation.

(Q1) Clarification on whether the approximation guarantee extends to the practical fixed-memory algorithm.

Response> 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.

ARXIVMetricAlgo2Algo3
TimeAP44.4 +/- 0.847.9 +/- 0.6
AF-10.4 +/- 1.0-3.2 +/- 1.1
TotTime11736.3
MixedAP43.6 +/- 0.441.8 +/- 0.8
AF-8.5 +/- 0.4-2.2 +/- 1.0
TotTime173.377.5
ClassRAP60.5 +/- 0.160.9 +/- 0.6
AF-7.3 +/- 0.2-7.1 +/- 0.5
TotTime141.958.9
Dataset / TaskMetricAlgo2Algo3
Ogbn-mag
TimeAP12.3 +/- 0.319.5 +/- 0.5
AF-2.6 +/- 0.3-0.6 +/- 0.3
TotTime417.7113.2
MixedAP12.1 +/- 0.220.0 +/- 0.2
AF-4.1 +/- 0.2-1.0 +/- 0.2
TotTime845.6303.6
Corafull
ClassRAP69.8 +/- 1.068.9 +/- 0.6
AF-5.9 +/- 0.7-6.3 +/- 0.7
TotTime126161.9

The theoretical intuition is provided in Appendix D.1

(Q2) Clarification on whether using budget proportions relative to total stream size introduces look-ahead bias (information about future data) in an online setting.

Response: We clarify that setting the condensation budget bb as a percentage of the total stream size does not imply any knowledge of future data. In our experimental setup, bb is a pre-defined hyperparameter representing a fixed capacity (e.g., b=100b=100 nodes). We express this budget as a percentage (e.g., 1%1\% of NN) solely to provide a relative scale for comparison against the full dataset and to demonstrate how the method performs under varying levels of strictness.

The algorithm's decision-making process at any time step tt depends only on the current snapshot and the existing condensed set; it does not "look ahead" to adjust the budget based on the total final size of the stream. This is a standard practice in streaming literature to characterize the efficiency of an algorithm across different orders of magnitude of data volume.

Thank you for your rebuttal. The empirical comparison on W1 and the clarification on W2 are helpful. However, the theoretical gap limits the theoretical contribution of the work, and the lack of sensitivity analysis remains a concern. Therefore, I will maintain my original score.

We have added memory sensitivity analysis plots to the Appendix Fig.4, showing the effect of varying intermediate memory sizes by a factor of two and plotting AP over successive snapshots. For enhanced clarity, we also included Pareto curves in Appendix E.5 (Figs. 3 ) to illustrate the performance-efficiency trade-offs among various replay methods. Regarding the theoretical concerns, in addition to the emperical results, we have provided clarification on compression-based approximation quality in Appendix D.1. We also highlight that Lemma 2 now provides a direct theoretical link between clustering quality and the generalization gap, which serves as a clear motivation for our clustering-based approach.

Reviewer_KG36OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors introduce StreamCGL, a method for continual graph learning, specifically node classification. For each incoming graph snapshot, the node features XX are propagated ℓ\ell times to their neighbors to produce aggregated features Z(ℓ)Z^{(\ell)}. The edge information is discarded, and streaming kk-means methods are used to condense Z(ℓ)Z^{(\ell)} to a set of weighted centers. This condensed set is what is used in training to update the node classifier parameters. Experiments compare StreamCGL against other methods across multiple datasets and GNN architectures.

Critical strengths

None

Critical weaknesses

(1) The streaming formulation is underspecified. What exactly is being streamed? Problem 1 only specifies a limit bb on the condensed graph and that only the current graph snapshot is available. It does not specify the access model to the nodes, edges, or node features, nor what can/cannot be revisited. As written, unrestricted, centralized access to the current snapshot is allowed in Problem 1. It is unclear how prior methods are incompatible with streaming, under this formulation.

The meaning of "single-pass" is also unclear. Algorithm 2 refers to the stream consisting of the WL-refined features Z(ℓ)Z^{(\ell)}. As noted in Appendix B.5, "computing Z(ℓ)Z^{(\ell)} via Eq. 3 requires ℓ\ell sparse matrix–vector products". It is unclear how this is computed in the streaming model without maintaining all of the node features in memory at once and doing ℓ\ell passes over the edges.

(2) The analysis does not bound StreamCGL's validation-performance gap (the objective stated in Problem 1). All 3 of the steps have major flaws: (a) removing the edges via continuous WL aggregation, (b) condensing those features via kk-means, and (c) maintaining the kk-means summary with a fixed-memory algorithm.

(2a) The continuous WL relaxation for removing the edges is unsupported, even when no compression is applied. There is no guarantee that the averaging relaxations in Eqs. 2 and 3 match the expressivity of discrete 1-WL. For example, consider a pair of nodes connected by an edge, with features X=(−1,+1)X = (-1, +1) vs. X′=(0,0)X' = (0, 0). The averaging relaxations given would produce Z=Z′=(0,0)Z = Z' = (0, 0) for both graphs, but a message passing update zv=xv+12∑u∈N(v)xuz_v = x_v + \tfrac{1}{2} \sum_{u \in N(v)} x_u distinguishes the two cases. The empirical evidence for this claim in Table 6 has a typo: GraphSAGE on Arxiv has Δ=11.3\Delta = 11.3, not 1.31.3.

(2b) There is no bound on the classification error when training on the condensed kk-means set. Lemma 2 bounds the output differences of a fixed linear readout Θ\Theta. However, this does not mean that training Θs\Theta_{s} on the condensed set has similar classification error compared to training Θtr\Theta_{tr} on the full graph. Even under the assumption that the loss is smooth and Lipschitz, there is no guarantee that the training dynamics are similar.

(2c) There is no bound on the distortion of Algorithm 3. Lemma 5 discusses Algorithm 2, not Algorithm 3's repeated in-place shrinking operation. Application of Ailon et al.'s composition lemma for each summary shrinking operation (as in Lemma 5) would introduce multiplicative factors each time, which would accumulate.

(3) The presentation is exceptionally difficult to follow, even with careful reading. The meaning of "single-pass" can only be (partially) understood after reading through page 6. The notations are inconsistent and confusing. For example, the problem is defined for a fixed training and validation set, yet in Definition 5, an unexplained sampling distribution ZZ is introduced and immediately discarded. The classification error ϵ\epsilon is used three different ways on lines 110, 111, and 135, and not once is it directly related to the distortion objective ϕ\phi. It is a waste of the reviewer's time to decode the intended access model and key definitions from context scattered across the paper to even assess the claimed contribution.

(4) Section 4 claims that the code is available in the supplementary. The reproducibility statement says that all code has been made publicly available anonymously. To the best of my knowledge, these availability claims are not substantiated by the materials accessible to me.

These failures affect the central problem formulation, the justification for the reduction, and the claimed guarantees of the method. The submission does not establish its central claims and falls below an acceptable standard of technical rigor and clarity. I recommend clear rejection.

Questions for authors

(1) Please clarify the access model for the nodes, edges, and features of the current snapshot. (2) How do the size of the budget bb and the refinement depth ℓ\ell affect the overall memory usage and the overall classification error?

2 comments

Clarification on the streaming formulation, specifically regarding the access model for nodes, edges, and features and revisit constraints. Clarification on the "single-pass" implementation for WL-feature refinement relative to memory and pass requirements for sparse matrix-vector products.

Response> We clarify that our "streaming" formulation implies a one-pass access model with strictly limited memory. Specifically, once a subgraph (or snapshot) has been processed and integrated into the condensed representation, the original raw constituent nodes, edges, and features are evicted and cannot be revisited. We assume a sub-linear memory constraint relative to the total graph size, which necessitates an efficient condensation mechanism. To be precise, our model does not assume that individual edges within a subgraph appear in a single pass; rather, each subgraph is received and processed in its entirety using standard computational methods. The "single-pass" constraint applies to the sequence of subgraphs: once a snapshot is processed, the model must rely solely on the updated condensation rather than re-accessing the raw data. Regarding the incompatibility of prior methods, the distinction is not that they cannot process snapshots individually, but rather that they lack a mechanism to maintain or update a unified condensation of all previously observed subgraphs. Our work focuses on the ability to evolve a single, compressed representation continuously as new data arrives, while maintaing a fixed budget sublinear memory.

Ambiguity regarding the expressivity of continuous WL relaxation compared to discrete 1-WL (e.g., distinguishing specific node feature pairs).

Response> We wish to clarify that we do not claim the continuous relaxation of the WL kernel is equivalent to the 1-WL test. The purpose of this discussion is to motivate the problem by providing a meaningful metric for comparing two distinct subgraph embeddings. As noted in the paper, we utilize a linear message-passing operation (e.g., SGC) for the actual feature propagation; however, this choice is not restrictive, as any linear function with sufficient expressivity could be employed. Our objective in this component is not to propose a new state-of-the-art (SOTA) GNN architecture, but rather to provide a robust mechanism for capturing and preserving graph topology within the condensation.

(2b) Clarification on the connection between Lemma 2's output difference bounds and the classification error when training on the condensed set versus the full graph.

Response> We have updated Lemma 2 to explicitly address the generalization gap and its relationship to the quality of the condensation process. The revised lemma now provides a formal theoretical bound on the difference in classification probabilities between a GNN trained on the full-scale dataset and one trained on the condensed set. By bounding this discrepancy, we establish a formal link between the fidelity of the condensation and the resulting predictive performance.

(2c) Clarification on the distortion bound for Algorithm 3, specifically regarding the repeated in-place shrinking operation. Ambiguity regarding the accumulation of multiplicative factors from the composition lemma when applied across multiple shrinking operations.

Response> 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.

ARXIVMetricAlgo2Algo3
TimeAP44.4 +/- 0.847.9 +/- 0.6
AF-10.4 +/- 1.0-3.2 +/- 1.1
TotTime11736.3
MixedAP43.6 +/- 0.441.8 +/- 0.8
AF-8.5 +/- 0.4-2.2 +/- 1.0
TotTime173.377.5
ClassRAP60.5 +/- 0.160.9 +/- 0.6
AF-7.3 +/- 0.2-7.1 +/- 0.5
TotTime141.958.9
Dataset / TaskMetricAlgo2Algo3
Ogbn-mag
TimeAP12.3 +/- 0.319.5 +/- 0.5
AF-2.6 +/- 0.3-0.6 +/- 0.3
TotTime417.7113.2
MixedAP12.1 +/- 0.220.0 +/- 0.2
AF-4.1 +/- 0.2-1.0 +/- 0.2
TotTime845.6303.6
Corafull
ClassRAP69.8 +/- 1.068.9 +/- 0.6
AF-5.9 +/- 0.7-6.3 +/- 0.7
TotTime126161.9

The theoretical intuition is provided in Appendix D.1

(3) Clarification on the relationship between the sampling distribution in Definition 5 and the fixed training/validation sets, as well as the link between classification error and the distortion objective.

Repsonse> Acknowledged and addressed

(4) Code availability

Response> We have included the source code link in the Appendix E.1 section, which was mistakenly omitted from the initial submission.

(Q1) Clarification on the access model for nodes, edges, and features within the current snapshot. Investigation into how the budget size and refinement depth impact memory usage and overall classification error.

Response> The implemented access model follows the SGC (Simplified Graph Convolutional) framework, utilizing pre-aggregated neighborhood features. Regarding the impact of hyperparameters, Lemma 2 establishes a formal relationship between clustering quality and generalization error, while Lemma 3 demonstrates that increasing the memory budget directly improves clustering quality. We note that the refinement depth (number of layers) is an independent property of the GNN architecture rather than the condensation process itself; therefore, its impact on condensation quality is outside the scope of this study.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.