Layer-diverse Negative Sampling for Graph Neural Networks
Authors: Wei Duan
Jie Lu
Yu Guang Wang
Junyu Xuan
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) are a powerful solution for various structure learning applications due to their strong representation capabilities for graph data. However, traditional GNNs, relying on message-passing mechanisms that gather information exclusively from first-order neighbours (known as positive samples), can lead to issues such as over-smoothing and over-squashing.
To mitigate these issues, we propose a layer-diverse negative sampling method for message-passing propagation. This method employs a sampling matrix within a determinantal point process, which transforms the candidate set into a space and selectively samples from this space to generate negative samples. To further enhance the diversity of the negative samples during each forward pass, we develop a space-squeezing method to achieve layer-wise diversity in multi-layer GNNs. Experiments on various real-world graph datasets demonstrate the effectiveness of our approach in improving the diversity of negative samples and overall learning performance. Moreover, adding negative samples dynamically changes the graph's topology, thus with the strong potential to improve the expressiveness of GNNs and reduce the risk of over-squashing.

Published in Transactions on Machine Learning Research (03/2024)
Layer-diverse Negative Sampling for Graph Neural Networks
Wei Duan
wei. veeiddaann@studeeve uts. aadd..eddu.ar
Australian Artificial Intelligence Institute University of Technology Sydney
Jie Lu
jie.lu edu. au
Australian Artificial Intelligence Institute University of Technology Sydney
Yu Guang Wang
Institute of Natural Sciences
School of Mathematical Sciences Shanghai Jiao Tong University
Junyu Xuan
jureyu.naan@ulee edu on
Australian Artificial Intelligence Institute University of Technology Sydney
Reviewed OpenReview: https: https://openrevveau openreview.
net/ formm id= WOrdokbuh6
Abstract
Graph neural networks (GNNs) are a powerful solution for various structure learning appli- cations due to their strong representation capabilities for graph data. However, traditional GNNs, relying message-passnng mechanisms that gather information exclusively from first-order neighbours (known as positive samples), can lead to issues such over-smoothing and over-squashing To mitigate these issues, we propose a layer-diverse negative sampling method for message-passingg propagation. This method employs a sampling matrix within a determinantal point process, which transforms the candidate set into a space and selectively samples from this space to generate negative samples. To further enhance the diversity of the negative samples during each forward pass, we develop a space-squeezing method to various real-world graph
achieve layer-wise diversity in multi-layer GNNs. Experiments datasets demonstrate the effectiveness of our approach in improving the diversity of negalive samples and overall learning performance, Moreover, adding negative samples dynamically changes the graph's topology, thus with the strong potential to improve the expressiveness of GNNs and reduce the risk of over-squashing
1 Introduction
Graph neural networks (GNNs) have emerged as a formidable tool for various applications of structure learning, including drug discovery (Sun et al.) 2020 recommendation systems YYu & Qin 2020), and traffic prediction (Lan et al. 2022). owing their strong representation learning power. GNNs propagate the learning of nodes through message-passing mechanism (Geerts et al.) 2021 that conveys and aggregates information from neighbouring nodes, known first-order neighbours. The message passing is based on the assumption that neighbours of node have similar representations. The common practice of updating node
representations solely with positive samples in most GNNs (Kipf & Welling 2017 Xu et al. 2019 Brody
el al. 2022), can have three limitations: 1) Over-smoothing (Chen el. al.) 2020 Rong et. al.
2020 Zhao &
Akoglu 2020 where the node representations become less distinct as the number of layers increases; 2) GNNs expressivity (Xu al. 2019), where becomes difficult. distinguish different graph topologics after aggregation; and 3) Over-squashing (Alon & Yahav 2021 Topping al.] 20022 Karhadkar et al. 2022).
where bottlenecks exist and limit the information passing between weakly connected subgraphs.

---

Published in Transactions on Machine Learning Research (03/2024)
Layer
Layer
Given
samples
Selected nodes different length patt get candidate
Candidate
Different negative samples in each layer
(b)
(c)
Figure 1: Negative samples from layer-diverse DPP sampling. (a) For a given node in a graph, its first-order neighbours can thought as positive samples, despite the fact that these neighbours may belong to different clusters. (b) Algorithm [ calculates the shortest path from a given node other nodes in the graph to obtain smaller, yet more efficient candidate sets for further sampling. (c) As the candidate set is significantly larger than the number of negative samples needed, the ideal subset of negative samples is not unique. By using the layer-diverse DPP sampling method to select negative samples, it is possible to include as much information from the entire graph as possible while also reducing redundancy among negative samples in different layers.
In addition to a node's positive samples, there are many other non-neighbouring nodes that can pro- vide diverse and valuable information for updating the representations. Unlike neighbouring nodes, non- neighbouring nodes typically have distinct representations compared the given node and are referred as negative samples (Duan et al. p022p. While is crucial to select appropriate negative samples, only a few studics have given adequate attention to this aspect of negative sampling.
It is believed that the ideal negalive samples should contain enough informalion aboud the enlire graph without including a large amount of redundant information. However, a remaining issue is that all previous approaches treat the nogative samples in each layer as independent. Thus, from a holistic perspective, the negative samples obtained still contain a considerable amount of redundancy. In fact, experiments show that the overlap between the node samples for different layers obtained by Duan al. (2022) more than 75%, as outlined in further detail in Section 4.2
To address the issue of redundant information in negative samples, propose approach called layer- diverse negative sampling that utilizes the technique of space squeezing. This method is designed to obtain meaningful information with a smaller number of samples (as illustrated by Figure D Specifically, our method utilizes the sampling matrix DPP to transform the candidate set into a space. The dimension of the space the number of nodes the candidate set, with each node represented as a vector in this space. We then apply the space squcezing technique during sampling. which eliminates the dimensions corresponding to the samples of the last layer, thus significantly reducing the probability of selecting those samples again. These negative samples then utilized in message passing in GCN, resulting in new model called Layer-diverse GCN, or LDGCN in short.
The effectiveness of the LDGCN model has been demonstrated through extensive experimentation on seven publicly available benchmark datasets. These experiments have shown that LDGCN consistently achieves excellent performance across all datascts. We provide detailed discussion on why the use of layer-diverse DPP sampling for negative samples may improve learning ability by improving GNNs expressivity and reducing the risk of over-squashing. Our main contributions twofold:
2

---

Published in Transactions on Machine Learning Research (03/2024)
We propose method for layer-diverse negative sampling that utilizes space squeezing to effectively reduce redundancy in the samples found and enhance the overall performance of the model.
We empirically demonstrate the effectiveness of the proposed method in enhancing the diversity of layer-wise negative samples and overall node representation learning performance, and we also show the great potential of negative samples in improving GNNs expressivity and reducing the risk of over-squashing.
2 Preliminaries
2.1 Determinantal Point Processes (DPP)
A determinantal point process (DPP) V is a probability measure all possible subsets of the ground set Y with size of 2 For every subset Yau S WYa. DPP Hough et al. 2009) defined via a positive semidefinite L matrix is formulated as
DPP
del (Ly aab
V L (Msub) d I)
(1)
where det(-) denotes the determinant of given matrix, L is real and symmetric | Y matrix indexed by the elements of Y, and del + I) is normalisation term that is constant once the ground dataset Y is fixed.
DPP has an intuitive geometric interpretation. If we have a L, there is always a matrix B that satisfies L = B B. Let B; be the columns B. determinantal operator can then be interpreted geometrically
as
L subb & det (Iy,,)
vol vol? = ((Bilre
(2)
where the right-hand side of the equation the squared |Y -dmmenniinii volume of the parallelepiped spanned by the columns of B corresponding to the elements in Ysub. Intuitively, diverse sets probable because their feature vectors are more orthogonal and span larger volumes. (See the more details in Appendix A.1
2.2 Negative Sampling for GNNs
Let G EV denote graph with node features h, for i E V, where V and E are the sets of nodes and edges. Let N ; | denote the number of nodes. GNNs aggregate information via message-passing (Geerts ct al. 2021). , where cach node repeatedly reccives information from its first-order neighbours N; to update its representation as
h
SEN.uG) Vdeg(() deg(j) (w) 1
Σ
(3)
where deg(-) 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
h/'= Σ
deg(i) ddg(() (w' h
(111))
Σ jeN,
deg(i) deg(() (wo h (-1))).
JEN.u()
where N, are the negative samples of node i, and a is a hyper-parameter to balance the contribution of negative samples.
The current art approaches for selecting negative samples N, used in Eq. (4) are the DPP-baser methods (Duan et al. 20022 2023). Intuitively, good negative samples for node should have different semantics while containing as complete knowledge of the whole graph as possible. Since the sampling procedure in the DPP requires eigendecomposition, the computational cost for once sampling from N
3

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 1: Get candidate set S using shortest-path--asee method Input : A graph G, sample length P, node
Compute the shortest path lengths from to all reachable nodes Vy;
Divide V, into different sets Vp based on the path length pi
S, -- -;;
for p 2 to do
Randomly choose node in Vpi Collect first-order neighbours N, of j:
+ S UN, UJ;
end
Output: Candidate set S;
nodes set could be O( (), and the total becomes an excessive O([][*) 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 form smaller but more effective candidate set S; for node i, which is detailed in Algorithm 1 Using this method, the computational cost is approximately O((P- deg)"), where P < N is the path length (normally smaller than the diameter of the graph) and deg < N is the average degree of the graph. As an example, consider a Citeseer graph (Sen et al. 2008) with 3,327 nodes and deg = 2.74. When using the experimental sctting shown below, where P = 5, we observe that O(N3) = 3.6 x 10 which is significantly larger than 2571 = O(P deg)
After obtaining the candidate set S,, the subsequent step involves effectively leveraging the characteristics of the graph to devise the computation method for the L matrix. As major fundamental technique of DPP, Quality-Diversityy decomposition is used to balance the diversily against some underlying preferences for different items in Y (Kulesza. & Taskar, (012)). Since L can be written as L = B B, each column of B is further written as the product of quality term Qj E IR and a vector of normalized diversity features 3j DR || 1. The probability of subset is the square of the volume spanned by q;0} for W.
Hence, L for the given node i now becomes
- g g3.
(5)
where 3. S are two candidate negative nodes.
Utilizing the Quality-Diversity decomposition of DPP, we use the node feature representations and graph structural information to calculate L for the intended sample selection. Specifically, following the Duan ct al. 2023), all the nodes V in a graph G are first divide into Q communitics, denoted as V = ( 9=11 using Fluid Communities method (Parés et al. 2017). Then, the features of each community Froom and each candidate set S; are extracted from the node representations h; via
EieWoum h;
b EjeS. h
(6)
Wrom
[
With the Eq. G the quality terms in Eq. (5 will be defined as:
q} = cos(a; a, b,) O cos(a,,
d cos(a, b.) @ cos(a, az),
(7)
where a, Oj, aj. represents the feature expression of the node belonging to its community, b, denotes the features of the candidate set S, and the O means point-wise product. These quality terms ensure the candidate node j is not similar to the given node i. The diversity term in Eq. 5 is clefned as
TT09 Φ7 cos(h;, az)) cos(az, hzz)) @ exp (cos( hz)) 1)),
(8)
4

---

Published in Transactions on Machine Learning Research (03/2024)
Vun
Vise
Viee
Vi.ri
Vi-I
Vi-i
Vnni Voue)
(Vn- Visai)
VViva Mhat Visal Viarg Mikr Viea Vieu Miax Vixay
Vi-i
Vour Visai vaa
Ves
Vis Vasi Vinas
-y
Via
Viuu vin-i viva
Vour Vizat Visa
Vian Visit Vaaa
(a)
(b)
(c)
Figure 2: Illustration of the layer-diverse sampling process. (a) In the candidate set with 3 nodes, construct the v3x3 The original space is spanned by the eigenvectors 01, 22 it and every node in the candidate set corresponds to a coloured vector in this space. (b) Suppose node (green vector) is selected in the last layer, which has the greatest impact on the / 1], we then squeeze the space along the Vi: 1] direction. the sign of another node V[: 1] projection the same as the green one, the re-scale direction will be the same (the orange vector) and vice versa (the blue vector). (c) This operation will result a new space, where the component [ 1] is significantly cut-off, which means the probability of picking the corresponding node 1 has been reduced.
which ensures that there are sufficient differences between every pair of candidate nodes j and Jr.
Due to the primary focus of this paper not being on the computation of the matrix, additional details can 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 being independent.
3 Proposed Model
3.1 Layer-diverse Negative Sampling
Given a node i and its candidate negative sample set S N₂ E S, and N; N₂ E S; denote the negative samples for node i in multi-layer GNNs collected from layers and 1+ 1, respectively, as illustrated in Figure 1 Our goal is to reduce the overlap between N₂" and N, 1+1 to cover as much negative information in the graph possible while retaining accurate representation of Note that S could be geometrically as a space spanned by the node representations, while N.' is just a subspace of this space spanned by the selected negative samples/representaie rrepresentations. Inspired by this geometric interpretation of negative sampling, our idea to squeeze this space for negative sampling at layer I conditioned on obtained N," reduce the probability of re-picking the samples in N."
To be specific, an eigendecomposition is first performed on L from Eq. 15 of S. = (s), which yields the eigenvalues U {Ai,.., .s.,)) Às} and the eigenvectors space of & since sSs [01, 10. Us), where each corresponds to node in S,, and v[J,:] :] also the impacts/contributte of the node on cach cigenvector. The probability of picking node j through the DPP sampling is then proportional to :|]l- Given N7, the goal is reduce the information of any J" E N. in space V. To this end, the eigenvector basis of node j* that makes the greatest copprtcconntibttion is identified as:
(Vi,..,, ws}. Here, an orthogonal basis for the real and symmetric matrix. All the eigenvectors compose new matrix denoted
arg (E..2....
V
1s, denotes non-neighbour nodes graph in theory, but we follow Duan al. 2022 2023 reduce size the Algorithm
5

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 2: Layer-diverse negative sampling
Input : Node i, candidate set S N;
Calculate L' using Eq- 55;
Eigendccompose L' to get U and T;
for every j E E, 1-1
Find m using Eq. 9:
Get layer-diverse matrix V using Eq.
10
end
Perform k-DPP sampling on S using Algorithm Output: N;
The space V along the m direction is then squeezed by
V V m
v'= V >V
m) &
(10)
where denotes the outer product and y (0,1) is the weight of the squeezing. The outer product can be thought of a way to 'stretch' every vector of node j along the didreeiin. Since in Eq. {10) implies that the node j* has the strongest influence on this aigenvector/directtee contribution of the node jr at m-direction to all vectors as much as possible. It is worth noting about Eq. 110 that:
it helps to reduce the
Remark 3.1. Suppose the probability of re-picking node jr E N; in V is p, the new probability of re-picking it in V' would be reduced to (1 (),7)p, where 0 << S 1. It means that we can control the squeezing degree by 7. See the proof given in Appendir A.2
Remark 3.2. For node 7 E and J", if V[. and V [:] are sufficiently similar with each other, then the probabilily of re-picking i would also be reduced. (See the proof in Appendir A.2. It means we do not just reduce the re-picking probability j" By reducing the re-picking probability of j also decrease the influence of similar nodes, reducing the likelihood of them being considered.
After obtaining the layer-diverse vector matrix V we employ k-DPP for negative sampling. k-DPP is generalization of the DPP for sampling a fixed number of items, rather than 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 AA.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 k-DPP is eigenvector matrix V, while the input of Algorithm 3 is layer-diverse matrix V Our method can be used for all layers by collecting all negative samples before a given layer the candidate set. To reduce the computational cost, two consecutive layers are used in the following experiments.
To better illustrate our method, three-dimensional example is shown in Figure 2 where the candidate set contains three nodes and the size of V is 3 x 3. Figure aa) shows that the original space is spanned by V1, 02 13, with the eigenvectors [V[:,//y=m
Suppose node 1 has the highest impact on Vı, that is 1 = arg max V[: 1]. The space along the dirieccioo then squeezes, as we can observe Figure (). The original space finally turns the new space in Figure (cc) where the magnitude of the on component is significantly reduced and the probability of choosing the corresponding nodes (ineluding node 1) becomes smaller.
3.2 Discussion
Although there 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 GNNs expressivity and over-squashing. Our

---

Published in Transactions on Machine Learning Research (03/2024)
2
2
2
(a)
(b)
Figure 3: Case 1: Adding negative samples can help GNN learn different embedding for different structures.
Dash lines mean adding negative samples. (a) After adding negative samples, MAX can distinguish different structures. (b) After adding negative samples, MAX and MEAN can distinguish different structures.
2
Layer I-1
Layer
Figure 4: Case 2: Although for layer -- 1, MAX and MEAN aggregators still can distinguish different structures after adding negative samples. Since the layer-diverse method can obtain different samples from the last layer, for layer L, adding negative samples lets MAX and MEAN aggregators to be able to distinguish different structures.
results show that negative samples have strong potential to improve GNNs expressivity and reduce the degree of over-squashing
3.2.1 GNN expressivity
Intuitivoly, adding negative samples into graph's convolution layers will temporarily change the graph's topologies. Xu el al. (2019) state that ideally powerful GNNs can distinguish between different graph structures by mapping them into different embeddings (so-called GNN expressivily). In the following, from topological view, we will demonstrate the three different aggregation cases in which adding negative samples to GNNs may improve the GNN expressivity.
Case In single layer, negative samples can help aggregators distinguish different structures. As shown in Figure 3 aa), before adding negative samples, MAX fails to distinguish two structures because
max (2, 2, 1) max 1) =
(11)
After adding negative samples, we have
max(22220) a max (2,2,0) # fa m0, v'.
(12)

---

Published in Transactions on Machine Learning Research (03/2024)
0
3
(a)
(b)
(c)
Figure Case 3: (a) Aggregators in the original graph can distinguish different structures. (b) Under the specific condition, adding negative samples has a small probability of preventing that. (c) Even if this situation occurs, the layer-diverse approach will address this in the next. layer.
In Figure 3(b,, before adding negative samples, MAX and MEAN both fail to distinguish two structures because for MAX, it will be
== max (1,12,, max 1) =
(13)
and for MEAN, it will be
v 1+1+2+2
1+2 v. 2
(14)
After adding negative samples, we have
= 2 max 1,,1,2,0) #2 2 mm (0, 1) v'
(15)
3 1+1+0+2
0+1 v'.
(16)
2
Negative samples help MAX and MEAN distinguish different structures in this case.
Case 2 Layer-diverse negative samples can help distinguish different structures in multi-layers. The outcomes of only one negative sampling process do not always help the aggregators to generate different embeddings for various structures. As Figure 4 shows, even after adding some negative samples, the MAX and MEAN
aggregators for layer | still cannot distinguish between the different structures. This is because we have:
v = max 1,,,,2 - 1 max ma, 1, = maxx112) - 1 max max
(17)
1+1+2+2 1+1+0+2
1+2
0 v'.
(18)
4
4
2
However, if the sampling method is well-designed, the probability of distinguishing between different graph structures in the network will be higher. Benefit from the layer-diverse method which obtain different samples from the last layer, for layer I, we get different samples and have
max 1,,,2 max (1t.max1,,002000 (1,0,2,2) + mmxx1122 11 max =
(19)
1+1+2+2 1+0+2+2
1+2
P
1
=
(20)
4
4
In this case, the layer-diverse negative sampling will help MAX and MEAN to distinguish different structures in multi-layers.
Case There exist some situations where adding negative samples could make the originally distinguishable
structures indistinguishable but the probability of such situations low. As shown in Figure (), the MAX and MEAN aggregators can distinguish two different structures because we have
r max maxx11,1, 1,,), (1, = v',
(21)

---

Published in Transactions on Machine Learning Research (03/2024)
Bottleneck
Weakly connected
Figure Over-squashing occurs when information passes between weakly connected subgraphs, where bottlenecks exist and lead to the graph failing to propagate messages flowing from distant nodes.
1 1+1+2+3
1+2
+
(22)
4
As shown in Figure 5(),, in the l layer, after adding negative samples, using MEAN will have
v= 1+1+2+3
1+3+0+3
7
7
-M
(23)
4
4
4
0 1+2 2
0+3
3
(24)
2
2
2
We notice that it cannot distinguish two structures after adding negative samples when 1. However, from this example, we can see that to make the originally distinguishable structures indistinguishable, the negative samples and y must exactly complement the difference between the two structures from the original aggregation. Apparently, the probability of finding satisfied the negative samples and μ significantly smaller than the finding of some negalive samples to make representations of two structures different. Furthermore, considering our layer-diverse design, the probability of finding such satisfied negative samples and μ at every layer would be exponentially reduced. As shown in Figure 5(c), the result of the MEAN operator is
1x 1 ++0+++2
# 2 -1x
0+1 0+1_
U
(25)
2
Hence, we believe our layer-diverse negative sampling is helpful improving GNN expressivity.
3.2.2 Over-squashing
Separate from over-smoothing and GNN expressivity, over-squahhing is much less known, first pointed out by Alon & Yahav (2021). Over-squashing occurs when bottlenecks exist and limit the information passing between weakly connected subgraphs, which leads to the graph failing to propagate messages flowing from distant nodes (Alon & Yahav] 2021 Topping et al.] 2022), as shown in Figure 6 An effective approach addressing over-squashing is rewire the input graph to remove the structural bottlenecks Karhadkar et al. 2022). However, the rewiring methods face two main challenges: 1) losing the original topological information when the graph changes and 2) suffering from over-smoothing when adding too many edges. In the following, will show negative samples have the potential to address these two challenges.
An alternative way to understand negative samples in Eq. is to introduce new (negative) into GNNs, which can be rewritten as
4
h = w/t (1-1) Σ
Cza w
with
Σ ww'n (-1)
(26)
Cj,4
(.EE,
G.NEE,
where E, and Eg denote positive and negative relations separately. Firstly, as stated Karhadkar et al. 2022), the flexible wn and u2 could help to balance the over-smoothing and over-squashing. Secondly,

---

Published in Transactions on Machine Learning Research (03/2024)
Table Accuracy of all 4-layer models on datasets
Citeseer
Cora
PubMed
CS
Computers
Photo
ogbu-arxiv
GCN
55.78.s8 1.69
17.92
14.34
14.00
47.21 16.22
68.04
70.57 11002
GATv2
63.67 77.07
74.4343..0
74.95+1.71
85.00+1.58
61.90
79.08+3.43
70.60+0.80
SAGE
59. 70
73. 13..54
75.48+1.91
82.22.+2.60
+9.27777.85
79.01
71.15+1.00
GIN-6
60.89 1..97
68.0748.87
72.93+5.09
59.00 59.00
37. 37.09
31 31.5646.91
35.04.5.33
AERO
62.35
73.37
42.80
64.50
50.20
56.61 11..54
70.04
RGCN
62.82
71.75+:3.4
74.96+1.40
79.91
56.4449.77
75.19 75.19+8.60
71.19+0..z
MCGON
50.90_9.70
69.2844.33
71.44
80.66
64.09
73.01 19.54
65.494..26
PGCN
63.03
70.37
75.47+1.78
52.73
71. 71.1346.22
79. 19.2646.66
66. 66.1640.15
D2GCN
63.3042.01
73.02+3.01
75.36
83.47
74. 14.1194:2.0
82.78+4.29
71.46
LDGCN
68.27 +11 22
76.80+1.26
77.07 -1.23
86. 86.23
77.92+2.34
86.50+1.48
71.66++0.30
Citeseer
Cora
PubMed
877
Accuracy
0.5
0.5
0.5
0.4-
GCN
RGON
- GON
RSON
GCN
RGCM
0.3
GATV2
MCGEN
0.3
G4TV2
MOGCN
GATV2
MOGON
SAGE
PGCM
SAGE
PGCN
SAGE
PSON
D2GEN
0.2
B2GCH
G0K-aps
025DN
AIRO
AERO
LDGON
0.5
Computers
Photo
0.8
0.0
0.6
5.7
Accuracy
8.6-
0.4-
0.4
5.5
-4- GATV2
-6- GCN
NCGCN
ROCh
GDN
G4TV2
-6- MOSCH
ROON
3.4
BEN
GATV2
RGCN
MCSCN
SAGE
PGCN
SAGE
-6- PCCN
SAGE
PSCh
0.0
GN
D2GCN
-6- D26CN
GN epc
D25CN
AERO
LOGON
AESO
- (DGCN
AERO
LDGCN
layers
Number layers
layers
Figure 7: Node classification accuracy of all models with 2-6 layers in six datasets.
different from the positive samples/ added by Karhadkar et al. (0022). negative cempleeseddgss could further improve the ability to preserve the node representations. The reason is that the underlying assumption of GNNs is that the representation of a node should be similar to the representation attiossttiios of its (positive) linked nodes, so any new positive samples might very likely bring some incorrect information to a node and then damage the original node representation significantly. However, our negative samples are purposely chosen to provide negative information a given node, so the Eq. { would not damage the original node representation too much under the same number of newly added edges with Karhadkar et al. (2022). Hence, believe the negative samples are useful to overcome the over-squashing problem.
4 Experiments
Our experiments aimed to address these questions: (1) Can the addition of negative samples obtained using method improve the performance of GNNs compared to baseline methods? (Section 4.1 (2) Does
10

---

Published in Transactions on Machine Learning Research (03/2024)
method result in negative samples with reduced redundancy? (Section 1.2) (3) Does our method yield
consistent results even when fewer nodes are included in the negative sampling? (Section 4.2
(4)
How
would our negative sampling approach perform when applied to other GNNs architectures? (Section
4.3)
(5) Does incorporating these negative samples into graph convolution alleviate issues with over-smoothing
and over-squashing? (Section 4.4 (6) What the time complexity of the proposed method? (Section
4.5
(7) How do the sampling results of our LDGCN model compare to those of the D2GCN model in terms of overlap reduction and sample diversity? (Section 4.6
4.1 Evaluation of Node Classification
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 net- works: 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 Kipp & Welling 2017), GATv2 (Brody et al. 2022), SAGE (Hamilton et al,) 2017), GIN-e (Xu et al., 2019) and AERO (Lee et al. 2023). We also compared existing GNN models with negative sampling mothods
RGCN (Kim & Oh 2021) selects negative samples in purely random manner. MCGCN (Yang et al. 2020
selects negative samples using Monte Carlo chains. PGCN (Ying et al. 2018 uses personalised PageRank D2GCN (Dan et al. 2022) calculates the 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 datasets, to ensure 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).
. For heterophilous
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
Results homophilous datasets. The results reported are the average accuracy values of the node classification after 10 runs, shown in Figure for layers to 6 and the detailed values for layer 4 are presented in Table [ The results indicate that our model outperforms the other models. It performed better than the shate-of-the-art GCN variants: GraphSAGE, GATv2, GIN-e, and AERO. Unlike these methods, LDGCN incorporates both neighbouring nodes (positive samples) and negative samples obtained by our mothod 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 (Ta- ble 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 nnighhouring nodes have similar labels or features!.
Our layer-diverse negative sampling method is well-suited for such graphs for several reasons:
11

---

Published in Transactions on Machine Learning Research (03/2024)
Table 2: Acc of 2-layer models on WebKB dataset
Cornell
Texas
Wisconsin
GCN
48.52 15009
56.21 15.65
49.80 5.70
LD-GCN
55.36
61. 61.62+5.90
61.56_5.63
GATv2
51.35
40.54
50.54_4.21
LD-GATv2
66.48 14.71
61.8617.36
64.31
GraphSAGE
61.01 14.17
70.27
70.65
LD-SAGE
67.11
76.46=4.52
76.47
GIN
43.78
56.48 15.19
47 17.055.5.500
5.33
LD-GIN
56.78
61.56+5.37
52.94=4.16
Table 3: Acc of 4-layer models on WebKB dataset.
Cornell
Texas
Wisconsin
GCN
43.78
54.23
53.13.6.02
LD-GCN
48.65
58.6445.42
58.47=6.02
GATv2
49.54 28.50
57.97
51.52_5.37
LD-GATv2
52.54
60.0643.75
57.14_3.54
GraphSAGE
52.97
64.86+5.40
59.37 =5.33=25.8
LD-SAGE
58.5946.10
70.64
62.94
GIN
48.38
58.39
47.12
LD-GIN
54.055+4.99
60.48
54.37=3.15
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' important lo capture 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 pro- cosses.
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 versatile tool in the GNN toolkit, capable of addressing the challenges presented by both homophilous and heterophilous graphs.
12

---

Published in Transactions on Machine Learning Research (03/2024)
Table 4: Overlap rates of D2GCN and LDGCN on Cora
OVRnode
OVRals
OVRsxls
METHOD
4-yyeer
6-Layer
4-Layer
L-Lyerr
4-Layer
6-Layer
D2GCN-19 1%
75.00
65.4617.62
85.88
79.61
47.55
71.0647.71
LDGCN- 1%
10.74
9.25+33.04
6..8
57.8214.34
26.6224.76
23. 23.1545.58
D2GCN-10%
70.99 1..79
72.42
83.24 1.54
84.59 12.71
74.08
75.44
LDGCN-10%
13.72
12.90
02.89-2.43
59.82+2.81
28.65
26.23+2.99
Table 5: Overlap Rate of D2GCN and LDGCN on Computers
OVRnode
OVRek
OVR
METHOD
4-Layer
6-Layer
4-Layer
G-Lyyer
4-Layer
6-Layer
D2GCN-1%
99.7.0.04
99.69
99.84
99.7940.04
99.7740.02
99.72+0.05
LDGCN-1%
40.45+1.61
43.27
93.83
94.23+1.30
69.61
68.9941.42
D2GCN- 10%
99.71
g9.04
99.83 1o.02
99.83
99.7440.03
99.7610.03
LDGCN-10%
52.59
54.85
96.05
94.61
74.01
74.29+0.70
Table 6: Overlap Rate of D2GCN and LDGCN on CS
OVRnode
OVRels
OVRsxels
METHOD
4-Layer
6-Layer
4-Layer
G-Layer
4-Layer
6-Layer
D2GCN-1%
95.53_0.05
95.18
96.67 20.75
96.3810.24
95.81
95.4640.37
LDGCN-I5 1%
24.73+1.19
30.32+3.02
59.76=1.76
66.61+1.20
34.57+1.39
41.72+0.38
D2GCN-100 10% LDGCN-10%
95.58
95.37 10.10
96.80 20.25
96.5940.09
95.89 40.31
95. 15.6840.10
25.48
25.77 10.14
63. 63.23
62.13
36.33
35.1840.36
Cora
Computers
2.50
0.75
0.8
Acourccy
Accuracy
0.7
0.60-
0.55
026CW40%
D700M.15
D2SCN-105
D2SCN.1 18
06
D2G0N-155
D2GCN11
LONON 3%,
LDOCN 1%
LPOCN 1%
05
LDGOW-1%
Number of layers
Number of layers
Number of loyers
Figure 8: Compare the accuracy of LDGCN and D2GCN by choosing 1% and 10% nodes to perform negative sampling in three datasets.
4.2 Evaluation of Layer-diversity
This scction presents a comparison of our LDGCN model with the previous D2GCN (Duan et al., 2022) demonstrate that our approach effectively reduces the overlap rate of negative samples in terms of both nodes and clusters, and that these samples more beneficial for graph learning.
13

---

Published in Transactions on Machine Learning Research (03/2024)
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 (OVRnode) and Cluster Overlap Rate (OVRets). OVRnode assesses the average overlap of the samples in the last and current layers of the network, defined by
1 L VV
N
N
OVRnode
(27)
V
where Ve 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, shown in Figure [ 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-Mcans to partition all nodes V into K clusters V k after each layer. This ensures that the negative samples N, for each layer belong to different clusters I2 and form the cluster set C. Then, we define OVRels to measure the overlap of the cluster sets between layers:
1 1 L
OVR
(28)
V 1=2 V.V.
5 and G 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 OVRas, and (b) times the actual number of classes, denoted as OVR5xels- 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 further significant reduction in the sample overlap rate, while D2GCN only saw a slight reduction.
Results. Table 1
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 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 g LDGON 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 reduced sampling rate, while D2GCN's performance decreased significantly.
4.3 Evaluation of different GNNs architectures
This section presents an investigation of applying our layer-diverse sampling method to different GNN architectures the Cora, CS and Computers datasets, which have different graph densities.
14

---

Published in Transactions on Machine Learning Research (03/2024)
Table 7: Applying the layer-diverse sampling method to different GNN architectures on Cora
Method
Layer
Layer
Layer
Layer 8
Layer 16
Layer 32
GCN
10.52
63.39 7.92
17.16
13.50
14.19 19.56
14.33.10.7
LDGCN
80.94_0.70
76.80 1.26
67.91
52.80+5.96
30. 1.05
25. 25.25
GATv2
78.36
2..4
66.03
30.7542.24
23.17 28.17 18.18
22.72:5.66
LDGATv2
79.30.0.61
78.46 10.85
67.79 12.34
30.93 10.00
25.11 19.03
24.28 18.30
SAGE
80.1910.60
73.13
58.83
18.51
16.96 14.66
16.5613.45
LDSAGE
80.26=0.45
76.55.0.94
65.39
23.2540016
20.89 43.74
20.7944.51
GIN
78.95
68.07 2.226
36.36 16.80
29.36
27.47 13360
15.86
LDGIN
79.21
69.27 11.70
39.3447.51
31.80+3.33
31.79 -6.9946.99
30.14
Table 8: Applying the layer-diverse sampling method to different GNN architectures on CS
samplling
Method
Layer 2
Layer
Layer
Layer
Layer 16
Layer 32
GCN
90.71 10.91
54.00
40.77.3..55
24.92
10.26
9.02
LDGCN
91.5340041
86.23.0.55
64.37
53.9640.87
19.82+2.76
15.53+1.15
GATv2
89.28 1.62
85.00+ 1.55
52.1947.86
34.24412.67
21.8943.03
22.90
LDGATv2
90.264110r
88.70+1.21
75.59+4.00
35.70
22.90
22.90=0.00
SAGE
g0.64
82.22
59. 59.60
12.14
10.26
9.20
LDSAGE
91.60.1..3
86.33
64.79+1.58
47.54
13.83
12.80
GIN
20.50
59.00
20. 20.1945.77
20.16_6.83
21.4614.00
6.98
LDGIN
90.88
66.10
22.37+4.25
20.61
20.40+2.03
8.27+3.31
Table 9: Applying the layer-diverse sampling method to different GNN architectures on Computers
METROD
LAYER 2
LAYER 4
LAYER 6
LAYER 8
LAYER 16
LAYER 32
GCN
61.4743.14
47.21
47.81
25.12
22.21 4-2322
24.33
LDGCN
80.81
77.9212234
70.30
59.39 :0.39:1.22
55.85
54.50
GATv2
70.9813.89
6..90.1..3
24.74
23.86
23.86:110888
22.90
LDGATv2
72.59
70.28 12209
28.28 47
31.10.11.08
22.90
22.90
SAGE
80.75+0.84
59.27+7.88
21.59+9.07
20.89
19.89+s.s6
19.23+s.09
LDSAGE
80.92.0.41
75.61
63.87
56.06
33.28 33.28
37. 37.29
GIN
33.73
37 37.0942.21
35.80
35.65
6,62
3.06
LDGIN
35.38+2.12
36.67+1.30
39.3447.51
36.7624.22
7.39
3.0620.00
Setup. Besides GCN Kiipf & Welling 2017) layer-diverse sampling method was applied to GATv2 (Booy et al. 2022). SAGE (Hamilton et al., 2017 and GIN-c (Xu et al. 2019), which were called LDGATv2, LDSAGE, LDGIN-E seperately in the following. We repeated the experiments using 1% of the nodes selected for negative sampling. The layers of different models 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 g 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, IDSAGE, LDGIN) consistently outperform their counterparts
15

---

Published in Transactions on Machine Learning Research (03/2024)
Table 10: MAD of 4-layer NegGON models on all datasets
Citeseer
Cora
PubMed
Coauthor-CS
Computers
Photo
ogbn-arxiv
GCN
66.4611.35
15.72
16.97
63.7615.19
50.08 14.88
15.66
9.78.10.11
RGCN
74.08 75.22+4.44
87.18+7.61
73. 134391
55.70+6.88
73.07 #6.08
77.17+2.49
MCGCN
70.49
74.40+5.51
80.52+44.11
72.41
55.5646.04
71.20
76.32+0.67
PGCN
70.89
74.86+5.07
85.3349.37
73.2443.15
57.81 +6.31
74.7546.10
75.91 +1.05
D2GCN
73.93
73.1511.06
83.201s.15
72.51
57.34
75.90
80.47
LDGCN
74.7142.60
75.2443.69
88.88
73.25+3.57
62.33
79.45+4.19
81.09
Table 11: MAD of 6-layer NegGCN models on all datasets
Citesoer
Cora
PubMed
Coauthor-CS
Computers
Photo
ogbn-arxiv
GCN
7.44
6.68 23.44
75.9447.26
62.57
46.1646.74
57.88
8.96
RGCN
45.98
64. 64.71+660r
76.52+4.37
69.73
54.7448.24
79.16+1.19
76.04+1.35
MCGCN
57.33
67. 67.60
16.77
67.8211.40
56.67
77.8814..8
72.81 100.5
PGCN
50.95=18.73
69.02+5.95
76.0343.89
71.1643.95
57.35
76.76
73.01
D2GCN
71.79+2.39
75.51
76.37
72.22+2.07
57.45
78.83
77.87
LDGCN
74.2942.27
74.9245.66
81.4043.55
73.70+1.39
62.18
82.67 +1.43
78.33+122
without layer-diverse methods (GCN, GATv2, SAGE, GIN) across all layer sizes for both datasets. Although the layers in the network increased, all models showed 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 Layer (from 21.59 to 63.87).
Interestingly, it observed that GIN failed to converge for all layer settings the Computers dataset. As result, the layer-diverse method, which had consistently shown improvements on other GNN architectures. couldn't enhance the performance of GIN on the Computers datasct. 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 lasks. They have potential for further exploration in other tasks architectures, and could be promising direction for improving the performance of GNNs, especially those with multiple layers.
4.4 Evaluation of Over-smoothing and Over-squashing
Over-smoothing. To measure the smoothness of the graph representations, we employed the Mean
D. where
Average Distance (MAD) metric (Chen et al. 2020), which was computed MAD I(D,)*
Do Dis ID,, and Dij 1 o))( is the cosine distance between the nodes i and j. Our compar- ison between LDGCN and other negative sampling methods are presented in Table I0 and Table [I As can be seen from these results, LDGCN's MAD is higher than the other methods on all datascts. 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 argument
D: E,
16

---

Published in Transactions on Machine Learning Research (03/2024)
Table 12: Assessing oquashigg using accuracy and MAD on Cora-based graph
ACC
MAD
GCN
65.2416.11
57.39
GCN+FA
43.6440.00
0.00
LDGCN
71.17
74.48+2.19
Table 13: Computational time per epoch and per run for various methods on Citeseer
Methods
Time (s) /Epoch
Time (s) /Run
GCN
0.01 + 0.00
1.58 = 0.15
SAGE
0.01 + 0.00
1.20 0.11
GATv2
0.01 + 0.00
2.18 1.81
GIN
0.01 + 0.00
1.16 0.18
AERO
0.07 0.00
14.53 3.46
MCGCN
0.39 0.01
41.76
PGCN
0.01
1.17 0.87
RGCN
0.01 1.010..0
1.98 = 1.83
D2GCN-1%
0.25
47.73 + 2.62
LDGCN-1%
0.21 + 0.04
39.30 = 3.38
D2GCN-10%
2.10 1
431.89 + 13.03
LDGCN-10%
1.73 0.08
346.01 = 13.01
in Section 3.2 that incorporating negative samples into the convolution increases the upper bound of the distance between nodes.
Over-squashing. Using the Cora dataset, we created a graph G. with bottleneck where only one edge linked two distinct communities. We then compared LDGCN with the basic GCN method (Kipf & Welling 2017) and the GCN+FFA method (Alon & Yahav 2021,, where the last layer of GCN was fully connected. More information on the methods used to construct the graph, as well as the experiment settings, can be found in (A.3.3 Table [12 presents the results in terms of accuracy and MAD. GCN+FA added too many edges in the graph at the last layer, which resulted in over-smoothing problems, and MAD went to zero. In contrast, our method reduces the likelihood of over-squashing and improves classification accuracy without the negative side effect of over-smoothing.
4.5 Evaluation of Time Complexity
The computational complexities of Eqs. 19 and 10 are O(S) and O(S2) respectively for S = [8y]. Let the average node degree, which is a constant for a given dataset and D < S < N. The complexity of the loop in Algorithm 2 is then ODD?)) Since matrix decomposition an essential step DPP, with complexity O(S*), if we take into account every node in the sampling process, the total one-time cost of method would be (DS2 + 5²)). To reduce this cost, can do negative sampling only on fractional nunber of nodes. Experiments in Section 4.2 show that negative sampling on (random) 1% 10% nodes suffices to achieve good performance in general. Taking the Citeseer as an example, Tabel shows the computational time per epoch and per run for varions methods under 4 layers.
4.6 Case Study for Different Negative Sampling Methods
We conducted a case study using the Cora dataset to provide a qualitative comparison between our proposod Layer-Diverse Graph Convolutional Network (LDGCN) and the existing Determinantal Point Process (DPP) based model (D2GCN).
17

---

Published in Transactions on Machine Learning Research (03/2024)
Successive Twice DPP Sampling
Successive 2-Layer Layer Diverse Sampling
20
ap
-60
-00 -20
29
Figure 9: Left: Sampling results from the D2GCN model without layer diversity. Right: Sampling results from LDGCN model with layer-diverse. Overlap nodes, indicating sampling redundancy, are highlighted in dark blue. Sample diversity is shown in red dash box.
We implemented a 2-layer GNN for both the D2GCN (without layer diversity) and our LDGCN (with layer diversity). We employed the respective sampling strategies for each model and collected the indices of nodes sampled in two consecutive layers. When visualizing these nodes in 2D space, used the original node features as shown in Figure g The left panel depicts the sampling results from the D2GCN model, and the right panel illustrates the sampling by our LDGCN model. Overlap nodes from two successive layers are highlighted in dark blue for clarity.
From this case study, we observe two key outcomes:
Reduced overlap in sampling: The LDGCN model demonstrates fewer overlap nodes than the D2GCN model. This finding substantiates our claim that layer-diverse negative sampling effectively reduces the likelihood of resampling duplicate nodes across layers.
Enhanced sample diversity: Aside from reducing overlap nodes, the LDGCN model's samples are more uniformly distributed in the 2D space. This contrasts with the D2GCN model, where samples appear more clustered and thus exhibit higher spatial overlap. The more dispersed samples from the LDGCN model suggest that layer diversity contributes to increased sample diversity and more distinct representation for each layer.
5 Related Work
GNNs and their variants. GNNs are typically divided into two categories: spectral-based and spatial- based. A widely used and straightforward example of the first category is the graph convolutional network (GCN) Kipp & Welling 2017), which utilizes first-order approximations of spectral graph convolutions. Many variations have been proposed based GCN, such GPRGNN (Chien al. 2021), GNN-LF/HI (Zhu et al. )021), UFG (Zheng et al. 2021) which uses graph framelet transforms to define convolution. In the spalial stream, GraphSAGE (Hamilton el al. 2017) is a well-known model. It. utilizes node altribute information to effectively generate representations for previously unseen data, Xu et al. (2019) provides a thcoretical analysis of GNNs' representational power capturing various graph structures and proposed the Graph Isomorphism Network. Besides these two models, there are numerous spatial-base based methods, such
GAT (Velickovic et al. 2018) and PPNP (Kliepera et. al. 2019) to mention just few.
18

---

Published in Transactions on Machine Learning Research (03/2024)
Negative sampling in GNNs. All the GNNs previously mentioned are based on positive sampling. In terms of negative sampling, there are roughly two kinds negative sampling methods for graph representation learning, The first includes methods such as randomly selecting (Kim & Oh 2021), Monte Carlo chains based (Yang et al. 2020,, and personalized Page-Rank Rank based (Ying et al.) 2018). While these methods do find negative samples, they often have a high degree of redundancy or the small clusters are overwhelmed by large clusters. These do not meet the criteria for obtaining good negative samples as proposed in (Duan jet al. 2022). Duan et al. (2022) attempt to find negative samples that meet the above criteria, and focus controlling the diversity of negative samples using DPP (Kulesza & Taskar 2012). However, the found samples were still highly redundant, and it has not yet. been confirmed whether these samples meet the criteria for being good negative samples.
DPP and its applications. Determinantal point process (DPP) was first introduced to the field of machine learning by Kulesza & Taskar (2012) as k-determinantal point process (K-DPP). The k-DPP is a gencralization of the DPP for sampling a fixed number of items, k, rather than a variable number, which is defined by positive semidefinite kernel matrix, and encodes the similarity between the items in the candidate set. The k-DPP method for negative sampling in graph representation learning is a way of selecting negative samples by controlling the diversity of negative samples using the k-DPP. This method is particularly effective in capturing the properties of repulsion and has been successfully applied to various scenarios such as sequential labelling (Qiao et al. 2015), document summarization (Cho et al. 2019 video summarization (Zheng & Lu 2020).
6 Conclusion
In this paper, we presented novel approach for negative sampling in graph representation learning, based layer-diverse DPP sampling method and space squeezing technique. Our method is able to signifi- cantly reduce the redundancy associated with negative sampling, resulting in improved overall classification performance. We also provided an in-depth analysis of why negative samples are beneficial for GNNs and how they help to address common issucs such as over-smoothing, GNN expressivity, and over-squashing. Through extensive experiments, we confirmed that our method can effectively improve graph learning abil- ity. Furthermore, our approach can be applied to various types of graph learning tasks, and it expected to have a wide range of potential applications.
Acknowledgments
This work is supported by the Australian Research Council under Australian Laureate Fellowships FL190100149 and Discovery Early Carcer Rescarcher Award DE200100245.
References
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, (ICLR 2021), Virtual Event, Austria, 2021.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In The Tenth International Conference on Learning Representations, (ICLR 2022), Virtual Event, April 25-29, 2022.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of The 34th AAAT Conference on Artificial Intelligence (AAAI 2020), New York, NY, USA, February 7-12, pp. 3438 3445, 2020.
Eli Chien, Jianhao Peng. Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, (ICLR 2021), Virtual Event, Austria, May 3-7, 2021.
Sangwoo Cho, Logan Lebanoff, Hassan Foroosh, and Fei Liu. Improving the similarity measure of de- terminantal point processes for extractive multi-document. summarization. In Proceedings of the 57th Conference of the Association for Computational Linguistics (ACL 2019), Florence, Italy, July 28- August 2, pp. 1037-1038, 2019.
19

---

Published in Transactions on Machine Learning Research (03/2024)
Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom M. Mitchell, Kamal Nigam, and Scán Slattery. Learning to extract symbolic knowledge from the world wide web. In Proceedings of the Fifleenth National Conference on Artificial Intelligence, (AAAI 1998), Madison, Wisconsin, USA, pp. 509 516. AAAI Press/ / The MIT Press, 1998.
Wei Duan, Junyu Xuan, Maoying Qiao, and Jie Lu. Learning from the dark: Boosting graph convolutional neural networks with diverse negative samples. In Thirty-Sizte AAAI Conference on Artificial Intelligence, (AAAI 2022), Virtual Event, February 22 March 1, pp. 6550-6558, 2022.
Wei Duan, Junyu Xuan, Maoying Qiao, and Jie Lu. Graph convolutional neural networks with diverse negative samples via decomposed determinant, point processes. IEFE Transactions on Neural Networks and Learning Systems, 2023. Accepted on 30 August 2023.
Floris Georts, Filip Mazowiecki, and Guillermo A. Pérez. Let's agree to degree: comparing graph convolu- tional networks in the message- passsnn framework. In Proceedings of the 38th International Conference on Mochine Learning (ICML 2021), Virtual Event, July 18-24, pp. 3640-300 (6400-36999000 2021.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA, December 4-9, pp. 1024-1034, 2017.
Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. Determinantal processes and inde- pendence. Probability Surveys, 3:206-229, 2006.
J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. Zeros of gaussian analytic functions and determinantal poinl processes, volume 51 of Universily Lecture Series. American Mathematical Sociely, 2009.
Weihua HU, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In Advances in Newral Information Processing Systems 33: Annual Conference on Neural Information Processing Systems (NIPS 2020), Virtual Event, December 6-12, 2020.
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. 2022. doi: 2t.48850/arXiv.22110 2210.11790.
Dongkwan Kim and Alice H. Oh. How to find your friendly neighbourhood: graph attention design with self-supervision. In Proceedings of the 9th International Conference on Learning Representations (ICLR 2021), Virtual Event, Austria, May 3-7, 2021.
Thomas N. Kipf and Max Welling, supi-sue classification with graph convolutional networks. In 5th International Conference on Learning Representations (ICLR 2017), Toulon, France, April 24-26, 2017.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learning Representations, (ICLR 2019), 2019.
Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 5(2-3):123 286, 2012.
Shiyong Lan, Yitong Ma, Weikang Huang, Wenwu Wang, Hongyu Yang, and Pyang Li. DSTAGNN: dynamic spatial-temppoal aware graph neural network for traffic flow forecasting. In International Conference on Machine Learning (TCML 2022), Baltimore, Maryland, USA, July 17-29, pp. 11906-11911 2022.
Soo Yong Loe, Fanchen Bu, Jacmin Yoo, and Kijung Shin. Towards deep attention in graph neural networks: Problems and remedies. In Proceedings of the 40th International Conference on Machine Learning (ICML 2023), Honobulu, Hawaii, USA, volume 202, pp. 18774-1888 18795, 2023.
20

---

Published in Transactions on Machine Learning Research (03/2024)
Ferran Parés, Dario Garcia-Gasulla, Armand Vilalta, Jonathan Moreno, Eduard Ayguadé, Jesús Labarta, Ulises Cortés, and Toyotaro Suzumura. Fluid communities: A competitive, scalable and diverse community detection algorithm. In Complex Networks & Their Applications VI Proceedings of Complex Networks 2017, (COMPLEX NETWORKS 2017), Lyon, France, November 29 December 1, volume 689, pp. 229- 240, 2017.
Maoying Qiao, Wei Bian, Richard Yi Da Xu, and Dacheng Tao. Diversified hidden models for sequential labeling. IEEE Transactions Knowledge and Data Engineering, 27(11):2947 2947-29000 2015.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, (ICLR 2020), Addis Ababa, Ethiopia, April 26-30, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Col- lective classification in network data. AT Magazine, 29(3):93-106, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, 0ass/1111.58666 2018.
Mengying Sun, Sendong Zhao, Coryandar Gilvary Olivier Elemento, Jiayu Zhou, and Fei Wang. Graph convolutional networks for computational drug development and discovery. Briefings Bioinform., 21(3): 919-935, 2020.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bron- stein. Understanding over-squashing and bottlenecks on graphs via curvature. In The Tenth International Conference on Learning Representations, (ICLR 2022), Virtual Event, April 25-29, 2022.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio, Graph attention networks. In 6th International Conference on Learning Representations, (ICL. 2018), Vancouver, BC, Canada, April 30 May 3, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations (ICLR 2019), New Orleans, LA, USA, 2019.
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning. Tn Proceedings of the 26th ACM SIGKDD International Con- ference on Knowledge Discovery & Data Mining (KDD 2020), Virtual Event, CA, USA, August 23-27,
pp. 1666 1676, 2020.
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 International Conference on Knowledge Discovery & Data Mining (KDD 2018), London, UK, August 19,23, pp. 974 983, 2018.
Wenhui Yu and Zheng Qin. Graph convolutional network for recommendation with low-pass collaborative filters. In Proceedings of the 37th International Conference on Machine Leorning (ICML 2020), Virtual Event, July 13-18, volume 119, pp. 10936-10945, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In 8th International Con- ference on Learning Represenlations, (ICLR 2020), Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Jiping Zheng and Ganfeng Lu. k-sdpp: Fixed-size video summarizatiio via sequential determinantal point processes. In Christian Bessiere (ed.), Proceedings of the Twenty-Nine International Joint Conference on Artificial Intelligence (IJCAI 2020), pp- 774 781, 2020.
Xucbin Zheng, Bingxin Zhou, Junbin Gao, Yu Guang Wang, Pictro Lió, Ming Li, and Guido Montúfar. How framelets enhance graph neural networks. In Proceedings of the 38th International Conference on Machine 2021.
Learning (ICML 2021), Virbual Event, 18-24 July, volume 139, pp.
21

---

Published in Transactions on Machine Learning Research (03/2024)
Algorithm 3: Obtain sample from k-DPP (Kulesza & Taskar 2012
Input: Ground set Y, size k, matrix L used for sampling Eigen-decompose L to obtain eigenvalues :1....: :
Iteratively calculate all elementary symmetric polynomials of for I = o,..., k and v = o,...,12
following Eq. (33
J 0;
k;
for v 1 ,.,,, do
if = then break end
if μ ~ U|0,1| < A 1 then
J Ju
11
1-1-1;
12
end
18
end
+ (UnineJi
Yuu + 0:
while |V/> > do
Select from Y with Pr(i) = M Evev (v e;);
17
Yuub sub Ui; 18
V Vi orthonormal basis for the subspace of V orthogonal to e;
20
end
Output: Yuu with size Yuul k
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Jure Leskovec, Marko Grobelnik, Mare Najork, Jie Tang, and Leila Zia (eds.), WWW '21: The Web Conference (WWW 2021), Virtual Event / Ljubljana, Slovenia, April 19-23, 2021, pp. 1215-1226, 2021.
A Appendix
A.1 Detail for Determinantal Point Processes (DPP)
A point process on ground set Y a probability measure over "point patterns', which are finite subsets of Y (Kulesza & Taskar 2012). A determinantal point process is a probability measure on all possible subsets of the ground set Y with size of 2 V For every subset Yau S Y, DPP (Hough et al. 2009 defined via a positive semidefinite L matrix is formulated as
det (LV V L (Yab)) = det (L
(29)
where det(-) denotes the determinant of a given matrix, is a real and symmetric [Y] x |Y] matrix indexed by the elements of V, and det + I) normalisation term that constant. once the ground dataset is fixed.
DPP has intuitive geometric interpretation. If we have L, there is always matrix B that satisfies L = B B. Let B; be the columns of B. A determinantal operator can then be interpreted geometrically
as
V L (Yaub) x del (Iy,..) vol vol2((Biiee) (BBiliXmm.)
(30)
22

---

Published in Transactions on Machine Learning Research (03/2024)
where the right-hand side of the equation is the squared [Ysallddimensional volume of the parallelepiped spanned by the columns of B corresponding to the elements in Ysub. Intuitively, diverse sets are more probable because their feature vectors are more orthogonal and span larger volumes.
One important variant DPP is k-DPP (Kulesza & Taskar 2012 k-DPP measures only k-sized subsets of Y rather than all of them including an empty subset. Tt formally defined as
det (Lx)
V (Ysub) Σ W /ool== =b det Lngg )
(31)
with the cardinality of subset Yuu being fixed size h i.e. yubll k. Here, use sampling method
based on eigendecompositionn (Hough et al. 2006 Kulesza & Taskar 2012
Eq. (31 can be rewritten as:
V sub) =
det det(L L + V I (Ysub),
(32)
Y c
Y
where 66
is the htth elementary symmetric polynomial eigenvalues d1, d1. l1Xi of L defined as:
Ck Px (\i, Apx))
Y
Σ II
(33)
U Y NEJ |
Following Kulesza
Taskar (2012), Eq. 32
decomposed into elementary parts as
V suub
Σ 6k JJ|mk
PV,
II Am: mEJ
(34)
Y
where Vy denotes the set {Um Jmme and Vm and Am are the eigenvectors and eigenvalues of the L-ensemble, respectively. Basod on Eq. (34), for the self-contained reason, the complete process of sampling from k-DPP is given in Algorithm More details about DPP and k-DPP can be found in Kulesza & Taskar' 22022)
Since the sampling procedure in the DPP requires eigendecoopositiion, the computational cost for Algo- rithm could be O(INT)), where N | If the sampling is performed for every node in the graph, the total will become an excessive O([N)*) for 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-patie paatess-patthbaaeedd based method Duan et al. 2023 is first used form smaller but more effective candidate set S, for node i, which is detailed in A Algorithm method, the computational cost is approximately O(PP- deg)*), where P < N is the path length (normally smaller than the diameter of the graph) and deg & N is the average degree of the graph. As an example, consider a Citeseer graph (Sen et al. 2008) with 3,327 nodes and deg = 2.74. When using the experimental setting shown below, where P P== 5, we observe that O(N3) = 3.6 x 10 which is significantly larger than 2571 O(P deg)
Using this
A.2 Remark of Space Squeeze
Remark A.1. Suppose the probability of re-picking node j E N in p. the new probability of re-picking it in V would be reduced (1 (1-7)p, where 0 sy means that we con control the squeezing degree by
7-
23

---

Published in Transactions on Machine Learning Research (03/2024)
Proof. After the space squeezing using Eq. (10,, the jr row of new space is
vūi": v
V v : 1111--vV"- vVD" ml
(35)
= -1- :].
Since the probability of picking node jr through the DPP sampling is proportional to |V we denote the probability of re-picking node j E N, in V
p
VVD".:lll.
(36)
According Eqs.
35 and 366 the new probability of ro-picking it V is (1 (1-77/ 7)p.
Remark A.2. For a node e M. and j V and V[j". are sufficiently similar with each other, then the probability of re-picking i would also be reduced. It means that we do not just reduce the re-picking probability j". By reducing the re-picking probability of jr, also decrease the inftuence of similar nodes, reducing the likelihood of them being considered.
Proof. For any two L-length vectors U1 and U2 if the following conditions are satisfied,
V1 1 1-85 sm/m
for any 0 S m S L,
(37)
022
then we call U1 and 02 are d-similar with each other.
For node i E N,' and + jr, the new representation of i in new space V would be
v
(38)
Víj.mm
If [ūū: and V are 8-similar with each other, we have
V
viū vp. -V..-vva.m Vi.
(39)
Vij*, m]
and according to conditions in we have
((1 (1-6) 6) (1 + 8)) V' ((1 5) ((110)
(40)
When å goes to 0, according to sandwich theorem, we have
lim (1- 8-2
(41)
That is to say, if node i is similar enough with j*, the space squeezing will also reduce the probability of selecting node i. The more similar the two nodes are, the lower node i will be re-picked. Hence, we do not just reduce the re-picking probability of j* but also the information of this node, and any nodes sharing similar information with this node would not be considered with high probability.
A.3
Experiment Details
A.3.1 Dataset statistics
The datasets are split generally following Kipf & Welling (017)). For the first datasets, we choose nodes for each class as the training set. For the Ogbn-arxiv, because this graph is large, we choose 100 nodes for each class as the training set.
The first six datasets are downloaded from PyTorch Geometric (PyG The Ogbn-arxiv is downloaded from Open Graph Benchmark (OGB
3 www.ee/eeeeeattttttooooe/aaaaa/e
24

---

Published in Transactions on Machine Learning Research (03/2024)
Table 14: Dataset Statisric
Average of Degree
Dataset
Nodes
Edges
Classes
Features
Label Rate
Val / Test
Epoch
Citeseer
3,327
9,104
3,703
2.74
3.61 %
500/1000
200
Cora
2,708
10,556
1,443
3.90
5.17
500/1000
200
PubMed
19,717
88,648
500
4.50
0.30
500/1000
200
CoauthorOS
18,333
163,788
15
6805
8.93
1.64%
500/1000
200
Computers
13,752
491,722
10
767
35.76
1.45%
500/1000
200
Photo
7,650
238,166 162
8
745
31.13
2.09%
500/1000
400
Ogbn-arxiv
169,343
1,166,243
40
128
35.76
53.70%
29799 /86003
200
Cornell
183
298
1703
1.63
48%
59/37
200
Texas
183
325
1703
1.78
48%
59/37
200
Wisconsin
251
515
1703
2.05
48%
80/51
200
A.3.2 Implementation Details
The experimental task was standard node classification. We set the maximum length of the shortest path P to in Algorithm 1 which mcans after throwing away the first-order nearest neighbours, there are still nodes at the end of the different shortest paths. The size of the candidate set for node is |& When selecting 1% 10% nodes to perform negative sampling, we choose nodes whose degree is greater than the average degree D.
D.
The negalive rate is a trainable parameter and is trained in all models. Each model was trained using an Adam optimiser with a learning rate 0.02. The number of hidden channels is set to 16 for all models. Tests for each model with each dataset were conducted ten times. The convolution layers of GCN (Kipf Welling, 2017). SAGE (Hamilton et al.] 2017), GATv2 (Brody et al., 2022) and GIN-c (Xu et al.] 2019) use PyTorch Geometric to implement. | The AERO (Lee et. al. 2023) is implemented by the code published on Github All experiments were conducted 80GB GPU. The software that use for experiments is Python 3.7.13, PyTorch 1.12.1, torch-geometric 2.1.0, torch-scatter 2.0.9, torch-sparse 0.6.15, torchvision 0.13.1, ogb 1.3.4, mumpy 1.21.5 and CUDA 11.6.
Intel(R) Xeon(R) Gold 6326 CPU @ 2.90GHz and NVIDIA A100 PCIe
Algorithm 4: Coustructing the graph Go having bottlenecks
Input Number of communities Q, original graph G
Using Fluid Communities method (aaré et al. 2017) to get Q communities 9; while True do
Delete the node linking two different communities; if only one node linking two different communities then Break;
end
end
Obtain the maximum connected subgraph from the remaining graph as Goi Output: Graph Go
A.3.3 Over-squashing Experiment Details
Algorithm of constructing the graph having bottlenecks. The central concept in construction is to segment the initial graph into distinct clusters and incrementally eliminate the nodes linking these clusters
25

---

Published in Transactions on Machine Learning Research (03/2024)
Table 15: STATISTICS of Go
Average of Degree
Dataset
Nodes
Edges
Classes
Features
Tabel Rate
Val / Test
Epoch
Go (Cora-based)
915
3054
1443
3.33
8%
400/400
200
Figure 10: Based on the Cora dataset, we construct a graph with a bottleneck by only having one edge (shown the orange dash box) linking two different communitics. Left: nodes labelled by communitics. Right: nodes labelled by true classes.
until only one edge remains, connecting the two communities. This edge can be considered bottleneck in the graph. The pseudo-code for constructing this graph Go is shown in the Algorithm 1
is important to consider a dataset's specific characteristics and purpose before making any modifications to it, as it can affect the validity and reliability of the analysis and results obtained from it. We construct graph with bottlenecks Go based on the real dataset Cora. The statistics of Go shown in Table 12 and visualization is shown in Figure 10 As Cora is citation dataset, it consists of set of nodes representing scientific publications and edges representing citations between them. If some nodes and corresponding edges are deleted from the dataset, it will not affect the authenticity of the dataset as long as it still represents the citation relationships among the remaining publications.
Detail Cora-based Graph.
However, not all datasets are suitable for the above constructing method. Take the PROTEINS dataset as an example. This datasct represents the interactions between different proteins a biological system, and the edges in the dataset represent the interactions between them. Suppose some nodes and corresponding edges deleted from the dataset. In that case, it could potentially alter the overall structure and function of the modelled biological system, thus affecting the authenticity of the dataset.
A.4 Additional Experiment Results
A.4.1 Best Performance of Various GNN Models in Experiment 4.1
We thoroughly examined and tuned the number of layers for each model using the validation set. This has led more nuanced understanding of how layer configurations impact model performance. 16lloss the highest accuracy achieved by various GNN models across diverse datasets. The table provides insights into whether each model attained its peak performance through 2-layer, 3-layer, 4-layer configuration,
26

---

Published in Transactions on Machine Learning Research (03/2024)
Table 16: Best Performance Accuracy of Various GNN Models Across Datasets. Most models
achieved optimal performance with 2-layer setting, which is the default and hence not specifically marked. Models achieving their best performance at 3 or layers have this indicated in brackets.
Citeseer
Cora
PubMed
CS
Computers
Photo
ogbn-arxiv
GCN
02.11
80.03+0.52
78.15
90.71
61.47+3.14
80.67+3.59
71.10
20.64
GATv2
72.49
78.3641.66
77. 77.40+0.49
89.28
70.98
83.45
71.76
(3)
-0.31
SAGE
11.78
80.19 00.1940.60
26.24
90.6440068
80.75 80.854
87.9710.44
71.15
GIN-
70. 1..47
78.95
77.61 10.73
90.80
33. 16.25
65.19 19.22
60.95
AERO
68.12
12.12240 (3)
1.78
81.7940.93
74.91
#3.25
(3)
89.06
81.18 $1.18_2.14
91.59
71.32 (3)
21.3220.86
RGCN
1..5
77. 17.78+1106
75.73
91.13:10.59
78.80
85.00
70.45
MCGCN
73.44
77.11
76.66
(3)
91.27:10.4
77.78
1..24 1.224
83.03
69.67 11221
PGCN
73.24_1..5
77.78
76.35
88.30
78.39 1.49
86.48 1.776
70.53 1.776
D2GCN
73.20=0.70
80.4140.54
77.84
90.4640.58
80.02+1.74
87.03+0.80
70.61+0.20
LDGCN
74.33++0.79
81.93 11.40
(3)
78.02+0.31
91.53
80.81
88.84 11.48
(3)
71.66 10.30
(4)
denoted within brackets where applicable. In the table, the best-performing method for each dataset. is highlighted in bold, emphasizing the top achievement, while the second-best performance is underscored for clarity.
The results revcaled that while a 2-layer setup is generally effective, certain models and datasets benefit from more layers. For instance, our LDGCN exhibited its highest accuracies on Cora and Photo datasets with 3 layers. An interesting pattern emerged from analysis: methods that incorporated negative sam- ples frequently achieved the second-best results. This observation suggests that adding negative samples to graph convolutional neural networks can significantly enhance the model's ability to learn different types of relat ionships, thereby improving overall performance. However, it's crucial to note that not all mel involving negative samples yielded consistent performance across different datasets. This variability high- lights that the selection of negative samples is a non-trivial aspect of model design and that carcfully chosen negative samples can substantially aid GCNs in better learning from graph data.
A.4.2 Big Dataset
We conducted additional experiments using the Open Graph Benchmark's login-mag datasct, which indood presents a more challenging environment with its larger graph size of approximately 1.94 million nodes and over 21 million edges. The statistics of bbgn-mag are shown in Table
Table 17: STATISTICS of obgn-mag
Average of Degree
Dataset
Nodes
Edges
Classes
Split Ration
Epoch
ogbn-mag
1,939,743
21,111,007
349
21.7
85/9/6
400
The eigendecomposition techniques employed in DPP sampling do introduce considerable computational complexity, which lead to scaling challenges very large graphs. To address this and maintain balance between computational efficiency and the benefits of our approach, we strategically sampled subset of 0.1% of the nodes from the ogbn-mag dataset for layer-diverse negative sampling. The results are shown in Table [8
Despite the reduced sampling size, our LDGCN achieved an accuracy of 33.51%+0.32 on the ogbn-mag dataset. This performance is higher compared the baseline models. The results demonstrate that even with only fraction of the nodes subjected to layer-diverse negative sampling, there is still enhancement
27

---

Published in Transactions on Machine Learning Research (03/2024)
in the performance of the original GCN framework. This evidences the efficacy of our proposed sampling method, suggesting that it could be valuable strategy for managing the trade-off between computational demand and performance in large-scale graph neural networks.
Table 18: Acc of 4-layer models on obgn-mag dataset
GCN
GATv2
GraphSAGE
LDGCN
obgn-mag 31.99
32.21 10.46
30.11
33.51
A.4.3 Graphs Classification
We conducted additional experiments focusing on graph-level classification tasks, this time extending our approach to the Graph Isomorphism Network (GIN) model. We selected two well-known graph datasets, Proteins and MUTAG, for our experiments. We employed a 10-fold cross-validation scheme and utilized SUM readout pooling to aggregate node leatures at the graph level. Our experiments compared the performance of standard graph neural network models like GCN, GATv2, GraphSAGE, and GIN with our modified version, the Layer-Diverse GIN (LD-GIN). The results of these experiments are shown in the Table 19
Table 19: Acc of 2-layer models on graph dataset
GCN
GATv2
GraphSAGE
GIN
LD-GIN
PROTEINS
72.97
64.11
72.43
73.06
74.07
MUTAG 76.5448.19
77.78
79.16
87.83
88.8946.05
The results from these experiments were encouraging, Our LD-GIN model improved over the baseline models on both the PROTEINS and MUTAG datasets. This enhanced performance on graph-level classification (asks demonstrates the versatility of our layer-diverse negative sampling method. not only maintains its effectiveness across different graph structures but also adapts to varying task requirements, whether they involve node-level or graph-level classification. This extension of our experiments to graph-level tasks aligns to broaden the applicability and relevance of our method.
28


Reviews:
[{"review_id": "ATzCwzlHLz", "reviewer": "Reviewer_kkpA", "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": "The proposed method can enhance the performance of several existing GNNs according to experiments, however, there are some major concerns listed below.\n\nThe formulation of equation 4 is a core part of the work, however, this formulation lacks explanation. Why is the negative nodes simply minused from the message passing formulation? It seems to imply that the negative nodes contain irrelavant information and should be deleted. However, the original term consisting of the positive node aggregation (i.e. the first term of equation 4) does not contain the information from the negative samples, therefore this design is not convincing and require serious justification. \n\nWhile the aim to resolve the over-smoothing and over-squashing problems is meaningful, the explanations on how the proposed method is related to this target problem is not satisfying, with some vague claims. For example, in the second paragraph of Introduction, since the aim of GNN is to refine the representation of a given node with its neighbors with similar information, why would it be important to incorporate distant 'negative nodes' with very different information? Node representations are local, unlike the graph representation of the entire graph, and it is not straightforwardly convincing to say that each node should contain distant information, which may blur the node's own information. Moreover, it is also unclear what is the relation between the negative sampling and the over-smoothing/squashing problem, which is the motivation of this work and should be clarified at the very beginning.\n\nThe proposed method is applied to different GNN models in experiments. However, the adopted GNNs are mostly old ones without consideration on the over-smoothing or over-squashing problem. Therefore, it is necessary to discuss what the advantages of the proposed method are, being compared to other works also studying over-smoothing and over-squashng problem, both conceptually and experimentally.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "This paper, targeting the over-smoothing and over-squashing problem, proposes a solution to add negative samples (nodes) and alter the original graph topology. Specifically, the proposed method aims to sample the negative samples (nodes) in an effecient way, and then add an additional term as the minus of the summation of the negative nodes (Equation 4).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As detailed in the weakness and strengths part, the recommended revisions are:\n\n1. Explanations on the motivation \n\n2. Justification of the formulation in equation 4\n\n3. Discussion and comparison with new works that focus on the same problem (over-smoothing and over-squashing)", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3pQDHM4fKz", "reviewer": "Reviewer_3kP1", "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. It is an interesting and reasonable extension to improve D2GCN(Duan et al. 2022). Table 2 and 3 are good proof of the motivation. \n2. It is good to discuss how it impacts expressivity and oversquashing and experimentally demonstrate it.\n\nWeakness:\n1. When I first read it, my impression is it is not self-contained and thus hard to follow. However after checking the paper of D2GCN, I found that the formulation and background are very similar. So, maybe it is just the writing issue. For readers who are not familiar with DPP, it may take some time for they to understand the whole flow of how you define L and how you use it to do sampling. I believe Section 2 can be improved to make it easier understandable (e.g. by adding some simple description of the whole pipeline).\n2. The major issue is the practicality. As the authors may already notice, L is different for every node; the procedures of candidate set generation/eigendecomposition/negative sampling are time consuming compared to message passing. Although only sampling 1% of the nodes can still show improvement, the scalability is still a serious issue when the graph is larger. \n3. The paper focused more on the discussion of oversmoothing and oversquashing, but I think it is more related to heterophily. In the case of heterophilious graphs, intuitively there are more negative samples and negative sampling is more useful. Unfortunately the paper did not have experiments on heterophilous graphs. It is better to add experiments on those datasets. \n4. Following 3 and 2, on heterophilous graphs, there are many advanced algorithms which are not only effective but also efficient, such as GCNII. I checked the leaderboard of ogb-arxiv, GCNII is also better than the reported results in this paper. Considering there are easily alternatives to be more efficient while having similar or even better results, the usefulness of the proposed negative sampling method is doubtful.", "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": "This paper proposes a new negative sampling methods to improve the message passing of graph neural networks. Negative samples are found to be useful to prevent oversmoothing and overquashing in previous works; however the previous DPP-based sampling methods contain too much redundancy in different layers. This paper improves the approach in (Duan et al. 2022) by advancing a new layer-diverse DPP sampling schema. Experiments show that it can reduce the overlap rates of negative samples and improve the accuracy of GNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Revising the paper, correcting the typos, and trying to make Sec2 easier to follow. Example typos: Page5, \"the hope is reduce the information of any\" --> \"the goal is to reduce the information of any\"\n2. Adding experiments on some heterophilous graphs such as Cornell, Texas, and Wisconsin.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "P6p7DLpFTk", "reviewer": "Reviewer_qV4F", "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 utilization of negative sampling to address over-smoothing and over-squashing in GNNs is conceptually sound and intuitive.\n2. The paper offers a comprehensive presentation of the problem, methodology, analysis, and experimental results.\n\nWeaknesses:\n1. Lack of Thorough Theoretical Analysis:\n   - It is essential to provide a more rigorous theoretical foundation to support the claim of improved expressiveness. It is insufficient to claim better expressiveness by providing several good cases. It is easy to find some bad cases, which are distinguishable by GNN but become indistinguishable by using negative sampling.\n   - The analysis of over-squashing is not convincing. Existing literature indicates that the over-squashing can be remitted by adding connections between two dense clusters. It is not clear if adding negative connections can also help. Moreover, there is no evidence to show that negative sampling is more focused within dense clusters or across clusters. More theoretical evaluation is needed.\n\n2. Doubtful Experimental Results:\n   -  In Figure 7, the model performance with the number of layers set to 4 never achieves the best when compared against other number of layers. However, Table 1 only reports the results at 4 layers, which is unrepresentative. Better to tune the number of layers by using the validation set and report the best performance.\n   - The baseline results for the Computers and Photo datasets appear significantly lower than the results reported on the leaderboard. The performance of GCN on Computers and Photo are always higher than 80% and 90%, but only 47% and 68% in this paper. This raises concerns about the reproducibility and reliability of the reported results. A more rigorous comparison with established baselines is necessary.\n\n3. Limited Exploration of Applicability:\n   - It would be beneficial to conduct extensive comparisons by incorporating the proposed method with state-of-the-art methods to assess the potential for further improvement.\n   - Additionally, investigating whether the proposed method is applicable to graph-level tasks is an avenue worth exploring, as it can enhance the paper's applicability and relevance to a broader range of problems.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "This paper introduces a novel approach to mitigating over-smoothing and over-squashing issues in traditional GNNs through the incorporation of layer-diverse negative sampling using a determinantal point process and a space-squeezing method in multi-layer GNNs. The experimental results demonstrate better performance on node classification tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide more rigorous theoretical analyses, especially for expressiveness and over-squashing.\n2. Enhance the experimental study with more convincing results.\n3. Conduct extended experiments for applicability exploration.", "broader_impact_concerns": "No ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HXSbyNnpj8", "reviewer": "Reviewer_qXu9", "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* Effective novel method for negative sampling in GNNs\n\nThe paper presents a new way to do negative sampling in graph neural networks using determinantal point processes and space squeezing. This is an innovative technique not explored before. Experimental results demonstrate that this novel approach consistently outperforms existing negative sampling methods and baseline GNNs without sampling across diverse datasets. So the strength is proposing and validating a new effective technique to enhance representation learning in GNNs.\n\n* Reduces redundancy across layers\n\nPrior negative sampling methods treat each layer independently, leading to high redundancy in samples across layers. The proposed space squeezing method significantly reduces overlap in negative samples between consecutive layers. This is empirically shown through node and cluster overlap metrics. Lower overlap implies more useful information from sampling, avoiding repeated nodes across layers.\n\n* Applicable to different GNN architectures\n\nThe layer-diverse negative sampling technique is tested on various GNN models like GCN, GAT, GraphSAGE and shows consistent improvements in their performance. This demonstrates the wide applicability and flexibility of the proposed approach across diverse architectures beyond a single model.\n\n### Weaknesses\n\n* Computational complexity\n\nThe eigendecomposition and space squeezing in DPP sampling add significant computational overhead. This causes scaling issues for very large graphs with millions of nodes and edges. Approximate solutions would be needed. The complexity also increases with more layers in the GNN, limiting depth of models.\n\n* Universal benefits not guaranteed\n\nWhile the technique helps most models on most datasets, the GIN architecture failed to benefit on the Computers dataset. This highlights dataset-specific and model-specific factors may affect gains seen from the approach. More analysis needed on where the technique consistently falls short.\n\n* Lack of case studies or qualitative results\n\nThe paper lacks any case studies or qualitative results to provide better intuition about the model's effectiveness. For example, visualizing the differences in negative samples selected by the proposed method versus prior techniques could have helped build better intuition. Providing some examples demonstrating improved representation learning through case studies would have been beneficial.\n\n* Small datasets used in experiments\n\nAll the datasets used in the experiments are relatively small. The model should have been evaluated on some larger graphs with millions of nodes to better demonstrate scalability. Using larger datasets would have strengthened the empirical results and conclusions drawn.", "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": "This paper proposes a layer-diverse negative sampling method for graph neural networks (GNNs) to mitigate issues like over-smoothing and over-squashing. Traditional GNNs only gather information from first-order neighbors (positive samples) during message passing. This can lead to limited expressivity and over-smoothing. Negative sampling incorporates non-neighboring nodes (with distinct representations) into message passing. This enhances representation learning. Existing negative sampling methods treat samples independently per layer. This results in redundancy across layers. The proposed method transforms the candidate set into a space using a sampling matrix in determinantal point processes (DPP). It then squeezes this space along dimensions corresponding to previous layer's samples. This reduces overlap. Experiments on 7 datasets show consistently superior performance over baselines. Layer-diverse sampling reduces node and cluster overlap versus prior DPP sampling. Negative sampling can improve GNN expressivity by temporarily changing graph topology. It can also alleviate over-squashing by introducing new negative edges without over-smoothing.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* It would be more convincing to add some case studies.\n\n* It would be more convincing to add results on some larger datasets.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers agreed that the paper contributes to an important topic of research (GNN's issues on over-smoothing and over-squashing). They are satisfied overall with the empirical evidence for justifying the proposed approach.

However, they also pointed out a few issues:
1. Theoretical justification of the proposed approach is lacking;
2. The baseline methods in comparison are not from state-of-the-art (2021 or earlier);
3. The paper's notations and writing are not self-contained; also the introduction to DPP are not easy to digest.

While I believe the authors were not tackling the theoretical challenges in this paper, I believe the rest of the two points need to be addressed in the camera ready version. Hence I recommend the following revisions:
1. Include at least one baseline from the latest paper, or justify explicit at the beginning of the experiment section why some of the SOTA methods won't address the over-smoothing/over-squashing issue;
2. Consider making the paper self-contained by e.g., adding appendix materials to explain the notation/setting better, as well as a longer intro to DPP.
Decision: Accept (poster)