Dynamic Mixture-of-Experts for Incremental Graph Learning

Thank you for your very knowledgeable and thoughtful comments, these greatly help us in making our paper better, and we would like to discuss some of your concerns here.

The identified problem and the proposed method are not novel.

The continual learning problem in the graph is unique compared to that in the CV/NLP domain. Specifically, the model not only needs to learn from new data blocks and keep the old knowledge but also needs to adapt the representation learned for old blocks according to the new graph contexts, as the new data block may change the topology of nodes from the old data blocks.

There are two challenges in graph continual learning: 1) Reducing forgetting: The model needs to remember old data blocks, which is a common challenge for other continual learning domains, like CV and NLP. 2) Adapting old nodes to new graph context: unlike CV/NLP, the nodes in old data blocks change as new data arrives, a model should account for this.

To solve the first challenge, we dynamically add MoE modules to learn individual data blocks to reduce forgetting. The trained modules are not modified afterward, preserving as much learned information as possible. Consider an experience-replay variant that finetune the model with the memory node set from previous data blocks, it can potentially modify all parameters of the model causing significant forgetting, whereas we only adjust the gating vectors, meaning that we can replicate the output when the gating values are correct. Lastly, to ensure the gating value correctness, we propose the block-guided loss, which is the directly supervised signal to produce correct gating values.

The second challenge happens because a node from data block 1 can later be connected to nodes from future data blocks. Our design interleaves the MoE modules into GNN layers, so the models learn to calibrate the input to the next layer via message-passing, without changing the experts' parameters. Intuitively, because of the distribution shift, the previously trained experts no longer work. Training like ER-GNN would significantly change the expert’s performance while heavily overfitted towards the memory nodes, whereas we only update the gating vectors to account for the distribution shift in the representative memory nodes and all information previously about the entire data block is not lost.

While MoE in CV/NLP are indeed used for continual learning, they do not tackle the second challenge. For example, to perform class-incremental learning, [1] needs to train an auto-selector which depends on a specific data block, and does not evolve over time. Consequently, if we adapt this method to the graph domain, an auto-selector trained for data block one will fail quickly when new data blocks arrive, because the auto-selector no longer works for data block one as the new connection changes the distribution of the nodes in data block one.

What happens to the parameter complexity (overall model size) when the data stream is large

The overall complexity indeed increases linearly as the length of the data stream increases, which is why we implemented the sparse variant to ensure the activated parameters and inference time remains constant as the length increases.

How effective is this approach for parameter/information sharing among tasks (otherwise, why not train a separate network for each task)

An important target in our paper is a class-incremental setting, where new data blocks introduce new classes and the tasks also require the model to distinguish these new classes from the old ones. A separate model cannot perform this task, and hence an integrated model is essential. Meanwhile, to study the effectiveness of information sharing we additionally conduct task-incremental learning.

We compare DyMoE to the separate baseline where we train separate models for each task. We can see that without support from a larger dataset (previous data blocks), the separate model struggles to achieve optimal performance.

The theorem statement tells us that it is possible for the proposed method to achieve a smaller...

As we discussed in your previous concern, the loss is just the classification loss (cross-entropy) between the predicted value and the true label, as can be seen in equation (20), we will state this more clearly in the theorem. So here the loss is independent of the model and directly reflects the accuracy (if a model has low cross-entropy loss, it assigns high probability to correct classes, and hence higher accuracy). Optimizing the cross-entropy loss will optimize the performance. The theorem proves that, in arbitrary circumstances, DyMoE can achieve the same classification loss, which is a direct indicator of the classification accuracy, as PI. And, in the case of a Mixture of Gaussian, DyMoE can achieve lower classification loss, leading to higher accuracy.

Outdated baselines.

We compare DyMoE with more recent baselines, including RCL-CN[3] and SSRM[2] in general response. DyMoE is still strong compared to these baselines.

Inconsistent performance.

The lower performance is because we follow a different split than the CGLB[4]. We follow the split in the PI-GNN[5] paper.

[1] "Boosting continual learning of vision-language models via mixture-of-experts adapters." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.

[2] "Towards robust graph incremental learning on evolving graphs." International Conference on Machine Learning. PMLR, 2023.

[3] ''Reinforced continual learning for graphs,'' in Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022, pp. 1666–1674.

[4] "Cglb: Benchmark tasks for continual graph learning." Advances in Neural Information Processing Systems 35 (2022): 13006-13021.

[5] "Continual learning on dynamic graphs via parameter isolation." Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2023.

The effectiveness of the gating mechanism.

Our framework is more than the MoE architecture, it contains a dynamically added MoE module with a gating/router mechanism, a collected memory dataset containing subsets of previously trained data, and block-guided loss to ensure old data in the memory set is still routed correctly to their corresponding experts. Specifically, we keep a small memory set of previous data blocks, when new data arrives, adding new knowledge and changing old patterns, the memory node-set is used as a proxy of the entire old data block. The detailed information of the old data block is stored within each frozen expert ensuring the knowledge is not lost, whereas we adapt the gating process through training with the memory node set to account for the overall distribution shift. In terms of unlearnability, could you be a bit more specific about the conclusion? In [2], the authors developed a catastrophic forgetting upper bound consisting of the training loss, an intra-block structural shift loss, and an inter-block structural shift loss for a fixed GNN. This bound only correlates to the performance of a fixed GNN under structural shift and does not suggest unlearnable results. To the best of my understanding, their proposed method shows that by properly training the model, they can minimize such a loss to improve continual learning performance. Intuitively, consider two data blocks, whose structures follow completely different distributions and are isolated graph components, which results in high inter-block structural shift. In DyMoE, the first expert is trained on one block, and its gating vector is set as the mean of the inputs. The input to the MoE module will be very different for data in the second block because of the structural shift, and the second expert learns to capture that with a gating vector very different from the first gating vectors. Thus during inference, the input that is closer to the first gating vector will have high gating values, and correctly route the input.

First, it is not clear what $\mathcal{L}(Dy)$ and $\mathcal{L}(PI)$ are exactly. Assuming the loss function is the one given by (10), the loss function would have a dependency on the $\beta$ which is not reflected in the theorem statement.

For the theoretical analysis, we follow a clean setting, where the loss is just the cross entropy, which directly reflects the prediction accuracy. The block-guided loss $\mathcal{L}_{BL}$ is omitted, because it is an auxiliary loss for regularization not directly related to the prediction accuracy, and it would be pointless to include this loss when we compare PI with our method.

There are many cases, where the theoretical result does not add any value. For example...

The proof has two parts, and the first part is easy to see, DyMoE is always at least as good as PI. To find such a parametrization, the model can simply set all gating vectors to the same one. The second part is to show that under certain conditions (Gaussian), DyMoE can achieve better loss, which shows that DyMoE is a stronger model. Note that in training, the block-guided loss will enforce inputs to be close to their gating vectors, which encourages the gating vectors to stay at the mean of the inputs.

In terms of separable data, consider both PI and DyMoE, models can indeed achieve zero loss in a fully supervised setting, but in the continual learning setting, when the model is presented with only the second data block, the incremental model/expert will optimize only for the second data-block, leading to increased loss for data from the first data block, because the incremental model will only output large logits for classes in the second data block. The proof in the paper shows that for any loss achieved by the PI model, DyMoE can achieve a lower one. To achieve such a lower loss, we only need the gating vector to be close to the distribution mean of their corresponding data block, which is achieved by the block-guided loss. We will add more clarity to both the theorem statement and intuition.

Your comments are invaluable to us, and we will use them as important source to improve our work. Here, we would like to discuss some of your concerns.

The use of symbols is inconsistent

The $n$ and $m$ are input and output dimensions, we’ve clarified this in the updated pdf.

You are correct that $y$ is $h$, thanks for pointing this out, we’ve fixed it in the pdf.

Here, the triangle and the vertical bar represent data blocks, not nodes. We use color and shapes to distinguish different data blocks.

More baselines.

These are definitely related works and we will include them as important reference points in our revision. Meanwhile, we compared DyMoE to RCL-CN and SSRM which have open-sourced access in the general response.

In line 255, ''Figure 6 shows that direct training will not result in specialized experts'' seems confusing, can you explain it more clearly?

This section motivates the design of block-guided loss. In Figure 6, we show two results of two models, the left one shows the results of a DyMoE model trained without block-guided loss, and the right one is trained with block-guided loss. In this experiment, after training, we isolate the experts by only activating one expert during inference to obtain their individual performance on data blocks. Every line in Figure 6 represents an expert’s isolated performance. We can see that if we train the MoE without block-guided loss, the experts are not specialized to have a good performance on their corresponding data blocks.

Randomization process.

Here we follow the Sparse MoE [1]. Specifically, during training, the gating value is $g = **x**\cdot v + StandardNormal()\ast softplus(**x**\cdot v_n)$, where $v$ is the gating vector and $v_n$ is a trainable noise vector determining the level of noise.

[1] Shazeer, Noam, et al. "Outrageously large neural networks: The sparsely-gated mixture-of-experts layer." arXiv preprint arXiv:1701.06538 (2017).

Thank you for your reply. For weaknesses 3 and 4, I still have two questions.

Regarding Figure 6, I noticed that in the experimental section, the authors use it to "evaluate whether their model and training procedure result in specialized experts as designed." However, the author mentioned Figure 6 "motivates the design of block-guided loss". This creates a circular reasoning issue, as the validation of the method is being used as its motivation.

Regarding the randomization process, Sparse MoE states that "the noise term helps with load balancing," while the authors claim that "all experts have similar selection opportunities." However, in the subsequent experiments, k=3. I am curious how this random noise ensures the inclusion of the last expert, as it seems that this randomness does not guarantee the last expert will be part of the top-k selection.

We greatly appreciate your positive comments and critical feedback on our work, we address your concerns as follows.

In real-world applications, how do the dynamic changes in graph structures and data blocks affect the model's performance? Have you considered the impact of data noise and outliers on the results?

That’s a great question. It is indeed more challenging when the data are noisy and dynamic. We can compare the performance of the Pretrain baseline (we only train the model using the first data block and run inference on the following data blocks with this model) with other existing baselines, and we can see a large performance gap because the distribution of the data significantly shifted. More interestingly, we observe that when the graph changes more rapidly, such as in arxiv where the volume of publications significantly increases over the past few decades, the gap is large, and the gap is smaller when the graph is more consistent, such as in Elliptic where the data only span roughly 2 years. To cope with this challenge, we propose block-guided loss to stabilize training. For example, when an outlier falls in the distribution boundary of two data blocks, it would be difficult for the MoE model alone to determine the most relevant expert. However, in the case of continual learning, every data point is accompanied by a block index, and hence we can use that information to provide direct supervision to reduce the risk of assigning wrong experts to noisy/outlier data points.

The MoE structure increases the number of parameters in the model, thereby enhancing its capability. In contrast, the parameter count of the baseline model is not specifically mentioned. Does this represent an unfair comparison?

It is indeed important to evaluate the models under the same parameter budget, and we present results in general response and show that the fixed-sized parameters model experience performance degradation when they are given the same parameter budget as DyMoE, mostly due to the overfitting.

This paper mentions "with minimal computation increase," but it seems insufficient experimental or theoretical evidence is provided. Could there be a comparison of throughput?

Compared to the complexity/running time lower bound finetune on the cora-full dataset, we observe that the training time increases by 7%, whereas we observe a 109% performance increase. Compared to the ER method, the training time increase is 4%, whereas the performance increase is 14.4%. This shows that DyMoE achieves higher performance in an efficient way.

From a theoretical standpoint, the complexity of Training DyMoE is $O(nkT)$, where $n$ is the number of samples, $k$ is the number of active experts, and $T$ is the complexity of a single expert, the complexity of online GNN is $O(nT)$, because k is usually a small constant, the running time of DyMoE is comparable to the lower bound online GNN. On the contrary, the retraining method has a complexity of $O(ntT)$, where $t$ is the number of data blocks, and $t$ is usually large ($t > 10$), leading to higher computational costs.

The paper claims that this method can handle topological and contextual changes, but how is this topological change quantified and assessed? Understanding the extent and nature of these changes is crucial for evaluating the effectiveness of the proposed approach. There are no experiments to address this problem.

Note that there is no golden rule/single metric to determine and quantify the distribution shift. Moreover, not all structural changes impact the labeling process. Hence, we did not include a distribution shift in the submission. However, we agree it will be more tangible to include some structural changes across data blocks to understand the problem and proposed method, and hence provide the change of several graph properties to understand the evolution of the data blocks. Because most datasets have over 10 data blocks, we present the overall standard deviation and mean of the graph properties for clarity. Specifically, we compute two important graph properties, the average number of triangles per node and the graph density, for each data block, and we compute the standard deviation and mean of these properties across data blocks, to show the change in graph structure.

From the results we can see that both properties have large standard deviations, validating the necessity of accounting for the structural shift.

The proposed DyMoE learns a new expert when a new data block arrives. This requires prior ...

Compared to other methods, the block-guided loss, which directly correlates samples to their corresponding experts, is designed to better distribute samples to the most relevant experts during inference.

In case of very small block sizes, it will not shift the entire distribution, and we might consider simply using the existing model for prediction or combining the new data into the latest block and retrain the last export. If we fine-tune on the small data block, most existing methods will suffer from overfitting due to the small sample size. On the other hand, updating the model with a small data block is not economical and favorable in production. People usually control the intervals between model refreshes to balance the model performance and the cost, and they typically update their models at regular intervals, such as daily or weekly, to accumulate sufficient numbers of samples.

However, we agree with you that the uneven block sizes present unique challenges to continual learning, and is a valuable setting to explore and present experimental results where the sizes of data blocks in a data stream are uneven.

[1] Zhou, Fan, and Chengtai Cao. "Overcoming catastrophic forgetting in graph neural networks with experience replay." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 5. 2021.

[2] Kim, Seoyoon, Seongjun Yun, and Jaewoo Kang. "DyGRAIN: An Incremental Learning Framework for Dynamic Graphs." IJCAI. 2022.

The results in Table 1 and Table 2 indicate that the proposed DyMoE model performs worse than baselines on the DBLP and Arxiv in terms of AA. However, the paper lacks analysis to explain this result.

Our method still outperforms other baseline on the Arxiv-Class incremental learning scenario. For the instance incremental scenario, we note that even the most basic baseline (Online GNN) is performing very well, showing that Arxiv Instance Incremental does not carry significant distribution shift that DyMoE is good at capturing, and DyMoE uses more parameters, which makes the model prone to overfitting more. For the DBLP dataset, we observe a trade-off between average accuracy and average forget. (Methods with higher accuracy get worse forget) For this dataset, it is difficult to learn new knowledge, without compromising some previously acquired knowledge. Hence we observe that DyMoE is good at maintaining a low forgetting while sacrificing some accuracy.

Efficiency Concern

For the training time, we pick these baselines for running time comparison because they are the most representative baselines. In particular, C-GNN has the same running time as ER-GNN when their memory set sizes are the same (which is the case in this paper). Hence, we only provided the running time of the most representative ones.

For the inference time, because finetune, ER-GNN and Retrain have the same architecture, they will have the same running time as well, which is why we provided the results for ER-GNN.

In the appendix, we conducted experiments when we increased the sizes of baseline models and found that their running time increased with minimal or even negative performance improvement. We present results when we make DyMoE’s parameter sizes the same as other baseline models in general response.

We can see that, when DyMoE and baselines have the similar number of active parameters, the inference time is similar, and DyMoE can still achieve promising results.

Concerns about ablation study.

We appreciate your detailed look into the paper, we will carefully revise this section to accurately reflect the experimental results. Meanwhile, we still observe that without data balancing, the overall average accuracy dropped by 1.8%, showing the necessity to inform the gating vectors the actual distribution of the data blocks. Without block-guided loss, the overall AA dropped by 3.8%, validating block-guided loss is necessary to train specialized experts. If the model is trained with all experts initialized at the first data block, the performance dropped by 2.2%, as this essentially degrades to a regular MoE model, which does not have a mechanism to prevent forgetting.

For Paper100M, we observe that the number of data samples per block increases, making more recent blocks have a higher weight in the overall accuracy. In this case, accurately representing the full distribution through DB is not as critical. For reddit, we observe that it is much denser then other datasets, requiring more parameters to learn the graph, and with more initial parameters, the w/o Dy model can model the first few data blocks better. Because reddit only has 8 data blocks, the benefit of DyMoE in choosing correct experts is not apparent.

Effectiveness of $K$

We additionally present results when we increase K. We can see that even with just one active expert, DyMoE is performing well, showing the effectiveness of the specialized experts. We also observe that K has a different impact on different data. Specifically, the benefit of more active experts saturates quite early for the arxiv dataset, while the reddit dataset continuously benefits from more active experts, which is intuitive as the gap between the full DyMoE and sparse DyMoE(K=3) is larger.

Code availability

We will release the code after the final decision.

We sincerely thank you for your detailed comments to help us improve the paper, and we would like to address some of your concerns here.

Theorem 1 is established under the assumption that the data follow a Gaussian mixture distribution, and this assumption should be explicitly stated in the theorem to make it more precise. Can this theorem extend to data following distributions other than the Gaussian mixture distribution?

We agree with you and modify the theorem to be more accurate in our revision. Meanwhile, theorem 1 consists of two parts, in the first part we show that DyMoE is at least as powerful as PI in arbitrary distribution. In the second part, we show that DyMoE is more powerful than PI under the Gaussian Mixture assumption. These two parts combined show that DyMoE is generally more favorable than PI. In terms of the theorem’s generalizability, we observe that in our proof, the only Gaussian property it relies on is the Gaussian Tail bound. In the proof, we can replace the bound with the definition of a sub-gaussian probability, and the theorem will still hold (sub-gaussian already includes a large class of distributions, such as symmetric Bernoulli, symmetric triangular).

The details of the data balancing training procedure (line 297-301) is not very clear from the paper. Specifically, how to select the memory set for the new data block?

Following many previous works [1,2], the memory node set is selected as top-K nodes whose embedding is closest to the class embedding. The K for each class is determined by the population. Let $d$ be the overall memory budget for a data block $B$, for one class $c$, $K = \frac{|B_c|}{|B|}*d$.

We perform data balancing training after training the new data block $B$. We first obtain its memory set $S_B$, and take the union of the memory set with all previous memory sets to get the overall memory set $S$. Finally, we train the model on S for a small number of epochs (e.g. 5 epochs) with classification loss and block-guided loss.

We will include a detailed description in the revision.

The number of nodes and edges per data block is not provided in Table 8. Moreover, the paper only introduces how to split the data into different blocks in Appendix C.2. However, it is unclear how to obtain the training, validation and test sets in each block.

For CoraFull and Reddit, we use the split provided by the DGL package, for ArxivIIL, we use the 0.6/0.2/0.2 train/val/test split within each data block, for ArxivCIL, we use the original split provided by the OGB package. For DBLP and paper100M, we use the split provided by PI-GNN.

For the specific number of nodes and edges, because the datasets have up to 49 data blocks, we present them as line plots in the updated pdf.

It is unclear which GNN model was used in the experiments, and whether the same GNN model was applied to the baseline models.

We strictly follow the GNN architecture described in line 323 of the paper, which is a GIN with the proposed DyMoE module. For all other baselines, we also use GIN, if applicable.

Details of the evaluation metrics are missing, including how each metric is calculated.

The evaluation metrics are average accuracy and average precision, which are described in the preliminary section in Equation 1.

In line 429, the paper states that “we can see our method significantly improves over existing baselines for both AA and AF”. However, this is inaccurate since the performance of DyMoE (57.85) is actually worse than the baseline PI-GNN (59.18) on DBLP in terms of AA. AND In line 430, the paper states that “We reach an average of 5.47% improvement in AA and 34.64% reduction in AF”. However, it didn’t specify which model these improvements are compared to.

We will revise the experimental section to more accurately analyze the results. Here, we are referring to the overall performance. Because none of the baselines achieves unanimously the best performance on all datasets, the average performance improvement is computed over the best baselines for each dataset to make it a more strict and challenging evaluation for DyMoE. Specifically, we compare DyMoE with C-GNN on Corafull, arxiv, and Reddit for AA, because C-GNN is the best baseline on these datasets, and we compare with PI-GNN on DBLP as PI-GNN is the best baseline on DBLP. We then take the average change as the overall performance improvement. Under this protocol, we achieve a 5.47% average improvement in AA and a 34.64% average reduction in AF, which show that overall DyMoE is more optimal.