Graph Self-supervised Learning with Accurate Discrepancy Learning
Authors: Dongki Kim
Jinheon Baek
Sung Ju Hwang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Network
Graph Self-supervised Learning

Abstract: Self-supervised learning of graph neural networks (GNNs) aims to learn an accurate representation of the graphs in an unsupervised manner, to obtain transferable representations of them for diverse downstream tasks. Predictive learning and contrastive learning are the two most prevalent approaches for graph self-supervised learning. However, they have their own drawbacks. While the predictive learning methods can learn the contextual relationships between neighboring nodes and edges, they cannot learn global graph-level similarities. Contrastive learning, while it can learn global graph-level similarities, its objective to maximize the similarity between two differently perturbed graphs may result in representations that cannot discriminate two similar graphs with different properties. To tackle such limitations, we propose a framework that aims to learn the exact discrepancy between the original and the perturbed graphs, coined as Discrepancy-based Self-supervised LeArning (D-SLA). Specifically, we create multiple perturbations of the given graph with varying degrees of similarity, and train the model to predict whether each graph is the original graph or the perturbed one. Moreover, we further aim to accurately capture the amount of discrepancy for each perturbed graph using the graph edit distance. We validate our D-SLA on various graph-related downstream tasks, including molecular property prediction, protein function prediction, and link prediction tasks, on which ours largely outperforms relevant baselines.

Graph Self-supervised Learning with Accurate Discrepancy Learning
Dongki Kim'; Jinheon Backl", Sung Hwang 1.2
KAIST AITRICS", South Korea
cleverki@kaist.co ac. ac.kr, kr, jinheon. baekčkaist.. ac kr, sjawang820kaist.co ac.
Abstract
Self-supervised learning of graph neural networks (GNNs) aims to learn accurate representation of the graphs in an unsupervised manner, to obtain transferable representations of them for diverse downstream tasks. Predictive learning and contrastive learning are the two most prevalent approaches for graph self-supervised learning. However, they have their own drawbacks. While the predictive learning methods can learn the contextual relationships between neighboring nodes and edges, they cannot learn global graph-level similarities. Contrastive learning, while it can learn global graph-level similarities, its objective to maximize the similarity between two differently perturbed graphs may result in representations that cannot discriminate two similar graphs with different properties. To tackle such limitations, we propose a framework that aims to learn the exact discrepancy between the original and the perturbed graphs, coined Discrepancy-basee based Self-supervised LeArning (D-SLA). Specifically, we create multiple perturbations of the given graph with varying degrees of similarity, and train the model to predict whether each graph is the original graph or the perturbed one. Moreover, we further aim to accurately capture the amount of discrepancy for each perturbed graph using the graph edit distance. We validate our D-SLA on various graph-relater downstream tasks, including molecular property prediction, protein function prediction, and link prediction tasks, on which ours largely outperforms relevant baselines!.
1 Introduction
graph, consisting of nodes and edges, a data structure that defines a relationship among objects. Recently, graph neural networks (GNNs) [15, 8, 31, 38), which aim to represent this structure with neural networks, have achieved great successes in modeling real-world graphs such as social networks [5], knowledge graphs [1], biological networks [20], and molecular graphs [36]. However, is extremely costly and time-consuming to annotate every label of the graphs. For example, labeling the properties of molecular graphs requires time-consuming laboratory experiments [11].
Recently, various self-supervised learning methods for GNNs [11, 45, 12, 28] have been studied to overcome this issue of the lack of labeled graph data. The existing self-supervised learning methods can be classified into two categories: predictive learning and contrastive learning. Predictive learning methods [11, 22, 14] aim to learn representations by predicting contexts of graph (Figure 1, (a-1)). However, predictive learning schemes are limited as they consider only the subgraphical semantics. Contrastive learning [32, 27, 42, 46, 43, 37], which is popular self-supervised learning approach in the computer vision field [24, 35, 4, 9], can learn the global semantics by maximizing the similarity between instances (images) perturbed by semantic-invarian perturbations (e.g. color jittering or flipping). Graph contrastive learning methods also use a similar strategy, generating positive examples
"quual Contribution.
1 Coode available at http://gthabbooo/ooodiiinnnnnss
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Local Prediction
Altribute Masking
sim x -1
Discriminator
sim
sim
Local Prediction
sim
(a-1) I) Conventional Predictive learning
(b-1 Conventional Contrastive learning
(c-1) Our Discrepancy- based Leaminng
(a-2) Predictive (AttMMak)) (b-2) Contrastive (GraphCL) (c-2) D-SLA (Ours)
Active
(c) Inactive
Figure I: (a) Conventional predictive learning that aims to predict local attributes by masking them. (b) Conventional contrastive learning that could maximize the similarity of dissimilar graphs perturbed from original graphs. (c) Our discrepancy-basee learning that discriminates an original graph from perturbed graphs by capturing global semanties of them unlike predictive learning, but also that reflects the amount of discrepancy across original, perturbed, and different graphs, unlike contrastive learning. (a,b,e-2) Graph embedding visualization trained by cach self-supervised learning scheme. (d),(e) Motivation: A pitfall of contrastive learning methods, which assumes two similar graphs as the same, despite of their different properties.
with edge perturbation, attribute masking, and subgraph sampling, and then maximizing the similarity between two differently perturbed graphs from the original graph (See Figure I, (b-1)).
However, is it always correct to assume that the perturbed graphs by such perturbations will preserve the semanties of the original graph? In computer vision, there exists set of well-defined perturbations, that does not change the human perception of the given image. However, in contrast to images that reside in a continuous domain, graphs are discrete data structures by nature, and thus their properties could become completely different even with slight perturbations. For example, two molecules in Figure (d) and (e) show that, although they have highly correlated structure, one molecular graph could be actively bound to set of inhibitors of human 3-secretase [34), whereas the other is not. In this case, existing contrastive learning with perturbations may lead the representations for two semantically dissimilar graphs to collapse into the one representation (See Figure I (b-2)).
To tackle this problem, we propose a novel self-supervised learning method which aims to learn the discrepancy between graphs, which we refer to as Discrepancy-basee Self-supervised LeAming (D- SLA). Specifically, we first perturb the given graph similarly as with contrastive learning schemes, but instead of maximizing the similarities across the perturbed graphs as done with contrastive learning, we aim to learn their discrepancies. To this end, we first introduce discriminator which learns to discriminate real graphs from the perturbed ones (See Discriminator in Figure 1, (c-1)). This allows the model to learn small differences that may largely impact the global property of the graph, as illustrated by the example in Figure/ (d) and (e). However, simply knowing that two graphs are different insufficient, and we would want learn the exact amount of discrepancy between them. Notably, with our perturbation scheme, the exact discrepancy can be trivially obtained since the graph edit distance [23] is automatically derived as the number of edges we perturb for given graph. Then, we enforce the embedding
difference between original and perturbed graphs to be proportional to the graph edit distance (See dotted circles in Figure I (c-1)). Finally, to discriminate the original and perturbed graphs from the completely different graphs, enforce the relative distance of the latter to be larger than the former, by a large margin (See blue arrows in Figure 1, (c-1)).
This will enable our D-SLA to capture both small and large topological differences (See Figure 1 (c-2)). Thus, our framework can enjoy the best of both worlds for graph self-supervised learning: predictive and contrastive learning. The experimental results show that our model significantly outperforms baselines, especially on the datasets where graphs with different properties have highly correlated structures, demonstrating the effectiveness of ours. Our main contributions are as follows:
We propose novel graph self-supervised learning framework with a completely opposite objective from contrastive learning, which aims to learn to differentiate a graph and its perturbed ones using discriminator, as even slight perturbations could lead to completely different properties for graphs.
Utilizing the graph edit distance that is obtained for perturbed graphs at no cost, we propose a novel objective to preserve the exact amount of discrepancy between graphs in the representation space.
We validate our D-SLA by pre-training and fine-tuning on various benchmarks of chemical, biology, and social domains, which it significantly outperforms baselines.

---

2
Related Work
We now briefly review the existing works on graph neural networks (GNNs), and self-supervised learning methods for GNNs including predictive and contrastive learning.
2.1 Graph Neural Networks
Most existing graph neural networks (GNNs) could be formulated under the message passing scheme [7], which represents each node by firstly aggregating the features from its neighbors, and then combining the aggregated message with its own node representation. Different variants of update and aggregation functions have been studied. To mention a few, Graph Convolutional Network (GCN) [15] generalizes the convolution operation in a spectral domain of graphs, approximated by the mean aggregation. GraphSAGE [8] concatenates the representations of neighbors with its own representation when updating the node representation. Graph Attention Network (GAT) [31] considers the relative importance among neighboring nodes for neighborhood aggregation, which helps identify relevant neighbors for the given task. Graph Isomorphism Network (GIN) [38] uses the sum aggregation, allowing the model to distinguish two different graphs as powerfully as the Deisfeiler-Lehman (WL) test [17]. While GNNs have achieved impressive results on various graph- related tasks, the trained representations from one dataset are usually not transferable to different downstream tasks. Moreover, labels of such trientrde data are often scarce, especially in scientific domains (e.g.. chemistry and biology) [11]. Thus, in this work, we aim at obtaining transferable representations of graph-structured data with self-supervised learning, without using any labels. Self-supervised learning for GNNs can be broadly classified into two categories: predictive learning and contrastive learning, which we will briefly introduce in the following paragraphs.
2.2 Predictive Learning for Graph Self-supervised Learning
Predictive learning aims to learn contextual relationships by predicting subgraphical features, for example, nodes, edges, and subgraphs. Specifically, Hu et al. [11] propose predict the attributes of masked nodes. Also, Hwang et al. [13] and Kim and Oh [14] propose to predict the presence of an edge or path with the link prediction scheme. Furthermore, Hu al. [12] and Rong et [22] propose to predict the generative sequence, contextual properties, and motifs of the given graphs.
However, the predictive learning methods are limited in that they may not well capture the global structures and/or semantics of graphs.
2.3 Contrastive Learning for Graph Self-supervised Learning
The limitations of predictive learning gave rise contrastive learning methods, which aim to capture global graph-level information. Early contrastive learning methods for GNNs aim to learn the similarity between the entire graph and its substructure, to obtain the representations for them without using any perturbations [32, 27]. Despite their successes, to further expand the embedding space of model, contrastive learning methods have been actively studied with perturbation methods such as attribute masking, edge perturbation, and subgraph sampling [42. 46, 33, 43]. Recently proposed adversarial methods further generate positive examples either by adaptively removing the edges [29] or by adjusting the attributes [40]. Further, Xu et al. [39] aim to cluster graph representations via contrastive learning, and Thakoor et al. [30] propose a memory-efficient method for large-scale graph representation learning. However, while contrastive learning allows learning the global semantics with perturbed graphs, there exists a potential risk where the model can consider two dissimilar graphs as the same (See Figure I (b). (d), and (e)), due to the discrete nature of graphs. Contrarily, our novel pretext task of predicting the correct graph from multiple choices, which includes both slightly perturbed graphs and strongly perturbed graphs, allows the model to learn the correct relationships among local elements, but also learn the global graph-level differences.
Method
In this section, we introduce our novel graph self-supervised learning framework, Discrepancy- Self-supervised LeArning (D-SLA), which is illustrated in Figure 2. Specifically, we first recount the notion of graph neural networks and existing graph self-superviser learning in section 3.1. Then, we introduce each component of our D-SLA in Section 3.2, 3.3, and 3.4, respectively. After that, we finally describe the overall framework that combines all three components in Section 3.5.
3

---

Fy Gioph)
Ga 1
Node Meskena
Drainal Portured Fertubed Partubed
Fdge
Graph Discrminator
Nade Altribuute bubtibbbbee Sarkkin
Graph Encoding
Edite
Resition Dalitinn
Enge
G2
6''s 450-
4-3
Other graphs
seme
Distance- Leariin
Figure 2: Illustration of our overall framework (D-SLA), We perturb the original graph by adding or deleting edges, where the discrepancy between original and perturbed graphs is defined by graph edit distance [23]. Then, we mask the node attributes to make more difficult to distinguish original and perturbed graphs. After that, we learn GNNs to distinguish perturbed graphs from original ones, but also accurately discriminate the original. perturbed, and other graphs on the embedding space with their distances.
3.1 Preliminaries
Graph Neural Networks A graph 9 can be defined by four components: G
where V is the set of nodes, is the set of edges, Xy IR V is the matrix of node features, and XS E [R(E|xdd the matrix of edge features, where d and d' are the dimensionalities of node and edge attributes, respectively. Let he be representation of node and hgg be a representation of graph g. Then, the goal of graph neural networks (GNNs) is to represent nodes of the given graph by leveraging its topological structure. To be specific, GNNs learn node representations (i.e., h.) by iteratively aggregating messages from their neighbors in a layer-wise manner, which is usually referred to as message-passing [7] and formally defined as follows:
h(+1) = 1 ( (f : E(()))))
where 1 denotes an update function that updates a representation of the given node along with its neighbors' representations, 1² denotes an aggregate function that aggregates messages from the node's 's neighbors, (1x) denotes a set of neighbors of the node u, and I denotes l-th layer of GNNs.
To further obtain the representation for an entire graph, we usually summarize all node representations from Equation into a single embedding vector with a permutation-invarian function fn as follows:
lg fn [1 Ve voev))
((
While natural choice of fR is simple operations, such mean or sum, various graph representation learning methods have been recently studied to accurately capture the entire graph information, including node clustering based [41, 2], and node drop based methods [6. 16).
Contrastive Learning for Self-supervised Learning of GNNs We now describe why contrastive learning fails to distinguish two topologically similar graphs yet having completely different properties. In particular, contrastive learning aims increase the similarity between positive pairs of graphs while increasing the dissimilarity between negative pairs [42, 46, 43). Thereat, to define positive pairs, they perturb the original graph by manipulating edges, masking attributes, and sampling subgraphs, and then consider the perturbed graphs as the same as the original graph. On the other hand, they consider other graphs in the same batch as dissimilar. Formally, for the perturbed graphs G, and Gj from the original graph Go. the objective of contrastive learning is defined as follows:
fhi.(hg. lgg,)
LeL = log Ee, S' fhm.(hg.,
where G' is the other graph in the same batch with the graph Go. which is also referred as negative graph. Therefore, Ga and G5 are positive pair, whereas, G, and G' are negative pair. faim denotes a similarity function between two graphs, for example, L2 distance or cosine similarity. By minimizing the objective in Equation 3, existing contrastive learning methods closely embed two perturbed graphs G and Gj: 9; ~ G,. However, as the perturbations may not preserve the properties of the given graph due to the discrete nature of graph-structured data, they indeed should not be similar: G. o Gj (See Figure (d) and (e)). To this end, we propose new objective that can differentiate between the original graph and its perturbations, which we describe in the next subsection.

---

3.2 Diserepancy Learning with Graph Discrimination
We now introduce novel graph supe-suee learning objective to preserve the discrepancy between two graphs in the learned representation space, for which we then describe the perturbation scheme to generate augmented graphs from the original graph.
Discriminating Original Graphs from Perturbed Graphs Contrarily to contrastive learning that trains perturbed graphs to be similar, our goal is to distinguish the original graph from perturbed graphs, by predicting the original graph among original and perturbed graphs, which we term as the original graph discrimination (See Graph Discriminator in Figure 2). Let Go be an original graph, and Gú be a perturbed graph with i 2 1. Then objective of our discrimination scheme is as follows:
30
LGD = -o e:0
with S fs(hc),
e.
where Sk is a score of the graph 9r. obtained from learnable score network fs of the discriminator, i.e. fs hg + S E R. By training to discriminate the original graph from the perturbed graphs, the model enforced to embed the perturbed graphs apart from the original graph (Figure (b)). Therefore, the model learned by our discrimination scheme will be capable of distinguishing even the slight differences between the original graph and its perturbations, as well as be capable of capturing the correct distribution of the graphs, since perturbed graphs could be semantically incorrect.
Perturbation The remaining question how to perturb the graph generate negative examples (i.e., G.). We aim at adding or deleting the subset of edges in the given graph, and thus such perturbed graphs are slightly different from the original graph but also could be semantically incorrect. Again, in this way, since our graph discrimination objective in Equation 4 discriminates the original graph from slightly perturbed graphs, the graph-level representations from our pre-trained GNNs can capture subtle difference that may have a large impact on the properties of graphs, for downstream tasks.
In particular, our perturbation scheme consists of the following two steps: 1) removing and adding small number of edges, and 2) masking node attributes (Figure 2). To be specific, given an original To do so, we first
graph G (V, E, Ny, Xg), we aim perturb it times, obtain (..,,..,. manipulate the edge set & by removing existing edges as well as adding new edges on it and then adjust its corresponding edge matrix Xg. After that, we further randomly mask the node attributes on Ny for both original and perturbed graphs. to make it more difficult to distinguish between them. Formally, the original and perturbed graphs from our nodeledge perturbations are obtained follows:
Go = (V. -v==(ve,, E
Kz). 2 (()).
(5)
g (,. E4 Ag. x22 X M()), (E" ~ PP())
where M and are the node masking and edge perturbation functions, respectively. The scores of original and perturbed graphs are then computed with the score function fs: [So. Si,..,, = [fs(Go), fs(91),..,, fs.])) which are then used for our previous learning objective in Equation 4.
3.3 Learning Discrepancy with Edit Distance
While the learning to discriminate original and perturbed graphs described in Section 3.2 allows the model to learn the discrepancy between original and perturbed graphs by embedding them onto different points, it cannot learn how dissimilar the perturbed graph is from the original one as all perturbed graphs are considered equal (Figure 3 (b)). Thus, to further learn the accurate discrepancy among different graphs, here we introduce a method for efficiently computing the graph discrepancy between original and perturbed graphs leveraging the graph edit distance [23]. Then we describe how to preserve the calculated discrepancy in the learned graph representation space.
Graph Edit Distance To preserve the exact amount of discrepancies between original and perturbed graphs in the leameed representation space, we first need to measure the graph distance. Graph edit distance, which is widely used to measure the dissimilarity between two graphs [23], is defined by the number of insertion, deletion, and substitu- tion operations for nodes and edges, to transform one graph into the other graph. Although computing
Table 1: Costs for calculating distance, with
edges and h iterations for WL-kernel [25].
Methods
Costs
edit [23]
NP-hard [4] (fuw)
Weisfeiler- chhman kernel [25]
Graph edit distance with our perturbation
O(1)
5

---

Oegiss Notureed
(a) RRRaddolyy
(b) CoD
(c) CoD + Cedit
(d) LCD + feest + fmmrrii
Figure 3: Visualizations of the graph embeddings to see the effect of each loss for our D-SLA. We represent the
level of perturbations via the transparency of color, i.c., the stronger the perturbation, the lighter the color.
the graph edit distance is the NP-hard problem [44], for our case, it is trivially obtained without any cost. This is because, for each perturbed graph, we know the exact number of edge addition and deletion steps as we have generated it using the same process. In other words, the number of added and deleted edges is simply the edit distance between original and perturbed graphs. This brings us significant computational advantages, as we generally require a significant amount of costs for calculating or estimating the distances between two graphs, as shown in Table 1. Note that although several existing works [18, 3] leverage graph edit distance, they are completely different from our work since they are neither self-supervised learning methods nor leverage the graph perturbation.
Distance-based Discrepancy Learning Based upon the graph edit distance, we design the regular- ization term to learn the exact amount of differences between original and perturbed graphs over the embedding space. To be specific, we regularize the model to learn that the embedding-lewwe difference between original and perturbed graphs is proportional their actual graph edit distance (i.e., if the edit distance between two graphs is large, then they are far away in the embedding space, whereas, if it is small, then they are close each other) as shown in Distance-based Learning of Figure
We first let an original graph Go be an anchor graph, then a graph edit distance and an embedding- distance between the anchor graph Go and the perturbed graph G. are defined e, and d,, respectively. With such notations, to achieve our objective of learning an exact amount of discrepancy across original and perturbed graphs, we formalize our edit distance-based regularization loss as follows:
d di (4_ i.j E, eg
Ledst Σ
with d, = famr(ho. hg.). )
(6)
where faitt measures the embedding-Ievel differences between graphs with L2-norm. We find that Equation 6 can capture the exact amount of differences as shown in Figure 3 (c). Note that Equation 6 alone does not work as shown in Table 5, since the trivial solution of Equation 6 is to set all the embedding-leeed distance between original and perturbed graphs as zero (i.e., d; 0 Vi). However, learning the accurate amount of discrepancy without the trivial solution is feasible by jointly training with the objective of original graph discrimination in Equation 4 where the model should differently embed Go and G; to discriminate them. Furthermore, as we can generate different levels of perturbations according to the graph edit distance, our graph embedding space can interpolate between two different graphs, for example, weakly and strongly perturbed graphs in terms of their actual distances, unlike previous predictive and contrastive learning methods.
3.4 Relative Discrepancy Learning with Other Graphs
Thus far, we aimed toward distinguishing the perturbed graphs from the original graph in Section 3.2, with their actual edit distance-based discrepancy learning in Section 3.3. However, such schemes alone will not allow the model to learn the discrepancy between two completely different graphs (Figure (c)). While one might consider learning the discrepancy between original and its negative graphs (other graphs in the same batch) with their graph edit distance, is impractical as computing the edit distance between completely different graphs is NP-hard [44]. Thus, we instead propose to learn a relative distance, exploiting the assumption that the distance between original and negative graphs in the same batch is larger than the distance between original and perturbed graphs with some amount of margin (See Figure 2, Distance-based Learning). The usage of margin is highly beneficial learning framework, since, if the negative graphs are far apart than the amount of margin plus the distance between original and perturhed graphs, the model does not attract the perturbed graphs the original graph, therefore not losing the discrepancy learned in Equation
for our discrepancy-
Formally, we realize the relative discrepancy learning with the triplet margin loss as follows:
Emargin
max(O, a + d, dz),

---

where d; is the distance between original and its perturbed graphs: d; = Fain(hg,, hg,), d' is the distance between original and its negative graphs: d' = faar(ho hg;;) with g' as in-batch negative graphs, and a > 0 as margin hyperparameter. In this way, we can allow the model to learn that, for the original graph, negative graphs are more dissimilar than the perturbed graphs, while perturbed graphs are also marginally dissimilar to it with the amount of edit distances shown in Figure 3 (d).
3.5 Overall Framework
To sum up, our D-SLA framework aims to learn a graph representation space which preserves the discrepancy among graphs. Our graph discriminator described in Section 3.2 helps learn space that can discriminate even the slightly perturbed graph from its original graph (Figure 3 (b)). Then, the discrepancy learning with graph edit distance described in Section 3.3 (Figure 3 (c)) enforces the embedding space to preserve the exact discrepancy among graphs. Finally, the margin-based triplet constraints between the perturbed and completely different graphs Section 3.4 allow the learned embedding space to capture the relative distance between graphs (Figure 3 (d)). Our overall learning objective, dubbed as Discrepancy-basse based Self superviedd LeArnnng (D-SLA), is given as follows:
L + Ce + X2hmargin:
where hyperparameters Å and A2 are scaling weights to each loss. Note that, unlike predictive learning [11] which aims to capture local semantics of graphs by masking and predicting local components, such as nodes and edges, our D-SLA learns the graph-level representations where the subtle differences corner regions of different graphs could be captured by distinguishing original and perturbed graphs. Moreover, our D-SLA can discriminate differently perturbed graphs having different properties, unlike contrastive learning [42, 43] that considers them as similar.
Experiments
In this section, we first experimentally validate the proposed Discrepancy-basee Self-supervised LeArning (D-SLA) on graph classification tasks to verify its effectiveness in obtaining accurate graph-level representations. After that, we further evaluate our D-SLA on link prediction tasks for which capturing the local semantics of graphs is important.
4.1 Graph Classification
Accurately capturing the global semantics of given graphs is crucial for graph classification tasks, on which we validate the performance of our D-SLA against existing baselines.
Experimental Setup We evaluate our D-SLA on two different domains: the molecular property prediction task from chemical domain [34, 10] and the protein function prediction task from biological domain [1 1]. For the chemical domain, we follow the experimental setup from You al. [43], whose goal is to predict the molecules" biochemical activities. For the self-supervised learning, we use 2M molecules from the 7INC15 dataset [26]. Then, after the self-supervised learning, we perform fine-tuning on datasets from MoleculeNet [34] to evaluate the down-stream performances of models. For the biological domain, we follow the setup from You et al. [43], for which the goal is to predict the proteins' biological functions. For pre-training and fine-tuning,
use the dataset of PPI networks [47]. We use the ROC-AUC value as an evaluation metric, and report the average performance over five different runs following Xu et al. [39]. See Appendix A.2 for dataset details.
Models We compare our D-SLA against predictive learning baselines: EdgePred [8], AttrMask- ing [11] and ContextPred [11], and contrastive learning baselines: Infomax [32], GraphCL [42], JOAO [43], GraphLoG [39], and BGRL [30]. Detailed explanations of models including baselines and ours are provided in Appendix A.I.
Implementation Details We follow the conventional experimental setup of graph self supervupee learning from Hu al. [11], where we use the GIN [38] as the base network. For pre-training of our model, we perturb the original graph three times. To be specific, to obtain the perturbed graphs from the original graph, we first randomly select subgraph of it, and then add or remove edges in the range of (20%, 40% 60%) over the sampled subgraph. For fine-tuning, we follow the hyperparameters from You et al. [43]. We provide additional details in Appendix A.2.
7

---

Table 2: Fine-tuning results on graph classification tasks of chemical and biological domains. Best performances are highlighted in bold. The reported results are taken from You al. [43] and et al. [39]. except for the BGRL results and the PPI performance of GraphLoG as they are not available.
SSL mechank
BBBP
ClinTox
MUV
HIV
BACE
SIDER
Tos21
TosCist
PPI
Arg.
No Pretmin
65..1445
58.0
71.8 25
75.3
20.1 5.4
57.3 1 1.6
74.0 1 088
63.4 1 0.6
66.8 1 1,0
66.72
Podkite
Edgepred
2.4
76.3
79.9
0.7
65.7
69.77
ArmMaskig
64.3 + 2.8
718 4.1
747++14
72. 1.1
79.3 1.5
6..0++0.7
76.7+
6..2+00.
652 653++1. 1.6
70.49
CoticuPPed
68.0
1.7
77.3+:1000
75.7 0.7
63.
1,3
Infomex
1888:00..
69. +
2.
0.
75.
58.4 0.8
75.3 0.5
62.7
64.1
69.60
GrsphCLL
09.68 0:07 0.67
75.99 à: 2,65
69,80 a: 2.66
78.47 d: 1.22
75.38 d: 1.44
61.53 a 0.58
73887 a 0.66
62.40 à: 0.57
67.88 à 0.85
70.44
Dannakee
JOAD
$1.32
2,49
71.66
76.73
1.23
77.34
59.97
74.98 0.29
62.94
71:07
10ADv2
71.39:
$0:97
+ 1.64
73.67
= 1.000
77.51
1.17
75.49
+: 1.27
60 = 0.74
74.27
0.62
63.16
+ 0.45
63.94 # 1.99
71.21
GraphLooi
4:8
76.7
76.0 1.1
77.8
0.8
83.5
61.2 1.1
75.7
63.5
72.65
RCRRL
66.73 +: 1,70
64.74 + 6.46
69.36
75.52
1.85
71.27 + 5,48
60.41
74.83
0.74
63.20
0.76
64.00
67.86
D SLA (Ouna
72,00 0.79
80.17 1 1.50
7666 a 0.91
78,59
0.44
83.81 1: 1.01
60.22 a 1.13
76811 0.52
64.24 1 0,50
71.56 1 0.46
7385
Dataset
Act. Sim.
Insct. Sim.
0.6743
HIV
0,4186
0.4516
MUV
0.1946
0.4881
Active Malocules
3.307
TonCast
SIDER
00.2800
0.2962
0.2316
Anchar Molcruic
Clinlox
00.2225
0.22774
00.9963
Inactiv Molecules
Table 3: Tanimoto simi- Figure 4:
Visualization of molecules in BACE, where the active and inactive larity on chemical bench- molecules in the top and bottom sides the most similar ones the molecule in the left, according to the Tanimoto similarity.
mark datasets.
Results Table 2 shows that our D-SLA achieves the best average performance against existing predictive and contrastive learning baselines on tasks from both chemical and biological domains, demonstrating the effectiveness of our discrepancy- based framework. To better see what aspects of D-SLA contribute to the performance improvements, we perform in-depth analyses of each dataset, and how our model can effectively handle the task on it, in the next paragraph.
Analysis To analyze whether the structural similarity of molecules is correlated to their biochemical activities, we measure the inherent discrepancy of graphs with the Tanimoto similarity over Morgan fingerprints [21]. To be specific, we first iteratively sample an anchor molecule among active molecules in the dataset, and then measure the average Tanimoto similarities of the five most similar active/inactive molecules. In other words, the high similarity values of Inact. Sim. in Table 3 suggests that the molecules have highly overlapped structures regardless of their biochemical activities. For example, as shown in Table 3, the molecules in the BACE dataset are highly correlated, although their activities are different. Also, we further observe that, as shown in Figure 4 that visualizes the most similar active/inactive molecules with respect to the certain anchor molecule in the BACE dataset, the structures between active and inactive molecules are highly similar.
From the above observations, we suggest that, due to the discrete nature of graphs, two slightly different graphs can have completely different properties, which may be the reason for the performance degeneration of contrastive learning methods in Table 2 which consider perturbed graphs similar while they might not be the semantically same - on such particular datasets (c.g.. BACE, MUV, Tox21, ToxCast) having the high Inact. Sim. scores in Table 3. However, our D-SLA largely outperforms contrastive learning baselines on them?, because ours not only discriminates an original graph from its perturbations but also can learn their exact discrepancy via the graph edit distance. We note that our method shows the competitive performance on Clin'Tox and SIDER in Table 2, since they have the lowest structural similarities across different biochemical properties, for which contrastive learning could be effective. We provide more analysis in Appendix B.I.
4.2 Link Prediction
Accurately capturing the local semantics of a graph is an important requisite for solving node/edge- level tasks. Thus, we further validate our D-SLA on the link prediction task.
Experimental Setup
We conduct link prediction experiments on social network datasets - COL- LAB, IMDB-B, and IMDB-M from the TU benchmarks [19]. We separate the dataset into four parts: pre-training, training, validation, and test sets in the ratio of 5:1:1:3. We use the average
*GraphLoG also adopts the predictive learning scheme by matching the locally masked nodes/subgraphs to their original substructures, thus it shows decent performances on such high similarity datasets.
8

---

SSL Methed
COLLAB
IMDB-B B
IMDS M
AVE.
W. Apprittm
WL Algontti
No Proimin
9001
1.14
2.58
64.93
1.92
SLA
ContesPred
AltMakkingg
83:96
S1AS 0.50
4. 0.75
30,62
70.47
0: 3,66
2.24
63.37
65.09
2:15
+ 2.74
71.81
73.51
Graphiat
BGRL
Gruphlod
BGal
Informa
0.62
67
1.87
2.47
71.02
CroshCL
Grapha
70,04
1.04
03.71-
2.6
62.40
4 3.4
67:36
Infomme
Infommx
10AD
76.57
Corkeet
Contaci
GrggaLoG
01.88
01:71
3.18
64.58
1.7
72.51
BOKL
75.79
1.13
67.97
4.24
63.71
1 2.00
89.40
EdyoProd
bdgaitred
Average Rank Confiicint of 2INCI5
Average Rank Coult dent of gws
Table 4: Link prediction results on the social
Figure 5: Rank correlation cnefficient of 1,000 graphs from ZINC15 and QM9 datasets, measuring the coefficient between the actual similarity ranks and the calculated similarity ranks, between original and perturbed graphs.
network datasets. The reported results are the average precision, and the bold number denotes the best performance on each datasct.
precision as an evaluation metric, and report the results over five different runs. We provide more details in Appendix A.3.
Implementation Details tion, we add or delete only a tiny amount of edges (c.g. or 2 edges) while increasing the magnitude of perturbation to obtain three perturbed graphs. Note that we do not use the margin triplet loss in Section 3.4, since for local prediction tasks, the graph-level discrepancy learning between completely different graphs is not much helpful in capturing local semantics. For fine-tuning we train the GNNs to predict whether there is an edge between nodes, and evaluate the GNNs for predicting the existence of 10 edges. For more implementation details, please see Appendix A.3.
For GNNs, we use the GCN [15] following You et al. [43]. For perturba-
As shown in Table 4, predictive learning baselines outperform other baselines, since it learns predict local node/edge attributes. However, our D-SLA largely outperforms all baselines, while it aims to discriminate graph-level representations though. We suggest that this is because ours can capture subtle differences of graphs by leveraging the graph edit distance, demonstrating that accurate discrepancy learning is obviously useful for the local link prediction task.
Results
4.3 Analysis
In this section, we further analyze the efficacy of our D-SLA, We provide the additional experimental details in Appendix A.4.
Rank Correlation Coefficient To see whether learned representations capture the exact amount of discrepancy, we compare the ranks of the calculated vs actual similarities between original and perturbed graphs with Spearman's rank correlation coefficient. Note that the results of the WL algorithm [17] are merely a performance indicator of discriminative power since it cannot obtain representations that generalize to downstream tasks. As shown in Figure 5, unlike baselines that mostly fail to discriminate different graphs, our D-SLA has the discriminative power that is on par with the powerful WL algorithm, while ours can generalize to downstream tasks shown in Table 2.
Ablation Study To see how much each component contributes to the performance gain, we conduct an ablation study. As shown in Table 5, we observe that our graph discrimination task (LeD) significantly improves the performance on stremmttmmmmmmm tasks against no-pretraining. However, leveraging the exact edit distance alone (Lodit does not learn meaningful representations, since the model trivially sets all the distances between original and its perturbations as zero, as discussed in Section 3.3. Also, we further obscrve that each component of distance- based learning in Section 3.3 and 3.4 helps to improve the performance, verifying that accurate discrepancy learning with edit and relative distances is important for modeling graphs. We further discuss the ablation study in Appendix B.2.
Table 5: Ablation study for D D-SLA on graph classification and link prediction tasks.
Eep fodu Conrg ClinTox BACE,
COLLAB
58,00
70.30
71.21
70.33
$1.58
34:23
57.46
69.99
72.61
77.48
83.55
76.19
80.17
83.81
Embedding Visualization We visualize the embedding space from various pre-training methods: predictive, contrastive, and ours, in Figure (a.b,c-2). We observe that predictive learning cannot capture the global graph-level similarity well, as it aims to predict subgraphical semantics of graphs during the pretext task. While contrastive learning can closely embed the highly similar graphs to the original graph, it cannot accurately capture the exact amount of discrepancies among perturbed graphs. Contrarily, our D-SLA can accurately distinguish between the original, perturbed, and negative graphs, while accurately capturing the exact amount of discrepancy for the perturbed graphs.

---

5 Conclusion
In this work, we focused on the limitations of existing self-supervised learning for GNNs: predictive learning does not capture the graph-level similarities; contrastive learning might treat two semantically different graphs from perturbations as similar. To overeome such limitations, we proposed a novel framework (D-SLA) that can learn the graph-level differences among different graphs while also can learn the slight edge-wise differences, by discriminating the original from perturbed graphs. Further, the model is trained to differentiate the target graph from its perturbations and other graphs, while preserving the accurate graph edit distance, allowing the model to discriminate between not only two structurally different graphs but also similar graphs with slight differences. We validated our D-SLA on 12 benchmark datasets, achieving the best average performance. Further analysis shows that learns discriminative space of graphs, reflecting the graph edit distances between them.
6 Limitation and Potential Societal Impacts
In this section, we discuss the limitation and potential societal impacts of our work.
Limitation In this work, we propose graph self-supervised learning framework, which aims to learn the discrepancy between the original and perturbed graphs, by discriminating the original graph among the original and its perturbations, but also by learning the exact amount of discrepancy across them with the graph edit distance. Note that, while our perturbation scheme can easily make the slight structural differences, it cannot be aware of the semantic differences across differently perturbed graphs, since the graph semantics depend on the target domain. In other words, nodes and edges could differently contribute to the graph semantics depending graphs or social networks), which are hard to pre-define in one framework. As manually annotating the semantic differences across different graphs is impossible do in an end-to-end fashion, one may need to devise a clever way to be aware of the semantics of graphs for further reflecting the exact semantic difference in the embedding space, which we leave future work.
the target graph domain (e.g., molecular
Potential Societal Impacts Discovering de novo drugs is significantly important to our society since they can be used for curing disease or enhancing agricultural production, that is directly related to our life. However, it is extremely costly and time-consuming to design drug candidates and validate them, requiring immense lab experiments and labor. In this work, we verify our proposed method in the graph classification task in Table 2 of the main paper, and ours outperforms the other baselines for classifying toxicity on the Tox21 and ToxCast datasets. We strongly believe that such aspects of our method can positively contribute to our society in developing valuable drugs. However, when validating the toxicity of the most acceptable drug candidates, someone might badly use our method to reduce the money and time (i.e., does not check the toxicity of drugs for reducing costs, however, which may be used for clinical trials to humans), which can negatively affect our society. We sincerely hope that our method would not be utilized for such a bad purpose.
7 Acknowledgements and Disclosure of Funding
We thank anonymous reviewers for their constructive feedback. This work was supported by Institute of Information & communications Technology Planning & Evaluation (IIPP) grant funded by the Korea government (MSIT) (No.2019-0-000) --000-00755. Artificial Intelligence Graduate School Program (KAIST), and 2021-0002008, Artificial Intelligence Innovation Hub), the Engineering Research Center Program through the National Research Foundation of Korea (NRF) funded by the Korean Government MSIT (NRF-201 8R A5A 1059921), ), Samsung Electronics (10201214-081455 the HPC Support Project funded by the Ministry of Science and ICT and NIPA.
and
10

---

References
[1] Jinheon Baek, Dong Bok Lee, and Sung Ju Hwang. Learning to extrapolate knowledge: Trans- ductive few-shot out-of-graph link prediction. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[2] Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representations (ICLR), 2021.
[3] Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-baat based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020.
[4] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
[5] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Yihong Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference (WWW), 2019.
[6] Hongyang Gao and Shuiwang Ji. Graph u-nets. In Proceedings of the International Conference on Machine Learning (ICML), 2019.
[7] Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the International Conference on Machine Learning (ICML), 2017.
[8] William L.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[9] Kaiming He. Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[10] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[11] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[12] Ziniu Hu, Yuxiao Dong, Kuansan Wang. Kai- Wei Chang, and Yizhou Sun. GPT-GNN: genera- tive pre-training of graph neural networks. In Conference Knowledge Discovery and Data Mining (KDD), 2020.
[13] Dasol Hwang, Jinyoung Park, Sunyoung Kwon, Kyung-Min Kim, Jung- Woo Ha, and Hyun- woo Kim. Self-supervised auxiliary learning with meta-paths for heterogeneous graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[14] Dongkwan Kim and Alice H. Oh. How find your friendly neighborhood: Graph attention design with self-supervision. In International Conference on Learning Representations (ICLR), 2021.
[15] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[16] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In Proceedings of the International Conference on Machine Learning (ICML., 2019.
[17] AA Leman and B Weisfeiler. reduction of graph to a canonical form and an algebra arising Informatsiya, 129): 1968.
during this reduction.

---

[18] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity graph structured objects. In International Conference on Machine Learning (ICML), 2019.
[19] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. arXiv preprint, arXiv:2007.08666 2020.
[20] Giulia Muzio, Leslie O' O'Bray, and Karsten M. Borgwardt. Biological network analysis with deep learning. Briefings Bioinform., 1212)151--1530, 2021.
[21] David Rogers and Mathew Hahn. Extended--onnecctvtty fingerprints. J. Chem. Inf. Model., 50 (5):742-754, 2010.
[22] Yu Rong. Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Sepf-super graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[23] Alberto Sanfeliu and King-Sun Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE transactions systems, man, and cybernetics, (3):353-362, 1983.
[24] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: unified embedding for face recognition and clustering. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2015.
[25] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[26] Teague Sterling and John Irwin. Zine 15 - ligand discovery for everyone. Journal of chemical information and modeling, 55, 10 2015. doi: 10. /accs.ccim.bb00555
[27] Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In International Conference on Learning Representations (ICLR), 2020.
[28] Qingyun Sun, Jianxin Li, Hao Peng. Jia Wu, Yuanxing Ning, Philip S. Yu, and Lifang He. SUGAR: subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism. In The Web Conference (WWW), 2021.
[29] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. arXiv preprint arXiv:2106.0588 2021.
[30] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representations (ICLR), 2022.
[31] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, In International Conference on Learning Representations (ICLR), 2018.
[32] Petar Velickovie, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. International Conference on Learning Representations (ICLR), 2019.
[33] Yuyang Wang, Jianren Wang. Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learning of representations via graph neural networks. Nature Machine Intelligence, 4(3): 279-287, 2022.
[34] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 92):513-530, 2018.
12

---

[35] Zhirong Wu, Yuanjun Xiong, Stella X. Yu, and Dahua Lin. Unsupervised feature learning via non con-paametriic instance discrimination. In JEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2018.
[36] Yutong Xie, Chence Shi, Hao Zhou, Yuwei Yang, Weinan Zhang, Yong Yu, and Lei Li. MARS: markov molecular sampling for multi-objective drug discovery. In International Conference on Learning Representations (ICLR), 2021.
[37] Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang. Infogel: Information-aware graph contrastive learning. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[38] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
[39] Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph- level representation learning with local and global structure. In Proceedings of the International Conference Machine Learning (ICML), 2021.
[40] Longgi Yang, Liangliang Zhang, and Wenjing Yang. Graph adversarial self-supervised learning. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[41] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems (Nurrl/S, 2018.
[42] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[43] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In Proceedings of the International Conference on Machine Learning (ICML), 2021.
[44] Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proc. VLDB Endow., 2 2(1):25-36 22, 2009.
[45] Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
[46] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In The Web Conference (WWW). 2021.
[47] Marinka Zitnik, Rok Sosič, Marcus W. Feldman, and Jure Leskovec. Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences, 116(10):4426 4433, 2019. ISSN 0027-042740000 2424.4 doi: 10.10733/pass.81// 1818013116
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We discuss the limitation in Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss the potential societal impacts in Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We provide the results.
code for reproducing
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] We provide the detailed experimental setups in section A of Appendix.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] All of our main results contain variances or standard deviations of multiple runs.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We provide the type of GPUs in Section A of Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]] We uses the public code and data, and we provide the citation and URLs of them in Section A of Appendix.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "qpdmGV6iegN", "reviewer": "Reviewer_yyyE", "summary": "The paper presents a novel self-supervised learning approach on graphs to boost up the performance on downstream graph classification tasks. In many scenarios, two graphs with highly similar structure have remarkably different properties ((i.e. belong to different classes). By design, the classical contrastive learning-based approaches fail to separate out the representations of such similar graphs because they aim to maximize similarity between graphs and their perturbations. To address these limitations, the authors propose a novel approach referred to as Discrepancy-Based Self-Supervised Learning(D-SLA) that comprises of multiple pretext tasks including: i) training a discriminator to distinguish between a real graph and a perturbed variant; ii) learning the exact discrepancy between the original and the perturbed graphs, where the discrepancy is measured as the graph-edit distance. Additionally, increase the discrepancy measure between any two real graphs by introducing a margin factor, thereby enforcing that the original graph is embedded closer to its perturbed variants than any other  similar-looking real graph. The proposed approach outperforms the SOTA approaches from contrastive learning and \npredictive learning literature on on several graph-related downstream tasks, including molecular property prediction, protein function prediction, and link prediction. ", "questions": "1. For ablation study in Table 5, there needs to be another variant where graph-discriminator is turned off, but the discrepancy modeling is on. This will justify the additional utility of graph discriminator over the discrepancy-modeling pretext tasks.", "limitations": "I will encourage authors to discuss more on the possible intuition behind the efficacy of the proposed approach. To my understanding, discrepancy modeling with margin factor for real graphs is indirectly helping the model to identify key features (edges or nodes) that if perturbed, could lead to a valid graph with distinctive properties. Identification of such distinctive nodes/edges could largely aid to the downstream task of graph classification. Is that correct? If so, perhaps authors should clearly articulate this clearly in the paper as it might not be obvious to readers. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The proposed approach is quite plausible and likely to be relevant to biological networks and molecular graphs where two similar graphs could have distinct properties.\n2. The approach outperforms or matches the performance of several baselines from the fields of predictive and contrastive learning approaches on both graph classification and link prediction downstream tasks.\n3. The paper is overall well-written and augmented with informative figures.\n\n\nWeaknesses: \n1. The approach involves a bunch of hyperparameters (e.g. the margin parameter \\alpha, parameters \\lambda_1 and \\lambda_2 to determine the weight of each pretext task in the final objective function, max graph-edit distance considered to generate perturbed graphs). The paper does not include any guidelines on tuning these hyperparameters and how the choice of hyperparameters affect the results.\n\n2. I  am not quite convinced if graph-discriminator pretext task is needed over L_{edit} and L_{margin}. (See my questions on table 5 below). It would be helpful if authors could throw insights on why all the three pretext tasks might be needed.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "c83OwEyH1bn", "reviewer": "Reviewer_3WcA", "summary": "This paper argues that existing graph self-supervised learning methods have some drawbacks. Specifically, predictive learning methods may not capture the global properties of graphs, and contrastive learning methods may not discriminate two similar graphs with different properties. To this end, a framework D-SLA is proposed to learn the exact discrepancy between the original and the perturbed graphs.", "questions": "Please respond to the weaknesses listed above.", "limitations": "Yes. the authors have detailedly discussed the limitations and potential societal impacts in the appendix.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strengths\n>    1. The drawbacks of existing graph self-supervised methods are well analyzed and demonstrated.\n>    2. The visualization experiment shows that the proposed method is quite effective.\n>    3. The provided source codes facilitate the good reproducibility of this work.\n\n- Weaknesses\n>    1. There are also some existing works that do not rely on contrasting perturbed graphs, e.g., [1,2,3]. In this case, the argued drawbacks of existing methods claimed by the authors do not seem to hold.\n>    2. Why use Equation (4) to discriminate original graphs from perturbed graphs? This could be explained more intuitively.\n>    3. The proposed method D-SLA consists of many components and many hyperparameters. The sensitivity of the three key hyperparameters $\\alpha$, $\\lambda_1$, and $\\lambda_2$ should be studied in the main text.\n>    4. Most existing works report AUC and AP scores for the link prediction experiment. This work only reports accuracy.\n\n\n*References*\n\n[1] [arXiv 2022] Augmentation-Free Graph Contrastive Learning\n\n[2] [SIGIR 2022] Are Graph Augmentations Necessary Simple Graph Contrastive Learning for Recommendation\n\n[3] [WWW 2022] A Simple Framework for Graph Contrastive Learning without Data Augmentation\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "ULVLpe7cYqR", "reviewer": "Reviewer_BmqR", "summary": "This paper proposes a discrepancy-based framework to learn graph representations. The framework leverages the discrepancy between 1) the original graph and the perturbed graphs and 2) the original graph with other negative graphs. The discrepancy amount for perturbed graph is defined via graph edit distance, which is easy to obtain by perturbed graph generating process. The discrepancy amount for other negative graphs are defined above a margin. Under such discrepancy hierarchy, the learned graph representations could preserve dissimilarity among graphs accurately. The learned representations could be used for downstream tasks such as graph classification and link predictions in chemical and biological domains or social networks.", "questions": "1. This method has data augmented by generating perturbed graph via eq(5). I wonder is this a common approach for obtaining perturbed graph, or a novel part of this paper? For those contrastive learning method papers which also consider original graph and perturbed graphs, are the perturbed graphs being generated, or being found by calculating graph edit distance? \n\n2. This approach first generates perturbed graphs and defines discrepancy as graph edit distance. Then all the other samples are viewed as negative samples, and eq(7) assumes distance between original graph and negative graph is greater than a margin. This assumes that all the other graphs are very different from the original graph, at least not as some perturbation of original graph. I wonder could it be the case that in real data the graph samples already contains graphs similar to the original graph. For example, in Figure 1, (d) and (e) are two similar graphs in the samples, and the edit distance between (d) and (e) appear to be 1. Based on the proposed method, it will first generates some perturbed graph of (d), and then define distance of (d) and (e) greater than $\\alpha$. In this example, distance(d,e)  > distance(d, perturbed graph of d), is this still a reasonable assumption? How the graph sample (e) different from those generated perturbation of (d)?\n\nIn summary, my question is: how the method differentiate the generated perturbed graphs, and the graphs that are similar to the original graphs in the sample? Will the assumption that all the other graphs are negative samples and have distance at least $\\alpha$ actually disturb learning and makes the learning results worse, when they are actually similar to the original graph? Consider the extreme cases that the graph samples are all perturbations of one graph, what graph representations the proposed method would give?\n\n3. How to choose the number of perturbed graphs n, and if the perturbed graphs samples are large, would the imbalance of two classes (1 vs n) affect the performance of classifier/discriminator?\n", "limitations": "The authors have discussed limitations thoroughly in the supplementary materials. I do not have other to add except the ones listed in Questions and Strengths And Weaknesses sections.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\nThis paper proposes a new discrepancy preserved framework for learning graph representations, addressing limitations in existing literatures that would learn similar representations of two perturbed graphs with different properties. However, I would like to understand the novelty of the framework as how the discrepancy framework is different from redefining the similarity functions, e.g., sim(two perturbed graphs) = graph edit distance, and sim(graph, negative graph) = $\\alpha$ + additional terms, and then use existing methods. Would appreciate if the authors could further clarify it.\n\nQuality:\nThe paper is well written. The experiments are overall comprehensive, and additional analysis support the main points well.\n\nClarity:\nThe methodologies and implementation details are clearly explained in the main article and supplementary material.\n\nSignificance\nAs mentioned in the originality section, this paper uses discrepancy preserved framework to learn graph representations. However, my understanding is that authors define a new similarity function, which leverages the discrepancy among graphs. The significance is not quite obvious, and would appreciate authors' further clarifications.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "0KdXGuPIKVP", "reviewer": "Reviewer_NxMJ", "summary": "This paper studies the problem of self-supervised learning of graph neural networks. The goal is to learn representations for nodes and graphs in an unsupervised manner. The paper studies the limitations of the predictive and contrastive learning methods and proposes a new framework (D-SLA) to incorporate the discrepancy between the original and perturbed graphs in the self-supervised loss. D-SLA is tested for various tasks.", "questions": "1. Tables 2 and 4: how many times did the authors run the model to get the results in these two tables? which results are statistically significant compared to the best baseline?\n\n2. How does the value of $\\lambda_1$ and $\\lambda_2$ in Equation 8 affect the performance of the model? some charts that show the performance of the model for different values of $\\lambda_1$ and $\\lambda_2$ will be helpful.\n\n3. The paper tested the proposed model for link prediction on social networks. However, I find the motivation of the paper to be weak in social networks (and stronger for small graphs like molecules). Why some perturbations in a large social network might drastically change some of its properties?", "limitations": "See weaknesses 1 and 2.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. Self-supervised learning is an important problem that has recently gained a lot of attention. \n\n2. The proposed method is tested on various tasks on several graph benchmarks.\n\n\nWeaknesses: \n\n\n1. The proposed self-supervised loss in Equation 8 mainly focuses on the global information in a graph as Equations 4, 6, and 7 are all defined on the graph embedding level. This might cause the model not to pay attention to local information in the graph.\n\n2. The motivation of the work is based on a pitfall of contrastive learning methods, which assumes two similar graphs (one original and one perturbed version of the original) are the same. The paper proposed using distance-based self-supervised learning which incorporates the distance of two graphs when pushing their embeddings closer or pulling their embeddings apart in the latent space. However, the notion of distance here is a weighted version of the original contrastive learning version:  two similar graphs will still have small distances and be close in the latent space even if some properties of the perturbed graph drastically change from the original graph. Also, it is not clear why a perturbed graph with a distance of two to the original graph should be further apart compared to a graph with a distance of one to the original graph. How can we make sure that graph edit distance is a good proxy for measuring if two graphs should be close or far in the latent space?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept