Efficient Neural Common Neighbor for Temporal Graph Link Prediction

Authors: Xiaohui Zhang, Yanbo Wang, Xiyuan Wang, Muhan Zhang
Primary area: learning on graphs and other geometries & topologies
Keywords: Temporal graph, Neural common neighbor, Efficient

Abstract:
Temporal graphs are ubiquitous in real-world scenarios, such as social network, trade and transportation. Predicting dynamic links between nodes in a temporal graph is of vital importance. \textcolor{blue}{
Traditional memory-based methods typically leverage the temporal neighborhood of interaction histories to generate node embeddings, which are then aggregated to predict links between source and target nodes. However, these methods primarily focus on learning individual node representations and often neglect the nature of pairwise representation learning aspect. While some recent methods attempt to capture pairwise features, they are less emphasized in large-scale datasets like TGB. Meanwhile, most of these 
existing methods tend to suffer from high computational complexity due to the repeated calculation of node embeddings.
}
Motivated by the success of Neural Common Neighbor (NCN) for static graph link prediction, we propose \textbf{TNCN}, a temporal version of NCN for link prediction in temporal graphs. Based on a memory-based backbone instead of traditional static graph neural network, TNCN dynamically updates a temporal neighbor dictionary for each node, and utilizes multi-hop common neighbors between the source and target node to learn a more effective pairwise representation. We validate our model on five large-scale real-world datasets from the Temporal Graph Benchmark (TGB), and find that it achieves new state-of-the-art performance on three of them. Additionally, TNCN demonstrates excellent scalability on large datasets, outperforming popular GNN baselines by up to 6.4 times in speed.

Decision: reject
Reviewer scores: 6, 3, 5, 6

Reviews and discussion:
<thread>
creation date:
1729501318355

thread_type:
official_review

<thread_object>
creator: reviewer_erh5

<content>
summary:
The paper is about temporal link prediction, which is an interesting topic. The authors propose a temporal version of NCN for link prediction in temporal graphs, which dynamically updates a temporal neighbor dictionary for each node and utilizes multi-hop common neighbors between the source and target node to learn a more effective pairwise representation. The paper is well written and well organized. However, there are several concerns in the current version of the paper that addressing them will increase the quality of this paper.

strengths:
1 Cutting-edge research directions.

2 Clear writing logic.

3 Sufficient experimental results.

weaknesses:
1 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.

2 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.

3 The motivation and contribution of the paper are worthy of recognition, but in the main text, the authors can consider putting more emphasis on the contribution description and logical arrangement. At present, it seems that the proof takes up a certain amount of space, making the method and experiment part seem less substantial, and the information that can be expressed is not clear and comprehensive enough.

4 The authors could consider discussing the computational complexity, especially comparing it to similar methods (including static graphs and temporal graphs).

questions:
As above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730017802170

thread_type:
official_review

<thread_object>
creator: reviewer_p1sl

<content>
summary:
The author focuses on link prediction tasks in temporal graphs, which have ubiquitous applications in real-world systems. Instead of implicitly encoding common neighbor features from the historical neighborhood of the target node, the author proposes the Temporal Common Neighbor Extractor to explicitly integrate these features into the process of temporal graph representation learning, achieving both effectiveness and efficiency compared to existing methods on the TGB benchmark. Additionally, the author provides theoretical analysis based on their proposed method, offering a more thorough illustration of the model.

strengths:
This paper has several strengths worth noting:

* **Interesting Motivation.** The motivation for extracting common neighbor features is compelling.
* **Extensive Experiments.** The author has designed a variety of experiments to demonstrate the effectiveness and efficiency of their methods.
* **Well-Organized Representation.** The paper is well-structured, and the theoretical analysis provides strong support for the proposed methods.

weaknesses:
However, the paper also has some weaknesses, outlined as follows:

* **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.
* **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.
* **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)?
* **Parameter Analysis.** Given that your method is based on multi-hop common neighbors, analyzing parameters across different multi-hop settings could better validate the robustness of your model.

[1] Co-Neighbor Encoding Schema: A Light-cost Structure Encoding Method for Dynamic Link Prediction, KDD 2024.

questions:
Q1: In what ways does your approach build upon or differ from existing methods that also extract common neighbors in temporal graphs?

Q2: Can you clarify the importance of including static baselines in your experiments, and how their absence affects the interpretation of your results?

Q3: What specific case studies can you provide to illustrate the practical application and effectiveness of your proposed method?

Q4: Can you provide a detailed explanation of the notation used in your equations, particularly regarding $emb$ in Equation 2, and how this impacts the overall methodology?

Q5: How do you plan to conduct a thorough parameter analysis for the multi-hop common neighbors, and what insights do you anticipate this will provide regarding your model's robustness?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730379901798

thread_type:
official_review

<thread_object>
creator: reviewer_bfz2

<content>
summary:
This paper proposes a method for link prediction on continuous-time dynamic graphs (CTDGs), aiming to unify two prominent model families: memory-based models and neighbor-based models. The authors introduce TNCN, demonstrating experimentally that it performs better in certain configurations and is more efficient than existing models in the literature.

strengths:
- **Evaluation**: The proposed model is evaluated on established benchmarks, enhancing the reliability of the results.

- **Engineering**: The paper introduces an engineering approach to combine common neighbor (CN) techniques with memory-based methods, integrating these two modeling approaches.

weaknesses:
**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.

**Limited Novelty**: The proposed model's core components primarily consist of established techniques. For instance, the memory-based module closely resembles TGN, lacking additional innovations or a clear positioning relative to other memory-based approaches. Similarly, while TNCN incorporates common neighbor (CN) techniques with optimized computation, it employs multi-hop methods similar to those in models like CAWN, further limiting its novelty. 

**Theoretical Claims**: The paper presents familiar results as novel contributions, such as the $O(∣E∣)$ memory complexity for event aggregation, along with upper and lower bounds that are established in prior work (e.g., Caen, 1998). Presenting these as new theoretical results may be misleading.

The paper exhibits strong engineering but lacks clear new contributions. Theoretical results on memory complexity and specific experimental results are weak, with minimal performance gains in dynamic link prediction tasks. Given the limitations in presentation, contribution, and experimental validation, I recommend rejection.

**Experimental results**: While combining memory and neighbor-based methods is interesting, the observed performance gains are minimal, with certain results (e.g., in Table 5) showing limited improvement using unclear metrics (possibly AUC or AP).

questions:
1. Could you clarify the main novelty of your memory-based module and its differentiation from TGN?
2. What is the specific metric used in Table 5? Understanding whether it's AUC or AP is essential for interpreting the results.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730453218684

thread_type:
official_review

<thread_object>
creator: reviewer_2n9e

<content>
summary:
This work proposes TNCN, which is  a temporal version of NCN based on a memory-based backbone. Comprosing with three key parts: the memory module,the temporal CN extractor,,and the NCN-based prediction head, TNCN improves the performance in terms of efficiency and effectiveness. Comparing with a diverse set of baseline models, the experiments on five datasets demonstrate its outstanding performance.

strengths:
1. The experiments is substantial and the result is good.  Comparing with 9 baseline models, TNCN performs best on three of the five selected datasets, which emphasizes its effectiveness.
2. The method section is clearly described using formulas. With clear definition and detailed formulas, the method is well-presented.
3. There are proofs on the theorems in appendix, which improves the professionalism of the paper.

weaknesses:
1. Since the process is relatively complicated, it is recommended to provide a pseudo code to make it easier for readers to understand.
2. I suggest that the experimental part be supplemented with an analysis of the hyperparameters, which can make the values of the hyperparameters more reasonable.

questions:
1. High surprings 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?
2. Why is the result of TNCN-0∼2-hop-CN lower than TNCN-0∼1-hop-CN on the commen dataset in Table 2, which is different from the other three datasets?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732209161361

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Response

comment:
We have revised our paper in the following aspects, which are marked in blue fonts: 
1. Clarify the notation and transformation from node memory to embedding in section 4;
2. Add some parameter analysis in  Appendix C;
3. Attach pseudocode in Appendix E;
4. Add realistic case studies in Appendix G;
5. Add a comparison table between TNCN and NCN in section 4;
6. Complement contemporary work in related work;
7. Slightly modify some parts in abstract and description of Theorem 5.6.

We further address each reviewer's comments below.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732500688905

thread_type:
official_comment

<thread_object>
creator: area_chair_khkd

<content>
title:
Please reply to the authors' response.

comment:
Dear reviewers,

The ICLR author discussion phase is ending soon. Could you please review the authors' responses and take the necessary actions? Feel free to ask additional questions during the discussion. If the authors address your concerns, kindly acknowledge their response and update your assessment as appropriate.


Best,
AC
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes TNCN, a temporal version of Neural Common Neighbor (NCN) for link prediction in temporal graphs. The paper demonstrates significant improvements in performance and efficiency, with TNCN outperforming popular GNN baselines and showing excellent scalability on large datasets.  However, some reviewers found the presentation misleading regarding the novelty of the method, and the core components of TNCN were seen as incremental rather than groundbreaking. Additionally, the performance gains were minimal on certain datasets, and there were concerns about presenting well-known results as novel contributions.

Despite these efforts, the concerns raised by some reviewer, particularly regarding the limited novelty and the misleading presentation, remain valid. Therefore, I recommend a reject for this paper.