Layer-diverse Negative Sampling for Graph Neural Networks

A determinantal point process (DPP) $\Psi$ is a probability measure on all possible subsets of the ground set $\displaystyle{\mathbb{Y}}$ with a size of $2^{\left|\displaystyle{\mathbb{Y}}\right|}$. For every subset ${\displaystyle{\mathbb{Y}}}_{\rm sub}\subseteq{\displaystyle{\mathbb{Y}}}$, a DPP (Hough et al., 2009) defined via a positive semidefinite $\displaystyle{\bm{L}}$ matrix is formulated as

where $\det(\cdot)$ denotes the determinant of a given matrix, $\displaystyle{\bm{L}}$ is a real and symmetric $|\displaystyle{\mathbb{Y}}|\times|\displaystyle{\mathbb{Y}}|$ matrix indexed by the elements of $\displaystyle{\mathbb{Y}}$, and $\det(\displaystyle{\bm{L}}+\displaystyle{\bm{I}})$ is a normalisation term that is constant once the ground dataset $\displaystyle{\mathbb{Y}}$ is fixed.

DPP has an intuitive geometric interpretation. If we have a $\displaystyle{\bm{L}}$, there is always a matrix $\displaystyle{\bm{B}}$ that satisfies $\displaystyle{\bm{L}}={\displaystyle{\bm{B}}}^{\top}{\displaystyle{\bm{B}}}$. Let ${\displaystyle{\bm{B}}}_{i}$ be the columns of ${\displaystyle{\bm{B}}}$. A determinantal operator can then be interpreted geometrically as

where the right-hand side of the equation is the squared $\left|{\displaystyle{\mathbb{Y}}}_{\rm sub}\right|$-dimensional volume of the parallelepiped spanned by the columns of $\displaystyle{\bm{B}}$ corresponding to the elements in ${\displaystyle{\mathbb{Y}}}_{\rm sub}$. Intuitively, diverse sets are more probable because their feature vectors are more orthogonal and span larger volumes. (See the more details in Appendix A.1)

Let ${\displaystyle{\mathcal{G}}}=\left({\displaystyle{\mathbb{V}}},{\displaystyle\mathbb{E}}\right)$ denote a graph with node features ${\displaystyle{\bm{h}}}_{i}$ for $i\in{\displaystyle{\mathbb{V}}}$, where ${\displaystyle{\mathbb{V}}}$ and ${\displaystyle\mathbb{E}}$ are the sets of nodes and edges. Let $N:=\left|{\displaystyle{\mathbb{V}}}\right|$ denote the number of nodes. GNNs aggregate information via message-passing (Geerts et al., 2021), where each node $i$ repeatedly receives information from its first-order neighbours ${\displaystyle{\mathbb{N}}}_{i}$ to update its representation as

where $\text{deg}(\cdot)$ is the degree of the node. Introducing negative samples can improve the quality of the node representations and alleviate the over-smoothing problem (Chen et al., 2020; Rong et al., 2020; Duan et al., 2022). The new update to the representations is formulated as

where $\overline{\displaystyle{\mathbb{N}}}_{i}$ are the negative samples of node $i$, and $\displaystyle\mu$ is a hyper-parameter to balance the contribution of negative samples.

The current state-of-the-art approaches for selecting negative samples $\overline{\displaystyle{\mathbb{N}}}_{i}$ used in Eq. (4) are the DPP-based methods (Duan et al., 2022; 2023). Intuitively, good negative samples for a node should have different semantics while containing as complete knowledge of the whole graph as possible. Since the sampling procedure in the DPP requires an eigendecomposition, the computational cost for once sampling from a $N$ nodes set could be $O(|N|^{3})$, and the total becomes an excessive $O(|N|^{4})$ for sampling $N$ times (all nodes). Thus, the large size of candidates found from exploring the whole graph to find negative samples would make such an approach impractical, even for a moderately sized graph.

To reduce the computational complexity, the shortest-path-based method (Duan et al., 2023) is first used to form a smaller but more effective candidate set ${\displaystyle{\mathbb{S}}}_{i}$ for node $i$, which is detailed in Algorithm 1. Using this method, the computational cost is approximately $O((P\cdot\overline{\text{deg}})^{3})$, where $P\ll N$ is the path length (normally smaller than the diameter of the graph) and $\overline{\text{deg}}\ll N$ is the average degree of the graph. As an example, consider a Citeseer graph (Sen et al., 2008) with 3,327 nodes and $\overline{\text{deg}}=2.74$. When using the experimental setting shown below, where $P=5$, we observe that $O(N^{3})=3.6\times 10^{10}$, which is significantly larger than $2571=O((P\cdot\overline{\text{deg}})^{3})$.

After obtaining the candidate set ${\displaystyle{\mathbb{S}}}_{i}$, the subsequent step involves effectively leveraging the characteristics of the graph to devise the computation method for the $\displaystyle{\bm{L}}$ matrix. As a major fundamental technique of DPP, Quality-Diversity decomposition is used to balance the diversity against some underlying preferences for different items in $\displaystyle{\mathbb{Y}}$ (Kulesza & Taskar, 2012). Since $\displaystyle{\bm{L}}$ can be written as $\displaystyle{\bm{L}}={\displaystyle{\bm{B}}}^{\top}{\displaystyle{\bm{B}}}$, each column of ${\displaystyle{\bm{B}}}$ is further written as the product of a quality term ${\displaystyle{\bm{q}}}_{\bar{j}}\in{\displaystyle{\mathbb{R}}}^{+}$ and a vector of normalized diversity features $\bm{\phi}_{\bar{j}}\in{\displaystyle{\mathbb{R}}}^{D}$,$\left\|\bm{\phi}_{\bar{j}}\right\|=1$. The probability of a subset is the square of the volume spanned by ${\displaystyle{\bm{q}}}_{\bar{j}}\bm{\phi}_{\bar{j}}$ for $\bar{j}\in\displaystyle{\mathbb{Y}}$. Hence, ${\displaystyle{\bm{L}}}$ for the given node $i$ now becomes

where $\bar{j},{\bar{j}^{\prime}}\in{\displaystyle{\mathbb{S}}}_{i}$ are two candidate negative nodes.

Utilizing the Quality-Diversity decomposition of DPP, we use the node feature representations and graph structural information to calculate ${\displaystyle{\bm{L}}}$ for the intended sample selection. Specifically, following the Duan et al. (2023), all the nodes ${\displaystyle{\mathbb{V}}}$ in a graph $\displaystyle{\mathbb{G}}$ are first divide into $Q$ communities, denoted as ${\displaystyle{\mathbb{V}}}=\left\{{\displaystyle{\mathbb{V}}}^{com}_{q}\right\}_{q=1}^{Q}$, using Fluid Communities method (Parés et al., 2017). Then, the features of each community ${\displaystyle{\mathbb{V}}}^{com}_{q}$ and each candidate set ${\displaystyle{\mathbb{S}}}_{i}$ are extracted from the node representations ${\displaystyle{\bm{h}}}_{i}$ via

With the Eq. (6), the quality terms in Eq. (5) will be defined as:

where ${\displaystyle{\bm{a}}}_{i},{\displaystyle{\bm{a}}}_{\bar{j}},{{\displaystyle{\bm{a}}}_{\bar{j}^{\prime}}}$ represents the feature expression of the node belonging to its community, ${\displaystyle{\bm{b}}}_{i}$ denotes the features of the candidate set ${\displaystyle{\mathbb{S}}}_{i}$ and the $\odot$ means point-wise product. These quality terms ensure the candidate node $\bar{j}$ is not similar to the given node $i$. The diversity term in Eq. (5) is defined as

which ensures that there are sufficient differences between every pair of candidate nodes $\bar{j}$ and $\bar{j}^{\prime}$.

Due to the primary focus of this paper not being on the computation of the $\displaystyle{\bm{L}}$ matrix, additional details can be referenced in Duan et al. (2022; 2023). Although the above method ensures good diversity for each layer, there is still plenty of redundancy across the layers because the negative samples in each layer are treated as being independent.

Given a node $i$ and its candidate negative sample set ${\displaystyle{\mathbb{S}}}_{i}$¹¹1${\displaystyle{\mathbb{S}}}_{i}$ denotes all non-neighbour nodes of $i$ in the graph in theory, but we follow Duan et al. (2022; 2023) to reduce its size by the Algorithm 1.. ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l}\in{\displaystyle{\mathbb{S}}}_{i}$ and ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l+1}\in{\displaystyle{\mathbb{S}}}_{i}$ denote the negative samples for node $i$ in a multi-layer GNNs collected from layers $l$ and $l+1$, respectively, as illustrated in Figure 1. Our goal is to reduce the overlap between ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l}$ and ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l+1}$ to cover as much negative information in the graph as possible while retaining an accurate representation of $i$. Note that ${\displaystyle{\mathbb{S}}}_{i}$ could be seen geometrically as a space spanned by the node representations, while ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l}$ is just a subspace of this space spanned by the selected negative samples/representations. Inspired by this geometric interpretation of negative sampling, our idea is to squeeze this space for negative sampling at layer $l+1$ conditioned on obtained ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l}$ to reduce the probability of re-picking the samples in ${\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l}$.

To be specific, an eigendecomposition is first performed on $\displaystyle{\bm{L}}$ from Eq. (5) of ${\displaystyle{\mathbb{S}}}_{i}=\left\{\bar{j}_{1},...,\bar{j}_{S}\right\}$, which yields the eigenvalues $\displaystyle{\mathbb{U}}=\left\{\lambda_{1},...,\lambda_{S}\right\}$ and the eigenvectors ${\displaystyle{\mathbb{T}}}=\left\{\bm{v}_{1},...,\bm{v}_{S}\right\}$. Here, ${\displaystyle{\mathbb{T}}}$ is an orthogonal basis for the space of ${\displaystyle{\mathbb{S}}}_{i}$ since ${\displaystyle{\bm{L}}}$ is a real and symmetric matrix. All the eigenvectors compose a new matrix denoted as ${{\displaystyle{\bm{V}}}}^{S\times S}=\left[{{\displaystyle{\bm{v}}}}_{1},...,{\displaystyle{\bm{v}}}_{S}\right]$, where each row corresponds to a node in ${\displaystyle{\mathbb{S}}}_{i}$, and ${\displaystyle{\bm{V}}}[\bar{j},:]$ is also the impacts/contributions of the node $\bar{j}$ on each eigenvector. The probability of picking node $\bar{j}$ through the DPP sampling is then proportional to $\displaystyle||{\bm{V}}[\bar{j},:]||_{2}$. Given ${\overline{{{\displaystyle{\mathbb{N}}}}_{i}}}^{l}$, the goal is reduce the information of any $\bar{j}^{*}\in{\overline{{\displaystyle{\mathbb{N}}}_{i}}}^{l}$ in space ${\displaystyle{\bm{V}}}$. To this end, the eigenvector/basis of node $\bar{j}^{*}$ that makes the greatest impact/contribution is identified as:

The space ${\displaystyle{\bm{V}}}$ along the $m$ direction is then squeezed by

where $\otimes$ denotes the outer product and $\gamma\in(0,1)$ is the weight of the squeezing. The outer product can be thought of as a way to "stretch" every vector of node $\bar{j}^{*}$ along the ${\displaystyle{\bm{V}}}[:,m]$-direction. Since $m$ in Eq. (10) implies that the node $\bar{j}^{*}$ has the strongest influence on this eigenvector/direction, it helps to reduce the contribution of the node $\bar{j}^{*}$ at $m$-direction to all vectors as much as possible. It is worth noting about Eq. (10) that:

After obtaining the layer-diverse vector matrix ${\displaystyle{\bm{V}}}^{\prime}$, we employ $k$-DPP for negative sampling. $k$-DPP is a generalization of the DPP for sampling a fixed number of items, rather than a variable number. By setting the value of $k$, we can effectively control the number of negative samples obtained through sampling. (See the more details in Appendix A.1) The process of layer-diverse negative sampling for node $i$ is outlined in Algorithm 2. The most significant difference lies in the original input of $k$-DPP is eigenvector matrix ${\displaystyle{\bm{V}}}$, while the input of Algorithm 3 is layer-diverse matrix ${\displaystyle{\bm{V}}}^{\prime}$. Our method can be used for all layers by collecting all negative samples before a given layer as the candidate set. To reduce the computational cost, two consecutive layers are used in the following experiments.

To better illustrate our method, a three-dimensional example is shown in Figure 2, where the candidate set contains three nodes and the size of ${\displaystyle{\bm{V}}}$ is $3\times 3$. Figure 2(a) shows that the original space is spanned by ${{\displaystyle{\bm{v}}}_{1},{\displaystyle{\bm{v}}}_{2},{\displaystyle{\bm{v}}}_{3}}$, with the eigenvectors $\{{\displaystyle{\bm{V}}}[:,y]\}_{y=1,2,3}$. Suppose node $1$ has the highest impact on ${\displaystyle{\bm{v}}}_{1}$, that is $1=\arg\max{\displaystyle{\bm{V}}}[:,1]$. The space along the ${\displaystyle{\bm{v}}}_{1}$-direction then squeezes, as we can observe in Figure 2(b). The original space finally turns to the new space in Figure 2(c), where the magnitude of the $\bm{v}_{1}$ component is significantly reduced and the probability of choosing the corresponding nodes (including node $1$) becomes smaller.

Although there is a limited number of works having investigated the use of negative samples for GNNs, the exact benefits of using such samples remain largely unexplored. To better understand the impact of negative samples, we give examples and discussions on their effects on GNNs expressivity and over-squashing. Our results show that negative samples have a strong potential to improve GNNs expressivity and reduce the degree of over-squashing.

Datasets. We first conducted our experiments with seven homophilous datasets for semi-supervised node classification, including citation network: Citeseer, Cora and PubMed (Sen et al., 2008), Coauthor networks: CS (Shchur et al., 2018), Amazon networks: Computers and Photo (Shchur et al., 2018), and Open Graph Benchmark: ogbn-arxiv (Hu et al., 2020). Then, we expanded our experiments to three heterophilous datasets, including Cornell, Texas, and Wisconsin Craven et al. (1998).

Baselines. For homophilous datasets, we compared our framework to four GNN baselines: GCN (Kipf & Welling, 2017), GATv2 (Brody et al., 2022), SAGE (Hamilton et al., 2017), GIN-$\epsilon$ (Xu et al., 2019), and AERO (Lee et al., 2023). We also compared existing GNN models with negative sampling methods. RGCN (Kim & Oh, 2021) selects negative samples in a purely random manner. MCGCN (Yang et al., 2020) selects negative samples using Monte Carlo chains. PGCN (Ying et al., 2018) uses personalised PageRank. D2GCN (Duan et al., 2022) calculates the $\bm{L}$-ensemble using node representations only and does not take into account the diversity of the samples found across layers. Once the negative samples were obtained using these methods, they were integrated into the convolution operation using Eq. (4). For heterophilous datasets, to ensure a comprehensive analysis, we tested the layer-diverse negative sampling method across multiple graph neural network architectures, both in 2-layer and 4-layer configurations. The architectures tested include GCN (LD-GCN), GATv2 (LD-GATv2), GraphSAGE (LD-SAGE), and GIN (LD-GIN).

Experimental setup. We selected 1% of the nodes for negative sampling in each network layer. The datasets were divided consistently with Kipf & Welling (2017). Further information on the experimental setup and hyperparameters can be found in Appendix A.3.

Results on homophilous datasets. The results reported are the average accuracy values of the node classification after 10 runs, shown in Figure 7 for layers 2 to 6 and the detailed values for layer 4 are presented in Table 1. The results indicate that our model outperforms the other models. It performed better than the state-of-the-art GCN variants: GraphSAGE, GATv2, GIN-$\epsilon$, and AERO. Unlike these methods, LDGCN incorporates both neighbouring nodes (positive samples) and negative samples obtained by our method into message passing. Although RGCN, MCGCN, and PGCN also incorporate negative samples into the convolution operation, they have not shown consistent performance across various datasets. D2GCN does not utilize layer-diverse sampling to reduce the chances of selecting the same nodes in consecutive layers. Consequently, the negative samples identified by this method contain less information about the overall graph, impeding graph learning.

Results on heterophilous datasets. The results of the 2-layer are shown in Table 2. On the Cornell dataset, our LD-GCN model outperformed the standard GCN by approximately 6.84%. In Texas, the LD-GATv2 model showed an improvement of 11.32% over the standard GATv2. For Wisconsin, LD-SAGE exceeded the performance of standard GraphSAGE by 5.82%. Furthermore, the 4-layer model results (Table 3) are consistent with the improved performance observed in the 2-layer models, suggesting that our layer-diverse negative sampling method contributes positively across different model depths.

Heterophilous graphs are characterized by their tendency to connect nodes with dissimilar features or labels. This starkly contrasts the homophilous nature typically assumed in many GNN designs. This heterophily implies a diverse neighbourhood for each node, which can challenge learning algorithms that rely on the assumption that ’neighbouring nodes have similar labels or features’.

Our layer-diverse negative sampling method is well-suited for such graphs for several reasons:

• •

  DPP-based sampling within layers: Our method uses DPP-based sampling to ensure diversity within each layer of the graph. This approach is crucial for heterophilous graphs, where it’s important to capture a wide range of node characteristics within the same layer.

• •

  Layer-diverse enhancement: We enhance diversity between layers and reduce overlap, allowing for richer information capture across the graph. This method is particularly effective in heterophilous graphs, where nodes with similar properties may not be close in the graph’s topology.

• •

  Improved node representation learning: Our approach effectively learns node representations by distinguishing between similar and dissimilar neighbors. This is key in heterophilous graphs, where traditional GNNs might struggle due to the uniformity in their aggregation and update processes.

• •

  Structural insight: Our method offers more structural insight into the graph by allowing the GNN to learn from a wider range of node connections, thus avoiding the pitfall of homogeneity in the learning process.

We believe that these results and our analysis of the structural properties of heterophilous graphs demonstrate the applicability and advantages of our layer-diverse negative sampling method in a broader range of graph types. This strengthens the case for our approach as a versatile tool in the GNN toolkit, capable of addressing the challenges presented by both homophilous and heterophilous graphs.

This section presents a comparison of our LDGCN model with the previous D2GCN (Duan et al., 2022) to demonstrate that our approach effectively reduces the overlap rate of negative samples in terms of both nodes and clusters, and that these samples are more beneficial for graph learning.

Datasets. Three of seven previous datasets were chosen to test this claim: the citation network Cora, the coauthor network CS, and the Amazon network Computers. The average degrees of the three datasets are 3.90, 8.93 and 35.76, respectively. This difference in density facilitates the comparison of the two methods in different graph datasets.

Setup. We repeated the experiments using both 1% and 10% of the nodes selected for negative sampling. Our aim was to show that: (1) the layer-diverse projection method can identify a set of negative samples with reduced overlap between layers and less redundant information; (2) an efficient sampling method can achieve better performance with fewer central nodes.

Metric. In addition to utilizing accuracy to display the final prediction results, we developed two metrics to evaluate the overlap rate of the selected samples: the Node Overlap Rate $(\text{OVR}_{\rm node})$ and Cluster Overlap Rate $(\text{OVR}_{\rm cls})$. $\text{OVR}_{\rm node}$ assesses the average overlap of the samples in the last and current layers of the network, defined by

where ${\displaystyle{\mathbb{V}}}_{c}$ are the central nodes performing the negative sampling, and $L$ is the number of network layers.

In addition to selecting diverse nodes, it is crucial that the selected nodes come from different clusters, as shown in Figure 1. In the context of semi-supervised learning with GNNs, we assume that the true labels of all nodes are currently unknown. Therefore, we employ K-Means to partition all nodes $\displaystyle{\mathbb{V}}$ into $K$ clusters $\displaystyle{\mathbb{V}}=\cup_{k=1}^{K}{\displaystyle{\mathbb{K}}}_{k}$ after each layer. This ensures that the negative samples $\overline{\displaystyle{\mathbb{N}}}_{i}^{l}$ for each layer belong to different clusters ${\displaystyle{\mathbb{K}}}_{k}$ and form the cluster set $\overline{\displaystyle{\mathbb{C}}}_{i}^{l}$. Then, we define $\text{OVR}_{\rm cls}$ to measure the overlap of the cluster sets between layers:

Results. Table 4, 5, and 6 illustrate the various overlap rates for the two methods on three datasets. To evaluate the cluster overlap rate, the number of clusters $K$ was set to: (a) the actual number of classes, denoted as $\text{OVR}_{\rm cls}$, and (b) 5 times the actual number of classes, denoted as $\text{OVR}_{5\times\text{\rm cls}}$. On all three datasets, we found that in comparison to D2GCN, LDGCN not only significantly decreased the node overlap rate but also reduced the repetition rate of the clusters to which the nodes belong. An interesting observation is that when we increased the number of clusters from the actual number of classes to 5 times the actual number of classes, LDGCN saw a further significant reduction in the sample overlap rate, while D2GCN only saw a slight reduction.

One possible explanation is that within each class, nodes can be further clustered. For instance, in the citation network, articles classified as machine learning can be further divided into articles on CNNs, GNNs, etc. Our layer-diverse method is designed to find the most diverse samples possible, even when searching within the same class, such as those belonging to these more specific clusters. In contrast, D2GCN consistently selects negative samples from the same cluster. These results demonstrate that LDGCN provides more useful information about the entire graph for feature extraction than D2GCN during message passing.

We evaluated the accuracy of LDGCN and D2GCN on the Cora, Computers, and CS datasets using different negative sampling rates. As shown in Figure 8, LDGCN demonstrated superior performance on all three datasets using both 1% and 10% of nodes for sampling. Examining the 1% experiment, where fewer nodes were used for negative message passing, we found that the selected nodes were meaningful enough to aid in graph learning. LDGCN maintained consistent performance even with a reduced sampling rate, while D2GCN’s performance decreased significantly.

This section presents an investigation of applying our layer-diverse sampling method to different GNN architectures on the Cora, CS and Computers datasets, which have different graph densities.

Setup. Besides GCN (Kipf & Welling, 2017), layer-diverse sampling method was applied to GATv2 (Brody et al., 2022), SAGE (Hamilton et al., 2017) and GIN-$\epsilon$ (Xu et al., 2019), which were called LDGATv2, LDSAGE, LDGIN-$\epsilon$ seperately in the following. We repeated the experiments using 1% of the nodes selected for negative sampling. The layers of different models are set as $\{2,4,6,8,16,32\}$. Our aim was to show that: the layer-diverse negative sampling is applicable to different GNN architectures and helps theses models to relieve the over-smoothing problem so that to achieve better results when the layers of the model become deeper.

Results. The results are shown Table.7, 8 and 9, which compare the performance of GNN architectures with and without layer-diverse negative sampling methods on the Cora and CS datasets. It’s clear that layer-diverse methods (LDGCN, LDGATv2, LDSAGE, LDGIN) consistently outperform their counterparts without layer-diverse methods (GCN, GATv2, SAGE, GIN) across all layer sizes for both datasets. Although as the layers in the network increased, all models showed a trend of decreasing accuracy, layer-diverse methods consistently performed better, implying that these methods enhance the effectiveness of GNNs in capturing informative samples for learning better graph representations. For example, LDGATv2 outperforms GATv2 on CS, with the highest performance improvement observed in Layer 6 (from 52.19 to 75.59); LDSAGE outperforms SAGE in all layer sizes on Computers, with the highest performance improvement observed in Layer 6 (from 21.59 to 63.87).

Interestingly, it was observed that GIN failed to converge for all layer settings on the Computers dataset. As a result, the layer-diverse method, which had consistently shown improvements on other GNN architectures, couldn’t enhance the performance of GIN on the Computers dataset. This outcome underlines the fact that the layer-diverse approach may not be universally applicable or beneficial for all GNN architectures and datasets and that individual characteristics of the networks and the data can play a significant role.

In summary, the layer-diverse negative sampling methods have consistently improved performance across various architectures and datasets, supporting their effectiveness in graph-based learning tasks. They have potential for further exploration in other tasks or architectures, and could be a promising direction for improving the performance of GNNs, especially those with multiple layers.

Over-smoothing. To measure the smoothness of the graph representations, we employed the Mean Average Distance (MAD) metric (Chen et al., 2020), which was computed as $\hbox{MAD}=\frac{\sum_{i}D_{i}}{\sum_{i}1\left(D_{i}\right)}$, where $D_{i}=\frac{\sum_{j}{\displaystyle{\bm{D}}}_{ij}}{\sum_{j}1\left({\displaystyle{\bm{D}}}_{ij}\right)}$, and ${\displaystyle{\bm{D}}}_{ij}=1-\cos(x_{i},x_{j})$ is the cosine distance between the nodes $i$ and $j$. Our comparison between LDGCN and other negative sampling methods are presented in Table 10 and Table 11. As can be seen from these results, LDGCN’s MAD is higher than the other methods on all datasets. All the negative sampling methods, except for GCN, had relatively high MADs, indicating that adding negative samples to the message passing increases the distance between nodes. These results confirm our argument in Section 3.2 that incorporating negative samples into the convolution increases the upper bound of the distance between nodes.