Node Duplication Improves Cold-start Link Prediction

Let an attributed graph be $G=\{\mathcal{V},\mathcal{E},\textbf{X}\}$, where $\mathcal{V}$ is the set of $N$ nodes and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the edges where each $e_{vu}\in\mathcal{E}$ indicates nodes $v$ and $u$ are linked. Let $\textbf{X}\in\mathbb{R}^{N\times F}$ be the node attribute matrix, where $F$ is the attribute dimension. Let $\mathcal{N}_{v}$ be the set of neighbors of node $v$, i.e., $\mathcal{N}_{v}=\{u|e_{vu}\in\mathcal{E}\}$, and the degree of node $v$ is $|\mathcal{N}_{v}|$. We separate the set of nodes $\mathcal{V}$ into three disjoint sets $\mathcal{V}_{iso}$, $\mathcal{V}_{low}$, and $\mathcal{V}_{warm}$ by their degrees based on the threshold hyperparameter $\delta$¹¹1This threshold $\delta$ is set as 2 in our experiments, based on observed performance gaps in LP on various datasets, as shown in Figure 1 and Figure 6. Further reasons for this threshold are detailed in Section D.1.. For each node $v\in\mathcal{V}$, $v\in\mathcal{V}_{iso}$ if $|\mathcal{N}_{v}|=0$; $v\in\mathcal{V}_{low}$ if $0<|\mathcal{N}_{v}|\leq\delta$; $v\in\mathcal{V}_{warm}$ if $|\mathcal{N}_{v}|>\delta$. For ease of notation, we also use $\mathcal{V}_{cold}=\mathcal{V}_{iso}\cup\mathcal{V}_{low}$ to denote the cold nodes, which is the union of Isolated and Low-degree nodes.

In this work, we follow the commonly-used encoder-decoder framework for GNN-based LP (Kipf & 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 predicts the link existence probabilities given each pair of node representations. Most GNNs follow the message passing design (Gilmer et al., 2017) that iteratively aggregate each node’s neighbors’ information to update its embeddings. Without the loss of generality, for each node $v$, the $l$-th layer of a GNN can be defined as

where $\bm{h}_{v}^{(l)}$ is the $l$-th layer’s output representation of node $v$, $\bm{h}_{v}^{(0)}=\bm{x_{v}}$, $\text{\small AGG}(\cdot)$ is the (typically permutation-invariant) aggregation function, and $\text{\small UPDATE}(\cdot)$ 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 $\hat{y}_{vu}=\sigma\big{(}\text{\small DECODER}(\bm{h}_{v},\bm{h}_{u})\big{)},$ where $\bm{h}_{v}$ is the GNN’s output representation for node $v$ and $\sigma$ 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(N^{2})$ no-edges is infeasible in practice), where $K$ is the negative sampling rate ($K=1$ usually). We use $\mathcal{Y}=\{0,1\}^{M+KM}$ to denote the training set labels, where $y_{vu}=1$ if $e_{vu}\in\mathcal{E}$ and 0 otherwise.

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 to provide accurate recommendations. 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 in 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 a cold node $v\in\mathcal{V}_{cold}$ and target node $u\in\mathcal{V}$ (w.l.o.g.). 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 research direction.

The implementation of NodeDup can be summarized into four simple steps: (1): duplicate all cold nodes to generate the augmented node set $\mathcal{V}^{\prime}=\mathcal{V}\cup\mathcal{V}_{cold}$, whose node feature matrix is then $\mathbf{X}^{\prime}\in\mathbb{R}^{(N+|\mathcal{V}_{cold}|)\times F}$. (2): for each cold node $v\in\mathcal{V}_{cold}$ and its duplication $v^{\prime}$, add an edge between them and get the augmented edge set $\mathcal{E}^{\prime}=\mathcal{E}\cup\{e_{vv^{\prime}}:\forall v\in\mathcal{V}_{cold}\}$. (3): include the augmented edges into the training set and get $\mathcal{Y}^{\prime}=\mathcal{Y}\cup\{y_{vv^{\prime}}=1:\forall v\in\mathcal{V}_{cold}\}$. (4): proceed with the standard supervised LP training on the augmented graph $G^{\prime}=\{\mathcal{V}^{\prime},\mathcal{E}^{\prime},\textbf{X}^{\prime}\}$ with augmented training set $\mathcal{Y}^{\prime}$. We also summarize this whole process of NodeDup in Algorithm 1 in Appendix C.

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 $O(R^{L}(N+|\mathcal{V}_{cold}|)D^{2})$, 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(R^{L}|\mathcal{V}_{cold}|D^{2})$. For the inner product decoder, we incorporate additionally $|\mathcal{V}_{cold}|$ positive edges and also sample $|\mathcal{V}_{cold}|$ negative edges into the training process, resulting in the extra time complexity of the decoder as $O((M+|\mathcal{V}_{cold}|)D)$. Given that all cold nodes have few ($R\leq 2$ in our experiments) neighbors, and GSage is also always shallow (so $L$ is small) (Zhao & Akoglu, 2019), the overall extra complexity introduced by NodeDup is $O(|\mathcal{V}_{cold}|D^{2}+|\mathcal{V}_{cold}|D)$.

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 short, NodeDup leverages the extra information from an additional “view”. The existing view is when a node is regarded as the anchor node during message passing, whereas the additional view is when that node is regarded as one of its neighbors thanks to the duplicated node from NodeDup.

Aggregation. As described in Section 2.2, when UPDATE$(\cdot)$ and AGG$(\cdot)$ do not share the transformation for node features, GNNs would have separate weights for self-representation and neighbor representations. The separate weights enable the neighbors and the node itself to play distinct 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 a node is regarded as the anchor node during message passing, and the additional view is when that node is regarded as one of its neighbors thanks to the duplicated node from NodeDup. Taking the official PyG (Fey & Lenssen, 2019) implementation of GSage (Hamilton et al., 2017) as an example, it updates node representations using $\bm{h}_{v}^{(l+1)}=\text{W}_{1}\bm{h}_{v}^{(l)}+\text{W}_{2}\bm{m}_{v}^{(l)}$. Here, $\text{W}_{1}$ and $\text{W}_{2}$ correspond to the self-representation and neighbors’ representations, respectively. Without NodeDup, isolated nodes $\mathcal{V}_{iso}$ have no neighbors, which results with $\bm{m}_{v}^{(l)}=\bm{0}$. Thus, the representations of all $v\in\mathcal{V}_{iso}$ are only updated by $\bm{h}_{v}^{(l+1)}=\text{W}_{1}\bm{h}_{v}^{(l)}$. With NodeDup, the updating process for isolated node $v$ becomes $\bm{h}_{v}^{(l+1)}=\text{W}_{1}\bm{h}_{v}^{(l)}+\text{W}_{2}\bm{h}_{v}^{(l)}=(\text{W}_{1}+\text{W}_{2})\bm{h}_{v}^{(l)}$. It indicates that $\text{W}_{2}$ 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 with $\bm{h}_{v}^{(l+1)}=\alpha_{vv}\Theta\bm{h}^{(l)}_{v}+\sum_{u\in\mathcal{N}_{v}}\alpha_{vu}\Theta\bm{h}^{(l)}_{u}$, where $\alpha_{vu}=\frac{\text{exp}(\text{LeakyReLU}(\bm{a}^{\top}[\Theta\bm{h}^{(l)}_{v}||\Theta\bm{h}^{(l)}_{u}]))}{\sum_{i\in\mathcal{N}_{v}\cup v}\text{exp}(\text{LeakyReLU}(\bm{a}^{\top}[\Theta\bm{h}^{(l)}_{v}||\Theta\bm{h}^{(l)}_{i}]))}$. Attention scores in $\bm{a}$ partially correspond to the self-representation $\bm{h}_{v}$ and partially to neighbors’ representation $\bm{h}_{u}$. In this case, neighbor information also offers a different perspective compared to self-representation. Such “multi-view” enriches the representations learned for the isolated nodes in a similar way to how ensemble methods work (Allen-Zhu & Li, 2020). Moreover, apart from addressing isolated nodes, the same mechanism and multi-view perspective also apply to Low-degree nodes.

Supervision. For LP tasks, besides the aggregation, edges also serve as supervised training signals. Cold nodes have few or no positive training edges connecting to them, potentially leading to out-of-distribution (OOD) issues (Wu et al., 2022), especially for isolated nodes. The additional edges, added by NodeDup to connect cold nodes with their duplicates, serve as additional positive supervision signals for LP. More supervision signals for cold nodes usually lead to better-quality embeddings.

Ablation Study. Figure 2 shows an ablation study on these two designs where NodeDup w/o Step (3) indicates only using the augmented nodes and edges in aggregation but not supervision; NodeDup w/o Step (2) indicates only using the augmented edges in supervision but not aggregation. We can observe that using augmented nodes/edges either in supervision or aggregation can significantly improve the LP performance on Isolated nodes, and NodeDup, by combining them, results in larger improvements. Besides, NodeDup also achieves improvements on Low-degree nodes while not sacrificing Warm nodes’ performance.

Recently, Allen-Zhu & Li (2020) showed that the success of self-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, as a simplified and enhanced version of self-distillation for LP tasks for cold nodes, illustrated in Figure 3, in which we draw a connection between self-distillation and NodeDup.

In self-distillation, a teacher GNN is first trained to learn the node representations $\mathbf{H}^{t}$ from original features $\mathbf{X}$. We denote the original graph as $G^{o}$, and we denote the graph, where we replace the node features in $G^{o}$ with $\mathbf{H}^{t}$, as $G^{t}$ in Figure 3. The student GNN is then initialized with random parameters and trained with the sum of two loss functions: $\mathcal{L}_{SD}=\mathcal{L}_{SP}+\mathcal{L}_{KD}$, where $\mathcal{L}_{SP}$ denotes the supervised training loss with $G^{o}$ and $\mathcal{L}_{KD}$ denotes the knowledge distillation loss with $G^{t}$. Figure 4 shows that self-distillation outperforms the teacher GNN across all settings.

The effect of $\mathcal{L}_{KD}$ is similar to that of creating an additional link connecting nodes in $G^{o}$ to their corresponding nodes in $G^{t}$ when optimizing with $\mathcal{L}_{SP}$. This is illustrated by the red dashed line in Figure 3. 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 $\bm{h}_{v}^{t}$ and normalized student embedding $\bm{h}_{v}$, the additional loss term that would be added for distillation with cosine similarity is $\mathcal{L}_{KD}=-\frac{1}{N}\sum_{v\in\mathcal{V}}\bm{h}_{v}\cdot\bm{h}_{v}^{t}$. On the other hand, for the dashed line edges in Figure 3, we add an edge between the node $v$ and its corresponding node $v^{\prime}$ in $G^{t}$ with embedding $\bm{h}_{v^{\prime}}^{t}$. When trained with an inner product decoder and binary cross-entropy loss, it results in the following: $\mathcal{L}_{SP}=-\frac{1}{N}\sum y_{vv^{\prime}}\log(\bm{h}_{v}\cdot\bm{h}_{v^{\prime}}^{t})+(1-y_{vv^{\prime}})\log(1-\bm{h}_{v}\cdot\bm{h}_{v^{\prime}}^{t})$. Since we always add the edge $(v,v^{\prime})$, we know $y_{vv^{\prime}}=1$, and can simplify the loss as follows: $\mathcal{L}_{SP}=-\frac{1}{N}\sum\log(\bm{h}_{v}\cdot\bm{h}_{v^{\prime}}^{t})$. Here, we can observe that $\mathcal{L}_{KD}$ and $\mathcal{L}_{SP}$ are positively correlated as $\log(\cdot)$ is a monotonically increasing function.

To further improve this step and mitigate potential noise in $G^{t}$, we explore a whole graph duplication technique, where $G^{t}$ is replaced with an exact duplicate of $G^{o}$ to train the student GNN. The results in Figure 4 demonstrate significant performance enhancement achieved by whole graph duplication compared to self-distillation. NodeDup is a lightweight variation of the whole graph duplication technique, which focuses on duplicating only the cold nodes and adding edges connecting them to 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.

Inspired by the above analysis, we further introduce a 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 $\mathcal{E}$, that is, $\mathcal{E}^{\prime}=\mathcal{E}\cup\{e_{vv}:\forall v\in\mathcal{V}_{cold}\}$. NodeDup(L) preserves the two essential designs of NodeDup while avoiding the addition of extra nodes, which further saves time and space complexity. Moreover, NodeDup differs from NodeDup(L) since each duplicated node in NodeDup will provide another view for itself because of dropout layers, which leads to different performance as shown in Section 4.2.

NodeDup(L) vs. Self-loop. We remark upon a resemblance between NodeDup(L) and self-loops in GNNs (e.g., the additional self-connection in the normalized adjacency matrix by GCN) as they both add self-loop edges. However, they differ in two aspects. During aggregation: NodeDup(L) intentionally incorporates the self-representation $\bm{h}_{v}^{(l)}$ into the aggregated neighbors’ representation $\bm{m}^{(l)}_{v}$ by adding additional edges. Taking GSage as an example, the weight matrix $\text{W}_{2}$ would serve an extra “view” of $\bm{h}_{v}^{(l)}$ when updating $\bm{h}_{v}^{(l+1)}$, whereas the default self-loops only use information from $\text{W}_{1}$. Additionally, in the supervision signal: different from the normal self-loops and the self-loops introduced in the previous works (Cai et al., 2019; Wang et al., 2020), where self-loops are solely for aggregation, the edges added by NodeDup(L) also serve as additional positive training samples for the cold nodes.

Datasets 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%/10% for testing in IGB-100K, and 10%/20% in other datasets. We follow the standard evaluation metrics used in the Open Graph Benchmark (Hu et 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) and also report MRR performance in Appendix D. We follow Guo et al. (2022b) and Shiao et al. (2022) for the inductive settings, where new nodes appear after the training process.

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 categories 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 issue of the imbalance concerning node degrees. (3) Graph data augmentation methods: Augmentation frameworks including DropEdge (Rong et al., 2019), TuneUP (Hu et al., 2022), and LAGNN (Liu et al., 2022b) typically improve the performance while introducing additional preprocessing or training time.

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 setting, NodeDup achieves an impressive 29.6% improvement, on average, across all datasets. These findings provide clear evidence that our methods effectively address the issue of sub-optimal LP performance on cold nodes.

Table 1 presents the LP performance of various cold-start baselines. For both Isolated and Low-degree nodes, we consistently observe substantial improvements of our NodeDup and NodeDup(L) methods compared to other cold-start baselines. Specifically, NodeDup and NodeDup(L) achieve 38.49% and 34.74% improvement for Isolated nodes on average across all datasets, respectively.

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

Effectiveness Comparison. Since NodeDup and NodeDup(L) use graph data augmentation techniques, we compare them to other data augmentation baselines. The performance and time consumption results are presented in Figure 5 for three datasets (Citeseer, Physics, and IGB-100K), while the results for the remaining datasets are provided in Appendix D due to the page limit. From Figure 5, we consistently observe that NodeDup outperforms all the graph augmentation baselines for Isolated and Low-degree nodes across all three datasets. Similarly, NodeDup(L) outperforms graph data augmentation baselines on 17/18 cases for Isolated and Low-degree nodes. Not only did our methods perform better for Isolated and Low-degree nodes, NodeDup and NodeDup(L) 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 or during model training. For example, LAGNN (Liu et al., 2022b) requires extra preprocessing 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 of preprocessing, they require additional time to drop edges in each training epoch compared to base GNN training. Furthermore, the two-stage training employed by TuneUP 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, NodeDup(L) and NodeDup are 977.0$\times$ and 488.5$\times$ 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 in 8/9 cases. Additionally, NodeDup(L) achieves significant efficiency benefits compared to NodeDup in Figure 5, especially when the number of nodes in the graph increases substantially. Taking the IGB-100K dataset as an example, NodeDup(L) is 1.3$\times$ faster than NodeDup for the entire training process.

Under the inductive setting (Guo et al., 2022b; Shiao et al., 2022), which closely resembles real-world LP scenarios, the presence of new nodes after the training stage adds an additional challenge compared to the transductive setting. We evaluate and present the effectiveness of our methods under this setting in Table 2 for Citeseer, Physics, and IGB-100K datasets. Additional results for other datasets can be found in Appendix D. In Table 2, we observe that our methods consistently outperform base GSage across all of the datasets. We also observe significant improvements in the performance of our methods on Isolated nodes, where NodeDup and NodeDup(L) achieve 5.50% and 3.57% improvements averaged across the three datasets, respectively. Additionally, NodeDup achieves 5.09% improvements on Low-degree nodes. NodeDup leads to more pronounced improvements on Low-degree/Isolated nodes, making it particularly beneficial for the inductive setting.

As a 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 JKNet (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 D. When applying NodeDup to base LP 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. Meanwhile, we note that the improvement achieved with our methods is more pronounced when using JKNet as the encoder compared to GAT. This can be attributed to the more informative multi-view provided by JKNet during the aggregation step, as discussed in Section 3.2.

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 supervised 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 specific challenges presented by isolated nodes.