Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper addresses graph representation learning in a particular online/continual/streaming setting in which subgraphs are sequentially recieved which may contain nodes of categories/classes that haven't been seen before, while performance on the previously seen categories/classes must be maintained.  The approach involves extracting "atomic" features based on node features and local network structure, then constructing and maintaining prototype embeddings at various levels of abstraction, in order to produce a final embedding to be used by a node classifier. In each iteration the method decides whether to introduce new prototypes based on matching to previous prototypes. The authors prove a bound on the number of prototypes (hence, memory requirements) and show that the method will avoid catastrophic forgetting. Experimental results versus various baselines are positive.
main_review: 
Originality: While graph representation learning has been heavily studied, including substantial work on temporal/dynamic networks, and continual/online learning has also received significant attention, the particular setting addressed in the paper is an interesting special case of the problem.  The proposed method has not been considered before, but it is not clear that broader insights arise from, or underpin, its development.  

Quality: Although intuitively appealing, the proposed model design is somewhat heuristic in nature.  It is unclear what fundamental principles motivate the use of prototypes or the various algorithmic choices which were made.  At least, the theoretical results in Section 2.5 show that the proposed method avoids certain pitfalls, but they do not otherwise guarantee how close to optimal the predictions are (e.g., in terms of regret).  The experimental results are a strength of the work, including good results in a systematic cross-validation-with-hyperparameter-tuning experiment compared to a number of baselines on multiple datasets, an ablation study, memory consumption, and t-SNE visualizations.

Clarity: The paper can be understood, with some effort.  There are relatively few typos or grammatical issues.  Figure 1, explaining the method, is helpful in understanding the approach.

Significance: The strong experimental results suggest that the proposed method is an improvement over the current state of the art at this particular representation learning problem, which may have practical importance.  However, the heuristic nature of the approach does not suggest that the ideas here will have influence beyond the narrow task, or will stand the test of time.

------

Thanks to the authors for their detailed and well argued rebuttal. The response was helpful for understanding how the authors perceive the points I've raised.   I have no problem with the hierarchical prototype approach proposed here, but I don't really see an overarching objective or motivating principle that spans both the matching prototypes phase and the learning phase, each of which seems to have unrelated objectives.
limitations_and_societal_impact: Graph representation learning can be subject to algorithmic bias/fairness issues.  It would be worth mentioning how this might be addressed in future work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper addresses the continuous representation learning problem for graph data. The main goal is to learn emerging novel node categories, and simultaneously maintain the learned knowledge over existing graphs. In the proposed solution called Hierarchical Prototype Networks (HPNs), several levels of general knowledge are extracted, in the form of atomic, node and class-level prototypes. A theoretical analysis for the memory consumption and continual learning capability is presented. Empirical study is conducted  on eight different public datasets, including large-scale datasets with millions-scale nodes.
main_review: Strong points

- The paper addresses an important, well motivated problem in graph representation learning with practical significance. 

- The presentation is largely clearly. 

- Experiments are fairly comprehensive, including results on large-scale graphs.

Weak points

- There is some similarity to few-shot learning on graphs [a,b], although they mostly focus on novel class only without considering how the performance of existing classes are maintained. Nevertheless, discussion and comparison with few-shot methods should be included, to highlight the advantage of HPN over few-shot methods.

[a] Meta-GNN: On Few-shot Node Classification in Graph Meta-learning. CIKM19

[b] Relative and Absolute Location Embedding for Few-Shot Node Classification on Graph. AAAI21.

- Hierarchical graph representation learning has also been explored [c,d], which is more flexible/self-adaptive than the 3-level prototypes in this paper.  

[c] Hierarchical graph representation learning with differentiable pooling. In NIPS 2018

[d] Graph Few-shot Learning via Knowledge Transfer. AAAI20.

- The model involves a number of hyperparameters related to the thresholds/number of candidates, including l_a, l_r, l'_a, l'_r, t_A, t_N, t_C. This would make model tuning slow and impractical. It is also possible that, as novel classes emerge, these hyperparameters may not to change as well for optimal performance.

- Message passing GNN is considered SOTA on graph data. The proposed solution derives representations from multi-hop neighbors, lacking the recursively defined message passing mechanism. A discussion on this is needed to demonstrate the design advantages and disadvantages of HPN.

-- update after rebuttal --

Based on the rebuttal, i have increased my rating slightly.
limitations_and_societal_impact: Fine with me.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper aims to address the catastrophic forgetting issue with continual learning on streaming graphs. To comprehensively incorporate the feature and topological information of new nodes, this paper proposes atomic feature extractors to project raw node features and neighbor nodes into distinct base embeddings, which are then used to refine or compose atomic-, node-, and class-level prototype embeddings in a hierarchical manner. Experiments demonstrate that by doing so, catastrophic forgetting can be avoided and promising accuracy can be achieved on continual graph learning tasks.
main_review: The highlights of this paper are as follows:
1. The proposed approach is well motivated, where the compositional node embeddings based on hierarchical prototypes is able to make the approach scalable to larger datasets.
2. Despite some syntax errors, the presentation of this paper is overall clear and easy to follow.
3. The experimental evaluations are thorough, spanning across a wide range of heterogeneous graph datasets, and most technical claims are backed by the results.

At the same time, several shortcomings of this paper are also noticed, which are listed below:
1. The parameter-saving claim only holds when the input node features do not include node IDs, where the AFEs only need to perform transformations on the low-dimensional feature vectors. In some other graph learning settings where node IDs are used as the input feature, AFEs will essentially be multiple node embedding tables where $d_v$ is the total number of nodes, which will dominate the parameter size and become less scalable than other methods that only maintain one node embedding table.
2. Equations 5,6,7,8 need 4 repetitive computations of pairwise cosine similarity between atomic features and the prototype embeddings, which can be very time-consuming given the potential size of set $\mathbb{P}$. Is the approach able to reuse results from previous steps (e.g., Eq 5) to cut the time cost?
3. The atomic features are refined by a hard selection process with pre-defined threshold. While the learning process seems to be end-to-end in Algorithm 1, it remains unclear how the hard selection of atomic features is made differentiable to allow for end-to-end training. 
4. The overall learning objective directly combines three loss functions without any coefficients to balance any part of the sub-losses, which is uncommon. It is expected to provide more details and justifications on doing so.
5. As mentioned above, several syntax errors are found in this paper:
- Incomplete sentences: Figure 1 --> “Given a node v”; Section 2.3 --> “To map … prototype presentations.”; 
- Section 2.2., “they are be uncorrelated” --> are uncorrelated
- Section 2.3, “HPNs then starts to” --> start
- Section 2.3, “a N-prototype” --> an

In summary, the highlights of this paper outweighs its shortcomings, while this paper can still benefit from some clarifications on the issues listed above.

limitations_and_societal_impact: The limitations of this paper are mainly associated with the lack of detailed explanations w.r.t. some technical claims, and the authors are recommended to provide more corresponding justifications.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces continual learning in graph settings, where new graph-based tasks come in over time. To learn effective node classifiers for new tasks without forgetting the old tasks, a three-level prototype network is outlined. Atomic, node, and class prototypes are jointly used on top of Atomic Feature Extractors, where only the relevant features and prototypes are selected and updated in each new task, without disturbing the others. Experiments on eight benchmarks show the effectiveness and lack of forgetting for continual node classification.
main_review: [Strengths]

This paper addresses a challenging task in graph learning, namely the scenario where new graph tasks come in over time. The proposed multi-level approach is interesting at a high level as it addresses different levels of granularity.

The paper furthermore excels at outlining current advances in continual learning and specifically in the graph context. This outline helps not only with providing the proper background and starting point of this paper, but also helps to understand what is new here.

The presented results show that the approach not only obtains a high accuracy overall, but at the cost of minimal loss of accuracy with the introduction of new tasks. These results highlight the potential of the proposed approach.

[Weaknesses]

There are a number of limitations to the paper that require addressing.

First, the method is not written well and unnecessarily hard to go through. Section 2 contains many unintuitive steps and unclear notations that make it hard to understand what is going on. For example:
- What is the idea behind subsampling the neighbourhood in lines 125-127?
- According to Equation 3, the node v is represented by a set of features, both from node and structure information. Why are these two sets combined in Equation 3 and separated again in Equation 5? And how do you go from AFE_{node}^{select} and AFE_{struct}^{select} to \mathbb{E}_A^{select}(v)?  There is no explanation and completely unclear.
- What is the point of Algorithm 1? It contains so few steps that there is no information anymore. Steps 4 and 5 are the same too.
- Where does \mathbb{A}(v) magically come from in line 178? What does associated with mean? And how big is the set  for each node? Again not clear from the method section.
- The N-prototypes are obtained from \mathbb{A}(v), and C-prototypes are obtained from N-prototypes. What does Equation 11 mean in that case? How can you throw them on one pile?
- At the end, there is a cross-entropy objective in Equation 12, where the likelihoods are obtained from a fully-connected layers that takes inputs from all levels of prototypes. Don’t the prototypes have different dimensionalities however? What is going on on lines 193 and 195?

Next to the mathematical explanation, the writing also requires improvement. A few examples from Section 2.4 and 2.5 (not a full list):
- Line 192: pass = passed
- Line 203: unlike topology-aware = unlike the topology-aware
- Line 204: HPNs do not require task indicator = HPNs not require a task indicator
- Line 228: is = denotes the / are the

Section 2.5 provides two theorems, but the appendix only provides a proof for Theorem 2. Where is the proof for Theorem 1?

In the experiments, Table 1 shows that the proposed approach outperforms all other approaches. Where do the numbers of the baselines come from? Baseline [39] should btw be updated to:

[a] 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.

In [a], they report a best PM of 95.66% and 81.83% on Cora and Citeseer, compared to 93.7% and 79.0% for this paper. Notably, [39] obtains only 71.1% and 65.5%. How come there are such big differences between what is reported in the original paper and what is reported in Table 1? Table 1 suggest that the proposed approach is far better than the baselines, while a direct comparison between papers suggests otherwise.

[Overall]

This paper addresses a challenging task with a multi-level approach. The method is intuitive at a high level and the related work is outlined well. The method section itself can however hardly be followed and requires big changes. Experimentally, there are also open questions that require attention regarding reported numbers.
limitations_and_societal_impact: The main limitation that is discussed is that only node classification is investigated. The checklist states that there are no negative societal impacts of the work.
review_title: null

Meta-review: The paper addresses graph representation learning when new categories of nodes emerge continually along with their associated edges. The idea is to learn a Hierarchical Prototype Networks (HPNs) which extract prototypes at different levels (atom, node, class) to represent the continually growing graphs. This allows updates to focus on relevant prototypes and atomic feature extractors. Analysis on memory consumption is given, along with continual learning capability.

Although the proposed approach is a bit ad hoc, it has interesting ideas and the empirical performance looks fine.  Three major drawbacks are identified by the reviewers, and I agree with them. Firstly, the presentation can be improved to clarify the motivation, and to provide an overarching objective or motivating principle that spans both the matching prototype phase and the learning phase (quote Reviewer 9787).  Section 2.2 and 2.3 read very dry, and Reviewer eRkd provided very detailed comments.  Secondly a detailed discussion on the large number of hyperparameters is needed.  Finally, although [c, d] raised by Reviewer E15x do not directly work on continual learning, the few-shot nature makes such adaptation quite straightforward.  A detailed comparison is needed on such extensions.

All reviewers except the most positive one (eQnQ) participated in discussions that are not visible to the author.

Minor: 
Equation 4 needs to reduce to a scalar
Algorithm has duplicated lines 4 and 5
Decision: Reject