Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: This work studies the problem of online or incremental learning in temporal graphs (dynamic networks), and more precisely, whether past data can be discarded/ignored without losing predictive accuracy under the assumption that there is the presence of a distribution shift. This question has been essentially investigated over the years in various contexts, e.g., relational learning and classification in dynamic or time-evolving networks. It is also completely obvious that forgetting older data, especially under the assumption of a distribution shift, makes sense and is the correct thing to do. This is exactly what has been done in time-series forecasting for decades. The problem formulation is unclear and can be more precisely defined and motivated appropriately. This needs to be fixed. Are the class labels of a node changing over time, so if a node has label A at time t, then at time t+1 it could have label B, etc. This doesn’t seem true, as it seems the class labels of the nodes are “static”, which is unrealistic in many cases. How are the graph snapshots created? How was the timespan selected? What does every time step represent (1 hour, 5 minutes, etc.)?  Also, are the node features changing over time? This doesn’t seem true, but if this is the case, then it is unclear why this would be the case in practice (it would be great to provide some motivation for this, or an example application or problem where this may be true). There are many assumptions that make this problem unrealistic. Furthermore, there have even been works that study the dynamic node classification problem previously, see [1-2] below. 

The contribution and novelty of this work is unclear. Many important related works are missing. There have been countless works that have studied the impact of the temporal window and its size, as well as discarding past data, and using different amounts, as well as the representation of that past data (exponentially weighting links). This work also studies the impact of ignoring past data on node classification. Furthermore, many of the standard papers on this topic are seemingly missing such as CTDNE [10] and JODIE [6]. There are many other important works on incremental/online learning in dynamic and streaming graphs that are missing in the paper, see [4]-[13], which need to be referenced and appropriately discussed, mentioning the differences, and so on. The real contribution seems to be a new dataset with a controlled distribution shift. But putting this work into perspective with the related work, and explicitly stating the differences would help clarify the contribution and better position this work with respect to the existing literature.


Pros
  + Paper is well-written for the most part and easy to understand
  + New dataset with controlled distribution shift

Cons
  - Limited technical novelty and contribution
  - Important related work is missing and should be discussed appropriately to better position the work 
  - Problem formulation is unclear and can be more precisely defined, and motivated. 
  - Previous work has studied essentially the same research question and findings are obvious

The results and findings are in terms of time steps, however, the notion of a time step is not the same for every graph, nor is it ever discussed how the time steps are actually derived. Does every time step represent 30 seconds, 5 minutes, 1 hour, 1 day, etc. Furthermore, the results only make sense for the specific time step chosen for each graph. For instance, it is mentioned that “GNNs achieve 95% accuracy with a small window size of 3 or 4 time steps”. However, if the time step is extremely large then the result/findings change. And so all the findings in this paper and the discussion depend precisely on the data and the authors choice of how to create the time steps, and what granularity to use, which isn't discussed. This issue was discussed extensively in previous work. Minor comment: the labels in nearly all the figures are too small to read.




1. Time-evolving relational classification and ensemble methods
2. Deep dynamic relational classifiers: Exploiting dynamic neighborhoods in complex networks
3. A task-driven approach to time scale detection in dynamic networks
4. Dynamic Node Embeddings From Edge Streams
5. Afraid: fraud detection via active inference in time-evolving social networks
6. Learning Dynamic Embeddings from Temporal Interactions
7. Node Embedding over Temporal Graphs
8. Representation Learning in Continuous Entity-Set Associations
9. Efficient representation learning using random walks for dynamic graphs
10. Continuous-Time Dynamic Network Embeddings
11. Dyn2Vec: Exploiting dynamic behavior using difference networks-based node embeddings for classification
12. Real-Time Streaming Graph Embedding Through Local Actions
13. Temporal Graph Offset Reconstruction: Towards Temporally Robust Graph Representation Learning

review_title: Official Blind Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: ### Summary
This paper proposes a paradigm which speeds up the training time of GNNs while not compromising too much performance. The method adopts a layerwise training procedure. In particular, the authors inject a loss function at each layer while storing and fixing the feed-forward values of its previous layer. The training is then carried out along all layers parallelly, which allows the updating of paradigms to be decoupled and is not applicable in previous works. A further improvement (lazy-update) by not updating the feed-forward values of each layer is used to reduce the training time.

### Reasons for Score
The paper discusses the important topic of layer updating and proposes a decoupling strategy that enables a layerwise parallel updating scheme. However, the lazy-update technique that has been argued as another important point is not fully justified in its memory usage, higher parameter setting, and performance consistency between different experiments.

### Pros
The paper tackles the problem of layer decoupling in GNN training, which is an important problem when training large-scale networks. The decoupling training approach is useful if the memory can hold multiple feed-forward layers’ outputs, which is not the case with previous methods [1].

### Cons
The paper proposes two strategies: decoupling technique and lazy-update. While I think the first strategy is a good supplement to the previous work, I do feel there are some points that are not properly justified in the arguments and experiments of lazy-update.

1. The actual memory used in LU-DGL-GCN lazy-update. It is stated that in Algorithm 2, $\hat{H}^{(l)}$ is used for each layer, which means that there need to be at least $LNK$ extra space needed for memorizing these parameters as $\hat{H}^{(l)}$ can not be computed on-the-fly due to its lazy-update nature (e.g. $T_{lazy}$ is too large, when we are at Epoch $t$ updating $W^{(l)}$, $\hat{H}^{(l-1)}$ may refer to $FH^{(l-1)}$ where $H^{(l-1)}$ holds the value multiple epochs ago). With this being said, it’s hard to figure out why LU-DGL-GCN still has similar memory usage as with L2GCN and is drastically different from the normal GCN.

2. The balance between stableness of LU-DGL-GCN and the large value of $T_{lazy}$ is hard to find. In Fig. 3, the authors show that the framework is sensitive to $T_{lazy}$ and can be highly unstable when it is at a small value (e.g. 1 or 5). However, it is natural to find that $T_{lazy}$ should not be too large as it could slow the training procedure. In the extreme case, if $T_{lazy}$ is infinite, we can see that the previous layer’s output $\hat{H}^{(l)}$ is never updated and the parameters of the whole GCN, therefore, can never be properly optimized. It would be meaningful if the authors could discuss how to set $T_{lazy}$ for the balance of stableness and time cost which is an important point the paper has argued for the approach.

3. Exact training time comparison should be stated. It would be necessary to state clearly how the time is computed in Table 2, e.g. fixed epochs or same validation loss, the latter one of which is a more proper choice as the authors are wishing to show the framework is efficient with similar accuracy. With this stated, it is also strange to find that the accuracy of LGCN is higher than LU-DGL-GCN in Table 2 while it is not the case in Figure 3 where Sequential_test is larger than any lazy-update.

### Clarifications
Please address and clarify the cons above.


[1] L2-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks

review_title: Good framework for layer decoupling but lacks justification for lazy-update

final_score: rating: 5: Marginally below acceptance threshold
review_content: This work empirically evaluates the sliding-window strategy for training GNNs with temporal graphs. One may cast the temporal nature of the graph data in an online setting, under which the change of the graph structure as well as the variation of the classes cause distribution shift. The authors conduct a series of experiments to show that the sliding-window strategy is as effective as using the entire historical data for training.

Pluses:

+ For different temporal graphs, the duration of a time step and the number of time steps (window size) are often ad-hocly defined and are not comparable. The authors introduce a measure of temporal difference that facilitates a more principled definition of the time step and the window size so that they are comparable across datasets.

+ The authors pose four important questions and conclude clear answers based on experimentation. The findings are: (1) incremental training is necessary to account for distribution shift, compared to a once-trained, static model; (2) incremental training with warm start does not always yield better performance than cold start; (3) the window size needs be large enough for incremental training to catch up with the performance of full-data training (e.g., covering at least 50% receptive field); and (4) these findings extend to several GNN models.

+ The authors compile three temporal graphs, which enrich the availability of benchmark datasets.

Minuses:

- The empirical findings are very much expected, which means that they are not exciting. From the methodological point of view, using sliding windows to train temporal GNNs is a no brainer choice if certain RNN modeling is involved. Since most of the presented results are naturally expected and there lacks theory/method contribution, the reader is unsure about the value of the paper.

- A common pattern of the contributed datasets is that nodes and edges are inserted but never deleted. While the empirical findings are quite natural in this simple scenario, there will be a lot more uncertainty when the scenario becomes increasingly complex. For example, in social networks, accounts represented by nodes may be deleted and relationships represented by edges may dynamically change.

  For another example, in communication networks where an edge denotes communication between two entities, the edges are instant and time stamped. The challenge in this case is less about distribution shift, but more about how to handle edges and what are the consequences. The online learning of this kind of data necessarily goes beyond a simple GNN such as the ones experimented in this paper, but the findings will be more valuable.

review_title: Empirical work. Results are expected but not exciting.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Temporal graphs can naturally model many real-world networks, and many graph neural network (GNN)-based methods have been proposed recently. Existing temporal GNNs can handle vertices and edges appearing / disappearing over time, but not vertex classes. This paper precisely considers this problem, and
1) compiles three vertex classification datasets for future research,
2) proposes an experimental procedure for evaluating performance under this setting,
3) explores 5 existing GNNs, and concludes that incremental training for limited periods is as good as that over full timelines.



## Pros
1) (Motivation) It is reasonable to assume that new classes can appear over time in real-world networks. It is also worth investigating whether the full temporal graph (seen so far) is actually required for GNN neighbourhood aggregation in the current timestep.
2) (Relevance) Learning representations on temporal graphs is a challenging, fast-growing topic, and relevant to the ICLR community.



## Cons
1) (Soundness) Tables 2, 3, and 4 compare accuracies of different static GNNs with varying window sizes (proposed idea) and with full graph (existing idea) which is informative. However, to increase the impact of the paper, the proposed idea (with static GNNs) should also be compared against state-of-the-art temporal GNNs on full graphs (in all these tables). As already cited by the authors, recent temporal GNNs include (but are not limited to)
(a) EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs, In AAAI'20,
(b) Inductive Representation Learning on Temporal Graphs, In ICLR'20.
2) (Significance) The experiments in the paper are restricted to multi-class vertex classification with new classes appearing over time (in just one dataset domain based on scientific publications). The authors should clarify what challenges one would face for multi-label classification commonly seen with some datasets (e.g. social networks). It would be more convincing if experiments were also conducted on link prediction (e.g. social network link prediction with new classes i.e. communities appearing over time).  
3) (Originality) Although the assumptions (classes appearing/disappearing over time), evaluation procedure, and datasets have not been considered / proposed before, the novelty of the paper is quite limited. As also acknowledged by the authors, the paper explores well-known existing static GNNs for temporal graphs. From this point of view, the paper is of limited originality since it explores well-known algorithms in an unexplored setting.



To summarise, the paper has strong arguments along the axis of motivation but the major weaknesses outweigh the strengths.
review_title: Interesting problem; technical contribution is limited given prior work

Meta-review: This is an empirical paper that proposed a few different settings for applying GNNs on temporal data, including what context window to use, code-start vs warm-start, incremental training vs static.  This paper also proposed and released a few more temporal graph datasets, which could be useful.

The consensus assessment of the reviewers is that the contributions of this paper are incremental, and the results are expected and not exciting enough.

I want to in particular point out that the results highlighted in the paper, that a GNN with window size 1 is sufficient to recover 90% of the performance of the model on full graph, is probably not the correct message to communicate.  This either indicates that the data and task used in the benchmarks do not require sophisticated long-horizon temporal information (which makes the comparison between any methods uninteresting), or it indicates that the metric is not sensitive enough to sufficiently distinguish models trained with different settings.

I would recommend rejection and encourage the authors to improve this paper.
Decision: Reject