Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper suggests a method for buffer construction in memory replay for node classification.
The suggested technique reduce the space complexity of the trivial algorithm from O(nd^L) to O(n).
The authors also discover and define the pseudo-training effect which is unique to continual learning on non-euclidean data. Finally, the authors present a coverage maximization sampling strategy to improve their suggested continual learning technique further.
strength_and_weaknesses: *Strength* 

The paper aims to suggest solutions for an important real-world problem.

The suggested method outperforms previously suggested techniques for continual learning.

*Weaknesses*

The contributions for the paper, as presented by the authors, are divided into three:

1. PDGNNs - SSEs 
2. Pseudo-training effect discovery
3. coverage maximization sampling strategy

I will refer to each of them separately.

1. The idea of decoupling the weights from the topology using two steps, in which nodes are represented as vectors, is trivial. I believe the challenge is how to encode the nodes to minimize the effect of the forgetting problem. The authors chose to encode the entire subgraph required by an MPGNN with L layers to represent the node as a vector. Their suggested technique is strongly based on previous works with minor additions. Justifications for the additions are also missing (for example, why the summation operation is being used). Moreover, different works encode subgraphs in an unsupervised manner [1,2], so a comparison is required here, in my opinion.

2. The pseudo-training effect is an expected phenomenon when dealing with homophilic graphs. 
Question: Will the pseudo-training effect damage the performance of PDGNN - SSE on heterophilic graphs? 

3. The sampling method is relatively naïve, and it is not compared to any complicated sampling method presented in the literature [3,4].
Question: What changes (if any) are needed to be done to fit the sampling method to heterophilic graphs?



Question: In table 4, why PDGNNs sometimes outperform Joint?


[1] - Sub2Vec: Feature Learning for Subgraphs, Adhikari et al.
[2] - subgraph2vec: Learning Distributed Representations of Rooted Sub-graphs from Large Graphs, Narayanan et al.
[3] - Metropolis Algorithms for Representative Subgraph Sampling, H¨ubler et al.
[4] - Diversified Top-k Subgraph Querying in a Large Graph, Yang et al.
clarity,_quality,_novelty_and_reproducibility: The paper is clear and well written.

Reproducibility of the experiments is difficult due to the lack of all the implementation details (a link to the code for example).



summary_of_the_review: From the reasons written above, I think that the novelty of the paper is relatively weak and not meets the threshold of being published in a top-tier venue.
Hence my pre-rebuttal score is (reject: 3)

I expect the authors to respond to my concerns raised in the weaknesses section for my re-evaluation of this manuscript.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper presents a memory replay-based continual learning model based on simplified GNN models. When new nodes are added to the graph, the continual learning GNN keeps optimizing on both the new nodes and the old nodes in the reply buffer to avoid forgetting the historical information. The decoupling of message propagation from feature transformation enables the replay buffer to only store the target node embeddings without any neighborhood information, thus addressing the challenge of neighborhood explosion. Essentially, the proposed method is to apply decoupled GNN models to existing continual graph learning frameworks. Experiments show significant accuracy gains compared with baseline continual graph learning methods. 

strength_and_weaknesses: ## Strengths

+ The paper is clearly written and easy to read. 
+ The authors sufficiently discuss the related works in various areas, including continual learning and decoupled models. 
+ The proposed method achieves significant improvements in empirical evaluation. 


## Weaknesses

- The novelty is limited. The overall idea is simple. I view it as applying decoupled GNN models to the existing continual learning pipeline. The decoupled GNNs are based on known models in the literature. 
- The theoretical results are not too significant. The usefulness of pseudo-training highly depends on the extent of homophily as well as the graph structure. If a neighbor node has a different label from the target node, then the pseudo-training effect is actually not desired. In addition, if the neighborhood of a neighbor node is different from that of a target node, then the pseudo-training will also deviate significantly from the “actual” training. 
- How do you interpret the re-scaling factor in Theorem 1. For example, why such specific form of scaling helps improve learning quality? Why it makes sense to train the "real" target node without re-scaling yet pseudo-train the neighbor nodes with re-scaling?
- Although empirically working well, the proposed coverage maximization sampling is based on a straightforward heuristic.  
- Baselines in experiments seem to be a bit out-dated. Most of them are 2017 and 2018 models. In addition, from Table 2, it seems that coverage maximization does not significantly outperform other sampling algorithms, even though the coverage ratio of other sampling algorithms is significantly lower. The leads to a question on how important is the “coverage maximization” criteria. 

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and easy to read. There lacks some technical depth in the proposed model as I feel it is more like applying decoupled GNNs to the existing continual learning pipeline. The Theoretical results also lack some significance. Overall, the novelty seems to be limited due to its close connection with known decoupled and continual learning models. 
summary_of_the_review: Overall, although this is a well-written paper, I think it is still below the bar of acceptance due to its limited novelty and technical depth.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The author propose PDGNN with SSEM for continuous graph representation learning to solve technical challenge of applying memory replay techniques to GNNs. By applying SSE, the memory space complexity was reduced, which enables PDGNN to utilize topological information sampled from previous tasks. The author also analyzed the pseudo-training effect of SSE and develop coverage-maximization sampling, which is claimed to be efficient under tight memory budgets.
strength_and_weaknesses: Strengths
The paper is well written.
As mentioned in Section 3.3, the authors noted that NL(v) typically contains O(dL) nodes, replaying n sampled nodes would require storing O(ndL) nodes, where d is the average node degree. In the Reddit dataset, which has an average degree of 492, the buffer size is easily intractable even with a small MPNN. So, directly storing computation subgraphs for memory is not feasible for GNNs. To solve this problem, the proposed method reduces the memory space by storing SSEs instead of the computation subgraphs for optimizing PDGNNs. Specifically, for a model parameterized by θ and the input Gsub v, if optimizing θ with Gsub v or ev is equivalent, then the embedding vector ev is a sufficient subgraph embedding of Gsub v. Recomputing the representation of v every time the trainable parameters are updated requires computing all nodes and edges of Gsub v. To address this issue, the authors propose the Parameter Decoupled Graph Neural Network (PDGNN) framework, which decouples trainable parameters from individual nodes/edges. Its general process is that, first, the topological information of Gsub v is encoded into the embedding vector ev through the unlearnable function ftopo( ). Next, ev is further passed into the trainable function fout(θ) to obtain the output prediction ˆyv, since the trainable parameters act on ev and not directly on any single node/edge, the model parameters θ are optimized using ev or Gsub v are equivalent. Since optimizing the SSE is equivalent to optimizing the computational subgraph of the PDGNN, the memory buffer only needs to store the SSE to reduce the space complexity from O(ndL) to O(n). This is a simple and effective method.
In Section 3.5, the paper mentions that SSE with larger computational graphs covering more nodes may be more efficient. The authors design a coverage-maximization sampling strategy to exploit the benefits of pseudo-training effects. The paper states that computing Rc(SSEM) for all possible SSEs in each iteration is time-consuming, especially on large graphs. Therefore, the authors propose to sample SSEs from a multinomial distribution based on the coverage of each individual SSE. Coverage-maximization sampling strategies appear to be practical.
The authors conducted a number of persuasive experiments. Performances under class-IL are significant.
Related works are properly cited.

Weaknesses
Performance under task-IL is not good enough. It is just a little better than the previous SOTA work.
You'd better write the contribution of the paper in the form of bullet points, the writing style of the last paragraph in the first section is not easy to read.

clarity,_quality,_novelty_and_reproducibility: The paper is well written. Most sections are well organized. I suggest that you’d better write the contribution of the paper in the form of bullet points, the writing style of the last paragraph of the first section is not easy to read. The contributions of PDGNN with SSEM and coverage-maximization sampling proposed in the paper are significant. The results of the paper can be reproduced by other researchers.
summary_of_the_review: In conclusion, this is a good paper. I am in favor of accepting this submission.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper intends to solve the memory explosion problem in the memory replay method for continual graph learning. By presenting Parameter Decoupled Graph Neural Networks (PDGNNs) with the proposed Sufficient Subgraph Embedding Memory (SSEM), the paper shows by empirical studies that the method can reduce memory space by a large margin. 
strength_and_weaknesses: Strengths:
1. This paper exhibits a clear logic chain to solve the memory explosion problem in the memory replay method for continual graph learning. The idea of stripping trainable parameters from the neighbor aggregation procedure is clear and effective for reducing the burden of memory replay.
2. Exhaustive experiments are conducted to compare the proposed method with baselines. The proposed PDGNNs overwhelm other baselines across all datasets and perform close to the joint-training strategy, which is carried out as the upper bound.

Weaknesses:
1. This paper is more like to integrate various existing methods. The formulation of the PDGNN with SSEM is almost identical to that of the SGC (Simplifying Graph Convolutional Networks) method. The memory replay framework and coverage maximization sampling method almost show no differences from those of the ER-GNN paper (which is also a baseline in this paper). Consequently, this paper shows limited novelty.
2. This paper claims that the memory replay benefits from the SSEM module by compressing information from subgraphs, which shows an advantage over the ER-GNN method. However, to the best of our knowledge, the ER-GNN method adopts the GAT network as its backbone, which also integrates information from neighbor nodes. Thus, the ER-GNN method can not be treated as a single-node buffer method. Consequently, the reason for the performance improvement over ER-GNN is not convincing and needs more explanation.
3. Proposal of the coverage maximization sampling method is not innovative and lacks a detailed explanation in terms of two points. Firstly, the necessity of the sampling strategy requires more explanation: why not just exploit the coverage maximization method as stated in the ER-GNN paper? Moreover, the ER-GNN performs best with the influence maximization (IM) method, which is not mentioned in this paper.
4. In terms of the proposed metrics (Average Accuracy and Average Forgetting), this paper overwhelms other baselines and almost achieves the upper bound. However, the ER-GNN paper adopts different metrics (Performance Mean and Forgeting Mean) which are not inspected in this paper.
clarity,_quality,_novelty_and_reproducibility: Clarity: Good

Quality: Fair

Novelty: Limited

Reproducibility: Good
summary_of_the_review: The idea of compressing subgraphs into vectors is straightforward and intuitive, but the method in the paper is composed of off-the-shelf methods and lacks innovation.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes an approach for continual learning in the graph learning setting, based on a memory replay approach. To avoid the neighborhood explosion issue where too many node embeddings must be stored, they develop a decoupled approach (PDGNN) to enable efficient memory replay. They then propose a pseudo-training effect which strengthens the prediction of nodes in the same subgraph, motivating a coverage maximization sampling strategy to enhance performance.

In general, reviewers find the paper to be clearly written, and well-motivated by the memory explosion issue. However, there are a number of main issues raised by reviewers:

- Some reviewers felt that the technical novelty is limited, particularly as the method can be seen as an application of decoupled GNNs to the continual learning setting, considering that decoupled GNNs have well established benefits in computational efficiency. Other reviewers also find similarity to other continual learning approaches for the graph setting, e.g. ER-GNN. In the author response, the authors point out a number of differences to ER-GNN, such as storing subgraphs instead of nodes for replay, and their coverage maximization strategy focusing on the topology rather than attribute / embedding space. 

- Two reviewers questioned whether the method design is appropriate for heterophily graphs, considering some of the method's design aspects are tailored towards homophilic graphs. The author response states some additional strategies for adaptation to heterophily graphs, and that pseudo-training can still benefit this setting (though there is not empirical evidence for this, which is understandable).

- Reviewers also noted that the coverage maximization strategy does not clearly outperform other sampling algorithms, despite the other strategies having much lower coverage ratio, which leads to the question on the importance of the coverage maximization criteria. 

In the end, reviewers and AC agree that while the work has promising merits, due to these issues, the work is not yet ready for publication at ICLR. The reviews offer a number of helpful suggestions for improvement, so I encourage the authors to continue improving the paper based on the reviews for future submissions.
justification_for_why_not_higher_score: The main issues (in order) were the limited technical novelty (compared to decoupled GNNs, which have well established benefits in computational efficiency), the suitability of the method's design for heterophilic graphs, and evidence for benefits of the coverage maximization strategy.
Decision: Reject