Node Duplication Improves Cold-start Link Prediction

W1: The primary concern of this paper is its limited novelty. The main idea of duplicating cold nodes is not a novel strategy within existing GNN frameworks. Additionally, the distinction between NodeDup and the common data pre-processing step of adding self-loops is not clear. When adopting general message passing GNNs, isolated nodes can also treat themselves as neighbors and update node representations using both $\boldsymbol{W}\_1$ and $\boldsymbol{W}\_2$. Without a clear differentiation, it is challenging to justify the novelty of NodeDup over existing techniques.

W2: It is unclear why such a simple strategy significantly enhances overall GNN performance on warm nodes, particularly on the citeseer dataset, which contains a large number of isolated nodes with zero degrees. Consider an example in online social networks, where a node $u$ represents a famous individual with millions of followers, and most of $u$’s followers may have few connections with other users, serving as cold nodes. In this scenario, adding self-loops using NodeDup(L) on these cold nodes may introduce additional noise in predicting the warm node $u$. This could potentially degrade the model's performance rather than improve it.

W3: Additional theoretical analysis from a spectral perspective, such as examining changes in the graph Laplacian after self-augmentation, could enhance the understanding of the self-augmentation strategy. Such analysis might provide deeper insights into why and how the self-augmentation strategy works, potentially revealing underlying mechanisms that contribute to its effectiveness or limitations.

W4: More experiments on larger datasets, such as collab, ppa, and citation2 from the OGB benchmark datasets [R1], should be included in the main text. The current experimental setup may not be sufficient to generalize the findings across different types of graphs and scales. Including these larger datasets would provide a more comprehensive evaluation of the method scalability and robustness. Additionally, a comparison between NODEDUP and more recent link prediction models, such as MPLP [R2], is necessary.

[R1] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta and J. Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. 2020. NeurIPS(33): 22118-22133.

[R2] K. Dong, Z. Guo, N. V. Chawla. Pure Message Passing Can Estimate Common Neighbor for Link Prediction. arXiv:2309.00976.

1. The problem addressed in this paper does not align with the experimental datasets used. The cold start issue is a significant challenge in recommendation systems, and while the authors frequently mention the intent to tackle this problem, they rely on publicly available general graph datasets, such as citation networks, for their experiments. Crucially, they do not utilize any recommendation system datasets, such as Movielens-1M or Amazon-Books.

2. The work lacks theoretical guarantees. Although the authors attempt to explain in Section 3.2 how node duplication aids cold start link prediction, I would prefer to see definitive theorems or lemmas presented in the paper. This would provide a more solid theoretical foundation for the work.

3. In Table 18, GCN+NodeDup shows a decline in overall metrics compared to GCN. What is the reason for this phenomenon?

4. There are several works designed to solve link prediction problems using GNN methods, such as references [1], [2], and [3]. However, the authors do not compare NodeDup against these methods in their experiments.

5. The method description lacks clarity. In the NodeDup approach, determining which nodes are cold starts is a crucial step. However, in the core algorithm (Algorithm 1), the authors do not demonstrate how to deterministically obtain the set of cold start nodes V_{cold}.

6. The authors should provide a direct comparison with adding self-loops as an augmentation baseline is missing, which could help clarify the advantages of NodeDup and NodeDup(L) over simpler alternatives.

7. The authors state that OGB datasets were not used because they ``lack a substantial number of isolated or low-degree nodes'' (Lines 892-893). However, even though OGB datasets may primarily include high-degree nodes, they still contain a subset of lower-degree nodes, which would allow for a relevant evaluation of the proposed method's performance across both node types. Additionally, testing on these datasets could strengthen the claim that the method does not compromise warm node performance, as OGB is a widely recognized benchmark.

[1] Bai Q, et al. HGWaveNet: A Hyperbolic Graph Neural Network for Temporal Link Prediction. WWW-23.

[2] Zhu Z, et al. Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. NeurIPS-21.

[3] Cai L, et al. Line Graph Neural Networks for Link Prediction. TPAMI-21.

While NODEDUP demonstrates effectiveness in addressing the cold-start link prediction problem, several critical limitations should be considered:

1. Limited Scalability:

   NODEDUP's design focuses heavily on the "duplication of cold nodes," making it overly specialized for the cold-start problem and potentially too simple for broader link prediction tasks. The technique lacks flexibility to handle other challenges, such as heterophilic graphs or highly dynamic networks, which require adaptable augmentation strategies. This limits NODEDUP’s versatility as a universal approach in graph contrastive learning.

2. Lack of Theoretical Foundation:

   Despite extensive empirical results, the paper does not provide a theoretical explanation for why NODEDUP improves cold-node representation. A theoretical analysis would strengthen the validity and interpretability of the method, clarifying how and why node duplication facilitates performance gains for cold nodes in GNNs.

3. Outdated Baselines:

   Although the authors claim that NODEDUP does not compromise overall performance while addressing the cold-start problem, they compare it only against older baselines rather than the latest advancements in graph contrastive learning. This raises questions about how NODEDUP’s performance aligns with state-of-the-art methods and whether it may lag behind the latest graph contrastive learning approaches in overall link prediction performance.

4. High Dependency on Hyperparameters:

   The proposed NODEDUP method relies heavily on the selection of the hyperparameter δ, which determines the distinction between cold and warm nodes. Although the authors provide a heuristic method and a hyperparameter search experiment, they do not offer a clear rationale for selecting a specific value of δ. This raises concerns that an optimal δ may need to be tuned individually for each dataset, potentially limiting the method’s practical applicability and generalizability.

The paper appears to lack sufficient novelty in its contributions to the field of link prediction. The underlying idea of augmenting data through duplication has been explored in various contexts. Additionally, the paper does not convincingly demonstrate how NodeDup outperforms or fundamentally enhances prior methods, leading to concerns about the overall impact of the contribution.

Although the paper provides some justification for the proposed method, it could delve deeper into the theoretical foundations of why node duplication is particularly effective for cold-start link prediction. More comprehensive discussions could help solidify the rationale behind the approach.

The paper lacks a thorough investigation into the node degree distribution of the graphs used in the experiments, which can significantly impact the efficiency of the proposed method. In cases where the graph exhibits a highly skewed degree distribution, the additional complexity introduced by duplicating cold-start nodes could potentially lead to a doubling of the original computational complexity.