Node Duplication Improves Cold-start Link Prediction
Authors: Zhichun Guo
Tong Zhao
Yozen Liu
Kaiwen Dong
William Shiao
Mingxuan Ju
Neil Shah
Nitesh V Chawla
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) are prominent in graph machine learning and have shown state-of-the-art performance in Link Prediction (LP) tasks. Nonetheless, recent studies show that GNNs struggle to produce good results on low-degree nodes despite their overall strong performance. In practical applications of LP, like recommendation systems, improving performance on low-degree nodes is critical, as it amounts to tackling the cold-start problem of improving the experiences of users with few observed interactions. In this paper, we investigate improving GNNs' LP performance on low-degree nodes while preserving their performance on high-degree nodes and propose a simple yet surprisingly effective augmentation technique called NodeDup. Specifically, NodeDup duplicates low-degree nodes and creates links between nodes and their own duplicates before following the standard supervised LP training scheme. By leveraging a ``multi-view'' perspective for low-degree nodes, NodeDup shows significant LP performance improvements on low-degree nodes without compromising any performance on high-degree nodes. Additionally, as a plug-and-play augmentation module, NodeDup can be easily applied on existing GNNs with very light computational cost. Extensive experiments show that NodeDup achieves 38.49%, 13.34%, and 6.76% relative improvements on isolated, low-degree, and warm nodes, respectively, on average across all datasets compared to GNNs and the existing cold-start methods.

Published in Transactions on Machine Learning Research (08/2025)
Node Duplication Improves Cold-start Link Prediction
Zhichun Guo' Tong Zhao? Yozen Liu? Kaiwen Dong William Shiao*
Mingxuan Ju?
Neil Shah? Nitesh V. Chawla²
University of Washington Snap Inc. 3 UUniveriity of Notre Dame
University of California, Riverside
Reviewed on OpenReview: https: // openreview. net/ forum? id- h10
Abstract
Graph Neural Networks (GNNs) are prominent in graph machine learning and have shown state-of-the--at performance in Link Prediction (LP) tasks. Nonetheless, recent studies show that GNNs struggle to produce good results on low-degree nodes despite their overall strong performance. In practical applications of LP, like recommendation systems, improving performance on low-degrec nodes is critical, as it amounts to tackling the cold-start problem of improving the experiences of users with few observed interactions. In this paper, we investigate improving GNNs LP performance low-degree nodes while preserving their performance on high-degree nodes and propose simple yet surprisingly effective augmentation technique called NODEDUP. Specifically, NODEDUP duplicates low-degree nodes and creates links between nodes and their own duplicates before following the standard supervised I.P training scheme. By leveraging a "multi-view" perspective for low-degree nodes, NODEDUP shows significant LP performance improvements on low-degroe nodes without compromising any performance on high-degree nodes. Additionally, as a alug-and-play augmentation module, NODEDUP be easily applied on existing GNNs with very light computational cost. Extensive experiments show that NODEDUP achieves 38.49%, 13.34%, and 6.76% relative improvements on isolated, low-degree, and warm nodes, respectively, on average across all datasets compared to GNNs and the existing cold-start methods.
1 Introduction
Link prediction (LP) is fundamental task of graph-structured data (Liben-Nowell & Kleinberg, 2007; Trouillon et al., 2016), which aims to predict the likelihood of the links existing between two nodes in the network. It has wide-ranging worldworld applications across different domains, such as friend recommendations in social media (Sankar et al., 2021; Tang et al., 2022; Fan et al., 2022), product recommendations in o-commerce platforms (Ying al., 2018; He al., 2020), knowledge graph completion (Li al., 2023; Vashishth et al., 2020; Zhang al., 2020), and chemical interaction prediction (Stanfield et. al., 2017; Kovács et al., 2019; Yang et al., 2021).
120
400
In recent years, graph neural networks (GNNs) (Kipf & Welling, 2016a; Veličković et al., 2017; Hamilton et al., 2017) have been widely applied to LP, and a scries of cutting-edge models have been proposed (Zhang & Chen, 2018; Zhang al., 2021; Zhu al., 2021; Zhao et al., 2022b). Most GNNs follow messago-passingg scheme (Gilmer et al., 2017) in which information is it- eratively aggregated from neighbors and used to update node representations accordingly. Consequently, the suc- cess of GNNs usually heavily relics on having sufficient high-quality neighbors for each node (Zheng et al., 2021; Liu et al., 2021). However, real-world graphs often ex- hibit long-tailed distribution in terms of node degrees,
Hits@ 10
100
Avg. Hits@1 10
350
Nodes
300
His@
250
Nodes
60
200
150
100
0
0
1
4
7
10
Node Degree
Figure 1: Node Degree Distribution and LP Per- formance (GSage encoder and inner product as decoder) Distribution w.r.t Nodes Degrees showing reverse trends on Citeseer dataset.
* CCorresoonds acguo

---

Published in Transactions on Machine Learning Research (08/2025)
where significant fraction of nodes have very few neighbors (Tang et al., 2020b; Ding et al., 2021; Hao et al., 2021). For example, Figure 1 shows the long-tailed degree distribution of the Citeseer dataset. Moreover, LP performances w.r.t. node degrees on this dataset also clearly indicate that GNNss struggle to generate satisfactory results for nodes with low or zero degrees. For simplicity, in this paper, we refer to the nodes with low or zero degrees as cold nodes and the nodes with higher degrees as warm nodes.
To boost GNNs' performance on cold nodes, recent studies have proposed various training strategies (Liu et al., 2020; 2021: Zheng et al., 2021; Hu et al., 2022) and augmentation strategies (Hu et al., 2022; Rong et al., 2019; Zhao et al,, 2022b) to improve representation learning quality. For instance, ColdBrew (Zheng et al., 2021) posits that training a powerful MLP can rediscover missing neighbor information for cold nodes; TailGNN (Liu et al., 2021) utilizes a cold-node-specific module to accomplish the same objective. However, such advanced training strategies (e.g., ColdBrew and TaiGGNN) share a notable drawback: they are trained with a. bias towards cold nodes, which then sacrifices performance on warm nodes (empirically validated in Table 1). However, in real-world applications, both cold nodes and warm nodes are critical (Clausct et al., 2009). On the other hand, while augmentation methods such as LAGNN (Liu et al., 2022b) do not have such bias, they primarily focus improving the overall performance of GNNs in LP tasks, which may be dominated by warm nodes due to their higher connectivity. Additionally, the augmentation methods usually introduce a significant amount of extra computational costs (empirically validated in Figure 8). In light of the existing work discussed above on improving LP performance for cold nodes, we are naturally motivated to explore the following crucial but rather unexplored research question:
Can we improve LP performance on cold nodes without compromising warm node performance?
We observe that cold node LP performance usually sulfers because they are under-represented in standard supervised LP training due to their few (if any) connections. Given this observation, in this work, we introduce a simple yet effective augmentation method, NODEDUP, for improving LP performance on cold nodes. Specifically, NODEDUP duplicates cold nodes and establishes edges between each original cold node and its corresponding duplicate. Subsequently, we conduct standard supervised end-to-end training of GNNs on the augmented graph. To better understand why NODEDUP is able to improve LP performance for cold nodes, thoroughly analyze it from multiple perspectives, during which we discover that this simple technique effectively offers "muult-viiw" perspective of cold nodes during training. This "multi-view" perspective of the cold nodes acts similarly to an ensemble and drives performance improvements for these nodes. Additionally, our straight forward augmentation method provides valuable supervised training signals for cold nodes and especially isolated nodes. Furthermore, we also introduce NODEDUP(L), a lightweight variation of NODEDUP that adds only self-loop edges into training edges for cold nodes. NODEDUP(L) empirically offers up to a 1.3x speedup over NODEDUP for the training process and achieves significant speedup over existing augmentation baselines. In our experiments, we comprehensively evaluate our method seven benchmark datasets. Compared to GNNs and the existing cold-start methods, NODEDUP achieves 38.49%, 13.34%, and 6.76% relative improvements on isolated, low-degroe, and warm nodes, respectively, on average across all datasets. NODEDUP also greatly outperforms augmentation baselines on cold nodes, with comparable warm node performance. Finally, as plug-and-play augmentation methods, our methods are versatile and effective with different LP encoders/ encoders/decoder:. deeoders. They also achieve significant performance in a more realistic inductive setting. Our code can be found at bttps://githuu com/zhi Bethiiihunguooooooeeee
2 Preliminaries
Notation, Let an attributed graph be G EV,E, X}. where V is the set of N nodes and E C V x V is the odges where each evu E indicates nodes v and u are linked. Let X E NxF be the node attribute matrix, where F is the attribute dimension. Let Ng be the set of neighbors of node v, i.e., Nr = {uleru E E), and the degree of node e is W.] We separate the set of nodes V into three disjoint sets Visa: Viow, and Vuarm by their degrees based on the threshold hyperparameter 8", For each node E V, E Vieo if [AG] O; u E Viow if 0 < [No] < 6; V E V Vwarm if [. > 8. For case of notation, we also use Veold = Viso U Viow to denote the cold nodes, which is the union of Isolated and Low-degree nodes.
This threshold is set as 2 our experiments, based on observed performance gaps LP on various datasets, as shown in Figure and Figure 10. Further reasons for this threshold are detailed Appendix C.1.
2

---

Published in Transactions on Machine Learning Research (08/2025)
LP with GNNs. In this work, we follow the commonly-used encoder-decoder framework for GNN-based LP (Kipl& & Welling, 2016b; Berg et al., 2017; Schlichtkrull et al., 2018; Ying et al., 2018; Davidson et al., 2018; Zhu et al., 2021; Yun et al., 2021; Zhao et al., 2022b), where a GNN encoder learns the node representations and the decoder prodicts the link existence probabilities given cach pair of node reprosentations. Most GNNs follow the message passing design (Gilmer et. al., 2017) that iteratively aggregale each node's neighbors' information to update its embeddings. Without the loss of generality, for each node v, the I-th layer of a GNN can be defined as
h = UPDATE(h!")) 11-1), " mm--)) s.tt m AGG AGG((M Vu E No);
(1)
where h is the I-th layer's output reprosentation of node U, ( = I., AGG(.) is the (typically permutation- invariant) aggregation function, and UPDATE(.) is the update function that combines node v's neighbor embedding and its own embedding from the previous layer. For any node pair v and u, the decoding process can be defined as Pon- a (DECODER(H., hw)), where h, is the GNN's output representation for node v and is the Sigmoid function. Following existing literature, we use inner product (Wang et al., 2021; Zheng et al., 2021) as the default DECODER.
The standard supervised LP training optimizes model parameters w.r.t. a training set, which is usually the union of all observed M edges and KM no-edge node pairs (as training with all O(N2) no-edges is infeasible in practice), where K is the negative sampling rate (K = 1 usually). We use y = {0, 1 M+KM to denote the training set labels, where you = 1 if Cvw E E and otherwisc.
The Cold-Start Problem. The cold-start problem is prevalent in various domains and scenarios. In recommendation systems (Chen et al., 2020; Lu et al., 2020; Hao et al., 2021; Zhu et al, 2019; Volkovs et al., 2017; Liu & Zheng, 2020), cold-start refers to the lack of sufficient interaction history for new users or items, which makes it challenging lo provide accurate recommendattonns Similarly, in the context of GNNs, the cold-start problem refers to performance in tasks involving cold nodes, which have few or no neighbors in the graph. As illustrated in Figure 1, GNNs usually struggle with cold nodes LP tasks due to unreliable or missing neighbors' information. In this work, we focus on enhancing LP performance for cold nodes, specifically predicting the presence of links between cold node Veold and target node u E V (w. (w.l.ogg.). Additionally, we aim to maintain satisfactory LP performance for warm nodes. Prior studies on cold-start problems (Tang et al., 2020b; Liu et al., 2021; Zheng et al., 2021) inspired this rescarch direction.
3 Node Duplication to Improve Cold-start Performance
As described in Section 2, a model will not see an isolated node unless it is randomly sampled as a negative training edge for another node in standard supervised T.P training. In the same vein, all the cold nodes are strongly underrepresented in the I.P training, given their few or even no directly connected neighbors. In light of such observations, our proposed augmen- tation technique is simple: we duplicate under-represented cold nodes. By both training and aggregating with the edges connecting the cold nodes with their dupli- cations, cold nodes are able to gain better visibility in the training process, which al- lows the GNN-based LP models to learn better representations. In this section, we introduce NODEDUP in detail, followed by comprehensive analyses of why it works from different. perspectives.
Algorithm 1: NODEDUP.
Require: Craph G = (V, E, X). Supervision V, AGG, UPDATE, GNNs Layer L, DECODER, Supervised loss function Loup.
1: # Augment the graph by duplicating cold-start nodes Venta-
2: Identify cold node set Veoid based the node degree.
3: (Step 1) Duplicate all cold nodes generate the augmented node set
V VCoolold whose node feature matrix then X' R
4: (Step IT) Add an edge between each cold node E Veold and its duplication v', then get the augmented edge set.
el = &U (eeer : E Venta).
5: (Step III) Add the augmented edges into the training set and get
y' = yo (B.. = 1 : E Veola).
6: (Step IV) # End-to-end supervised training based on the augmented graph G' = "V",'',
7: for -= 1 to L do
8:
for v in V do
9: N 1((41) = UPDATT (M (0) AGG((I!))) (ACPDAATT vew E EE')
10: end for
11: end for
12: for (i,j) in y" do
13: 81 = = (DECOODER(MM)))
14: end for
15: Loss Enseey Coup (ily vis)
3

---

Published in Transactions on Machine Learning Research (08/2025)
3.1 Proposed Method
We summariie the entire process of NODEDUP in Algorithm 1, where the key steps are broken down into four simple stages: Step I: Duplicate all cold nodes to generate the augmented node set V= VUUVe whose node feature matrix is then X' E [N(N+IVeoaa)>xF, Step II: For each cold node E Voold and its duplication v', add an edge between them and get the augmented edge set E' = E U fere' V' E Voold?; Step III: Include the augmented edges into the training set and get y" = y U (Yeer = 1 : Ve E Veote); Step IV: Proceed with the standard supervised LP training on the augmented graph G' - ",,,'' with augmented training set yr, Based on extensive experimental analysis, we choose to duplicate code nodes once. The impact of both the type of duplicated nodes and the duplication frequency is further analyzed in Section 4.7.
Time Complexity. We discuss complexity of our method in terms of the training process on the augmented graph. We use GSage (Hamilton et al., 2017) and inner product decoder as the default architecture when demonstrating the following complexity (w.l.o.g). With the augmented graph, GSage has a complexity of ON + (Vootal) where R represents the number of sampled neighbors for each node, L is the number of GSage layers (Wu et al., 2020), and D denotes the size of node representations. In comparison to the non-augmented graph, NODEDUP introduces an extra time complexity of O (Vetal)D))) For the inner product decoder, we incorporate additionally [Vontll positive edges and also sample [Vestal negative edges into the training process, resulting in the extra time complexity of the decoder as O(Veols)))) Given that all cold nodes have few (R S 2 in our experiments) neighbors, and GSage is also always shallow (so T. is small) (Zhao & Akoglu, 2019), the overall extra complexity introduced by NODEDUP is O([Vooia) |Vootd D).
3.2 How does Node Duplication Help Cold-start LP?
In this subsection, we analyze how such a simple method can improve cold-start LP from two perspectives: the neighborhood aggregation in GNNs and the supervision signal during training, in comparison to self-loops in GNNs (c.g., the additional self-connection in the normalized adjacency matrix by GCN).
Aggregation. As described in Equation (1); when UPDATE(-) and AGG(-) do not share the transforma- tion for node features, GNNs would have separate weights for self-representation and neighbor represen- tations, as shown in Figure 2. The separate weights enable the neighbors and the node itself to play dis- tinct roles in the UPDATE step. By leveraging this property, with NODEDUP, the model can leverage the two "views" for each node: first, the existing view is when node is regarded as the anchor node during message passing, and the additional view is when that node is regarded as one of its neigh- bors thanks to the duplicated node from NODEDUP. Taking the official PyG (Fey & Lensssn, 2019) implementation of GSage (Hamilton et al., 2017) as an example, it updates node representations using h w,k!" + Wym!!" Here, W1 and W2 correspond to the self-reprrsentationn and neighbors' represen- tations, respectively. Without NODEDUP, isolated nodes Viso have no neighbors. Thus, the representations of all Viso are only updated by h! (1+1) Wi With Step II in NODEDUP, the updating process for isolated node v becomes h ([+1)
GNN with Self-loop
Node
NodeDup((solated)
W2
W
W2
W
W Leechh
W
W
W2
Cold Node
Self Aggregation
Augmented Neighbor Aggregation
Duplicated Cold Node
Neighbor Aggregation
Figure 2:
Comparison of aggregation mechanisms: GNN with Self-loop, NODEDUP for Low-degree nodes, and NODEDUP for Isolated nodes.
Win (0) + Wzh = (W₂ + !2) It indicates that W₂ is also incorporated into the node updating process for isolated nodes, which offers an additional perspective for isolated nodes' representation learning. Similarly, GAT (Veličković et al., 2017) updates node representations exp(LeakyReLLU(
with h
((+1) Oh EuEN, Oh. (1) where Own Eiexcu exp(LeakyRLLU(( |e^! (en""i)"""))"
Attention
scores in partially correspond to the self-reprrsontatioon h and partially to neighbors' representation h.. In this case, neighbor information offers a different perspective compared to sell-representationn Such "multi-view" enriches the representations learned for the isolated nodes in a similar way to how ensemble methods work (Allen-Zhu & Li, 2020). Apart from addressing isolated nodes, the same mechanism and multi-view perspective also apply to Low-degree nodes.
4

---

Published in Transactions on Machine Learning Research (08/2025)
Self-distillation
graph duplication
NodeDup
G Graph Learned by Teacher GNN
KD|
Student GNN SP
SP !
SP
Go: Original Graph
Student GNN
GNN
GNN
KD: knowledge distillation
SP: supervised training
Figure Comparing NODEDUP coff-disillattin. training the student GNN on an augmented graph, which combines G G³, and edges connecting corresponding nodes in the two graphs. This process be further improved by replacing G with Go to explore the whole graph duplication. NODEDUP is a lightweight variation of it.
The self-distillation process can be approximated by
Supervision. In LP tasks, edges not only facilitate aggre- gation but also act as positive supervised training signals,
GNN with Self-loop
NodeDup
NodaDup((solated)
as depicted Figure Cold nodes, which typically have few no positive training edges, are particularly sus- ceptible to out-of-distribation (OOD) issucs (Wu et al., 2022), especially in the case of Isolated nodes. Unlike normal self-loops and the self-loops introduced in previous works (Cai et al., 2019; Wang et al., 2020), where self-loops are solely for aggregation, the edges added by NODEDUP Figure 3: Comparison of supervision mechanisms.
Cold Node
Positive Supervision
Duplicated Cold Node
..... Augmented Positive Supervision
also serve as positive supervision signals for cold nodes through Step III of Algorithm By leveraging these additional signals, cold nodes can learn more robust and higher quality embeddings, ultimately improving their performance in LP tasks.
Figure 4 shows ablation study these two designs where NODEDUP w/o Step III indicates only using the augmented nodes and edges in aggregation but not supervision; NODEDUP w/o Step II indicates only using the augmented edges in supervision but not aggregation. We can observe that using augmented nodes and edges either in pervision aggregation
Ablation Study,
100
D GSage
D NodeDup w/o Step III Node wlo Step
Hits@10 10
80
NodeDup
40
significantly improve the LP performance on Isolated nodes. By combin- ing them, NODEDUP results in larger improvements. Besides, NODEDUP also achieves improvements on Low-degree nodes while not sacrificing the perfor- mance Warm nodes.
Isolated
Low-degree
Warm
Overall
Figure 4: Ablation study of NODEDUP on Physics. Both Step 1l and Step III, introduced in Algorithm 1, play an important role in performance improvements of NODEDUP.
3.3 Further Insight: Understanding NodeDup through Self-distillation
As introduced in Section 3.2, the effectiveness of NODEDUP arises from leveraging diverse perspectives signals obtained during both the aggregation and supervision steps. Allen-Zhu & Li (2020) showed that the success of sell-distillation, similar to our method, contributes to ensemble learning by providing models with different perspectives on the knowledge. Building on this insight, we show an interesting interpretation of NODEDUP, positioning it as a simplified and enhanced adaptation of self-distillation for LP tasks for cold nodes, as illustrated Figure 5, in which we draw a connection between self-distillation and NODEDUP.
5

---

Published in Transactions on Machine Learning Research (08/2025)
In self-distillation, teacher GNN is first trained to learn the node representations H' from original features X through supervised training for LP tasks on the original graph. We denote the original graph as Go and we denote the graph, where we replace the node features G with H", as G Figure The student GNN is then initialized with random parameters and trained with the sum of two loss func- tions: LSD Ler + LKD, where Lsp denotes the supervised training loss with Go and LKD denotes the knowledge distillation loss with G Figure shows that delf-disiillation outperforms the teacher GNN across all scttings.
100
O Teacher GNN
8 Self-ditillation
Whole Graph Dup.
Hits@10
NodeDup
60
40
Isolated
Low-degree
Warm
Overall
Figure 6: Performance with different training strate- gies introduced in Figure 5 on Citeseer. NODEDUP achieves better performance across all settings.
The effect of LKD is similar to that of creating an additional link connecting nodes in Go to their corresponding nodes in G when optimizing with Csp. This is illustrated by the red dashed line in Figure 5. For better clarity, we show the similarities between these two when we use the inner product as the decoder for LP with the following example. Given a node v with normalized teacher embedding he and normalized student embedding he, the additional loss term that would be added for distillation with cosine similarity is LKD = - Evey h. h:. On the other hand, for the dashed line edges in Figure 5, we add an edge between the node v and its corresponding node v' in G" with embedding he When trained with an inner product decoder and binary cross-entropy loss, it results in the following: LSP - Σ You log(h, h², (1 Uve') log(1 h, ht,)). Since always add the edge (v,0"), we know you! and simplify the loss follows: Lsp - N Σ log(h, h².). Here, we can observe that LKD and Lsp are positively correlated log(-) is monotonically increasing function.
To further improve this step and mitigate potential noise in G we explore a whole graph duplication technique, where G replaced with an exact duplicate of Go to train the student GNN. The results Figure demonstrate significant performance enhancement achieved by whole graph duplication compared to self-distillation. NODEDUP is lightweight variation of the whole graph duplication technique, which focuses duplicating only the cold nodes and adding edges connecting them their duplicates. From the results, it is evident. that NodeDup consistently outperforms the teacher GNN and self-distillation in all scenarios. Additionally, NODEDUP exhibits superior performance on isolated nodes and is much more efficient compared to the whole graph duplication approach.
3.4 NodeDup(L): An Efficient Variant of NodeDup
Inspired by the above analysis, further introduce lightweight variant of NODEDUP for better efficiency, NODEDUP(L). To provide above-described "multi-view" information as well as the supervision signals for cold nodes, NODEDUP(L) simply add additional self-loop edges for the cold nodes into the edge set E, that is, E' = & (eve Ve E Veota)- During aggregation, NODEDUP(L.) intentionally incorporales the self-representation h into the aggregated neighbors' representation m!! through these additional edges, This allows the weight matrix W2 to provide an extra "view" of h when updating
Aggregation
Supervision
W
W
W
W2
Cold Node
Self Aggregation
Neighbor Aggregation
Positive Supervision
Augmented Neighbor Aggregation
Augmented Positive Supervision
h (!+1) For supervision, the added edges also serve positive training samples for cold nodes. As demonstrated in Figure 7, NODEDUP(L) preserves the two essential designs of NODEDUP while avoiding the addition of extra nodes, which further saves time and space complexity. Morcover, NODEDUP differs from NODEDUP(L) since cach duplicated node in NODEDUP will provide another view for itself because of dropout layers, which leads different. performance shown in Section 4.2.
Figure 7: Aggregation and supervision mechanisms of NODEDUP(L.).

---

Published in Transactions on Machine Learning Research (08/2025)
4 Experiments
4.1 Experimental Settings
Datascts and Evaluation Settings. We conduct experiments on 7 benchmark datasets: Cora, Citeseer, CS, Physics, Computers, Photos and IGB-100K, with their details specified in Appendix B. We randomly split edges into training, validation, and testing sets. We allocated 10% for validation and 40% for testing in Computers and Photos, 5%/109 for testing in IGB-100K, and 10%/20% in other datasets. We follow the standard evaluation metrics used in the Open Graph Benchmark (Hu el al., 2020) for LP, in which we rank missing references higher than 500 negative reference candidates for each node. The negative references are randomly sampled from nodes not connected to the source node. We use Hits@10 as the main evaluation metric (Han et al., 2022). We follow Guo et al. (2022) and Shiao et al. (2022) for the inductive settings, where new nodes appear after the training process. Additionally, results for large-scale datasets and heterophilic graphs are presented in Appendix C.3 and Appendix C.4.
Baselines. Both NODEDUP and NODEDUP(L) are flexible to integrate with different GNN encoder architectures and LP decoders. For our experiments, we use GSage (Hamilton et al., 2017) encoder and the inner product decoder as the default base LP model. To comprehensively evaluate our work, we compare NODEDUP against three calegories of baselines. (1) Base LP models.
(2) Cold-start methods: TailGNN (Liu et al., 2021) and Cold-brew (Zheng et al., 2021) primarily aim to enhance the performance on cold nodes. We also compared with Imbalance (Lin et al., 2017), viewing cold nodes as an issuc of the imbalance concerning node degrecs.
(3) Graph data augmentation methods: Augmentation frameworks inchuding DropEdge (Rong et al., 2019), UP (Hu et al., 2022), and LAGNN (Liu et al., 2022b) typically improve the performance while introducing additional preprocessing or training time. Performance comparisons with heuristic methods and additional cold-start methods (c.g. Upsampling, DegFairGNN (Liu et al., 2023), SAILOR (Liao et al., 2023) and GRADE (Wang et al., 2022)) are in Appendix C.6 and Appendix C.7.
4.2 Performance Compared to Base GNN LP Models
Isolated and Low-degree Nodes. We compare our methods with base GNN LP models that consist of a GNN encoder in conjunction with an inner product decoder and are trained with a supervised loss. From Table 1, we observe consistent improvements for both NODEDUP(L) and NODEDUP over the base GSage model across all datasets, particularly in the Isolated and Low-degree node settings. Notably, in the Isolated sctting, NODEDUP achieves an impressive 29.6% improvement, on average, across all datasots. These findings provide clear evidence that our methods effectively address the issue of sub-optimal LP performance on cold nodes.
Warm Nodes and Overall. It is encouraging to see that NODEDUP(L.) consistently outperforms GSage across all the datasets in the Warm nodes and Overall settings. NODEDUP also outperforms GSage in 13 out of 14 cases under both settings. These findings support the notion that our methods can effectively maintain and enhance the performance of Warm nodes. Why? The superior performance on Warm nodes is directly tied to our focus on LP tasks, where we evaluate node pair outcomes. Given the substantial number of Warm-Cold node pairs under prediction, these outcomes contribute to the overall performance metrics for both Warm node prediction. Better learning of Cold nodes thus boosts Cold-Warm node pairs link prediction performance, which subsequently elevates the prediction accuracy for Warm nodes. A more detailed experimental analysis is provided in Section 4.8.
NodeDup vs. NodcDup(L). Furthermore, we observe that NODEDUP achieves greater improvements over NODEDUP(L) for Isolated nodes. However, NODEDUP(L) outperforms NODEDUP on 6 out of 7 dalasets for Warm nodes. The additional improvements achieved by NODEDUP for Isolated nodes can be attributed to the extra view provided cold nodes through node duplication during aggregation. On the other hand, the impact of node duplication on the original graph structure likely affects the performance of Warm nodes, which explains the superior performance of NODRDUP(T.) in this setting compared to NODEDUP.
7

---

Published in Transactions on Machine Learning Research (08/2025)
Table 1: Performance compared with base GNN and baselines for cold-start methods. The best result is bold, and the rumner-up is underlined. NO and NODEDUP(L) outperform GSage and cold-start baselines almost all the cases.
GSage
Imbalance
TailGNN
Cold-brew
NODEDUP(L)
NODEDUP
Isolated
32.201a
34.51 11.m
36.9511.a4
28
39.7611.a9
44.27
Low-degree
59.4511
59.4221.a1
31.35o
57.27
62.53 11.00
61.9811.14
Cora
Warm
61.14+0.76
59.54-0..4
61 +0.90
56.28+0.s1
62.07 +0.37
59.07
Overall
58.31 20 os
57.5520.07
59.02a..7
54.4420.5
60.49
20.00
58.9220.92
Isolated
47.13
26.26:2.aa
37.78::42s
52.46.1.14
1..64
Low-degree
61.881o.r
61.90.o.c0
22.06
29.12
73.71 11.22
75.50
Citeseer
Warm
71.45+0.8 sa
71.54=0.00
71.32
65. 63.12
74.99
74.68=0.07
Overall
63.7719.s3
63. 63..661..40
62.02. 02.0211.88
58.03
10.34
71.7310.47
Isolated
56.41+1.s:
60=1.00
55. 70+1.sa
57.70=o.s1
65. 68.184
65.87+1.10
Low-degree
25.
75. 25.53
73. 73.60
73.99+o..
81.46+00a7
81,12-o.56
CS
Warm
84.37
83.7020.4
79.8620.a5
78. 28.23
85.48
84.76g0.41
Overall
83.3310
82.56.0.10
79.05.0.a0
77.6320
84.90.0.00
84.2320:30
Isolated
47.41
55.01 20.88
52.54
24.38
65.04
66. 66.65.20.
Low-degree
79.31
29.50
75.95
75.8620.10
82.70
84.04
Physica
Warm
90.2810.2
89.8510.08
85.931n.40
78.4810.4
90.4410.23
90.33_o.ar
Overall
89.761..22
89.38 10.00
85.4810..8
78.3410.1
90.09 10.02
90.03 Lo.00
Isolated
9.32+1.44
10.14+a.a0
10.63+1.a9
9.75m1.4
17.11+
19.62+2.65
Low-degree
57.91
59.191..e
51. 21.11..8
49.0310
62. 022.441.00
61.16.0.9
Computers
Warm
66.87+0.47
65. 62.622
62.77+a.44
67.52+0.25
68 58.022+..4
68.10
Overall
60.67++.47
62.42.0.20
62.55++.4n
67.35+0.25
67 66
67.94+0.25
Isulated
9.25
10.80
13 13.62a1.00
12.86
21.50
17.8423.5
Low-degree
52.611o
20.57
42.75
43.1420.64
55.70.1.aa
54.13:3.56
Photos
Warm
67.64+0. ss
64.5 54.000
63
58. 25.0022..o 8o
$9.6820.59
08.66800.4
Overall
67.32 54
64. 24.2440.40
61. 20.77
57.77=0.00
69.40=00av
08.30=0.4s
Isolated
75.92 52
77.321o.ra
77.2910.44
82.31 1o.00
87.43.10.14
88.04
Low-degree
70.38+0.2s
79.19+0.00
80.57+a.114
83.84+0.1s
88.37 +0.24
88.98 +0.4
IGB-100K
Warm
86.4220.4 24
86.01
85.3520.10
82.442o
88.5410a
88.28 20.288...0
Overall
84.7720.2
84.4720.14
19.0....1
82.6820.17
88.47 19:09
88.39
4.3 Performance Compare to Cold-start Methods
Table 1 presents the LP performance of various cold-start baselincs. For both Isolated and Low-degree nodes, consistently observe subslantial improvements of our NODEDUP and NODEDUP(T.) methods compared to other cold-start basclines. Specifically, NODEDUP and (TD)DuP(L)) achieve 38.49% and 34.74% improvement for Isolated nodes on average across all datasets, respectively.
addition, our methods consistently outperform cold-start baselines for Warm nodes across all the datasets, where NODEDUP(L) and NODEDUP achieve 6.76% and 7.95% improvements on average, respectively. This shows that our methods can successfully overcome issues with degrading performance on Warm nodes in cold-start baselines. Further analyses with other cold-start methods and efficiency comparisons be found in Appendix C.7 and Appendix C.8.
4.4 Performance Compared to Augmentation Methods
Effectiveness Comparison. Since NODEDUP and NODEDUP(L) use graph data augmentation techniques, compare them to other data augmentation baselines. The performance and time consumption results for Citeseer, Physics, and IGB-100K are shown in Figure 8, with additional datasets in Appendix C.9 due to space constraints. From Figure 8, NODEDUP consistently outperforms all the graph augmentation basclines for Isolated and Low-degree nodes across all three datasets, while NODEDUP(L) outperforms baselines in 17/18 cases for Isolated and Low-degree nodes. Both NODEDUP and NODEDUP(T.) also perform on par or above baselines for Warm nodes.
Efficiency Comparison. Augmentation methods often come with the trade-off of adding additional run time before during model training. For example, LAGNN (Liu et al., 2022b) requires extra preprocessing
8

---

Published in Transactions on Machine Learning Research (08/2025)
GSage DrDroeeege
LOGNNNNN
TuneUp
esaNodeDup(L)
sua Nud
Hits@h11
Citeseer
Tima(s)
120
97-7
60
60
0.0
0.0 0.00.10 1.2
6.2 5.6.5699055.. 5.65.
Isolated
Low-degree
Warm
Overall
Preprocess
Train
Physics
400
Hits 10
80
Time(s)
196216
200
165173 73
60
40
0
Isolated
Low-degree
Warm
Overall
Preprocess
Train
90
1GB-100K
300
Hits
Timefs)
80
200
134128
12
100
86
70
Isolated
Low-degree
Warm
Overall
Preprocess
Train
Evaluated Nodes
Evaluated Time
Figure 8: Performance and runtime comparisons different augmentation methods. The left histograms show the performance results, and the right histograms show the preprocessing and training time consumption of each method. Our methods consistently achieve significant improvements in both performance for Isolated and Low-degree node settings and runtime efficiency over baselines.
time to train the generative model prior to GNN training. It also takes additional time to generate extra features for each node during training. Although Dropedge (Rong et al., 2019) and TuneUP (Hu et al., 2022) are free preprocessing, they require additional time to drop edges in each training epoch compared to base GNN training. Furthermore, the two-stage training employed by TuncUP doubles the training time compared to one-stage training methods. For NODEDUP methods, duplicating nodes and adding edges is remarkably swift and consumes significantly less preprocessing time than other augmentation methods. As an example, (ODEDUP(L) and NODEDUP are 977.0x and 488.5x faster than LAGNN in preprocessing Citeseer, respectively. We also observe that NODEDUP(L) has the least training time among all augmentation methods and datasets, while NODEDUP also requires less training time 8/9 cases. Additionally, NODEDUP(L. achieves significant efficiency benefits compared to NODEDUP in Figure 8, especially when the number of nodes in the graph increases substantially. Taking the IGB-100K dataset as an example, NODEDUP(L) is 1.3x faster than NODEDUP for the entire training process.
4.5 Performance under the Inductive Setting
Under the inductive setting (Guo al., 2022; Shiao al., 2022), which closely resembles real-world LP scenarios, the presence of new nodes after the train- ing stage adds an additional challenge compared to the transductive setting. We evaluate and present the effectiveness of our methods under this setting in Ta- ble for Citeseer, Physics, and IGB-100K datasets. Additional results for other datasets can be found in Appendix C.10. In Table 2, we observe that our methods consistently outperform base GSage across all of the datasets. We also observe significant per- formance improvements of our methods on Isolated nodes, where NODEDUP and NODEDUP(L) achieve 5.50% and 3.57% improvements averaged across the three datasots, respectively. Additionally, NODEDUP achieves 5. 5.09% improvements on Low-degree nodes. NODEDUP leads to more pronounced improvements on Low-degree/ Tsolated nodes, making it partieularly beneficial for the inductive setting.
Table 2: Performance in inductive settings. The best result is bold, and the runner-up is underlined. Our methods consistently outperform GSage.
GSage
NODEDUP(L)
NODEDUP
Isolated
58 38.422a..o
62.42.1..
62.94..m
Low-degree
67. 75...6
69. 69.93
72.05
Citeseer
Warm
72.98
75.04gmm
74.40la
Overall
06. oou
69.65 vo.s0
70.26
Isolated
85 i5.62
85.94
86.90.s.x
80.87 Low-reegree
81.23
85.56g
Physicn
Warm
90 ouse
90.37 +0.45
90.54+a.4
Overall
89 40.40aa
89.57 co.2s
89.98
Isolated
84.33 84.33ga
92.94
93.95gam
Low-degree
93. 19.119mmm
93.333a
94.00gam
IGB-100K
Warm
90.76 00.76aaaa
91.21 2
91.20 20.
Overall
90.31
91.9210..
92.21
9

---

Published in Transactions on Machine Learning Research (08/2025)
Table Performance with different encoders (inner product as the decoder). The best result for each encoder is bold, and the runner-up is underlined. Our methods consistently outperform the base models, particularly for Isolated and Low-degree nodes.
GAT
NonRDuP(T.)
NODRDUP
JKNet
NODEDUP(T.)
NODEDUP
Isolated
37.78
38.95
37 2a
49.06
55.15
Low-degree
58.0422
61 a1
66.73
60.74
71.78
75.26
Citeseer
Warm
56.37s2:8
64.55
66.61
71.61 2077
74.66
15.81
Overall
53.42g150
28.89
61.7320.v 6
=
71.75gaaa
Isolated
38.19
39.95 11.4
45.89 12
42.57 +1.90
55.47
61.11 82:47
Low-degree
74.19soa1
74.77 60.40
76.36 so
79.55
81.14
Physica
Warm
85.842032
86.02an.r
85.84 85.84
88 24
89.42an.t
89.242m.0
Overall
85.27
85.47 25.47
85.37 20.24
87 64
88.96
88.87
Isolated
45
78.17
80.18
29.29
86.60
86.85
Low-degree
77.05go
78.50
81.00
76.90
86.942o.s
87.65200
IGB-100X
Warm
81.40voor
81.95 aaas
81.19.0.20
84.93
87.41
86.19
Overall
80.4220or
81.192ams
21.11
82.91 20.25
87.29
86.4720.3
4.6 Performance with Different Encoders/Decoders
As simple plug-and-play augmentation method, NODEDUP can work with different GNN encoders and LP decoders. In Tables 3 and 4, we present results with GAT (Veličković et al., 2017) and JKNeet (Xu et al., 2018) as encoders, along with a MLP decoder. Due to the space limit, we only report the results of three datasets here and leave the remaining in Appendix C.11. When applying NODEDUP to base LPP training, with GAT or JKNet as the encoder and inner product as the decoder, we observe significant performance improvements across the board. Regardless of the encoder choice, NODEDUP consistently outperforms the base models, particularly for Isolated and Low-degree nodes. From Appendix C.11, we also observe the performance improvements of NODEDUP with GCN (Kipf & Welling, 2016a), Graph Transforeee (Dwivedi & Bresson, 2020) as encoders.
In Table 4, we present the results of our methods applied to the base LP training, where GSage serves as the encoder and MLP as the decoder. Regardless of the decoder, we observe better performance with our methods. These improvements are significantly higher compared to the improvements observed with the inner product decoder. The primary reason for this discrepancy is the inclusion of additional su- pervised training signals for isolated nodes in our methods, as discussed in Section 3.2. These signals play a crucial role in training the MLP decoder, making it more responsive to the specifie challenges presented by isolated nodes.
Table LP performance with MLP decoder (GSage as the encoder). Our methods outperform the base model.
MLP-Dec. (LDEDUP(L)
NODEDUP
Isolated
17.16
37.84
51.17
Low-degree
63.82 1
68.49 .9.49
71.98 11.9
Citeseer
Warm
72.93
75.332mas
75.72gmm.
Overall
59.49-1
06.07
69.89 2c.0
Isolated
11.59 1s
60.25 2.54
59.50 1.07
Low-degree
76.37-oox
81.74-wo7
82.58
Physice
Warm
91.54_oa1
91.96
91.59-o.2
Overall
90.78
91.51
91.13-05s
Isolated
3.51
82.71 +..00
82.02
Low-degree
75.25
85.96
86,04
IGB-1000
Warm
85.06
87.89
86.87
Overall
80.16
87.35
86.54
Furthermore, we apply NODEDUP to SEAL (Zhang & Chen, 2018), a subgraph- based LP model, and observe notable performance gains, as shown in Appendix C.11, demonstrating the broad applicability of our method across different GNN models and training paradigms.
4.7 Influence of the Duplication Frequency and Duplicated Node Types in NodeDup
In experiments, we duplicate the cold nodes once and add one edge for each cold node in NODEDUP. Figure 9 presents the results of our ablation study on Citeseer datasct, which examines how varying the duplication frequency and the types of duplicated nodes alfect the performance of NODEDUP across the Isolated, Low-degree, and Overall settings. The numbers in each block represent the performance differences relative to the bascline of duplicating cold nodes once. From the results, we observe that increasing the duplication frequency does not consistently lead performance improvements across all settings. Notably, duplicating all nodes multiple times significantly enhances the performance of Isolated nodes. However, this
10

---

Published in Transactions on Machine Learning Research (08/2025)
10
10
Duplicated Times
in
-1.88
-7.14
Duplicated Times
0.62
-2.02
-16.41
Duplicated Times
in
0.42
-1.82
-30.48
-2.25
-4.88
6.48
0.98
-1.57
-7.49
0.16
-0.97
-20.47
-2.82
-1.60
8.64
0
1.97
-1.09
-5.42
0.36
-0.37
-14.86
0
-1.03
-1.22
6.57
0.73
-0.21
-0.43
-0.13
0.25
-8.25
-5
-5
-5
1
1.46
0.00
4.88
0.53
0.00
-1.55
-0.24
0.00
-6.39
10
-10
-10
Isolated Cold Duplicated Nodes
All
Isolated Cold Duplicated Nodes
All
Isolated Cold Duplicated Nodes
All
(a) Isolated
(b) Low-degree
(c) Overall
Figure Ablation study on duplication frequency and node types of NODEDUP, (a), (b), (c) show the
performance for Isolated nodes, Low-degree nodes, and Overall scttings, respectively. The values in cach block represent the performance differences compared to the baseline setting of duplicating cold nodes once.
Table 5: Distribution and AUC performance of testing Warm-Warm and Warm-Coll links. NODEDUP improves Warm-Col link performance while maintaining Warm-Waa link performance.
Warm- Warm
Warm-Cold
Number
GSage
NODEDuP(L)
NODEDUP
Number
GSage
NODEDUP(L)
NODEDUP
Cora
157738
94. 91.92
95.17=0.19
18.18+
16759
77. 97.06+1.42
81.41+1.1
80.51+1.2
63266
97.21 g0.00
97.0620mm
97.022n.1a
24020
75
87.9610.7
88.401o.22
4209161
98.31
98.30
98.4210.02
91458
87. 17.9220.1
91.47
90.4410st
Physics
11462743
99.01 +o.01
99.01-o.m
99.02 to.00
103174
86.21+o.as
89.91+n.11
90.23 +0.01
Photos
2984253
97. 97.80
08.03-+o.00
97.87 +0.02
104737
59.80+1.s
68.11+o.45
6..32
Computers
5417165
97.5820
97.60=0.os
97.54.0..0
217090
46.49
57.3220.09
47.63
IGB-100K
6899924
98.702o.00
98.71 0.002
98.64
1372994
97.14
98.631..42
98.2311..
approach also introduces a large number isolated nodes into the graph, which negatively impacts the overall performance. Consequently, duplicating only cold nodes once emerges as the most effective strategy, it consistently maintains strong performance across all settings. Further analysis of the impact of different. duplicated node types is provided in Appendix C.2.
4.8 Analyzing Performance Gains of NodeDup on Warm Nodes
To better understand the performance improvements of NODEDUP on Warm nodes, we first analyzed the distribution of Warm-Warm Warm and Warm-Cold links in the testing set. Our analysis reveals that, across all datasets, the number of Warm- Warm links consistently exceeds that of Warm-Cold links, as shown in Table 5. This observation indicates that Warm-Cold links do not overwhelmingly influence the overall performance of Warm nodes. To further investigate, we conducted experiments comparing the performance of our method on these two types of links. The results demonstrate that our approach consistently enhances performance on Warm-Cold links while maintaining strong performance on Warm-Ward links. These findings confirm that our method does not negatively impact the learning ability Warm nodes. Instead, the observed performance gains primarily stem from improved learning Cold nodes, previously discussed in Section 4.2.
5 Conclusion
GNNs in LP encounter difficulties when dealing with cold nodes that lack sufficient or absent neighbors. To address this challenge, we presented simple yet effective augmentation method (NODEDUP) specifically tailored for the cold-stari LP problem, which can elfectively enhance the prediction capabilities of GNNs for cold nodes while maintaining overall performance. Extensive evaluations demonstrated that both NODEDUP and its lightweight variant, NODEDUP(L), consistently outperformed baselines on both cold node and warm node settings across 7 benchmark datasets. NODEDUP also achioved better runtime efficiency compared to the augmentation baselines.
11

---

Published in Transactions on Machine Learning Research (08/2025)
Acknowledgements
We are grateful for all the insightful comments and constructive suggestions provided by the reviewers. This research was partially conducted during Zhichun's s internship at Snap Inc. and was supported by the National Science Foundation (NSF) through the Center for Computer Assisted Synthesis (C-CAS), under grant number CHE-2202693.
References
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012. 09816, 2020.
Rianne den Berg, Thomas N Kipf, and Max Welling, Graph convolutional matrix completion. arXiv preprint arXio:1706. 02263, 2017.
Lei Cai and Shuiwang Ji. multi-scale approach for graph link prediction. In Proceedings of the AAAI conference artificial intelligence, 2020.
Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. 1EEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Ling Cai, Bo Yan, Gengchen Mai, Krzysztof Janowicz, and Rui Zhu. Transgen: Coupling transformation assumptions with graph convolutional networks for link prediction. In Proceedings of the 10th international conference on knowledge capture, pp. 131 138, 2019.
Benjamin Paul Chamberlain, Sergey Shirobokov, Emanucle Rossi, Fabrizio Frasca, Thomas Markovich, Nils Hammerla, Michael M Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. arXiv preprint ar arXie:2009. 15486, 2022.
Zhihong Chen, Rong Xiao, Chenliang Li, Gangfeng Ye, Haochuan Sun, and Hougbo Deng. Esam: Discrimina- tive domain adaptation with non-displayed items improve long-tail performance. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp- 579-588 2020.
Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction. arXic preprint. arXiv:2111.0006, 2021.
Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM review, 2009.
Tim R Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M Tomczak. Hyperspherical variational auto-encoders. arXiv preprinl Xiv: 00891, 2018.
Hao Ding, Yifei Ma, Anoop Deoras, Yuyang Wang, and Hao Wang. Zero-shot recommender systems. arXie preprint arXft:2105.0883 2021.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey.
ACM SIGKDD Explorations Newsletter, 2022.
Kaiwen Dong, Yijun Tian, Zhichun Guo, Yang Yang, and Nitesh Chawla. Fakeedge: Alleviate dataset shift in link prediction. In Learning on Graphs Conference, pp. 56-1. PMLR, 2022.
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint ar Xiv:2001 09699, 2020.
Wenqi Fan, Xiaorui Liu, Wei Jin, Xiangyu Zhao, Jiliang Tang, and Qing Li. Graph trend filtering networks for recommendation. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022.
12

---

Published in Transactions on Machine Learning Research (08/2025)
Wenzheng Feng. Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092 22103, 2020.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint Xiv: 02428, 2019.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning. PMTRR, 2017.
Zhichun Guo, William Shiao, Shichang Zhang, Yozen Liu, Nitesh Chawla, Neil Shah, and Tong Zhao. Linkless link prediction via relational distillation. arXiv preprint arXiv:2210.0588 2022.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs Advances in neural information processing systems, 2017.
Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah. Mlpinit: Embarrassingly simple gan training acceleration with mlp initialization. arXiv preprint arXic:2210.000 00102, 2022.
Bowen Hao, Jing Zhang, Hongzhi Yin, Cuiping Li, and Hong Chen. Pro-training graph neural networks for cold-start users and items representation. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, 2021.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for rocommendation. In Proceedings of the 43rd International ACM SIGIR conference on reseurch and development Information Retrieval, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 2020.
Weihua Hu, Kaidi Cao, Kexin Huang, Edward W Huang, Karthik Subbian, and Jure Leskovec. Tuncup: A training strategy for improving generalization of graph neural networks. arXio preprinl ar 221.2220..4.... 2022.
Chao Huang, Huance Xu, Yong Xu, Peng Dai, Lianghao Xia, Mengyin Lu, Liefeng Bo, Hao Xing, Xiaoping Lai, and Yanfang Ye. Knowledge-awark coupled graph neural network for social recommendation. In Proceedings of the AAAT conference on artificial intelligence, volume 35, pp. 4115 4122, 2021.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. arXiv preprint 1rX00:1910.000
2019.
Arpandeep Khatua, Vikram Sharma Mailthody, Bhagyashree Taleka, Tengfei Ma, Xiang Song, and Wen-mei Hwu. Igb: Addressing the gaps in labeling, features, heterogencity, and size of public graph datasets for deep learning research, 2023. URL https:tt///// www.aaawwwi..gga/////2222/2/
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXie preprint arXiv: 02907, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07300 2016b.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Crabska-Barwiiske et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114(13))3511-3356, 2017.
István A Kovács, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Dae-Kyum Kim, Nishka Kishore, Tong Hao, et al. Network-basee prediction of protein interactions. Nature communications, 2019.
13

---

Published in Transactions on Machine Learning Research (08/2025)
Juanhui Li, Harry Shomer, Jiayuan Ding, Yiqi Wang, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. Are message passing neural networks really helpful for knowledge graph completion? ACT, 2023.
Jie Liao, Jintang Li, Liang Chen, Bingzhe Wu, Yatao Bian, and Zibin Zheng. Sailor: Structural augmentation based tail node representation learning. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 1389 1399, 2023.
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 2007.
Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision, pp. 2980-2988, 2017.
Gang Liu, Tong Zhao, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Graph rationalization with -easronment-based augmentations. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1069-1078, 2022a.
Siyi Liu and Yujia Zheng. Long-tail session-based recommendation. In Proceedings of the 14th ACM Conference on Recommender Systems, pp. 509 514, 2020.
Songtao Liu, Rex Ying, Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu. Local augmentation for graph neural networks. In International Conference on Machine Learning, pp. 14054-14072. PMLR, 2022b.
Zemin Liu, Wentao Zhang, Yuan Fang, Ximming Zhang, and Steven CH Hoi. Towards locality-aware meta- learning of tail node embeddings on networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 975-9844 2020.
Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. Tail-gnn: Tail-node graph noural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Dala Mining, 2021.
Zemin Liu, Trung-Kien Nguyen, and Yuan Fang. On generalized degree fairness in graph neural networks. arXiv preprint arXim:290200388 038881 2023.
Yuanfu Lu, Yuan Fang, and Chuan Shi. Meta-learning on hetcrogencous information networks for cold-start recommendation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020.
Youzhi Luo, Michael McThrow, Wing Yee Au, Tao Komikado, Kanji Uchino, Koji Maruhash, and Shuiwang Ji. Automated data augmentations for graph classification. arXic preprint arXiv:2202. 13248, 2022.
Hyeonjin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung- Woo Ha, and Hyunwoo J Kim. Metropolis hastings data augmentation for graph neural networks. Advances in Neural Information Processing Systems, 34:19010-19020, 2021.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXic:2002. 052887, 2020.
Foster Provost. Machine learning from imbalanced data sets 101. 2000.
Jiawei Ren, Cunjun Yu, Xiao Ma, Haiyu Zhao, Shuai Yi, et al. Balanced meta-softmax for long-tailed visual recognition. Advances in neural information processing systems, 13:4175-4186, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXio preprint
2019.
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021, 2021.
14

---

Published in Transactions on Machine Learning Research (08/2025)
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semanlic web conference, pp- 593 607. Springer, 2018.
William Shiao, Zhichun Guo, Tong Zhao, Evangelos E Papalexakis, Yozen Liu, and Neil Shah. Link prediction with non-contrastive learning. arXiv preprint arXio:2211.14394 2022.
Zachary Stanfield, Mustafa Coskun, and Mehmet Koyutürk. Drug response prediction as link prediction problem. Scientific reports, 2017.
Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan. Equalization loss for long-tailed object recognition. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pp. 11662 11671, 2020.
Kaihua Tang, Jianqiang Huang, and Hanwang Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. Advonces in Neural Information Processing Systems, 33: 1513-1524, 2020a.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degroo-related biases in graph convoltuional networks. In Proceedings of the 29th ACM International Conference Information & Knowledge Management, 2020b.
Xianfeng Tang, Yozen Liu, Xinran He, Suhang Wang, and Neil Shah. Friend story ranking with edge- contextual local graph convolutions. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, 2022.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Eric Gaussior, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International conference machine learning. PMLR, 2016.
Antonios Valkanas, Yuening Wang, Yingxue Zhang, and Mark Coates. Personalized negative reservoir for incremental learning in recommender systems. Xix preprint arXiv:2433.0300 2024.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition-basee multi-relational graph convolutional networks. In International Conference on Learning Representations, 2020.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint MSX::111000100: 2017.
Maksims Volkovs, Guangwei Yu, and Tomi Poutanen. Dropoutnet: Addressing cold start in recommender systems. Advances in neural information processing systems, 30, 2017.
Ruijia Wang, Xiao Wang, Chuan Shi, and Le Song. Uncovering the structural fairness in graph contrastive learning. Advances in neural information processing systems, 35:32465- 85:32465-32473, 2022.
Zhitao Wang, Yu Lei, and Wenjie Li. Neighborhood attention networks with adversarial learning for link prodiction. JEEE Transactions Neural Networks and Learning Systems, 32(8))3653-366) 2020.
Zhitao Wang, Yong Zhou, Litao Hong, Yuanhang Zou, Hanjing Su, and Shouzhi Chen. Pairwisc learning for neural link prediction. ar preprinl arXiv:21 12.029,,, 2021.
Jun Wu, Jingrui He, and Jiejun Xu. Net: Degree-specific graph neural networks for node and graph classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery g Data Mining, pp. 406-415, 2019.
Qitian Wu, Hengrui Zhang. Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. arXiv preprint arXix:2202. 024666000 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEFE Iransactions neuraa networks and learning systems, 2020.
15

---

Published in Transactions on Machine Learning Research (08/2025)
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453 5462. PMLR, 2018.
Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates. Graphsail: Graph structure aware incremental learning for recommender systems. In Proceedings of the 29th ACM International Conference on Informalion & Knowledge Management,, pp.
2020.
Zuoyu Yan, Tengfei Ma, Liangeai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In International conference on machine learning, pp. 11659-11669. PMLR, 2021.
Chaoqi Yang, Cao Xiao, Fenglong Ma, Lucas Glass, and Jimeng Sun. Safedrug: Dual molecular graph encoders for recommending effective and safe drug combinations. In IJCAI, pp. 3735-3741 3741, 2021.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD internalional conference on knowledge discovery & data mining, 2018.
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 2021.
Chuxu Zhang, Huaxiu Yao, Chao Huang, Meng Jiang, Zhenhui Li, and Nitesh V Chawla, Few-shot knowledge graph completion. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in newral information processing systems, 2018.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Newral Information Processing Systems, 2021.
Lingxiao Zhao and Leman Akoglu. Pairnorm:
Tackling oversmoothing in guns. arXie preprint
orXiv:1909, 12223, 2019.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the aaai conference on artificial intelligence, 2021.
Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang, Gang Liu, Stephan Günneman, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. arXiv preprint ar Xix: 08871, 2022a.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfactual links for link prediction. In International Conference on Machine Learning. PMLR, 2022b.
Wenqing Zheng, Fdward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete or missing neighborhoods. arXie preprint arXiv:2111.04840, 2021.
Fan Zhou and Chengtai Cao. Overcoming catastrophic forgetting in graph neural networks with experience replay. In Proceedings of the AAAT conference on artificial intelligence, volume 35, pp. 4714-4222, 2021.
Yu Zhu, Jinghao Lin, Shibi He, Beidou Wang, Ziyu Guan, Haifeng Liu, and Deng Cai. Addressing the item cold-start problem by attribute-driven active learning. IEEE Transactions on Knowledge and Data Engincering, 2019.
Zhaocheng Zhu, Zuobai Zhang, Lasis-Pascal Xhonneux, and Jian Tang. Neural bellman-ford networks: A general graph neural network framework for link prodiction. Advances in Neural Information Processing Systems, 2021.
16

---

Published in Transactions on Machine Learning Research (08/2025)
CONTENTS OF APPENDIX
A Related Work
18
B Additional Datascts Details
18
B.1 Transductive Setting
19
B.2 Inductive Sctting
20
C Further Experimental Results
20
C.1 Selection of the threshold 8.
20
C.2 Further analysis about the duplication node lypes
................................
21
C.3 Performance large-scale datasets
................................
21
C.4 Performance on heterophily datasets
21
................................
C.5 Performance on recommendation datasets
23
C.6 Performance compared with heuristic methods
................................
23
C.7 Performance compared with additional cold-start methods
................................
23
C.8 Efficiency comparison with the base GNN model and cold-start baselines
24
C.9 Additional results compared with augmentation baselines
24
C.10 Additional results under the inductive sctting
25
C.11 Ablation study
C.11.1 Performance with various encoders and decoders
27
C.11.2 Performance with SEAL (Zhang & Chen, 2018)
28
D Implementation Details
28
E Limitations
28
F Ethics Statement
29
17

---

Published in Transactions on Machine Learning Research (08/2025)
A Related Work
LP with GNNs. Over the past few years, GNN architectures (Kipf & Welling, 2016a; Gilmer et al., 2017; Hamilton et al., 2017; Veličković et al., 2017; Xu et al., 2018) have gained significant attention and demonstrated promising outcomes in LP tasks. There are two primary approaches to applying GNNs in LP. The first approach involves a node-wise encoder-decoder framework, which we discussed in Section 2. The second approach reformulates LP tasks as enclosing subgraph classification tasks (Zhang & Chen, 2018; Cai & Ji, 2020; Cai et al., 2021: Dong et al., 2022). Instead of directly predicting links, these methods perform graph classification tasks on the enclosing subgraphs sampled around the target link. These methods can achieve even better results compared to node-wise encoder-decoder frameworks by assigning node labels to indicate different roles within the subgraphs. However, constructing subgraphs poses challenges in terms of elficiency and scalability, requiring substantial computational resources, Our work focuses on the encoder framework for LP, circumventing the issues associated with subgraph construction.
Methods for Cold-start Nodes. Recently, several GNN-based methods (Wu al., 2019; Liu et al., 2020; Tang et al., 2020b; Liu et al., 2021; Zheng et al., 2021) have explored degree-specific transformations to address robustness and cold-start node issues. Tang et al. al.(Tang et al., 2020b) introduced a degree-related graph convolutional network to mitigate degree-related bias in node classification tasks. Liu et al. et al., 2021) proposed a transferable neighborhood translation model to address missing neighbors for cold-start nodes. Zheng et (Zheng et al., 2021) tackled the cold-start nodes problem by recovering missing latent neighbor information. These methods require aodd-start-nod--peeeff architectural components, unlike our approach, which does not necessitate any architectural modifications. Additionally, other studies have focused on long-tail scenarios in various domains, such as cold-start recommendation( (Chen et al., 2020; Lu et al., 2020; Hao el al., 2021). Imbalance lasks present another common long-tail problem, where there are long-tail instances within small classes (Lin et al., 2017; Ren et al., 2020; Tan et al., 2020; Kang et al., 2019; Tang et al., 2020a). Approaches like (Lin ct al., 2017; Ren et al., 2020; Tan et al., 2020) address this issue by adapting the loss for different samples. However, due to the different problem settings, it is challenging to directly apply these methods to our lasks. We only incorporate the balanced cross entropy introduced by Lin et al. (Lin et al., 2017) as one of our baselines. In addition to these one-shot training methods, many recommendation studies (Kirkpatrick et al., 2017; Xu et al., 2020; Zhou & Cao, 2021; Valkanas et al., 2024) have addressed the issue of incorporating new nodes through incremental learning frameworks, where new nodes are continually added into the training process and specific strategies are designed to alleviate forgetting previous knowledge (i.e., warm nodes or old classes).
(Chen
Graph Data Augmentation. Graph data augmentation expands the original data by perturbing or modifying the graphs to enhance the generalizability of GNNs (Zhao et al., 2022a; Ding et al., 2022). Existing methods primarily focus on semi-supervised node-level (asns
al., 2019; Feng al., 2020; Zhao et al., 2021; Park et al., 2021) and graph-level tasks (Liu et al., 2022a; Luo et al., 2022). However, the exploration of graph data augmentation for LP remains limited (Zhao et al., 2022b). CFLP (Zhao et al., 2022b) proposes the creation of counterfactual links to learn representations from both observed and counterfactual links. Nevertheless, this method encounters scalability issues due to the high computational complexity associated with finding counterfactual links. Moreover, there exist general graph data augmentation methods (Liu et al., 2022b; Hu et al., 2022) that can be applied to various tasks. LAGNN (Liu et al., 2022b) proposed to use a generative model to provide additional neighbor features for each node. TuneUP (Hu et al., 2022) designs a two-stage training strategy, which trains GNNs twice to make them perform well on both warm nodes and cold-start nodes. These augmentation methods come with the trade-off of introducing extra runtime either before or during the model training. Unlike TLC-GNN (Yan et al., 2021), which necessitates extracting topological features for each node pair, and GIANT (Chien et al., 2021), which requires pre-training of the text encoder to improve node features, our methods are more streamlined and less complex.
B Additional Datasets Details
This section provides detailed information about the datasots used in our experiments. We consider various types of networks, including citation networks, collaboration networks, and co-purchase networks. The datasets we utilize are as follows:
18

---

Published in Transactions on Machine Learning Research (08/2025)
Table 6: Detailed statistics of data splits under the transductive and inductive setting.
Transductive Setting
Original
Graph # #Edges
Testing Isolated
Testing Low-degree #Nodes
Testing
Warm
Datasets
# #Nodes
# Nodes
#Edges
#Edges
# NNoee
# #ddges
Cora
2,708
5,278
135
164
541
726
662
1,220
Citeseer
3,327
4,552
291
342
492
591
469
887
CS
18,333
163,788
309
409
1,855
2,687
10,785
29,660
Physics
34,493
495,924
275
397
2,062
3,188
25,730
95,599
Computers
13,752
491,722
218
367
830
1,996
11,887
194,325
Photos
7,650
138.162
127
213
516
1,178
6,595
93,873
IGB-100K
100,000
547,416
1,556
1,737
6,750
7,894
23,949
35,109
Inductive Setting
Original Graph
Testing Isolated
Testing Low-degree #Nodes
Testing Warm
Datasets
# #Nodes
#Edges
# #Nodes
#Edges
#Edges
# Nodes
# Eddes
Cora
2,708
5,278
149
198
305
351
333
505
Ciseseer
3,327
4,552
239
265
302
339
CS
18,333
163,789
1,145
1,867
1,202
1,476
6,933
13,033
Physics
34,493
495,924
2,363
5,263
1,403
1,779
17 17,881
42,548
Computers
13,752
491,722
1,126
4,938
239
302
9,235
43,928
Photos 7,650
238,162
610
2,375
169
212
5,118
21,225
IGB-100K
100,000
547,416
5,507
9,708
8,706
13,815
24,903
41,217
Citation Networks: Cora and Citeseer originally introduced by Yang et al. (2016), consist cita- tion networks where the nodes represent papers and the edges represent citations between papers. IGB-100K (Khatua et al., 2023) recently-relaased benchmark citation network with high-quality node features and large dataset size.
Collaboration Networks: CS and Physics are representativ ive collaboration networks. In these networks, the nodes correspond to authors and the edges represent collaborations between authors.
Co-purchase Networks: Computers and Photos are co-purchase networks, where the nodes represent. products and the edges indicate the co-purchase relationship between two products.
Why there are no OGB (Hu et al., 2020) datasets applied? OGB benchmarks that come with node features, such OGB-collab and OGB-citation2, lack substantial number of isolated or low-degree nodes, which makes it challenging to yield convincing results for experiments focusing the cold-start problem. This is primarily due to the split setting adopted by OGB, where the evaluation is centered around a set of the most recent papers with high degrees. Besides, considering these datasets have their fixed splitting settings based on time, it will lead to inconsistent problems to compared with the leaderboard results if we use our own splitting method to ensure we have a reasonable number of solated/low-dogge these constraints, we opted for another extensive benchmark dataset, IGB-100K (Khatua et al., 2023), to test. and showcase the effectiveness of our methods on large-scale graphs. We further conducted the experiments on IGB1M, which are shown in Appendix C.3.
nodes. Given
B.1 Transductive Setting
For the transductive setting, we randomly split the edges into training, validation, and testing sets based on the splitting ratio specified Section 4.1. The nodes in haaiin/gvvviaaaionn/oooooooooa training process. However, the positive edges validation teatttiiottttinngg sets are masked out for training. After the split, we calculate the degrees of each node using the validation graph. The dataset statistics are shown in Table 6.
are all visible during the
19

---

Published in Transactions on Machine Learning Research (08/2025)
120
350
1600
Hits@ 10
120
Hits@
100
Avg. H0
Avg. Hits@10
1400
Nodes
250
100
# Nodes
1200
H
80
Nodes
H1t@@10
80
1000
200
60
150
60
800
40
100
40
400
20
200
0
2
3
6
7
8
9
10
2
8
10
12
14
16
18
20
Node Degree
Node Degree
(a) Cora
(b)
120
Hits@ 10
Avg. H0
700
120
Avg. Hits@
Hits@
4000
100
Nodes
600
100
Nodes
Hits@10
80
500
Nodee
Hits@h10
80
#oNoos
60
400
60
2000
300
40
40
200
1000
20
100
20
10 12 14
16 18 20 22 24 26 28 30
2
8
10
12
14
16
18
20
Node Degree
Node Degree
(c) Computers
(d) IGB-100K
Figure 10: Node Degree Distribution and LP Performance Distribution w.r.t Nodes Degrees showing reverse trends on various datasets.
B.2 Inductive Setting
The inductive sctting considered more realistic setting compared the transductive sctting, where new nodes appear aftrr the training process. Following the inductive setting introduced in Guo et al. (2022) and Shiao et al. (2022), perform node splitting to randomly sample 10% nodes from the original graph as the new nodes appear after the training process. The remaining nodes are considered observed nodes during the training. Next, we group the edges into three sets: observed-observed, observed-new, and new-new node pairs. We select 10% of observed-observed, 10% observed-new, and 10% of new-new node pairs as the testing edges. We consider the remaining abserved-news and new-new node pairs, along with an additional 10% of obscrved-observer node pairs, as the newly visible edges for the testing inference. The datasets statistics are shown in Table 6.
C Further Experimental Results
C.1 Selection of the threshold 8.
Our decision to set the threshold 8 at 2 is grounded in data-driven analysis, illustrated in Figure 1 and Figure 10. These figures reveal that nodes with degrees not exceeding 2 consistently perform below the average Hits@10 across all datascts, and higher than 2 will outperform the average results. Besides, our choice aligus with methodologies in previous studies (Liu et al., 2020; 2021), where cold nodes are identified using a fixed threshold across the datasets. In addition, we conduct experiments with different thresholds on Cora and Citeseer datasots. The results are shown Table Our findings were consistent across different thresholds, with similar obscrvations effectiveness is not significantly impacted by changes in this threshokd.
1, 2, and 3. This indicates that our method's
20

---

Published in Transactions on Machine Learning Research (08/2025)
Table 7: Performance with different thresholds on Cora and Citeseer datasets. 6 3
A ==1
ó ==2 2
Gsage
NODEDUP
Gsage
NODEDUP
Gsage
NODEDUP
Isolated
31.34gs so
42.20 as
32.20ga.1a
44.27
31.95g100 so
43.17
Low-degree
23.98
57 37.99.1.x
59.45=1.0
61.98
59.64-1.4
62,68 ro.03
Cora
Warm
61. 61.6820m
61.172o 11.1720.s
61.14gom
59.07
61.03gom
59.91 an
Overall
58.01 an
59. 100.622.44
58.31 go.se
08.92an.x
58. 08.088a 74
59.99
Isolated
56.49 za
47.13
57.54g
ga.w
56.90
Low-degree
54. 40
71.0920.4v
61.88go.0
75.50
62.97
75.45
Citeseer
Warm
72. a2.4
71.45
74.68
75.02-to.4
Overall
a4.27
70.53gn91
63.7720.a
71.73 47
64.05go.n
71.80 o0
C.2
Further analysis about the duplication node types
To make our analysis about the duplication node types more comprehensive, we conducted additional experiments to evaluate different node duplication strategies under both the NODEDUP and NODEDUP(L) settings. We present dctailed experiments on the Citeseer datasct, where we duplicate different subscts of nodes: isolated nodes, cold nodes, mid-warm nodes, warm nodes, random nodes, and all nodes. We report the corresponding training time, memory usage, and performance across multiple evaluation subsets. The results are summarized in Table 8.
From the table, we can observe that for both NODEDUP and NODEDUP(L), duplicating mid-ward and warm nodes results in little to no performance improvement. Random duplication provides clear improvements over both no duplication and warm node duplication, but remains less effective than cold node duplication. Since random duplication and cold nodes duplication duplicate the same number of nodes, they incur similar memory and training costs. Under the NODEDUP setting, compared to cold nodes duplication, all nodes duplication increases training time by approximately 32% (3.3s 2.5s) and memory usage by approximately 35% (93.99MB vs. 69.46MB), while achieving only marginal additional performance gain (Low-degree Hits@ 10: 76.09 vs. 75.50). Under the NODEDUP(L) setting, full duplication increases training time by approximately 14% (2.4s vs. 2.1s), while memory usage remains identical, again with limited additional performance gain dLow-degree @its@10: 75.32 vs. 74.99).
These results demonstrate that our proposed selective cold node duplication achieves most of the performance improvement while significantly reducing both training time and memory cost compared to full duplication. This further supports the practical advantage of our method under constrained compute budgets.
C.3 Performance on large-scale datasets
As outlined in Section 3.1, our methods incur min- imal increase in time complexity compared to base GNNs, with the increase being linearly proportional to the number of cold nodes. This ensures scalabil- ity. Besides, the effectiveness of our method is also insensitive to dataset size. We extend our experi- ments to the IGB1M dataset, featuring million nodes and 12 million edges. The findings, which we detail in Table 9, affirm the effectiveness of our methods
Table 9: Performance on the large-scale dataset. The best result is bold. Our method consistently outper- forms GSage on IGB1M
GSage
NodeDup
Isolated
82.10 12.10....
87.81
10.80 10.40
Low-degree
84.73
90.841o.03
IGB1M
Warm
89.98
91.31 10.02
Overall
89.80
91.29to.az
in handling large-scale datasets, consistent with observations from smaller datasets.
C.4 Performance on heterophily datasets
We have conducted experiments on two heterophilic datasets (i.e., Chameleon (Pei et al., 2020) and Squirrel (Pei et al., 2020)), with the results shown in Table 10. Our mothods improve GNN performance across all scttings on these datasets. Specifically, NodeDup and NodeDup(L) enhance the performance of Isolated nodes by 9.9% and 23.5% on Chameleon, and by 20.2% and 32.0% on Squirrel.
21

---

Published in Transactions on Machine Learning Research (08/2025)
Table 8: Computation time, memory usage, and link prediction performance with different duplication nodes of NODEDUP and NODEDUP(L) on Citeseer. 'D * indicates duplication *** group nodes for one time.
NodeDup
Time(s)
(Mmory(MB))
Performance (litts110)
Training
Node attributes
Edges
Isolated
Low-degrce
Warm
Overall
Supervised
1.8
47.00
0.14
47.13
61.88
71.45
63.77
D Isolated
54.03
0.14
54.04
72.28
74.53
69.95
Cold
69.46
0.14
57.54
75.50
74.68
71.73
D Mid-warm
2.2
55.83
0.14
46.93
61.34
71.84
63.75
Warm
2.2
57.53
0.14
47.49
62.20
71.54
63.99
Random
69.46
54.10
72.39
75.05
70.06
All
3.3
93.99
0.14
58.87
76.09
76.01
72.44
NodeDup(L)
Time(s)
Memory(MB)
Performanceellits@ll
Training
Node attributes
Edges
Isolated
Low-degree
Warm
Overall
Supervised
47.00
47.13
61.88
71.45
63.77
Isolated
2.0
47.00
0.14
49.06
69.95
74.67
68.32
D Cold
2.1
47.00
0.14
52.46
73.71
74.99
70.34
Mid-warm
2.2
47.00
0.14
46.05
61.57
72.30
63.88
Warm
47.00
46.53
61.86
71.77
63.82
D Random
2.2
47.00
0.14
48.92
69.59
73.90
67.81
D All
2.4
47.00
0.14
52.44
74.05
75.21
70.49
Table 10: Performance on heterophilic datasets.
The best result for each dataset is bold.
GSage
NodeDup(L)
NodeDup
Isolated
24.91 16.75
30.7614.02
27.37
Low-degree
79.09-1.21
80.11+o.as
80.91-0.4.
Chameleon
Warm
94.00-o.29
94.01+o11
03.688+n.44
Overall
92.77
92.88
92.57.0.44
Isolated
25.05
33.07
30.11:1.. 11.57
Low-degree
63.34=a.12
66.61
68.05=0.a0
Squirrel
Warm
93.35
03.43
93.82=0.1
Overall
92,89..o.m
13
93.41_o.n
22

---

Published in Transactions on Machine Learning Research (08/2025)
Table 12: Performance compared with heuristic methods, Upsampling and DegFairGNN (Liu et al., 2023).
The best result is bold.
CN
AA
RA
Upsampling
DegFairGNN
GSage
NODEDUP
Isolated
0.00
0.00
0.00
32.81s2m5
18.70
32.
44.27
Low-degree
20.30
20.14
20.14
50.57
38. 13
30.45
61.98-114
Cora
Warm
38.33
38.90
38.90
60.49
42.4921
61.142am
59.07200s
Overall
25.27
25.49
23.49
57.90 a7
39.24g1
58.31 an
58.9220.2
Isolated
0.00
0.00
0.00
26.88
15.50 av
47.13
57.54.1.0
Low-degree
26.86
27. $7.00
27.00
62.32
45.0620.0
g1.
g5.50
Citeseer
Warm
37.30
39
39.02
71.33
65.47+1.0
+1.45
74.68
Overall
30.81
31.85
31.85
63.8 gnai
44.58g1
63. 03
71.73gm.r
Isolated
0.00
0.00
0.00
49.63
17.9321
56.41
65.87
Low-degree
39.60
39. .0
39.60
75.62
49.832o.4
81.12
Warm
72.73
72.74
72.72
23.40
61.72
84.37
84.76
Overall
69.10
09.11
69.10
=2.34
60.20
83.33
84.23
Isolated
0.00
0.00
0.00
52.01 Lavor
19.48an
66.6520.m
Low-legree
46.08
46 .8
46.08
79. 2o..s
47 27.632mmm
79.31
84.0420.22
Physics
Warm
85. 48.48
85.74
85.70
89.4 gouas
62.79
90.28
90.33
Overall
83.87
84.12
84.09
89.33
62. 13g0
89.76ga.a
90.03
Isolated
0.00
0.00
0.00
11.36-0.ra
9.36
9.32
19.62
Low-legree
28.31
28.31
28.31
18.9020
57.91 an
61.16ga.02
Computers
Warm
59.67
63.50
62.84
31.4422
66.87
68.1020.2
Overall
59.24
63.03
62.37
86.87
31 $1.27aa00
66.67 29042
67.94
Tsolated
0.00
0.00
0.00
10.92
12.99
9.25gaa
17.84
Low-degree
28.44
28.78
28. 78
51. 66 6o.as
20.18
52,61 ro.ss
54.13
Photoa
Warm
64.53
67 26
66.88
65. 75.
42.7220
67.64
68.682n.a
Overall
63.94
66.6 64
66.26
65. 45.4
42.3Ta0
67.32
68.392..0
Isolated
0.00
0.00
0.00
25.492200
57. 67.092ai.0n os
75.92
88.04.n.00
Low-degree
12.26
12.26
12.26
79.472mm1
59.452m a4
a9.38
88.98
IGB-100K
Warm
30.65
30.65
30.65
86.54+o11
65.37 +20.44 20.43
86.42 +o.24
88. 0.20
Overall
26.22
26.22
26.22
84.872m14
64. 16.16 to
84.77
88.392..11
C.5 Performance recommendation datasets
To further evaluate the practical applicability of our method to real-world recommendation scenarios, we fol- lowed the approach introduced in KGCN (Huang et al., 2021) to construct a movie-movie graph, where two movies are connected if they received high ratings from the same user. This graph then used recommend similar movics to users. This setup forms an item-based collaborative filtering recommendation task, allowing to apply methods. The results is shown in Table 11. Compared to the baseline, both NODEDUP and NODEDUP(L) achieve consistent improvements, particularly on low-degree and isolated nodes, where these cold-start items often limits recommendation accuracy.
Table 11: Performance on the MovieLens. The best result is bold. Our method consistently outperforms GSage.
MovieLens 1M
GSage
NodeDup(L)
NodeDup
Tsolated
3.08
5.38
Low degree
30.7
35.07
37.69
Warm
41.79
44.61
45.52
Overall
41.71
44.56
45.78
C.6 Performance compared with heuristic methods
We compare our method with traditional link prediction baselines, such as common noighbors (CN), Adamic- Adar(AA), Resource allocation (RA). The results are shown in Table 12. We observe that NODEDUP can consistently outperform these heuristic methods across all the datasets, with particularly significant. improvements observed on Isolated nodes.
C.7 Performance compared with additional cold-start methods
Upsampling (Provost, 2000). In Scction 3, we discussed the issue of under-repreeenntatin of cold nodes during the training of LP, which is the main cause of their unsatisfactory performance. To tackle this problem, one forwigh and naive approach is upsampling (Provost, 2000), which involves increasing
23

---

Published in Transactions on Machine Learning Research (08/2025)
Table 13: Performance compared with GRADE (Wang et al., 2022) and SAIL.OR (Liao et al., 2023). The best result is bold.
GCN
GRADE
SAILOR
NODEDUr(L)
NODEDUP
Tsolated
40.61
43.29gamm
45.12
42.93ga
46.71
Low-degree
58.762197
62.98
64.63g1.m
10
Cora
Warm
60.59.
60.00sa.11
67.34
61.31 no.40
60.26
Overall
60.16g0.44
56.90
08.33
61.02 20.0x
59.90goa0
Isolated
45.56
50.11
49. 29.2992275
47 84
50.64:1.10
Low-degree
69.37
69.499
68.78
70.15
71.13
Ciseeee
Warm
74.68am.s
70.01
72.6620ar
73.262007
72.93
Overall
67.48.0.42
61.11 80.72
64.80vo..0
67.47
67.67
the number of samples in the minority class. In order to further demonstrate the effectiveness of our methods, conducted experiments where we doubled the edge sampling probability of code nodes, aiming to enhance their visibility, The results are presented in Table 12. We can observe that NODEDUP outperforms upsampling in almost all the cases, except for Warm nodes on Cora.
The methods tackling degree bias in GNNs. SAILOR (Liao et al., 2023) proposes a structural augmentation framework to enhance the representation learning of tail nodes. GRADE (Wang et al., 2022) improves structural fairness using graph contrastive Icarning methods. We used GCN as the encoder for both NODEDUP(L) and NODEDUP to ensure consistency, as both GRADE and SAILOR used GCN their encoder. Table 13 shows that our methods outperform these baselines in all settings. Additionally, both GRADE and SAILOR perform better than vanilla. GCN on Isolated nodes, which is the primary focus of their training. The sub-optimal performance of GRADE and SAILOR on Low-degree nodes in link prediction likely stems from the fact that their augmentation strategies, which are tailored for node classification, are less suited for ranking-bass link prediction tasks. The specific reasons are as follows: GRADE encourages representation smoothness via degree-aware contrastive learning, which benefits node classification but reduces the embedding discrimination required for link prediction, particularly when ranking edges involving low-degree nodes, as reflected by Hits@10. SAILOR constructs peeudo-homohilic edges based node labels; however, label similarity does not always align with link formation in link prediction, and adding label-based edges may introduce noise.
DegFairGNN (Liu et al., 2023) introduces a learnable debiasing function the GNN architecture to produce fair representations for nodes, aiming for similar predictions for nodes within the same class, regardless of their degrees. Unfortunately, we' ve found Table 12 that this approach not well-suited for link prediction tasks for several reasons: (1) This method is designed specifically for node classification tasks. For example, the fairness loss, which ensures prediction distribution uniformity among low and high-degree node groups, is not suitable for link prediction because there is no defined node class in link prediction tasks. (2) This approach achieves significant performance in node classification tasks by effectively mitigating degree bias. However, in the context of link prediction, the degree trait is crucial. Applying DegFairGNN (Liu et al., 2023) would compromise the model's ability to learn from structural information, such as isomorphism and common neighbors. This, in turn, would negatively impact link prediction performance, as evidenced by references (Zhang & Chen, 2018; Chamberlain al., 2022).
C.8 Efficiency comparison with the base GNN model and cold-start baselines
The efficiency comparison between our methods and cold-start baselines is presented in Figure 11. We can observe that our methods and Imbalance exhibit similar efficiency, comparable to GSage. However, TailGNN and Cold-brew demand significantly more preprocessing and training time. Cold-brew, in particular, needs the most preprocessing time as it needs to train teacher model for distillation.
C.9 Additional results compared with augmentation baselines
Figure 12 presents the performance compared with augmentation methods on the remaining datascts. On Cora and CS datasets, can consistently observe that NODEDUP and NODEDUP(T.) outperform all the
24

---

Published in Transactions on Machine Learning Research (08/202)
(NooeDupiL) NodeCOp
15
Cora
10.7
Time(s)
5.1 5.5
preprocess
Train
15
Citeseer
Time,a)
10
5.1
5.9
preprocess
Timele)
90
CS
83
91
60
GO
B6
Train
400
Physics
401
Time(s)
200
184
preprocess
Train
Computers
Time(s)
100
68
70
preprocess
Train
Time(s)
75
Photos
50
34
preprocess
Train
300
1GB-100K
Time(e)
200
100
106
88
10
preprocess
Train
Evaluated Time
Time- coneeooosnmngg compared with cold-start methods. The histograms show the preprocessing and training time consumption of each method.
Figure 11:
graph augmentation baselines for Isolated and Low-degree nodes. Moreover, for Warm nodes, NODEDUP can also perform on par or above baselines. On the Computers and Photos datasets, our methods generally achieve comparable or superior performance compared the basclines, except in comparison TuneUP. However, it is worth noting that both NODEDUP and NODEDUP(L.) exhibit more than 2x faster execution speed than TuneUP these two datasets.
C.10 Additional results under the inductive setting
We further evaluate and present the effectiveness of our methods under the inductive setting on the remaining datascts Table 14. We can observe that both NODEDUP and NODEDUP(L)) consistently outperform GSage for Isolated, Lew-degree, and Warm nodes. Compared to NODEDUP(L). NODEDUP is particularly beneficial for this inductive setting.
25

---

Published in Transactions on Machine Learning Research (08/2025)
Table 14: Performance inductive settings (Remaining results of Table 2).
The best result bold, and the runner-up is underlined. Our methods consistently outperform GSage,
GSage
NODEDUP(L)
NODEDUP
Isolated
43.6411.84
45.311o.4
46.06.o.o6
Low-degree
60.061m.ca
60.46...m
61.9412.9
Cora
Warm
60.95+144 1.95+1..0
62.53+1.2
Overall
57 23.aa
57.65+o.8s
59.24+1.02
Isolated
74.34+0.a0
75.42 oo.36
77.80+0.or
Low-degree
75.75+tn.a
77.02 to.0s
81.33
Warm
82.55
83.52 20.00
83.55
Overall
$1.00=0.28
82.01
82.70
Isolated
66.81 10.72
67.03 Lo.51
69.82.1.c
Low-degree
64. 17+2.01
65. 10,100+am 1.79
66.36+0.0
Computers
Warm
68.7610.1
68.78
70.49
Overall
68.5410.4
08.59
70.40
Isolated
68.297
60.60+
70.46
Low-degree
63.0221.51
64,25
68.49
Photos
Warm
70.17
71.05
71.61innet 1:001
Overall
69.9210.77
20.84
71.47:10.7
Table 15: Performance with different encoders (Remaining results of Table 3), where the inner product is the decoder. The best result for each encoder is bold, and the rumner-up is underlined. Our methods consistently outperform the base models, particularly for Isolated and Low-degree nodes.
GAT
NODEDUP(L)
NODEDUP
JKNet
NODEDUP(L)
NODEDUP
Isolated
25.61+1.7
30.73
36.83
30.12
37.44-2.2
43.90
Low-degree
reast
66.76
56.72
59.56
61.93
62.89
Cora
Warm
54.31
55.36
53.704:.9
59.36.1m
57.6741..
Overall
52. 25
53.582m.
53.434x.4
77
58.54g0.m
58.4021.3
Tsolated
33. 38.74gn.0
34.77
41.76go.0 go
54.43
26.38
64.79...0
Low-degree
40
70.9
71.92
73.97
77.77
Warm
78.39
78.67
77.69
82.38 vo.07
83.29
79.20
Overall
77.1626
77.4920.0
77.20an
81.35
82.41
78.91
Isolated
12. 04
44
17.17 =2.22
9.92
25.50
Low-degree
53.60 10
53.62
53.65
62.29
67.21 2m.m
68.49
Computers
Warm
60.19
58. 68.64-an an
58.55 on
69.96 ax
70.90go.o
70.66fge
Overall
60.03 L.19
10.00
58.77
69.77
70.78 10.40
70.55 ro.25
Isolated
15.31
18. 18,03
18.77 23.
12.77aa.4
19.444a.a:
20.56a1.et
Low-degree
43.11
43.40
44.21
57.27
59. 86...on
60.93
Photos
Warm
56. 574474
56.75
56.10
68.35
69.56faa.o
69.60go.0
Overall
55.9144
56.48
55.93
68.09 x>
69.33
69.38
Table 16: Link prediction performance with MLP decoder (Remaining results of Table 4), where GSage is the encoder. Our methods achieve better performance than the base model.
MLP-Dee.
NODEDUP(L)
NODEDUP
Isolated
16.83
37.32
38.41g1.
Low-dogree
58 18.83
64.46:22a
64 64.02+aa
Cora
Warm
58.84
61.57 no.ss
58 eo
Overall
55.57
60.68
58. 28.93
Isolated
5.60
58.68
60.20.ao.e
Low-degree
71.462
78.82
79.58
CS
Warm
84.54
85.88 20.22
20
Overall
02.48
84.96 -0.25
84. +o.22
Isolated
6.13
27.74
26. 26.70
Low-degree
62.5621.34
63.35
Computers
Warm
69.72
70.01.944
68.43
Overall
69.53
69.91=sat
08.30+2.00
Isolated
6.34
18. 15.10.a2.0z 2.02
18.97 11.71
Low-degree
55.63
56.132a..
$5.93
Photos
Warm
70.402o.4
70.67 2.0.00
60. 00..97-.. 2.77
Overall
69.89
69.93....s
69.09 $5.07
26

---

Published in Transactions on Machine Learning Research (08/2025)
GSage
Dropeddge
HDTA LAGNN
TuneUp
Io NodeDup(()
2 NodeDup
100
Cora
Hits
60
Time(s)
40
6.565599871 5.1
0.0
0.0
0.0 0.1
20
Isolated
Low-degree
Warm
Overall
Preprocess
Train
180
144
Hit@@10
80
Time(s)
120
60
60
48
59
40
Isolated
Low-degree
Warm
Overall
Preprocess
Train
200
1
60
Computers
Time(s)
150
163
100
30
60
50
0
Isolated
Low-degree
Warm
Overall
Preprocess
Train
100
60
Photos
72
Hits@110
Time(s)
56
30
50
31
Isolated
Low-degree
Warm
Overall
Prepracess
Train
Evaluated Nodes
Evaluated Time
Figure 12: Performance and time-consuming compared with augmentation methods (Remaining results of Figure 8). The left histograms show the performance results, and the right histograms show the preprocessing and training time consumption of each method.
Table 17: Performance with GCN (Kipf & Welling, 2016a) and GT (Dwivedi Bresson, 2020) encoders, where the inner product is the decoder. The best result for each encoder bold.
GCN
NoN+Node))))))
GCN+ GCN+Nodelly NodeDup
GT
GT++NodeDup())
GT+NoddDDpp
Isolated
40.61
42.93-2.6
48.71
20.93+2 46
38.82
37.40.143
Lowree
83.86
64.6321.60
64.10g.av
58.594a.9
61.164...
20.0
Cora
Warm
60.502ees
61.31
60.26g
58.14g
59.292a.s
59.07200s
Overall
60.16sa44
61.02
a9.90
55.40+o.4
58.344.0.10
58. 38.18+p.42
Isolated
45.5621a0
47.8420.01
50.64.1.18
36.84ga00
51.462047
52.34:1.40
Low-degree
89.37
70.15
71. 0.00
60.21v11s
72.98
73.77 11.07
Citeseer
Waru
74.68
73.26
72.93
71.14 47
74.48
75.08 :..00
Overall
67.4820
67.472n.s
67.67
61.15gr
69.67
70.38
C.11
Ablation study
C.11.1
Performance with various encoders and decoders
For the ablation study, we further explored various encoders and decoders on the remaining datascts. The results are shown in Table 15 and Table 16. From these two tables, we can observe that regardless of the encoders or decoders, both NODEDUP and NODEDuP(L) consistently outperform the base model for Isolated and Low-degree nodes, which further demonstrates the effoctiveness of our methods on cold nodes. Furthermore, NODEDUP(L) consistently achieves better performance compared to the base model for Warm nodes.
27

---

Published in Transactions on Machine Learning Research (08/2025)
Besides GSage, GAT and JKNet, also conducted further experiments with convolutional-based GNNSs, such GCN (Kipf & Welling, 201 and @rrrriiiiTrannformm Transformer) (Dwivedi & Bresson, 2020). The results are shown in Table 17. Our findings indicate that our methods can also improve performance when using GCN and GT as the encoder. However, since GCN uses the same matrix for both self-xepresentationn and neighbor representations our methods only benefit from the supervision aspect. This leads to less pronounced performance improvements on cold nodes compared to using GT and GSage as the encoder. Specifically, NodeDup shows 13.10% improvement for GCN, 60.38% for GT, and 29.79% for GSage on isolated nodes. Moverover, NodeDup(L) on average improves GCN by 5.4%, GT by 62.58%, and GSage by 17.4%.
C.11.2 Performance with SEAL (Zhang & Chen, 2018)
Considering our methods are flexible to integrate with GNN-based link prediction structures, we con- duct the experiments on top of SEAL (Zhang & Chen, 2018) on the Cora and Citeseer datasets. The re- sults are shown in Table 18. We can observe Chat adding NODEDUP on top of SEAL can consistently improve link prediction performance in the Isolated and Low-degree node settings on these two datasets. This further demonstrates the broad applicability of NODEDUP in enhancing the performance of diverse GNN-based link prediction models.
Table 18: Performance with SEAL (Zhang & Chen, 2018) on Cora and Citeseer datasets.
SEAL
SEAL NODEDUP
Isolated
62.20g1m
70.78gmmr
Low-degree
26.
67.70:444
Cora
Warm
56.
54.87
Overall
60.60.a..
60.89
Isolated
56.922a.o
60.3721.m
Low-degree
64.13
65.54:1.4
Citeaeer
Warm
58.81
60.73:2.7
Overall
60.18
63.35
D Implementation Details
In this section, we introduce the implementation details of our experiments. Our implementation can be found at https://github. wtt.ccoo//i.i. zhi CawiichuunooooddDiiii
Parameter Settings. We use 2-layer GNN architectures with 256 hidden dimensions for all GNNs and datasets. The dropout rate set as 0.5. We report the results over 10 random sceds. Hyperparametors were tuned using an early stopping strategy based on performance on the validation set. We manually tune the learning rate for the final results. For the results with the inner product as the decoder, we tune the learning rate over range: Ir E {0.001, 0.0005, 0.0001, 0.00005]. For the results with MLP the decoder, we tune the learning rate over range: Ir E (0.01, 0.005, 0.001, 0.0005}.
Hardware and Software Configuration All methods were implemented in Python 3.10.9 with Pytorch 1.13.1 and PyTorch Geometric (Fey & Lenssen, 2019). The experiments were all conducted on an NVIDIA P100 GPU with 16GB memory.
E Limitations
In our work, NODEDUP and NODEDUP(L) are specifically proposed for LP tasks. Although cold-start is a widespread issue in all graph learning lasks, our proposed methods might not be able to generalize to other tasks, such as node classification, due to their unique design. Furthermore, the two heterophily datasets we usod for evaluation involve graphs where nodes with similar fcatures are assigned different labels. Our methods may struggle on heterophilic graphs where connected nodes have dissimilar features, such molecular networks, which are beyond the scope of this study.
28

---

Published in Transactions on Machine Learning Research (08/2025)
F Ethics Statement
In this work, our simple but effective method enhances the link prediction performance on cold-start nodes, which mitigates the degree bias and advances the fairness of graph machine learning. It can be widely used and beneficial for various real-world applications, such as recommendation systems, social network analysis, and bioinformatics. We do not foresee any negative societal impact or ethical concerns posed by our method. Nonetheless, we note that both positive and negative socictal impacts can be made by applications of graph machine learning techniques, which may benefit. from the improvements induced by work. Care must be taken, in general, to ensure positive socictal and ethical consequences of machine learning.
29


Reviews:
[{"review_id": "jJwGcrUYKT", "reviewer": "Reviewer_mDuZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- The proposed method is simple, intuitive, and easy to implement on any graph.\n\n- Results are consistently strong across datasets.\n\n- Extensive experimental validation of claims. \n\n- The paper is well-written and clear, making the contributions easy to understand.\n\n\n**Weaknesses:**\n\nGlobally, improved performance comes from added supervision (new edge labels: nodes should be linked with themselves) and added compute (more operations and capacity due to increased graph size). The whole graph duplication results -- the best performance across all settings -- confirm this. Random node duplication is also a strong baseline.\n\n- The core practical question to me is: *How do we best allocate duplication under a fixed compute budget?* That is, how can a practitioner selectively duplicate nodes to maximize performance while staying within resource constraints? This is only partially answered in the appendix.\n\n- The same question applies to Nodedup(L), no results are available for whole graph or random node duplication.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors give a very simple graph augmentation method to help with cold-start link prediction. \n\n*Nodedup*: duplicating *cold* nodes — those with few or no connections — leads to improved predictive performances of GNNs on all nodes of the graph, more prevalently in cold nodes.\n\nA simplified version, *Nodedup(L)* replaces duplication with self-edges, leading to improved run-times with similar performance.\n\nA discussion is included explaining the performance gains, making a link with self-distillation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I deem the paper is strong as is, but I would like to see a table comparing performance and computation time between node duplication methods.\n\nI would also very much like to see whole-graph and random duplication results for Nodedup(L).", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xTAhGLbgYm", "reviewer": "Reviewer_Mp7P", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper studies a meaningful and interesting problem to the community.\n2. Extensive experimental evaluation with reasonable number of datasets / baselines.\n3. Compelling performance shows that the algorithm, which is not prohibitively costly, raises performance.\n4. Code is provided.\n\n\nWeaknesses:\n1. While the paper is certainly interesting to a subset of the TMLR community, I think it can be further improved and made accessible to a larger subset of the community.\nTo make the paper more accessible I recommend explaining how we arrive to the problem in the introduction section. The introduction could ease into the problem by approaching it from two directions.\nLink Prediction (which is already done well in the paper) and Continual Learning. Continual / Incremental Learning for graph based recommendation systems is a wide field. While it might not always focus on cold start nodes, it foces on all nodes, complementing the cold start methods that focus on the new ones.\nIn this sense the paper's motivation is enchanced by showing how the practical application of the research may translate to continual deployment of recommendation systems in real world settings.\nSome references:\n- James Kirkpatrick et al., 2017, Overcoming catastrophic forgetting in neural networks. Proc. Natl. Acad. Sci. U.S.A. 114 (13) 3521-3526.\n- Yishi Xu et al., 2020, GraphSAIL: Graph Structure Aware Incremental Learning for Recommender Systems. In Proc. ACM International Conference on Information & Knowledge Management (CIKM '20).\n- Fan Zhou et al., 2021, Overcoming catastrophic forgetting in graph neural networks with experience replay. In Proceedings of the AAAI conference on artificial intelligence (Vol. 35, No. 5, pp. 4714-4722).\n- Antonios Valkanas et al., 2025, Personalized Negative Reservoir for Incremental Learning in Recommender Systems. Transactions on Machine Learning Research.\n\n2. A huge motivator for cold start LP is application to recommender systems. However, this is not sufficiently touched on in the experiments (Cora / Citeseer are basically toy datasets and citation networks in general are not very interesting compared to the larger datasets that mimic industrial settings). Overall it would be nice to see at least a few experiments with classic recommender system datasets such as MovieLens. I believe such an experiment would bolster both the case for the paper's thorough experimental validation as well as the motivational aspect.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "It is known that Graph Neural Networks (GNNs) perform well in Link Prediction (LP) tasks but struggle with low-degree nodes, which is a key issue in applications like recommendation systems. This paper introduces a simple augmentation technique that duplicates low-degree nodes and connects them to their duplicates, improving LP performance by offering a \"multi-view\" representation. NodeDup delivers performance boosts for low-degree and isolated nodes with minimal computational cost and no negative impact on high-degree nodes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses 1, 2 where I outline how the paper's audience reach (motivation) and technical validation (experiments) can be improved. In general, I think the paper is good work and I am positively inclined.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tKn5oiGh8e", "reviewer": "Reviewer_Ai8u", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. The authors introduce a method NodeDup to address the cold-start problem in link prediction, which is simple yet very effective and efficient.\n\n2. The authors introduce a comprehensive analysis of the success of NodeDup, which would benefit the research community.\n\n3. I admire the comprehensive experiments conducted by the authors to verify the effectiveness of NodeDup under various settings.\n\n**Weakness:**\n\n1. Minor: The citation for GRADE in Section C.6 seems to be wrong. To the best of my knowledge, Luo et al. used data augmentation methods to reduce the bias in link prediction instead. Please double check.\n\n2. Why the performance of  SAILOR and GRADE are even worse than GCN on  Low-degree nodes in Table 12? More explanations and analysis are needed in Section C.6.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce a simple yet effective method namely NodeDup by simply duplicating low-degree nodes in the graph, which is lightweight and easy to deploy for multiple link prediction algorithms. The authors also conduct very comprehensive experiments on seven datasets and detailed ablation studies to verify the effectiveness of NodeDup.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Minor: The citation for GRADE in Section C.6 seems to be wrong. To the best of my knowledge, Luo et al. used data augmentation methods to reduce the bias in link prediction instead. Please double check.\n\n2. Why the performance of  SAILOR and GRADE are even worse than GCN on  Low-degree nodes, i.e. tail nodes, in Table 12? More explanations and analysis are needed in Section C.6.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)