Efficient Neural Common Neighbor for Temporal Graph Link Prediction

Thank you for acknowledging the effectiveness and efficiency of our method demonstrated by extensive experiments. We address your concerns as follows.

Weaknesses:

W1. The authors should have a special discussion on whether the biggest difference between TNCN and NCN is the core contribution of this paper. If so, this should be highlighted. If not, more introduction is needed on the importance of the new scenario.

Thank you for the suggestion on clarifying our contributions. In fact, the core contribution is our combination of memory-based backbone and Neural Common Neighbor method for temporal link prediction, which is exactly about the difference between our TNCN and traditional NCN.

For the utilization of memory-based backbone, it uses a memory module to dynamically store and update the node memory. This pipeline can process the edge interaction stream only once for inference, avoiding the repeated computation of node embeddings within different subgraph. However, traditional NCN uses static GNNs as its backbone, thus bringing about high computational costs. Another is our NCN extractor. Here we adopt a batch-wise operation to extract the common neighbor information between a given node pair. These information can be used to aggregate the related node embeddings to obtain the pair-wise features, thus enhancing the capability of our TNCN model.

For a clear representation, we have also appended a table about the comparison between TNCN and NCN in section 4 in the revised PDF. We have also put it below:

W2. Since the strategy proposed in the paper is built around the batch processing mode of sequential graph learning, whether the batch size will have a different impact on the strategy is something that needs to be considered and discussed.

Thank you for your inquiry regarding batch size. In our experiments, two notations of batch size should be considered: the ''benchmark batch size'' and the ''model batch size''. 1. The benchmark batch size refers to how the benchmark processes events. Theoretically, each event can access all preceding events for prediction. However, to reduce computational cost and seek for a fair evaluation comparison, most benchmarks process consecutive events that occur in a specified time interval, allowing the model to make predictions for them using the same context. In TGB, this consecutive grouping is fixed at 200 for all models. 2. The model batch size defines the number of events the model exactly processes in a batch. In TGB, this is also commonly set to 200, which we follow in our default configuration.

We also conducted an ablation study to analyze the effects of varying the model batch size. Our results indicate that our model achieves consistent, linear speedup with increasing batch size, showing potential for further scaling. In contrast, some models that lack batch processing capabilities do not demonstrate this acceleration.

For W3 and W4, please see the comment below.

Thank you for acknowledging the motivation and representation, and the effectiveness and efficiency of our method demonstrated by extensive experiments. We address your concerns as follows.

Weaknesses:

W1. Lack of Novelty. Firstly, the idea of extracting common neighbors in temporal graphs has certainly been explored before. It seems that the design of your key component, the "CN Extractor," closely resembles existing work in KDD2024 [1]. Moreover, your CN extracting component does not appear to include any specific improvements for temporal graphs. Simply extracting "monotone k-hop events" does not substantiate this claim.

Thanks for recommending this contemporaneous work. This paper is on arxiv in July and published in KDD in August, while ICLR submssion is on October 1st. It is within four months and is not required to be compared according to ICLR policy (https://iclr.cc/Conferences/2025/FAQ). Nevertheless, we have incorporated the comparison in the revision.

For the aspect of encoding common neighbor information, TNCN has its own distinctions apart from CNE-N from [1]. The biggest difference between our TNCN and the CNE-N is that, we explicitly utilize the node embeddings of the common neighbors in the prediction stage. While CNE-N calculates the co-neighbor encoding of node pairs within the local subgraph, it only records the number of the neighboring nodes, ignoring their embedding information. There are also two slight differences between the two models. Given node pair $(u,v)$, CNE-N considers the number of common neighbors of $(u,i)$ and $(v,i)$ pairs for all $i$ in the local subgraph. In contrast, TNCN only takes the common neighbors between $u$ and $v$ and their embeddings into account. Furthermore, CNE-N uses hash table to map a node to its position while TNCN takes monotone storage to keep the order of the input events. Our implementation is more friendly when it's required to take the most recent interactions within a specified time interval.

W2. Lack of Important Baselines. Since you "extend Neural Common Neighbor for static prediction methods," these static methods should also be included in your comparisons. Lack of Case Study. Providing specific case studies could enhance the understanding of your method.

About static methods

Thanks for your suggestion on adding the static methods as baselines.

In fact, we had put the experimental results of some classic static methods in appendix B.2. We considered CN, RA, AA, PPR and ELPH of BUDDY. Please refer to the table 7 for detailed performances.

About case studies

Thanks for your advice. You can refer to the figure 1 in our paper to get a first sight about the effectivity of our TNCN. We have also complemented some case study examples from Wiki and Coin dataset to make it more intuitive to understand the key component. Please refer to Appendix G in our revised PDF.

W3. Ambiguous Expression. What does 'emb' mean in Equation 2? It seems you haven't explained it anywhere—does it refer to memory? Your method encodes the common neighbor neighborhood composed of source-destination node pairs; might this lead to a loss of other information (e.g., nodes that are not common)?

Thanks for your point. Here the 'emb' refers to the node embeddings, which can be obtained from the node memory (i.e. 'mem') with some transformations, including identity, linear, or graph attention, etc. Our implementation follows the standard TGN, which uses graph attention. Thus, emb also includes neighbors' mem information. We have updated it in the revised PDF.

Note that TNCN does not only leverage common neighbor while losing other information (e.g., nodes that are not common). As shown in Equation (5) in the paper, the final representation of (u,v) combines both u and v's embeddings as well as their common neighbors' embeddings, where u and v's embeddings contain those non-common-neigbhor information.

For W4, W5 and Questions, please see the comment below.

Thank you for acknowledging our reliability of evaluation and the combination of the modeling approches. We address your concerns as follows.

Weaknesses

W1. Presentation: The abstract implies that common neighbor methods are primarily used in static graphs, overlooking their established role in dynamic graph modeling. Additionally, the motivation for combining memory-based and neighbor-based techniques is presented only briefly at the end of the introduction.

Thank you for your comment on our presentation. Firstly, we want to clarify that we do not intend to overlook previous work; in fact, we provide a comprehensive discussion on related work in both Sections 1 and 2. Below we further explain each point in detail.

Abstract

Note that we said "traditional methods usually ..." in abstract. That is exactly the case. The methods in large-scale benchmark TGB, including DyRep, TGN, CAWN, TGAT, TCL, Edgebank and Graphmixer, primarily still do not involve pair-wise information to make the final prediction. Only two out of nine methods consider pairwise features in dynamic graph modeling, thus substantiating our statement.

A second perspective, which we did not emphasize in the abstract, is how our model achieves greater efficiency than graph-based framework methods that already incorporate pairwise information. Balancing the use of pairwise information and the overall efficiency is essential but challenging. Pairwise information was typically excluded in memory-based methods due to its high computational cost, and existing dynamic graph models face limitations in handling it. For instance, DyGFormer only considers the frequency of 1-hop common neighbors without capturing their features or embeddings, while NAT learns conditional representations for each node’s neighbors, requiring subsampling to avoid the quadratic complexity. These limitations make these models less applicable to large datasets. To address these challenges, we developed TNCN, which is an efficient and powerful pairwise model.

We chose not to highlight all the points in the abstract to present our model more straightforwardly, not to overlook existing methods. We certainly acknowledge the contributions of prior work, as outlined in our Introduction (lines 80-85) and in Section 2.2 (Related Work). With your feedback in mind, we have further revised the abstract to clarify these dual perspectives. We welcome any suggestions on how we might better convey our approach while balancing simplicity and comprehensiveness.

Motivation

Our motivation of combining memory-based backbone and neighbor-based technique is not limited to the end of the introduction. In fact, in section 1 (introduction) paragraph 3 and 4, we have first mentioned that we are urged to seek for pair-wise information for the innate drawbacks of node-wise prediction. In paragraph 5, we have stated that graph-based methods commonly suffer from high computational complexity issue, thus turning our sight to the more efficient memory-based backbone. In section 2 (related work) we have also talked about the characteristics about memory-based methods with efficiency and graph-based with pair-wise feature, enhancing our motivation about our innovation on combining the memory-based backbone and dynamic NCN processor. We will present the introduction better to make the motivation more clear.

For other concerns, please see the following comments.

Thank you for acknowledging the performance and efficiency advantages of our model. We address your concerns as follows.

W1. Since the process is relatively complicated, it is recommended to provide a pseudo code to make it easier for readers to understand.

Thank you for this suggestion. We have included pseudo code to illustrate the pipeline of TNCN, and it is now placed in Appendix E in the revised PDF.

W2. I suggest that the experimental part be supplemented with an analysis of the hyperparameters, which can make the values of the hyperparameters more reasonable.

As per you request, we conduct experiments for the analysis of the hyperparameters to make their values more clear and reasonable. We particularly focus on num_neighbors and emb_dim&mem_dim, which have a larger influence on the performance of the model. The experimental results are shown as follows:

We have also attached these parameter analysis in the appendix C in our revised PDF, and we will make a better organization later.

Questions:

Q1. High surprising values will degrade TNCN's performance. So will the model performance decrease monotonically as the surprise value increases? In other words, will TNCN have the best performance when the surprise value is the lowest?

Thank you for highlighting this point. The “surprising value” refers to the ratio of test edges that were not observed during training. Datasets with a higher surprising value are generally considered to require more advanced inductive capabilities.

We conduct experiments on the Wiki and Review datasets, calculating the MRR over ''surprising'' edges and ''unsurprising'' edges respectively. The result shown below reflects that the model can achieve a higher MRR on unsurprising edges than the surprising ones on both the datasets.

Q2. Why is the result of TNCN-0∼2-hop-CN lower than TNCN-0∼1-hop-CN on the comment dataset in Table 2, which is different from the other three datasets?

Neural Common Neighbors at different hops may contain varying information or even noise, thus having no guarantee to improve the model capability with the increase of the CN hops. We also conduct some experiments on Comment dataset and find that the performances are distinctive when using different hops of CNs. We can get some observations from the results:

1. The result of TNCN with all 1 hop CNs is higher than TGN, while TNCN with all 2 hop CNs is lower. This indicates that in this dataset, 1 hop CNs can benifit the capability of the model while 2 hop CNs will confuse it.
2. The result of TNCN with (0+1) hops CNs is higher than the (0+1+2), also suggesting the negative influence of 2 hop CNs.
3. (0+1) is higher than (1), and (0+1+2) higher than (1+2), facilitating the usefulness of introducing the 0 hop CNs.