Towards Continuous Reuse of Graph Models via Holistic Memory Diversification

W1: The title presented on the website is not the same as the one in the paper

We are sorry for the clerical error. We initially considered multiple titles and inadvertently failed to replace the title in the latest version of the manuscript. We will ensure this is corrected.

W2: The citation style is not used appropriately. Most of the citations should be in parenthesis using \citep{}.

Thank you for pointing out the inconsistencies in our citation style. We will revise all citations to ensure they are in parentheses using \citep{} as required by the citation guidelines.

W3: The authors are encouraged to include the time consumption of different memory selection strategies.

In our paper, we compared our proposed heuristic diversified memory selection methods with three other memory selection strategies--K-center sampling, Coverage Maximization (CM), and Mean of Feature (MF). Here we analyze the time complexity to assess the efficiency of different methods.

For our method, for each batch, there are $b$ sampling steps where $b$ is the size of the buffers. Each sampling can be done in $O((K+n)|\mathcal{C}^t_{i}|)$, by determining distances and making comparisons, where $K+n$ is the total number of classes up to $t$-th task and $\mathcal{C}^t_i$ is the training set corresponding to the $i$-th class. Thus, the overall complexity of selecting each buffer is $O(b(K+n)*|\mathcal{C}^t_{i}|)$.

For K-center sampling, the time complexity of selecting $b$ clustering centers for each class is $O(b*|\mathcal{C}^t_{i}|)$. Thus, the overall complexity is also $O(bK*|\mathcal{C}^t_{i}|)$.

For Coverage Maximization and Mean of Feature, they did not report the time complexity in their own paper, we further analyze them based on their papers and codes. Coverage Maximization needs to calculate and sort the distance of nodes in each class to other classes, which costs at least $O(K(K-1)|\mathcal{C}^t_{i}|^2)$ where $|\mathcal{C}^t_{i}|$ is the mean of node number in each class, which could much more complex. Mean of Feature calculates the prototypes of each class and selects nodes are closest to the prototype, the time complexity is $O(K|\mathcal{C}^t_{i}| + K|\mathcal{C}^t_{i}|log(|\mathcal{C}^t_{i}|))$.

Considering the node number in each class is much more than the buffer size and class number, it is evident that our heuristic diversified memory selection method, while being slightly more complex compared to K-center sampling, remains more efficient than the rest. From the comparison results in Table 4 in Section A.5.2, our method achieves much better results, offering a reasonable trade-off between computational efficiency and effective diversity enhancement of the memory buffer.

W4: The statements in lines 178-181 are not clear. Please revise it to make it clearer.

Sorry if we did not make it clear.

Here's a more comprehensive version that better explains the statements in lines 178-181:

The covariance matrices $\Sigma_p$ and $\Sigma_q$ are key indicators of the diversity within the distributions of $p(G_{<t})$ and $q(B_{<t})$, respectively. Typically, the replay buffer $B_{<t}$, being a sampled subset of $G_{<t}$, exhibits less diversity than the entire graph dataset from previous tasks, meaning $\Sigma_q$ is often smaller than $\Sigma_p$. Assuming that the sampling strategy used to populate $B_{<t}$ is unbiased with respect to the mean of the distributions, enhancing the diversity of $B_{<t}$ so that it better represents the full dataset, $\Sigma_q$ will approach $\Sigma_p$. This leads to a smaller Wasserstein distance because the distributions are more similarly "shaped.":

$W_2^2(\mathcal{N}(\mu_p, \Sigma_p), \mathcal{N}(\mu_q, \Sigma_q)) = \| \mu_p - \mu_q \|^2 + \operatorname{Tr}(\Sigma_p + \Sigma_q - 2(\Sigma_p^{1/2} \Sigma_q \Sigma_p^{1/2})^{1/2}).$

According to the bound in Theorem 1:

$\left| E_{v \sim p(G_{<t})}[\mathcal{L}(\theta, v)] -E_{v \sim q(B_{<t})}[\mathcal{L}(\theta, v)] \right| \leq \beta \cdot W(p(G_{<t}), q(B_{<t}))$

A decrease in the Wasserstein distance leads to a smaller discrepancy between the expected loss under the true distribution $p(G_{<t})$ and the distribution represented by the replay buffer $q(B_{<t})$. Consequently, optimizing the model using the replay buffer becomes a closer approximation to optimizing using the entire dataset from previous tasks, thereby improving the effectiveness of incremental learning.

We will revise the statements to be more clear in the manuscript.

W1: The theoretical analysis is not rigorous enough. Theorem 1 reveals that smaller distance between the memory data distribution and the full data distribution indicates that the loss computed based on memory can more closely mirrors the expected over the full previous data. This is a straightforward and reasonable conclusion...

Thank you for your constructive feedback.

The assumption that the data follow Gaussian distributions is a common simplification in theoretical analyses. This assumption is justified by the Central Limit Theorem[1] under certain conditions.

In the context of Theorem 1, 'diversity' refers specifically to the spread of data as captured by covariance matrices. This is a measure of how broadly the data are distributed around the mean, which is directly relevant to how well the buffer represents the variability seen in the full data. The mention that buffered data is "typically less diverse" is indeed subject to sampling variability, particularly when the sample size is small. Here is a simple prove:

In the univariate case, the sample variance $\sigma_q^2$ is related to the chi-squared distribution[2] as follows:

$(n-1)\frac{\sigma_q^2}{{\sigma_p}^2}\sim \chi^2_{n-1}$

where $\sigma_p$ is the ture variance and $n$ is the sample number. The mean of the chi-squared distribution is $n-1$, and its right-skewed nature implies that:

$P(\chi^2_{n-1} < n-1) > 0.5$, i.e.,

$P(\sigma_q^2 < \sigma_p^2) = P\left( (n-1)\frac{\sigma_q^2}{\sigma_p^2} < n-1 \right) = P(\chi^2_{n-1} < n-1) > 0.5$

This indicates that there is a greater than 50% chance that the sample variance underestimates the population variance. In higher dimensions, the sample covariance matrix (related to the Wishart distribution) display properties analogous to the chi-squared distribution used in the unidimensional case. This statistical property extends to the sample covariance matrix in higher dimensions, suggesting that the eigenvalues of $\Sigma_q$ are likely to be smaller than those of $\Sigma_p$. This supports our initial claim--"typically less diverse" from a high-dimensional perspective.

[1] https://en.wikipedia.org/wiki/Central_limit_theorem

[2] https://statproofbook.github.io/P/norm-chi2.html

W2: The implemented diversity maximization strategy is inconsistent with the theoretical motivation, as mentioned in the first weakness point.

Thank you for pointing out this.

The theoretical foundation of our approach was intended to emphasize the importance of a diverse memory buffer in reducing the gap between the empirical loss calculated over the buffer and the expected loss over the entire dataset. This is underpinned by the principle that a diverse buffer more accurately approximates the full data distribution, thereby improving the learning model's generalization capabilities.

The apparent inconsistency between the theoretical use of covariance to measure diversity and the practical use of average distance among data points in the experiments arises from the need to adapt theoretical concepts for empirical validation. While covariance provides a measure of diversity that is theoretically sound, average distances serves as an effective and correlative approximation, which offer a more intuitive and directly observable metric that can be used in practical scenarios.

Q1: Please explain more on the probability distance used in Section 3.1, e.g. the specific formulation.

We are sorry we did not make it clear.

In equation 2, $A(v, B_i)$ represents the distance measure between a node $v$ and a set of nodes $B_i$ in the buffer. The term 'L2 norm distance on probabilities' refers to the Euclidean distance calculated between the probability distributions of node features or embeddings. These probabilities are derived from the output of our model. Specifically, they represent the probability distribution of each node belonging to different classes, as obtained from the softmax output layer of the classifier.

To clarify, for a given node $v$ and the buffer $B_i$, the L2 norm distance is calculated by $A(v, B_i) = \min_{u \in B_i} \left( \sum_{j=1}^{K} (p^v_j - p^u_j)^2 \right)$, where $p^v$ and $p^u$ are the probability distribution of node $v$ and $u$, $p^v_j$ and $p^u_j$ are their $j$-th item. $K$ is the current class number.

Thanks for the detailed responses from the authors. I guess that additional explanation on the theoretical analysis makes the paper more convincing. I would recommend that the authors to include the theoretical justification of 'sample data has >50% probability to underestimate the covariance' in the paper. But I would also like to say that >50% is actually not convincing enough. Because if it is only very slightly above 50% in practice, then it is no difference to 50%. Since this is the major concern, I would like to increase the rating to 6.

W3: Lack of comprehensive datasets. What about the performance of the proposed model on Citeseer, Pubmed, and PPI? How about Collab, IMDB, Proteins, and NCI1?

In the current study, we use the four datasets, CoraFull, OGB-Arxiv, Reddit, and OGB-Products, based on their common usage in the literature, which allows for direct comparison with state-of-the-art methods and ensures that our findings are relevant and comparable. Notably, most of the papers mentioned in the last question use these four datasets.

Thank you for your suggestion and we will certainly consider including more datasets in subsequent studies based on your valuable feedback.

W4:Lack of hyperparameter sensitivity study. The method introduces several hyperparameters such as λ1, λ2, and λ3 for balancing the loss. A discussion on their impact and guidelines for tuning these hyperparameters would be valuable. More in-depth analyses about balancing these losses to understand the contribution and reasons for developing them are encouraged.

We have conducted hyperparameter sensitivity experiments on several critical hyperparameters. For example, the effect of buffer size is analyzed in Section A.5.3. For the loss weights, we report the setting in our experiments in A.4.3. To tune these parameters, we employed a grid search strategy over a predefined range of values. The findings suggest that $\lambda_2$ and $\lambda_3$ are relatively robust across a wide range of settings, while $\lambda_1$ for the memory replay needs to be set as about 20 times higher weight than other weights. We analyze that there are two key reasons--Minimizing Forgetting: Since the model has already been trained on data in the buffers, the loss values for these classes are relatively smaller than for new classes. This discrepancy can lead the model to focus excessively on new classes, thereby exacerbating the forgetting problem. Addressing Imbalance Issues: The number of nodes in the buffers is significantly less than that of the new data, presenting an imbalance challenge. Increasing the weight helps address this by giving more importance to the smaller, buffered classes, which is a common approach in tackling imbalanced classification problems.

W1: Lack of novelty. This paper largely builds on existing concepts of memory replay and buffer selection strategies that are already well-established in incremental learning and continual learning literature. While the paper proposes a diversified memory selection and generative replay approach, the techniques, such as adversarial learning and variational embedding, have been previously applied in other contexts. The paper simply combines different losses to facilitate learning.

We appreciate your feedback and the opportunity to further explain the novel contributions of our work. Our paper introduces the Holistic Diversified Memory Selection and Generation framework, specifically designed for incremental learning on growing graphs. This framework innovatively both proposed new algorithms and integrates several advanced techniques, tailored to overcome the unique challenges of graph-based continual learning. Below, we detail the distinctive aspects of each component:

1. Greedy Algorithm for Diversified Memory Sampling with Theoretical Grounding:

   Our greedy algorithm for memory sampling is specifically designed to handle the complexity of graph structures, which is distinct from previous applications in general datasets. This algorithm considers both intra-class and inter-class diversities, which are critical in graph-based models due to their relational nature. We provide a rigorous theoretical analysis to support the effectiveness of our approach, proving that our diversified sampling strategy minimizes the loss in representational fidelity—a novel contribution that extends beyond typical greedy approaches in non-graph data.

2. Adversarial Variational Generation-based Memory Replay:

   The use of adversarial variational techniques for memory replay in graphs is an innovative approach within the domain of graph incremental learning. This method not only aids in better generalization but also enhances the model’s ability to synthesize new graphs that maintain the integrity of past learnings—addressing the catastrophic forgetting problem more robustly than existing methods. This differs from traditional graph memory replay methods because it can introduce more diversified memories via variational generation.

3. Holistic Diversified Memory Selection and Generation Framework:

   The holistic nature of our framework, which integrates both the diversified memory selection through a greedy algorithm and the generative replay via adversarial variational techniques, provides a unique and comprehensive framework that is specifically tailored for graph-based data. This is a key innovation over existing methods that often treat memory selection and replay as disjointed components.

In conclusion, the proposed framework to the domain of incremental graph learning, coupled with theoretical underpinnings and empirical validations, contributes novel insights and practical method to the field.

W2: Lack of baselines. The following papers should be discussed and compared for experiments: Towards robust graph incremental learning on evolving graphs. ICML 2023 Replay-and-Forget-Free Graph Class-Incremental Learning: A Task Profiling and Prompting Approach. NeurIPS 2024 On the Limitation and Experience Replay for GNNs in Continual Learning. CoLLAs 2024 ... Accordingly, it is encouraged that the authors discuss the difference between their proposed model and these baselines.

Thank you for your comments and for pointing out relevant literature. We have checked the mentioned papers one by one carefully.

The first three papers focus on task incremental learning, where the node's task affiliation is known. This is different from our setting—class-incremental learning—which does not presuppose knowledge of node class assignments in different tasks, presenting a more complex challenge.

The last three papers were all published late this year, aligning with the same period as our paper. The fourth paper proposes parameter decoupled graph neural networks with topology-aware embedding memory for the graph incremental learning problem. The last two papers both use different graph condensation technology to preserve memory graphs. But still, they do not address memory diversification. Our method not only preserves but also enhances memory graphs through a learned generative model, fostering richer and more adaptable memory representations. Furthermore, it is worth mentioning that our method employs a greedy algorithm for memory selection and an additional variational layer for memory selection. Compared to these papers, our require much fewer parameters.

In response to these observations, we will include citations and a detailed discussion of these papers in the revised version of our manuscript.

W5: With the introduction of complex mechanisms for memory selection and replay, how do the time and computational costs of the proposed method compare to other baseline approaches in the experiments?

The main part of computational costs is the memory selection strategy, and the memory replay stage involves similar quantities of propagation costs across all baselines.

We analyze the time complexity of our method in Line 240-244 in Section 3.1, which demonstrates that our method is efficient and comparable with other straightforward strategies such as K-center, Covering Machines (CM), and Matrix Factorization (MF). And our method consistently excels in performance.

For a more detailed time complexity analysis for these memory selection methods, please refer to the response to Review T2ad in W3. where we have further detailed time complexity.

W6: Why have a direct assumption that "Let the loss function L(θ, x) be β-Lipschitz continuous in respect to the input x" in Theorem 1. ? And how can we evaluate whether the selected nodes in buffers are with diversity?

The assumption that the loss function $L(\theta,x)$ is β-Lipschitz continuous with respect to the input $x$ is a standard theoretical simplification that ensures the stability and smoothness of the loss function. It is widely used as an established assumption for graph neural networks[1].

We evaluate the diversity of the selected nodes using both intra-class and inter-class diversity metrics. Intra-class diversity ensures that the nodes within the same class in the buffer are varied, covering different aspects or features of the class. Inter-class diversity, on the other hand, ensures that nodes from different classes are distinct enough to reinforce class boundaries effectively. Specific metrics might include variance measures within classes for intra-class diversity and distance metrics like Euclidean or cosine distances for inter-class diversity. In this paper, we use the Euclidean distance.

[1] Levie, Ron. "A graphon-signal analysis of graph neural networks." Advances in Neural Information Processing Systems 36 2024.

W1: For the buffer node selection part, are the buffer nodes only node-set or graph-structural data, if graph data, how to connect these nodes? and if node-set, how to directly feed it into GNN in Figure 2?

Thank you for the question. As mentioned in Line 340-341, we utilize a mini-batch GNN propagation approach. For each node, whether from the buffer or associated with new tasks, we extract its multi-hop neighborhood according to the original graph structure. Nodes are fed into the GNN along with their extracted neighborhood subgraphs. This aligns with practices in existing graph continual learning research.

W2: How many nodes are typically selected in the buffer for each class? How experimental results would change along with the varying number of nodes in buffers?

Thank you for your inquiry. We report the number of nodes seleted for each datasets in Section A.4.3. In our experiments, we have standardized the buffer size to ensure consistency across evaluations and comparability with baseline methods. Specifically, we use a buffer size of 60 nodes for the CoraFull dataset and 400 nodes for the other datasets. This also aligns with the buffer sizes typically employed in baselines.

To explore how the number of nodes in the buffer affects our model's performance, we conducted additional experiments with varying buffer sizes. The results are presented in Figure 7 in Section A.5.3 of our manuscript. Our findings indicate that increasing the buffer size tends to improve the model’s ability to retain knowledge, particularly for more complex datasets, but up to a point where the returns diminish. This helps in understanding the trade-offs involved in buffer size selection concerning memory constraints and performance optimization.

W3: In the ablation study, the effectiveness of the buffer node selection is not verified. For instance, how to illustrate the effectiveness of the proposed heuristic greedy method?

We have conducted experiments to analyze the effectiveness of the proposed heuristic greedy method for buffer node selection. The results are in Table 4 in Section A.5.2, we compare our selection method with other widely used memory selection methods, the results show that our sampling method consistently excels in performance. This can be attributed to exploring both the intra-class and inter-class diversity of nodes within our method that efficiently captures the required diversity among nodes, ensuring a holistic representation of the dataset.

W4: Why the variational layer in the memory replays could broaden knowledge from the buffer? Does that mean, it generates something new from the original Z? Additionally, the minimization term in equation 7 is difficult to interpret—could you provide a more detailed explanation or expanded expressions for this term?

Thank you for your insightful questions. The variational layer in our model is designed to enhance the diversity and generalization capabilities of the buffer memory by generating new node embeddings from the existing data (original $Z$). This is achieved through a process known as variational inference, where the layer learns to approximate the probability distribution of the node embeddings based on the input data. Yes, the variational layer effectively generates new samples from the learned distribution, which are similar but not identical to the original data $Z$. These synthesized embeddings are derived by sampling from a distribution parameterized by the means $Z^{\mu}$ and variances $Z^{\sigma}$ produced by the variational layer. This capability allows the model to interpolate and extrapolate within the space of known data, thereby enhancing the model's ability to handle new or slightly different data scenarios without needing explicit examples of such variations.

Equation 7 employs a min-max optimization strategy within an adversarial framework. The term is expressed as:

$\min_{\theta,\phi_v}\max_{\phi_d}E_{z_i \sim Z}E_{q_{\phi_v}(\hat{z}_i|z)} [l_D(z_i,\hat{z}_i)]$

which can also be written as a bilevel optimization expression:

$\min_{\theta, \phi_v} \quad E_{z_i \sim Z}E_{q_{\phi_v}(\hat{z}_i|z)} [l_D(z_i, \hat{z}_i, \phi_d^* )]$

subject to

$\phi_d^* = \arg\max_{\phi_d} \quad E_{z_i \sim Z}E_{q_{\phi_v}(\hat{z}_i|z)} [l_D(z_i, \hat{z}_i)]$

Here, $\theta$ and $\phi_v$ represent the parameters of the main network and the variational network, respectively, and $\phi_d$ represents the parameters of a discriminator network. The $q_{\phi_v}(\hat{z}_i|z)$ is the variational distribution to sample $\hat{z}_i$. The discriminator $D$ attempts to distinguish between original and generated node embeddings, whereas the generator (part of the variational layer) tries to fool the discriminator by producing embeddings that are indistinguishable from actual data. The loss $l_D$ is a binary cross-entropy loss, measuring how well the discriminator performs and how effectively the generator deceives it.