PaperlayerView exact revision on arXiv

Source-linked AI summary

CoPE-CGL: Community-aware Prototype Extraction for Replay-Free Continual Graph Learning

Bo-Young Lim, Seokhwan Kim, Kisung Lee, Hyuk-Yoon Kwon

arXiv:2610.35313v2cs.LGcs.DB

TL;DR

Continual graph learning must update models as graphs evolve while mitigating forgetting, but existing approaches often target only one graph setting or retain past graph data. CoPE-CGL centers learning, memory, and inference on a parameter-free structural prior, using task-specific adapters, community prototypes, and prototype-based routing. It reports higher AP than the second-best model by up to 1.41, 6.32, and 9.33 points across transductive, inductive, and mixed settings, respectively.

  • Problem

    Class-incremental CGL requires classifying nodes from all seen classes without task identifiers while mitigating forgetting, and prior methods often focus on a single setting or retain past graph data.

    Source: §2 · p. 2, §1 · p. 2

  • Method

    CoPE-CGL uses one parameter-free structural prior to support task-specific bottleneck adapters, community-level prototypes, and prototype-based task routing without a GNN backbone.

    Source: §1 · p. 2, §6 · p. 12

  • Results

    CoPE-CGL exceeds the second-best model by up to 1.41, 6.32, and 9.33 AP points across transductive, inductive, and mixed settings, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    CoPE-CGL maintains an evolving-graph model with constant storage per task and without retaining its own copy of past graph data.

    Source: §6 · p. 12

    The design assumes homophilic graphs with community structure, and the paper does not test heterophilic graphs.

    Source: §6 · p. 12

Abstract

from arXiv · show

Continual graph learning (CGL) maintains models as graphs evolve without retraining from scratch, while mitigating catastrophic forgetting. Existing methods typically target either transductive or inductive settings and often store past subgraphs or require task identifiers at inference. We propose Community-aware Prototype Extraction for Continual Graph Learning (CoPE-CGL), a replay-free framework that uses a parameter-free structural prior, precomputed by multi-hop Laplacian smoothing, to anchor learning, memory, and inference. CoPE-CGL combines topology-infused bottleneck adaptation, community-level prototypes, and dynamic routing by majority vote over node-to-prototype matches. The default protocol assumes each test graph comes from one learned task; a node-level variant handles mixed-task graphs. Each task adds at most a constant amount of storage, with no past graph data retained. At equal storage and without task identifiers, CoPE-CGL matches the strongest replay baseline even when it receives true task identifiers: average performance (AP) is 95.17% and 95.72% versus 94.28% and 95.82% on Arxiv and CoraFull, respectively, with 5.9-14.0 times faster runtime and zero forgetting. Across four transductive and three inductive benchmarks and mixed streams, CoPE-CGL exceeds the second-best of up to eleven baselines by up to 1.41, 6.32, and 9.33 AP percentage points, respectively. It runs 1.3-7.9 times faster end-to-end than the most accurate competitor on each benchmark and scales to the largest benchmark graph. On graphs mixing two tasks, its node-level variant achieves the best AP among CGL methods. The design targets homophilic graphs with community structure.

1 INTRODUCTION

Continual graph learning must maintain models as graph structure and labels evolve while mitigating forgetting, but existing methods face trade-offs in memory, plasticity, and coverage across settings. CoPE-CGL uses a shared parameter-free structural prior for learning, memory, and task-free inference, and reports gains across transductive, inductive, and mixed streams.

1 INTRODUCTION

  • Replay-based methods retain past graph data, raising privacy and data-retention concerns and limiting scalability under strict memory budgets; regularization can limit plasticity.The introduction also notes that TPP freezes its first-task-pretrained GNN backbone, while TAAM can lose earlier-task accuracy.Source: §1 · pp. 1–2
  • Existing CGL methods are often designed and evaluated primarily for one setting, and the compared methods had not evaluated interleaved transductive and inductive streams in their original papers.The introduction identifies this setting-specific bias as motivation for unified evaluation.Source: §1 · p. 2
  • CoPE-CGL organizes topology-infused bottleneck adaptation, community-aware prototype extraction, and graph-level dynamic routing around one parameter-free structural prior, enabling task-free inference without a GNN backbone.The prior supports learning, memory, and inference.Source: §1 · p. 2
  • CoPE-CGL stores at most M non-learned community-level prototypes per task and uses constant memory per task, without retaining past graph data.It runs 1.3–7.9× faster end to end than the most accurate competing baseline on each of seven benchmarks, and 1.1–14.0× faster across 35 mixed configurations.Source: §1 · p. 2
  • Across transductive, inductive, and mixed settings, CoPE-CGL beats the second-best model by up to 1.41, 6.32, and 9.33 AP points, respectively.It trails TACO or TPP only on DBLP, by at most 2.50 AP points.Source: §1 · p. 2

2 PROBLEM STATEMENT

The problem statement studies class-incremental continual graph learning, where task identities are withheld at inference and models must classify among all previously seen classes while mitigating forgetting. It distinguishes transductive, inductive, and mixed task regimes, and specifies a default single-task test-graph protocol alongside a node-level mixed-task evaluation.

2 PROBLEM STATEMENT

  • In class-IL, the model receives no task identifier at test time and must label each test node from all classes seen so far while mitigating catastrophic forgetting.Source: §2 · p. 2
  • The transductive regime uses disjoint task node sets and severs inter-task edges; the inductive regime allows earlier nodes to reappear, overlapping label spaces, and preserved inter-task edges.Source: §2 · p. 2
  • The mixed regime randomly interleaves transductive and inductive tasks, while the default test protocol assumes all test nodes come from one source task with its identity withheld.A separate evaluation considers test graphs spanning several tasks and infers the task per node.Source: §2 · p. 2
  • After learning a task, the replay-free setting forbids retaining earlier raw nodes, attributes, or labels; knowledge remains only in model parameters or compressed nonraw statistics.Source: §2 · pp. 2–3

3 METHODOLOGY

CoPE-CGL combines a precomputed structural prior, task-specific adaptation, community-level prototype memory, and prototype-based routing to classify test graphs without retaining past graph data.

3.1 Topology-Infused Bottleneck Adaptation

  • A precomputed K-hop Laplacian-smoothed embedding anchors a lightweight residual bottleneck adapter, which starts as the identity and is trained with a task-specific linear head.The same structural prior is reused for prototype extraction and test-time routing.Source: §3.1 · pp. 3–4

3.2 Community-Aware Prototype Extraction

  • CoPE-CGL partitions each task graph into communities and stores fixed centroids of their training-node base embeddings, capped at M prototypes and O(Md) memory per task.The prototypes are computed without gradient updates and preserve local neighborhood semantics; memory is independent of task-graph size.Source: §3.2 · p. 4
  • Matching nodes to their own community means rather than one global prototype reduces average norm-weighted squared distance, but does not itself enlarge margins to other tasks.The within-task approximation gap grows as community means spread apart in direction.Source: §3.2 · p. 4

3.3 Task-Free Inference and Dynamic Routing

  • At inference, nodes match by maximum cosine similarity to each task’s prototypes, and graph-level majority voting selects the adapter and classifier for the test graph.A new task leaves earlier task components unchanged; earlier-task accuracy is lost only when another task wins the vote.Source: §3.3 · p. 5
  • For a positive plurality margin, graph-level voting returns the correct task; it can succeed even when fewer than half of nodes vote for that task.The plurality margin was positive in all 294 transductive test-graph evaluations, and every vote was correct.Source: §3.3 · p. 5

3.4 Efficiency Analysis

  • Each task adds one adapter, one head, and at most M prototypes, keeping storage per task bounded and total task-growing storage O(Td) for fixed dimensions.Smoothing is paid once per task rather than repeated each training epoch; prototype matching grows linearly with the number of tasks.Source: §3.4 · p. 5

4 PERFORMANCE EVALUATION

CoPE-CGL is evaluated on seven benchmarks across transductive, inductive, and mixed streams, against eleven baselines, with a shared configuration across benchmarks and settings. It generally combines strong accuracy, low forgetting, and faster execution, while results also examine routing, robustness, memory, and scaling.

4.2.1 Main Results on the Individual Settings.

  • 0.65, 1.41, 0.04, and 0.22 AP points are CoPE-CGL’s transductive leads on CoraFull, Arxiv, Reddit, and Products; it leads on Kindle and ACM by 5.93 and 6.32 points.Its BWT is 0.00 across the transductive benchmarks and on DBLP, where it trails TACO and TPP in AP but runs faster.Source: §4.2.1 · p. 6, Table 2 · p. 7, Table 3 · p. 8

4.2.2 Main Results on the Mixed Settings.

  • 33 of 35 mixed-setting configurations have the best AP for CoPE-CGL, and 34 have its shortest runtime; BWT is zero or higher in 33.The two AP exceptions are DBLP at ratios 1:9 and 3:7, where TPP leads by 1.47 and 2.50 points, respectively.Source: §4.2.2 · p. 7, Table 4 · p. 9

4.2.3 Ablation Studies.

  • Removing smoothing lowers AP by 2.87 points on CoraFull and 40.11 on Kindle, while removing majority voting causes the largest CoraFull drop, 6.24 points.Removing community-aware prototypes lowers AP by 5.26 points on CoraFull and 1.43 on Kindle; removing the bottleneck lowers Kindle AP by 6.04 points.Source: §4.2.3 · p. 7, Table 5 · p. 10

4.3 Memory Efficiency at Matched Storage

  • At matched storage of about 0.4 MB on Arxiv and 48 MB on CoraFull, CoPE-CGL exceeds CaT by 33.48 and 15.82 AP points and runs 5.9× and 14.0× faster.CaT reaches 94.28% and 95.82% AP when given the true task identifier, close to CoPE-CGL, which infers the task.Source: §4.3 · p. 7, Table 6 · p. 10

4.4.1 Correlated Routing Errors and Task-ID Accuracy.

  • Graph-level routing picks the correct task in all 294 test cases, including 40 cases where at most half the nodes individually select it.With 10 sampled test nodes per graph, routing accuracy is 86.5–100%; with 100 nodes, it is 98.1–100%.Source: §4.4.1 · p. 7, Table 7 · p. 10

4.4.2 Mixed-Task Test Graphs.

  • 55.86% on Arxiv and 96.59% on Reddit are CoPE-CGL’s mixed-task AP scores, beating the strongest baseline by 15.74 and 23.72 points.On Arxiv, node-level task routing is a remaining difficulty: only 55.46% of nodes select the correct task on single-task test graphs.Source: §4.4.2 · pp. 8–9, Table 8 · p. 10

4.5 Robustness to Graph Structure

  • CoPE-CGL has the highest AP in 19 of 20 edge-noise settings, including all 16 noisy settings, and loses 5.09 points on average from 0% to 50% noise.Strongly heterophilic graphs remain outside the stated scope; five community detection algorithms yield 95.78–95.79% AP on CoraFull.Source: §4.5 · pp. 9–11, Table 9 · p. 10

4.6 Cost Breakdown, Scalability, and Sensitivity

  • On Products, CoPE-CGL leads TPP and TAAM in AP at every tested data scale and is faster than TPP at every scale; at 20% data it scores 95.88% versus TPP’s 95.42% at 100%.Adapter training dominates time on five benchmarks, while community detection dominates on Reddit and Products; for prototype counts, AP plateaus at 6 ≤ M ≤ 19.Source: Figure 4 · p. 11, §4.6 · p. 11

5 RELATED WORK

CoPE-CGL addresses model maintenance on evolving graphs without retaining past graph data, complementing graph-processing systems that maintain graphs and predict over a single graph. It differs from replay-based and replay-free CGL methods through its task memory and use of a shared structural prior.

RELATED WORK

  • Unlike replay-based methods that retain and replay graph data, CoPE-CGL stores an adapter and at most M community-level prototypes per task; the prototypes route test graphs, not retrain the model.Unlike prior replay-free methods, it avoids a pretrained or per-task GNN backbone.Source: §5 · pp. 11–12
  • Graph-processing systems maintain evolving graphs and predict over a single graph, whereas CoPE-CGL maintains a model without retaining its own copy of past graph data.Source: §5 · p. 11
  • The running-time breakdown reports component wall-clock times and shares; re-evaluation of earlier tasks is needed for AP and BWT, not deployment.Source: Table 11 · p. 12
  • Figure 5 compares Products AP as smoothing hops K, adapter scaling weight α, and prototype count M vary, against default-setting baseline means.CoPE-CGL curves are single runs; baseline lines are three-seed means.Source: Figure 5 · p. 12
  • TPP optimizes prompts during training and stores a task mean, while TAAM uses node-level modulators at each forward pass; PDGNN and PUMA precompute propagation but retain replay buffers.Source: §5 · p. 12

6 CONCLUSION

CoPE-CGL unifies task learning, memory, and inference around a parameter-free structural prior, using task-specific adapters, community prototypes, and graph-level majority voting. It avoids replay storage and recursive message passing, but assumes homophilic graphs with community structure and explicit task boundaries.

6 CONCLUSION

  • CoPE-CGL computes one parameter-free structural prior per task via SGC, then uses a task-specific bottleneck adapter, up to M community prototypes, and graph-level majority voting to route test graphs.Source: §6 · p. 12
  • The design avoids replay memory and recursive message passing while maintaining constant storage per task without retaining its own copy of past graph data.Source: §6 · p. 12
  • The default protocol assumes one task per test graph; the node-level variant still needs stream-provided graph boundaries, and Mixed AP on Arxiv is 55.86%.The design targets homophilic graphs with community structure; heterophilic graphs are not tested.Source: §6 · p. 12

A.1 Dataset Details

The appendix details seven public benchmarks and how mixed-setting task streams are constructed. The mixed-stream scheduler varies the transductive-to-inductive task ratio and randomizes task regimes after a fixed initial transductive task.

A.1 Dataset Details

  • The benchmarks comprise four transductive graphs—CoraFull, Arxiv, Reddit, and Products—and three inductive graphs—Kindle, DBLP, and ACM, with dataset-specific graph and feature construction.The transductive benchmarks follow the CGLB protocol; the inductive benchmarks follow the TACO protocol.Source: §A.1 · p. 14
  • For mixed streams, task regimes after the first task are drawn independently with the inductive probability set by ρ, then permuted per run; the first task is always transductive.This is intended to require handling arbitrary task orderings without prior schedule knowledge.Source: §A.1 · p. 14

A.2 Implementation Details

The implementation evaluates continual-learning performance and runtime across common benchmarks and task streams, while the algorithm precomputes task embeddings, trains adapters, and stores community prototypes for inference-time routing. The appendix also formalizes the design choices underlying the structural prior, prototype memory, and graph-level vote.

A.2 Implementation Details

  • Evaluation uses Average Performance (AP↑), measuring overall accuracy after all tasks, and Backward Transfer (BWT↑), measuring how much later-task training impacts earlier tasks; higher is better.Source: §A.2 · p. 14
  • Seeds control initialization, shuffling, mini-batching, and baseline-specific sampling, but do not reproduce CoPE-CGL exactly; ten Arxiv reruns of one seed yielded AP from 95.13% to 95.24%.Source: §A.2 · p. 14
  • Replay baselines use per-task memory budgets and shared task streams; baselines follow original settings, while CoPE-CGL uses one untuned configuration across benchmarks and settings.The bottleneck width follows a fixed rule based on input dimension, and the authors do not tune CoPE-CGL on validation or test performance.Source: §A.2 · pp. 14–15

B ALGORITHM

  • For each incoming task, the algorithm computes a parameter-free K-hop smoothed embedding, initializes a task adapter and head, and trains them over the precomputed embedding.Zero-initializing the adapter's up-projection makes the initial adapted embedding equal to the base embedding.Source: B ALGORITHM · p. 15
  • After training, the algorithm selects up to M largest communities and stores the mean base embedding of each community, avoiding storage of raw nodes or edges.Source: B ALGORITHM · p. 15
  • At inference, nodes are projected with the same parameter-free operation, matched to task prototypes by cosine similarity, and their predictions are combined by graph-level majority vote.The resulting task selects the adapter and classifier used for label prediction.Source: B ALGORITHM · p. 15

C FORMAL STATEMENTS AND PROOFS

  • The formal results justify three design choices: a precomputed low-pass prior, community-level rather than single-centroid memory with max-over-prototypes matching, and graph-level voting over node-wise routing.Source: C FORMAL STATEMENTS AND PROOFS · p. 15

C.1 Proof of Proposition 1 (Laplacian Low-Pass Filtering)

The proof characterizes multi-hop normalized-adjacency smoothing as a low-pass filter that preserves smooth graph signals while attenuating high-frequency components. The framework precomputes this structural embedding before task-specific adaptation.

C.1 Proof of Proposition 1 (Laplacian Low-Pass Filtering)

  • The normalized adjacency has an orthonormal eigendecomposition, and its eigenvalues define the graph-signal components used to characterize the smoothing response.The proof expresses the signal in the eigenbasis and describes the response as (1 − μ)^K, equal to one at μ = 0 and below one in absolute value elsewhere.Source: §C.1 · p. 15
  • CoPE-CGL computes the structural base embedding by applying K-hop smoothing to the task graph, then initializes a task-specific bottleneck adapter and classifier.The algorithm specifies a static precomputation of the normalized adjacency aggregation before adapter optimization.Source: §C.1 · p. 16
  • For even K, the smoothing response can rise again for μ > 1, but the base embedding retains smooth homophilous content while attenuating high-frequency components.Accuracy saturates around K = 2 to 3 as additional smoothing yields diminishing returns after high-frequency noise is damped.Source: §C.1 · p. 16

C.2 Proof of Proposition 2 (Within-Task Approximation)

The proof compares community prototypes with node embeddings within a task and bounds the loss from retaining only the top-M matching prototypes. Its approximation claim is in-sample and does not itself guarantee separation from other tasks' prototypes.

C.2 Proof of Proposition 2 (Within-Task Approximation)

  • Community means minimize the weighted distance of their training nodes over all unit-vector directions, with the tightening greatest when community means point in different directions.The result holds for any partition; the text notes that Louvain supplies a partition from the task's edges without fixing the number of groups.Source: §C.2 · p. 16
  • The within-task approximation concerns the task's own training nodes, not the margin to other tasks' prototypes or test-node routing accuracy.The text says inference-time gains depend on test nodes resembling their community's training nodes, which is evaluated separately through task-ID accuracy.Source: §C.2 · p. 16
  • 0 ≤ ε_M ≤ 2 E_v∈U[r(v)] bounds the top-M truncation gap through the per-node loss in prototype matching score.At default M = 10, Table 13 reports the measured gap and bound; its caption identifies the reported quantities and test-node comparison.Source: §C.2 · p. 16, Table 13 · p. 16

C.3 Proof of Proposition 3 (Majority-Vote Consistency)

The majority-vote proof gives conditions under which graph-level routing selects the source task, including a probability guarantee when nodes are sampled. Its bound allows dependence between neighboring-node votes.

C.3 Proof of Proposition 3 (Majority-Vote Consistency)

  • If the source task's vote share exceeds one half, it wins the full graph-level vote; a positive margin over every competitor also makes it the mode.The proof defines the source share and margin and contrasts the winning case with a negative margin.Source: §C.3 · p. 17
  • With positive margin γ, sampling N nodes returns the source task with probability at least 1 − (T−1) exp(−Nγ^2/2), even when graph-neighbor votes are correlated.The randomness is from sampling; the bound does not assume independent node votes, though correlation can change the margin.Source: §C.3 · p. 17

D EXTENDED COMPARISON

  • The appendix expands the Section 3.4 comparison into an architectural and computational contrast with the two closest replay-free baselines.Source: D EXTENDED COMPARISON · p. 17

D.1 Comparison with Existing Replay-Free Methods

The comparison attributes CoPE-CGL's replay-free design to a shared precomputed structural embedding, community-level prototypes, and task-specific bottleneck adaptation. The components connect prototype memory to routing while keeping the trainable pathway task-specific.

D.1 Comparison with Existing Replay-Free Methods

  • CoPE-CGL statically precomputes structural features and adapts them with a lightweight bottleneck, avoiding epoch-level message passing and complex node-level modulators used by the compared methods.Its prototypes come directly from the same precomputed embedding used for adaptation, without additional training cost.Source: §D.1 · p. 17

D.2 Novelty against Single-Centroid Prototypes

  • Community prototypes represent local feature-space modes, unlike the single global prototype used by TPP and TAAM [21] [25], allowing queries from diverse neighborhoods to match different task regions.Routing and adaptation use the same base embedding.Source: §D.2 · p. 17

D.3 Implication of TIBA

  • Because the structural prior is shared across tasks, adaptation remains anchored to a non-drifting structural manifold and stored prototypes stay compatible with future query embeddings.The text describes new tasks as adding bounded perturbations around the shared base embedding.Source: §D.3 · p. 17

D.4 Putting the Three Components Together

  • Inference projects the test graph, matches nodes to the full prototype memory, aggregates task votes, then applies only the selected task's adapter and classifier.The parameter-free steps precede and gate the trainable pathway; prototypes serve as compact memory and a discrete router.Source: §D.4 · p. 17

D.5 LwF

  • LwF reports 2.90–7.98% AP on the four transductive benchmarks, so the paper omits it from reported comparisons.Source: §D.5 · p. 17

D.6 Choice of Community Detector

  • Across four alternative community detectors on CoraFull, CoPE-CGL exceeds the strongest Table 2 baseline, SAFER at 95.13% AP, while graph-level voting selects the correct task on every test graph.Per-node routing accuracy ranges from 70.76% with Infomap to 75.84% with Fast-Greedy.Source: §D.6 · p. 18, Table 14 · p. 18

E MODEL-MAINTENANCE MEASUREMENTS

In a 70-task CoraFull stream, storage grows linearly and routing selects the correct task for 68 of 70 test graphs. Routing accuracy also improves as more test nodes vote, while per-task Arxiv training time and peak GPU memory are measured separately.

Cost of adding a task

  • Per-task Arxiv training time and peak GPU memory are measured on an A100 with seed 1024, excluding re-evaluation of earlier tasks; all runs use PyTorch 2.4.1 and CUDA 12.1.Peak GPU memory is reset at the start of each task and read at its end.Source: E MODEL-MAINTENANCE MEASUREMENTS · p. 18, Table 15 · p. 18

A long task stream

  • At T=70, storage grows linearly and routing selects the correct task for 68 of 70 test graphs; within-task accuracy is trivially 100% with one class per task.Storage growth is mostly in adapters, and the table omits within-task accuracy because it is trivial in this setup.Source: E MODEL-MAINTENANCE MEASUREMENTS · p. 18

How many nodes the vote needs

  • With 10 sampled test nodes, routing is correct for 86.48–100% of test graphs, rising to 98.07–100% with 100 nodes.A single node routes correctly in 52.78–98.89% of test graphs; results use three draws and models trained with seeds 1024–1026.Source: E MODEL-MAINTENANCE MEASUREMENTS · p. 18

Related papers

Loading 2610.35313v2…