Topology-aware Embedding Memory for Learning on Expanding Graphs

We sincerely appreciate the reviewer for recognizing our writing quality and empirical merits. We have carefully prepared responses to the concerns/questions from the reviewer below.

Q1. From my understanding, the Topology-aware Embedding Memory is to replace the dynamic message passing aggregation of the subgraph with the fixed representation, I have concern about the novelty.

A1. Thanks for this nice concern, and we are happy to have the opportunity to further clarify our novelty.

First, besides the TE generation (i.e. replacing the message passing with fixed representations mentioned by the reviewer), which is a part of our proposed PDGNNs-TEM framework, the whole framework is innovative, effective, and has important practical implications. Our proposed PDGNNs-TEM, for the first time, resolves the memory explosion problem and enable full preservation of the topological information. As recognized by the reviewer, this framework can significant improve the performance on multiple large datasets, especially in the challenging class-IL scenario. This general framework for tackling the memory explosion problem was never developed in existing works.

Second, we made the first theoretical attempt to analyze the relationship between the stored data and the remaining ones in the context of continual learning on expanding graphs. This effort resulted in the theoretical results on the pseudo-training effect (Section 3.5).

Third, based on the theoretical findings, we proposed the novel coverage maximization sampling technique (Section 3.6). This technique could enlarge the coverage ratio and further boost the performance, especially when the memory budget is tight.

Above all, besides the operation to replace message passing, our work actually consists many innovative elements including the framework, theoretical analysis, and the coverage maximization sampling scheme.

Q2. how does the subgraph size influence the quality of the topology-aware Embedding? and how to choose the subgraph size for computing?

A2.

Thanks for the nice question, which is a keen observation. In our work, the theoretical analysis on the pseudo-training effect (Section 3.5) can answer this question.

According to the pseudo-training effect (Section 3.5), the larger the computation ego-subgraph, the more nodes benefit from the mempry replay. Therefore, the Topology-aware Embeddings (TEs) with larger computation ego-subgraphs are preferred. Accordingly, we have defined the concept of coverage ratio and developed the novel coverage maximization sampling strategy (Section 3.6) for obtaining higher quality TEs. The effectiveness of coverage maximization sampling is also validated in experiments (Table 1 in page 7, Section 4.3).

We hope that our explanations can help clarify our novelty and answer the question on the influence of subgraph sizes. We are also more than happy to address any remaining concern.

Q2. Reproducibility and Open Access: It is not mentioned whether the authors plan to make their code, dataset, or pre-trained models available for the research community. This could be a weak point, as open access to these resources is essential for the reproducibility and widespread adoption of the proposed approach.

A2. Thanks for the nice concern. We will make all of the code, dataset, and the pre-trained models be publicly available in the final version.

We sincerely hope that our responses can address the concerns of the reviewer. We are also happy to address any remaining concern.

We sincerely appreciate the reviewer for recognizing our in-depth discussion on the literature, as well as the strong and comprehensive empirical results. We have carefully prepared responses to the concerns/questions from the reviewer below.

Q1. A potential weak point of the paper is the perceived limitation in technical novelty. The paper could be interpreted as an application of decoupled GNNs to the continual learning domain, which has already been acknowledged for its computational efficiency benefits. However, I believe that combining existing, well-established techniques that work efficiently is a valid approach in research. It's essential to leverage the best tools available to address complex problems effectively. In this case, applying decoupled GNNs to the continual learning context is a sensible choice, as it capitalizes on the advantages of both areas. However, it would be beneficial to describe clearly the paper's contribution, impact, and novel techniques.

A1. Thanks for the nice suggestion. We are happy to further clarify our contribution, novelty, and impact in the following.

1. A novel and effective framework. As recognized by the reviewer, our proposed PDGNNs-TEM framework, for the first time, resolves the memory explosion problem and enable full preservation of the topological information, which significantly improves the performance on multiple large datasets, especially in the challenging class-IL scenario.

Besides, the contribution of PDGNNs (backbone part of PDGNNs-TEM) lies in presenting a general framework, in which TEs can be derived. Some existing decoupled GNNs can be viewed as instantiations of PDGNNs, but not all of them. As mentioned by the reviewer, the existing decoupled GNNs focus on improving the computational efficiency. Accordingly, they focus on decoupling the neighborhood aggregation and the node feature transformation, without the specific consideration on decoupling the trainable parameters, e.g. APPNP [1], PTA [2], etc. In these decoupled GNNs, the trainable parameters are still entangled with individual nodes in the computation ego-subgraph, therefore TEs cannot be derived and our TEM cannot be implemented. In contrast, our PDGNNs framework explicitly requires decoupling the trainable parameters from the computation ego-subgraphs, and the TEs can be derived (Section 3.3).

2. Theoretical contribution. In this work, we made the first theoretical attempt to analyze the relationship between the stored the data and the remaining ones in the field of continual learning on expanding graphs. This effort resulted in the theoretical results on the pseudo-training effect (Section 3.5).

3. A novel sampling technique (Section 3.6). Based on the theoretical findings, we proposed the coverage maximization sampling technique. This technique could enlarge the coverage ratio and further boost the performance, especially when the memory budget is tight (Table 1, page 7).

4. Impact. Our proposed PDGNNs-TEM can generally benefit various graph data related research areas. As introduced in the Introduction (paragraph 1), since a majority of real-world graphs are expanding over time with distribution shift, the studied problem is practically important in many real-world applications, and are attracting researchers from various communities.

For example, in the recommender system research, new products and new users are continuously added to the purchasing network. In this case, the recommender system have to keep learning new patterns emerging in the new data without forgetting the patterns learnt from previous observations [4,5]. Besides, knowledge graph is also growing over time with new knowledge added, and a machine learning model is required to keep adapting to new knowledge without forgetting the previous ones [3]. Moreover, expanding graphs also exist in many other fields, like papers are constantly increasing in citation networks, new users/posts constantly emerge in social networks, etc. In all these applications, the core problem is the continual learning on expanding graphs studied in our paper, and are extensively studied by researchers [6,7,8,9,10].

Our proposed method is a general solution for representation learning in this continual learning scenario, and can be applied to all these different applications. This is also demonstrated by our comprehensive experiments on different graph types including social network, product co-purchasing network, and citation networks.

[1] Klicpera, Johannes, Aleksandar Bojchevski, and Stephan Günnemann. "Predict then propagate: Graph neural networks meet personalized pagerank." arXiv preprint arXiv:1810.05997 (2018).

[2] Dong, Hande, et al. "On the equivalence of decoupled graph convolution network and label propagation." Proceedings of the Web Conference 2021. 2021.

[3] Ahrabian, Kian, et al. "Structure aware experience replay for incremental learning in graph-based recommender systems." Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021.

[4] Xu, Yishi, et al. "Graphsail: Graph structure aware incremental learning for recommender systems." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[5] Daruna, Angel, et al. "Continual learning of knowledge graph embeddings." IEEE Robotics and Automation Letters 6.2 (2021): 1128-1135.

[6] Carta, Antonio, et al. "Catastrophic forgetting in deep graph networks: an introductory benchmark for graph classification." arXiv preprint arXiv:2103.11750 (2021).

[7] Zhang, Xikun, Dongjin Song, and Dacheng Tao. "Cglb: Benchmark tasks for continual graph learning." Advances in Neural Information Processing Systems 35 (2022): 13006-13021.

[8] Liu, Huihui, Yiding Yang, and Xinchao Wang. "Overcoming catastrophic forgetting in graph neural networks." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 10. 2021.

[9] Galke, Lukas, et al. "Lifelong learning of graph neural networks for open-world node classification." 2021 International Joint Conference on Neural Networks (IJCNN). IEEE, 2021.

[10] Han, Yi, Shanika Karunasekera, and Christopher Leckie. "Graph neural networks with continual learning for fake news detection from social media." arXiv preprint arXiv:2007.03316 (2020).

Q5. Overall, the scope of the problem has limited value. There are not many practical use cases with this setting.

A5. Thanks for this concern.

As introduced in the Introduction (paragraph 1) of the paper, since a majority of real-world graphs are expanding over time with distribution shift, the studied problem is practically important in many real-world applications, and are attracting researchers from various communities.

For example, in the recommender system research, new products and new users are continuously added to the purchasing network. In this case, the recommender system have to keep learning new patterns emerging in the new data without forgetting the patterns learnt from previous observations [1,2]. Besides, knowledge graph is also growing over time with new knowledge added, and a machine learning model is required to keep adapting to new knowledge without forgetting the previous ones [3]. Moreover, expanding graphs also exist in many other fields, like papers are constantly increasing in citation networks, new users/posts constantly emerge in social networks, etc. In all these applications, the core problem is the continual learning on expanding graphs studied in our paper, and are extensively studied by researchers [4,5,6,7,8].

Our proposed method is a general solution for representation learning in this continual learning scenario, and can be applied to all these different applications. This is also demonstrated by our comprehensive experiments on different graph types including social network, product co-purchasing network, and citation networks.

[1] Ahrabian, Kian, et al. "Structure aware experience replay for incremental learning in graph-based recommender systems." Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021.

[2] Xu, Yishi, et al. "Graphsail: Graph structure aware incremental learning for recommender systems." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[3] Daruna, Angel, et al. "Continual learning of knowledge graph embeddings." IEEE Robotics and Automation Letters 6.2 (2021): 1128-1135.

[4] Carta, Antonio, et al. "Catastrophic forgetting in deep graph networks: an introductory benchmark for graph classification." arXiv preprint arXiv:2103.11750 (2021).

[5] Zhang, Xikun, Dongjin Song, and Dacheng Tao. "Cglb: Benchmark tasks for continual graph learning." Advances in Neural Information Processing Systems 35 (2022): 13006-13021.

[6] Liu, Huihui, Yiding Yang, and Xinchao Wang. "Overcoming catastrophic forgetting in graph neural networks." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 10. 2021.

[7] Galke, Lukas, et al. "Lifelong learning of graph neural networks for open-world node classification." 2021 International Joint Conference on Neural Networks (IJCNN). IEEE, 2021.

[8] Han, Yi, Shanika Karunasekera, and Christopher Leckie. "Graph neural networks with continual learning for fake news detection from social media." arXiv preprint arXiv:2007.03316 (2020).

Q6. It is confusing for readers to understand the relationships between PDGNN and TEM. What makes a PDGNN? Does it mean we combine any MPNN with TEM?

A6. Thanks for this nice question. We are happy to further clarify what makes a PDGNN, as well as the relation between PDGNN and TEM.

First, as analyzed in Section 3.2 and 3.3, the principle of designing PDGNNs is to decouple the trainable parameters from the neighborhood aggregation operation (for capturing topological information). In this way, the trainable parameters act on the computation ego-subgraph as a whole (via the TEMs), and are not involved in computation with individual nodes in the computation ego-subgraph, thereby the storage of the complete computation ego-subgraph is avoided. To summarize, PDGNN is a framework of GNNs in which the trainable parameters do not participate in computation with individual nodes in the computation ego-subgraph, but not any MPNN.

Second, as explained in the paragraph above Equation (6) of the paper, TEM refers to the memory buffer that stores Topology-aware embeddings (TEs). And TE is the connection between TEM and PDGNNs. Specifically, as introduced in Section 3.3, only within the PDGNNs framework can we derive the TE as a single-vector representation of the computation ego-subgraph. Therefore, TEM can only be implemented with the PDGNNs framework. For an arbitrary MPNN that does not decouple the trainable parameters, TE cannot be derived, therefore TEM cannot be used either.

To summarize, PDGNNs are specially designed for obtaining TEs and using TEM. Also, TEM can only be used with PDGNNs, but not any MPNN.

We sincerely hope that our explanations can address the concerns and answer the questions from the reviewer. We are also more than happy to address any remaining concern.

Q3. The experimental datasets are limited. First, it is not clear why Cora and OGB datasets are proper for the expanding graphs problem. I hope the authors can evaluate the methods on more practically useful expanding graph datasets.

A3. Thanks for this suggestion. As introduced in Section 4.1, the datasets are actually public benchmark datasets in the field, and are specially pre-processed for continual learning on expanding graphs.

Specifically, CoraFull and OGB datasets are pre-processed by the Continual Graph Learning Benchmark (CGLB) [1]. In CGLB, the datasets are first split into subgraphs (tasks) according to the classes. Then the subgraphs are gradually connected to simulate the expanding process of the graph. Moreover, these datasets are representative for the naturally expanding graphs. First, CoraFull and OGB-Arxiv are constructed based on real-world citation networks, and new papers with potential new classes are constantly emerging in real-world citation networks. Second, the OGB-Products is a co-purchasing network constructed based on real-world shopping data from Amazon. On real-world shopping platforms like Amazon, new products and users also emerge continuously.

These benchmark datasets, as well as the splitting scheme, are widely adopted by the field of continual learning on expanding graphs [2,3]. This class based dataset splitting can effectively ensure the diversity in task distributions, therefore is adopted in different continual learning research on expanding graphs [1,4], images [5,6], etc.

[1] Zhang, Xikun, Dongjin Song, and Dacheng Tao. "Cglb: Benchmark tasks for continual graph learning." Advances in Neural Information Processing Systems 35 (2022): 13006-13021.

[2] Sun, Li, et al. "Self-supervised continual graph learning in adaptive riemannian spaces." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.

[3] Liu, Huihui, Yiding Yang, and Xinchao Wang. "Overcoming catastrophic forgetting in graph neural networks." Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 10. 2021.

[4] Carta, Antonio, et al. "Catastrophic forgetting in deep graph networks: an introductory benchmark for graph classification." arXiv preprint arXiv:2103.11750 (2021).

[5] Rebuffi, Sylvestre-Alvise, et al. "icarl: Incremental classifier and representation learning." Proceedings of the IEEE conference on Computer Vision and Pattern Recognition. 2017.

[6] Van de Ven, Gido M., and Andreas S. Tolias. "Three scenarios for continual learning." arXiv preprint arXiv:1904.07734 (2019).

Q4. The main claim, memory cost reduction, is not validated. There is no memory analysis in the main paper. I found the discussions on the Appendix, but I think it should appear in the main paper and be more thoroughly discussed.

A4. Thanks for this nice suggestion. In the revised version of the main paper, we have carefully added the discussion on the memory cost reduction in a new subsection (Section 4.5) to discuss the empirical memory efficiency PDGNNs-TEM.

In Section 4.5, the actual memory usage (the number of float32 values) of different memory based methods after learning each entire dataset are provided in Table 4 ,page 9. As a reference, the memory consumption of storing full computation ego-subgraph is also calculated. The table is also provided below for convenience.

Q2. I hope the authors can showcase the true insights behind PDGNN, potentially via an ablation study, demonstrating which component really works.

A2. Thanks for this nice concern on the functionality of each component. We are more than happy to have the opportunity to further clarify the insights.

Briefly speaking, the insights are:

1. Topological-aware Embedding Memory (TEM) is the main reason of the significant performance improvement.

2. The functionality of the PDGNNs framework is to enable the implementation of TEM, i.e. TEM cannot work without PDGNNs.

3. Coverage maximization sampling serves to further boost the performance especially when the memory budget is tight.

First, our proposed PDGNNs-TEM mainly consists of the following components: 1. the memory buffer TEM with the sampling strategy, 2. the backbone model PDGNNs consisting of $f_{topo}$ and $f_{out}$.

To investigate the functionality of each component, typical ablation study would try to remove one of the component and check how the performance is influenced. Within our PDGNNs-TEM, the backbone PDGNNs cannot be removed, and only TEM is removable. We could definitely provide the results of PDGNNs without TEM, as shown in the table below. Just like any GNN without continual learning technique, PDGNNs alone will suffer from catastrophic forgetting. This is empirically justified in the paper by the results of 'Fine-tune' shown in Table 2 and 3 (page 7 and 9).

However, for our continual learning research, this only justifies the existence of catastrophic forgetting phenomenon, but cannot reflect why our continual learning technique is superior over the baselines.

Therefore, in the paper, we have designed experiments to investigate our PDGNNs-TEM from multiple perspectives, and to demonstrate the functionality of each component.

First, the advantage of our TEM is that it completely store the topological information. Therefore, to test whether full topological information preservation is crucial, we include two other memory replay based baselines ER-GNN and SSM in Table 2 and 3 (page 7 and 9). ER-GNN stores individual nodes and completely ignore the topological information, while SSM stores sparsified computation ego-subgraphs with partial topological information preserved. According to the results, our PDGNNs-TEM outperforms SSM, and SSM outperforms ER-GNN. In other words, the more topological information is preserved, the better the performance is. This demonstrates the importance of topological, and justifies that TEM is a crucial part.

Second, as introduced in Section 3.2 and 3.3, Topology-aware Embeddings (TEs) can only be derived in the proposed PDGNNs framework. Therefore, to implement TEM, which is the key to the performance improvement, PDGNNs is an indispensable component.

Finally, as introduced in Section 3.5 and 3.6, with the PDGNNs framework, we theoretically justified the existence of pseudo-training effect, based on which we develop the coverage maximization sampling technique. This sampling technique can select the TEs that are more effective for alleviating the forgetting problem, which is advantageous especially for the tight memory budget situation, as empirically justified in Section 4.3.

We hope the explanations above could clarify the insights of our work.

Algorithm Inference of PDGNNs-TEM

Input: Test task sequence $\mathcal{S}$ = {$\mathcal{G}\_{1}$, $\mathcal{G}\_{2}$,...,$\mathcal{G}\_{T}$}, function $\mathrm{f}\_{topo} (\cdot)$, $\mathrm{f}\_{out}(\cdot; \boldsymbol{\theta})$.

Output: Constructed memory buffer $\mathcal{TEM}$, trained parameters $\boldsymbol{\theta}$.

  1: for each $\mathcal{G} \in \mathcal{S}$

  2:     Calculate the TEs for nodes in node set $\mathbb{N}\_{\tau}$ of $\mathcal{G}\_{\tau}$

  3:     {$\mathbf{e}\_v \mid \mathbf{e}\_v = \mathrm{f}\_{topo}(\mathcal{G}\_{v}^{sub}), v \in \mathbb{V}\_{\tau}$}

  4:     Calculate final prediction of nodes in $\mathbb{N}\_{\tau}$

  5:     {$\hat{\mathbf{y}}\_v \mid \hat{\mathbf{y}}\_v=\mathrm{f}\_{out}(\mathbf{e}\_v;\boldsymbol{\theta}) , v \in \mathbb{V}\_{\tau}$}

  6: end for each

During training, when learning on each task, function $\mathrm{f}\_{topo}(\cdot)$ will first generate the TE for each node, which is subsequently fed into the output function $\mathrm{f}\_{out}(\cdot; \boldsymbol{\theta})$ to get the final prediction. After obtaining the predictions, the loss $\mathcal{L}\_{\tau}$ is calculated based on the predictions and the ground-truth labels. The same procedure is also conducted for data in the memory buffer $\mathcal{TEM}$ to get the loss $\mathcal{L}\_{aux}$. Then a total loss is obtained by summing up $\mathcal{L}\_{\tau}$ and $\mathcal{L}\_{aux}$ with $\lambda$ to balance the contribution from classes with different sizes. After learning each task, the memory buffer will be updated with new representative data selected by the sampling function $\mathrm{sampler}(\cdot, \cdot)$.

During testing, only the inference stage is conducted. The given data will sequentially go through function $\mathrm{f}\_{topo}(\cdot)$ and $\mathrm{f}\_{out}(\cdot;\boldsymbol{\theta})$ to get the final prediction.

We sincerely appreciate the reviewer for recognizing our theoretical merits and our contribution in significantly reducing the memory complexity. We have carefully responded to every concern or question of the reviewer. We have also seriously taken the suggestions and revised the paper. The revised parts are highlighted in blue.

Q1. The PDGNN and TEM definitions are vague. I hope the paper can include concrete algorithms to showcase how they are implemented. Overall, the formation of PDGNN looks overly complex to me.

A1. Thanks for this nice suggestion. To further clarify the definitions of PDGNNs and TEM, we have added detailed algorithms in Appendix C.3 (page 29) to explain the workflow of PDGNNs-TEM step by step, which are also provided below.

Algorithm Training of PDGNNs-TEM

Input: Training task sequence $\mathcal{S}$ = {$\mathcal{G}\_{1}$, $\mathcal{G}\_{2}$,...,$\mathcal{G}\_{T}$}, function $\mathrm{f}\_{topo} (\cdot)$, $\mathrm{f}\_{out}(\cdot; \boldsymbol{\theta})$, sampling function $\mathrm{sampler}(\cdot, \cdot)$, memory budget $n$, loss function $l(\cdot,\cdot)$, neural network optimizer $\mathrm{Optimizer(\cdot,\cdot)}$, number of epochs $M$.

Output: Constructed memory buffer $\mathcal{TEM}$, trained parameters $\boldsymbol{\theta}$.

  1: Initialize $\mathcal{TEM}$ = {}.

  2: for each $\mathcal{G} \in \mathcal{S}$ do

  3:      for each $\mathrm{epoch} \in$ {$1,...,M$} do

  4:          Calculate the TEs for nodes in node set $\mathbb{N}\_{\tau}$ of $\mathcal{G}\_{\tau}$.

  5:          {$\mathbf{e}\_v \mid \mathbf{e}\_v = \mathrm{f}\_{topo}(\mathcal{G}\_{v}^{sub}), v \in \mathbb{V}\_{\tau}$}

  6:          Calculate final prediction of nodes in $\mathbb{N}\_{\tau}$

  7:          {$\hat{\mathbf{y}}\_v \mid \hat{\mathbf{y}}\_v=\mathrm{f}\_{out}(\mathbf{e}\_v;\boldsymbol{\theta}) , v \in \mathbb{V}\_{\tau}$}

  8:          Calculate loss of the current task $\tau$

  9:          $\mathcal{L}\_{\tau} = \sum\_{v \in \mathbb{V}\_{\tau}} l(\mathrm{f}\_{out}(\mathbf{e}\_v; \boldsymbol{\theta}), \mathbf{y}\_v)$

10:          Calculate the TEs for nodes in memory $\mathcal{TEM}$

11:          {$\mathbf{e}\_v \mid \mathbf{e}\_v = \mathrm{f}\_{topo}(\mathcal{G}\_{v}^{sub}), v \in \mathcal{TEM}$}

12:          Calculate final prediction of nodes in $\mathcal{TEM}$

13:          {$\hat{\mathbf{y}}\_v \mid \hat{\mathbf{y}}\_v=\mathrm{f}\_{out}(\mathbf{e}\_v;\boldsymbol{\theta}) , v \in \mathbb{V}\_{\tau}$}

14:          Calculate the auxiliary loss for preventing forgetting

15:          $\mathcal{L}\_{aux} = \sum\_{\mathbf{e}\_w \in \mathcal{TEM}} l(\mathrm{f}\_{out}(\mathbf{e}\_w;\boldsymbol{\theta}), \mathbf{y}\_w)$

16:          Calculate balancing parameter $\lambda$ according to the class sizes in $\mathbb{N}\_{\tau}$ and $\mathcal{TEM}$

17:          Calculate the total loss

18:          $\mathcal{L}\_{total} = \mathcal{L}\_{\tau} + \lambda \mathcal{L}\_{aux}$

19:          Calculating the gradients of the trainable parameters $\frac{\partial \mathcal{L}\_{total}}{\partial \boldsymbol{\theta}}$.

20:          Update $\boldsymbol{\theta}$ with the optimizer

21:          $\boldsymbol{\theta} = \mathrm{Optimizer}(\boldsymbol{\theta},\frac{\partial \mathcal{L}\_{total}}{\partial \boldsymbol{\theta}})$

22:      end for each

23:      Update the memory buffer

24:      $\mathcal{TEM}=\mathcal{TEM} \; \bigcup \; \mathrm{sampler}(${$\mathbf{e}\_v \mid v\in \mathbb{V}\_{\tau}$}, $n)$

25: end for each

We sincerely thank the reviewer for the constructive comments.

In our detailed responses, we have tried our best to address all the concerns.

Given that the discussion period is approaching to the end, we will appreciate if the reviewer can advise whether there is any remaining concern, and we are more than happy to address them.

We sincerely thank the reviewer for the constructive comments.

Given that the discussion period is ending in 2 days, we will appreciate if the reviewer can advise whether there is any remaining concern, and we are more than happy to address them.

We sincerely thank the reviewer for the constructive comments.

Given that the discussion period is ending in 1 day, we will appreciate if the reviewer can advise whether there is any remaining concern, and we are more than happy to address them.

We sincerely appreciate the reviewer for recognizing the novelty and the empirical effectiveness of our proposed framework. We have carefully prepared responses to the concerns of the reviewer. We have also seriously taken the suggestions and made revisions to the paper. The revised parts are highlighted in blue.

Q1. This paper describes the avoidance of memory explosion as an issue, and specifically argues for a reduction from $O(nd^L)$ to O(n). The reduction in memory order is almost trivial, and is also discussed in a simplified manner in the text. On the other hand, no experiments with actual memory perspectives have been conducted. Memory reduction may have contributed to the improved performance shown in the experiment, but not directly. For example, a comparison of the possible scale of response between ER-GNNs and PDGNNs should be mentioned in a clear manner.

A1. Thanks for this nice concern on the memory reduction. Originally, the discussion on the memory reduction was included in Appendix B.2. We have now added a new section (Section 4.5) in the paper to discuss this issue. In Section 4.5, the actual memory usage (the number of float32 values) of different memory based methods after learning each entire dataset, including ER-GNN mentioned by the reviewer, are provided in Table 4 ,page 9. As a reference, the memory consumption of storing full computation ego-subgraph is also calculated. The table is also provided below for convenience.

Q2. I would like to know the impact of TEM sampler settings, I understand that coverage maximization sampling is recommended, but are there other sampling methods with catastrophic results? Does the sample size of coverage maximization sampling make a critical difference? If possible, experimental results would be useful for actual use.

A2. Thanks for this nice question on the sampling strategy, which is an important contribution in our work. We have actually provided experimental results (Table 1, page 7) regarding this issue and discussed about it (Section 4.3), as explained below. The table is also provided below for convenience

In this table, we show the performance of coverage maximization as well as two other samplers, uniform sampling and Mean of Feature (MoF). Results with different memory budget (sample size) are also shown in Table 1. According to the result, PDGNNs-TEM can avoid catastrophic forgetting with different samplers. When the budget is tight (sample size is small), the advantage of Coverage Maximization sampling is more significant.

Above all, we summarize our answer to the two questions as:

First, our key design to avoid catastrophic forgetting is the full preservation of the topological information in TEM. Therefore, PDGNNs-TEM can perform well with different TEM samplers.

Second, the sample size does make a critical difference, just like any memory replay based method in continual learning. The more data is preserved from the previous tasks, the less forgetting is suffered from.

Q3. Minor: Misformatted citations. Some examples: Section 2.2: misformatted citation Kipf and Welling (2016) Section 3.2: “prevent forgetting LopezPaz and Ranzato (2017); Rebuffi et al. (2017).” “Take the Reddit dataset (Hamilton et al., 2017) as a concrete example, its average degree is 492, and even with a 2 layer MPNN, the buffer size will be easily intractable.” This sentence was repeated in the intro.

A3. Thanks for pointing out these issues. We have carefully corrected every issue in the revised version. Specifically, the misformatted citations are updated into the correct format, and the last paragraph of Section 3.2 containing a duplicate sentence from Introduction is re-written and highlighted in blue.

Q4. Please clarify my concerns regarding theory. In particular, the existence of a non-trivial topology-aware embedding as in Definition 1, as I think the definition refers to the existence of a very strong function.

A3. Thanks for further clarifying this question. As explained in A2.(a), the reviewer is correct that it is hard to guarantee the existence of a non-trivial topology aware embedding universally for different GNNs, which is not implied by our Definition 1. Instead, Definition 1 requires the optimization equivalence to exist with respect to each specific GNN that is capable of generating TEs. We have carefully rewritten Definition 1 and highlighted it in blue (page 4).

We hope our explanations can help in the clarification of the concerns. We are also happy to address any remaining concerns.

Q2. Some issues with theory: (a) I believe Definition 1 is both too strong and not rigorous enough, “if optimizing $\mathbf{\theta}$ with $\mathcal{G}^{sub}_v$ or $\mathbf{e}_v$ are equivalent,” does this mean the same stationary points are achieved? Additionally, since $\mathbf{e}_v$ is an embedding, this would be a highly unusual possibility as any type of compression leads to different solution spaces. (b) Theorem 1: “It is equivalent to training PDGNNs with each node w in $\mathcal{G}^{sub}_v$ with $\mathcal{G}^{sub}_v$ being a pseudo computation ego-subgraph and $\mathbf{y}_v$ being a pseudo label,” in my opinion, this is a near circular outcome. You have defined the embedding as $\mathbf{e}_v$ as being a representation of $\mathcal{G}^{sub}_v$ such that optimization is equivalent, which is strong enough to allow all these results to naturally fall out.

A2.(a) Thanks for these nice concerns on the theory.

First of all, we agree with the reviewer that 'any type of compression leads to different solution spaces'. For example, in our PDGNNs framework, different choices of $f_{topo}$ would result in different embedding spaces for the TEs. However, as stated in Definition 1, the optimization equivalence is based on a 'given GNN parameterized with $\mathbf{\theta}$'. In other words, the TEs are not generated once and universally fit all GNNs. Instead, different qualified (capable of generating TEs) GNNs generate TEs in different embedding spaces, and the equivalence is only required within the specified GNN. In our PDGNNs framework, the function $f_{topo}$ is formulated with different choices in the experiments (Section 3.4). Different choices of $f_{topo}$ lead to different embedding spaces of TEs, and the optimization equivalence is only required after $f_{topo}$ is specified and the embedding space is fixed.

After clarification on the above issue, we can address the two concerns in Q2.(a) from the reviewer.

1. As for 'since $\mathbf{e}_v$ is an embedding, this would be a highly unusual possibility as any type of compression leads to different solution spaces.' Yes, the embeddings (TEs) are model dependent, and each qualified GNN generates their own TEs. The TEs derived within one specific GNN may not full-fill the 'optimization equivalence' requirement of Definition 1 for another GNN.

2. As for 'if optimizing $\mathbf{\theta}$ with $\mathcal{G}^{sub}_v$ or $\mathbf{e}_v$ are equivalent, does this mean the same stationary points are achieved?' Yes, equivalence in terms of optimization requires achieving the same stationary points. For example, in our PDGNNs framework, we provided proof in Appendix A.1 to show that optimizing with TEs and computation ego-subgraphs results in same gradient on the trainable parameters $\mathbf{\theta}$ with respect to the loss function, at each optimization step. Therefore, after optimization, the same stationary points can be achieved.

Based on the reviewer's constructive comments, we have carefully rewritten Definition 1 to strengthen that the optimization equivalence is only required with respect to each specified GNN structure, which is highlighted in blue in the updated version (page 4).

A2.(b) Thanks for this nice concern. The reviewer's observation (Definition 1 is the foundation of Theorem 1) is correct. However, Definition 1 alone is insufficient for developing Theorem 1 for the following reasons.

1. Definition 1 describes a desired surrogate (TE) of the computation ego-subgraph. But it does not guarantee the existence of such a surrogate or specify the model structure for deriving TEs. Differently, Theorem 1 is built upon the constructed PDGNNs framework, with detailed analysis on the pseudo-training effect within this specific framework. For example, Theorem 1 describes the pseudo-training in both situations where $\mathrm{f}_{out}$ is linear or not, as well as how exactly the contribution of the nodes are re-scaled in both situations.

2. The optimization equivalence in Definition 1 and the pseudo-training in Theorem 1 are actually different. The optimization equivalence in Definition 1 is between the TE and the computation ego-subgraph of a specific node $v$, instead of every node $w$ within the subgraph, while Theorem 1 describes the relationship between training with $v$ and its neighbors in its computation ego-subgraph $\mathcal{G}_v^{sub}$.

3. Moreover, Theorem 1 leads to our novel coverage maximization sampling technique, which cannot be directly derived from Definition 1.

We sincerely appreciate the reviewer for recognizing that our proposed framework effectively addresses the important memory explosion issue, with strong empirical results on large datasets and theoretical merits. The concerns and questions are very constructive to further improve our work, and we have carefully prepared responses below. We have also seriously made necessary revisions to the paper, which are highlighted in blue.

Q1. The authors do not suggest a novel $f_{topo}$ (the embedding function) which limits the novelty of the work. Essentially, the authors are proposing to reduce the memory complexity of ego-subgraph topological information using known techniques.

A1. Thanks for this nice concern, and we are happy to have the opportunity to further clarify it.

1. A new framework: as the reviewer noticed, $f_{topo}$ is one component of our proposed PDGNNs framework and it is formulated based on existing techniques. The entire framework, which consists of both PDGNNs and TEM, is the first in the field that can fully leverage the topological information with highly efficiently memory usage. As recognized by the reviewer and other reviewers, this new framework can significantly boost the performance on large datasets.

2. Innovative theoretical analysis (Section 3.5): In the field of continual learning on expanding graphs, we provide the first attempt to theoretically analyze the relationship between the sampled and the remaining nodes.

3. A novel sampling technique with theoretical foundations (Section 3.6): Based on the theoretical analysis, we developed the Coverage Maximization Sampling, which is also empirically justified to be effective especially when the memory budget is tight.

All of these have not been accomplished by existing works and are important issues for continual learning on expanding graphs.